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 ()
  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 /* subtractFromSet - take away from set1 elements of set2          */
 409 /*-----------------------------------------------------------------*/
 410 set *
 411 subtractFromSet (set * left, set * right, int throw)
 412 {
 413   set *result = setFromSet (left);
 414   set *loop;
 415
 416   if (right)
 417     {
 418       for (loop = right; loop; loop = loop->next)
 419         if (isinSet (result, loop->item))
 420           deleteSetItem (&result, loop->item);
 421     }
 422
 423   switch (throw)
 424     {
 425     case THROW_SRC:
 426       setToNull ((void **) &right);
 427       break;
 428     case THROW_DEST:
 429       setToNull ((void **) &left);
 430       break;
 431     case THROW_BOTH:
 432       setToNull ((void **) &left);
 433       setToNull ((void **) &right);
 434       break;
 435     }
 436
 437   return result;
 438 }
 439
 440 /*-----------------------------------------------------------------*/
 441 /* applyToSet - will call the supplied function with each item     */
 442 /*-----------------------------------------------------------------*/
 443 int
 444 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
 445 {
 446   set *lp;
 447   va_list ap;
 448   int rvalue = 0;
 449
 450   for (lp = list; lp; lp = lp->next)
 451     {
 452       va_start (ap, somefunc);
 453       rvalue += (*somefunc) (lp->item, ap);
 454       va_end (ap);
 455     }
 456   return rvalue;
 457 }
 458
 459 /*-----------------------------------------------------------------*/
 460 /* applyToSetFTrue - will call the supplied function with each item */
 461 /*                   until list is exhausted or a true is returned */
 462 /*-----------------------------------------------------------------*/
 463 int
 464 applyToSetFTrue (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       if (rvalue)
 476         break;
 477     }
 478   return rvalue;
 479 }
 480
 481 /*-----------------------------------------------------------------*/
 482 /* peekSet - will return the first element of the set              */
 483 /*-----------------------------------------------------------------*/
 484 void *
 485 peekSet (set * sp)
 486 {
 487   if (!sp)
 488     return NULL;
 489
 490   return sp->item;
 491 }
 492
 493 /*-----------------------------------------------------------------*/
 494 /* setFirstItem - gets the first item in the set, begins iteration */
 495 /*-----------------------------------------------------------------*/
 496 void *
 497 setFirstItem (set * sset)
 498 {
 499   if (sset)
 500     {
 501       sset->curr = sset;
 502       return sset->item;
 503     }
 504
 505   return NULL;
 506 }
 507 /*-----------------------------------------------------------------*/
 508 /* setNextItem - gets the next item, changes the iteration         */
 509 /*-----------------------------------------------------------------*/
 510 void *
 511 setNextItem (set * sset)
 512 {
 513   if (sset && sset->curr)
 514     {
 515       sset->curr = sset->curr->next;
 516       if (sset->curr)
 517         return sset->curr->item;
 518     }
 519   return NULL;
 520 }
 521
 522 /*-----------------------------------------------------------------*/
 523 /* getSet - will delete & return the first item from the set   */
 524 /*-----------------------------------------------------------------*/
 525 void *
 526 getSet (set ** list)
 527 {
 528   set *lp;
 529   void *item;
 530
 531   /* if list is empty then we cannot delete */
 532   if (*list == NULL)
 533     return (void *) NULL;
 534
 535
 536   /* find the item in the list */
 537   lp = *list;
 538   item = lp->item;              /* save the item */
 539
 540   *list = lp->next;
 541   return item;
 542 }
 543
 544 /*-----------------------------------------------------------------*/
 545 /* setToNull - will throw away the entire list                   */
 546 /*-----------------------------------------------------------------*/
 547 void
 548 setToNull (void **item)
 549 {
 550
 551   if (!item)
 552     return;
 553
 554   if (!*item)
 555     return;
 556   Safe_free (*item);
 557   *item = NULL;
 558 }