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 -------------------------------------------------------------------------*/
26 #if defined(__APPLE__) && defined(__MACH__)
27 #include <sys/malloc.h>
35 /*-----------------------------------------------------------------*/
36 /* newSet - will allocate & return a new set entry */
37 /*-----------------------------------------------------------------*/
43 lp = Safe_calloc (1, sizeof (set));
45 // fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
49 lp->item = lp->curr = lp->next = NULL;
54 /*-----------------------------------------------------------------*/
55 /* setFromSet - creates a list from another list */
56 /*-----------------------------------------------------------------*/
64 addSetHead (&lfl, lp->item);
72 /*-----------------------------------------------------------------*/
73 /* isSetsEqual - are the lists equal, they are equal if they have */
74 /* the same objects & the same number of objects */
75 /*-----------------------------------------------------------------*/
77 isSetsEqual (set * dest, set * src)
81 for (; dest && src; dest = dest->next, src = src->next)
83 if (!isinSet (src1, dest->item))
91 /*-----------------------------------------------------------------*/
92 /* isSetsEqualWith - are the lists equal, they are equal if they have */
93 /* the same objects & the same number of objects , compare function */
94 /*-----------------------------------------------------------------*/
96 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
100 for (; dest && src; dest = dest->next, src = src->next)
102 if (!isinSetWith (src1, dest->item, cFunc))
110 /*-----------------------------------------------------------------*/
111 /* addSetIfnotP - adds to a linked list if not already present */
112 /*-----------------------------------------------------------------*/
114 addSetIfnotP (set ** list, void *item)
117 if (isinSet (*list, item))
120 addSetHead (list, item);
125 /*-----------------------------------------------------------------*/
126 /* addSetHead - add item to head of linked list */
127 /*-----------------------------------------------------------------*/
129 addSetHead (set ** list, void *item)
136 assert (lp != lp->item);
142 /*-----------------------------------------------------------------*/
143 /* addSet - add an item to a linear linked list */
144 /*-----------------------------------------------------------------*/
146 addSet (set ** list, void *item)
150 /* item added to the tail of the list */
152 /* if the list is empty */
155 lp = *list = newSet ();
159 /* go to the end of the list */
160 for (lp = *list; lp->next; lp = lp->next);
161 lp = lp->next = newSet ();
170 /*-----------------------------------------------------------------*/
171 /* deleteItemIf - will delete from set if cond function returns 1 */
172 /*-----------------------------------------------------------------*/
174 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
181 // On the x86 va_list is just a pointer, so due to pass by value
182 // ap is not mofified by the called function. On the PPC va_list
183 // is a pointer to a structure, so ap is modified. Re-init each time.
186 if ((*cond) (sp->item, ap))
188 deleteSetItem (sset, sp->item);
198 /*-----------------------------------------------------------------*/
199 /* deleteSetItem - will delete a given item from the list */
200 /*-----------------------------------------------------------------*/
202 deleteSetItem (set ** list, void *item)
206 /* if list is empty */
210 /* if this item is at the head of the list */
211 if ((*list)->item == item)
214 *list = (*list)->next;
218 /* find the item in the list */
219 for (lp = *list; lp->next; lp = lp->next)
221 if (lp->next->item == item) /* the next one is it */
223 lp1 = lp->next; /* this one will need to be freed */
224 lp->next = lp->next->next; /* take out of list */
229 /* could not find it */
233 /*-----------------------------------------------------------------*/
234 /* isinSet - the item is present in the linked list */
235 /*-----------------------------------------------------------------*/
237 isinSet (set * list, void *item)
241 for (lp = list; lp; lp = lp->next)
242 if (lp->item == item)
248 /*-----------------------------------------------------------------*/
249 /* isinSetWith - the item is present in the linked list */
250 /*-----------------------------------------------------------------*/
252 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
256 for (lp = list; lp; lp = lp->next)
257 if ((*cFunc) (lp->item, item))
263 /*-----------------------------------------------------------------*/
264 /* unionSets - will return the union of the two lists */
265 /*-----------------------------------------------------------------*/
267 unionSets (set * list1, set * list2, int throw)
272 /* add all elements in the first list */
273 for (lp = list1; lp; lp = lp->next)
274 addSet (&un, lp->item);
276 /* now for all those in list2 which does not */
277 /* already exist in the list add */
278 for (lp = list2; lp; lp = lp->next)
279 if (!isinSet (un, lp->item))
280 addSet (&un, lp->item);
285 setToNull ((void **) &list2);
288 setToNull ((void **) &list1);
291 setToNull ((void **) &list1);
292 setToNull ((void **) &list2);
298 /*-----------------------------------------------------------------*/
299 /* unionSetsWith - will return the union of the two lists */
300 /*-----------------------------------------------------------------*/
302 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
307 /* add all elements in the first list */
308 for (lp = list1; lp; lp = lp->next)
309 addSet (&un, lp->item);
311 /* now for all those in list2 which does not */
312 /* already exist in the list add */
313 for (lp = list2; lp; lp = lp->next)
314 if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
315 addSet (&un, lp->item);
320 setToNull ((void **) &list2);
323 setToNull ((void **) &list1);
326 setToNull ((void **) &list1);
327 setToNull ((void **) &list2);
333 /*-----------------------------------------------------------------*/
334 /* intersectSets - returns list of items in common to two lists */
335 /*-----------------------------------------------------------------*/
337 intersectSets (set * list1, set * list2, int throw)
342 /* we can take any one of the lists and iterate over it */
343 for (lp = list1; lp; lp = lp->next)
344 if (isinSet (list2, lp->item))
345 addSetHead (&in, lp->item);
350 setToNull ((void **) &list2);
353 setToNull ((void **) &list1);
356 setToNull ((void **) &list1);
357 setToNull ((void **) &list2);
363 /*-----------------------------------------------------------------*/
364 /* intersectSetsWith - returns list of items in common to two lists */
365 /*-----------------------------------------------------------------*/
367 intersectSetsWith (set * list1, set * list2,
368 int (*cFunc) (void *, void *), int throw)
373 /* we can take any one of the lists and iterate over it */
374 for (lp = list1; lp; lp = lp->next)
375 if (isinSetWith (list2, lp->item, cFunc))
376 addSetHead (&in, lp->item);
381 setToNull ((void **) &list2);
384 setToNull ((void **) &list1);
387 setToNull ((void **) &list1);
388 setToNull ((void **) &list2);
394 /*-----------------------------------------------------------------*/
395 /* elementsInSet - elements count of a set */
396 /*-----------------------------------------------------------------*/
398 elementsInSet (set * s)
412 /*-----------------------------------------------------------------*/
413 /* subtractFromSet - take away from set1 elements of set2 */
414 /*-----------------------------------------------------------------*/
416 subtractFromSet (set * left, set * right, int throw)
418 set *result = setFromSet (left);
423 for (loop = right; loop; loop = loop->next)
424 if (isinSet (result, loop->item))
425 deleteSetItem (&result, loop->item);
431 setToNull ((void **) &right);
434 setToNull ((void **) &left);
437 setToNull ((void **) &left);
438 setToNull ((void **) &right);
445 /*-----------------------------------------------------------------*/
446 /* applyToSet - will call the supplied function with each item */
447 /*-----------------------------------------------------------------*/
449 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
455 for (lp = list; lp; lp = lp->next)
457 va_start (ap, somefunc);
458 rvalue += (*somefunc) (lp->item, ap);
464 /*-----------------------------------------------------------------*/
465 /* applyToSetFTrue - will call the supplied function with each item */
466 /* until list is exhausted or a true is returned */
467 /*-----------------------------------------------------------------*/
469 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
475 for (lp = list; lp; lp = lp->next)
477 va_start (ap, somefunc);
478 rvalue += (*somefunc) (lp->item, ap);
486 /*-----------------------------------------------------------------*/
487 /* peekSet - will return the first element of the set */
488 /*-----------------------------------------------------------------*/
498 /*-----------------------------------------------------------------*/
499 /* setFirstItem - gets the first item in the set, begins iteration */
500 /*-----------------------------------------------------------------*/
502 setFirstItem (set * sset)
512 /*-----------------------------------------------------------------*/
513 /* setNextItem - gets the next item, changes the iteration */
514 /*-----------------------------------------------------------------*/
516 setNextItem (set * sset)
518 if (sset && sset->curr)
520 sset->curr = sset->curr->next;
522 return sset->curr->item;
527 /*-----------------------------------------------------------------*/
528 /* getSet - will delete & return the first item from the set */
529 /*-----------------------------------------------------------------*/
536 /* if list is empty then we cannot delete */
538 return (void *) NULL;
541 /* find the item in the list */
543 item = lp->item; /* save the item */
549 /*-----------------------------------------------------------------*/
550 /* setToNull - will throw away the entire list */
551 /*-----------------------------------------------------------------*/
553 setToNull (void **item)