set.c

主要进行大规模的电路综合

/*
 * Revision Control Information
 *
 * $Source: /projects/mvsis/Repository/mvsis-1.3/src/sis/espresso/set.c,v $
 * $Author: wjiang $
 * $Revision: 1.3 $
 * $Date: 2003/04/21 22:25:03 $
 *
 */
/*
 *   set.c -- routines for maniuplating sets and set families
 */

/* LINTLIBRARY */

#include "espresso.h"
static pset_family set_family_garbage = NULL;

static int intcpy(d, s, n)
register unsigned int *d, *s;
register long n;
{
    register int i;
    for(i = 0; i < n; i++) {
	*d++ = *s++;
    }
}


/* bit_index -- find first bit (from LSB) in a word (MSB=bit n, LSB=bit 0) */
int bit_index(a)
register unsigned int a;
{
    register int i;
    if (a == 0)
	return -1;
    for(i = 0; (a & 1) == 0; a >>= 1, i++)
	;
    return i;
}


/* set_ord -- count number of elements in a set */
int set_ord(a)
register pset a;
{
    register int i, sum = 0;
    register unsigned int val;
    for(i = LOOP(a); i > 0; i--)
	if ((val = a[i]) != 0)
	    sum += count_ones(val);
    return sum;
}

/* set_dist -- distance between two sets (# elements in common) */
int set_dist(a, b)
register pset a, b;
{
    register int i, sum = 0;
    register unsigned int val;
    for(i = LOOP(a); i > 0; i--)
	if ((val = a[i] & b[i]) != 0)
	    sum += count_ones(val);
    return sum;
}

/* set_clear -- make "r" the empty set of "size" elements */
pset set_clear(r, size)
register pset r;
int size;
{
    register int i = LOOPINIT(size);
    *r = i; do r[i] = 0; while (--i > 0);
    return r;
}

/* set_fill -- make "r" the universal set of "size" elements */
pset set_fill(r, size)
register pset r;
register int size;
{
    register int i = LOOPINIT(size);
    *r = i;
    r[i] = ~ (unsigned) 0;
    r[i] >>= i * BPI - size;
    while (--i > 0)
	r[i] = ~ (unsigned) 0;
    return r;
}

/* set_copy -- copy set a into set r */
pset set_copy(r, a)
register pset r, a;
{
    register int i = LOOPCOPY(a);
    do r[i] = a[i]; while (--i >= 0);
    return r;
}

/* set_and -- compute intersection of sets "a" and "b" */
pset set_and(r, a, b)
register pset r, a, b;
{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] & b[i]; while (--i > 0);
    return r;
}

/* set_or -- compute union of sets "a" and "b" */
pset set_or(r, a, b)
register pset r, a, b;
{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] | b[i]; while (--i > 0);
    return r;
}

/* set_diff -- compute difference of sets "a" and "b" */
pset set_diff(r, a, b)
register pset r, a, b;
{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] & ~b[i]; while (--i > 0);
    return r;
}

/* set_xor -- compute exclusive-or of sets "a" and "b" */
pset set_xor(r, a, b)
register pset r, a, b;
{
    register int i = LOOP(a);
#ifdef IBM_WATC
    PUTLOOP(r,i); do r[i] = (a[i]&~b[i]) | (~a[i]&b[i]); while (--i > 0);
#else
    PUTLOOP(r,i); do r[i] = a[i] ^ b[i]; while (--i > 0);
#endif
    return r;
}

/* set_merge -- compute "a" & "mask" | "b" & ~ "mask" */
pset set_merge(r, a, b, mask)
register pset r, a, b, mask;
{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = (a[i]&mask[i]) | (b[i]&~mask[i]); while (--i > 0);
    return r;
}

/* set_andp -- compute intersection of sets "a" and "b" , TRUE if nonempty */
bool set_andp(r, a, b)
register pset r, a, b;
{
    register int i = LOOP(a);
    register unsigned int x = 0;
    PUTLOOP(r,i); do {r[i] = a[i] & b[i]; x |= r[i];} while (--i > 0);
    return x != 0;
}

/* set_orp -- compute union of sets "a" and "b" , TRUE if nonempty */
bool set_orp(r, a, b)
register pset r, a, b;
{
    register int i = LOOP(a);
    register unsigned int x = 0;
    PUTLOOP(r,i); do {r[i] = a[i] | b[i]; x |= r[i];} while (--i > 0);
    return x != 0;
}

/* setp_empty -- check if the set "a" is empty */
bool setp_empty(a)
register pset a;
{
    register int i = LOOP(a);
    do if (a[i]) return FALSE; while (--i > 0);
    return TRUE;
}

/* setp_full -- check if the set "a" is the full set of "size" elements */
bool setp_full(a, size)
register pset a;
register int size;
{
    register int i = LOOP(a);
    register unsigned int test;
    test = ~ (unsigned) 0;
    test >>= i * BPI - size;
    if (a[i] != test)
	return FALSE;
    while (--i > 0)
	if (a[i] != (~(unsigned) 0))
	    return FALSE;
    return TRUE;
}

/* setp_equal -- check if the set "a" equals set "b" */
bool setp_equal(a, b)
register pset a, b;
{
    register int i = LOOP(a);
    do if (a[i] != b[i]) return FALSE; while (--i > 0);
    return TRUE;
}

/* setp_disjoint -- check if intersection of "a" and "b" is empty */
bool setp_disjoint(a, b)
register pset a, b;
{
    register int i = LOOP(a);
    do if (a[i] & b[i]) return FALSE; while (--i > 0);
    return TRUE;
}

