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 /*-----------------------------------------------------------------*/
37 lp = Safe_calloc(1,sizeof(set));
39 // fprintf(stderr, "out of virtual memory: %s\n", __FILE__);
43 lp->item = lp->curr= lp->next = NULL;
48 /*-----------------------------------------------------------------*/
49 /* setFromSet - creates a list from another list */
50 /*-----------------------------------------------------------------*/
51 set *setFromSet (set *lp)
56 addSetHead(&lfl,lp->item);
64 /*-----------------------------------------------------------------*/
65 /* isSetsEqual - are the lists equal, they are equal if they have */
66 /* the same objects & the same number of objects */
67 /*-----------------------------------------------------------------*/
68 int isSetsEqual ( set *dest, set *src )
72 for (; dest && src ; dest=dest->next , src=src->next) {
73 if (!isinSet(src1, dest->item))
81 /*-----------------------------------------------------------------*/
82 /* isSetsEqualWith - are the lists equal, they are equal if they have */
83 /* the same objects & the same number of objects , compare function */
84 /*-----------------------------------------------------------------*/
85 int isSetsEqualWith ( set *dest, set *src , int (*cFunc)(void *,void *))
89 for (; dest && src ; dest=dest->next , src=src->next) {
90 if (!isinSetWith(src1, dest->item,cFunc))
98 /*-----------------------------------------------------------------*/
99 /* addSetIfnotP - adds to a linked list if not already present */
100 /*-----------------------------------------------------------------*/
101 void *addSetIfnotP ( set **list, void *item)
104 if (isinSet(*list,item))
107 addSetHead(list,item);
112 /*-----------------------------------------------------------------*/
113 /* addSetHead - add item to head of linked list */
114 /*-----------------------------------------------------------------*/
115 void *addSetHead (set **list, void *item )
122 assert(lp != lp->item);
128 /*-----------------------------------------------------------------*/
129 /* addSet - add an item to a linear linked list */
130 /*-----------------------------------------------------------------*/
131 void *addSet ( set **list , void *item )
135 /* item added to the tail of the list */
137 /* if the list is empty */
138 if (*list == NULL ) {
139 lp = *list = newSet();
141 /* go to the end of the list */
142 for (lp = *list ; lp->next ; lp = lp->next );
143 lp = lp->next = newSet();
152 /*-----------------------------------------------------------------*/
153 /* deleteItemIf - will delete from set if cond function returns 1 */
154 /*-----------------------------------------------------------------*/
155 void deleteItemIf ( set **sset, int (*cond) (void *, va_list), ... )
163 if ((*cond)(sp->item,ap)) {
164 deleteSetItem(sset,sp->item);
173 /*-----------------------------------------------------------------*/
174 /* deleteSetItem - will delete a given item from the list */
175 /*-----------------------------------------------------------------*/
176 void deleteSetItem ( set **list, void *item )
180 /* if list is empty */
184 /* if this item is at the head of the list */
185 if ((*list)->item == item ) {
187 *list = (*list)->next ;
191 /* find the item in the list */
192 for (lp = *list ; lp->next ; lp = lp->next ) {
193 if (lp->next->item == item ) /* the next one is it */ {
194 lp1 = lp->next ; /* this one will need to be freed */
195 lp->next = lp->next->next ; /* take out of list */
200 /* could not find it */
204 /*-----------------------------------------------------------------*/
205 /* isinSet - the item is present in the linked list */
206 /*-----------------------------------------------------------------*/
207 int isinSet (set *list, void *item )
211 for (lp = list ; lp ; lp = lp->next )
212 if ( lp->item == item )
218 /*-----------------------------------------------------------------*/
219 /* isinSetWith - the item is present in the linked list */
220 /*-----------------------------------------------------------------*/
221 int isinSetWith (set *list, void *item , int (*cFunc)(void *,void *) )
225 for (lp = list ; lp ; lp = lp->next )
226 if ( (*cFunc)(lp->item,item) )
232 /*-----------------------------------------------------------------*/
233 /* unionSets - will return the union of the two lists */
234 /*-----------------------------------------------------------------*/
235 set *unionSets (set *list1 , set *list2, int throw)
240 /* add all elements in the first list */
241 for (lp = list1 ; lp ; lp = lp->next )
242 addSet(&un,lp->item);
244 /* now for all those in list2 which does not */
245 /* already exist in the list add */
246 for (lp = list2 ; lp ; lp = lp->next )
247 if (!isinSet(un,lp->item))
248 addSet (&un,lp->item);
252 setToNull ((void **)&list2);
255 setToNull ((void **)&list1);
258 setToNull ((void **)&list1);
259 setToNull ((void **)&list2);
265 /*-----------------------------------------------------------------*/
266 /* unionSetsWith - will return the union of the two lists */
267 /*-----------------------------------------------------------------*/
268 set *unionSetsWith (set *list1 , set *list2, int (*cFunc)(),int throw)
273 /* add all elements in the first list */
274 for (lp = list1 ; lp ; lp = lp->next )
275 addSet (&un,lp->item);
277 /* now for all those in list2 which does not */
278 /* already exist in the list add */
279 for (lp = list2 ; lp ; lp = lp->next )
280 if (!isinSetWith(un,lp->item,cFunc))
281 addSet (&un,lp->item);
285 setToNull ((void **)&list2);
288 setToNull ((void **)&list1);
291 setToNull ((void **)&list1);
292 setToNull ((void **)&list2);
298 /*-----------------------------------------------------------------*/
299 /* intersectSets - returns list of items in common to two lists */
300 /*-----------------------------------------------------------------*/
301 set *intersectSets (set *list1, set *list2, int throw)
306 /* we can take any one of the lists and iterate over it */
307 for (lp = list1 ; lp ; lp = lp->next )
308 if (isinSet (list2,lp->item) )
309 addSetHead(&in,lp->item);
313 setToNull ((void **)&list2);
316 setToNull ((void **)&list1);
319 setToNull ((void **)&list1);
320 setToNull ((void **)&list2);
326 /*-----------------------------------------------------------------*/
327 /* intersectSetsWith - returns list of items in common to two lists*/
328 /*-----------------------------------------------------------------*/
329 set *intersectSetsWith (set *list1, set *list2,
330 int (*cFunc)(void *,void *),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 (isinSetWith (list2,lp->item,cFunc) )
338 addSetHead(&in,lp->item);
342 setToNull ((void **)&list2);
345 setToNull ((void **)&list1);
348 setToNull ((void **)&list1);
349 setToNull ((void **)&list2);
355 /*-----------------------------------------------------------------*/
356 /* elementsInSet - elements count of a set */
357 /*-----------------------------------------------------------------*/
358 int elementsInSet (set *s)
371 /*-----------------------------------------------------------------*/
372 /* subtractFromSet - take away from set1 elements of set2 */
373 /*-----------------------------------------------------------------*/
374 set *subtractFromSet (set *left, set *right, int throw)
376 set *result = setFromSet(left);
380 for (loop = right ; loop ; loop = loop->next)
381 if (isinSet(result,loop->item))
382 deleteSetItem (&result,loop->item);
387 setToNull ((void **)&right);
390 setToNull ((void **)&left);
393 setToNull ((void **)&left);
394 setToNull ((void **)&right);
401 /*-----------------------------------------------------------------*/
402 /* applyToSet - will call the supplied function with each item */
403 /*-----------------------------------------------------------------*/
404 int applyToSet ( set *list , int (*somefunc)(void *, va_list ), ...)
410 for (lp = list ; lp ; lp = lp->next ) {
411 va_start(ap,somefunc);
412 rvalue += (*somefunc)(lp->item,ap) ;
418 /*-----------------------------------------------------------------*/
419 /* applyToSetFTrue - will call the supplied function with each item*/
420 /* until list is exhausted or a true is returned */
421 /*-----------------------------------------------------------------*/
422 int applyToSetFTrue ( set *list , int (*somefunc)(void *, va_list ), ...)
428 for (lp = list ; lp ; lp = lp->next ) {
429 va_start(ap,somefunc);
430 rvalue += (*somefunc)(lp->item,ap);
438 /*-----------------------------------------------------------------*/
439 /* peekSet - will return the first element of the set */
440 /*-----------------------------------------------------------------*/
441 void *peekSet ( set *sp)
449 /*-----------------------------------------------------------------*/
450 /* setFirstItem - gets the first item in the set, begins iteration */
451 /*-----------------------------------------------------------------*/
452 void *setFirstItem (set *sset)
461 /*-----------------------------------------------------------------*/
462 /* setNextItem - gets the next item, changes the iteration */
463 /*-----------------------------------------------------------------*/
464 void *setNextItem (set *sset)
466 if (sset && sset->curr ) {
467 sset->curr = sset->curr->next ;
469 return sset->curr->item ;
474 /*-----------------------------------------------------------------*/
475 /* getSet - will delete & return the first item from the set */
476 /*-----------------------------------------------------------------*/
477 void *getSet (set **list)
482 /* if list is empty then we cannot delete */
484 return (void *) NULL ;
487 /* find the item in the list */
489 item = lp->item; /* save the item */
495 /*-----------------------------------------------------------------*/
496 /* setToNull - will throw away the entire list */
497 /*-----------------------------------------------------------------*/
498 void setToNull (void **item )