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 -------------------------------------------------------------------------*/
27 /*-----------------------------------------------------------------*/
28 /* newSet - will allocate & return a new set entry */
29 /*-----------------------------------------------------------------*/
34 ALLOC(lp,sizeof(set)) ;
36 lp->item = lp->curr= lp->next = NULL;
41 /*-----------------------------------------------------------------*/
42 /* setFromSet - creates a list from another list */
43 /*-----------------------------------------------------------------*/
44 set *setFromSet (set *lp)
49 addSetHead(&lfl,lp->item);
57 /*-----------------------------------------------------------------*/
58 /* isSetsEqual - are the lists equal, they are equal if they have */
59 /* the same objects & the same number of objects */
60 /*-----------------------------------------------------------------*/
61 int isSetsEqual ( set *dest, set *src )
65 for (; dest && src ; dest=dest->next , src=src->next) {
66 if (!isinSet(src1, dest->item))
74 /*-----------------------------------------------------------------*/
75 /* isSetsEqualWith - are the lists equal, they are equal if they have */
76 /* the same objects & the same number of objects , compare function */
77 /*-----------------------------------------------------------------*/
78 int isSetsEqualWith ( set *dest, set *src , int (*cFunc)(void *,void *))
82 for (; dest && src ; dest=dest->next , src=src->next) {
83 if (!isinSetWith(src1, dest->item,cFunc))
91 /*-----------------------------------------------------------------*/
92 /* addSetIfnotP - adds to a linked list if not already present */
93 /*-----------------------------------------------------------------*/
94 void *addSetIfnotP ( set **list, void *item)
97 if (isinSet(*list,item))
100 addSetHead(list,item);
105 /*-----------------------------------------------------------------*/
106 /* addSetHead - add item to head of linked list */
107 /*-----------------------------------------------------------------*/
108 void *addSetHead (set **list, void *item )
115 assert(lp != lp->item);
121 /*-----------------------------------------------------------------*/
122 /* addSet - add an item to a linear linked list */
123 /*-----------------------------------------------------------------*/
124 void *addSet ( set **list , void *item )
128 /* item added to the tail of the list */
130 /* if the list is empty */
131 if (*list == NULL ) {
132 lp = *list = newSet();
134 /* go to the end of the list */
135 for (lp = *list ; lp->next ; lp = lp->next );
136 lp = lp->next = newSet();
145 /*-----------------------------------------------------------------*/
146 /* deleteItemIf - will delete from set if cond function returns 1 */
147 /*-----------------------------------------------------------------*/
148 void deleteItemIf ( set **sset, int (*cond) (void *, va_list), ... )
156 if ((*cond)(sp->item,ap)) {
157 deleteSetItem(sset,sp->item);
166 /*-----------------------------------------------------------------*/
167 /* deleteSetItem - will delete a given item from the list */
168 /*-----------------------------------------------------------------*/
169 void deleteSetItem ( set **list, void *item )
173 /* if list is empty */
177 /* if this item is at the head of the list */
178 if ((*list)->item == item ) {
180 *list = (*list)->next ;
184 /* find the item in the list */
185 for (lp = *list ; lp->next ; lp = lp->next ) {
186 if (lp->next->item == item ) /* the next one is it */ {
187 lp1 = lp->next ; /* this one will need to be freed */
188 lp->next = lp->next->next ; /* take out of list */
193 /* could not find it */
197 /*-----------------------------------------------------------------*/
198 /* isinSet - the item is present in the linked list */
199 /*-----------------------------------------------------------------*/
200 int isinSet (set *list, void *item )
204 for (lp = list ; lp ; lp = lp->next )
205 if ( lp->item == item )
211 /*-----------------------------------------------------------------*/
212 /* isinSetWith - the item is present in the linked list */
213 /*-----------------------------------------------------------------*/
214 int isinSetWith (set *list, void *item , int (*cFunc)(void *,void *) )
218 for (lp = list ; lp ; lp = lp->next )
219 if ( (*cFunc)(lp->item,item) )
225 /*-----------------------------------------------------------------*/
226 /* unionSets - will return the union of the two lists */
227 /*-----------------------------------------------------------------*/
228 set *unionSets (set *list1 , set *list2, int throw)
233 /* add all elements in the first list */
234 for (lp = list1 ; lp ; lp = lp->next )
235 addSet(&un,lp->item);
237 /* now for all those in list2 which does not */
238 /* already exist in the list add */
239 for (lp = list2 ; lp ; lp = lp->next )
240 if (!isinSet(un,lp->item))
241 addSet (&un,lp->item);
245 setToNull ((void **)&list2);
248 setToNull ((void **)&list1);
251 setToNull ((void **)&list1);
252 setToNull ((void **)&list2);
258 /*-----------------------------------------------------------------*/
259 /* unionSetsWith - will return the union of the two lists */
260 /*-----------------------------------------------------------------*/
261 set *unionSetsWith (set *list1 , set *list2, int (*cFunc)(),int throw)
266 /* add all elements in the first list */
267 for (lp = list1 ; lp ; lp = lp->next )
268 addSet (&un,lp->item);
270 /* now for all those in list2 which does not */
271 /* already exist in the list add */
272 for (lp = list2 ; lp ; lp = lp->next )
273 if (!isinSetWith(un,lp->item,cFunc))
274 addSet (&un,lp->item);
278 setToNull ((void **)&list2);
281 setToNull ((void **)&list1);
284 setToNull ((void **)&list1);
285 setToNull ((void **)&list2);
291 /*-----------------------------------------------------------------*/
292 /* intersectSets - returns list of items in common to two lists */
293 /*-----------------------------------------------------------------*/
294 set *intersectSets (set *list1, set *list2, int throw)
299 /* we can take any one of the lists and iterate over it */
300 for (lp = list1 ; lp ; lp = lp->next )
301 if (isinSet (list2,lp->item) )
302 addSetHead(&in,lp->item);
306 setToNull ((void **)&list2);
309 setToNull ((void **)&list1);
312 setToNull ((void **)&list1);
313 setToNull ((void **)&list2);
319 /*-----------------------------------------------------------------*/
320 /* intersectSetsWith - returns list of items in common to two lists*/
321 /*-----------------------------------------------------------------*/
322 set *intersectSetsWith (set *list1, set *list2,
323 int (*cFunc)(void *,void *),int throw)
328 /* we can take any one of the lists and iterate over it */
329 for (lp = list1 ; lp ; lp = lp->next )
330 if (isinSetWith (list2,lp->item,cFunc) )
331 addSetHead(&in,lp->item);
335 setToNull ((void **)&list2);
338 setToNull ((void **)&list1);
341 setToNull ((void **)&list1);
342 setToNull ((void **)&list2);
348 /*-----------------------------------------------------------------*/
349 /* elementsInSet - elements count of a set */
350 /*-----------------------------------------------------------------*/
351 int elementsInSet (set *s)
364 /*-----------------------------------------------------------------*/
365 /* subtractFromSet - take away from set1 elements of set2 */
366 /*-----------------------------------------------------------------*/
367 set *subtractFromSet (set *left, set *right, int throw)
369 set *result = setFromSet(left);
373 for (loop = right ; loop ; loop = loop->next)
374 if (isinSet(result,loop->item))
375 deleteSetItem (&result,loop->item);
380 setToNull ((void **)&right);
383 setToNull ((void **)&left);
386 setToNull ((void **)&left);
387 setToNull ((void **)&right);
394 /*-----------------------------------------------------------------*/
395 /* applyToSet - will call the supplied function with each item */
396 /*-----------------------------------------------------------------*/
397 int applyToSet ( set *list , int (*somefunc)(void *, va_list ), ...)
403 va_start(ap,somefunc);
404 for (lp = list ; lp ; lp = lp->next )
405 rvalue += (*somefunc)(lp->item,ap) ;
410 /*-----------------------------------------------------------------*/
411 /* applyToSetFTrue - will call the supplied function with each item*/
412 /* until list is exhausted or a true is returned */
413 /*-----------------------------------------------------------------*/
414 int applyToSetFTrue ( set *list , int (*somefunc)(void *, va_list ), ...)
420 va_start(ap,somefunc);
421 for (lp = list ; lp ; lp = lp->next )
422 if (rvalue += (*somefunc)(lp->item,ap))
428 /*-----------------------------------------------------------------*/
429 /* peekSet - will return the first element of the set */
430 /*-----------------------------------------------------------------*/
431 void *peekSet ( set *sp)
439 /*-----------------------------------------------------------------*/
440 /* setFirstItem - gets the first item in the set, begins iteration */
441 /*-----------------------------------------------------------------*/
442 void *setFirstItem (set *sset)
451 /*-----------------------------------------------------------------*/
452 /* setNextItem - gets the next item, changes the iteration */
453 /*-----------------------------------------------------------------*/
454 void *setNextItem (set *sset)
456 if (sset && sset->curr ) {
457 sset->curr = sset->curr->next ;
459 return sset->curr->item ;
464 /*-----------------------------------------------------------------*/
465 /* getSet - will delete & return the first item from the set */
466 /*-----------------------------------------------------------------*/
467 void *getSet (set **list)
472 /* if list is empty then we cannot delete */
474 return (void *) NULL ;
477 /* find the item in the list */
479 item = lp->item; /* save the item */
485 /*-----------------------------------------------------------------*/
486 /* setToNull - will throw away the entire list */
487 /*-----------------------------------------------------------------*/
488 void setToNull (void **item )