/* setp_implies -- check if "a" implies "b" ("b" contains "a") */
bool setp_implies(a, b)
register pset a, b;
{
    register int i = LOOP(a);
    do if (a[i] & ~b[i]) return FALSE; while (--i > 0);
    return TRUE;
}

/* sf_or -- form the "or" of all sets in a set family */
pset sf_or(A)
pset_family A;
{
    register pset or, last, p;

    or = set_new(A->sf_size);
    foreach_set(A, last, p)
	INLINEset_or(or, or, p);
    return or;
}

/* sf_and -- form the "and" of all sets in a set family */
pset sf_and(A)
pset_family A;
{
    register pset and, last, p;

    and = set_fill(set_new(A->sf_size), A->sf_size);
    foreach_set(A, last, p)
	INLINEset_and(and, and, p);
    return and;
}

/* sf_active -- make all members of the set family active */
pset_family sf_active(A)
pset_family A;
{
    register pset p, last;
    foreach_set(A, last, p) {
	SET(p, ACTIVE);
    }
    A->active_count = A->count;
    return A;
}


/* sf_inactive -- remove all inactive cubes in a set family */
pset_family sf_inactive(A)
pset_family A;
{
    register pset p, last, pdest;

    pdest = A->data;
    foreach_set(A, last, p) {
	if (TESTP(p, ACTIVE)) {
	    if (pdest != p) {
		INLINEset_copy(pdest, p);
	    }
	    pdest += A->wsize;
	} else {
	    A->count--;
	}
    }
    return A;
}


/* sf_copy -- copy a set family */
pset_family sf_copy(R, A)
pset_family R, A;
{
    R->sf_size = A->sf_size;
    R->wsize = A->wsize;
/*R->capacity = A->count;*/
/*R->data = REALLOC(unsigned int, R->data, (long) R->capacity * R->wsize);*/
    R->count = A->count;
    R->active_count = A->active_count;
    intcpy(R->data, A->data, (long) A->wsize * A->count);
    return R;
}


/* sf_join -- join A and B into a single set_family */
pset_family sf_join(A, B)
pset_family A, B;
{
    pset_family R;
    long asize = A->count * A->wsize;
    long bsize = B->count * B->wsize;
    
    assert (A->sf_size == B->sf_size);
    /* if (A->sf_size != B->sf_size) {
        fatal("sf_join: sf_size mismatch");
        } */
    
    /* if (A->sf_size != B->sf_size) fatal("sf_join: sf_size mismatch"); */
    R = sf_new(A->count + B->count, A->sf_size);
    R->count = A->count + B->count;
    R->active_count = A->active_count + B->active_count;
    intcpy(R->data, A->data, asize);
    intcpy(R->data + asize, B->data, bsize);
    return R;
}


/* sf_append -- append the sets of B to the end of A, and dispose of B */
pset_family sf_append(A, B)
pset_family A, B;
{
    long asize = A->count * A->wsize;
    long bsize = B->count * B->wsize;
    
    assert( A->sf_size == B->sf_size );
    /* if (A->sf_size != B->sf_size) fatal("sf_append: sf_size mismatch"); */
    A->capacity = A->count + B->count;
    A->data = REALLOC(unsigned int, A->data, (long) A->capacity * A->wsize);
    intcpy(A->data + asize, B->data, bsize);
    A->count += B->count;
    A->active_count += B->active_count;
    sf_free(B);
    return A;
}


/* sf_new -- allocate "num" sets of "size" elements each */
pset_family sf_new(num, size)
int num, size;
{
    pset_family A;
    A = ALLOC(set_family_t, 1);
    
    /* if (set_family_garbage == NULL) {
	A = ALLOC(set_family_t, 1);
    } else {
	A = set_family_garbage;
	set_family_garbage = A->next;
	}*/
    A->sf_size = size;
    A->wsize = SET_SIZE(size);
    A->capacity = num;
    A->data = ALLOC(unsigned int, (long) A->capacity * A->wsize);
    if (A->data == 0) {
      if ((A->capacity * A->wsize) != 0) {
        printf("memory exausted in sf_new\n");
      }
    }
    A->count = 0;
    A->active_count = 0;
    return A;
}


/* sf_save -- create a duplicate copy of a set family */
pset_family sf_save(A)
register pset_family A;
{
    return sf_copy(sf_new(A->count, A->sf_size), A);
}


/* sf_free -- free the storage allocated for a set family */
void sf_free(A)
pset_family A;
{
    pset_family F=0;
    /* Test if (set_family_garbage==A) {F->count=1;} */
    
    FREE(A->data);
    A->next = set_family_garbage;
    set_family_garbage = A;
}


/* sf_cleanup -- free all of the set families from the garbage list */
void sf_cleanup()
{
    register pset_family p, pnext;
    for(p = set_family_garbage; p != (pset_family) NULL; p = pnext) {
	pnext = p->next;
	FREE(p);
    }
    set_family_garbage = (pset_family) NULL;
}


/* sf_addset -- add a set to the end of a set family */
pset_family sf_addset(A, s)
pset_family A;
pset s;
{
    register pset p;

    if (A->count >= A->capacity) {
	A->capacity = A->capacity + A->capacity/2 + 1;
	A->data = REALLOC(unsigned int, A->data, (long) A->capacity * A->wsize);
    }
    p = GETSET(A, A->count++);
    INLINEset_copy(p, s);
    return A;
}

/* sf_delset -- delete a set from a set family */
void sf_delset(A, i)
pset_family A;
int i;
{   (void) set_copy(GETSET(A,i), GETSET(A, --A->count));}