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 /* reverseSet - reverse the order of the items of a set            */
 407 /*-----------------------------------------------------------------*/
 408
 409 set *
 410 reverseSet(set * s)
 411 {
 412   set *t = NULL;
 413   set *u = NULL;
 414
 415   while(s->next) {
 416     t = s->next;
 417     s->next = u;
 418     u = s;
 419     s = t;
 420   }
 421   s->next = u;
 422   return s;
 423 }
 424
 425 /*-----------------------------------------------------------------*/
 426 /* subtractFromSet - take away from set1 elements of set2          */
 427 /*-----------------------------------------------------------------*/
 428 set *
 429 subtractFromSet (set * left, set * right, int throw)
 430 {
 431   set *result = setFromSet (left);
 432   set *loop;
 433
 434   if (right)
 435     {
 436       for (loop = right; loop; loop = loop->next)
 437         if (isinSet (result, loop->item))
 438           deleteSetItem (&result, loop->item);
 439     }
 440
 441   switch (throw)
 442     {
 443     case THROW_SRC:
 444       setToNull ((void **) &right);
 445       break;
 446     case THROW_DEST:
 447       setToNull ((void **) &left);
 448       break;
 449     case THROW_BOTH:
 450       setToNull ((void **) &left);
 451       setToNull ((void **) &right);
 452       break;
 453     }
 454
 455   return result;
 456 }
 457
 458 /*-----------------------------------------------------------------*/
 459 /* applyToSet - will call the supplied function with each item     */
 460 /*-----------------------------------------------------------------*/
 461 int
 462 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
 463 {
 464   set *lp;
 465   va_list ap;
 466   int rvalue = 0;
 467
 468   for (lp = list; lp; lp = lp->next)
 469     {
 470       va_start (ap, somefunc);
 471       rvalue += (*somefunc) (lp->item, ap);
 472       va_end (ap);
 473     }
 474   return rvalue;
 475 }
 476
 477 /*-----------------------------------------------------------------*/
 478 /* applyToSetFTrue - will call the supplied function with each item */
 479 /*                   until list is exhausted or a true is returned */
 480 /*-----------------------------------------------------------------*/
 481 int
 482 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
 483 {
 484   set *lp;
 485   va_list ap;
 486   int rvalue = 0;
 487
 488   for (lp = list; lp; lp = lp->next)
 489     {
 490       va_start (ap, somefunc);
 491       rvalue += (*somefunc) (lp->item, ap);
 492       va_end (ap);
 493       if (rvalue)
 494         break;
 495     }
 496   return rvalue;
 497 }
 498
 499 /*-----------------------------------------------------------------*/
 500 /* peekSet - will return the first element of the set              */
 501 /*-----------------------------------------------------------------*/
 502 void *
 503 peekSet (set * sp)
 504 {
 505   if (!sp)
 506     return NULL;
 507
 508   return sp->item;
 509 }
 510
 511 /*-----------------------------------------------------------------*/
 512 /* setFirstItem - gets the first item in the set, begins iteration */
 513 /*-----------------------------------------------------------------*/
 514 void *
 515 setFirstItem (set * sset)
 516 {
 517   if (sset)
 518     {
 519       sset->curr = sset;
 520       return sset->item;
 521     }
 522
 523   return NULL;
 524 }
 525 /*-----------------------------------------------------------------*/
 526 /* setNextItem - gets the next item, changes the iteration         */
 527 /*-----------------------------------------------------------------*/
 528 void *
 529 setNextItem (set * sset)
 530 {
 531   if (sset && sset->curr)
 532     {
 533       sset->curr = sset->curr->next;
 534       if (sset->curr)
 535         return sset->curr->item;
 536     }
 537   return NULL;
 538 }
 539
 540 /*-----------------------------------------------------------------*/
 541 /* getSet - will delete & return the first item from the set   */
 542 /*-----------------------------------------------------------------*/
 543 void *
 544 getSet (set ** list)
 545 {
 546   set *lp;
 547   void *item;
 548
 549   /* if list is empty then we cannot delete */
 550   if (*list == NULL)
 551     return (void *) NULL;
 552
 553
 554   /* find the item in the list */
 555   lp = *list;
 556   item = lp->item;              /* save the item */
 557
 558   *list = lp->next;
 559   return item;
 560 }
 561
 562 /*-----------------------------------------------------------------*/
 563 /* setToNull - will throw away the entire list                   */
 564 /*-----------------------------------------------------------------*/
 565 void
 566 setToNull (void **item)
 567 {
 568
 569   if (!item)
 570     return;
 571
 572   if (!*item)
 573     return;
 574   Safe_free (*item);
 575   *item = NULL;
 576 }
 577
 578 /*-----------------------------------------------------------------*/
 579 /* deleteSet - will throw away the entire list                     */
 580 /*  note - setToNull doesn't actually throw away the whole list.   */
 581 /*         Instead it only throws away the first item.             */
 582 /*-----------------------------------------------------------------*/
 583 void deleteSet(set **s)
 584 {
 585   set *curr;
 586   set *next;
 587
 588   if(!s || !*s)
 589     return;
 590
 591   curr = *s;
 592   next = curr->next;
 593   while (next) {
 594     Safe_free (curr);
 595     curr = next;
 596     next = next->next;
 597   }
 598
 599   Safe_free (curr);
 600
 601   *s = NULL;
 602 }
 603