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 "newalloc.h"
  27 #include <assert.h>
  28 #include "SDCCset.h"
  29
  30 /*-----------------------------------------------------------------*/
  31 /* newSet - will allocate & return a new set entry             */
  32 /*-----------------------------------------------------------------*/
  33 set *
  34 newSet (void)
  35 {
  36   set *lp;
  37
  38   lp = Safe_alloc ( sizeof (set));
  39 //  if (lp == 0) {
  40   //  fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
  41   //  exit(1);
  42   //  }
  43
  44   lp->item = lp->curr = lp->next = NULL;
  45   return lp;
  46 }
  47
  48
  49 /*-----------------------------------------------------------------*/
  50 /* setFromSet - creates a list from another list                */
  51 /*-----------------------------------------------------------------*/
  52 set *
  53 setFromSet (set * lp)
  54 {
  55   set *lfl = NULL;
  56
  57   while (lp)
  58     {
  59       addSetHead (&lfl, lp->item);
  60       lp = lp->next;
  61     }
  62
  63   return lfl;
  64
  65 }
  66
  67 /*-----------------------------------------------------------------*/
  68 /* isSetsEqual - are the lists equal, they are equal if they have  */
  69 /*               the same objects & the same number of objects     */
  70 /*-----------------------------------------------------------------*/
  71 int
  72 isSetsEqual (set * dest, set * src)
  73 {
  74   set *src1 = src;
  75
  76   for (; dest && src; dest = dest->next, src = src->next)
  77     {
  78       if (!isinSet (src1, dest->item))
  79         return 0;
  80     }
  81   if (!dest && !src)
  82     return 1;
  83   return 0;
  84 }
  85
  86 /*-----------------------------------------------------------------*/
  87 /* isSetsEqualWith - are the lists equal, they are equal if they have  */
  88 /* the same objects & the same number of objects , compare function    */
  89 /*-----------------------------------------------------------------*/
  90 int
  91 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
  92 {
  93   set *src1 = src;
  94
  95   for (; dest && src; dest = dest->next, src = src->next)
  96     {
  97       if (!isinSetWith (src1, dest->item, cFunc))
  98         return 0;
  99     }
 100   if (!dest && !src)
 101     return 1;
 102   return 0;
 103 }
 104
 105 /*-----------------------------------------------------------------*/
 106 /* addSetIfnotP - adds to a linked list if not already present   */
 107 /*-----------------------------------------------------------------*/
 108 void *
 109 addSetIfnotP (set ** list, void *item)
 110 {
 111
 112   if (isinSet (*list, item))
 113     return item;
 114
 115   addSetHead (list, item);
 116
 117   return item;
 118 }
 119
 120 /*-----------------------------------------------------------------*/
 121 /* addSetHead - add item to head of linked list                  */
 122 /*-----------------------------------------------------------------*/
 123 void *
 124 addSetHead (set ** list, void *item)
 125 {
 126   set *lp = newSet ();
 127
 128   lp->item = item;
 129   lp->next = *list;
 130
 131   assert (lp != lp->item);
 132   *list = lp;
 133   return item;
 134
 135 }
 136
 137 /*-----------------------------------------------------------------*/
 138 /* addSet - add an item to a linear linked list                  */
 139 /*-----------------------------------------------------------------*/
 140 void *
 141 addSet (set ** list, void *item)
 142 {
 143   set *lp;
 144
 145   /* item added to the tail of the list */
 146
 147   /* if the list is empty */
 148   if (*list == NULL)
 149     {
 150       lp = *list = newSet ();
 151     }
 152   else
 153     {
 154       /* go to the end of the list */
 155       for (lp = *list; lp->next; lp = lp->next);
 156       lp = lp->next = newSet ();
 157     }
 158
 159   /* lp now all set */
 160   lp->item = item;
 161
 162   return item;
 163 }
 164
 165 /*-----------------------------------------------------------------*/
 166 /* deleteItemIf - will delete from set if cond function returns 1  */
 167 /*-----------------------------------------------------------------*/
 168 void
 169 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
 170 {
 171   set *sp = *sset;
 172   va_list ap;
 173
 174   while (sp)
 175     {
 176       // On the x86 va_list is just a pointer, so due to pass by value
 177       // ap is not mofified by the called function.  On the PPC va_list
 178       // is a pointer to a structure, so ap is modified.  Re-init each time.
 179       va_start (ap, cond);
 180
 181       if ((*cond) (sp->item, ap))
 182         {
 183           deleteSetItem (sset, sp->item);
 184           sp = *sset;
 185           continue;
 186         }
 187
 188       va_end(ap);
 189       sp = sp->next;
 190     }
 191 }
 192
 193 /*-----------------------------------------------------------------*/
 194 /* deleteSetItem - will delete a given item from the list          */
 195 /*-----------------------------------------------------------------*/
 196 void
 197 deleteSetItem (set ** list, void *item)
 198 {
 199   set *lp, *lp1;
 200
 201   /* if list is empty */
 202   if (*list == NULL)
 203     return;
 204
 205   /* if this item is at the head of the list */
 206   if ((*list)->item == item) {
 207     lp = *list;
 208     *list = (*list)->next;
 209     Safe_free (lp);
 210     return;
 211   }
 212
 213   /* find the item in the list */
 214   for (lp = *list; lp->next; lp = lp->next) {
 215     if (lp->next->item == item) { /* the next one is it */
 216       lp1 = lp->next;             /* this one will need to be freed */
 217       lp->next = lp->next->next;  /* take out of list */
 218       Safe_free (lp1);
 219       return;
 220     }
 221   }
 222
 223   /* could not find it */
 224 }
 225
 226 /*-----------------------------------------------------------------*/
 227 /* isinSet - the item is present in the linked list              */
 228 /*-----------------------------------------------------------------*/
 229 int
 230 isinSet (set * list, void *item)
 231 {
 232   set *lp;
 233
 234   for (lp = list; lp; lp = lp->next)
 235     if (lp->item == item)
 236       return 1;
 237
 238   return 0;
 239 }
 240
 241 /*-----------------------------------------------------------------*/
 242 /* isinSetWith - the item is present in the linked list            */
 243 /*-----------------------------------------------------------------*/
 244 int
 245 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
 246 {
 247   set *lp;
 248
 249   for (lp = list; lp; lp = lp->next)
 250     if ((*cFunc) (lp->item, item))
 251       return 1;
 252
 253   return 0;
 254 }
 255
 256 /*-----------------------------------------------------------------*/
 257 /* unionSets - will return the union of the two lists             */
 258 /*-----------------------------------------------------------------*/
 259 set *
 260 unionSets (set * list1, set * list2, int throw)
 261 {
 262   set *un = NULL;
 263   set *lp;
 264
 265   /* add all elements in the first list */
 266   for (lp = list1; lp; lp = lp->next)
 267     addSet (&un, lp->item);
 268
 269   /* now for all those in list2 which does not */
 270   /* already exist in the list add             */
 271   for (lp = list2; lp; lp = lp->next)
 272     if (!isinSet (un, lp->item))
 273       addSet (&un, lp->item);
 274
 275   switch (throw)
 276     {
 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 /* unionSetsWith - will return the union of the two lists          */
 293 /*-----------------------------------------------------------------*/
 294 set *
 295 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
 296 {
 297   set *un = NULL;
 298   set *lp;
 299
 300   /* add all elements in the first list */
 301   for (lp = list1; lp; lp = lp->next)
 302     addSet (&un, lp->item);
 303
 304   /* now for all those in list2 which does not */
 305   /* already exist in the list add             */
 306   for (lp = list2; lp; lp = lp->next)
 307     if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
 308       addSet (&un, lp->item);
 309
 310   switch (throw)
 311     {
 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 un;
 324 }
 325
 326 /*-----------------------------------------------------------------*/
 327 /* intersectSets - returns list of items in common to two lists    */
 328 /*-----------------------------------------------------------------*/
 329 set *
 330 intersectSets (set * list1, set * list2, 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 (isinSet (list2, lp->item))
 338       addSetHead (&in, lp->item);
 339
 340   switch (throw)
 341     {
 342     case THROW_SRC:
 343       setToNull ((void **) &list2);
 344       break;
 345     case THROW_DEST:
 346       setToNull ((void **) &list1);
 347       break;
 348     case THROW_BOTH:
 349       setToNull ((void **) &list1);
 350       setToNull ((void **) &list2);
 351     }
 352
 353   return in;
 354 }
 355
 356 /*-----------------------------------------------------------------*/
 357 /* intersectSetsWith - returns list of items in common to two lists */
 358 /*-----------------------------------------------------------------*/
 359 set *
 360 intersectSetsWith (set * list1, set * list2,
 361                    int (*cFunc) (void *, void *), int throw)
 362 {
 363   set *in = NULL;
 364   set *lp;
 365
 366   /* we can take any one of the lists and iterate over it */
 367   for (lp = list1; lp; lp = lp->next)
 368     if (isinSetWith (list2, lp->item, cFunc))
 369       addSetHead (&in, lp->item);
 370
 371   switch (throw)
 372     {
 373     case THROW_SRC:
 374       setToNull ((void **) &list2);
 375       break;
 376     case THROW_DEST:
 377       setToNull ((void **) &list1);
 378       break;
 379     case THROW_BOTH:
 380       setToNull ((void **) &list1);
 381       setToNull ((void **) &list2);
 382     }
 383
 384   return in;
 385 }
 386
 387 /*-----------------------------------------------------------------*/
 388 /* elementsInSet - elements count of a set                         */
 389 /*-----------------------------------------------------------------*/
 390 int
 391 elementsInSet (set * s)
 392 {
 393   set *loop = s;
 394   int count = 0;
 395
 396   while (loop)
 397     {
 398       count++;
 399       loop = loop->next;
 400     }
 401
 402   return count;
 403 }
 404
 405 /*-----------------------------------------------------------------*/
 406 /* indexSet - returns the i'th item in set                         */
 407 /*-----------------------------------------------------------------*/
 408 void *indexSet(set * s, int index)
 409 {
 410   set *loop=s;
 411
 412   while(loop && index) {
 413         index--;
 414         loop = loop->next;
 415   }
 416
 417   return (loop->item);
 418 }
 419
 420
 421 /*-----------------------------------------------------------------*/
 422 /* reverseSet - reverse the order of the items of a set            */
 423 /*-----------------------------------------------------------------*/
 424
 425 set *
 426 reverseSet(set * s)
 427 {
 428   set *t = NULL;
 429   set *u = NULL;
 430
 431   while(s->next) {
 432     t = s->next;
 433     s->next = u;
 434     u = s;
 435     s = t;
 436   }
 437   s->next = u;
 438   return s;
 439 }
 440
 441 /*-----------------------------------------------------------------*/
 442 /* subtractFromSet - take away from set1 elements of set2          */
 443 /*-----------------------------------------------------------------*/
 444 set *
 445 subtractFromSet (set * left, set * right, int throw)
 446 {
 447   set *result = setFromSet (left);
 448   set *loop;
 449
 450   if (right)
 451     {
 452       for (loop = right; loop; loop = loop->next)
 453         if (isinSet (result, loop->item))
 454           deleteSetItem (&result, loop->item);
 455     }
 456
 457   switch (throw)
 458     {
 459     case THROW_SRC:
 460       setToNull ((void **) &right);
 461       break;
 462     case THROW_DEST:
 463       setToNull ((void **) &left);
 464       break;
 465     case THROW_BOTH:
 466       setToNull ((void **) &left);
 467       setToNull ((void **) &right);
 468       break;
 469     }
 470
 471   return result;
 472 }
 473
 474 /*-----------------------------------------------------------------*/
 475 /* applyToSet - will call the supplied function with each item     */
 476 /*-----------------------------------------------------------------*/
 477 int
 478 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
 479 {
 480   set *lp;
 481   va_list ap;
 482   int rvalue = 0;
 483
 484   for (lp = list; lp; lp = lp->next)
 485     {
 486       va_start (ap, somefunc);
 487       rvalue += (*somefunc) (lp->item, ap);
 488       va_end (ap);
 489     }
 490   return rvalue;
 491 }
 492
 493 /*-----------------------------------------------------------------*/
 494 /* applyToSetFTrue - will call the supplied function with each item */
 495 /*                   until list is exhausted or a true is returned */
 496 /*-----------------------------------------------------------------*/
 497 int
 498 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
 499 {
 500   set *lp;
 501   va_list ap;
 502   int rvalue = 0;
 503
 504   for (lp = list; lp; lp = lp->next)
 505     {
 506       va_start (ap, somefunc);
 507       rvalue += (*somefunc) (lp->item, ap);
 508       va_end (ap);
 509       if (rvalue)
 510         break;
 511     }
 512   return rvalue;
 513 }
 514
 515 /*-----------------------------------------------------------------*/
 516 /* peekSet - will return the first element of the set              */
 517 /*-----------------------------------------------------------------*/
 518 void *
 519 peekSet (set * sp)
 520 {
 521   if (!sp)
 522     return NULL;
 523
 524   return sp->item;
 525 }
 526
 527 /*-----------------------------------------------------------------*/
 528 /* setFirstItem - gets the first item in the set, begins iteration */
 529 /*-----------------------------------------------------------------*/
 530 void *
 531 setFirstItem (set * sset)
 532 {
 533   if (sset)
 534     {
 535       sset->curr = sset;
 536       return sset->item;
 537     }
 538
 539   return NULL;
 540 }
 541 /*-----------------------------------------------------------------*/
 542 /* setNextItem - gets the next item, changes the iteration         */
 543 /*-----------------------------------------------------------------*/
 544 void *
 545 setNextItem (set * sset)
 546 {
 547   if (sset && sset->curr)
 548     {
 549       sset->curr = sset->curr->next;
 550       if (sset->curr)
 551         return sset->curr->item;
 552     }
 553   return NULL;
 554 }
 555
 556 /*-----------------------------------------------------------------*/
 557 /* getSet - will delete & return the first item from the set   */
 558 /*-----------------------------------------------------------------*/
 559 void *
 560 getSet (set ** list)
 561 {
 562   set *lp;
 563   void *item;
 564
 565   /* if list is empty then we cannot delete */
 566   if (*list == NULL)
 567     return (void *) NULL;
 568
 569
 570   /* find the item in the list */
 571   lp = *list;
 572   item = lp->item;              /* save the item */
 573
 574   *list = lp->next;
 575   return item;
 576 }
 577
 578 /*-----------------------------------------------------------------*/
 579 /* setToNull - will throw away the entire list                   */
 580 /*-----------------------------------------------------------------*/
 581 void
 582 setToNull (void **item)
 583 {
 584
 585   if (!item)
 586     return;
 587
 588   if (!*item)
 589     return;
 590   Safe_free (*item);
 591   *item = NULL;
 592 }
 593
 594 /*-----------------------------------------------------------------*/
 595 /* deleteSet - will throw away the entire list                     */
 596 /*  note - setToNull doesn't actually throw away the whole list.   */
 597 /*         Instead it only throws away the first item.             */
 598 /*-----------------------------------------------------------------*/
 599 void deleteSet(set **s)
 600 {
 601   set *curr;
 602   set *next;
 603
 604   if(!s || !*s)
 605     return;
 606
 607   curr = *s;
 608   next = curr->next;
 609   while (next) {
 610     Safe_free (curr);
 611     curr = next;
 612     next = next->next;
 613   }
 614
 615   Safe_free (curr);
 616
 617   *s = NULL;
 618 }
 619