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 -------------------------------------------------------------------------*/
29 /*-----------------------------------------------------------------*/
30 /* newSet - will allocate & return a new set entry */
31 /*-----------------------------------------------------------------*/
36 ALLOC(lp,sizeof(set)) ;
38 lp->item = lp->curr= lp->next = NULL;
43 /*-----------------------------------------------------------------*/
44 /* setFromSet - creates a list from another list */
45 /*-----------------------------------------------------------------*/
46 set *setFromSet (set *lp)
51 addSetHead(&lfl,lp->item);
59 /*-----------------------------------------------------------------*/
60 /* isSetsEqual - are the lists equal, they are equal if they have */
61 /* the same objects & the same number of objects */
62 /*-----------------------------------------------------------------*/
63 int isSetsEqual ( set *dest, set *src )
67 for (; dest && src ; dest=dest->next , src=src->next) {
68 if (!isinSet(src1, dest->item))
76 /*-----------------------------------------------------------------*/
77 /* isSetsEqualWith - are the lists equal, they are equal if they have */
78 /* the same objects & the same number of objects , compare function */
79 /*-----------------------------------------------------------------*/
80 int isSetsEqualWith ( set *dest, set *src , int (*cFunc)(void *,void *))
84 for (; dest && src ; dest=dest->next , src=src->next) {
85 if (!isinSetWith(src1, dest->item,cFunc))
93 /*-----------------------------------------------------------------*/
94 /* addSetIfnotP - adds to a linked list if not already present */
95 /*-----------------------------------------------------------------*/
96 void *addSetIfnotP ( set **list, void *item)
99 if (isinSet(*list,item))
102 addSetHead(list,item);
107 /*-----------------------------------------------------------------*/
108 /* addSetHead - add item to head of linked list */
109 /*-----------------------------------------------------------------*/
110 void *addSetHead (set **list, void *item )
117 assert(lp != lp->item);
123 /*-----------------------------------------------------------------*/
124 /* addSet - add an item to a linear linked list */
125 /*-----------------------------------------------------------------*/
126 void *addSet ( set **list , void *item )
130 /* item added to the tail of the list */
132 /* if the list is empty */
133 if (*list == NULL ) {
134 lp = *list = newSet();
136 /* go to the end of the list */
137 for (lp = *list ; lp->next ; lp = lp->next );
138 lp = lp->next = newSet();
147 /*-----------------------------------------------------------------*/
148 /* deleteItemIf - will delete from set if cond function returns 1 */
149 /*-----------------------------------------------------------------*/
150 void deleteItemIf ( set **sset, int (*cond) (void *, va_list), ... )
158 if ((*cond)(sp->item,ap)) {
159 deleteSetItem(sset,sp->item);
168 /*-----------------------------------------------------------------*/
169 /* deleteSetItem - will delete a given item from the list */
170 /*-----------------------------------------------------------------*/
171 void deleteSetItem ( set **list, void *item )
175 /* if list is empty */
179 /* if this item is at the head of the list */
180 if ((*list)->item == item ) {
182 *list = (*list)->next ;
186 /* find the item in the list */
187 for (lp = *list ; lp->next ; lp = lp->next ) {
188 if (lp->next->item == item ) /* the next one is it */ {
189 lp1 = lp->next ; /* this one will need to be freed */
190 lp->next = lp->next->next ; /* take out of list */
195 /* could not find it */
199 /*-----------------------------------------------------------------*/
200 /* isinSet - the item is present in the linked list */
201 /*-----------------------------------------------------------------*/
202 int isinSet (set *list, void *item )
206 for (lp = list ; lp ; lp = lp->next )
207 if ( lp->item == item )
213 /*-----------------------------------------------------------------*/
214 /* isinSetWith - the item is present in the linked list */
215 /*-----------------------------------------------------------------*/
216 int isinSetWith (set *list, void *item , int (*cFunc)(void *,void *) )
220 for (lp = list ; lp ; lp = lp->next )
221 if ( (*cFunc)(lp->item,item) )
227 /*-----------------------------------------------------------------*/
228 /* unionSets - will return the union of the two lists */
229 /*-----------------------------------------------------------------*/
230 set *unionSets (set *list1 , set *list2, int throw)
235 /* add all elements in the first list */
236 for (lp = list1 ; lp ; lp = lp->next )
237 addSet(&un,lp->item);
239 /* now for all those in list2 which does not */
240 /* already exist in the list add */
241 for (lp = list2 ; lp ; lp = lp->next )
242 if (!isinSet(un,lp->item))
243 addSet (&un,lp->item);
247 setToNull ((void **)&list2);
250 setToNull ((void **)&list1);
253 setToNull ((void **)&list1);
254 setToNull ((void **)&list2);
260 /*-----------------------------------------------------------------*/
261 /* unionSetsWith - will return the union of the two lists */
262 /*-----------------------------------------------------------------*/
263 set *unionSetsWith (set *list1 , set *list2, int (*cFunc)(),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 (!isinSetWith(un,lp->item,cFunc))
276 addSet (&un,lp->item);
280 setToNull ((void **)&list2);
283 setToNull ((void **)&list1);
286 setToNull ((void **)&list1);
287 setToNull ((void **)&list2);
293 /*-----------------------------------------------------------------*/
294 /* intersectSets - returns list of items in common to two lists */
295 /*-----------------------------------------------------------------*/
296 set *intersectSets (set *list1, set *list2, int throw)
301 /* we can take any one of the lists and iterate over it */
302 for (lp = list1 ; lp ; lp = lp->next )
303 if (isinSet (list2,lp->item) )
304 addSetHead(&in,lp->item);
308 setToNull ((void **)&list2);
311 setToNull ((void **)&list1);
314 setToNull ((void **)&list1);
315 setToNull ((void **)&list2);
321 /*-----------------------------------------------------------------*/
322 /* intersectSetsWith - returns list of items in common to two lists*/
323 /*-----------------------------------------------------------------*/
324 set *intersectSetsWith (set *list1, set *list2,
325 int (*cFunc)(void *,void *),int throw)
330 /* we can take any one of the lists and iterate over it */
331 for (lp = list1 ; lp ; lp = lp->next )
332 if (isinSetWith (list2,lp->item,cFunc) )
333 addSetHead(&in,lp->item);
337 setToNull ((void **)&list2);
340 setToNull ((void **)&list1);
343 setToNull ((void **)&list1);
344 setToNull ((void **)&list2);
350 /*-----------------------------------------------------------------*/
351 /* elementsInSet - elements count of a set */
352 /*-----------------------------------------------------------------*/
353 int elementsInSet (set *s)
366 /*-----------------------------------------------------------------*/
367 /* subtractFromSet - take away from set1 elements of set2 */
368 /*-----------------------------------------------------------------*/
369 set *subtractFromSet (set *left, set *right, int throw)
371 set *result = setFromSet(left);
375 for (loop = right ; loop ; loop = loop->next)
376 if (isinSet(result,loop->item))
377 deleteSetItem (&result,loop->item);
382 setToNull ((void **)&right);
385 setToNull ((void **)&left);
388 setToNull ((void **)&left);
389 setToNull ((void **)&right);
396 /*-----------------------------------------------------------------*/
397 /* applyToSet - will call the supplied function with each item */
398 /*-----------------------------------------------------------------*/
399 int applyToSet ( set *list , int (*somefunc)(void *, va_list ), ...)
405 va_start(ap,somefunc);
406 for (lp = list ; lp ; lp = lp->next )
407 rvalue += (*somefunc)(lp->item,ap) ;
412 /*-----------------------------------------------------------------*/
413 /* applyToSetFTrue - will call the supplied function with each item*/
414 /* until list is exhausted or a true is returned */
415 /*-----------------------------------------------------------------*/
416 int applyToSetFTrue ( set *list , int (*somefunc)(void *, va_list ), ...)
422 va_start(ap,somefunc);
423 for (lp = list ; lp ; lp = lp->next )
424 if (rvalue += (*somefunc)(lp->item,ap))
430 /*-----------------------------------------------------------------*/
431 /* peekSet - will return the first element of the set */
432 /*-----------------------------------------------------------------*/
433 void *peekSet ( set *sp)
441 /*-----------------------------------------------------------------*/
442 /* setFirstItem - gets the first item in the set, begins iteration */
443 /*-----------------------------------------------------------------*/
444 void *setFirstItem (set *sset)
453 /*-----------------------------------------------------------------*/
454 /* setNextItem - gets the next item, changes the iteration */
455 /*-----------------------------------------------------------------*/
456 void *setNextItem (set *sset)
458 if (sset && sset->curr ) {
459 sset->curr = sset->curr->next ;
461 return sset->curr->item ;
466 /*-----------------------------------------------------------------*/
467 /* getSet - will delete & return the first item from the set */
468 /*-----------------------------------------------------------------*/
469 void *getSet (set **list)
474 /* if list is empty then we cannot delete */
476 return (void *) NULL ;
479 /* find the item in the list */
481 item = lp->item; /* save the item */
487 /*-----------------------------------------------------------------*/
488 /* setToNull - will throw away the entire list */
489 /*-----------------------------------------------------------------*/
490 void setToNull (void **item )