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 #if defined(__APPLE__) && defined(__MACH__)
  27 #include <sys/malloc.h>
  28 #else
  29 #include <malloc.h>
  30 #endif
  31 #include "newalloc.h"
  32 #include <assert.h>
  33 #include "SDCCset.h"
  34
  35 /*-----------------------------------------------------------------*/
  36 /* newSet - will allocate & return a new set entry             */
  37 /*-----------------------------------------------------------------*/
  38 set *
  39 newSet ()
  40 {
  41   set *lp;
  42
  43   lp = Safe_calloc (1, sizeof (set));
  44 //  if (lp == 0) {
  45   //  fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
  46   //  exit(1);
  47   //  }
  48
  49   lp->item = lp->curr = lp->next = NULL;
  50   return lp;
  51 }
  52
  53
  54 /*-----------------------------------------------------------------*/
  55 /* setFromSet - creates a list from another list                */
  56 /*-----------------------------------------------------------------*/
  57 set *
  58 setFromSet (set * lp)
  59 {
  60   set *lfl = NULL;
  61
  62   while (lp)
  63     {
  64       addSetHead (&lfl, lp->item);
  65       lp = lp->next;
  66     }
  67
  68   return lfl;
  69
  70 }
  71
  72 /*-----------------------------------------------------------------*/
  73 /* isSetsEqual - are the lists equal, they are equal if they have  */
  74 /*               the same objects & the same number of objects     */
  75 /*-----------------------------------------------------------------*/
  76 int
  77 isSetsEqual (set * dest, set * src)
  78 {
  79   set *src1 = src;
  80
  81   for (; dest && src; dest = dest->next, src = src->next)
  82     {
  83       if (!isinSet (src1, dest->item))
  84         return 0;
  85     }
  86   if (!dest && !src)
  87     return 1;
  88   return 0;
  89 }
  90
  91 /*-----------------------------------------------------------------*/
  92 /* isSetsEqualWith - are the lists equal, they are equal if they have  */
  93 /* the same objects & the same number of objects , compare function    */
  94 /*-----------------------------------------------------------------*/
  95 int
  96 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
  97 {
  98   set *src1 = src;
  99
 100   for (; dest && src; dest = dest->next, src = src->next)
 101     {
 102       if (!isinSetWith (src1, dest->item, cFunc))
 103         return 0;
 104     }
 105   if (!dest && !src)
 106     return 1;
 107   return 0;
 108 }
 109
 110 /*-----------------------------------------------------------------*/
 111 /* addSetIfnotP - adds to a linked list if not already present   */
 112 /*-----------------------------------------------------------------*/
 113 void *
 114 addSetIfnotP (set ** list, void *item)
 115 {
 116
 117   if (isinSet (*list, item))
 118     return item;
 119
 120   addSetHead (list, item);
 121
 122   return item;
 123 }
 124
 125 /*-----------------------------------------------------------------*/
 126 /* addSetHead - add item to head of linked list                  */
 127 /*-----------------------------------------------------------------*/
 128 void *
 129 addSetHead (set ** list, void *item)
 130 {
 131   set *lp = newSet ();
 132
 133   lp->item = item;
 134   lp->next = *list;
 135
 136   assert (lp != lp->item);
 137   *list = lp;
 138   return item;
 139
 140 }
 141
 142 /*-----------------------------------------------------------------*/
 143 /* addSet - add an item to a linear linked list                  */
 144 /*-----------------------------------------------------------------*/
 145 void *
 146 addSet (set ** list, void *item)
 147 {
 148   set *lp;
 149
 150   /* item added to the tail of the list */
 151
 152   /* if the list is empty */
 153   if (*list == NULL)
 154     {
 155       lp = *list = newSet ();
 156     }
 157   else
 158     {
 159       /* go to the end of the list */
 160       for (lp = *list; lp->next; lp = lp->next);
 161       lp = lp->next = newSet ();
 162     }
 163
 164   /* lp now all set */
 165   lp->item = item;
 166
 167   return item;
 168 }
 169
 170 /*-----------------------------------------------------------------*/
 171 /* deleteItemIf - will delete from set if cond function returns 1  */
 172 /*-----------------------------------------------------------------*/
 173 void
 174 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
 175 {
 176   set *sp = *sset;
 177   va_list ap;
 178
 179   while (sp)
 180     {
 181       // On the x86 va_list is just a pointer, so due to pass by value
 182       // ap is not mofified by the called function.  On the PPC va_list
 183       // is a pointer to a structure, so ap is modified.  Re-init each time.
 184       va_start (ap, cond);
 185
 186       if ((*cond) (sp->item, ap))
 187         {
 188           deleteSetItem (sset, sp->item);
 189           sp = *sset;
 190           continue;
 191         }
 192
 193       va_end(ap);
 194       sp = sp->next;
 195     }
 196 }
 197
 198 /*-----------------------------------------------------------------*/
 199 /* deleteSetItem - will delete a given item from the list          */
 200 /*-----------------------------------------------------------------*/
 201 void
 202 deleteSetItem (set ** list, void *item)
 203 {
 204   set *lp, *lp1;
 205
 206   /* if list is empty */
 207   if (*list == NULL)
 208     return;
 209
 210   /* if this item is at the head of the list */
 211   if ((*list)->item == item)
 212     {
 213       lp = *list;
 214       *list = (*list)->next;
 215       return;
 216     }
 217
 218   /* find the item in the list */
 219   for (lp = *list; lp->next; lp = lp->next)
 220     {
 221       if (lp->next->item == item)       /* the next one is it */
 222         {
 223           lp1 = lp->next;       /* this one will need to be freed */
 224           lp->next = lp->next->next;    /* take out of list */
 225           return;
 226         }
 227     }
 228
 229   /* could not find it */
 230   return;
 231 }
 232
 233 /*-----------------------------------------------------------------*/
 234 /* isinSet - the item is present in the linked list              */
 235 /*-----------------------------------------------------------------*/
 236 int
 237 isinSet (set * list, void *item)
 238 {
 239   set *lp;
 240
 241   for (lp = list; lp; lp = lp->next)
 242     if (lp->item == item)
 243       return 1;
 244
 245   return 0;
 246 }
 247
 248 /*-----------------------------------------------------------------*/
 249 /* isinSetWith - the item is present in the linked list            */
 250 /*-----------------------------------------------------------------*/
 251 int
 252 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
 253 {
 254   set *lp;
 255
 256   for (lp = list; lp; lp = lp->next)
 257     if ((*cFunc) (lp->item, item))
 258       return 1;
 259
 260   return 0;
 261 }
 262
 263 /*-----------------------------------------------------------------*/
 264 /* unionSets - will return the union of the two lists             */
 265 /*-----------------------------------------------------------------*/
 266 set *
 267 unionSets (set * list1, set * list2, int throw)
 268 {
 269   set *un = NULL;
 270   set *lp;
 271
 272   /* add all elements in the first list */
 273   for (lp = list1; lp; lp = lp->next)
 274     addSet (&un, lp->item);
 275
 276   /* now for all those in list2 which does not */
 277   /* already exist in the list add             */
 278   for (lp = list2; lp; lp = lp->next)
 279     if (!isinSet (un, lp->item))
 280       addSet (&un, lp->item);
 281
 282   switch (throw)
 283     {
 284     case THROW_SRC:
 285       setToNull ((void **) &list2);
 286       break;
 287     case THROW_DEST:
 288       setToNull ((void **) &list1);
 289       break;
 290     case THROW_BOTH:
 291       setToNull ((void **) &list1);
 292       setToNull ((void **) &list2);
 293     }
 294
 295   return un;
 296 }
 297
 298 /*-----------------------------------------------------------------*/
 299 /* unionSetsWith - will return the union of the two lists          */
 300 /*-----------------------------------------------------------------*/
 301 set *
 302 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
 303 {
 304   set *un = NULL;
 305   set *lp;
 306
 307   /* add all elements in the first list */
 308   for (lp = list1; lp; lp = lp->next)
 309     addSet (&un, lp->item);
 310
 311   /* now for all those in list2 which does not */
 312   /* already exist in the list add             */
 313   for (lp = list2; lp; lp = lp->next)
 314     if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
 315       addSet (&un, lp->item);
 316
 317   switch (throw)
 318     {
 319     case THROW_SRC:
 320       setToNull ((void **) &list2);
 321       break;
 322     case THROW_DEST:
 323       setToNull ((void **) &list1);
 324       break;
 325     case THROW_BOTH:
 326       setToNull ((void **) &list1);
 327       setToNull ((void **) &list2);
 328     }
 329
 330   return un;
 331 }
 332
 333 /*-----------------------------------------------------------------*/
 334 /* intersectSets - returns list of items in common to two lists    */
 335 /*-----------------------------------------------------------------*/
 336 set *
 337 intersectSets (set * list1, set * list2, int throw)
 338 {
 339   set *in = NULL;
 340   set *lp;
 341
 342   /* we can take any one of the lists and iterate over it */
 343   for (lp = list1; lp; lp = lp->next)
 344     if (isinSet (list2, lp->item))
 345       addSetHead (&in, lp->item);
 346
 347   switch (throw)
 348     {
 349     case THROW_SRC:
 350       setToNull ((void **) &list2);
 351       break;
 352     case THROW_DEST:
 353       setToNull ((void **) &list1);
 354       break;
 355     case THROW_BOTH:
 356       setToNull ((void **) &list1);
 357       setToNull ((void **) &list2);
 358     }
 359
 360   return in;
 361 }
 362
 363 /*-----------------------------------------------------------------*/
 364 /* intersectSetsWith - returns list of items in common to two lists */
 365 /*-----------------------------------------------------------------*/
 366 set *
 367 intersectSetsWith (set * list1, set * list2,
 368                    int (*cFunc) (void *, void *), int throw)
 369 {
 370   set *in = NULL;
 371   set *lp;
 372
 373   /* we can take any one of the lists and iterate over it */
 374   for (lp = list1; lp; lp = lp->next)
 375     if (isinSetWith (list2, lp->item, cFunc))
 376       addSetHead (&in, lp->item);
 377
 378   switch (throw)
 379     {
 380     case THROW_SRC:
 381       setToNull ((void **) &list2);
 382       break;
 383     case THROW_DEST:
 384       setToNull ((void **) &list1);
 385       break;
 386     case THROW_BOTH:
 387       setToNull ((void **) &list1);
 388       setToNull ((void **) &list2);
 389     }
 390
 391   return in;
 392 }
 393
 394 /*-----------------------------------------------------------------*/
 395 /* elementsInSet - elements count of a set                         */
 396 /*-----------------------------------------------------------------*/
 397 int
 398 elementsInSet (set * s)
 399 {
 400   set *loop = s;
 401   int count = 0;
 402
 403   while (loop)
 404     {
 405       count++;
 406       loop = loop->next;
 407     }
 408
 409   return count;
 410 }
 411
 412 /*-----------------------------------------------------------------*/
 413 /* subtractFromSet - take away from set1 elements of set2          */
 414 /*-----------------------------------------------------------------*/
 415 set *
 416 subtractFromSet (set * left, set * right, int throw)
 417 {
 418   set *result = setFromSet (left);
 419   set *loop;
 420
 421   if (right)
 422     {
 423       for (loop = right; loop; loop = loop->next)
 424         if (isinSet (result, loop->item))
 425           deleteSetItem (&result, loop->item);
 426     }
 427
 428   switch (throw)
 429     {
 430     case THROW_SRC:
 431       setToNull ((void **) &right);
 432       break;
 433     case THROW_DEST:
 434       setToNull ((void **) &left);
 435       break;
 436     case THROW_BOTH:
 437       setToNull ((void **) &left);
 438       setToNull ((void **) &right);
 439       break;
 440     }
 441
 442   return result;
 443 }
 444
 445 /*-----------------------------------------------------------------*/
 446 /* applyToSet - will call the supplied function with each item     */
 447 /*-----------------------------------------------------------------*/
 448 int
 449 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
 450 {
 451   set *lp;
 452   va_list ap;
 453   int rvalue = 0;
 454
 455   for (lp = list; lp; lp = lp->next)
 456     {
 457       va_start (ap, somefunc);
 458       rvalue += (*somefunc) (lp->item, ap);
 459       va_end (ap);
 460     }
 461   return rvalue;
 462 }
 463
 464 /*-----------------------------------------------------------------*/
 465 /* applyToSetFTrue - will call the supplied function with each item */
 466 /*                   until list is exhausted or a true is returned */
 467 /*-----------------------------------------------------------------*/
 468 int
 469 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
 470 {
 471   set *lp;
 472   va_list ap;
 473   int rvalue = 0;
 474
 475   for (lp = list; lp; lp = lp->next)
 476     {
 477       va_start (ap, somefunc);
 478       rvalue += (*somefunc) (lp->item, ap);
 479       va_end (ap);
 480       if (rvalue)
 481         break;
 482     }
 483   return rvalue;
 484 }
 485
 486 /*-----------------------------------------------------------------*/
 487 /* peekSet - will return the first element of the set              */
 488 /*-----------------------------------------------------------------*/
 489 void *
 490 peekSet (set * sp)
 491 {
 492   if (!sp)
 493     return NULL;
 494
 495   return sp->item;
 496 }
 497
 498 /*-----------------------------------------------------------------*/
 499 /* setFirstItem - gets the first item in the set, begins iteration */
 500 /*-----------------------------------------------------------------*/
 501 void *
 502 setFirstItem (set * sset)
 503 {
 504   if (sset)
 505     {
 506       sset->curr = sset;
 507       return sset->item;
 508     }
 509
 510   return NULL;
 511 }
 512 /*-----------------------------------------------------------------*/
 513 /* setNextItem - gets the next item, changes the iteration         */
 514 /*-----------------------------------------------------------------*/
 515 void *
 516 setNextItem (set * sset)
 517 {
 518   if (sset && sset->curr)
 519     {
 520       sset->curr = sset->curr->next;
 521       if (sset->curr)
 522         return sset->curr->item;
 523     }
 524   return NULL;
 525 }
 526
 527 /*-----------------------------------------------------------------*/
 528 /* getSet - will delete & return the first item from the set   */
 529 /*-----------------------------------------------------------------*/
 530 void *
 531 getSet (set ** list)
 532 {
 533   set *lp;
 534   void *item;
 535
 536   /* if list is empty then we cannot delete */
 537   if (*list == NULL)
 538     return (void *) NULL;
 539
 540
 541   /* find the item in the list */
 542   lp = *list;
 543   item = lp->item;              /* save the item */
 544
 545   *list = lp->next;
 546   return item;
 547 }
 548
 549 /*-----------------------------------------------------------------*/
 550 /* setToNull - will throw away the entire list                   */
 551 /*-----------------------------------------------------------------*/
 552 void
 553 setToNull (void **item)
 554 {
 555
 556   if (!item)
 557     return;
 558
 559   if (!*item)
 560     return;
 561   free (*item);
 562   *item = NULL;
 563 }