summaryrefslogtreecommitdiffstats
path: root/src/misc/vec/vecHash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc/vec/vecHash.h')
-rw-r--r--src/misc/vec/vecHash.h253
1 files changed, 253 insertions, 0 deletions
diff --git a/src/misc/vec/vecHash.h b/src/misc/vec/vecHash.h
new file mode 100644
index 00000000..e695f154
--- /dev/null
+++ b/src/misc/vec/vecHash.h
@@ -0,0 +1,253 @@
+/**CFile****************************************************************
+
+ FileName [vecHash.h]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Resizable arrays.]
+
+ Synopsis [Hashing integer pairs/triples into an integer.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: vecHash.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#ifndef ABC__misc__vec__vecHash_h
+#define ABC__misc__vec__vecHash_h
+
+
+////////////////////////////////////////////////////////////////////////
+/// INCLUDES ///
+////////////////////////////////////////////////////////////////////////
+
+#include <stdio.h>
+
+ABC_NAMESPACE_HEADER_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// PARAMETERS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// BASIC TYPES ///
+////////////////////////////////////////////////////////////////////////
+
+typedef struct Hash_IntObj_t_ Hash_IntObj_t;
+struct Hash_IntObj_t_
+{
+ int iData0;
+ int iData1;
+ int iData2;
+ int iNext;
+};
+
+typedef struct Hash_IntMan_t_ Hash_IntMan_t;
+struct Hash_IntMan_t_
+{
+ Vec_Int_t * vTable; // hash table
+ Vec_Int_t * vObjs; // hash objects
+};
+
+////////////////////////////////////////////////////////////////////////
+/// MACRO DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static inline Hash_IntObj_t * Hash_IntObj( Hash_IntMan_t * p, int i ) { return i ? (Hash_IntObj_t *)Vec_IntEntryP(p->vObjs, 4*i) : NULL; }
+static inline int Hash_IntObjData0( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData0; }
+static inline int Hash_IntObjData1( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData1; }
+static inline int Hash_IntObjData2( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData2; }
+
+static inline int Hash_Int2ObjInc( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData2++; }
+static inline int Hash_Int2ObjDec( Hash_IntMan_t * p, int i ) { return --Hash_IntObj(p, i)->iData2; }
+static inline void Hash_Int2ObjSetData2( Hash_IntMan_t * p, int i, int d ) { Hash_IntObj(p, i)->iData2 = d; }
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Hashing data entries composed of nSize integers.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline Hash_IntMan_t * Hash_IntManStart( int nSize )
+{
+ Hash_IntMan_t * p; nSize += 100;
+ p = ABC_CALLOC( Hash_IntMan_t, 1 );
+ p->vTable = Vec_IntStart( Abc_PrimeCudd(nSize) );
+ p->vObjs = Vec_IntAlloc( 4*nSize );
+ Vec_IntFill( p->vObjs, 4, 0 );
+ return p;
+}
+static inline void Hash_IntManStop( Hash_IntMan_t * p )
+{
+ Vec_IntFree( p->vObjs );
+ Vec_IntFree( p->vTable );
+ ABC_FREE( p );
+}
+static inline int Hash_IntManEntryNum( Hash_IntMan_t * p )
+{
+ return Vec_IntSize(p->vObjs)/4 - 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int Hash_Int2ManHash( int iData0, int iData1, int nTableSize )
+{
+ return (4177 * (unsigned)iData0 + 7873 * (unsigned)iData1) % (unsigned)nTableSize;
+}
+static inline int * Hash_Int2ManLookup( Hash_IntMan_t * p, int iData0, int iData1 )
+{
+ Hash_IntObj_t * pObj;
+ int * pPlace = Vec_IntEntryP( p->vTable, Hash_Int2ManHash(iData0, iData1, Vec_IntSize(p->vTable)) );
+ for ( ; (pObj = Hash_IntObj(p, *pPlace)); pPlace = &pObj->iNext )
+ if ( pObj->iData0 == iData0 && pObj->iData1 == iData1 )
+ return pPlace;
+ assert( *pPlace == 0 );
+ return pPlace;
+}
+static inline int Hash_Int2ManInsert( Hash_IntMan_t * p, int iData0, int iData1, int iData2 )
+{
+ Hash_IntObj_t * pObj;
+ int i, nObjs, * pPlace;
+ nObjs = Vec_IntSize(p->vObjs)/4;
+ if ( nObjs > Vec_IntSize(p->vTable) )
+ {
+// printf( "Resizing...\n" );
+ Vec_IntFill( p->vTable, Abc_PrimeCudd(2*Vec_IntSize(p->vTable)), 0 );
+ for ( i = 1; i < nObjs; i++ )
+ {
+ pObj = Hash_IntObj( p, i );
+ pObj->iNext = 0;
+ pPlace = Hash_Int2ManLookup( p, pObj->iData0, pObj->iData1 );
+ assert( *pPlace == 0 );
+ *pPlace = i;
+ }
+ }
+ pPlace = Hash_Int2ManLookup( p, iData0, iData1 );
+ if ( *pPlace )
+ return *pPlace;
+ *pPlace = nObjs;
+ Vec_IntPush( p->vObjs, iData0 );
+ Vec_IntPush( p->vObjs, iData1 );
+ Vec_IntPush( p->vObjs, iData2 );
+ Vec_IntPush( p->vObjs, 0 );
+ return nObjs;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int Hsh_Int3ManHash( int iData0, int iData1, int iData2, int nTableSize )
+{
+ return (4177 * (unsigned)iData0 + 7873 * (unsigned)iData1 + 1699 * (unsigned)iData2) % (unsigned)nTableSize;
+}
+static inline int * Hsh_Int3ManLookup( Hash_IntMan_t * p, int iData0, int iData1, int iData2 )
+{
+ Hash_IntObj_t * pObj;
+ int * pPlace = Vec_IntEntryP( p->vTable, Hsh_Int3ManHash(iData0, iData1, iData2, Vec_IntSize(p->vTable)) );
+ for ( ; (pObj = Hash_IntObj(p, *pPlace)); pPlace = &pObj->iNext )
+ if ( pObj->iData0 == iData0 && pObj->iData1 == iData1 && pObj->iData2 == iData2 )
+ return pPlace;
+ assert( *pPlace == 0 );
+ return pPlace;
+}
+static inline int Hsh_Int3ManInsert( Hash_IntMan_t * p, int iData0, int iData1, int iData2 )
+{
+ Hash_IntObj_t * pObj;
+ int i, nObjs, * pPlace;
+ nObjs = Vec_IntSize(p->vObjs)/4;
+ if ( nObjs > Vec_IntSize(p->vTable) )
+ {
+// printf( "Resizing...\n" );
+ Vec_IntFill( p->vTable, Abc_PrimeCudd(2*Vec_IntSize(p->vTable)), 0 );
+ for ( i = 1; i < nObjs; i++ )
+ {
+ pObj = Hash_IntObj( p, i );
+ pObj->iNext = 0;
+ pPlace = Hsh_Int3ManLookup( p, pObj->iData0, pObj->iData1, pObj->iData2 );
+ assert( *pPlace == 0 );
+ *pPlace = i;
+ }
+ }
+ pPlace = Hsh_Int3ManLookup( p, iData0, iData1, iData2 );
+ if ( *pPlace )
+ return *pPlace;
+ *pPlace = nObjs;
+ Vec_IntPush( p->vObjs, iData0 );
+ Vec_IntPush( p->vObjs, iData1 );
+ Vec_IntPush( p->vObjs, iData2 );
+ Vec_IntPush( p->vObjs, 0 );
+ return nObjs;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Test procedure.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Hash_IntManHashArrayTest()
+{
+ Hash_IntMan_t * p;
+ int RetValue;
+
+ p = Hash_IntManStart( 10 );
+
+ RetValue = Hash_Int2ManInsert( p, 10, 11, 12 );
+ assert( RetValue );
+
+ RetValue = Hash_Int2ManInsert( p, 20, 21, 22 );
+ assert( RetValue );
+
+ RetValue = Hash_Int2ManInsert( p, 10, 11, 12 );
+ assert( !RetValue );
+
+ Hash_IntManStop( p );
+}
+
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+ABC_NAMESPACE_HEADER_END
+
+#endif
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-09 19:44:00 +0000