src/misc/espresso/set.c File Reference

#include "espresso.h"

Include dependency graph for set.c:

Go to the source code of this file.

Defines
#define	largest_string   120
Functions
static int	intcpy (unsigned int *d, unsigned int *s, long n)
int	bit_index (unsigned int a)
int	set_ord (pset a)
int	set_dist (pset a, pset b)
pset	set_clear (pset r, int size)
pset	set_fill (pset r, int size)
pset	set_copy (pset r, pset a)
pset	set_and (pset r, pset a, pset b)
pset	set_or (pset r, pset a, pset b)
pset	set_diff (pset r, pset a, pset b)
pset	set_xor (pset r, pset a, pset b)
pset	set_merge (pset r, pset a, pset b, pset mask)
bool	set_andp (pset r, pset a, pset b)
bool	set_orp (pset r, pset a, pset b)
bool	setp_empty (pset a)
bool	setp_full (pset a, int size)
bool	setp_equal (pset a, pset b)
bool	setp_disjoint (pset a, pset b)
bool	setp_implies (pset a, pset b)
pset	sf_or (pset_family A)
pset	sf_and (pset_family A)
pset_family	sf_active (pset_family A)
pset_family	sf_inactive (pset_family A)
pset_family	sf_copy (pset_family R, pset_family A)
pset_family	sf_join (pset_family A, pset_family B)
pset_family	sf_append (pset_family A, pset_family B)
pset_family	sf_new (int num, int size)
pset_family	sf_save (pset_family A)
void	sf_free (pset_family A)
void	sf_cleanup ()
pset_family	sf_addset (pset_family A, pset s)
void	sf_delset (pset_family A, int i)
void	sf_print (pset_family A)
void	sf_bm_print (pset_family A)
void	sf_write (FILE *fp, pset_family A)
pset_family	sf_read (FILE *fp)
void	set_write (FILE *fp, pset a)
pset_family	sf_bm_read (FILE *fp)
char *	ps1 (pset a)
char *	pbv1 (pset s, int n)
void	set_adjcnt (pset a, int *count, int weight)
int *	sf_count (pset_family A)
int *	sf_count_restricted (pset_family A, pset r)
pset_family	sf_delc (pset_family A, int first, int last)
pset_family	sf_addcol (pset_family A, int firstcol, int n)
pset_family	sf_delcol (pset_family A, int firstcol, int n)
pset_family	sf_copy_col (pset_family dst, int dstcol, pset_family src, int srccol)
pset_family	sf_compress (pset_family A, pset c)
pset_family	sf_transpose (pset_family A)
pset_family	sf_permute (pset_family A, int *permute, int npermute)
Variables
static pset_family	set_family_garbage = NULL
static char	s1 [largest_string]

---

Define Documentation

#define largest_string   120

Definition at line 510 of file set.c.

---

Function Documentation

int bit_index

(

unsigned int

a

)

Definition at line 31 of file set.c.

{
    register int i;
    if (a == 0)
        return -1;
    for(i = 0; (a & 1) == 0; a >>= 1, i++)
        ;
    return i;
}

static int intcpy	(	unsigned int *	d,
		unsigned int *	s,
		long	n
	)			[static]

Definition at line 19 of file set.c.

{
    register int i;
    for(i = 0; i < n; i++) {
        *d++ = *s++;
    }
}

char* pbv1	(	pset	s,
		int	n
	)

Definition at line 541 of file set.c.

{
    register int i;
    for(i = 0; i < n; i++)
        s1[i] = is_in_set(s,i) ? '1' : '0';
    s1[n] = '\0';
    return s1;
}

char* ps1

(

pset

a

)

Definition at line 512 of file set.c.

{
    register int i, num, l, len = 0, n = NELEM(a);
    char temp[20];
    bool first = TRUE;

    s1[len++] = '[';
    for(i = 0; i < n; i++)
        if (is_in_set(a,i)) {
            if (! first)
                s1[len++] = ',';
            first = FALSE; num = i;
            /* Generate digits (reverse order) */
            l = 0; do temp[l++] = num % 10 + '0'; while ((num /= 10) > 0);
            /* Copy them back in correct order */
            do s1[len++] = temp[--l]; while (l > 0);
            if (len > largest_string-15) {
                s1[len++] = '.'; s1[len++] = '.'; s1[len++] = '.';
                break;
            }
        }

    s1[len++] = ']';
    s1[len++] = '\0';
    return s1;
}

void set_adjcnt	(	pset	a,
		int *	count,
		int	weight
	)

