3 The following is a general-purpose set library originally developed
4 by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.
6 Sets are now structs containing the #words in the set and
7 a pointer to the actual set words.
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
15 Sets can be explicitly created with set_new(s, max_elem).
17 Sets can be declared to have minimum size to reduce realloc traffic.
18 Default minimum size = 1.
20 Sets can be explicitly initialized to have no elements (set.n == 0)
21 by using the 'empty' initializer:
24 set a = empty; -- set_deg(a) == 0
28 Example set creation and destruction:
36 b = set_of(e); -- Creates space for b and sticks in e
37 set_new(c, g); -- set_new(); set_orel() ==> set_of()
55 Made it smell less bad to C++ 7/31/93 -- TJP
73 /* elems can be a maximum of 32 bits */
74 static unsigned bitmask[] = {
75 0x00000001, 0x00000002, 0x00000004, 0x00000008,
76 0x00000010, 0x00000020, 0x00000040, 0x00000080,
77 0x00000100, 0x00000200, 0x00000400, 0x00000800,
78 0x00001000, 0x00002000, 0x00004000, 0x00008000,
79 #if !defined(PC) || defined(PC32)
80 0x00010000, 0x00020000, 0x00040000, 0x00080000,
81 0x00100000, 0x00200000, 0x00400000, 0x00800000,
82 0x01000000, 0x02000000, 0x04000000, 0x08000000,
83 0x10000000, 0x20000000, 0x40000000, 0x80000000
88 static unsigned min=1;
94 if ( a.setword != NULL ) \
95 if ( !valid(a.setword) ) \
96 {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
102 * Set the minimum size (in words) of a set to reduce realloc calls
106 set_size( unsigned n )
123 /* Fast compute degree of a set... the number
124 of elements present in the set. Assumes
125 that all word bits are used in the set
126 and that SETSIZE(a) is a multiple of WORDSIZE.
128 register unsigned *p = &(a.setword[0]);
129 register unsigned *endp = &(a.setword[a.n]);
130 register unsigned degree = 0;
133 if ( a.n == 0 ) return(0);
136 register unsigned t = *p;
137 register unsigned *b = &(bitmask[0]);
139 if (t & *b) ++degree;
140 } while (++b < &(bitmask[WORDSIZE]));
149 set_or( set b, set c )
156 /* Fast set union operation */
157 /* resultant set size is max(b, c); */
161 register unsigned *r, *p, *q, *endp;
165 if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;}
169 /* Or b,c until max of smaller set */
172 endp = &(b.setword[n]);
173 while ( p < endp ) *r++ = *p++ | *q++;
175 /* Copy rest of bigger set into result */
176 p = &(big->setword[n]);
177 endp = &(big->setword[m]);
178 while ( p < endp ) *r++ = *p++;
185 set_and( set b, set c )
192 /* Fast set intersection operation */
193 /* resultant set size is min(b, c); */
196 register unsigned *r, *p, *q, *endp;
200 n = (b.n > c.n) ? c.n : b.n;
201 if ( n == 0 ) return t; /* TJP 4-27-92 fixed for empty set */
205 /* & b,c until max of smaller set */
208 endp = &(b.setword[n]);
209 while ( p < endp ) *r++ = *p++ & *q++;
216 set_dif( set b, set c )
223 /* Fast set difference operation b - c */
224 /* resultant set size is size(b) */
227 register unsigned *r, *p, *q, *endp;
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 */
237 /* Dif b,c until smaller set size */
240 endp = &(b.setword[n]);
241 while ( p < endp ) *r++ = *p++ & (~ *q++);
243 /* Copy rest of b into result if size(b) > c */
247 endp = &(b.setword[b.n]);
248 while ( p < endp ) *r++ = *p++;
262 /* Fast singleton set constructor operation */
265 if ( b == nil ) return( empty );
267 a.setword[DIVWORD(b)] = bitmask[MODWORD(b)];
273 * Extend (or shrink) the set passed in to have n words.
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.
278 * TJP 4-27-92 Fixed so won't try to alloc 0 bytes
282 set_ext( set *a, unsigned int n )
289 register unsigned *p;
290 register unsigned *endp;
296 if ( n == 0 ) return;
297 a->setword = (unsigned *) calloc(n, BytesPerWord);
298 if ( a->setword == NULL )
300 fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
306 if ( n < min ) n = min;
307 if ( a->n == n || n == 0 ) return;
310 a->setword = (unsigned *) realloc( (char *)a->setword, (n*BytesPerWord) );
311 if ( a->setword == NULL )
313 fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
317 p = &(a->setword[size]); /* clear from old size to new size */
318 endp = &(a->setword[a->n]);
321 } while ( p < endp );
332 /* Fast not of set a (assumes all bits used) */
333 /* size of resultant set is size(a) */
334 /* ~empty = empty cause we don't know how bit to make set */
336 register unsigned *r;
337 register unsigned *p = a.setword;
338 register unsigned *endp = &(a.setword[a.n]);
342 if ( a.n == 0 ) return( empty );
348 } while ( p < endp );
355 set_equ( set a, set b )
362 /* Fast set equality comparison operation */
363 register unsigned *p = a.setword;
364 register unsigned *q = b.setword;
365 register unsigned *endp = &(a.setword[a.n]);
368 /* if ( a.n != b.n ) return(0);*/
369 if ( set_deg(a) != set_deg(b) ) return(0);
370 else if ( a.n==0 ) return(1); /* empty == empty */
373 if (*p != *q) return(0);
375 } while ( ++p < endp );
382 set_sub( set a, set b )
389 /* Fast check for a is a proper subset of b (alias a < b) */
390 register unsigned *p = a.setword;
391 register unsigned *q = b.setword;
392 register unsigned *endp = &(a.setword[a.n]);
393 register int asubset = 0;
396 if ( set_deg(a) > set_deg(b) ) return(0);
397 if ( set_deg(a)==0 && set_deg(b)==0) return(1);/* empty prop sub of empty */
398 if ( set_deg(a) == 0 ) return(1); /* empty is sub of everything */
401 if ( a.n > b.n ) return(0);
402 if (a.n==0 && b.n==0) return(1);/* empty prop sub of empty */
403 if ( a.n == 0 ) return(1); /* empty is sub of everything */
407 /* Prune tests based on guess that most set words
408 will match, particularly if a is a subset of b.
412 /* Fail -- a contains something b does not */
415 /* At least this word was a proper subset, hence
416 even if all other words are equal, a is a
422 } while (++p < endp);
424 /* at this point, a,b are equ or a subset */
425 if ( asubset || b.n == a.n ) return(asubset);
427 /* if !asubset, size(b) > size(a), then a=b and must check rest of b */
429 endp = &(b.setword[b.n]);
432 if ( *p++ ) return(1);
433 } while ( p < endp );
446 /* Fast pick any element of the set b */
447 register unsigned *p = b.setword;
448 register unsigned *endp = &(b.setword[b.n]);
451 if ( b.n == 0 ) return( nil );
455 /* Found a non-empty word of the set */
456 register unsigned i = ((p - b.setword) << LogWordSize);
457 register unsigned t = *p;
464 } while (++p < endp);
466 /* Empty -- only element it contains is nil */
472 set_el( unsigned b, set a )
480 /* nil is an element of every set */
481 if (b == nil) return(1);
482 if ( a.n == 0 || NumWords(b) > a.n ) return(0);
484 /* Otherwise, we have to check */
485 return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
496 /* Fast check for nil set */
497 register unsigned *p = a.setword;
498 register unsigned *endp = &(a.setword[a.n]);
501 if ( a.n == 0 ) return(1);
502 /* The set is not empty if any word used to store
503 the set is non-zero. This means one must be a
504 bit careful about doing things like negation.
508 } while (++p < endp);
521 /* Fast convert set a into ASCII char string...
522 assumes that all word bits are used in the set
523 and that SETSIZE is a multiple of WORDSIZE.
524 Trailing 0 bits are removed from the string.
525 if no bits are on or set is empty, "" is returned.
527 register unsigned *p = a.setword;
528 register unsigned *endp = &(a.setword[a.n]);
529 static char str_tmp[StrSize+1];
530 register char *q = &(str_tmp[0]);
533 if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
535 register unsigned t = *p;
536 register unsigned *b = &(bitmask[0]);
538 *(q++) = (char) ((t & *b) ? '1' : '0');
539 } while (++b < &(bitmask[WORDSIZE]));
540 } while (++p < endp);
542 /* Trim trailing 0s & NULL terminate the string */
543 while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
546 return(&(str_tmp[0]));
551 set_val( register char *s )
557 /* Fast convert set ASCII char string into a set.
558 If the string ends early, the remaining set bits
560 The resulting set size is just big enough to hold all elements.
563 register unsigned *p, *endp;
565 set_new(a, strlen(s));
567 endp = &(a.setword[a.n]);
569 register unsigned *b = &(bitmask[0]);
570 /* Start with a word with no bits on */
575 /* Turn-on this bit */
580 } while (++b < &(bitmask[WORDSIZE]));
581 } while (++p < endp);
587 * Or element e into set a. a can be empty.
591 set_orel( unsigned e, set *a )
599 if ( e == nil ) return;
600 if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
601 a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
605 * Or set b into set a. a can be empty. does nothing if b empty.
609 set_orin( set *a, set b )
616 /* Fast set union operation */
617 /* size(a) is max(a, b); */
619 register unsigned *p,
621 *endq = &(b.setword[b.n]);
624 if ( b.n == 0 ) return;
625 m = (a->n > b.n) ? a->n : b.n;
630 } while ( q < endq );
635 set_rm( unsigned e, set a )
642 /* Does not effect size of set */
644 if ( (e == nil) || (NumWords(e) > a.n) ) return;
645 a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
656 /* Does not effect size of set */
657 register unsigned *p = a.setword;
658 register unsigned *endp = &(a.setword[a.n]);
661 if ( a.n == 0 ) return;
664 } while ( p < endp );
676 register unsigned *p,
678 *endq = &(a.setword[a.n]);
682 if ( a.n == 0 ) return( empty );
687 } while ( q < endq );
693 * Return a nil terminated list of unsigned ints that represents all
694 * "on" bits in the bit set.
696 * e.g. {011011} --> {1, 2, 4, 5, nil}
698 * _set_pdq and set_pdq are useful when an operation is required on each element
699 * of a set. Normally, the sequence is:
701 * while ( set_deg(a) > 0 ) {
708 * t = e = set_pdq(a);
709 * while ( *e != nil ) {
715 * We have saved many set calls and have not destroyed set a.
719 _set_pdq( set a, register unsigned *q )
723 register unsigned *q;
726 register unsigned *p = a.setword,
727 *endp = &(a.setword[a.n]);
728 register unsigned e=0;
731 /* are there any space (possibility of elements)? */
732 if ( a.n == 0 ) return;
734 register unsigned t = *p;
735 register unsigned *b = &(bitmask[0]);
737 if ( t & *b ) *q++ = e;
739 } while (++b < &(bitmask[WORDSIZE]));
740 } while (++p < endp);
745 * Same as _set_pdq except allocate memory. set_pdq is the natural function
760 max_deg = WORDSIZE*a.n;
761 /* assume a.n!=0 & no elements is rare, but still ok */
762 if ( a.n == 0 ) return(NULL);
763 q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
764 if ( q == NULL ) return( NULL );
769 /* a function that produces a hash number for the set
773 set_hash( set a, register unsigned int mod )
777 register unsigned int mod;
780 /* Fast hash of set a (assumes all bits used) */
781 register unsigned *p = &(a.setword[0]);
782 register unsigned *endp = &(a.setword[a.n]);
783 register unsigned i = 0;