set.c

一个c语言写做的编译器的源码

/*@A (C) 1992 Allen I. Holub                                                */

#include  <stdio.h>
#include  <ctype.h>
#include  <signal.h>
#include  <stdlib.h>
#include  <string.h>
#include  <tools/debug.h>
#include  <tools/set.h>

PUBLIC SET	*newset()
{
    /* Create a new set and return a pointer to it. Print an error message
     * and raise SIGABRT if there's insufficient memory. NULL is returned
     * if raise() returns.
     */

    SET	*p;

    if( !(p = (SET *) malloc( sizeof(SET) )) )
    {
	fprintf(stderr,"Can't get memory to create set\n");
	raise( SIGABRT );
	return NULL;		/* Usually won't get here */
    }
    memset( p, 0, sizeof(SET) );
    p->map    = p->defmap;
    p->nwords = _DEFWORDS;
    p->nbits  = _DEFBITS;
    return p;
}

/*----------------------------------------------------------------------*/

PUBLIC void	delset( set )
SET	*set;
{
    /* Delete a set created with a previous newset() call. */

    if( set->map != set->defmap )
	free( set->map );
    free( set );
}

/*----------------------------------------------------------------------*/

PUBLIC SET	*dupset( set )
SET	*set;
{
    /* Create a new set that has the same members as the input set */

    SET	  *new;

    if( !(new = (SET *) malloc( sizeof(SET) )) )
    {
	fprintf(stderr,"Can't get memory to duplicate set\n");
	exit(1);
    }

    memset( new, 0, sizeof(SET) );
    new->compl  = set->compl;
    new->nwords = set->nwords;
    new->nbits  = set->nbits;

    if( set->map == set->defmap )		   /* default bit map in use */
    {
	new->map = new->defmap;
	memcpy( new->defmap, set->defmap, _DEFWORDS * sizeof(_SETTYPE) );
    }
    else					/* bit map has been enlarged */
    {
	new->map = (_SETTYPE *) malloc( set->nwords * sizeof(_SETTYPE) );
	if( !new->map )
	{
	    fprintf(stderr,"Can't get memory to duplicate set bit map\n");
	    exit(1);
	}
	memcpy( new->map, set->map, set->nwords * sizeof(_SETTYPE) );
    }
    return new;
}

PUBLIC int	_addset( set, bit )
SET	*set;
int	bit;
{
    /* Addset is called by the ADD() macro when the set isn't big enough. It
     * expands the set to the necessary size and sets the indicated bit.
     */

    void enlarge P(( int, SET* ));		/* immediately following */

    enlarge( _ROUND(bit), set );
    return _GBIT( set, bit, |= );
}
/* ------------------------------------------------------------------- */
PRIVATE	void	enlarge( need, set )
int	need;
SET	*set;
{
    /* Enlarge the set to "need" words, filling in the extra words with zeros.
     * Print an error message and exit if there's not enough memory.
     * Since this routine calls malloc, it's rather slow and should be
     * avoided if possible.
     */

    _SETTYPE  *new;

    if( !set  ||  need <= set->nwords )
	return;

    D( printf("enlarging %d word map to %d words\n", set->nwords, need); )

    if( !(new = (_SETTYPE *) malloc( need * sizeof(_SETTYPE)))  )
    {
	fprintf(stderr, "Can't get memory to expand set\n");
	exit( 1 );
    }
    memcpy( new, set->map,        set->nwords * sizeof(_SETTYPE)          );
    memset( new + set->nwords, 0, (need - set->nwords) * sizeof(_SETTYPE) );

    if( set->map != set->defmap )
	free( set->map );

    set->map    = new  ;
    set->nwords = (unsigned char) need ;
    set->nbits  = need * _BITS_IN_WORD ;
}