Definition at line 555 of file set.c.

{
    register int i, base;
    register unsigned int val;

    for(i = LOOP(a); i > 0; ) {
        for(val = a[i], base = --i << LOGBPI; val != 0; base++, val >>= 1) {
            if (val & 1) {
                count[base] += weight;
            }
        }
    }
}

pset set_and	(	pset	r,
		pset	a,
		pset	b
	)

Definition at line 101 of file set.c.

{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] & b[i]; while (--i > 0);
    return r;
}

bool set_andp	(	pset	r,
		pset	a,
		pset	b
	)

Definition at line 150 of file set.c.

{
    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;
}

pset set_clear	(	pset	r,
		int	size
	)

Definition at line 68 of file set.c.

{
    register int i = LOOPINIT(size);
    *r = i; do r[i] = 0; while (--i > 0);
    return r;
}

pset set_copy	(	pset	r,
		pset	a
	)

Definition at line 92 of file set.c.

{
    register int i = LOOPCOPY(a);
    do r[i] = a[i]; while (--i >= 0);
    return r;
}

pset set_diff	(	pset	r,
		pset	a,
		pset	b
	)

Definition at line 119 of file set.c.

{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] & ~b[i]; while (--i > 0);
    return r;
}

int set_dist	(	pset	a,
		pset	b
	)

Definition at line 56 of file set.c.

{
    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;
}

pset set_fill	(	pset	r,
		int	size
	)

Definition at line 78 of file set.c.

{
    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;
}

pset set_merge	(	pset	r,
		pset	a,
		pset	b,
		pset	mask
	)

Definition at line 141 of file set.c.

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

pset set_or	(	pset	r,
		pset	a,
		pset	b
	)

Definition at line 110 of file set.c.

{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] | b[i]; while (--i > 0);
    return r;
}

int set_ord

(

pset

a

)

Definition at line 44 of file set.c.

{
    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;
}

bool set_orp	(	pset	r,
		pset	a,
		pset	b
	)

Definition at line 160 of file set.c.

{
    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;
}

void set_write	(	FILE *	fp,
		pset	a
	)

Definition at line 461 of file set.c.

{
    register int n = LOOP(a), j;

    for(j = 0; j <= n; j++) {
        (void) fprintf(fp, "%x ", a[j]);
        if ((j+1) % 8 == 0 && j != n)
            (void) fprintf(fp, "\n\t");
    }
    (void) fprintf(fp, "\n");
}

pset set_xor	(	pset	r,
		pset	a,
		pset	b
	)

Definition at line 128 of file set.c.

{
    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;
}

bool setp_disjoint	(	pset	a,
		pset	b
	)

Definition at line 205 of file set.c.

{
    register int i = LOOP(a);
    do if (a[i] & b[i]) return FALSE; while (--i > 0);
    return TRUE;
}

bool setp_empty

(

pset

a

)

Definition at line 170 of file set.c.

{
    register int i = LOOP(a);
    do if (a[i]) return FALSE; while (--i > 0);
    return TRUE;
}

bool setp_equal	(	pset	a,
		pset	b
	)

Definition at line 196 of file set.c.

{
    register int i = LOOP(a);
    do if (a[i] != b[i]) return FALSE; while (--i > 0);
    return TRUE;
}

bool setp_full	(	pset	a,
		int	size
	)

Definition at line 179 of file set.c.

{
    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;
}

bool setp_implies	(	pset	a,
		pset	b
	)

Definition at line 214 of file set.c.

{
    register int i = LOOP(a);
    do if (a[i] & ~b[i]) return FALSE; while (--i > 0);
    return TRUE;
}

pset_family sf_active

(

pset_family

A

)

Definition at line 247 of file set.c.

{
    register pset p, last;
    foreach_set(A, last, p) {
        SET(p, ACTIVE);
    }
    A->active_count = A->count;
    return A;
}

pset_family sf_addcol	(	pset_family	A,
		int	firstcol,
		int	n
	)

Definition at line 648 of file set.c.

{
    int maxsize;

    /* Check if adding columns at the end ... */
    if (firstcol == A->sf_size) {
        /* If so, check if there is already enough room */
        maxsize = BPI * LOOPINIT(A->sf_size);
        if ((A->sf_size + n) <= maxsize) {
            A->sf_size += n;
            return A;
        }
    }
    return sf_delcol(A, firstcol, -n);
}

pset_family sf_addset	(	pset_family	A,
		pset	s
	)

Definition at line 383 of file set.c.

{
    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;
}

pset sf_and

