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