Restructuring for better separation of Tool packages.

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

/*      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 <stdio.h>
#include "pcctscfg.h"
#ifdef __STDC__
#include <stdlib.h>
#else
#include <malloc.h>
#endif
#include <string.h>

#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 ; i++) {
        if (a.setword[i]) return 0;
      };
    };
    return 1;
}

unsigned
#ifdef __USE_PROTOS
set_int( set b )
#else
set_int( b )
set b;
#endif
{
        /* Fast pick any element of the set b */
        register unsigned *p = b.setword;
        register unsigned *endp = &(b.setword[b.n]);

        CHK(b);
        if ( b.n == 0 ) return( nil );

        do {
                if (*p) {
                        /* Found a non-empty word of the set */
                        register unsigned i = ((p - b.setword) << LogWordSize);
                        register unsigned t = *p;
                        p = &(bitmask[0]);
                        while (!(*p & t)) {
                                ++i; ++p;
                        }
                        return(i);
                }
        } while (++p < endp);

        /* Empty -- only element it contains is nil */
        return(nil);
}

int
#ifdef __USE_PROTOS
set_el( unsigned b, set a )
#else
set_el( b, a )
unsigned b;
set a;
#endif
{
        CHK(a);
        /* nil is an element of every set */
        if (b == nil) return(1);
        if ( a.n == 0 || NumWords(b) > 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, 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<endp){
                i += (*p);
                ++p;
        }

        return(i % mod);
}