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     {
 208       lp = *list;
 209       *list = (*list)->next;
 210       return;
 211     }
 212
 213   /* find the item in the list */
 214   for (lp = *list; lp->next; lp = lp->next)
 215     {
 216       if (lp->next->item == item)       /* the next one is it */
 217         {
 218           lp1 = lp->next;       /* this one will need to be freed */
 219           lp->next = lp->next->next;    /* take out of list */
 220           return;
 221         }
 222     }
 223
 224   /* could not find it */
 225   return;
 226 }
 227
 228 /*-----------------------------------------------------------------*/
 229 /* isinSet - the item is present in the linked list              */
 230 /*-----------------------------------------------------------------*/
 231 int
 232 isinSet (set * list, void *item)
 233 {
 234   set *lp;
 235
 236   for (lp = list; lp; lp = lp->next)
 237     if (lp->item == item)
 238       return 1;
 239
 240   return 0;
 241 }
 242
 243 /*-----------------------------------------------------------------*/
 244 /* isinSetWith - the item is present in the linked list            */
 245 /*-----------------------------------------------------------------*/
 246 int
 247 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
 248 {
 249   set *lp;
 250
 251   for (lp = list; lp; lp = lp->next)
 252     if ((*cFunc) (lp->item, item))
 253       return 1;
 254
 255   return 0;
 256 }
 257
 258 /*-----------------------------------------------------------------*/
 259 /* unionSets - will return the union of the two lists             */
 260 /*-----------------------------------------------------------------*/
 261 set *
 262 unionSets (set * list1, set * list2, int throw)
 263 {
 264   set *un = NULL;
 265   set *lp;
 266
 267   /* add all elements in the first list */
 268   for (lp = list1; lp; lp = lp->next)
 269     addSet (&un, lp->item);
 270
 271   /* now for all those in list2 which does not */
 272   /* already exist in the list add             */
 273   for (lp = list2; lp; lp = lp->next)
 274     if (!isinSet (un, lp->item))
 275       addSet (&un, lp->item);
 276
 277   switch (throw)
 278     {
 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 /* unionSetsWith - will return the union of the two lists          */
 295 /*-----------------------------------------------------------------*/
 296 set *
 297 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
 298 {
 299   set *un = NULL;
 300   set *lp;
 301
 302   /* add all elements in the first list */
 303   for (lp = list1; lp; lp = lp->next)
 304     addSet (&un, lp->item);
 305
 306   /* now for all those in list2 which does not */
 307   /* already exist in the list add             */
 308   for (lp = list2; lp; lp = lp->next)
 309     if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
 310       addSet (&un, lp->item);
 311
 312   switch (throw)
 313     {
 314     case THROW_SRC:
 315       setToNull ((void **) &list2);
 316       break;
 317     case THROW_DEST:
 318       setToNull ((void **) &list1);
 319       break;
 320     case THROW_BOTH:
 321       setToNull ((void **) &list1);
 322       setToNull ((void **) &list2);
 323     }
 324
 325   return un;
 326 }
 327
 328 /*-----------------------------------------------------------------*/
 329 /* intersectSets - returns list of items in common to two lists    */
 330 /*-----------------------------------------------------------------*/
 331 set *
 332 intersectSets (set * list1, set * list2, int throw)
 333 {
 334   set *in = NULL;
 335   set *lp;
 336
 337   /* we can take any one of the lists and iterate over it */
 338   for (lp = list1; lp; lp = lp->next)
 339     if (isinSet (list2, lp->item))
 340       addSetHead (&in, lp->item);
 341
 342   switch (throw)
 343     {
 344     case THROW_SRC:
 345       setToNull ((void **) &list2);
 346       break;
 347     case THROW_DEST:
 348       setToNull ((void **) &list1);
 349       break;
 350     case THROW_BOTH:
 351       setToNull ((void **) &list1);
 352       setToNull ((void **) &list2);
 353     }
 354
 355   return in;
 356 }
 357
 358 /*-----------------------------------------------------------------*/
 359 /* intersectSetsWith - returns list of items in common to two lists */
 360 /*-----------------------------------------------------------------*/
 361 set *
 362 intersectSetsWith (set * list1, set * list2,
 363                    int (*cFunc) (void *, void *), int throw)
 364 {
 365   set *in = NULL;
 366   set *lp;
 367
 368   /* we can take any one of the lists and iterate over it */
 369   for (lp = list1; lp; lp = lp->next)
 370     if (isinSetWith (list2, lp->item, cFunc))
 371       addSetHead (&in, lp->item);
 372
 373   switch (throw)
 374     {
 375     case THROW_SRC:
 376       setToNull ((void **) &list2);
 377       break;
 378     case THROW_DEST:
 379       setToNull ((void **) &list1);
 380       break;
 381     case THROW_BOTH:
 382       setToNull ((void **) &list1);
 383       setToNull ((void **) &list2);
 384     }
 385
 386   return in;
 387 }
 388
 389 /*-----------------------------------------------------------------*/
 390 /* elementsInSet - elements count of a set                         */
 391 /*-----------------------------------------------------------------*/
 392 int
 393 elementsInSet (set * s)
 394 {
 395   set *loop = s;
 396   int count = 0;
 397
 398   while (loop)
 399     {
 400       count++;
 401       loop = loop->next;
 402     }
 403
 404   return count;
 405 }
 406
 407 /*-----------------------------------------------------------------*/
 408 /* reverseSet - reverse the order of the items of a set            */
 409 /*-----------------------------------------------------------------*/
 410
 411 set *
 412 reverseSet(set * s)
 413 {
 414   set *t = NULL;
 415   set *u = NULL;
 416
 417   while(s->next) {
 418     t = s->next;
 419     s->next = u;
 420     u = s;
 421     s = t;
 422   }
 423   s->next = u;
 424   return s;
 425 }
 426
 427 /*-----------------------------------------------------------------*/
 428 /* subtractFromSet - take away from set1 elements of set2          */
 429 /*-----------------------------------------------------------------*/
 430 set *
 431 subtractFromSet (set * left, set * right, int throw)
 432 {
 433   set *result = setFromSet (left);
 434   set *loop;
 435
 436   if (right)
 437     {
 438       for (loop = right; loop; loop = loop->next)
 439         if (isinSet (result, loop->item))
 440           deleteSetItem (&result, loop->item);
 441     }
 442
 443   switch (throw)
 444     {
 445     case THROW_SRC:
 446       setToNull ((void **) &right);
 447       break;
 448     case THROW_DEST:
 449       setToNull ((void **) &left);
 450       break;
 451     case THROW_BOTH:
 452       setToNull ((void **) &left);
 453       setToNull ((void **) &right);
 454       break;
 455     }
 456
 457   return result;
 458 }
 459
 460 /*-----------------------------------------------------------------*/
 461 /* applyToSet - will call the supplied function with each item     */
 462 /*-----------------------------------------------------------------*/
 463 int
 464 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
 465 {
 466   set *lp;
 467   va_list ap;
 468   int rvalue = 0;
 469
 470   for (lp = list; lp; lp = lp->next)
 471     {
 472       va_start (ap, somefunc);
 473       rvalue += (*somefunc) (lp->item, ap);
 474       va_end (ap);
 475     }
 476   return rvalue;
 477 }
 478
 479 /*-----------------------------------------------------------------*/
 480 /* applyToSetFTrue - will call the supplied function with each item */
 481 /*                   until list is exhausted or a true is returned */
 482 /*-----------------------------------------------------------------*/
 483 int
 484 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
 485 {
 486   set *lp;
 487   va_list ap;
 488   int rvalue = 0;
 489
 490   for (lp = list; lp; lp = lp->next)
 491     {
 492       va_start (ap, somefunc);
 493       rvalue += (*somefunc) (lp->item, ap);
 494       va_end (ap);
 495       if (rvalue)
 496         break;
 497     }
 498   return rvalue;
 499 }
 500
 501 /*-----------------------------------------------------------------*/
 502 /* peekSet - will return the first element of the set              */
 503 /*-----------------------------------------------------------------*/
 504 void *
 505 peekSet (set * sp)
 506 {
 507   if (!sp)
 508     return NULL;
 509
 510   return sp->item;
 511 }
 512
 513 /*-----------------------------------------------------------------*/
 514 /* setFirstItem - gets the first item in the set, begins iteration */
 515 /*-----------------------------------------------------------------*/
 516 void *
 517 setFirstItem (set * sset)
 518 {
 519   if (sset)
 520     {
 521       sset->curr = sset;
 522       return sset->item;
 523     }
 524
 525   return NULL;
 526 }
 527 /*-----------------------------------------------------------------*/
 528 /* setNextItem - gets the next item, changes the iteration         */
 529 /*-----------------------------------------------------------------*/
 530 void *
 531 setNextItem (set * sset)
 532 {
 533   if (sset && sset->curr)
 534     {
 535       sset->curr = sset->curr->next;
 536       if (sset->curr)
 537         return sset->curr->item;
 538     }
 539   return NULL;
 540 }
 541
 542 /*-----------------------------------------------------------------*/
 543 /* getSet - will delete & return the first item from the set   */
 544 /*-----------------------------------------------------------------*/
 545 void *
 546 getSet (set ** list)
 547 {
 548   set *lp;
 549   void *item;
 550
 551   /* if list is empty then we cannot delete */
 552   if (*list == NULL)
 553     return (void *) NULL;
 554
 555
 556   /* find the item in the list */
 557   lp = *list;
 558   item = lp->item;              /* save the item */
 559
 560   *list = lp->next;
 561   return item;
 562 }
 563
 564 /*-----------------------------------------------------------------*/
 565 /* setToNull - will throw away the entire list                   */
 566 /*-----------------------------------------------------------------*/
 567 void
 568 setToNull (void **item)
 569 {
 570
 571   if (!item)
 572     return;
 573
 574   if (!*item)
 575     return;
 576   Safe_free (*item);
 577   *item = NULL;
 578 }