set.c

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

    /* Performs binary operations depending on op:
     *
     * _UNION:        dest = union of src and dest
     * _INTERSECT:    dest = intersection of src and dest
     * _DIFFERENCE:   dest = symmetric difference of src and dest
     * _ASSIGN:       dest = src;
     *
     * The sizes of the destination set is adjusted so that it's the same size
     * as the source set.
     */

    _SETTYPE	*d;	/* Pointer to destination map	*/
    _SETTYPE	*s;	/* Pointer to map in set1	*/
    int		ssize;	/* # of words in src set	*/
    int		tail;	/* dest set is this much bigger */

    ssize = src->nwords ;

    if( (unsigned)dest->nwords < ssize ) /* Make sure dest set is at least */
	enlarge( ssize, dest );		 /* as big as the src set.	   */

    tail  = dest->nwords - ssize ;
    d     = dest->map ;
    s     = src ->map ;

    switch( op )
    {
    case _UNION:      while( --ssize >= 0 )
			    *d++ |= *s++ ;
		      break;
    case _INTERSECT:  while( --ssize >= 0 )
			    *d++ &= *s++ ;
		      while( --tail >= 0 )
			    *d++ = 0;
		      break;
    case _DIFFERENCE: while( --ssize >= 0 )
			    *d++ ^= *s++ ;
		      break;
    case _ASSIGN:     while( --ssize >= 0 )
			    *d++  = *s++ ;
		      while( --tail >= 0 )
			    *d++ = 0;
		      break;
    }
}

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

PUBLIC void	invert( set )
SET	*set;
{
    /* Physically invert the bits in the set. Compare with the COMPLEMENT()
     * macro, which just modifies the complement bit.
     */

    _SETTYPE *p, *end ;

    for( p = set->map, end = p + set->nwords ; p < end ; p++ )
	*p = ~*p;
}

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

PUBLIC void	truncate( set )
SET	*set;
{
    /* Clears the set but also set's it back to the original, default size.
     * Compare this routine to the CLEAR() macro which clears all the bits in
     * the map but doesn't modify the size.
     */

    if( set->map != set->defmap )
    {
	free( set->map );
	set->map = set->defmap;
    }
    set->nwords = _DEFWORDS;
    set->nbits  = _DEFBITS;
    memset( set->defmap, 0, sizeof(set->defmap) );
}

PUBLIC int	next_member( set )
SET	*set;
{
    /* set == NULL			Reset
     * set changed from last call:	Reset and return first element
     * otherwise			return next element or -1 if none.
     */

    static SET	*oset 	       = NULL;	/* "set" arg in last call 	    */
    static int	current_member = 0;	/* last-accessed member of cur. set */
    _SETTYPE    *map;

    if( !set )
	return( (int)( oset = NULL ) );

    if( oset != set )
    {
	oset           = set;
	current_member = 0 ;

	for(map = set->map; *map == 0  &&  current_member < set->nbits; ++map)
	    current_member += _BITS_IN_WORD;
    }

    /* The increment must be put into the test because, if the TEST() invocation
     * evaluates true, then an increment on the right of a for() statement
     * would never be executed.
     */

    while( current_member++ < set->nbits )
	if( TEST(set, current_member-1) )
	    return( current_member-1 );
    return( -1 );
}

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

PUBLIC void	pset( set, output_routine, param )
SET	*set;
pset_t	output_routine;
void	*param;
{
    /* Print the contents of the set bit map in human-readable form. The
     * output routine is called for each element of the set with the following
     * arguments:
     *
     * (*out)( param, "null",    -1);	Null set ("set" arg == NULL)
     * (*out)( param, "empty",   -2);	Empty set (no elements)
     * (*out)( param, "%d ",      N);	N is an element of the set
     */

    int	i, did_something = 0;

    if( !set )
	(*output_routine)( param, "null", -1 );
    else
    {
	next_member( NULL );
	while( (i = next_member(set))  >= 0 )
	{
	    did_something++;
	    ( *output_routine )( param, "%d ", i  );
	}
	next_member( NULL );

	if( !did_something )
	    ( *output_routine )(param, "empty",  -2 );
    }
}
#ifdef MAIN

