extraUtilBitMatrix.c File Reference

#include "extra.h"

Go to the source code of this file.

Data Structures
struct	Extra_BitMat_t_

Functions
Extra_BitMat_t *	Extra_BitMatrixStart (int nSize)
void	Extra_BitMatrixClean (Extra_BitMat_t *p)
void	Extra_BitMatrixStop (Extra_BitMat_t *p)
void	Extra_BitMatrixPrint (Extra_BitMat_t *pMat)
int	Extra_BitMatrixReadSize (Extra_BitMat_t *p)
void	Extra_BitMatrixInsert1 (Extra_BitMat_t *p, int i, int k)
int	Extra_BitMatrixLookup1 (Extra_BitMat_t *p, int i, int k)
void	Extra_BitMatrixDelete1 (Extra_BitMat_t *p, int i, int k)
void	Extra_BitMatrixInsert2 (Extra_BitMat_t *p, int i, int k)
int	Extra_BitMatrixLookup2 (Extra_BitMat_t *p, int i, int k)
void	Extra_BitMatrixDelete2 (Extra_BitMat_t *p, int i, int k)
void	Extra_BitMatrixOr (Extra_BitMat_t *p, int i, unsigned *pInfo)
void	Extra_BitMatrixOrTwo (Extra_BitMat_t *p, int i, int j)
int	Extra_BitMatrixCountOnesUpper (Extra_BitMat_t *p)
int	Extra_BitMatrixIsDisjoint (Extra_BitMat_t *p1, Extra_BitMat_t *p2)
int	Extra_BitMatrixIsClique (Extra_BitMat_t *pMat)

Function Documentation

void Extra_BitMatrixClean

(

Extra_BitMat_t *

p

)

Function*************************************************************

Synopsis [Stops the bit matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 110 of file extraUtilBitMatrix.c.

{
    memset( p->ppData[0], 0, sizeof(unsigned) * p->nSize * p->nWords );
}

int Extra_BitMatrixCountOnesUpper

(

Extra_BitMat_t *

p

)

Function*************************************************************

Synopsis [Counts the number of 1's in the upper rectangle.]

Description []

SideEffects []

SeeAlso []

Definition at line 349 of file extraUtilBitMatrix.c.

{
    int i, k, nTotal = 0;
    for ( i = 0; i < p->nSize; i++ )
        for ( k = i + 1; k < p->nSize; k++ )
            nTotal += ( (p->ppData[i][k>>5] & (1 << (k&31))) > 0 );
    return nTotal;
}

void Extra_BitMatrixDelete1	(	Extra_BitMat_t *	p,
		int	i,
		int	k
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file extraUtilBitMatrix.c.

{
    p->nDeletes++;
    if ( i < k )
        p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask));
    else
        p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask));
}

void Extra_BitMatrixDelete2	(	Extra_BitMat_t *	p,
		int	i,
		int	k
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 292 of file extraUtilBitMatrix.c.

{
    p->nDeletes++;
    if ( i > k )
        p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask));
    else
        p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask));
}

void Extra_BitMatrixInsert1	(	Extra_BitMat_t *	p,
		int	i,
		int	k
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 190 of file extraUtilBitMatrix.c.

{
    p->nInserts++;
    if ( i < k )
        p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask));
    else
        p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask));
}

void Extra_BitMatrixInsert2	(	Extra_BitMat_t *	p,
		int	i,
		int	k
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 252 of file extraUtilBitMatrix.c.

{
    p->nInserts++;
    if ( i > k )
        p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask));
    else
        p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask));
}

int Extra_BitMatrixIsClique

(

Extra_BitMat_t *

pMat

)

Function*************************************************************

Synopsis [Returns 1 if the matrix is a set of cliques.]

Description [For example pairwise symmetry info should satisfy this property.]

SideEffects []

SeeAlso []

Definition at line 391 of file extraUtilBitMatrix.c.

{
    int v, u, i;
    for ( v = 0; v < pMat->nSize; v++ )
    for ( u = v+1; u < pMat->nSize; u++ )
    {
        if ( !Extra_BitMatrixLookup1( pMat, v, u ) )
            continue;
        // v and u are symmetric
        for ( i = 0; i < pMat->nSize; i++ )
        {
            if ( i == v || i == u )
                continue;
            // i is neither v nor u
            // the symmetry status of i is the same w.r.t. to v and u
            if ( Extra_BitMatrixLookup1( pMat, i, v ) != Extra_BitMatrixLookup1( pMat, i, u ) )
                return 0;
        }
    }
    return 1;
}

