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