Home | History | Annotate | Download | only in set
      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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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