+++ /dev/null
-/* set.c\r
-\r
- The following is a general-purpose set library originally developed\r
- by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.\r
- \r
- Sets are now structs containing the #words in the set and\r
- a pointer to the actual set words.\r
- \r
- Generally, sets need not be explicitly allocated. They are\r
- created/extended/shrunk when appropriate (e.g. in set_of()).\r
- HOWEVER, sets need to be destroyed (free()ed) when they go out of scope\r
- or are otherwise no longer needed. A routine is provided to\r
- free a set.\r
- \r
- Sets can be explicitly created with set_new(s, max_elem).\r
- \r
- Sets can be declared to have minimum size to reduce realloc traffic.\r
- Default minimum size = 1.\r
- \r
- Sets can be explicitly initialized to have no elements (set.n == 0)\r
- by using the 'empty' initializer:\r
- \r
- Examples:\r
- set a = empty; -- set_deg(a) == 0\r
- \r
- return( empty );\r
- \r
- Example set creation and destruction:\r
- \r
- set\r
- set_of2(e,g)\r
- unsigned e,g;\r
- {\r
- set a,b,c;\r
- \r
- b = set_of(e); -- Creates space for b and sticks in e\r
- set_new(c, g); -- set_new(); set_orel() ==> set_of()\r
- set_orel(g, &c);\r
- a = set_or(b, c);\r
- .\r
- .\r
- .\r
- set_free(b);\r
- set_free(c);\r
- return( a );\r
- }\r
-\r
- 1987 by Hank Dietz\r
- \r
- Modified by:\r
- Terence Parr\r
- Purdue University\r
- October 1989\r
-\r
- Made it smell less bad to C++ 7/31/93 -- TJP\r
-*/\r
-\r
-#include <stdio.h>\r
-#include "pcctscfg.h"\r
-#ifdef __STDC__\r
-#include <stdlib.h>\r
-#else\r
-#include <malloc.h>\r
-#endif\r
-#include <string.h>\r
-\r
-#include "set.h"\r
-\r
-#define MIN(i,j) ( (i) > (j) ? (j) : (i))\r
-#define MAX(i,j) ( (i) < (j) ? (j) : (i))\r
-\r
-/* elems can be a maximum of 32 bits */\r
-static unsigned bitmask[] = {\r
- 0x00000001, 0x00000002, 0x00000004, 0x00000008,\r
- 0x00000010, 0x00000020, 0x00000040, 0x00000080,\r
- 0x00000100, 0x00000200, 0x00000400, 0x00000800,\r
- 0x00001000, 0x00002000, 0x00004000, 0x00008000,\r
-#if !defined(PC) || defined(PC32)\r
- 0x00010000, 0x00020000, 0x00040000, 0x00080000,\r
- 0x00100000, 0x00200000, 0x00400000, 0x00800000,\r
- 0x01000000, 0x02000000, 0x04000000, 0x08000000,\r
- 0x10000000, 0x20000000, 0x40000000, 0x80000000\r
-#endif\r
-};\r
-\r
-set empty = set_init;\r
-static unsigned min=1;\r
-\r
-#define StrSize 200\r
-\r
-#ifdef MEMCHK\r
-#define CHK(a) \\r
- if ( a.setword != NULL ) \\r
- if ( !valid(a.setword) ) \\r
- {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}\r
-#else\r
-#define CHK(a)\r
-#endif\r
-\r
-/*\r
- * Set the minimum size (in words) of a set to reduce realloc calls\r
- */\r
-void\r
-#ifdef __USE_PROTOS\r
-set_size( unsigned n )\r
-#else\r
-set_size( n )\r
-unsigned n;\r
-#endif\r
-{\r
- min = n;\r
-}\r
-\r
-unsigned int\r
-#ifdef __USE_PROTOS\r
-set_deg( set a )\r
-#else\r
-set_deg( a )\r
-set a;\r
-#endif\r
-{\r
- /* Fast compute degree of a set... the number\r
- of elements present in the set. Assumes\r
- that all word bits are used in the set\r
- and that SETSIZE(a) is a multiple of WORDSIZE.\r
- */\r
- register unsigned *p = &(a.setword[0]);\r
- register unsigned *endp = NULL; /* MR27 Avoid false memory check report */\r
- register unsigned degree = 0;\r
-\r
- CHK(a);\r
- if ( a.n == 0 ) return(0);\r
- endp = &(a.setword[a.n]);\r
- while ( p < endp )\r
- {\r
- register unsigned t = *p;\r
- register unsigned *b = &(bitmask[0]);\r
- do {\r
- if (t & *b) ++degree;\r
- } while (++b < &(bitmask[WORDSIZE]));\r
- p++;\r
- }\r
-\r
- return(degree);\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_or( set b, set c )\r
-#else\r
-set_or( b, c )\r
-set b;\r
-set c;\r
-#endif\r
-{\r
- /* Fast set union operation */\r
- /* resultant set size is max(b, c); */\r
- set *big;\r
- set t;\r
- unsigned int m,n;\r
- register unsigned *r, *p, *q, *endp;\r
-\r
- CHK(b); CHK(c);\r
- t = empty;\r
- if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;}\r
- set_ext(&t, m);\r
- r = t.setword;\r
-\r
- /* Or b,c until max of smaller set */\r
- q = c.setword;\r
- p = b.setword;\r
- endp = &(b.setword[n]);\r
- while ( p < endp ) *r++ = *p++ | *q++; \r
-\r
- /* Copy rest of bigger set into result */\r
- p = &(big->setword[n]);\r
- endp = &(big->setword[m]);\r
- while ( p < endp ) *r++ = *p++;\r
-\r
- return(t);\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_and( set b, set c )\r
-#else\r
-set_and( b, c )\r
-set b;\r
-set c;\r
-#endif\r
-{\r
- /* Fast set intersection operation */\r
- /* resultant set size is min(b, c); */\r
- set t;\r
- unsigned int n;\r
- register unsigned *r, *p, *q, *endp;\r
-\r
- CHK(b); CHK(c);\r
- t = empty;\r
- n = (b.n > c.n) ? c.n : b.n;\r
- if ( n == 0 ) return t; /* TJP 4-27-92 fixed for empty set */\r
- set_ext(&t, n);\r
- r = t.setword;\r
-\r
- /* & b,c until max of smaller set */\r
- q = c.setword;\r
- p = b.setword;\r
- endp = &(b.setword[n]);\r
- while ( p < endp ) *r++ = *p++ & *q++; \r
-\r
- return(t);\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_dif( set b, set c )\r
-#else\r
-set_dif( b, c )\r
-set b;\r
-set c;\r
-#endif\r
-{\r
- /* Fast set difference operation b - c */\r
- /* resultant set size is size(b) */\r
- set t;\r
- unsigned int n;\r
- register unsigned *r, *p, *q, *endp;\r
-\r
- CHK(b); CHK(c);\r
- t = empty;\r
- n = (b.n <= c.n) ? b.n : c.n ;\r
- if ( b.n == 0 ) return t; /* TJP 4-27-92 fixed for empty set */\r
- /* WEC 12-1-92 fixed for c.n = 0 */\r
- set_ext(&t, b.n);\r
- r = t.setword;\r
-\r
- /* Dif b,c until smaller set size */\r
- q = c.setword;\r
- p = b.setword;\r
- endp = &(b.setword[n]);\r
- while ( p < endp ) *r++ = *p++ & (~ *q++); \r
-\r
- /* Copy rest of b into result if size(b) > c */\r
- if ( b.n > n )\r
- {\r
- p = &(b.setword[n]);\r
- endp = &(b.setword[b.n]);\r
- while ( p < endp ) *r++ = *p++;\r
- }\r
-\r
- return(t);\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_of( unsigned b )\r
-#else\r
-set_of( b )\r
-unsigned b;\r
-#endif\r
-{\r
- /* Fast singleton set constructor operation */\r
- static set a;\r
-\r
- if ( b == nil ) return( empty );\r
- set_new(a, b);\r
- a.setword[DIVWORD(b)] = bitmask[MODWORD(b)];\r
-\r
- return(a);\r
-}\r
-\r
-/*\r
- * Extend (or shrink) the set passed in to have n words.\r
- *\r
- * if n is smaller than the minimum, boost n to have the minimum.\r
- * if the new set size is the same as the old one, do nothing.\r
- *\r
- * TJP 4-27-92 Fixed so won't try to alloc 0 bytes\r
- */\r
-void\r
-#ifdef __USE_PROTOS\r
-set_ext( set *a, unsigned int n )\r
-#else\r
-set_ext( a, n )\r
-set *a;\r
-unsigned int n;\r
-#endif\r
-{\r
- register unsigned *p;\r
- register unsigned *endp;\r
- unsigned int size;\r
- \r
- CHK((*a));\r
- if ( a->n == 0 )\r
- {\r
- if ( n == 0 ) return;\r
- if (a->setword != NULL) {\r
- free (a->setword); /* MR20 */\r
- }\r
- a->setword = (unsigned *) calloc(n, BytesPerWord);\r
- if ( a->setword == NULL )\r
- {\r
- fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);\r
- exit(-1);\r
- }\r
- a->n = n;\r
- return;\r
- }\r
- if ( n < min ) n = min;\r
- if ( a->n == n || n == 0 ) return;\r
- size = a->n;\r
- a->n = n;\r
- a->setword = (unsigned *) realloc( (char *)a->setword, (n*BytesPerWord) );\r
- if ( a->setword == NULL )\r
- {\r
- fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);\r
- exit(-1);\r
- }\r
-\r
- p = &(a->setword[size]); /* clear from old size to new size */\r
- endp = &(a->setword[a->n]);\r
- do {\r
- *p++ = 0;\r
- } while ( p < endp );\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_not( set a )\r
-#else\r
-set_not( a )\r
-set a;\r
-#endif\r
-{\r
- /* Fast not of set a (assumes all bits used) */\r
- /* size of resultant set is size(a) */\r
- /* ~empty = empty cause we don't know how bit to make set */\r
- set t;\r
- register unsigned *r;\r
- register unsigned *p = a.setword;\r
- register unsigned *endp = &(a.setword[a.n]);\r
-\r
- CHK(a);\r
- t = empty;\r
- if ( a.n == 0 ) return( empty );\r
- set_ext(&t, a.n);\r
- r = t.setword;\r
- \r
- do {\r
- *r++ = (~ *p++);\r
- } while ( p < endp );\r
-\r
- return(t);\r
-}\r
-\r
-int\r
-#ifdef __USE_PROTOS\r
-set_equ( set a, set b )\r
-#else\r
-set_equ( a, b )\r
-set a;\r
-set b;\r
-#endif\r
-{\r
-/* 8-Nov-97 Make it work with sets of different sizes */\r
-/* Easy to understand, too. Probably faster. */\r
-/* Check for a equal to b */\r
-\r
- unsigned int count; /* MR11 */\r
- unsigned int i; /* MR11 */\r
-\r
- CHK(a); CHK(b);\r
-\r
- count=MIN(a.n,b.n);\r
- if (count == 0) return 1;\r
- for (i=0; i < count; i++) {\r
- if (a.setword[i] != b.setword[i]) return 0;\r
- };\r
- if (a.n < b.n) {\r
- for (i=count; i < b.n; i++) {\r
- if (b.setword[i] != 0) return 0;\r
- }\r
- return 1;\r
- } else if (a.n > b.n) {\r
- for (i=count; i < a.n; i++) {\r
- if (a.setword[i] != 0) return 0;\r
- }\r
- return 1;\r
- } else {\r
- return 1;\r
- };\r
-}\r
-\r
-int\r
-#ifdef __USE_PROTOS\r
-set_sub( set a, set b )\r
-#else\r
-set_sub( a, b )\r
-set a;\r
-set b;\r
-#endif\r
-{\r
-\r
-/* 8-Nov-97 Make it work with sets of different sizes */\r
-/* Easy to understand, too. Probably faster. */\r
-/* Check for a is a PROPER subset of b */\r
-\r
- unsigned int count;\r
- unsigned int i;\r
-\r
- CHK(a); CHK(b);\r
-\r
- if (a.n == 0) return 1;\r
- count=MIN(a.n,b.n);\r
- for (i=0; i < count; i++) {\r
- if (a.setword[i] & ~b.setword[i]) return 0;\r
- };\r
- if (a.n <= b.n) {\r
- return 1;\r
- } else {\r
- for (i=count; i<a.n ; i++) {\r
- if (a.setword[i]) return 0;\r
- };\r
- };\r
- return 1;\r
-}\r
-\r
-unsigned\r
-#ifdef __USE_PROTOS\r
-set_int( set b )\r
-#else\r
-set_int( b )\r
-set b;\r
-#endif\r
-{\r
- /* Fast pick any element of the set b */\r
- register unsigned *p = b.setword;\r
- register unsigned *endp = &(b.setword[b.n]);\r
-\r
- CHK(b);\r
- if ( b.n == 0 ) return( nil );\r
-\r
- do {\r
- if (*p) {\r
- /* Found a non-empty word of the set */\r
- register unsigned i = ((p - b.setword) << LogWordSize);\r
- register unsigned t = *p;\r
- p = &(bitmask[0]);\r
- while (!(*p & t)) {\r
- ++i; ++p;\r
- }\r
- return(i);\r
- }\r
- } while (++p < endp);\r
-\r
- /* Empty -- only element it contains is nil */\r
- return(nil);\r
-}\r
-\r
-int\r
-#ifdef __USE_PROTOS\r
-set_el( unsigned b, set a )\r
-#else\r
-set_el( b, a )\r
-unsigned b;\r
-set a;\r
-#endif\r
-{\r
- CHK(a);\r
- /* nil is an element of every set */\r
- if (b == nil) return(1);\r
- if ( a.n == 0 || NumWords(b) > a.n ) return(0);\r
- \r
- /* Otherwise, we have to check */\r
- return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );\r
-}\r
-\r
-int\r
-#ifdef __USE_PROTOS\r
-set_nil( set a )\r
-#else\r
-set_nil( a )\r
-set a;\r
-#endif\r
-{\r
- /* Fast check for nil set */\r
- register unsigned *p = a.setword;\r
- register unsigned *endp;\r
-\r
- CHK(a);\r
- if ( a.n == 0 ) return(1);\r
- endp = &(a.setword[a.n]);\r
- \r
- /* The set is not empty if any word used to store\r
- the set is non-zero. This means one must be a\r
- bit careful about doing things like negation.\r
- */\r
- do {\r
- if (*p) return(0);\r
- } while (++p < endp);\r
- \r
- return(1);\r
-}\r
-\r
-char *\r
-#ifdef __USE_PROTOS\r
-set_str( set a )\r
-#else\r
-set_str( a )\r
-set a;\r
-#endif\r
-{\r
- /* Fast convert set a into ASCII char string...\r
- assumes that all word bits are used in the set\r
- and that SETSIZE is a multiple of WORDSIZE.\r
- Trailing 0 bits are removed from the string.\r
- if no bits are on or set is empty, "" is returned.\r
- */\r
- register unsigned *p = a.setword;\r
- register unsigned *endp = &(a.setword[a.n]);\r
- static char str_tmp[StrSize+1];\r
- register char *q = &(str_tmp[0]);\r
-\r
- CHK(a);\r
- if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}\r
- do {\r
- register unsigned t = *p;\r
- register unsigned *b = &(bitmask[0]);\r
- do {\r
- *(q++) = (char) ((t & *b) ? '1' : '0');\r
- } while (++b < &(bitmask[WORDSIZE]));\r
- } while (++p < endp);\r
-\r
- /* Trim trailing 0s & NULL terminate the string */\r
- while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;\r
- *q = 0;\r
-\r
- return(&(str_tmp[0]));\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_val( register char *s )\r
-#else\r
-set_val( s )\r
-register char *s;\r
-#endif\r
-{\r
- /* Fast convert set ASCII char string into a set.\r
- If the string ends early, the remaining set bits\r
- are all made zero.\r
- The resulting set size is just big enough to hold all elements.\r
- */\r
- static set a;\r
- register unsigned *p, *endp;\r
-\r
- set_new(a, strlen(s));\r
- p = a.setword;\r
- endp = &(a.setword[a.n]);\r
- do {\r
- register unsigned *b = &(bitmask[0]);\r
- /* Start with a word with no bits on */\r
- *p = 0;\r
- do {\r
- if (*s) {\r
- if (*s == '1') {\r
- /* Turn-on this bit */\r
- *p |= *b;\r
- }\r
- ++s;\r
- }\r
- } while (++b < &(bitmask[WORDSIZE]));\r
- } while (++p < endp);\r
-\r
- return(a);\r
-}\r
-\r
-/*\r
- * Or element e into set a. a can be empty.\r
- */\r
-void\r
-#ifdef __USE_PROTOS\r
-set_orel( unsigned e, set *a )\r
-#else\r
-set_orel( e, a )\r
-unsigned e;\r
-set *a;\r
-#endif\r
-{\r
- CHK((*a));\r
- if ( e == nil ) return;\r
- if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));\r
- a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];\r
-}\r
-\r
-/*\r
- * Or set b into set a. a can be empty. does nothing if b empty.\r
- */\r
-void\r
-#ifdef __USE_PROTOS\r
-set_orin( set *a, set b )\r
-#else\r
-set_orin( a, b )\r
-set *a;\r
-set b;\r
-#endif\r
-{\r
- /* Fast set union operation */\r
- /* size(a) is max(a, b); */\r
- unsigned int m;\r
- register unsigned *p,\r
- *q = b.setword,\r
- *endq; /* MR20 */\r
-\r
- CHK((*a)); CHK(b);\r
- if ( b.n == 0 ) return;\r
- endq = &(b.setword[b.n]); /* MR20 */\r
- m = (a->n > b.n) ? a->n : b.n;\r
- set_ext(a, m);\r
- p = a->setword;\r
- do {\r
- *p++ |= *q++;\r
- } while ( q < endq );\r
-}\r
-\r
-/*\r
- * And set b into set a. a can be empty. does nothing if b empty.\r
- */\r
-void\r
-#ifdef __USE_PROTOS\r
-set_andin( set *a, set b )\r
-#else\r
-set_andin( a, b )\r
-set *a;\r
-set b;\r
-#endif\r
-{\r
- /* Fast set intersection operation */\r
- /* size(a) is max(a, b); */\r
- unsigned int m;\r
- register unsigned *p,\r
- *q = b.setword,\r
- *endq = &(b.setword[b.n]);\r
-\r
- CHK((*a)); CHK(b);\r
- if ( b.n == 0 ) return;\r
- m = (a->n > b.n) ? a->n : b.n;\r
- set_ext(a, m);\r
- p = a->setword;\r
- do {\r
- *p++ &= *q++;\r
- } while ( q < endq );\r
-}\r
-\r
-void\r
-#ifdef __USE_PROTOS\r
-set_rm( unsigned e, set a )\r
-#else\r
-set_rm( e, a )\r
-unsigned e;\r
-set a;\r
-#endif\r
-{\r
- /* Does not effect size of set */\r
- CHK(a);\r
- if ( (e == nil) || (NumWords(e) > a.n) ) return;\r
- a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);\r
-}\r
-\r
-void\r
-#ifdef __USE_PROTOS\r
-set_clr( set a )\r
-#else\r
-set_clr( a )\r
-set a;\r
-#endif\r
-{\r
- /* Does not effect size of set */\r
- register unsigned *p = a.setword;\r
- register unsigned *endp;\r
- \r
- CHK(a);\r
- if ( a.n == 0 ) return;\r
- endp = &(a.setword[a.n]);\r
- do {\r
- *p++ = 0;\r
- } while ( p < endp );\r
-}\r
-\r
-set\r
-#ifdef __USE_PROTOS\r
-set_dup( set a )\r
-#else\r
-set_dup( a )\r
-set a;\r
-#endif\r
-{\r
- set b;\r
- register unsigned *p,\r
- *q = a.setword,\r
- *endq; /* MR20 */\r
- \r
- CHK(a);\r
- b = empty;\r
- if ( a.n == 0 ) return( empty );\r
- endq = &(a.setword[a.n]); /* MR20 */\r
- set_ext(&b, a.n);\r
- p = b.setword;\r
- do {\r
- *p++ = *q++;\r
- } while ( q < endq );\r
- \r
- return(b);\r
-}\r
-\r
-/*\r
- * Return a nil terminated list of unsigned ints that represents all\r
- * "on" bits in the bit set.\r
- *\r
- * e.g. {011011} --> {1, 2, 4, 5, nil}\r
- *\r
- * _set_pdq and set_pdq are useful when an operation is required on each element\r
- * of a set. Normally, the sequence is:\r
- *\r
- * while ( set_deg(a) > 0 ) {\r
- * e = set_int(a);\r
- * set_rm(e, a);\r
- * ...process e...\r
- * }\r
- * Now,\r
- *\r
- * t = e = set_pdq(a);\r
- * while ( *e != nil ) {\r
- * ...process *e...\r
- * e++;\r
- * }\r
- * free( t );\r
- *\r
- * We have saved many set calls and have not destroyed set a.\r
- */\r
-void\r
-#ifdef __USE_PROTOS\r
-_set_pdq( set a, register unsigned *q )\r
-#else\r
-_set_pdq( a, q )\r
-set a;\r
-register unsigned *q;\r
-#endif\r
-{\r
- register unsigned *p = a.setword,\r
- *endp = &(a.setword[a.n]);\r
- register unsigned e=0;\r
-\r
- CHK(a);\r
- /* are there any space (possibility of elements)? */\r
- if ( a.n == 0 ) return;\r
- do {\r
- register unsigned t = *p;\r
- register unsigned *b = &(bitmask[0]);\r
- do {\r
- if ( t & *b ) *q++ = e;\r
- ++e;\r
- } while (++b < &(bitmask[WORDSIZE]));\r
- } while (++p < endp);\r
- *q = nil;\r
-}\r
-\r
-/*\r
- * Same as _set_pdq except allocate memory. set_pdq is the natural function\r
- * to use.\r
- */\r
-unsigned *\r
-#ifdef __USE_PROTOS\r
-set_pdq( set a )\r
-#else\r
-set_pdq( a )\r
-set a;\r
-#endif\r
-{\r
- unsigned *q;\r
- int max_deg;\r
- \r
- CHK(a);\r
- max_deg = WORDSIZE*a.n;\r
- /* assume a.n!=0 & no elements is rare, but still ok */\r
- if ( a.n == 0 ) return(NULL);\r
- q = (unsigned *) malloc((max_deg+1)*BytesPerWord);\r
- if ( q == NULL ) return( NULL );\r
- _set_pdq(a, q);\r
- return( q );\r
-}\r
-\r
-/* a function that produces a hash number for the set\r
- */\r
-unsigned int\r
-#ifdef __USE_PROTOS\r
-set_hash( set a, register unsigned int mod )\r
-#else\r
-set_hash( a, mod )\r
-set a;\r
-register unsigned int mod;\r
-#endif\r
-{\r
- /* Fast hash of set a (assumes all bits used) */\r
- register unsigned *p = &(a.setword[0]);\r
- register unsigned *endp = &(a.setword[a.n]);\r
- register unsigned i = 0;\r
-\r
- CHK(a);\r
- while (p<endp){\r
- i += (*p);\r
- ++p;\r
- }\r
-\r
- return(i % mod);\r
-}\r
projects / mirror_edk2.git / blobdiff