1 /*-----------------------------------------------------------------
2 SDCCset.c - contains support routines for sets
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
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
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.
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.
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 -------------------------------------------------------------------------*/
30 /*-----------------------------------------------------------------*/
31 /* newSet - will allocate & return a new set entry */
32 /*-----------------------------------------------------------------*/
38 lp = Safe_calloc (1, sizeof (set));
40 // fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
44 lp->item = lp->curr = lp->next = NULL;
49 /*-----------------------------------------------------------------*/
50 /* setFromSet - creates a list from another list */
51 /*-----------------------------------------------------------------*/
59 addSetHead (&lfl, lp->item);
67 /*-----------------------------------------------------------------*/
68 /* isSetsEqual - are the lists equal, they are equal if they have */
69 /* the same objects & the same number of objects */
70 /*-----------------------------------------------------------------*/
72 isSetsEqual (set * dest, set * src)
76 for (; dest && src; dest = dest->next, src = src->next)
78 if (!isinSet (src1, dest->item))
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 /*-----------------------------------------------------------------*/
91 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
95 for (; dest && src; dest = dest->next, src = src->next)
97 if (!isinSetWith (src1, dest->item, cFunc))
105 /*-----------------------------------------------------------------*/
106 /* addSetIfnotP - adds to a linked list if not already present */
107 /*-----------------------------------------------------------------*/
109 addSetIfnotP (set ** list, void *item)
112 if (isinSet (*list, item))
115 addSetHead (list, item);
120 /*-----------------------------------------------------------------*/
121 /* addSetHead - add item to head of linked list */
122 /*-----------------------------------------------------------------*/
124 addSetHead (set ** list, void *item)
131 assert (lp != lp->item);
137 /*-----------------------------------------------------------------*/
138 /* addSet - add an item to a linear linked list */
139 /*-----------------------------------------------------------------*/
141 addSet (set ** list, void *item)
145 /* item added to the tail of the list */
147 /* if the list is empty */
150 lp = *list = newSet ();
154 /* go to the end of the list */
155 for (lp = *list; lp->next; lp = lp->next);
156 lp = lp->next = newSet ();
165 /*-----------------------------------------------------------------*/
166 /* deleteItemIf - will delete from set if cond function returns 1 */
167 /*-----------------------------------------------------------------*/
169 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
178 if ((*cond) (sp->item, ap))
180 deleteSetItem (sset, sp->item);
189 /*-----------------------------------------------------------------*/
190 /* deleteSetItem - will delete a given item from the list */
191 /*-----------------------------------------------------------------*/
193 deleteSetItem (set ** list, void *item)
197 /* if list is empty */
201 /* if this item is at the head of the list */
202 if ((*list)->item == item)
205 *list = (*list)->next;
209 /* find the item in the list */
210 for (lp = *list; lp->next; lp = lp->next)
212 if (lp->next->item == item) /* the next one is it */
214 lp1 = lp->next; /* this one will need to be freed */
215 lp->next = lp->next->next; /* take out of list */
220 /* could not find it */
224 /*-----------------------------------------------------------------*/
225 /* isinSet - the item is present in the linked list */
226 /*-----------------------------------------------------------------*/
228 isinSet (set * list, void *item)
232 for (lp = list; lp; lp = lp->next)
233 if (lp->item == item)
239 /*-----------------------------------------------------------------*/
240 /* isinSetWith - the item is present in the linked list */
241 /*-----------------------------------------------------------------*/
243 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
247 for (lp = list; lp; lp = lp->next)
248 if ((*cFunc) (lp->item, item))
254 /*-----------------------------------------------------------------*/
255 /* unionSets - will return the union of the two lists */
256 /*-----------------------------------------------------------------*/
258 unionSets (set * list1, set * list2, int throw)
263 /* add all elements in the first list */
264 for (lp = list1; lp; lp = lp->next)
265 addSet (&un, lp->item);
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);
276 setToNull ((void **) &list2);
279 setToNull ((void **) &list1);
282 setToNull ((void **) &list1);
283 setToNull ((void **) &list2);
289 /*-----------------------------------------------------------------*/
290 /* unionSetsWith - will return the union of the two lists */
291 /*-----------------------------------------------------------------*/
293 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
298 /* add all elements in the first list */
299 for (lp = list1; lp; lp = lp->next)
300 addSet (&un, lp->item);
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);
311 setToNull ((void **) &list2);
314 setToNull ((void **) &list1);
317 setToNull ((void **) &list1);
318 setToNull ((void **) &list2);
324 /*-----------------------------------------------------------------*/
325 /* intersectSets - returns list of items in common to two lists */
326 /*-----------------------------------------------------------------*/
328 intersectSets (set * list1, set * list2, int throw)
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);
341 setToNull ((void **) &list2);
344 setToNull ((void **) &list1);
347 setToNull ((void **) &list1);
348 setToNull ((void **) &list2);
354 /*-----------------------------------------------------------------*/
355 /* intersectSetsWith - returns list of items in common to two lists */
356 /*-----------------------------------------------------------------*/
358 intersectSetsWith (set * list1, set * list2,
359 int (*cFunc) (void *, void *), int throw)
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);
372 setToNull ((void **) &list2);
375 setToNull ((void **) &list1);
378 setToNull ((void **) &list1);
379 setToNull ((void **) &list2);
385 /*-----------------------------------------------------------------*/
386 /* elementsInSet - elements count of a set */
387 /*-----------------------------------------------------------------*/
389 elementsInSet (set * s)
403 /*-----------------------------------------------------------------*/
404 /* subtractFromSet - take away from set1 elements of set2 */
405 /*-----------------------------------------------------------------*/
407 subtractFromSet (set * left, set * right, int throw)
409 set *result = setFromSet (left);
414 for (loop = right; loop; loop = loop->next)
415 if (isinSet (result, loop->item))
416 deleteSetItem (&result, loop->item);
422 setToNull ((void **) &right);
425 setToNull ((void **) &left);
428 setToNull ((void **) &left);
429 setToNull ((void **) &right);
436 /*-----------------------------------------------------------------*/
437 /* applyToSet - will call the supplied function with each item */
438 /*-----------------------------------------------------------------*/
440 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
446 for (lp = list; lp; lp = lp->next)
448 va_start (ap, somefunc);
449 rvalue += (*somefunc) (lp->item, ap);
455 /*-----------------------------------------------------------------*/
456 /* applyToSetFTrue - will call the supplied function with each item */
457 /* until list is exhausted or a true is returned */
458 /*-----------------------------------------------------------------*/
460 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
466 for (lp = list; lp; lp = lp->next)
468 va_start (ap, somefunc);
469 rvalue += (*somefunc) (lp->item, ap);
477 /*-----------------------------------------------------------------*/
478 /* peekSet - will return the first element of the set */
479 /*-----------------------------------------------------------------*/
489 /*-----------------------------------------------------------------*/
490 /* setFirstItem - gets the first item in the set, begins iteration */
491 /*-----------------------------------------------------------------*/
493 setFirstItem (set * sset)
503 /*-----------------------------------------------------------------*/
504 /* setNextItem - gets the next item, changes the iteration */
505 /*-----------------------------------------------------------------*/
507 setNextItem (set * sset)
509 if (sset && sset->curr)
511 sset->curr = sset->curr->next;
513 return sset->curr->item;
518 /*-----------------------------------------------------------------*/
519 /* getSet - will delete & return the first item from the set */
520 /*-----------------------------------------------------------------*/
527 /* if list is empty then we cannot delete */
529 return (void *) NULL;
532 /* find the item in the list */
534 item = lp->item; /* save the item */
540 /*-----------------------------------------------------------------*/
541 /* setToNull - will throw away the entire list */
542 /*-----------------------------------------------------------------*/
544 setToNull (void **item)