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 -------------------------------------------------------------------------*/
31 /*-----------------------------------------------------------------*/
32 /* newSet - will allocate & return a new set entry */
33 /*-----------------------------------------------------------------*/
39 lp = Safe_calloc (1, sizeof (set));
41 // fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
45 lp->item = lp->curr = lp->next = NULL;
50 /*-----------------------------------------------------------------*/
51 /* setFromSet - creates a list from another list */
52 /*-----------------------------------------------------------------*/
60 addSetHead (&lfl, lp->item);
68 /*-----------------------------------------------------------------*/
69 /* isSetsEqual - are the lists equal, they are equal if they have */
70 /* the same objects & the same number of objects */
71 /*-----------------------------------------------------------------*/
73 isSetsEqual (set * dest, set * src)
77 for (; dest && src; dest = dest->next, src = src->next)
79 if (!isinSet (src1, dest->item))
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 /*-----------------------------------------------------------------*/
92 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
96 for (; dest && src; dest = dest->next, src = src->next)
98 if (!isinSetWith (src1, dest->item, cFunc))
106 /*-----------------------------------------------------------------*/
107 /* addSetIfnotP - adds to a linked list if not already present */
108 /*-----------------------------------------------------------------*/
110 addSetIfnotP (set ** list, void *item)
113 if (isinSet (*list, item))
116 addSetHead (list, item);
121 /*-----------------------------------------------------------------*/
122 /* addSetHead - add item to head of linked list */
123 /*-----------------------------------------------------------------*/
125 addSetHead (set ** list, void *item)
132 assert (lp != lp->item);
138 /*-----------------------------------------------------------------*/
139 /* addSet - add an item to a linear linked list */
140 /*-----------------------------------------------------------------*/
142 addSet (set ** list, void *item)
146 /* item added to the tail of the list */
148 /* if the list is empty */
151 lp = *list = newSet ();
155 /* go to the end of the list */
156 for (lp = *list; lp->next; lp = lp->next);
157 lp = lp->next = newSet ();
166 /*-----------------------------------------------------------------*/
167 /* deleteItemIf - will delete from set if cond function returns 1 */
168 /*-----------------------------------------------------------------*/
170 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
177 // On the x86 va_list is just a pointer, so due to pass by value
178 // ap is not mofified by the called function. On the PPC va_list
179 // is a pointer to a structure, so ap is modified. Re-init each time.
182 if ((*cond) (sp->item, ap))
184 deleteSetItem (sset, sp->item);
194 /*-----------------------------------------------------------------*/
195 /* deleteSetItem - will delete a given item from the list */
196 /*-----------------------------------------------------------------*/
198 deleteSetItem (set ** list, void *item)
202 /* if list is empty */
206 /* if this item is at the head of the list */
207 if ((*list)->item == item)
210 *list = (*list)->next;
214 /* find the item in the list */
215 for (lp = *list; lp->next; lp = lp->next)
217 if (lp->next->item == item) /* the next one is it */
219 lp1 = lp->next; /* this one will need to be freed */
220 lp->next = lp->next->next; /* take out of list */
225 /* could not find it */
229 /*-----------------------------------------------------------------*/
230 /* isinSet - the item is present in the linked list */
231 /*-----------------------------------------------------------------*/
233 isinSet (set * list, void *item)
237 for (lp = list; lp; lp = lp->next)
238 if (lp->item == item)
244 /*-----------------------------------------------------------------*/
245 /* isinSetWith - the item is present in the linked list */
246 /*-----------------------------------------------------------------*/
248 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
252 for (lp = list; lp; lp = lp->next)
253 if ((*cFunc) (lp->item, item))
259 /*-----------------------------------------------------------------*/
260 /* unionSets - will return the union of the two lists */
261 /*-----------------------------------------------------------------*/
263 unionSets (set * list1, set * list2, int throw)
268 /* add all elements in the first list */
269 for (lp = list1; lp; lp = lp->next)
270 addSet (&un, lp->item);
272 /* now for all those in list2 which does not */
273 /* already exist in the list add */
274 for (lp = list2; lp; lp = lp->next)
275 if (!isinSet (un, lp->item))
276 addSet (&un, lp->item);
281 setToNull ((void **) &list2);
284 setToNull ((void **) &list1);
287 setToNull ((void **) &list1);
288 setToNull ((void **) &list2);
294 /*-----------------------------------------------------------------*/
295 /* unionSetsWith - will return the union of the two lists */
296 /*-----------------------------------------------------------------*/
298 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
303 /* add all elements in the first list */
304 for (lp = list1; lp; lp = lp->next)
305 addSet (&un, lp->item);
307 /* now for all those in list2 which does not */
308 /* already exist in the list add */
309 for (lp = list2; lp; lp = lp->next)
310 if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
311 addSet (&un, lp->item);
316 setToNull ((void **) &list2);
319 setToNull ((void **) &list1);
322 setToNull ((void **) &list1);
323 setToNull ((void **) &list2);
329 /*-----------------------------------------------------------------*/
330 /* intersectSets - returns list of items in common to two lists */
331 /*-----------------------------------------------------------------*/
333 intersectSets (set * list1, set * list2, int throw)
338 /* we can take any one of the lists and iterate over it */
339 for (lp = list1; lp; lp = lp->next)
340 if (isinSet (list2, lp->item))
341 addSetHead (&in, lp->item);
346 setToNull ((void **) &list2);
349 setToNull ((void **) &list1);
352 setToNull ((void **) &list1);
353 setToNull ((void **) &list2);
359 /*-----------------------------------------------------------------*/
360 /* intersectSetsWith - returns list of items in common to two lists */
361 /*-----------------------------------------------------------------*/
363 intersectSetsWith (set * list1, set * list2,
364 int (*cFunc) (void *, void *), int throw)
369 /* we can take any one of the lists and iterate over it */
370 for (lp = list1; lp; lp = lp->next)
371 if (isinSetWith (list2, lp->item, cFunc))
372 addSetHead (&in, lp->item);
377 setToNull ((void **) &list2);
380 setToNull ((void **) &list1);
383 setToNull ((void **) &list1);
384 setToNull ((void **) &list2);
390 /*-----------------------------------------------------------------*/
391 /* elementsInSet - elements count of a set */
392 /*-----------------------------------------------------------------*/
394 elementsInSet (set * s)
408 /*-----------------------------------------------------------------*/
409 /* subtractFromSet - take away from set1 elements of set2 */
410 /*-----------------------------------------------------------------*/
412 subtractFromSet (set * left, set * right, int throw)
414 set *result = setFromSet (left);
419 for (loop = right; loop; loop = loop->next)
420 if (isinSet (result, loop->item))
421 deleteSetItem (&result, loop->item);
427 setToNull ((void **) &right);
430 setToNull ((void **) &left);
433 setToNull ((void **) &left);
434 setToNull ((void **) &right);
441 /*-----------------------------------------------------------------*/
442 /* applyToSet - will call the supplied function with each item */
443 /*-----------------------------------------------------------------*/
445 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
451 for (lp = list; lp; lp = lp->next)
453 va_start (ap, somefunc);
454 rvalue += (*somefunc) (lp->item, ap);
460 /*-----------------------------------------------------------------*/
461 /* applyToSetFTrue - will call the supplied function with each item */
462 /* until list is exhausted or a true is returned */
463 /*-----------------------------------------------------------------*/
465 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
471 for (lp = list; lp; lp = lp->next)
473 va_start (ap, somefunc);
474 rvalue += (*somefunc) (lp->item, ap);
482 /*-----------------------------------------------------------------*/
483 /* peekSet - will return the first element of the set */
484 /*-----------------------------------------------------------------*/
494 /*-----------------------------------------------------------------*/
495 /* setFirstItem - gets the first item in the set, begins iteration */
496 /*-----------------------------------------------------------------*/
498 setFirstItem (set * sset)
508 /*-----------------------------------------------------------------*/
509 /* setNextItem - gets the next item, changes the iteration */
510 /*-----------------------------------------------------------------*/
512 setNextItem (set * sset)
514 if (sset && sset->curr)
516 sset->curr = sset->curr->next;
518 return sset->curr->item;
523 /*-----------------------------------------------------------------*/
524 /* getSet - will delete & return the first item from the set */
525 /*-----------------------------------------------------------------*/
532 /* if list is empty then we cannot delete */
534 return (void *) NULL;
537 /* find the item in the list */
539 item = lp->item; /* save the item */
545 /*-----------------------------------------------------------------*/
546 /* setToNull - will throw away the entire list */
547 /*-----------------------------------------------------------------*/
549 setToNull (void **item)