More renames for Tool Packages

[mirror_edk2.git] / Tools / CodeTools / Source / Pccts / support / set / set.c

/*	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