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