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