summaryrefslogtreecommitdiffstats
path: root/src/misc
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc')
-rw-r--r--src/misc/extra/extraUtilSupp.c143
-rw-r--r--src/misc/vec/vecInt.h136
-rw-r--r--src/misc/vec/vecWrd.h17
3 files changed, 141 insertions, 155 deletions
diff --git a/src/misc/extra/extraUtilSupp.c b/src/misc/extra/extraUtilSupp.c
index a2e089bb..baf9f3f6 100644
--- a/src/misc/extra/extraUtilSupp.c
+++ b/src/misc/extra/extraUtilSupp.c
@@ -40,149 +40,6 @@ extern void Extra_PrintBinary( FILE * pFile, unsigned Sign[], int nBits
/**Function*************************************************************
- Synopsis [Counts the number of unique entries.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-static inline unsigned Vec_IntUniqueHashKeyDebug( unsigned char * pStr, int nChars, int TableMask )
-{
- static unsigned s_BigPrimes[4] = {12582917, 25165843, 50331653, 100663319};
- unsigned Key = 0; int c;
- for ( c = 0; c < nChars; c++ )
- {
- Key += (unsigned)pStr[c] * s_BigPrimes[c & 3];
- printf( "%d : ", c );
- printf( "%3d ", pStr[c] );
- printf( "%12u ", Key );
- printf( "%12u ", Key&TableMask );
- printf( "\n" );
- }
- return Key;
-}
-void Vec_IntUniqueProfile( Vec_Int_t * vData, int * pTable, int * pNexts, int TableMask, int nIntSize )
-{
- int i, Key, Counter;
- for ( i = 0; i <= TableMask; i++ )
- {
- Counter = 0;
- for ( Key = pTable[i]; Key != -1; Key = pNexts[Key] )
- Counter++;
- if ( Counter < 7 )
- continue;
- printf( "%d\n", Counter );
- for ( Key = pTable[i]; Key != -1; Key = pNexts[Key] )
- {
- Extra_PrintBinary( stdout, (unsigned *)Vec_IntEntryP(vData, Key*nIntSize), 40 ), printf( "\n" );
-// Vec_IntUniqueHashKeyDebug( (unsigned char *)Vec_IntEntryP(vData, Key*nIntSize), 4*nIntSize, TableMask );
- }
- }
- printf( "\n" );
-}
-
-
-static inline unsigned Vec_IntUniqueHashKey2( unsigned char * pStr, int nChars )
-{
- static unsigned s_BigPrimes[4] = {12582917, 25165843, 50331653, 100663319};
- unsigned Key = 0; int c;
- for ( c = 0; c < nChars; c++ )
- Key += (unsigned)pStr[c] * s_BigPrimes[c & 3];
- return Key;
-}
-
-static inline unsigned Vec_IntUniqueHashKey( unsigned char * pStr, int nChars )
-{
- static unsigned s_BigPrimes[16] =
- {
- 0x984b6ad9,0x18a6eed3,0x950353e2,0x6222f6eb,0xdfbedd47,0xef0f9023,0xac932a26,0x590eaf55,
- 0x97d0a034,0xdc36cd2e,0x22736b37,0xdc9066b0,0x2eb2f98b,0x5d9c7baf,0x85747c9e,0x8aca1055
- };
- static unsigned s_BigPrimes2[16] =
- {
- 0x8d8a5ebe,0x1e6a15dc,0x197d49db,0x5bab9c89,0x4b55dea7,0x55dede49,0x9a6a8080,0xe5e51035,
- 0xe148d658,0x8a17eb3b,0xe22e4b38,0xe5be2a9a,0xbe938cbb,0x3b981069,0x7f9c0c8e,0xf756df10
- };
- unsigned Key = 0; int c;
- for ( c = 0; c < nChars; c++ )
- Key += s_BigPrimes2[(2*c)&15] * s_BigPrimes[(unsigned)pStr[c] & 15] +
- s_BigPrimes2[(2*c+1)&15] * s_BigPrimes[(unsigned)pStr[c] >> 4];
- return Key;
-}
-static inline int * Vec_IntUniqueLookup( Vec_Int_t * vData, int i, int nIntSize, int * pNexts, int * pStart )
-{
- int * pData = Vec_IntEntryP( vData, i*nIntSize );
- for ( ; *pStart != -1; pStart = pNexts + *pStart )
- if ( !memcmp( pData, Vec_IntEntryP(vData, *pStart*nIntSize), sizeof(int) * nIntSize ) )
- return pStart;
- return pStart;
-}
-static inline int Vec_IntUniqueCount( Vec_Int_t * vData, int nIntSize, Vec_Int_t ** pvMap )
-{
- int nEntries = Vec_IntSize(vData) / nIntSize;
- int TableMask = (1 << Abc_Base2Log(nEntries)) - 1;
- int * pTable = ABC_FALLOC( int, TableMask+1 );
- int * pNexts = ABC_FALLOC( int, TableMask+1 );
- int * pClass = ABC_ALLOC( int, nEntries );
- int i, Key, * pEnt, nUnique = 0;
- assert( nEntries * nIntSize == Vec_IntSize(vData) );
- for ( i = 0; i < nEntries; i++ )
- {
- pEnt = Vec_IntEntryP( vData, i*nIntSize );
- Key = TableMask & Vec_IntUniqueHashKey( (unsigned char *)pEnt, 4*nIntSize );
- pEnt = Vec_IntUniqueLookup( vData, i, nIntSize, pNexts, pTable+Key );
- if ( *pEnt == -1 )
- *pEnt = i, nUnique++;
- pClass[i] = *pEnt;
- }
-// Vec_IntUniqueProfile( vData, pTable, pNexts, TableMask, nIntSize );
- ABC_FREE( pTable );
- ABC_FREE( pNexts );
- if ( pvMap )
- *pvMap = Vec_IntAllocArray( pClass, nEntries );
- else
- ABC_FREE( pClass );
- return nUnique;
-}
-static inline Vec_Int_t * Vec_IntUniqifyHash( Vec_Int_t * vData, int nIntSize )
-{
- Vec_Int_t * vMap, * vUnique;
- int i, Ent, nUnique = Vec_IntUniqueCount( vData, nIntSize, &vMap );
- vUnique = Vec_IntAlloc( nUnique * nIntSize );
- Vec_IntForEachEntry( vMap, Ent, i )
- {
- if ( Ent < i ) continue;
- assert( Ent == i );
- Vec_IntPushArray( vUnique, Vec_IntEntryP(vData, i*nIntSize), nIntSize );
- }
- assert( Vec_IntSize(vUnique) == nUnique * nIntSize );
- Vec_IntFree( vMap );
- return vUnique;
-}
-static inline Vec_Wrd_t * Vec_WrdUniqifyHash( Vec_Wrd_t * vData, int nWordSize )
-{
- Vec_Int_t * vResInt;
- Vec_Int_t * vDataInt = (Vec_Int_t *)vData;
- vDataInt->nSize *= 2;
- vDataInt->nCap *= 2;
- vResInt = Vec_IntUniqifyHash( vDataInt, 2 * nWordSize );
- vDataInt->nSize /= 2;
- vDataInt->nCap /= 2;
- vResInt->nSize /= 2;
- vResInt->nCap /= 2;
- return (Vec_Wrd_t *)vResInt;
-}
-static inline word * Vec_WrdLimit( Vec_Wrd_t * p )
-{
- return p->pArray + p->nSize;
-}
-
-
-/**Function*************************************************************
-
Synopsis [Generate m-out-of-n vectors.]
Description []
diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h
index 824846b4..535a15ef 100644
--- a/src/misc/vec/vecInt.h
+++ b/src/misc/vec/vecInt.h
@@ -331,18 +331,6 @@ static inline int ** Vec_IntArrayP( Vec_Int_t * p )
{
return &p->pArray;
}
-
-/**Function*************************************************************
-
- Synopsis []
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
static inline int * Vec_IntLimit( Vec_Int_t * p )
{
return p->pArray + p->nSize;
@@ -1317,6 +1305,130 @@ static inline int Vec_IntCountUnique( Vec_Int_t * p )
/**Function*************************************************************
+ Synopsis [Counts the number of unique entries.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline unsigned Vec_IntUniqueHashKeyDebug( unsigned char * pStr, int nChars, int TableMask )
+{
+ static unsigned s_BigPrimes[4] = {12582917, 25165843, 50331653, 100663319};
+ unsigned Key = 0; int c;
+ for ( c = 0; c < nChars; c++ )
+ {
+ Key += (unsigned)pStr[c] * s_BigPrimes[c & 3];
+ printf( "%d : ", c );
+ printf( "%3d ", pStr[c] );
+ printf( "%12u ", Key );
+ printf( "%12u ", Key&TableMask );
+ printf( "\n" );
+ }
+ return Key;
+}
+static inline void Vec_IntUniqueProfile( Vec_Int_t * vData, int * pTable, int * pNexts, int TableMask, int nIntSize )
+{
+ int i, Key, Counter;
+ for ( i = 0; i <= TableMask; i++ )
+ {
+ Counter = 0;
+ for ( Key = pTable[i]; Key != -1; Key = pNexts[Key] )
+ Counter++;
+ if ( Counter < 7 )
+ continue;
+ printf( "%d\n", Counter );
+ for ( Key = pTable[i]; Key != -1; Key = pNexts[Key] )
+ {
+// Extra_PrintBinary( stdout, (unsigned *)Vec_IntEntryP(vData, Key*nIntSize), 40 ), printf( "\n" );
+// Vec_IntUniqueHashKeyDebug( (unsigned char *)Vec_IntEntryP(vData, Key*nIntSize), 4*nIntSize, TableMask );
+ }
+ }
+ printf( "\n" );
+}
+
+static inline unsigned Vec_IntUniqueHashKey2( unsigned char * pStr, int nChars )
+{
+ static unsigned s_BigPrimes[4] = {12582917, 25165843, 50331653, 100663319};
+ unsigned Key = 0; int c;
+ for ( c = 0; c < nChars; c++ )
+ Key += (unsigned)pStr[c] * s_BigPrimes[c & 3];
+ return Key;
+}
+
+static inline unsigned Vec_IntUniqueHashKey( unsigned char * pStr, int nChars )
+{
+ static unsigned s_BigPrimes[16] =
+ {
+ 0x984b6ad9,0x18a6eed3,0x950353e2,0x6222f6eb,0xdfbedd47,0xef0f9023,0xac932a26,0x590eaf55,
+ 0x97d0a034,0xdc36cd2e,0x22736b37,0xdc9066b0,0x2eb2f98b,0x5d9c7baf,0x85747c9e,0x8aca1055
+ };
+ static unsigned s_BigPrimes2[16] =
+ {
+ 0x8d8a5ebe,0x1e6a15dc,0x197d49db,0x5bab9c89,0x4b55dea7,0x55dede49,0x9a6a8080,0xe5e51035,
+ 0xe148d658,0x8a17eb3b,0xe22e4b38,0xe5be2a9a,0xbe938cbb,0x3b981069,0x7f9c0c8e,0xf756df10
+ };
+ unsigned Key = 0; int c;
+ for ( c = 0; c < nChars; c++ )
+ Key += s_BigPrimes2[(2*c)&15] * s_BigPrimes[(unsigned)pStr[c] & 15] +
+ s_BigPrimes2[(2*c+1)&15] * s_BigPrimes[(unsigned)pStr[c] >> 4];
+ return Key;
+}
+static inline int * Vec_IntUniqueLookup( Vec_Int_t * vData, int i, int nIntSize, int * pNexts, int * pStart )
+{
+ int * pData = Vec_IntEntryP( vData, i*nIntSize );
+ for ( ; *pStart != -1; pStart = pNexts + *pStart )
+ if ( !memcmp( pData, Vec_IntEntryP(vData, *pStart*nIntSize), sizeof(int) * nIntSize ) )
+ return pStart;
+ return pStart;
+}
+static inline int Vec_IntUniqueCount( Vec_Int_t * vData, int nIntSize, Vec_Int_t ** pvMap )
+{
+ int nEntries = Vec_IntSize(vData) / nIntSize;
+ int TableMask = (1 << Abc_Base2Log(nEntries)) - 1;
+ int * pTable = ABC_FALLOC( int, TableMask+1 );
+ int * pNexts = ABC_FALLOC( int, TableMask+1 );
+ int * pClass = ABC_ALLOC( int, nEntries );
+ int i, Key, * pEnt, nUnique = 0;
+ assert( nEntries * nIntSize == Vec_IntSize(vData) );
+ for ( i = 0; i < nEntries; i++ )
+ {
+ pEnt = Vec_IntEntryP( vData, i*nIntSize );
+ Key = TableMask & Vec_IntUniqueHashKey( (unsigned char *)pEnt, 4*nIntSize );
+ pEnt = Vec_IntUniqueLookup( vData, i, nIntSize, pNexts, pTable+Key );
+ if ( *pEnt == -1 )
+ *pEnt = i, nUnique++;
+ pClass[i] = *pEnt;
+ }
+// Vec_IntUniqueProfile( vData, pTable, pNexts, TableMask, nIntSize );
+ ABC_FREE( pTable );
+ ABC_FREE( pNexts );
+ if ( pvMap )
+ *pvMap = Vec_IntAllocArray( pClass, nEntries );
+ else
+ ABC_FREE( pClass );
+ return nUnique;
+}
+static inline Vec_Int_t * Vec_IntUniqifyHash( Vec_Int_t * vData, int nIntSize )
+{
+ Vec_Int_t * vMap, * vUnique;
+ int i, Ent, nUnique = Vec_IntUniqueCount( vData, nIntSize, &vMap );
+ vUnique = Vec_IntAlloc( nUnique * nIntSize );
+ Vec_IntForEachEntry( vMap, Ent, i )
+ {
+ if ( Ent < i ) continue;
+ assert( Ent == i );
+ Vec_IntPushArray( vUnique, Vec_IntEntryP(vData, i*nIntSize), nIntSize );
+ }
+ assert( Vec_IntSize(vUnique) == nUnique * nIntSize );
+ Vec_IntFree( vMap );
+ return vUnique;
+}
+
+/**Function*************************************************************
+
Synopsis [Comparison procedure for two integers.]
Description []
diff --git a/src/misc/vec/vecWrd.h b/src/misc/vec/vecWrd.h
index 9c33a5ba..c765dd8d 100644
--- a/src/misc/vec/vecWrd.h
+++ b/src/misc/vec/vecWrd.h
@@ -317,6 +317,10 @@ static inline word * Vec_WrdArray( Vec_Wrd_t * p )
{
return p->pArray;
}
+static inline word * Vec_WrdLimit( Vec_Wrd_t * p )
+{
+ return p->pArray + p->nSize;
+}
/**Function*************************************************************
@@ -1080,6 +1084,19 @@ static inline void Vec_WrdUniqify( Vec_Wrd_t * p )
p->pArray[k++] = p->pArray[i];
p->nSize = k;
}
+static inline Vec_Wrd_t * Vec_WrdUniqifyHash( Vec_Wrd_t * vData, int nWordSize )
+{
+ Vec_Int_t * vResInt;
+ Vec_Int_t * vDataInt = (Vec_Int_t *)vData;
+ vDataInt->nSize *= 2;
+ vDataInt->nCap *= 2;
+ vResInt = Vec_IntUniqifyHash( vDataInt, 2 * nWordSize );
+ vDataInt->nSize /= 2;
+ vDataInt->nCap /= 2;
+ vResInt->nSize /= 2;
+ vResInt->nCap /= 2;
+ return (Vec_Wrd_t *)vResInt;
+}
/**Function*************************************************************