scmp(a,b) SET **a, **b; { return setcmp(*a,*b); }

main()
{
    int i;
    SET *s1 = newset();
    SET *s2 = newset();
    SET *s3 = newset();
    SET *s4 = newset();
    SET *a[ 40 ];

    printf("adding 1024 and 2047 to s1: ");
    ADD(  s2,1024);
    ADD(  s2,2047);
    pset( s2, (pset_t) fprintf, stdout );
    printf("removing 1024 and 2047: ");
    REMOVE(  s2, 1024);
    REMOVE(  s2, 2047);
    pset( s2, (pset_t) fprintf, stdout );

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

    for( i = 0; i <= 1024 ; ++i )
    {
	ADD( s1, i );
	if( !TEST(s1,i) || !MEMBER(s1,i) )
	    printf("initial: <%d> not in set and it should be\n", i);
    }
    for( i = 0; i <= 1024 ; ++i )
    {
	/* Make a second pass to see if a previous ADD messed
	 * up an already-added element.
	 */

	if( !TEST(s1,i) || !MEMBER(s1,i) )
	    printf("verify:  <%d> not in set and it should be\n", i);
    }
    for( i = 0; i <= 1024 ; ++i )
    {
	REMOVE( s1, i );
	if( TEST(s1,i) || MEMBER(s1,i) )
	    printf("initial: <%d> is in set and it shouldn't be\n", i);
    }
    for( i = 0; i <= 1024 ; ++i )
    {
	if( TEST(s1,i) || MEMBER(s1,i) )
	    printf("verify:  <%d> is in set and it shouldn't be\n", i);
    }

    printf("Add test finished: malloc set\n" );

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

    truncate(s1);

    printf(  IS_EQUIVALENT(s1,s2) ? "yeah!\n" : "boo\n" );

    ADD( s1, 1 );
    ADD( s2, 1 );
    ADD( s3, 1 );
    ADD( s1, 517 );
    ADD( s2, 517 );

    printf(  IS_EQUIVALENT(s1,s2) ? "yeah!\n" : "boo\n" );

    REMOVE( s2, 517 );

    printf( !IS_EQUIVALENT(s1,s2) ? "yeah!\n" : "boo\n" );
    printf( !IS_EQUIVALENT(s2,s1) ? "yeah!\n" : "boo\n" );
    printf( !IS_EQUIVALENT(s1,s3) ? "yeah!\n" : "boo\n" );
    printf(  IS_EQUIVALENT(s3,s2) ? "yeah!\n" : "boo\n" );
    printf(  IS_EQUIVALENT(s2,s3) ? "yeah!\n" : "boo\n" );

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

    ADD(s1, 3);
    ADD(s1, 6);
    ADD(s1, 9);
    ADD(s1, 12);
    ADD(s1, 15);
    ADD(s1, 16);
    ADD(s1, 19);
    ADD(s3, 18);

    printf(   "s1=" );  pset( s1, (pset_t) fprintf, stdout );
    printf( "\ns2=" );  pset( s2, (pset_t) fprintf, stdout );
    printf( "\ns3=" );  pset( s3, (pset_t) fprintf, stdout );
    printf( "\ns4=" );  pset( s4, (pset_t) fprintf, stdout );
    printf( "\n"    );
    printf("s1 has %d elements\n", num_ele( s1 ) );
    printf("s2 has %d elements\n", num_ele( s2 ) );
    printf("s3 has %d elements\n", num_ele( s3 ) );
    printf("s4 has %d elements\n", num_ele( s4 ) );

    s2 = dupset( s1 );
    printf( IS_EQUIVALENT(s2,s1)? "dupset succeeded\n" : "dupset failed\n");

    printf( "\ns1 %s empty\n", IS_EMPTY(s1) ? "IS" : "IS NOT" );
    printf( "s3 %s empty\n",   IS_EMPTY(s3) ? "IS" : "IS NOT" );
    printf( "s4 %s empty\n",   IS_EMPTY(s4) ? "IS" : "IS NOT" );

    printf("s1&s3 %s disjoint\n", IS_DISJOINT    (s1,s3) ? "ARE":"ARE NOT");
    printf("s1&s4 %s disjoint\n", IS_DISJOINT    (s1,s4) ? "ARE":"ARE NOT");

    printf("s1&s3 %s intersect\n",IS_INTERSECTING(s1,s3) ? "DO" : "DO NOT");
    printf("s1&s4 %s intersect\n",IS_INTERSECTING(s1,s4) ? "DO" : "DO NOT");

    printf("s1 %s a subset of s1\n", subset(s1,s1) ? "IS" : "IS NOT" );
    printf("s3 %s a subset of s3\n", subset(s3,s3) ? "IS" : "IS NOT" );
    printf("s4 %s a subset of s4\n", subset(s4,s4) ? "IS" : "IS NOT" );
    printf("s1 %s a subset of s3\n", subset(s3,s1) ? "IS" : "IS NOT" );
    printf("s1 %s a subset of s4\n", subset(s4,s1) ? "IS" : "IS NOT" );
    printf("s3 %s a subset of s1\n", subset(s1,s3) ? "IS" : "IS NOT" );
    printf("s3 %s a subset of s4\n", subset(s4,s3) ? "IS" : "IS NOT" );
    printf("s4 %s a subset of s1\n", subset(s1,s4) ? "IS" : "IS NOT" );
    printf("s4 %s a subset of s3\n", subset(s3,s4) ? "IS" : "IS NOT" );

    printf("\nAdding 18 to s1:\n");
    ADD(s1, 18);
    printf("s1 %s a subset of s1\n", subset(s1,s1) ? "IS" : "IS NOT" );
    printf("s3 %s a subset of s3\n", subset(s3,s3) ? "IS" : "IS NOT" );
    printf("s1 %s a subset of s3\n", subset(s3,s1) ? "IS" : "IS NOT" );
    printf("s3 %s a subset of s1\n", subset(s1,s3) ? "IS" : "IS NOT" );

    ASSIGN(s2,s3); puts("\ns3       =");
    pset(s2, (pset_t) fprintf, stdout );
    ASSIGN(s2,s3); UNION(s2,s1); puts("\ns1 UNI s3=");
    pset(s2, (pset_t) fprintf, stdout );
    ASSIGN(s2,s3); INTERSECT(s2,s1); puts("\ns1 INT s3=");
    pset(s2, (pset_t) fprintf, stdout );
    ASSIGN(s2,s3); DIFFERENCE(s2,s1); puts("\ns1 DIF s3=");
    pset(s2, (pset_t) fprintf, stdout );


    truncate( s2 );
    printf("s2 has%s been emptied\n", IS_EMPTY(s2) ? "" : " NOT" );

    invert( s2 ); printf("\ns2 inverted = "); pset(s2,(pset_t) fprintf,stdout);
    CLEAR ( s2 ); printf("\ns2 cleared  = "); pset(s2,(pset_t) fprintf,stdout);
    FILL  ( s2 ); printf("\ns2 filled   = "); pset(s2,(pset_t) fprintf,stdout);

    printf("\ns1="); pset( s1, (pset_t) fprintf, stdout );
    printf("\ns3="); pset( s3, (pset_t) fprintf, stdout );
    printf("\ns4="); pset( s4, (pset_t) fprintf, stdout );
    printf("\n");

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

    for( i = 40 ; --i >= 0; )
    {
	a[i] = newset();
	ADD( a[i], i % 20 );
    }

    ADD( a[0],  418 ); REMOVE( a[0],  418 );
    ADD( a[10], 418 ); REMOVE( a[10], 418 );

    printf("\nUnsorted:\n");
    for( i = 0; i < 40; i++ )
    {
	printf( "Set %d: ", i );
	pset(a[i], (pset_t) fprintf, stdout );
	printf( i & 1 ? "\n" : "\t" );
    }

    ssort( a, 40, sizeof(a[0]), scmp );

    printf("\nSorted:\n");
    for( i = 0; i < 40; i++ )
    {
	printf("Set %d: ", i );
	pset(a[i], (pset_t) fprintf, stdout );
	printf( i & 1 ? "\n" : "\t" );
    }
}
#endif