(

pset_family

A

)

Definition at line 235 of file set.c.

{
    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;
}

pset_family sf_append	(	pset_family	A,
		pset_family	B
	)

Definition at line 314 of file set.c.

{
    long asize = A->count * A->wsize;
    long bsize = B->count * B->wsize;

    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;
}

void sf_bm_print

(

pset_family

A

)

Definition at line 416 of file set.c.

{
    char *pbv1();
    register pset p;
    register int i;
    foreachi_set(A, i, p)
        printf("[%4d] %s\n", i, pbv1(p, A->sf_size));
}

pset_family sf_bm_read

(

FILE *

fp

)

Definition at line 477 of file set.c.

{
    int i, j, rows, cols;
    register pset pdest;
    pset_family A;

    (void) fscanf(fp, "%d %d\n", &rows, &cols);
    A = sf_new(rows, cols);
    for(i = 0; i < rows; i++) {
        pdest = GETSET(A, A->count++);
        (void) set_clear(pdest, A->sf_size);
        for(j = 0; j < cols; j++) {
            switch(getc(fp)) {
                case '0':
                    break;
                case '1':
                    set_insert(pdest, j);
                    break;
                default:
                    fatal("Error reading set family");
            }
        }
        if (getc(fp) != '\n') {
            fatal("Error reading set family (at end of line)");
        }
    }
    return A;
}

void sf_cleanup

(

)

Definition at line 371 of file set.c.

{
    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;
}

pset_family sf_compress	(	pset_family	A,
		pset	c
	)

Definition at line 735 of file set.c.

{
    register pset p;
    register int i, bcol;
    pset_family B;

    /* create a clean set family for the result */
    B = sf_new(A->count, set_ord(c));
    for(i = 0; i < A->count; i++) {
        p = GETSET(B, B->count++);
        INLINEset_clear(p, B->sf_size);
    }

    /* copy each column of A which has a 1 in c */
    bcol = 0;
    for(i = 0; i < A->sf_size; i++) {
        if (is_in_set(c, i)) {
            (void) sf_copy_col(B, bcol++, A, i);
        }
    }
    sf_free(A);
    return B;
}

pset_family sf_copy	(	pset_family	R,
		pset_family	A
	)

Definition at line 281 of file set.c.

{
    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;
}

pset_family sf_copy_col	(	pset_family	dst,
		int	dstcol,
		pset_family	src,
		int	srccol
	)

Definition at line 703 of file set.c.

{
    register pset last, p, pdest;
    register int word_test, word_set;
    unsigned int bit_set, bit_test;

    /* CHEAT! form these constants outside the loop */
    word_test = WHICH_WORD(srccol);
    bit_test = 1 << WHICH_BIT(srccol);
    word_set = WHICH_WORD(dstcol);
    bit_set = 1 << WHICH_BIT(dstcol);

    pdest = dst->data;
    foreach_set(src, last, p) {
        if ((p[word_test] & bit_test) != 0)
            pdest[word_set] |= bit_set;
/*
 *  equivalent code for this is ...
 *      if (is_in_set(p, srccol)) set_insert(pdest, destcol);
 */
        pdest += dst->wsize;
    }
    return dst;
}

int* sf_count

(

pset_family

A

)

Definition at line 574 of file set.c.

{
    register pset p, last;
    register int i, base, *count;
    register unsigned int val;

    count = ALLOC(int, A->sf_size);
    for(i = A->sf_size - 1; i >= 0; i--) {
        count[i] = 0;
    }

    foreach_set(A, last, p) {
        for(i = LOOP(p); i > 0; ) {
            for(val = p[i], base = --i << LOGBPI; val != 0; base++, val >>= 1) {
                if (val & 1) {
                    count[base]++;
                }
            }
        }
    }
    return count;
}

int* sf_count_restricted	(	pset_family	A,
		pset	r
	)

Definition at line 603 of file set.c.

{
    register pset p;
    register int i, base, *count;
    register unsigned int val;
    int weight;
    pset last;

    count = ALLOC(int, A->sf_size);
    for(i = A->sf_size - 1; i >= 0; i--) {
        count[i] = 0;
    }

    /* Loop for each set */
    foreach_set(A, last, p) {
        weight = 1024 / (set_ord(p) - 1);
        for(i = LOOP(p); i > 0; ) {
            for(val=p[i]&r[i], base= --i<<LOGBPI; val!=0; base++, val >>= 1) {
                if (val & 1) {
                    count[base] += weight;
                }
            }
        }
    }
    return count;
}