PUBLIC int	num_ele( set )
SET	*set;
{
    /* Return the number of elements (nonzero bits) in the set. NULL sets are
     * considered empty. The table-lookup approach used here was suggested to
     * me by Doug Merrit. Nbits[] is indexed by any number in the range 0-255,
     * and it evaluates to the number of bits in the number.
     */
    static unsigned char nbits[] =
    {
	/*   0-15  */	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	/*  16-31  */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	/*  32-47  */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	/*  48-63  */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	/*  64-79  */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	/*  80-95  */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	/*  96-111 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	/* 112-127 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	/* 128-143 */	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	/* 144-159 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	/* 160-175 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	/* 176-191 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	/* 192-207 */	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	/* 208-223 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	/* 224-239 */	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	/* 240-255 */	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
    int			i;
    unsigned int 	count = 0;
    unsigned char	*p;

    if( !set )
	return 0;

    p = (unsigned char *)set->map ;

    for( i = _BYTES_IN_ARRAY(set->nwords) ; --i >= 0 ; )
	count += nbits[ *p++ ] ;

    return count;
}

/* ------------------------------------------------------------------- */

PUBLIC int	_set_test( set1, set2 )
SET	*set1, *set2;
{
    /* Compares two sets. Returns as follows:
     *
     * _SET_EQUIV	Sets are equivalent
     * _SET_INTER	Sets intersect but aren't equivalent
     * _SET_DISJ	Sets are disjoint
     *
     * The smaller set is made larger if the two sets are different sizes.
     */

    int	  	i, rval = _SET_EQUIV ;
    _SETTYPE   *p1, *p2;

    i = max( set1->nwords, set2->nwords);

    enlarge( i, set1 );		/* Make the sets the same size	*/
    enlarge( i, set2 );

    p1 = set1->map;
    p2 = set2->map;

    for(; --i >= 0 ; p1++, p2++ )
    {
	if( *p1 != *p2 )
	{
	    /* You get here if the sets aren't equivalent. You can return
	     * immediately if the sets intersect but have to keep going in the
	     * case of disjoint sets (because the sets might actually intersect
	     * at some byte, as yet unseen).
	     */

	    if( *p1 & *p2 )
		return _SET_INTER ;
	    else
		rval = _SET_DISJ ;
	}
    }

    return rval;			/* They're equivalent	*/
}

/* ------------------------------------------------------------------- */

PUBLIC int setcmp( set1, set2 )
SET *set1, *set2;
{
    /* Yet another comparison function. This one works like strcmp(),
     * returning 0 if the sets are equivalent, <0 if set1<set2 and >0 if
     * set1>set2. A NULL set is less than any other set, two NULL sets
     * are equivalent.
     */

    int	  i, j;
    _SETTYPE   *p1, *p2;

    D( if( !set1 ) fprintf(stderr, "setcmp(): set1 is NULL\n" ); )
    D( if( !set2 ) fprintf(stderr, "setcmp(): set2 is NULL\n" ); )

    if(  set1 ==  set2 ){ return  0; }
    if(  set1 && !set2 ){ return  1; }
    if( !set1 &&  set2 ){ return -1; }

    i = j = min( set1->nwords, set2->nwords );

    for( p1 = set1->map, p2 = set2->map ; --j >= 0 ;  p1++, p2++  )
	if( *p1 != *p2 )
	    return *p1 - *p2;

    /* You get here only if all words that exist in both sets are the same.
     * Check the tail end of the larger array for all zeros.
     */

    if( (j = set1->nwords - i) > 0 )		/* Set 1 is the larger */
    {
	while( --j >= 0 )
	    if( *p1++ )
		return 1;
    }
    else if( (j = set2->nwords - i) > 0)	/* Set 2 is the larger */
    {
	while( --j >= 0 )
	    if( *p2++ )
		return -1;
    }

    return 0;					/* They're equivalent	*/
}

/* ------------------------------------------------------------------- */

PUBLIC unsigned sethash( set1 )
SET *set1;
{
    /* hash the set by summing together the words in the bit map */

    _SETTYPE    *p;
    unsigned	total;
    int		j;

    total = 0;
    j     = set1->nwords ;
    p     = set1->map    ;

    while( --j >= 0 )
	total += *p++ ;

    return total;
}

/* ------------------------------------------------------------------- */

PUBLIC int	subset( set, possible_subset )
SET	*set, *possible_subset;
{
    /* Return 1 if "possible_subset" is a subset of "set". One is returned if
     * it's a subset, zero otherwise. Empty sets are subsets of everything.
     * The routine silently malfunctions if given a NULL set, however. If the
     * "possible_subset" is larger than the "set", then the extra bytes must
     * be all zeros.
     */

    _SETTYPE  *subsetp, *setp;
    int	  common;		/* This many bytes in potential subset  */
    int	  tail;			/* This many implied 0 bytes in b	*/

    if( possible_subset->nwords > set->nwords )
    {
	common = set->nwords ;
	tail   = possible_subset->nwords - common ;
    }
    else
    {
	common = possible_subset->nwords;
	tail   = 0;
    }

    subsetp = possible_subset->map;
    setp    = set->map;

    for(; --common >= 0; subsetp++, setp++ )
	if( (*subsetp & *setp) != *subsetp )
	    return 0;

    while( --tail >= 0 )
	if( *subsetp++ )
	    return 0;

    return 1;
}

PUBLIC void	_set_op( op, dest, src )
int	op;
SET	*src, *dest;
{