1 /*	set.c
2 
3 	The following is a general-purpose set library originally developed
4 	by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.
5 
6 	Sets are now structs containing the #words in the set and
7 	a pointer to the actual set words.
8 
9 	Generally, sets need not be explicitly allocated.  They are
10 	created/extended/shrunk when appropriate (e.g. in set_of()).
11 	HOWEVER, sets need to be destroyed (free()ed) when they go out of scope
12 	or are otherwise no longer needed.  A routine is provided to
13 	free a set.
14 
15 	Sets can be explicitly created with set_new(s, max_elem).
16 
17 	Sets can be declared to have minimum size to reduce realloc traffic.
18 	Default minimum size = 1.
19 
20 	Sets can be explicitly initialized to have no elements (set.n == 0)
21 	by using the 'empty' initializer:
22 
23 	Examples:
24 		set a = empty;	-- set_deg(a) == 0
25 
26 		return( empty );
27 
28 	Example set creation and destruction:
29 
30 	set
31 	set_of2(e,g)
32 	unsigned e,g;
33 	{
34 		set a,b,c;
35 
36 		b = set_of(e);		-- Creates space for b and sticks in e
37 		set_new(c, g);		-- set_new(); set_orel() ==> set_of()
38 		set_orel(g, &c);
39 		a = set_or(b, c);
40 		.
41 		.
42 		.
43 		set_free(b);
44 		set_free(c);
45 		return( a );
46 	}
47 
48 	1987 by Hank Dietz
49 
50 	Modified by:
51 		Terence Parr
52 		Purdue University
53 		October 1989
54 
55 	Made it smell less bad to C++ 7/31/93 -- TJP
56 */
57 
58 #include <stdio.h>
59 #include "pcctscfg.h"
60 #ifdef __STDC__
61 #include <stdlib.h>
62 #else
63 #include <malloc.h>
64 #endif
65 #include <string.h>
66 
67 #include "set.h"
68 
69 #define MIN(i,j) ( (i) > (j) ? (j) : (i))
70 #define MAX(i,j) ( (i) < (j) ? (j) : (i))
71 
72 /* elems can be a maximum of 32 bits */
73 static unsigned bitmask[] = {
74 	0x00000001, 0x00000002, 0x00000004, 0x00000008,
75 	0x00000010, 0x00000020, 0x00000040, 0x00000080,
76 	0x00000100, 0x00000200, 0x00000400, 0x00000800,
77 	0x00001000, 0x00002000, 0x00004000, 0x00008000,
78 #if !defined(PC) || defined(PC32)
79 	0x00010000, 0x00020000, 0x00040000, 0x00080000,
80 	0x00100000, 0x00200000, 0x00400000, 0x00800000,
81 	0x01000000, 0x02000000, 0x04000000, 0x08000000,
82 	0x10000000, 0x20000000, 0x40000000, 0x80000000
83 #endif
84 };
85 
86 set empty = set_init;
87 static unsigned min=1;
88 
89 #define StrSize		200
90 
91 #ifdef MEMCHK
92 #define CHK(a)					\
93 	if ( a.setword != NULL )	\
94 	  if ( !valid(a.setword) )	\
95 		{fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
96 #else
97 #define CHK(a)
98 #endif
99 
100 /*
101  * Set the minimum size (in words) of a set to reduce realloc calls
102  */
103 void
104 #ifdef __USE_PROTOS
set_size(unsigned n)105 set_size( unsigned n )
106 #else
107 set_size( n )
108 unsigned n;
109 #endif
110 {
111 	min = n;
112 }
113 
114 unsigned int
115 #ifdef __USE_PROTOS
set_deg(set a)116 set_deg( set a )
117 #else
118 set_deg( a )
119 set a;
120 #endif
121 {
122 	/* Fast compute degree of a set... the number
123 	   of elements present in the set.  Assumes
124 	   that all word bits are used in the set
125 	   and that SETSIZE(a) is a multiple of WORDSIZE.
126 	*/
127 	register unsigned *p = &(a.setword[0]);
128 	register unsigned *endp = NULL; /* MR27 Avoid false memory check report */
129 	register unsigned degree = 0;
130 
131 	CHK(a);
132 	if ( a.n == 0 ) return(0);
133 	endp = &(a.setword[a.n]);
134 	while ( p < endp )
135 	{
136 		register unsigned t = *p;
137 		register unsigned *b = &(bitmask[0]);
138 		do {
139 			if (t & *b) ++degree;
140 		} while (++b < &(bitmask[WORDSIZE]));
141 		p++;
142 	}
143 
144 	return(degree);
145 }
146 
147 set
148 #ifdef __USE_PROTOS
set_or(set b,set c)149 set_or( set b, set c )
150 #else
151 set_or( b, c )
152 set b;
153 set c;
154 #endif
155 {
156 	/* Fast set union operation */
157 	/* resultant set size is max(b, c); */
158 	set *big;
159 	set t;
160 	unsigned int m,n;
161 	register unsigned *r, *p, *q, *endp;
162 
163 	CHK(b); CHK(c);
164 	t = empty;
165 	if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;}
166 	set_ext(&t, m);
167 	r = t.setword;
168 
169 	/* Or b,c until max of smaller set */
170 	q = c.setword;
171 	p = b.setword;
172 	endp = &(b.setword[n]);
173 	while ( p < endp ) *r++ = *p++ | *q++;
174 
175 	/* Copy rest of bigger set into result */
176 	p = &(big->setword[n]);
177 	endp = &(big->setword[m]);
178 	while ( p < endp ) *r++ = *p++;
179 
180 	return(t);
181 }
182 
183 set
184 #ifdef __USE_PROTOS
set_and(set b,set c)185 set_and( set b, set c )
186 #else
187 set_and( b, c )
188 set b;
189 set c;
190 #endif
191 {
192 	/* Fast set intersection operation */
193 	/* resultant set size is min(b, c); */
194 	set t;
195 	unsigned int n;
196 	register unsigned *r, *p, *q, *endp;
197 
198 	CHK(b); CHK(c);
199 	t = empty;
200 	n = (b.n > c.n) ? c.n : b.n;
201 	if ( n == 0 ) return t;		/* TJP 4-27-92 fixed for empty set */
202 	set_ext(&t, n);
203 	r = t.setword;
204 
205 	/* & b,c until max of smaller set */
206 	q = c.setword;
207 	p = b.setword;
208 	endp = &(b.setword[n]);
209 	while ( p < endp ) *r++ = *p++ & *q++;
210 
211 	return(t);
212 }
213 
214 set
215 #ifdef __USE_PROTOS
set_dif(set b,set c)216 set_dif( set b, set c )
217 #else
218 set_dif( b, c )
219 set b;
220 set c;
221 #endif
222 {
223 	/* Fast set difference operation b - c */
224 	/* resultant set size is size(b) */
225 	set t;
226 	unsigned int n;
227 	register unsigned *r, *p, *q, *endp;
228 
229 	CHK(b); CHK(c);
230 	t = empty;
231 	n = (b.n <= c.n) ? b.n : c.n ;
232 	if ( b.n == 0 ) return t;		/* TJP 4-27-92 fixed for empty set */
233 									/* WEC 12-1-92 fixed for c.n = 0 */
234 	set_ext(&t, b.n);
235 	r = t.setword;
236 
237 	/* Dif b,c until smaller set size */
238 	q = c.setword;
239 	p = b.setword;
240 	endp = &(b.setword[n]);
241 	while ( p < endp ) *r++ = *p++ & (~ *q++);
242 
243 	/* Copy rest of b into result if size(b) > c */
244 	if ( b.n > n )
245 	{
246 		p = &(b.setword[n]);
247 		endp = &(b.setword[b.n]);
248 		while ( p < endp ) *r++ = *p++;
249 	}
250 
251 	return(t);
252 }
253 
254 set
255 #ifdef __USE_PROTOS
set_of(unsigned b)256 set_of( unsigned b )
257 #else
258 set_of( b )
259 unsigned b;
260 #endif
261 {
262 	/* Fast singleton set constructor operation */
263 	static set a;
264 
265 	if ( b == nil ) return( empty );
266 	set_new(a, b);
267 	a.setword[DIVWORD(b)] = bitmask[MODWORD(b)];
268 
269 	return(a);
270 }
271 
272 /*
273  * Extend (or shrink) the set passed in to have n words.
274  *
275  * if n is smaller than the minimum, boost n to have the minimum.
276  * if the new set size is the same as the old one, do nothing.
277  *
278  * TJP 4-27-92 Fixed so won't try to alloc 0 bytes
279  */
280 void
281 #ifdef __USE_PROTOS
set_ext(set * a,unsigned int n)282 set_ext( set *a, unsigned int n )
283 #else
284 set_ext( a, n )
285 set *a;
286 unsigned int n;
287 #endif
288 {
289 	register unsigned *p;
290 	register unsigned *endp;
291 	unsigned int size;
292 
293 	CHK((*a));
294     if ( a->n == 0 )
295     {
296 		if ( n == 0 ) return;
297 		if (a->setword != NULL) {
298 			free (a->setword);	/* MR20 */
299 		}
300         a->setword = (unsigned *) calloc(n, BytesPerWord);
301         if ( a->setword == NULL )
302         {
303             fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
304             exit(-1);
305         }
306         a->n = n;
307         return;
308     }
309 	if ( n < min ) n = min;
310 	if ( a->n == n || n == 0 ) return;
311 	size = a->n;
312 	a->n = n;
313 	a->setword = (unsigned *) realloc( (char *)a->setword, (n*BytesPerWord) );
314 	if ( a->setword == NULL )
315 	{
316 		fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
317 		exit(-1);
318 	}
319 
320 	p    = &(a->setword[size]);		/* clear from old size to new size */
321 	endp = &(a->setword[a->n]);
322 	do {
323 		*p++ = 0;
324 	} while ( p < endp );
325 }
326 
327 set
328 #ifdef __USE_PROTOS
set_not(set a)329 set_not( set a )
330 #else
331 set_not( a )
332 set a;
333 #endif
334 {
335 	/* Fast not of set a (assumes all bits used) */
336 	/* size of resultant set is size(a) */
337 	/* ~empty = empty cause we don't know how bit to make set */
338 	set t;
339 	register unsigned *r;
340 	register unsigned *p = a.setword;
341 	register unsigned *endp = &(a.setword[a.n]);
342 
343 	CHK(a);
344 	t = empty;
345 	if ( a.n == 0 ) return( empty );
346 	set_ext(&t, a.n);
347 	r = t.setword;
348 
349 	do {
350 		*r++ = (~ *p++);
351 	} while ( p < endp );
352 
353 	return(t);
354 }
355 
356 int
357 #ifdef __USE_PROTOS
set_equ(set a,set b)358 set_equ( set a, set b )
359 #else
360 set_equ( a, b )
361 set a;
362 set b;
363 #endif
364 {
365 /* 8-Nov-97     Make it work with sets of different sizes       */
366 /*              Easy to understand, too.  Probably faster.      */
367 /*              Check for a equal to b                          */
368 
369     unsigned int    count;      /* MR11 */
370     unsigned int    i;          /* MR11 */
371 
372 	CHK(a); CHK(b);
373 
374     count=MIN(a.n,b.n);
375     if (count == 0) return 1;
376     for (i=0; i < count; i++) {
377       if (a.setword[i] != b.setword[i]) return 0;
378     };
379     if (a.n < b.n) {
380       for (i=count; i < b.n; i++) {
381         if (b.setword[i] != 0) return 0;
382       }
383       return 1;
384     } else if (a.n > b.n) {
385       for (i=count; i < a.n; i++) {
386         if (a.setword[i] != 0) return 0;
387       }
388       return 1;
389     } else {
390       return 1;
391     };
392 }
393 
394 int
395 #ifdef __USE_PROTOS
set_sub(set a,set b)396 set_sub( set a, set b )
397 #else
398 set_sub( a, b )
399 set a;
400 set b;
401 #endif
402 {
403 
404 /* 8-Nov-97     Make it work with sets of different sizes       */
405 /*              Easy to understand, too.  Probably faster.      */
406 /*              Check for a is a PROPER subset of b             */
407 
408     unsigned int    count;
409     unsigned int    i;
410 
411 	CHK(a); CHK(b);
412 
413     if (a.n == 0) return 1;
414     count=MIN(a.n,b.n);
415     for (i=0; i < count; i++) {
416       if (a.setword[i] & ~b.setword[i]) return 0;
417     };
418     if (a.n <= b.n) {
419       return 1;
420     } else {
421       for (i=count; i<a.n ; i++) {
422         if (a.setword[i]) return 0;
423       };
424     };
425     return 1;
426 }
427 
428 unsigned
429 #ifdef __USE_PROTOS
set_int(set b)430 set_int( set b )
431 #else
432 set_int( b )
433 set b;
434 #endif
435 {
436 	/* Fast pick any element of the set b */
437 	register unsigned *p = b.setword;
438 	register unsigned *endp = &(b.setword[b.n]);
439 
440 	CHK(b);
441 	if ( b.n == 0 ) return( nil );
442 
443 	do {
444 		if (*p) {
445 			/* Found a non-empty word of the set */
446 			register unsigned i = ((p - b.setword) << LogWordSize);
447 			register unsigned t = *p;
448 			p = &(bitmask[0]);
449 			while (!(*p & t)) {
450 				++i; ++p;
451 			}
452 			return(i);
453 		}
454 	} while (++p < endp);
455 
456 	/* Empty -- only element it contains is nil */
457 	return(nil);
458 }
459 
460 int
461 #ifdef __USE_PROTOS
set_el(unsigned b,set a)462 set_el( unsigned b, set a )
463 #else
464 set_el( b, a )
465 unsigned b;
466 set a;
467 #endif
468 {
469 	CHK(a);
470 	/* nil is an element of every set */
471 	if (b == nil) return(1);
472 	if ( a.n == 0 || NumWords(b) > a.n ) return(0);
473 
474 	/* Otherwise, we have to check */
475 	return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
476 }
477 
478 int
479 #ifdef __USE_PROTOS
set_nil(set a)480 set_nil( set a )
481 #else
482 set_nil( a )
483 set a;
484 #endif
485 {
486 	/* Fast check for nil set */
487 	register unsigned *p = a.setword;
488 	register unsigned *endp;
489 
490 	CHK(a);
491 	if ( a.n == 0 ) return(1);
492 	endp = &(a.setword[a.n]);
493 
494 	/* The set is not empty if any word used to store
495 	   the set is non-zero.  This means one must be a
496 	   bit careful about doing things like negation.
497 	*/
498 	do {
499 		if (*p) return(0);
500 	} while (++p < endp);
501 
502 	return(1);
503 }
504 
505 char *
506 #ifdef __USE_PROTOS
set_str(set a)507 set_str( set a )
508 #else
509 set_str( a )
510 set a;
511 #endif
512 {
513 	/* Fast convert set a into ASCII char string...
514 	   assumes that all word bits are used in the set
515 	   and that SETSIZE is a multiple of WORDSIZE.
516 	   Trailing 0 bits are removed from the string.
517 	   if no bits are on or set is empty, "" is returned.
518 	*/
519 	register unsigned *p = a.setword;
520 	register unsigned *endp = &(a.setword[a.n]);
521 	static char str_tmp[StrSize+1];
522 	register char *q = &(str_tmp[0]);
523 
524 	CHK(a);
525 	if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
526 	do {
527 		register unsigned t = *p;
528 		register unsigned *b = &(bitmask[0]);
529 		do {
530 			*(q++) = (char) ((t & *b) ? '1' : '0');
531 		} while (++b < &(bitmask[WORDSIZE]));
532 	} while (++p < endp);
533 
534 	/* Trim trailing 0s & NULL terminate the string */
535 	while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
536 	*q = 0;
537 
538 	return(&(str_tmp[0]));
539 }
540 
541 set
542 #ifdef __USE_PROTOS
set_val(register char * s)543 set_val( register char *s )
544 #else
545 set_val( s )
546 register char *s;
547 #endif
548 {
549 	/* Fast convert set ASCII char string into a set.
550 	   If the string ends early, the remaining set bits
551 	   are all made zero.
552 	   The resulting set size is just big enough to hold all elements.
553 	*/
554 	static set a;
555 	register unsigned *p, *endp;
556 
557 	set_new(a, strlen(s));
558 	p = a.setword;
559 	endp = &(a.setword[a.n]);
560 	do {
561 		register unsigned *b = &(bitmask[0]);
562 		/* Start with a word with no bits on */
563 		*p = 0;
564 		do {
565 			if (*s) {
566 				if (*s == '1') {
567 					/* Turn-on this bit */
568 					*p |= *b;
569 				}
570 				++s;
571 			}
572 		} while (++b < &(bitmask[WORDSIZE]));
573 	} while (++p < endp);
574 
575 	return(a);
576 }
577 
578 /*
579  * Or element e into set a.  a can be empty.
580  */
581 void
582 #ifdef __USE_PROTOS
set_orel(unsigned e,set * a)583 set_orel( unsigned e, set *a )
584 #else
585 set_orel( e, a )
586 unsigned e;
587 set *a;
588 #endif
589 {
590 	CHK((*a));
591 	if ( e == nil ) return;
592 	if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
593 	a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
594 }
595 
596 /*
597  * Or set b into set a.  a can be empty. does nothing if b empty.
598  */
599 void
600 #ifdef __USE_PROTOS
set_orin(set * a,set b)601 set_orin( set *a, set b )
602 #else
603 set_orin( a, b )
604 set *a;
605 set b;
606 #endif
607 {
608 	/* Fast set union operation */
609 	/* size(a) is max(a, b); */
610 	unsigned int m;
611 	register unsigned *p,
612 					  *q    = b.setword,
613 					  *endq; /* MR20 */
614 
615 	CHK((*a)); CHK(b);
616 	if ( b.n == 0 ) return;
617 	endq = &(b.setword[b.n]); /* MR20 */
618 	m = (a->n > b.n) ? a->n : b.n;
619 	set_ext(a, m);
620 	p = a->setword;
621 	do {
622 		*p++ |= *q++;
623 	} while ( q < endq );
624 }
625 
626 /*
627  * And set b into set a.  a can be empty. does nothing if b empty.
628  */
629 void
630 #ifdef __USE_PROTOS
set_andin(set * a,set b)631 set_andin( set *a, set b )
632 #else
633 set_andin( a, b )
634 set *a;
635 set b;
636 #endif
637 {
638 	/* Fast set intersection operation */
639 	/* size(a) is max(a, b); */
640 	unsigned int m;
641 	register unsigned *p,
642 					  *q    = b.setword,
643 					  *endq = &(b.setword[b.n]);
644 
645 	CHK((*a)); CHK(b);
646 	if ( b.n == 0 ) return;
647 	m = (a->n > b.n) ? a->n : b.n;
648 	set_ext(a, m);
649 	p = a->setword;
650 	do {
651 		*p++ &= *q++;
652 	} while ( q < endq );
653 }
654 
655 void
656 #ifdef __USE_PROTOS
set_rm(unsigned e,set a)657 set_rm( unsigned e, set a )
658 #else
659 set_rm( e, a )
660 unsigned e;
661 set a;
662 #endif
663 {
664 	/* Does not effect size of set */
665 	CHK(a);
666 	if ( (e == nil) || (NumWords(e) > a.n) ) return;
667 	a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
668 }
669 
670 void
671 #ifdef __USE_PROTOS
set_clr(set a)672 set_clr( set a )
673 #else
674 set_clr( a )
675 set a;
676 #endif
677 {
678 	/* Does not effect size of set */
679 	register unsigned *p = a.setword;
680 	register unsigned *endp;
681 
682 	CHK(a);
683 	if ( a.n == 0 ) return;
684 	endp = &(a.setword[a.n]);
685 	do {
686 		*p++ = 0;
687 	} while ( p < endp );
688 }
689 
690 set
691 #ifdef __USE_PROTOS
set_dup(set a)692 set_dup( set a )
693 #else
694 set_dup( a )
695 set a;
696 #endif
697 {
698 	set b;
699 	register unsigned *p,
700 					  *q    = a.setword,
701 					  *endq; /* MR20 */
702 
703 	CHK(a);
704 	b = empty;
705 	if ( a.n == 0 ) return( empty );
706 	endq = &(a.setword[a.n]);	/* MR20 */
707 	set_ext(&b, a.n);
708 	p = b.setword;
709 	do {
710 		*p++ = *q++;
711 	} while ( q < endq );
712 
713 	return(b);
714 }
715 
716 /*
717  * Return a nil terminated list of unsigned ints that represents all
718  * "on" bits in the bit set.
719  *
720  * e.g. {011011} --> {1, 2, 4, 5, nil}
721  *
722  * _set_pdq and set_pdq are useful when an operation is required on each element
723  * of a set.  Normally, the sequence is:
724  *
725  *		while ( set_deg(a) > 0 ) {
726  *			e = set_int(a);
727  *			set_rm(e, a);
728  *			...process e...
729  *		}
730  * Now,
731  *
732  *		t = e = set_pdq(a);
733  *		while ( *e != nil ) {
734  *			...process *e...
735  *			e++;
736  *		}
737  *		free( t );
738  *
739  * We have saved many set calls and have not destroyed set a.
740  */
741 void
742 #ifdef __USE_PROTOS
_set_pdq(set a,register unsigned * q)743 _set_pdq( set a, register unsigned *q )
744 #else
745 _set_pdq( a, q )
746 set a;
747 register unsigned *q;
748 #endif
749 {
750 	register unsigned *p = a.setword,
751 					  *endp = &(a.setword[a.n]);
752 	register unsigned e=0;
753 
754 	CHK(a);
755 	/* are there any space (possibility of elements)? */
756 	if ( a.n == 0 ) return;
757 	do {
758 		register unsigned t = *p;
759 		register unsigned *b = &(bitmask[0]);
760 		do {
761 			if ( t & *b ) *q++ = e;
762 			++e;
763 		} while (++b < &(bitmask[WORDSIZE]));
764 	} while (++p < endp);
765 	*q = nil;
766 }
767 
768 /*
769  * Same as _set_pdq except allocate memory.  set_pdq is the natural function
770  * to use.
771  */
772 unsigned *
773 #ifdef __USE_PROTOS
set_pdq(set a)774 set_pdq( set a )
775 #else
776 set_pdq( a )
777 set a;
778 #endif
779 {
780 	unsigned *q;
781 	int max_deg;
782 
783 	CHK(a);
784 	max_deg = WORDSIZE*a.n;
785 	/* assume a.n!=0 & no elements is rare, but still ok */
786 	if ( a.n == 0 ) return(NULL);
787 	q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
788 	if ( q == NULL ) return( NULL );
789 	_set_pdq(a, q);
790 	return( q );
791 }
792 
793 /* a function that produces a hash number for the set
794  */
795 unsigned int
796 #ifdef __USE_PROTOS
set_hash(set a,register unsigned int mod)797 set_hash( set a, register unsigned int mod )
798 #else
799 set_hash( a, mod )
800 set a;
801 register unsigned int mod;
802 #endif
803 {
804 	/* Fast hash of set a (assumes all bits used) */
805 	register unsigned *p = &(a.setword[0]);
806 	register unsigned *endp = &(a.setword[a.n]);
807 	register unsigned i = 0;
808 
809 	CHK(a);
810 	while (p<endp){
811 		i += (*p);
812 		++p;
813 	}
814 
815 	return(i % mod);
816 }
817