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_alloc ( 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),...)
176 // On the x86 va_list is just a pointer, so due to pass by value
177 // ap is not mofified by the called function. On the PPC va_list
178 // is a pointer to a structure, so ap is modified. Re-init each time.
181 if ((*cond) (sp->item, ap))
183 deleteSetItem (sset, sp->item);
193 /*-----------------------------------------------------------------*/
194 /* deleteSetItem - will delete a given item from the list */
195 /*-----------------------------------------------------------------*/
197 deleteSetItem (set ** list, void *item)
201 /* if list is empty */
205 /* if this item is at the head of the list */
206 if ((*list)->item == item) {
208 *list = (*list)->next;
213 /* find the item in the list */
214 for (lp = *list; lp->next; lp = lp->next) {
215 if (lp->next->item == item) { /* the next one is it */
216 lp1 = lp->next; /* this one will need to be freed */
217 lp->next = lp->next->next; /* take out of list */
223 /* could not find it */
226 /*-----------------------------------------------------------------*/
227 /* isinSet - the item is present in the linked list */
228 /*-----------------------------------------------------------------*/
230 isinSet (set * list, void *item)
234 for (lp = list; lp; lp = lp->next)
235 if (lp->item == item)
241 /*-----------------------------------------------------------------*/
242 /* isinSetWith - the item is present in the linked list */
243 /*-----------------------------------------------------------------*/
245 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
249 for (lp = list; lp; lp = lp->next)
250 if ((*cFunc) (lp->item, item))
256 /*-----------------------------------------------------------------*/
257 /* unionSets - will return the union of the two lists */
258 /*-----------------------------------------------------------------*/
260 unionSets (set * list1, set * list2, int throw)
265 /* add all elements in the first list */
266 for (lp = list1; lp; lp = lp->next)
267 addSet (&un, lp->item);
269 /* now for all those in list2 which does not */
270 /* already exist in the list add */
271 for (lp = list2; lp; lp = lp->next)
272 if (!isinSet (un, lp->item))
273 addSet (&un, lp->item);
278 setToNull ((void **) &list2);
281 setToNull ((void **) &list1);
284 setToNull ((void **) &list1);
285 setToNull ((void **) &list2);
291 /*-----------------------------------------------------------------*/
292 /* unionSetsWith - will return the union of the two lists */
293 /*-----------------------------------------------------------------*/
295 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
300 /* add all elements in the first list */
301 for (lp = list1; lp; lp = lp->next)
302 addSet (&un, lp->item);
304 /* now for all those in list2 which does not */
305 /* already exist in the list add */
306 for (lp = list2; lp; lp = lp->next)
307 if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
308 addSet (&un, lp->item);
313 setToNull ((void **) &list2);
316 setToNull ((void **) &list1);
319 setToNull ((void **) &list1);
320 setToNull ((void **) &list2);
326 /*-----------------------------------------------------------------*/
327 /* intersectSets - returns list of items in common to two lists */
328 /*-----------------------------------------------------------------*/
330 intersectSets (set * list1, set * list2, int throw)
335 /* we can take any one of the lists and iterate over it */
336 for (lp = list1; lp; lp = lp->next)
337 if (isinSet (list2, lp->item))
338 addSetHead (&in, lp->item);
343 setToNull ((void **) &list2);
346 setToNull ((void **) &list1);
349 setToNull ((void **) &list1);
350 setToNull ((void **) &list2);
356 /*-----------------------------------------------------------------*/
357 /* intersectSetsWith - returns list of items in common to two lists */
358 /*-----------------------------------------------------------------*/
360 intersectSetsWith (set * list1, set * list2,
361 int (*cFunc) (void *, void *), int throw)
366 /* we can take any one of the lists and iterate over it */
367 for (lp = list1; lp; lp = lp->next)
368 if (isinSetWith (list2, lp->item, cFunc))
369 addSetHead (&in, lp->item);
374 setToNull ((void **) &list2);
377 setToNull ((void **) &list1);
380 setToNull ((void **) &list1);
381 setToNull ((void **) &list2);
387 /*-----------------------------------------------------------------*/
388 /* elementsInSet - elements count of a set */
389 /*-----------------------------------------------------------------*/
391 elementsInSet (set * s)
405 /*-----------------------------------------------------------------*/
406 /* reverseSet - reverse the order of the items of a set */
407 /*-----------------------------------------------------------------*/
425 /*-----------------------------------------------------------------*/
426 /* subtractFromSet - take away from set1 elements of set2 */
427 /*-----------------------------------------------------------------*/
429 subtractFromSet (set * left, set * right, int throw)
431 set *result = setFromSet (left);
436 for (loop = right; loop; loop = loop->next)
437 if (isinSet (result, loop->item))
438 deleteSetItem (&result, loop->item);
444 setToNull ((void **) &right);
447 setToNull ((void **) &left);
450 setToNull ((void **) &left);
451 setToNull ((void **) &right);
458 /*-----------------------------------------------------------------*/
459 /* applyToSet - will call the supplied function with each item */
460 /*-----------------------------------------------------------------*/
462 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
468 for (lp = list; lp; lp = lp->next)
470 va_start (ap, somefunc);
471 rvalue += (*somefunc) (lp->item, ap);
477 /*-----------------------------------------------------------------*/
478 /* applyToSetFTrue - will call the supplied function with each item */
479 /* until list is exhausted or a true is returned */
480 /*-----------------------------------------------------------------*/
482 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
488 for (lp = list; lp; lp = lp->next)
490 va_start (ap, somefunc);
491 rvalue += (*somefunc) (lp->item, ap);
499 /*-----------------------------------------------------------------*/
500 /* peekSet - will return the first element of the set */
501 /*-----------------------------------------------------------------*/
511 /*-----------------------------------------------------------------*/
512 /* setFirstItem - gets the first item in the set, begins iteration */
513 /*-----------------------------------------------------------------*/
515 setFirstItem (set * sset)
525 /*-----------------------------------------------------------------*/
526 /* setNextItem - gets the next item, changes the iteration */
527 /*-----------------------------------------------------------------*/
529 setNextItem (set * sset)
531 if (sset && sset->curr)
533 sset->curr = sset->curr->next;
535 return sset->curr->item;
540 /*-----------------------------------------------------------------*/
541 /* getSet - will delete & return the first item from the set */
542 /*-----------------------------------------------------------------*/
549 /* if list is empty then we cannot delete */
551 return (void *) NULL;
554 /* find the item in the list */
556 item = lp->item; /* save the item */
562 /*-----------------------------------------------------------------*/
563 /* setToNull - will throw away the entire list */
564 /*-----------------------------------------------------------------*/
566 setToNull (void **item)
578 /*-----------------------------------------------------------------*/
579 /* deleteSet - will throw away the entire list */
580 /* note - setToNull doesn't actually throw away the whole list. */
581 /* Instead it only throws away the first item. */
582 /*-----------------------------------------------------------------*/
583 void deleteSet(set **s)