pset_family sf_delc	(	pset_family	A,
		int	first,
		int	last
	)

Definition at line 636 of file set.c.

{
    return sf_delcol(A, first, last-first + 1);
}

pset_family sf_delcol	(	pset_family	A,
		int	firstcol,
		int	n
	)

Definition at line 676 of file set.c.

{
    register pset p, last, pdest;
    register int i;
    pset_family B;

    B = sf_new(A->count, A->sf_size - n);
    foreach_set(A, last, p) {
        pdest = GETSET(B, B->count++);
        INLINEset_clear(pdest, B->sf_size);
        for(i = 0; i < firstcol; i++)
            if (is_in_set(p, i))
                set_insert(pdest, i);
        for(i = n > 0 ? firstcol + n : firstcol; i < A->sf_size; i++)
            if (is_in_set(p, i))
                set_insert(pdest, i - n);
    }
    sf_free(A);
    return B;
}

void sf_delset	(	pset_family	A,
		int	i
	)

Definition at line 399 of file set.c.

{   (void) set_copy(GETSET(A,i), GETSET(A, --A->count));}

void sf_free

(

pset_family

A

)

Definition at line 361 of file set.c.

{
    FREE(A->data);
    A->next = set_family_garbage;
    set_family_garbage = A;
}

pset_family sf_inactive

(

pset_family

A

)

Definition at line 260 of file set.c.

{
    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;
}

pset_family sf_join	(	pset_family	A,
		pset_family	B
	)

Definition at line 296 of file set.c.

{
    pset_family R;
    long asize = A->count * A->wsize;
    long bsize = B->count * B->wsize;

    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;
}

pset_family sf_new	(	int	num,
		int	size
	)

Definition at line 332 of file set.c.

{
    pset_family A;
    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);
    A->count = 0;
    A->active_count = 0;
    return A;
}

pset sf_or

(

pset_family

A

)

Definition at line 223 of file set.c.

{
    register pset or, last, p;

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

pset_family sf_permute	(	pset_family	A,
		int *	permute,
		int	npermute
	)

Definition at line 798 of file set.c.

{
    pset_family B;
    register pset p, last, pdest;
    register int j;

    B = sf_new(A->count, npermute);
    B->count = A->count;
    foreach_set(B, last, p)
        INLINEset_clear(p, npermute);

    pdest = B->data;
    foreach_set(A, last, p) {
        for(j = 0; j < npermute; j++)
            if (is_in_set(p, permute[j]))
                set_insert(pdest, j);
        pdest += B->wsize;
    }
    sf_free(A);
    return B;
}

void sf_print

(

pset_family

A

)

Definition at line 405 of file set.c.

{
    char *ps1();
    register pset p;
    register int i;
    foreachi_set(A, i, p)
        printf("A[%d] = %s\n", i, ps1(p));
}

pset_family sf_read

(

FILE *

fp

)

Definition at line 441 of file set.c.

{
    int i, j;
    register pset p, last;
    pset_family A;

    (void) fscanf(fp, "%d %d\n", &i, &j);
    A = sf_new(i, j);
    A->count = i;
    foreach_set(A, last, p) {
        (void) fscanf(fp, "%x", p);
        for(j = 1; j <= LOOP(p); j++)
            (void) fscanf(fp, "%x", p+j);
    }
    return A;
}

pset_family sf_save

(

pset_family

A

)

Definition at line 353 of file set.c.

{
    return sf_copy(sf_new(A->count, A->sf_size), A);
}

pset_family sf_transpose

(

pset_family

A

)

Definition at line 768 of file set.c.

{
    pset_family B;
    register pset p;
    register int i, j;

    B = sf_new(A->sf_size, A->count);
    B->count = A->sf_size;
    foreachi_set(B, i, p) {
        INLINEset_clear(p, B->sf_size);
    }
    foreachi_set(A, i, p) {
        for(j = 0; j < A->sf_size; j++) {
            if (is_in_set(p, j)) {
                set_insert(GETSET(B, j), i);
            }
        }
    }
    sf_free(A);
    return B;
}

void sf_write	(	FILE *	fp,
		pset_family	A
	)

Definition at line 428 of file set.c.

{
    register pset p, last;
    (void) fprintf(fp, "%d %d\n", A->count, A->sf_size);
    foreach_set(A, last, p)
        set_write(fp, p);
    (void) fflush(fp);
}

---

Variable Documentation

char s1[largest_string] [static]

Definition at line 511 of file set.c.

pset_family set_family_garbage = NULL [static]

Definition at line 17 of file set.c.