git.gag.com Git - fw/sdcc/blob - src/SDCCset.c

   1 /*-----------------------------------------------------------------
   2     SDCCset.c - contains support routines for sets
   3
   4     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
   5
   6     This program is free software; you can redistribute it and/or modify it
   7     under the terms of the GNU General Public License as published by the
   8     Free Software Foundation; either version 2, or (at your option) any
   9     later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20     In other words, you are welcome to use, share and improve this program.
  21     You are forbidden to forbid anyone else to use, share and improve
  22     what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24
  25 #include <stdio.h>
  26 #include <malloc.h>
  27 #include <assert.h>
  28 #include "SDCCset.h"
  29
  30 /*-----------------------------------------------------------------*/
  31 /* newSet - will allocate & return a new set entry             */
  32 /*-----------------------------------------------------------------*/
  33 set *newSet  ()
  34 {
  35   set *lp ;
  36
  37   lp = calloc(1, sizeof(set));
  38   if (lp == 0) {
  39         fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
  40         exit(1);
  41   }
  42
  43   lp->item = lp->curr= lp->next = NULL;
  44   return lp;
  45 }
  46
  47
  48 /*-----------------------------------------------------------------*/
  49 /* setFromSet - creates a list from another list                */
  50 /*-----------------------------------------------------------------*/
  51 set *setFromSet (set *lp)
  52 {
  53   set *lfl = NULL ;
  54
  55   while (lp) {
  56     addSetHead(&lfl,lp->item);
  57     lp = lp->next ;
  58   }
  59
  60   return lfl ;
  61
  62 }
  63
  64 /*-----------------------------------------------------------------*/
  65 /* isSetsEqual - are the lists equal, they are equal if they have  */
  66 /*               the same objects & the same number of objects     */
  67 /*-----------------------------------------------------------------*/
  68 int isSetsEqual ( set *dest, set *src )
  69 {
  70     set *src1 = src ;
  71
  72     for (; dest && src ; dest=dest->next , src=src->next) {
  73         if (!isinSet(src1, dest->item))
  74             return 0;
  75     }
  76     if ( !dest && !src)
  77         return 1;
  78     return 0;
  79 }
  80
  81 /*-----------------------------------------------------------------*/
  82 /* isSetsEqualWith - are the lists equal, they are equal if they have  */
  83 /* the same objects & the same number of objects , compare function    */
  84 /*-----------------------------------------------------------------*/
  85 int isSetsEqualWith ( set *dest, set *src , int (*cFunc)(void *,void *))
  86 {
  87     set *src1 = src ;
  88
  89     for (; dest && src ; dest=dest->next , src=src->next) {
  90         if (!isinSetWith(src1, dest->item,cFunc))
  91             return 0;
  92     }
  93     if ( !dest && !src)
  94         return 1;
  95     return 0;
  96 }
  97
  98 /*-----------------------------------------------------------------*/
  99 /* addSetIfnotP - adds to a linked list if not already present   */
 100 /*-----------------------------------------------------------------*/
 101 void *addSetIfnotP ( set **list, void *item)
 102 {
 103
 104     if (isinSet(*list,item))
 105         return item ;
 106
 107     addSetHead(list,item);
 108
 109     return item;
 110 }
 111
 112 /*-----------------------------------------------------------------*/
 113 /* addSetHead - add item to head of linked list                  */
 114 /*-----------------------------------------------------------------*/
 115 void *addSetHead (set **list, void *item )
 116 {
 117     set *lp = newSet();
 118
 119     lp->item = item ;
 120     lp->next = *list ;
 121
 122     assert(lp != lp->item);
 123     *list = lp ;
 124     return item ;
 125
 126 }
 127
 128 /*-----------------------------------------------------------------*/
 129 /* addSet - add an item to a linear linked list                  */
 130 /*-----------------------------------------------------------------*/
 131 void *addSet ( set **list , void *item )
 132 {
 133     set *lp ;
 134
 135     /* item added to the tail of the list */
 136
 137     /* if the list is empty */
 138     if (*list == NULL ) {
 139         lp = *list = newSet();
 140     } else {
 141         /* go to the end of the list */
 142         for (lp = *list ; lp->next ; lp = lp->next );
 143         lp = lp->next = newSet();
 144     }
 145
 146     /* lp now all set */
 147     lp->item = item ;
 148
 149     return item ;
 150 }
 151
 152 /*-----------------------------------------------------------------*/
 153 /* deleteItemIf - will delete from set if cond function returns 1  */
 154 /*-----------------------------------------------------------------*/
 155 void deleteItemIf ( set **sset, int (*cond) (void *, va_list), ... )
 156 {
 157     set *sp = *sset ;
 158     va_list ap;
 159
 160     va_start(ap,cond);
 161
 162     while (sp) {
 163         if ((*cond)(sp->item,ap)) {
 164             deleteSetItem(sset,sp->item);
 165             sp = *sset ;
 166             continue ;
 167         }
 168
 169         sp = sp->next ;
 170     }
 171 }
 172
 173 /*-----------------------------------------------------------------*/
 174 /* deleteSetItem - will delete a given item from the list          */
 175 /*-----------------------------------------------------------------*/
 176 void deleteSetItem ( set **list, void *item )
 177 {
 178     set *lp , *lp1;
 179
 180     /* if list is empty */
 181     if (*list == NULL )
 182         return ;
 183
 184     /* if this item is at the head of the list */
 185     if ((*list)->item == item ) {
 186         lp = *list ;
 187         *list = (*list)->next ;
 188         return ;
 189     }
 190
 191     /* find the item in the list */
 192     for (lp = *list ; lp->next ; lp = lp->next ) {
 193         if (lp->next->item == item ) /* the next one is it */ {
 194             lp1 = lp->next ; /* this one will need to be freed */
 195             lp->next = lp->next->next ; /* take out of list */
 196             return ;
 197         }
 198     }
 199
 200     /* could not find it */
 201     return ;
 202 }
 203
 204 /*-----------------------------------------------------------------*/
 205 /* isinSet - the item is present in the linked list              */
 206 /*-----------------------------------------------------------------*/
 207 int isinSet (set *list, void *item )
 208 {
 209     set *lp ;
 210
 211     for (lp = list ; lp ; lp = lp->next )
 212         if ( lp->item == item )
 213             return 1;
 214
 215     return 0;
 216 }
 217
 218 /*-----------------------------------------------------------------*/
 219 /* isinSetWith - the item is present in the linked list            */
 220 /*-----------------------------------------------------------------*/
 221 int isinSetWith (set *list, void *item , int (*cFunc)(void *,void *) )
 222 {
 223     set *lp ;
 224
 225     for (lp = list ; lp ; lp = lp->next )
 226         if ( (*cFunc)(lp->item,item) )
 227             return 1;
 228
 229     return 0;
 230 }
 231
 232 /*-----------------------------------------------------------------*/
 233 /* unionSets - will return the union of the two lists             */
 234 /*-----------------------------------------------------------------*/
 235 set *unionSets (set *list1 , set *list2, int throw)
 236 {
 237     set *un = NULL ;
 238     set *lp ;
 239
 240     /* add all elements in the first list */
 241     for (lp = list1 ; lp ; lp = lp->next )
 242         addSet(&un,lp->item);
 243
 244     /* now for all those in list2 which does not */
 245     /* already exist in the list add             */
 246     for (lp = list2 ; lp ; lp = lp->next )
 247         if (!isinSet(un,lp->item))
 248             addSet (&un,lp->item);
 249
 250     switch (throw) {
 251     case THROW_SRC :
 252         setToNull ((void **)&list2);
 253         break;
 254     case THROW_DEST :
 255         setToNull ((void **)&list1);
 256         break;
 257     case THROW_BOTH :
 258         setToNull ((void **)&list1);
 259         setToNull ((void **)&list2);
 260     }
 261
 262     return un;
 263 }
 264
 265 /*-----------------------------------------------------------------*/
 266 /* unionSetsWith - will return the union of the two lists          */
 267 /*-----------------------------------------------------------------*/
 268 set *unionSetsWith (set *list1 , set *list2, int (*cFunc)(),int throw)
 269 {
 270     set *un = NULL ;
 271     set *lp ;
 272
 273     /* add all elements in the first list */
 274     for (lp = list1 ; lp ; lp = lp->next )
 275         addSet (&un,lp->item);
 276
 277     /* now for all those in list2 which does not */
 278     /* already exist in the list add             */
 279     for (lp = list2 ; lp ; lp = lp->next )
 280         if (!isinSetWith(un,lp->item,cFunc))
 281             addSet (&un,lp->item);
 282
 283     switch (throw) {
 284     case THROW_SRC :
 285         setToNull ((void **)&list2);
 286         break;
 287     case THROW_DEST :
 288         setToNull ((void **)&list1);
 289         break;
 290     case THROW_BOTH :
 291         setToNull ((void **)&list1);
 292         setToNull ((void **)&list2);
 293     }
 294
 295     return un;
 296 }
 297
 298 /*-----------------------------------------------------------------*/
 299 /* intersectSets - returns list of items in common to two lists    */
 300 /*-----------------------------------------------------------------*/
 301 set *intersectSets (set *list1, set *list2, int throw)
 302 {
 303     set *in = NULL;
 304     set *lp ;
 305
 306     /* we can take any one of the lists and iterate over it */
 307     for (lp = list1 ; lp ; lp = lp->next )
 308         if (isinSet (list2,lp->item) )
 309             addSetHead(&in,lp->item);
 310
 311     switch (throw) {
 312     case THROW_SRC :
 313         setToNull ((void **)&list2);
 314         break;
 315     case THROW_DEST :
 316         setToNull ((void **)&list1);
 317         break;
 318     case THROW_BOTH :
 319         setToNull ((void **)&list1);
 320         setToNull ((void **)&list2);
 321     }
 322
 323     return in;
 324 }
 325
 326 /*-----------------------------------------------------------------*/
 327 /* intersectSetsWith - returns list of items in common to two lists*/
 328 /*-----------------------------------------------------------------*/
 329 set *intersectSetsWith (set *list1, set *list2,
 330                         int (*cFunc)(void *,void *),int throw)
 331 {
 332     set *in = NULL;
 333     set *lp ;
 334
 335     /* we can take any one of the lists and iterate over it */
 336     for (lp = list1 ; lp ; lp = lp->next )
 337         if (isinSetWith (list2,lp->item,cFunc) )
 338             addSetHead(&in,lp->item);
 339
 340     switch (throw) {
 341     case THROW_SRC :
 342         setToNull ((void **)&list2);
 343         break;
 344     case THROW_DEST :
 345         setToNull ((void **)&list1);
 346         break;
 347     case THROW_BOTH :
 348         setToNull ((void **)&list1);
 349         setToNull ((void **)&list2);
 350     }
 351
 352     return in;
 353 }
 354
 355 /*-----------------------------------------------------------------*/
 356 /* elementsInSet - elements count of a set                         */
 357 /*-----------------------------------------------------------------*/
 358 int elementsInSet (set *s)
 359 {
 360     set *loop = s;
 361     int count = 0 ;
 362
 363     while (loop) {
 364         count++ ;
 365         loop = loop->next ;
 366     }
 367
 368     return count ;
 369 }
 370
 371 /*-----------------------------------------------------------------*/
 372 /* subtractFromSet - take away from set1 elements of set2          */
 373 /*-----------------------------------------------------------------*/
 374 set *subtractFromSet (set *left, set *right, int throw)
 375 {
 376     set *result = setFromSet(left);
 377     set *loop ;
 378
 379     if (right) {
 380         for (loop = right ; loop ; loop = loop->next)
 381             if (isinSet(result,loop->item))
 382                 deleteSetItem (&result,loop->item);
 383     }
 384
 385     switch (throw) {
 386     case THROW_SRC :
 387         setToNull ((void **)&right);
 388         break;
 389     case THROW_DEST :
 390         setToNull ((void **)&left);
 391         break;
 392     case THROW_BOTH :
 393         setToNull ((void **)&left);
 394         setToNull ((void **)&right);
 395         break ;
 396     }
 397
 398     return result ;
 399 }
 400
 401 /*-----------------------------------------------------------------*/
 402 /* applyToSet - will call the supplied function with each item     */
 403 /*-----------------------------------------------------------------*/
 404 int applyToSet ( set *list , int (*somefunc)(void *, va_list ), ...)
 405 {
 406     set *lp ;
 407     va_list ap;
 408     int rvalue = 0 ;
 409
 410     for (lp = list ; lp ; lp = lp->next ) {
 411           va_start(ap,somefunc);
 412           rvalue += (*somefunc)(lp->item,ap) ;
 413           va_end(ap);
 414     }
 415     return rvalue;
 416 }
 417
 418 /*-----------------------------------------------------------------*/
 419 /* applyToSetFTrue - will call the supplied function with each item*/
 420 /*                   until list is exhausted or a true is returned */
 421 /*-----------------------------------------------------------------*/
 422 int applyToSetFTrue ( set *list , int (*somefunc)(void *, va_list ), ...)
 423 {
 424     set *lp ;
 425     va_list ap;
 426     int rvalue = 0 ;
 427
 428     for (lp = list ; lp ; lp = lp->next ) {
 429           va_start(ap,somefunc);
 430           rvalue += (*somefunc)(lp->item,ap);
 431           va_end(ap);
 432           if (rvalue)
 433                 break;
 434     }
 435     return rvalue;
 436 }
 437
 438 /*-----------------------------------------------------------------*/
 439 /* peekSet - will return the first element of the set              */
 440 /*-----------------------------------------------------------------*/
 441 void *peekSet ( set *sp)
 442 {
 443     if (!sp)
 444         return NULL ;
 445
 446     return sp->item;
 447 }
 448
 449 /*-----------------------------------------------------------------*/
 450 /* setFirstItem - gets the first item in the set, begins iteration */
 451 /*-----------------------------------------------------------------*/
 452 void *setFirstItem (set *sset)
 453 {
 454     if (sset) {
 455         sset->curr = sset ;
 456         return sset->item ;
 457     }
 458
 459     return NULL ;
 460 }
 461 /*-----------------------------------------------------------------*/
 462 /* setNextItem - gets the next item, changes the iteration         */
 463 /*-----------------------------------------------------------------*/
 464 void *setNextItem (set *sset)
 465 {
 466     if (sset && sset->curr ) {
 467         sset->curr = sset->curr->next ;
 468         if ( sset->curr )
 469             return sset->curr->item ;
 470     }
 471     return NULL ;
 472 }
 473
 474 /*-----------------------------------------------------------------*/
 475 /* getSet - will delete & return the first item from the set   */
 476 /*-----------------------------------------------------------------*/
 477 void *getSet (set **list)
 478 {
 479     set *lp;
 480     void *item ;
 481
 482     /* if list is empty then we cannot delete */
 483     if (*list == NULL )
 484         return (void *) NULL ;
 485
 486
 487     /* find the item in the list */
 488     lp = *list ;
 489     item = lp->item; /* save the item */
 490
 491     *list = lp->next ;
 492     return item ;
 493 }
 494
 495 /*-----------------------------------------------------------------*/
 496 /* setToNull - will throw away the entire list                   */
 497 /*-----------------------------------------------------------------*/
 498 void setToNull (void **item )
 499 {
 500
 501     if ( !item  )
 502         return ;
 503
 504     if (! *item )
 505         return ;
 506     free(*item);
 507     *item = NULL ;
 508 }