int Extra_BitMatrixIsDisjoint	(	Extra_BitMat_t *	p1,
		Extra_BitMat_t *	p2
	)

Function*************************************************************

Synopsis [Returns 1 if the matrices have no entries in common.]

Description []

SideEffects []

SeeAlso []

Definition at line 369 of file extraUtilBitMatrix.c.

{
    int i, w;
    assert( p1->nSize == p2->nSize );
    for ( i = 0; i < p1->nSize; i++ )
        for ( w = 0; w < p1->nWords; w++ )
            if ( p1->ppData[i][w] & p2->ppData[i][w] )
                return 0;
    return 1;
}

int Extra_BitMatrixLookup1	(	Extra_BitMat_t *	p,
		int	i,
		int	k
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 210 of file extraUtilBitMatrix.c.

{
    p->nLookups++;
    if ( i < k )
        return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0);
    else
        return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0);
}

int Extra_BitMatrixLookup2	(	Extra_BitMat_t *	p,
		int	i,
		int	k
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 272 of file extraUtilBitMatrix.c.

{
    p->nLookups++;
    if ( i > k )
        return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0);
    else
        return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0);
}

void Extra_BitMatrixOr	(	Extra_BitMat_t *	p,
		int	i,
		unsigned *	pInfo
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 313 of file extraUtilBitMatrix.c.

{
    int w;
    for ( w = 0; w < p->nWords; w++ )
        p->ppData[i][w] |= pInfo[w];
}

void Extra_BitMatrixOrTwo	(	Extra_BitMat_t *	p,
		int	i,
		int	j
	)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 331 of file extraUtilBitMatrix.c.

{
    int w;
    for ( w = 0; w < p->nWords; w++ )
        p->ppData[i][w] = p->ppData[j][w] = (p->ppData[i][w] | p->ppData[j][w]);
}

void Extra_BitMatrixPrint

(

Extra_BitMat_t *

pMat

)

Function*************************************************************

Synopsis [Prints the bit-matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 144 of file extraUtilBitMatrix.c.

{
    int i, k, nVars;
    printf( "\n" );
    nVars = Extra_BitMatrixReadSize( pMat );
    for ( i = 0; i < nVars; i++ )
    {
        for ( k = 0; k <= i; k++ )
            printf( " " );
        for ( k = i+1; k < nVars; k++ )
            if ( Extra_BitMatrixLookup1( pMat, i, k ) )
                printf( "1" );
            else
                printf( "." );
        printf( "\n" );
    }
}

int Extra_BitMatrixReadSize

(

Extra_BitMat_t *

p

)

Function*************************************************************

Synopsis [Reads the matrix size.]

Description []

SideEffects []

SeeAlso []

Definition at line 174 of file extraUtilBitMatrix.c.

{
    return p->nSize;
}

Extra_BitMat_t* Extra_BitMatrixStart

(

int

nSize

)

AutomaticStart AutomaticEnd Function*************************************************************

Synopsis [Starts the bit matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 81 of file extraUtilBitMatrix.c.

{
    Extra_BitMat_t * p;
    int i;
    p = ABC_ALLOC( Extra_BitMat_t, 1 );
    memset( p, 0, sizeof(Extra_BitMat_t) );
    p->nSize     = nSize;
    p->nBitShift = (sizeof(unsigned) == 4) ?  5:  6;
    p->uMask     = (sizeof(unsigned) == 4) ? 31: 63;
    p->nWords    = nSize / (8 * sizeof(unsigned)) + ((nSize % (8 * sizeof(unsigned))) > 0);
    p->ppData    = ABC_ALLOC( unsigned *, nSize );
    p->ppData[0] = ABC_ALLOC( unsigned, nSize * p->nWords );
    memset( p->ppData[0], 0, sizeof(unsigned) * nSize * p->nWords );
    for ( i = 1; i < nSize; i++ )
        p->ppData[i] = p->ppData[i-1] + p->nWords;
    return p;
}

void Extra_BitMatrixStop

(

Extra_BitMat_t *

p

)

Function*************************************************************

Synopsis [Stops the bit matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 126 of file extraUtilBitMatrix.c.

{
    ABC_FREE( p->ppData[0] );
    ABC_FREE( p->ppData );
    ABC_FREE( p );
}