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