sdcc/src/SDCCset.c

   1 /*-----------------------------------------------------------------
   2     SDCCset.c - contains support routines for linked lists.
   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 "SDCCerr.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   lp->item = lp->curr = lp->next = NULL;
  40   return lp;
  41 }
  42
  43
  44 /*-----------------------------------------------------------------*/
  45 /* setFromSet - creates a list from another list; the order of     */
  46 /*              elements in new list is reverted                   */
  47 /*-----------------------------------------------------------------*/
  48 set *
  49 setFromSet (const set *lp)
  50 {
  51   set *lfl = NULL;
  52
  53   while (lp)
  54     {
  55       addSetHead (&lfl, lp->item);
  56       lp = lp->next;
  57     }
  58
  59   return lfl;
  60 }
  61
  62 /*-----------------------------------------------------------------*/
  63 /* setFromSet - creates a list from another list; the order of     */
  64 /*              elements in retained                               */
  65 /*-----------------------------------------------------------------*/
  66 set *
  67 setFromSetNonRev (const set *lp)
  68 {
  69   set *lfl = NULL;
  70
  71   while (lp)
  72     {
  73       addSet (&lfl, lp->item);
  74       lp = lp->next;
  75     }
  76
  77   return lfl;
  78 }
  79
  80 /*-----------------------------------------------------------------*/
  81 /* isSetsEqual - are the lists equal, they are equal if they have  */
  82 /*               the same objects & the same number of objects     */
  83 /*-----------------------------------------------------------------*/
  84 int
  85 isSetsEqual (const set *dest, const set *src)
  86 {
  87   const set *src1 = src;
  88
  89   for (; dest && src; dest = dest->next, src = src->next)
  90     {
  91       if (!isinSet (src1, dest->item))
  92         return 0;
  93     }
  94   if (!dest && !src)
  95     return 1;
  96   return 0;
  97 }
  98
  99 /*-----------------------------------------------------------------*/
 100 /* isSetsEqualWith - are the lists equal, they are equal if they   */
 101 /*                   have  the same objects & the same number of   */
 102 /*                   objects , compare function                    */
 103 /*-----------------------------------------------------------------*/
 104 int
 105 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
 106 {
 107   set *src1 = src;
 108
 109   for (; dest && src; dest = dest->next, src = src->next)
 110     {
 111       if (!isinSetWith (src1, dest->item, cFunc))
 112         return 0;
 113     }
 114   if (!dest && !src)
 115     return 1;
 116   return 0;
 117 }
 118
 119 /*-----------------------------------------------------------------*/
 120 /* addSetIfnotP - adds to a linked list if not already present     */
 121 /*-----------------------------------------------------------------*/
 122 void *
 123 addSetIfnotP (set ** list, void *item)
 124 {
 125   if (isinSet (*list, item))
 126     return item;
 127
 128   addSetHead (list, item);
 129
 130   return item;
 131 }
 132
 133 /*-----------------------------------------------------------------*/
 134 /* addSetHead - add item to head of linked list                    */
 135 /*-----------------------------------------------------------------*/
 136 void *
 137 addSetHead (set ** list, void *item)
 138 {
 139   set *lp = newSet ();
 140
 141   lp->item = item;
 142   lp->next = *list;
 143
 144   assert (lp != lp->item);
 145   *list = lp;
 146   return item;
 147 }
 148
 149 /*-----------------------------------------------------------------*/
 150 /* addSet - add an item to a linear linked list                    */
 151 /*-----------------------------------------------------------------*/
 152 void *
 153 addSet (set ** list, void *item)
 154 {
 155   set *lp;
 156
 157   if (!list)
 158     werror (E_INTERNAL_ERROR,__FILE__,__LINE__, "Invalid set.");
 159
 160   /* item added to the tail of the list */
 161
 162   /* if the list is empty */
 163   if (*list == NULL)
 164     {
 165       lp = *list = newSet ();
 166     }
 167   else
 168     {
 169       /* go to the end of the list */
 170       for (lp = *list; lp->next; lp = lp->next);
 171       lp = lp->next = newSet ();
 172     }
 173   if (!list)
 174     werror (E_OUT_OF_MEM,__FILE__,__LINE__, "Can't add to set.");
 175
 176   /* lp now all set */
 177   lp->item = item;
 178
 179   return item;
 180 }
 181
 182 /*-----------------------------------------------------------------*/
 183 /* deleteItemIf - will delete from set if cond function returns 1  */
 184 /*-----------------------------------------------------------------*/
 185 void
 186 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
 187 {
 188   set *sp = *sset;
 189   va_list ap;
 190
 191   while (sp)
 192     {
 193       /*
 194        * On the x86 va_list is just a pointer, so due to pass by value
 195        * ap is not modified by the called function.  On the PPC va_list
 196        * is a pointer to a structure, so ap is modified.  Re-init each time.
 197        */
 198       va_start (ap, cond);
 199
 200       if ((*cond) (sp->item, ap))
 201         {
 202           deleteSetItem (sset, sp->item);
 203           sp = *sset;
 204           continue;
 205         }
 206
 207       va_end(ap);
 208       sp = sp->next;
 209     }
 210 }
 211
 212 /*-------------------------------------------------------------------*/
 213 /* destructItemIf - will delete from set if cond function returns 1, */
 214 /*                  upon deletion, item's destructor is also called  */
 215 /*-------------------------------------------------------------------*/
 216 void
 217 destructItemIf (set ** sset, void (*destructor)(void * item), int (*cond) (void *, va_list),...)
 218 {
 219   set *sp = *sset;
 220   va_list ap;
 221
 222   while (sp)
 223     {
 224       /*
 225        * On the x86 va_list is just a pointer, so due to pass by value
 226        * ap is not modified by the called function.  On the PPC va_list
 227        * is a pointer to a structure, so ap is modified.  Re-init each time.
 228        */
 229       va_start (ap, cond);
 230
 231       if ((*cond) (sp->item, ap))
 232         {
 233           destructor (sp->item);
 234           deleteSetItem (sset, sp->item);
 235           sp = *sset;
 236           continue;
 237         }
 238
 239       va_end(ap);
 240       sp = sp->next;
 241     }
 242 }
 243
 244
 245 /*-----------------------------------------------------------------*/
 246 /* deleteSetItem - will delete a given item from the list          */
 247 /*-----------------------------------------------------------------*/
 248 void
 249 deleteSetItem (set **list, void *item)
 250 {
 251   set *lp, *lp1;
 252
 253   /* if list is empty */
 254   if (*list == NULL)
 255     return;
 256
 257   /* if this item is at the head of the list */
 258   if ((*list)->item == item)
 259     {
 260       lp = *list;
 261       *list = (*list)->next;
 262       Safe_free (lp);
 263       return;
 264     }
 265
 266   /* find the item in the list */
 267   for (lp = *list; lp->next; lp = lp->next)
 268     {
 269       if (lp->next->item == item)     /* the next one is it */
 270         {
 271           lp1 = lp->next;             /* this one will need to be freed */
 272           lp->next = lp->next->next;  /* take out of list */
 273           Safe_free (lp1);
 274           return;
 275         }
 276     }
 277
 278   /* could not find it */
 279 }
 280
 281 /*-----------------------------------------------------------------*/
 282 /* replaceSetItem - will replace a given item in the list          */
 283 /*-----------------------------------------------------------------*/
 284 void
 285 replaceSetItem (set *list, void *olditem, void *newitem)
 286 {
 287   /* find the item in the list */
 288   for (; list; list = list->next)
 289     if (list->item == olditem)
 290       {
 291         list->item = newitem;
 292         return;
 293       }
 294
 295
 296   /* could not find it */
 297 }
 298
 299 /*-----------------------------------------------------------------*/
 300 /* isinSet - the item is present in the linked list                */
 301 /*-----------------------------------------------------------------*/
 302 int
 303 isinSet (const set *list, const void *item)
 304 {
 305   const set *lp;
 306
 307   for (lp = list; lp; lp = lp->next)
 308     if (lp->item == item)
 309       return 1;
 310
 311   return 0;
 312 }
 313
 314 /*-----------------------------------------------------------------*/
 315 /* isinSetWith - the item is present in the linked list            */
 316 /*-----------------------------------------------------------------*/
 317 int
 318 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
 319 {
 320   set *lp;
 321
 322   for (lp = list; lp; lp = lp->next)
 323     if ((*cFunc) (lp->item, item))
 324       return 1;
 325
 326   return 0;
 327 }
 328
 329 /*-----------------------------------------------------------------*/
 330 /* mergeSets - append list to sset                                 */
 331 /*-----------------------------------------------------------------*/
 332 void
 333 mergeSets (set **sset, set *list)
 334 {
 335   if (*sset == NULL)
 336     {
 337       *sset = list;
 338     }
 339   else
 340     {
 341       set *lp;
 342
 343       for (lp = *sset; lp->next; lp = lp->next)
 344         ;
 345       lp->next = list;
 346     }
 347 }
 348
 349 /*-----------------------------------------------------------------*/
 350 /* unionSets - will return the union of the two lists              */
 351 /*-----------------------------------------------------------------*/
 352 set *
 353 unionSets (set * list1, set * list2, int throw)
 354 {
 355   set *un = NULL;
 356   set *lp;
 357
 358   /* If we were going to throw away the destination list */
 359   /* anyway, save memory and time by using it as the */
 360   /* starting point for the new list. */
 361   if (throw == THROW_DEST || throw == THROW_BOTH)
 362     {
 363       un = list1;
 364       if (throw == THROW_BOTH)
 365         throw = THROW_SRC;
 366       else
 367         throw = THROW_NONE;
 368     }
 369   else
 370     {
 371       /* add all elements in the first list */
 372       for (lp = list1; lp; lp = lp->next)
 373         addSet (&un, lp->item);
 374     }
 375
 376   /* now for all those in list2 which does not */
 377   /* already exist in the list add             */
 378   for (lp = list2; lp; lp = lp->next)
 379     if (!isinSet (un, lp->item))
 380       addSet (&un, lp->item);
 381
 382   switch (throw)
 383     {
 384     case THROW_SRC:
 385       setToNull ((void *) &list2);
 386       break;
 387     case THROW_DEST:
 388       setToNull ((void *) &list1);
 389       break;
 390     case THROW_BOTH:
 391       setToNull ((void *) &list1);
 392       setToNull ((void *) &list2);
 393     }
 394
 395   return un;
 396 }
 397
 398 /*-----------------------------------------------------------------*/
 399 /* unionSetsWith - will return the union of the two lists          */
 400 /*-----------------------------------------------------------------*/
 401 set *
 402 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
 403 {
 404   set *un = NULL;
 405   set *lp;
 406
 407   /* add all elements in the first list */
 408   for (lp = list1; lp; lp = lp->next)
 409     addSet (&un, lp->item);
 410
 411   /* now for all those in list2 which does not */
 412   /* already exist in the list add             */
 413   for (lp = list2; lp; lp = lp->next)
 414     if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
 415       addSet (&un, lp->item);
 416
 417   switch (throw)
 418     {
 419     case THROW_SRC:
 420       setToNull ((void *) &list2);
 421       break;
 422     case THROW_DEST:
 423       setToNull ((void *) &list1);
 424       break;
 425     case THROW_BOTH:
 426       setToNull ((void *) &list1);
 427       setToNull ((void *) &list2);
 428     }
 429
 430   return un;
 431 }
 432
 433 /*-----------------------------------------------------------------*/
 434 /* intersectSets - returns list of items in common to two lists    */
 435 /*-----------------------------------------------------------------*/
 436 set *
 437 intersectSets (set * list1, set * list2, int throw)
 438 {
 439   set *in = NULL;
 440   set *lp;
 441
 442   /* we can take any one of the lists and iterate over it */
 443   for (lp = list1; lp; lp = lp->next)
 444     if (isinSet (list2, lp->item))
 445       addSetHead (&in, lp->item);
 446
 447   switch (throw)
 448     {
 449     case THROW_SRC:
 450       setToNull ((void *) &list2);
 451       break;
 452     case THROW_DEST:
 453       setToNull ((void *) &list1);
 454       break;
 455     case THROW_BOTH:
 456       setToNull ((void *) &list1);
 457       setToNull ((void *) &list2);
 458     }
 459
 460   return in;
 461 }
 462
 463 /*-----------------------------------------------------------------*/
 464 /* intersectSetsWith - returns list of items in common to two      */
 465 /*                     lists                                       */
 466 /*-----------------------------------------------------------------*/
 467 set *
 468 intersectSetsWith (set * list1, set * list2,
 469                    int (*cFunc) (void *, void *), int throw)
 470 {
 471   set *in = NULL;
 472   set *lp;
 473
 474   /* we can take any one of the lists and iterate over it */
 475   for (lp = list1; lp; lp = lp->next)
 476     if (isinSetWith (list2, lp->item, cFunc))
 477       addSetHead (&in, lp->item);
 478
 479   switch (throw)
 480     {
 481     case THROW_SRC:
 482       setToNull ((void *) &list2);
 483       break;
 484     case THROW_DEST:
 485       setToNull ((void *) &list1);
 486       break;
 487     case THROW_BOTH:
 488       setToNull ((void *) &list1);
 489       setToNull ((void *) &list2);
 490     }
 491
 492   return in;
 493 }
 494
 495 /*-----------------------------------------------------------------*/
 496 /* elementsInSet - elements count of a set                         */
 497 /*-----------------------------------------------------------------*/
 498 int
 499 elementsInSet (const set * s)
 500 {
 501   const set *loop = s;
 502   int count = 0;
 503
 504   while (loop)
 505     {
 506       count++;
 507       loop = loop->next;
 508     }
 509
 510   return count;
 511 }
 512
 513 /*-----------------------------------------------------------------*/
 514 /* indexSet - returns the i'th item in set                         */
 515 /*-----------------------------------------------------------------*/
 516 void *
 517 indexSet (set * s, int index)
 518 {
 519   set *loop = s;
 520
 521   while (loop && index--)
 522     {
 523       loop = loop->next;
 524     }
 525
 526   return loop ? loop->item : NULL;
 527 }
 528
 529
 530 /*-----------------------------------------------------------------*/
 531 /* reverseSet - reverse the order of the items of a set            */
 532 /*-----------------------------------------------------------------*/
 533 set *
 534 reverseSet (set * s)
 535 {
 536   set *t = NULL;
 537   set *u = NULL;
 538
 539   while(s->next)
 540     {
 541       t = s->next;
 542       s->next = u;
 543       u = s;
 544       s = t;
 545     }
 546   s->next = u;
 547   return s;
 548 }
 549
 550 /*-----------------------------------------------------------------*/
 551 /* subtractFromSet - take away from set1 elements of set2          */
 552 /*-----------------------------------------------------------------*/
 553 set *
 554 subtractFromSet (set * left, set * right, int throw)
 555 {
 556   set *result = setFromSet (left);
 557   set *loop;
 558
 559   if (right)
 560     {
 561       for (loop = right; loop; loop = loop->next)
 562         if (isinSet (result, loop->item))
 563           deleteSetItem (&result, loop->item);
 564     }
 565
 566   switch (throw)
 567     {
 568     case THROW_SRC:
 569       setToNull ((void *) &right);
 570       break;
 571     case THROW_DEST:
 572       setToNull ((void *) &left);
 573       break;
 574     case THROW_BOTH:
 575       setToNull ((void *) &left);
 576       setToNull ((void *) &right);
 577       break;
 578     }
 579
 580   return result;
 581 }
 582
 583 /*-----------------------------------------------------------------*/
 584 /* applyToSet - will call the supplied function with each item     */
 585 /*-----------------------------------------------------------------*/
 586 int
 587 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
 588 {
 589   set *lp;
 590   va_list ap;
 591   int rvalue = 0;
 592
 593   for (lp = list; lp; lp = lp->next)
 594     {
 595       va_start (ap, somefunc);
 596       rvalue += (*somefunc) (lp->item, ap);
 597       va_end (ap);
 598     }
 599   return rvalue;
 600 }
 601
 602 /*-----------------------------------------------------------------*/
 603 /* applyToSetFTrue - will call the supplied function with each     */
 604 /*                   item until list is exhausted or a true is     */
 605 /*                   returned                                      */
 606 /*-----------------------------------------------------------------*/
 607 int
 608 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
 609 {
 610   set *lp;
 611   va_list ap;
 612   int rvalue = 0;
 613
 614   for (lp = list; lp; lp = lp->next)
 615     {
 616       va_start (ap, somefunc);
 617       rvalue += (*somefunc) (lp->item, ap);
 618       va_end (ap);
 619       if (rvalue)
 620         break;
 621     }
 622   return rvalue;
 623 }
 624
 625 /*-----------------------------------------------------------------*/
 626 /* peekSet - will return the first element of the set              */
 627 /*-----------------------------------------------------------------*/
 628 void *
 629 peekSet (const set *sp)
 630 {
 631   if (!sp)
 632     return NULL;
 633
 634   return sp->item;
 635 }
 636
 637 /*-----------------------------------------------------------------*/
 638 /* setFirstItem - gets the first item in the set, begins iteration */
 639 /*-----------------------------------------------------------------*/
 640 void *
 641 setFirstItem (set *sset)
 642 {
 643   if (sset)
 644     {
 645       sset->curr = sset;
 646       return sset->item;
 647     }
 648
 649   return NULL;
 650 }
 651 /*-----------------------------------------------------------------*/
 652 /* setNextItem - gets the next item, changes the iteration         */
 653 /*-----------------------------------------------------------------*/
 654 void *
 655 setNextItem (set * sset)
 656 {
 657   if (sset && sset->curr)
 658     {
 659       sset->curr = sset->curr->next;
 660       if (sset->curr)
 661         return sset->curr->item;
 662     }
 663   return NULL;
 664 }
 665
 666 /*-----------------------------------------------------------------*/
 667 /* getSet - will delete & return the first item from the set       */
 668 /*-----------------------------------------------------------------*/
 669 void *
 670 getSet (set ** list)
 671 {
 672   set *lp;
 673   void *item;
 674
 675   /* if list is empty then we cannot delete */
 676   if (*list == NULL)
 677     return (void *) NULL;
 678
 679   /* find the item in the list */
 680   lp = *list;
 681   item = lp->item;              /* save the item */
 682
 683   *list = lp->next;
 684   return item;
 685 }
 686
 687 /*-----------------------------------------------------------------*/
 688 /* setToNull - will throw away the entire list                     */
 689 /*-----------------------------------------------------------------*/
 690 void
 691 setToNull (void **item)
 692 {
 693   if (!item)
 694     return;
 695
 696   if (!*item)
 697     return;
 698   Safe_free (*item);
 699   *item = NULL;
 700 }
 701
 702 /*-----------------------------------------------------------------*/
 703 /* deleteSet - will throw away the entire list                     */
 704 /*  note - setToNull doesn't actually throw away the whole list.   */
 705 /*         Instead it only throws away the first item.             */
 706 /*-----------------------------------------------------------------*/
 707 void
 708 deleteSet (set **s)
 709 {
 710   set *curr;
 711   set *next;
 712
 713   if(!s || !*s)
 714     return;
 715
 716   curr = *s;
 717   next = curr->next;
 718   while (next)
 719     {
 720       Safe_free (curr);
 721       curr = next;
 722       next = next->next;
 723     }
 724
 725   Safe_free (curr);
 726
 727   *s = NULL;
 728 }