/**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; int nSize; int nWords; int nBitShift; unsigned uMask; int nLookups; int nInserts; int nDeletes; }; /*---------------------------------------------------------------------------*/ /* 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/32] & (1 << (k%32))) > 0 ); return nTotal; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// ////////////////////////////////////////////////////////////////////////