contain.c File Reference

#include "espresso.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START pset_family	sf_contain (INOUT pset_family A)
pset_family	sf_rev_contain (INOUT pset_family A)
pset_family	sf_ind_contain (INOUT pset_family A, INOUT int *row_indices)
pset_family	sf_dupl (INOUT pset_family A)
pset_family	sf_union (INOUT pset_family A, INOUT pset_family B)
pset_family	dist_merge (INOUT pset_family A, IN pset mask)
pset_family	d1merge (INOUT pset_family A, IN int var)
int	d1_rm_equal (pset *A1, int(*compare)())
int	rm_equal (INOUT pset *A1, IN int(*compare)())
int	rm_contain (INOUT pset *A1)
int	rm_rev_contain (INOUT pset *A1)
int	rm2_equal (INOUT register pset *A1, INOUT register pset *B1, OUT pset *E1, IN int(*compare)())
int	rm2_contain (INOUT pset *A1, IN pset *B1)
pset *	sf_sort (IN pset_family A, IN int(*compare)())
pset *	sf_list (IN register pset_family A)
pset_family	sf_unlist (IN pset *A1, IN int totcnt, IN int size)
pset_family	sf_ind_unlist (IN pset *A1, IN int totcnt, IN int size, INOUT int *row_indices, IN register pset pfirst)
pset_family	sf_merge (INOUT pset *A1, INOUT pset *B1, INOUT pset *E1, IN int totcnt, IN int size)

Function Documentation

int d1_rm_equal	(	pset *	A1,
		int (*)()	compare
	)

Definition at line 171 of file contain.c.

{
    register int i, j, dest;

    dest = 0;
    if (A1[0] != (pcube) NULL) {
    for(i = 0, j = 1; A1[j] != (pcube) NULL; j++)
        if ( (*compare)(&A1[i], &A1[j]) == 0) {
        /* if sets are equal (under the mask) merge them */
        (void) set_or(A1[i], A1[i], A1[j]);
        } else {
        /* sets are unequal, so save the set i */
        A1[dest++] = A1[i];
        i = j;
        }
    A1[dest++] = A1[i];
    }
    A1[dest] = (pcube) NULL;
    return dest;
}

pset_family d1merge	(	INOUT pset_family	A,
		IN int	var
	)

Definition at line 161 of file contain.c.

{
    return dist_merge(A, cube.var_mask[var]);
}

pset_family dist_merge	(	INOUT pset_family	A,
		IN pset	mask
	)

Definition at line 141 of file contain.c.

{
    pset *A1;
    int cnt;
    pset_family R;

    (void) set_copy(cube.temp[0], mask);
    A1 = sf_sort(A, d1_order);
    cnt = d1_rm_equal(A1, d1_order);
    R = sf_unlist(A1, cnt, A->sf_size);
    sf_free(A);
    return R;
}

int rm2_contain	(	INOUT pset *	A1,
		IN pset *	B1
	)

Definition at line 304 of file contain.c.

{
    register pset *pa, *pb, a, b, *pdest = A1;

    /* for each set in the first array ... */
    for(pa = A1; (a = *pa++) != NULL; ) {
    /* for each set in the second array which is larger ... */
    for(pb = B1; (b = *pb++) != NULL && SIZE(b) > SIZE(a); ) {
        INLINEsetp_implies(a, b, /* when_false => */ continue);
        /* set was contained in some set of B, so don't save pointer */
        goto lnext1;
    }
    /* set wasn't contained in any set of B, so save the pointer */
    *pdest++ = a;
    lnext1: ;
    }

    *pdest = NULL;                      /* sentinel */
    return pdest - A1;                  /* # elements in A1 */
}

int rm2_equal	(	INOUT register pset *	A1,
		INOUT register pset *	B1,
		OUT pset *	E1,
		IN int (*)()	compare
	)

Definition at line 274 of file contain.c.

{
    register pset *pda = A1, *pdb = B1, *pde = E1;

    /* Walk through the arrays advancing pointer to larger cube */
    for(; *A1 != NULL && *B1 != NULL; )
    switch((*compare)(A1, B1)) {
        case -1:    /* "a" comes before "b" */
        *pda++ = *A1++; break;
        case 0:     /* equal cubes */
        *pde++ = *A1++; B1++; break;
        case 1:     /* "a" is to follow "b" */
        *pdb++ = *B1++; break;
    }

    /* Finish moving down the pointers of A and B */
    while (*A1 != NULL)
    *pda++ = *A1++;
    while (*B1 != NULL)
    *pdb++ = *B1++;
    *pda = *pdb = *pde = NULL;

    return pde - E1;
}

int rm_contain

(

INOUT pset *

A1

)

Definition at line 214 of file contain.c.

{
    register pset *pa, *pb;
    register pset *pcheck = NULL; // Suppress "might be used uninitialized"
    register pset a, b;
    pset *pdest = A1;
    int last_size = -1;

    /* Loop for all cubes of A1 */
    for(pa = A1; (a = *pa++) != NULL; ) {
    /* Update the check pointer if the size has changed */
    if (SIZE(a) != last_size)
        last_size = SIZE(a), pcheck = pdest;
    for(pb = A1; pb != pcheck; ) {
        b = *pb++;
        INLINEsetp_implies(a, b, /* when_false => */ continue);
        goto lnext1;
    }
    /* set a was not contained by some larger set, so save it */
    *pdest++ = a;
    lnext1: ;
    }

    *pdest = NULL;
    return pdest - A1;
}

int rm_equal	(	INOUT pset *	A1,
		IN int (*)()	compare
	)

Definition at line 196 of file contain.c.

{
    register pset *p, *pdest = A1;

    if (*A1 != NULL) {                  /* If more than one set */
    for(p = A1+1; *p != NULL; p++)
        if ((*compare)(p, p-1) != 0)
        *pdest++ = *(p-1);
    *pdest++ = *(p-1);
    *pdest = NULL;
    }
    return pdest - A1;
}

int rm_rev_contain

(

INOUT pset *

A1

)

Definition at line 244 of file contain.c.

{
    register pset *pa, *pb;
    register pset *pcheck = NULL; // Suppress "might be used uninitialized"
    register pset a, b;
    pset *pdest = A1;
    int last_size = -1;

    /* Loop for all cubes of A1 */
    for(pa = A1; (a = *pa++) != NULL; ) {
    /* Update the check pointer if the size has changed */
    if (SIZE(a) != last_size)
        last_size = SIZE(a), pcheck = pdest;
    for(pb = A1; pb != pcheck; ) {
        b = *pb++;
        INLINEsetp_implies(b, a, /* when_false => */ continue);
        goto lnext1;
    }
    /* the set a did not contain some smaller set, so save it */
    *pdest++ = a;
    lnext1: ;
    }

    *pdest = NULL;
    return pdest - A1;
}

ABC_NAMESPACE_IMPL_START pset_family sf_contain

(

INOUT pset_family

A

)

Definition at line 37 of file contain.c.

{
    int cnt;
    pset *A1;
    pset_family R;

    A1 = sf_sort(A, descend);           /* sort into descending order */
    cnt = rm_equal(A1, descend);        /* remove duplicates */
    cnt = rm_contain(A1);               /* remove contained sets */
    R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
    sf_free(A);
    return R;
}

pset_family sf_dupl

(

INOUT pset_family

A

)

Definition at line 99 of file contain.c.

{
    register int cnt;
    register pset *A1;
    pset_family R;

    A1 = sf_sort(A, descend);           /* sort the set family */
    cnt = rm_equal(A1, descend);        /* remove duplicates */
    R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
    sf_free(A);
    return R;
}

pset_family sf_ind_contain	(	INOUT pset_family	A,
		INOUT int *	row_indices
	)

Definition at line 81 of file contain.c.

{
    int cnt;
    pset *A1;
    pset_family R;

    A1 = sf_sort(A, descend);           /* sort into descending order */
    cnt = rm_equal(A1, descend);        /* remove duplicates */
    cnt = rm_contain(A1);               /* remove contained sets */
    R = sf_ind_unlist(A1, cnt, A->sf_size, row_indices, A->data);
    sf_free(A);
    return R;
}

pset_family sf_ind_unlist	(	IN pset *	A1,
		IN int	totcnt,
		IN int	size,
		INOUT int *	row_indices,
		IN register pset	pfirst
	)

Definition at line 382 of file contain.c.

{
    register pset pr, p, *pa;
    register int i, *new_row_indices;
    pset_family R = sf_new(totcnt, size);

    R->count = totcnt;
    new_row_indices = ALLOC(int, totcnt);
    for(pr = R->data, pa = A1, i=0; (p = *pa++) != NULL; pr += R->wsize, i++) {
    INLINEset_copy(pr, p);
    new_row_indices[i] = row_indices[(p - pfirst)/R->wsize];
    }
    for(i = 0; i < totcnt; i++)
    row_indices[i] = new_row_indices[i];
    FREE(new_row_indices);
    FREE(A1);
    return R;
}

pset* sf_list

(

IN register pset_family

A

)

Definition at line 351 of file contain.c.

{
    register pset p, last, *pdest, *A1;

    /* Create a single array pointing to each cube of A */
    pdest = A1 = ALLOC(pset, A->count + 1);
    foreach_set(A, last, p)
    *pdest++ = p;                   /* save the pointer */
    *pdest = NULL;                      /* Sentinel */
    return A1;
}

pset_family sf_merge	(	INOUT pset *	A1,
		INOUT pset *	B1,
		INOUT pset *	E1,
		IN int	totcnt,
		IN int	size
	)

Definition at line 407 of file contain.c.

{
    register pset pr, ps, *pmin, *pmid, *pmax;
    pset_family R;
    pset *temp[3], *swap;
    int i, j, n;

    /* Allocate the result set_family */
    R = sf_new(totcnt, size);
    R->count = totcnt;
    pr = R->data;

    /* Quick bubble sort to order the top member of the three arrays */
    n = 3;  temp[0] = A1;  temp[1] = B1;  temp[2] = E1;
    for(i = 0; i < n-1; i++)
    for(j = i+1; j < n; j++)
        if (desc1(*temp[i], *temp[j]) > 0) {
        swap = temp[j];
        temp[j] = temp[i];
        temp[i] = swap;
        }
    pmin = temp[0];  pmid = temp[1];  pmax = temp[2];

    /* Save the minimum element, then update pmin, pmid, pmax */
    while (*pmin != (pset) NULL) {
    ps = *pmin++;
    INLINEset_copy(pr, ps);
    pr += R->wsize;
    if (desc1(*pmin, *pmax) > 0) {
        swap = pmax; pmax = pmin; pmin = pmid; pmid = swap;
    } else if (desc1(*pmin, *pmid) > 0) {
        swap = pmin; pmin = pmid; pmid = swap;
    }
    }

    FREE(A1);
    FREE(B1);
    FREE(E1);
    return R;
}

pset_family sf_rev_contain

(

INOUT pset_family

A

)

Definition at line 58 of file contain.c.

{
    int cnt;
    pset *A1;
    pset_family R;

    A1 = sf_sort(A, ascend);            /* sort into ascending order */
    cnt = rm_equal(A1, ascend);         /* remove duplicates */
    cnt = rm_rev_contain(A1);           /* remove containing sets */
    R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
    sf_free(A);
    return R;
}

pset* sf_sort	(	IN pset_family	A,
		IN int (*)()	compare
	)

Definition at line 330 of file contain.c.

{
    register pset p, last, *pdest, *A1;

    /* Create a single array pointing to each cube of A */
    pdest = A1 = ALLOC(pset, A->count + 1);
    foreach_set(A, last, p) {
    PUTSIZE(p, set_ord(p));         /* compute the set size */
    *pdest++ = p;                   /* save the pointer */
    }
    *pdest = NULL;                      /* Sentinel -- never seen by sort */

    /* Sort cubes by size */
    qsort((char *) A1, A->count, sizeof(pset), compare);
    return A1;
}

pset_family sf_union	(	INOUT pset_family	A,
		INOUT pset_family	B
	)

Definition at line 121 of file contain.c.

{
    int cnt;
    pset_family R;
    pset *A1 = sf_list(A), *B1 = sf_list(B), *E1;

    E1 = ALLOC(pset, MAX(A->count, B->count) + 1);
    cnt = rm2_equal(A1, B1, E1, descend);
    cnt += rm2_contain(A1, B1) + rm2_contain(B1, A1);
    R = sf_merge(A1, B1, E1, cnt, A->sf_size);
    sf_free(A); sf_free(B);
    return R;
}

pset_family sf_unlist	(	IN pset *	A1,
		IN int	totcnt,
		IN int	size
	)

Definition at line 366 of file contain.c.

{
    register pset pr, p, *pa;
    pset_family R = sf_new(totcnt, size);

    R->count = totcnt;
    for(pr = R->data, pa = A1; (p = *pa++) != NULL; pr += R->wsize)
    INLINEset_copy(pr, p);
    FREE(A1);
    return R;
}