diff options
Diffstat (limited to 'src/misc/extra/extraUtilBitMatrix.c')
-rw-r--r-- | src/misc/extra/extraUtilBitMatrix.c | 415 |
1 files changed, 0 insertions, 415 deletions
diff --git a/src/misc/extra/extraUtilBitMatrix.c b/src/misc/extra/extraUtilBitMatrix.c deleted file mode 100644 index b860a538..00000000 --- a/src/misc/extra/extraUtilBitMatrix.c +++ /dev/null @@ -1,415 +0,0 @@ -/**CFile**************************************************************** - - FileName [extraUtilBitMatrix.c] - - PackageName [extra] - - Synopsis [Various reusable software utilities.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - September 1, 2003.] - - Revision [$Id: extraUtilBitMatrix.c,v 1.0 2003/09/01 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "extra.h" - -/*---------------------------------------------------------------------------*/ -/* Constant declarations */ -/*---------------------------------------------------------------------------*/ - -/*---------------------------------------------------------------------------*/ -/* Stucture declarations */ -/*---------------------------------------------------------------------------*/ - -struct Extra_BitMat_t_ -{ - unsigned ** ppData; // bit data - int nSize; // the number of bits in one dimension - int nWords; // the number of words in one dimension - int nBitShift; // the number of bits to shift to get words - unsigned uMask; // the mask to get the number of bits in the word - int nLookups; // the number of lookups - int nInserts; // the number of inserts - int nDeletes; // the number of deletions -}; - -/*---------------------------------------------------------------------------*/ -/* Type declarations */ -/*---------------------------------------------------------------------------*/ - -/*---------------------------------------------------------------------------*/ -/* Variable declarations */ -/*---------------------------------------------------------------------------*/ - -/*---------------------------------------------------------------------------*/ -/* Macro declarations */ -/*---------------------------------------------------------------------------*/ - - -/**AutomaticStart*************************************************************/ - -/*---------------------------------------------------------------------------*/ -/* Static function prototypes */ -/*---------------------------------------------------------------------------*/ - -/**AutomaticEnd***************************************************************/ - - -/*---------------------------------------------------------------------------*/ -/* Definition of exported functions */ -/*---------------------------------------------------------------------------*/ - -/**Function************************************************************* - - Synopsis [Starts the bit matrix.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Extra_BitMat_t * Extra_BitMatrixStart( int nSize ) -{ - Extra_BitMat_t * p; - int i; - p = 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 = ALLOC( unsigned *, nSize ); - p->ppData[0] = 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; -} - -/**Function************************************************************* - - Synopsis [Stops the bit matrix.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixClean( Extra_BitMat_t * p ) -{ - memset( p->ppData[0], 0, sizeof(unsigned) * p->nSize * p->nWords ); -} - -/**Function************************************************************* - - Synopsis [Stops the bit matrix.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixStop( Extra_BitMat_t * p ) -{ - FREE( p->ppData[0] ); - FREE( p->ppData ); - FREE( p ); -} - -/**Function************************************************************* - - Synopsis [Prints the bit-matrix.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixPrint( Extra_BitMat_t * pMat ) -{ - 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" ); - } -} - - -/**Function************************************************************* - - Synopsis [Reads the matrix size.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Extra_BitMatrixReadSize( Extra_BitMat_t * p ) -{ - return p->nSize; -} - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixInsert1( Extra_BitMat_t * p, int i, int k ) -{ - 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)); -} - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Extra_BitMatrixLookup1( Extra_BitMat_t * p, int i, int k ) -{ - 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); -} - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixDelete1( Extra_BitMat_t * p, int i, int k ) -{ - 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)); -} - - - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixInsert2( Extra_BitMat_t * p, int i, int k ) -{ - 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)); -} - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Extra_BitMatrixLookup2( Extra_BitMat_t * p, int i, int k ) -{ - 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); -} - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixDelete2( Extra_BitMat_t * p, int i, int k ) -{ - 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)); -} - - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixOr( Extra_BitMat_t * p, int i, unsigned * pInfo ) -{ - int w; - for ( w = 0; w < p->nWords; w++ ) - p->ppData[i][w] |= pInfo[w]; -} - -/**Function************************************************************* - - Synopsis [Inserts the element into the upper part.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Extra_BitMatrixOrTwo( Extra_BitMat_t * p, int i, int j ) -{ - 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]); -} - -/**Function************************************************************* - - Synopsis [Counts the number of 1's in the upper rectangle.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Extra_BitMatrixCountOnesUpper( Extra_BitMat_t * p ) -{ - 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; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if the matrices have no entries in common.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Extra_BitMatrixIsDisjoint( Extra_BitMat_t * p1, Extra_BitMat_t * p2 ) -{ - 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; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if the matrix is a set of cliques.] - - Description [For example pairwise symmetry info should satisfy this property.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Extra_BitMatrixIsClique( Extra_BitMat_t * pMat ) -{ - 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; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |