1 /*-----------------------------------------------------------------
2 SDCCset.c - contains support routines for doubly linked lists.
3
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
5
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
9 later version.
10
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.
15
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.
19
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 -------------------------------------------------------------------------*/
24
25 #include <stdio.h>
26 #include "newalloc.h"
27 #include "SDCCerr.h"
28 #include "SDCCset.h"
29
30 /*-----------------------------------------------------------------*/
31 /* newSet - will allocate & return a new set entry */
32 /*-----------------------------------------------------------------*/
33 set *
newSet(void)34 newSet (void)
35 {
36 set *lp;
37
38 lp = Safe_alloc (sizeof (set));
39 lp->item = lp->curr = lp->next = NULL;
40 return lp;
41 }
42
43
44 /*-----------------------------------------------------------------*/
45 /* setFromSet - creates a list from another list; the order of */
46 /* elements in new list is reverted */
47 /*-----------------------------------------------------------------*/
48 set *
setFromSet(const set * lp)49 setFromSet (const set *lp)
50 {
51 set *lfl = NULL;
52
53 while (lp)
54 {
55 addSetHead (&lfl, lp->item);
56 lp = lp->next;
57 }
58
59 return lfl;
60 }
61
62 /*-----------------------------------------------------------------*/
63 /* setFromSet - creates a list from another list; the order of */
64 /* elements in retained */
65 /*-----------------------------------------------------------------*/
66 set *
setFromSetNonRev(const set * lp)67 setFromSetNonRev (const set *lp)
68 {
69 set *lfl = NULL;
70
71 while (lp)
72 {
73 addSet (&lfl, lp->item);
74 lp = lp->next;
75 }
76
77 return lfl;
78 }
79
80 /*-----------------------------------------------------------------*/
81 /* isSetsEqual - are the lists equal, they are equal if they have */
82 /* the same objects & the same number of objects */
83 /*-----------------------------------------------------------------*/
84 int
isSetsEqual(const set * dest,const set * src)85 isSetsEqual (const set *dest, const set *src)
86 {
87 const set *src1 = src;
88
89 for (; dest && src; dest = dest->next, src = src->next)
90 {
91 if (!isinSet (src1, dest->item))
92 return 0;
93 }
94 if (!dest && !src)
95 return 1;
96 return 0;
97 }
98
99 /*-----------------------------------------------------------------*/
100 /* isSetsEqualWith - are the lists equal, they are equal if they */
101 /* have the same objects & the same number of */
102 /* objects , compare function */
103 /*-----------------------------------------------------------------*/
104 int
isSetsEqualWith(set * dest,set * src,int (* cFunc)(void *,void *))105 isSetsEqualWith (set * dest, set * src, int (*cFunc) (void *, void *))
106 {
107 set *src1 = src;
108
109 for (; dest && src; dest = dest->next, src = src->next)
110 {
111 if (!isinSetWith (src1, dest->item, cFunc))
112 return 0;
113 }
114 if (!dest && !src)
115 return 1;
116 return 0;
117 }
118
119 /*-----------------------------------------------------------------*/
120 /* addSetIfnotP - adds to a linked list if not already present */
121 /*-----------------------------------------------------------------*/
122 void *
addSetIfnotP(set ** list,void * item)123 addSetIfnotP (set ** list, void *item)
124 {
125 if (isinSet (*list, item))
126 return item;
127
128 addSetHead (list, item);
129
130 return item;
131 }
132
133 /*-----------------------------------------------------------------*/
134 /* addSetHead - add item to head of linked list */
135 /*-----------------------------------------------------------------*/
136 void *
addSetHead(set ** list,void * item)137 addSetHead (set ** list, void *item)
138 {
139 set *lp = newSet ();
140
141 lp->item = item;
142 lp->next = *list;
143
144 assert (lp != lp->item);
145 *list = lp;
146 return item;
147 }
148
149 /*-----------------------------------------------------------------*/
150 /* addSet - add an item to a linear linked list */
151 /*-----------------------------------------------------------------*/
152 void *
addSet(set ** list,void * item)153 addSet (set ** list, void *item)
154 {
155 set *lp;
156
157 if (!list)
158 werror (E_INTERNAL_ERROR,__FILE__,__LINE__, "Invalid set.");
159
160 /* item added to the tail of the list */
161
162 /* if the list is empty */
163 if (*list == NULL)
164 {
165 lp = *list = newSet ();
166 }
167 else
168 {
169 /* go to the end of the list */
170 for (lp = *list; lp->next; lp = lp->next);
171 lp = lp->next = newSet ();
172 }
173 if (!list)
174 werror (E_OUT_OF_MEM,__FILE__,__LINE__, "Can't add to set.");
175
176 /* lp now all set */
177 lp->item = item;
178
179 return item;
180 }
181
182 /*-----------------------------------------------------------------*/
183 /* deleteItemIf - will delete from set if cond function returns 1 */
184 /*-----------------------------------------------------------------*/
185 void
deleteItemIf(set ** sset,int (* cond)(void *,va_list),...)186 deleteItemIf (set ** sset, int (*cond) (void *, va_list),...)
187 {
188 set *sp = *sset;
189 va_list ap;
190
191 while (sp)
192 {
193 /*
194 * On the x86 va_list is just a pointer, so due to pass by value
195 * ap is not mofified by the called function. On the PPC va_list
196 * is a pointer to a structure, so ap is modified. Re-init each time.
197 */
198 va_start (ap, cond);
199
200 if ((*cond) (sp->item, ap))
201 {
202 deleteSetItem (sset, sp->item);
203 sp = *sset;
204 continue;
205 }
206
207 va_end(ap);
208 sp = sp->next;
209 }
210 }
211
212 /*-------------------------------------------------------------------*/
213 /* destructItemIf - will delete from set if cond function returns 1, */
214 /* upon deletion, item's destructor is also called */
215 /*-------------------------------------------------------------------*/
216 void
destructItemIf(set ** sset,void (* destructor)(void * item),int (* cond)(void *,va_list),...)217 destructItemIf (set ** sset, void (*destructor)(void * item), int (*cond) (void *, va_list),...)
218 {
219 set *sp = *sset;
220 va_list ap;
221
222 while (sp)
223 {
224 /*
225 * On the x86 va_list is just a pointer, so due to pass by value
226 * ap is not mofified by the called function. On the PPC va_list
227 * is a pointer to a structure, so ap is modified. Re-init each time.
228 */
229 va_start (ap, cond);
230
231 if ((*cond) (sp->item, ap))
232 {
233 destructor (sp->item);
234 deleteSetItem (sset, sp->item);
235 sp = *sset;
236 continue;
237 }
238
239 va_end(ap);
240 sp = sp->next;
241 }
242 }
243
244
245 /*-----------------------------------------------------------------*/
246 /* deleteSetItem - will delete a given item from the list */
247 /*-----------------------------------------------------------------*/
248 void
deleteSetItem(set ** list,void * item)249 deleteSetItem (set **list, void *item)
250 {
251 set *lp, *lp1;
252
253 /* if list is empty */
254 if (*list == NULL)
255 return;
256
257 /* if this item is at the head of the list */
258 if ((*list)->item == item)
259 {
260 lp = *list;
261 *list = (*list)->next;
262 Safe_free (lp);
263 return;
264 }
265
266 /* find the item in the list */
267 for (lp = *list; lp->next; lp = lp->next)
268 {
269 if (lp->next->item == item) /* the next one is it */
270 {
271 lp1 = lp->next; /* this one will need to be freed */
272 lp->next = lp->next->next; /* take out of list */
273 Safe_free (lp1);
274 return;
275 }
276 }
277
278 /* could not find it */
279 }
280
281 /*-----------------------------------------------------------------*/
282 /* replaceSetItem - will replace a given item in the list */
283 /*-----------------------------------------------------------------*/
284 void
replaceSetItem(set * list,void * olditem,void * newitem)285 replaceSetItem (set *list, void *olditem, void *newitem)
286 {
287 /* find the item in the list */
288 for (; list; list = list->next)
289 if (list->item == olditem)
290 {
291 list->item = newitem;
292 return;
293 }
294
295
296 /* could not find it */
297 }
298
299 /*-----------------------------------------------------------------*/
300 /* isinSet - the item is present in the linked list */
301 /*-----------------------------------------------------------------*/
302 int
isinSet(const set * list,const void * item)303 isinSet (const set *list, const void *item)
304 {
305 const set *lp;
306
307 for (lp = list; lp; lp = lp->next)
308 if (lp->item == item)
309 return 1;
310
311 return 0;
312 }
313
314 /*-----------------------------------------------------------------*/
315 /* isinSetWith - the item is present in the linked list */
316 /*-----------------------------------------------------------------*/
317 int
isinSetWith(set * list,void * item,int (* cFunc)(void *,void *))318 isinSetWith (set * list, void *item, int (*cFunc) (void *, void *))
319 {
320 set *lp;
321
322 for (lp = list; lp; lp = lp->next)
323 if ((*cFunc) (lp->item, item))
324 return 1;
325
326 return 0;
327 }
328
329 /*-----------------------------------------------------------------*/
330 /* mergeSets - append list to sset */
331 /*-----------------------------------------------------------------*/
332 void
mergeSets(set ** sset,set * list)333 mergeSets (set **sset, set *list)
334 {
335 if (*sset == NULL)
336 {
337 *sset = list;
338 }
339 else
340 {
341 set *lp;
342
343 for (lp = *sset; lp->next; lp = lp->next)
344 ;
345 lp->next = list;
346 }
347 }
348
349 /*-----------------------------------------------------------------*/
350 /* unionSets - will return the union of the two lists */
351 /*-----------------------------------------------------------------*/
352 set *
unionSets(set * list1,set * list2,int throw)353 unionSets (set * list1, set * list2, int throw)
354 {
355 set *un = NULL;
356 set *lp;
357
358 /* If we were going to throw away the destination list */
359 /* anyway, save memory and time by using it as the */
360 /* starting point for the new list. */
361 if (throw == THROW_DEST || throw == THROW_BOTH)
362 {
363 un = list1;
364 if (throw == THROW_BOTH)
365 throw = THROW_SRC;
366 else
367 throw = THROW_NONE;
368 }
369 else
370 {
371 /* add all elements in the first list */
372 for (lp = list1; lp; lp = lp->next)
373 addSet (&un, lp->item);
374 }
375
376 /* now for all those in list2 which does not */
377 /* already exist in the list add */
378 for (lp = list2; lp; lp = lp->next)
379 if (!isinSet (un, lp->item))
380 addSet (&un, lp->item);
381
382 switch (throw)
383 {
384 case THROW_SRC:
385 setToNull ((void *) &list2);
386 break;
387 case THROW_DEST:
388 setToNull ((void *) &list1);
389 break;
390 case THROW_BOTH:
391 setToNull ((void *) &list1);
392 setToNull ((void *) &list2);
393 }
394
395 return un;
396 }
397
398 /*-----------------------------------------------------------------*/
399 /* unionSetsWith - will return the union of the two lists */
400 /*-----------------------------------------------------------------*/
401 set *
unionSetsWith(set * list1,set * list2,int (* cFunc)(),int throw)402 unionSetsWith (set * list1, set * list2, int (*cFunc) (), int throw)
403 {
404 set *un = NULL;
405 set *lp;
406
407 /* add all elements in the first list */
408 for (lp = list1; lp; lp = lp->next)
409 addSet (&un, lp->item);
410
411 /* now for all those in list2 which does not */
412 /* already exist in the list add */
413 for (lp = list2; lp; lp = lp->next)
414 if (!isinSetWith (un, lp->item, (int (*)(void *, void *)) cFunc))
415 addSet (&un, lp->item);
416
417 switch (throw)
418 {
419 case THROW_SRC:
420 setToNull ((void *) &list2);
421 break;
422 case THROW_DEST:
423 setToNull ((void *) &list1);
424 break;
425 case THROW_BOTH:
426 setToNull ((void *) &list1);
427 setToNull ((void *) &list2);
428 }
429
430 return un;
431 }
432
433 /*-----------------------------------------------------------------*/
434 /* intersectSets - returns list of items in common to two lists */
435 /*-----------------------------------------------------------------*/
436 set *
intersectSets(set * list1,set * list2,int throw)437 intersectSets (set * list1, set * list2, int throw)
438 {
439 set *in = NULL;
440 set *lp;
441
442 /* we can take any one of the lists and iterate over it */
443 for (lp = list1; lp; lp = lp->next)
444 if (isinSet (list2, lp->item))
445 addSetHead (&in, lp->item);
446
447 switch (throw)
448 {
449 case THROW_SRC:
450 setToNull ((void *) &list2);
451 break;
452 case THROW_DEST:
453 setToNull ((void *) &list1);
454 break;
455 case THROW_BOTH:
456 setToNull ((void *) &list1);
457 setToNull ((void *) &list2);
458 }
459
460 return in;
461 }
462
463 /*-----------------------------------------------------------------*/
464 /* intersectSetsWith - returns list of items in common to two */
465 /* lists */
466 /*-----------------------------------------------------------------*/
467 set *
intersectSetsWith(set * list1,set * list2,int (* cFunc)(void *,void *),int throw)468 intersectSetsWith (set * list1, set * list2,
469 int (*cFunc) (void *, void *), int throw)
470 {
471 set *in = NULL;
472 set *lp;
473
474 /* we can take any one of the lists and iterate over it */
475 for (lp = list1; lp; lp = lp->next)
476 if (isinSetWith (list2, lp->item, cFunc))
477 addSetHead (&in, lp->item);
478
479 switch (throw)
480 {
481 case THROW_SRC:
482 setToNull ((void *) &list2);
483 break;
484 case THROW_DEST:
485 setToNull ((void *) &list1);
486 break;
487 case THROW_BOTH:
488 setToNull ((void *) &list1);
489 setToNull ((void *) &list2);
490 }
491
492 return in;
493 }
494
495 /*-----------------------------------------------------------------*/
496 /* elementsInSet - elements count of a set */
497 /*-----------------------------------------------------------------*/
498 int
elementsInSet(const set * s)499 elementsInSet (const set * s)
500 {
501 const set *loop = s;
502 int count = 0;
503
504 while (loop)
505 {
506 count++;
507 loop = loop->next;
508 }
509
510 return count;
511 }
512
513 /*-----------------------------------------------------------------*/
514 /* indexSet - returns the i'th item in set */
515 /*-----------------------------------------------------------------*/
516 void *
indexSet(set * s,int index)517 indexSet (set * s, int index)
518 {
519 set *loop = s;
520
521 while (loop && index--)
522 {
523 loop = loop->next;
524 }
525
526 return loop ? loop->item : NULL;
527 }
528
529
530 /*-----------------------------------------------------------------*/
531 /* reverseSet - reverse the order of the items of a set */
532 /*-----------------------------------------------------------------*/
533 set *
reverseSet(set * s)534 reverseSet (set * s)
535 {
536 set *t = NULL;
537 set *u = NULL;
538
539 while(s->next)
540 {
541 t = s->next;
542 s->next = u;
543 u = s;
544 s = t;
545 }
546 s->next = u;
547 return s;
548 }
549
550 /*-----------------------------------------------------------------*/
551 /* subtractFromSet - take away from set1 elements of set2 */
552 /*-----------------------------------------------------------------*/
553 set *
subtractFromSet(set * left,set * right,int throw)554 subtractFromSet (set * left, set * right, int throw)
555 {
556 set *result = setFromSet (left);
557 set *loop;
558
559 if (right)
560 {
561 for (loop = right; loop; loop = loop->next)
562 if (isinSet (result, loop->item))
563 deleteSetItem (&result, loop->item);
564 }
565
566 switch (throw)
567 {
568 case THROW_SRC:
569 setToNull ((void *) &right);
570 break;
571 case THROW_DEST:
572 setToNull ((void *) &left);
573 break;
574 case THROW_BOTH:
575 setToNull ((void *) &left);
576 setToNull ((void *) &right);
577 break;
578 }
579
580 return result;
581 }
582
583 /*-----------------------------------------------------------------*/
584 /* applyToSet - will call the supplied function with each item */
585 /*-----------------------------------------------------------------*/
586 int
applyToSet(set * list,int (* somefunc)(void *,va_list),...)587 applyToSet (set * list, int (*somefunc) (void *, va_list),...)
588 {
589 set *lp;
590 va_list ap;
591 int rvalue = 0;
592
593 for (lp = list; lp; lp = lp->next)
594 {
595 va_start (ap, somefunc);
596 rvalue += (*somefunc) (lp->item, ap);
597 va_end (ap);
598 }
599 return rvalue;
600 }
601
602 /*-----------------------------------------------------------------*/
603 /* applyToSetFTrue - will call the supplied function with each */
604 /* item until list is exhausted or a true is */
605 /* returned */
606 /*-----------------------------------------------------------------*/
607 int
applyToSetFTrue(set * list,int (* somefunc)(void *,va_list),...)608 applyToSetFTrue (set * list, int (*somefunc) (void *, va_list),...)
609 {
610 set *lp;
611 va_list ap;
612 int rvalue = 0;
613
614 for (lp = list; lp; lp = lp->next)
615 {
616 va_start (ap, somefunc);
617 rvalue += (*somefunc) (lp->item, ap);
618 va_end (ap);
619 if (rvalue)
620 break;
621 }
622 return rvalue;
623 }
624
625 /*-----------------------------------------------------------------*/
626 /* peekSet - will return the first element of the set */
627 /*-----------------------------------------------------------------*/
628 void *
peekSet(const set * sp)629 peekSet (const set *sp)
630 {
631 if (!sp)
632 return NULL;
633
634 return sp->item;
635 }
636
637 /*-----------------------------------------------------------------*/
638 /* setFirstItem - gets the first item in the set, begins iteration */
639 /*-----------------------------------------------------------------*/
640 void *
setFirstItem(set * sset)641 setFirstItem (set *sset)
642 {
643 if (sset)
644 {
645 sset->curr = sset;
646 return sset->item;
647 }
648
649 return NULL;
650 }
651 /*-----------------------------------------------------------------*/
652 /* setNextItem - gets the next item, changes the iteration */
653 /*-----------------------------------------------------------------*/
654 void *
setNextItem(set * sset)655 setNextItem (set * sset)
656 {
657 if (sset && sset->curr)
658 {
659 sset->curr = sset->curr->next;
660 if (sset->curr)
661 return sset->curr->item;
662 }
663 return NULL;
664 }
665
666 /*-----------------------------------------------------------------*/
667 /* getSet - will delete & return the first item from the set */
668 /*-----------------------------------------------------------------*/
669 void *
getSet(set ** list)670 getSet (set ** list)
671 {
672 set *lp;
673 void *item;
674
675 /* if list is empty then we cannot delete */
676 if (*list == NULL)
677 return (void *) NULL;
678
679 /* find the item in the list */
680 lp = *list;
681 item = lp->item; /* save the item */
682
683 *list = lp->next;
684 return item;
685 }
686
687 /*-----------------------------------------------------------------*/
688 /* setToNull - will throw away the entire list */
689 /*-----------------------------------------------------------------*/
690 void
setToNull(void ** item)691 setToNull (void **item)
692 {
693 if (!item)
694 return;
695
696 if (!*item)
697 return;
698 Safe_free (*item);
699 *item = NULL;
700 }
701
702 /*-----------------------------------------------------------------*/
703 /* deleteSet - will throw away the entire list */
704 /* note - setToNull doesn't actually throw away the whole list. */
705 /* Instead it only throws away the first item. */
706 /*-----------------------------------------------------------------*/
707 void
deleteSet(set ** s)708 deleteSet (set **s)
709 {
710 set *curr;
711 set *next;
712
713 if(!s || !*s)
714 return;
715
716 curr = *s;
717 next = curr->next;
718 while (next)
719 {
720 Safe_free (curr);
721 curr = next;
722 next = next->next;
723 }
724
725 Safe_free (curr);
726
727 *s = NULL;
728 }
729