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