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