1 /**CFile****************************************************************
2
3 FileName [vecHash.h]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Resizable arrays.]
8
9 Synopsis [Hashing integer pairs/triples into an integer.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: vecHash.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #ifndef ABC__misc__vec__vecHash_h
22 #define ABC__misc__vec__vecHash_h
23
24
25 ////////////////////////////////////////////////////////////////////////
26 /// INCLUDES ///
27 ////////////////////////////////////////////////////////////////////////
28
29 #include <stdio.h>
30
31 ABC_NAMESPACE_HEADER_START
32
33
34 ////////////////////////////////////////////////////////////////////////
35 /// PARAMETERS ///
36 ////////////////////////////////////////////////////////////////////////
37
38 ////////////////////////////////////////////////////////////////////////
39 /// BASIC TYPES ///
40 ////////////////////////////////////////////////////////////////////////
41
42 typedef struct Hash_IntObj_t_ Hash_IntObj_t;
43 struct Hash_IntObj_t_
44 {
45 int iData0;
46 int iData1;
47 int iData2;
48 int iNext;
49 };
50
51 typedef struct Hash_IntMan_t_ Hash_IntMan_t;
52 struct Hash_IntMan_t_
53 {
54 Vec_Int_t * vTable; // hash table
55 Vec_Int_t * vObjs; // hash objects
56 int nRefs; // reference counter for the manager
57 };
58
59 ////////////////////////////////////////////////////////////////////////
60 /// MACRO DEFINITIONS ///
61 ////////////////////////////////////////////////////////////////////////
62
Hash_IntObj(Hash_IntMan_t * p,int i)63 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; }
Hash_IntObjData0(Hash_IntMan_t * p,int i)64 static inline int Hash_IntObjData0( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData0; }
Hash_IntObjData1(Hash_IntMan_t * p,int i)65 static inline int Hash_IntObjData1( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData1; }
Hash_IntObjData2(Hash_IntMan_t * p,int i)66 static inline int Hash_IntObjData2( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData2; }
67
Hash_Int2ObjInc(Hash_IntMan_t * p,int i)68 static inline int Hash_Int2ObjInc( Hash_IntMan_t * p, int i ) { return Hash_IntObj(p, i)->iData2++; }
Hash_Int2ObjDec(Hash_IntMan_t * p,int i)69 static inline int Hash_Int2ObjDec( Hash_IntMan_t * p, int i ) { return --Hash_IntObj(p, i)->iData2; }
Hash_Int2ObjSetData2(Hash_IntMan_t * p,int i,int d)70 static inline void Hash_Int2ObjSetData2( Hash_IntMan_t * p, int i, int d ) { Hash_IntObj(p, i)->iData2 = d; }
71
72 ////////////////////////////////////////////////////////////////////////
73 /// FUNCTION DEFINITIONS ///
74 ////////////////////////////////////////////////////////////////////////
75
76 /**Function*************************************************************
77
78 Synopsis [Hashes pairs of intergers.]
79
80 Description []
81
82 SideEffects []
83
84 SeeAlso []
85
86 ***********************************************************************/
Hash_IntManStart(int nSize)87 static inline Hash_IntMan_t * Hash_IntManStart( int nSize )
88 {
89 Hash_IntMan_t * p; nSize += 100;
90 p = ABC_CALLOC( Hash_IntMan_t, 1 );
91 p->vTable = Vec_IntStart( Abc_PrimeCudd(nSize) );
92 p->vObjs = Vec_IntAlloc( 4*nSize );
93 Vec_IntFill( p->vObjs, 4, 0 );
94 p->nRefs = 1;
95 return p;
96 }
Hash_IntManStop(Hash_IntMan_t * p)97 static inline void Hash_IntManStop( Hash_IntMan_t * p )
98 {
99 Vec_IntFree( p->vObjs );
100 Vec_IntFree( p->vTable );
101 ABC_FREE( p );
102 }
Hash_IntManRef(Hash_IntMan_t * p)103 static inline Hash_IntMan_t * Hash_IntManRef( Hash_IntMan_t * p )
104 {
105 p->nRefs++;
106 return p;
107 }
Hash_IntManDeref(Hash_IntMan_t * p)108 static inline void Hash_IntManDeref( Hash_IntMan_t * p )
109 {
110 if ( p == NULL )
111 return;
112 if ( --p->nRefs == 0 )
113 Hash_IntManStop( p );
114 }
Hash_IntManEntryNum(Hash_IntMan_t * p)115 static inline int Hash_IntManEntryNum( Hash_IntMan_t * p )
116 {
117 return Vec_IntSize(p->vObjs)/4 - 1;
118 }
Hash_IntManProfile(Hash_IntMan_t * p)119 static inline void Hash_IntManProfile( Hash_IntMan_t * p )
120 {
121 Hash_IntObj_t * pObj;
122 int i, Count, Entry;
123 Vec_IntForEachEntry( p->vTable, Entry, i )
124 {
125 Count = 0;
126 for ( pObj = Hash_IntObj( p, Entry ); pObj; pObj = Hash_IntObj( p, pObj->iNext ) )
127 Count++;
128 printf( "%d ", Count );
129 }
130 printf( "\n" );
131 }
132
133 /**Function*************************************************************
134
135 Synopsis []
136
137 Description []
138
139 SideEffects []
140
141 SeeAlso []
142
143 ***********************************************************************/
Hash_Int2ManHash(int iData0,int iData1,int nTableSize)144 static inline int Hash_Int2ManHash( int iData0, int iData1, int nTableSize )
145 {
146 return (4177 * (unsigned)iData0 + 7873 * (unsigned)iData1) % (unsigned)nTableSize;
147 }
Hash_Int2ManLookup(Hash_IntMan_t * p,int iData0,int iData1)148 static inline int * Hash_Int2ManLookup( Hash_IntMan_t * p, int iData0, int iData1 )
149 {
150 Hash_IntObj_t * pObj;
151 int * pPlace = Vec_IntEntryP( p->vTable, Hash_Int2ManHash(iData0, iData1, Vec_IntSize(p->vTable)) );
152 for ( ; (pObj = Hash_IntObj(p, *pPlace)); pPlace = &pObj->iNext )
153 if ( pObj->iData0 == iData0 && pObj->iData1 == iData1 )
154 return pPlace;
155 assert( *pPlace == 0 );
156 return pPlace;
157 }
Hash_Int2ManInsert(Hash_IntMan_t * p,int iData0,int iData1,int iData2)158 static inline int Hash_Int2ManInsert( Hash_IntMan_t * p, int iData0, int iData1, int iData2 )
159 {
160 Hash_IntObj_t * pObj;
161 int i, nObjs, * pPlace;
162 nObjs = Vec_IntSize(p->vObjs)/4;
163 if ( nObjs > Vec_IntSize(p->vTable) )
164 {
165 // printf( "Resizing...\n" );
166 Vec_IntFill( p->vTable, Abc_PrimeCudd(2*Vec_IntSize(p->vTable)), 0 );
167 for ( i = 1; i < nObjs; i++ )
168 {
169 pObj = Hash_IntObj( p, i );
170 pObj->iNext = 0;
171 pPlace = Hash_Int2ManLookup( p, pObj->iData0, pObj->iData1 );
172 assert( *pPlace == 0 );
173 *pPlace = i;
174 }
175 }
176 pPlace = Hash_Int2ManLookup( p, iData0, iData1 );
177 if ( *pPlace )
178 return *pPlace;
179 *pPlace = nObjs;
180 Vec_IntPush( p->vObjs, iData0 );
181 Vec_IntPush( p->vObjs, iData1 );
182 Vec_IntPush( p->vObjs, iData2 );
183 Vec_IntPush( p->vObjs, 0 );
184 return nObjs;
185 }
186
187 /**Function*************************************************************
188
189 Synopsis [Hashes triples of intergers.]
190
191 Description []
192
193 SideEffects []
194
195 SeeAlso []
196
197 ***********************************************************************/
Hsh_Int3ManHash(int iData0,int iData1,int iData2,int nTableSize)198 static inline int Hsh_Int3ManHash( int iData0, int iData1, int iData2, int nTableSize )
199 {
200 return (4177 * (unsigned)iData0 + 7873 * (unsigned)iData1 + 1699 * (unsigned)iData2) % (unsigned)nTableSize;
201 }
Hsh_Int3ManLookup(Hash_IntMan_t * p,int iData0,int iData1,int iData2)202 static inline int * Hsh_Int3ManLookup( Hash_IntMan_t * p, int iData0, int iData1, int iData2 )
203 {
204 Hash_IntObj_t * pObj;
205 int * pPlace = Vec_IntEntryP( p->vTable, Hsh_Int3ManHash(iData0, iData1, iData2, Vec_IntSize(p->vTable)) );
206 for ( ; (pObj = Hash_IntObj(p, *pPlace)); pPlace = &pObj->iNext )
207 if ( pObj->iData0 == iData0 && pObj->iData1 == iData1 && pObj->iData2 == iData2 )
208 return pPlace;
209 assert( *pPlace == 0 );
210 return pPlace;
211 }
Hsh_Int3ManInsert(Hash_IntMan_t * p,int iData0,int iData1,int iData2)212 static inline int Hsh_Int3ManInsert( Hash_IntMan_t * p, int iData0, int iData1, int iData2 )
213 {
214 Hash_IntObj_t * pObj;
215 int i, nObjs, * pPlace;
216 nObjs = Vec_IntSize(p->vObjs)/4;
217 if ( nObjs > Vec_IntSize(p->vTable) )
218 {
219 // printf( "Resizing...\n" );
220 Vec_IntFill( p->vTable, Abc_PrimeCudd(2*Vec_IntSize(p->vTable)), 0 );
221 for ( i = 1; i < nObjs; i++ )
222 {
223 pObj = Hash_IntObj( p, i );
224 pObj->iNext = 0;
225 pPlace = Hsh_Int3ManLookup( p, pObj->iData0, pObj->iData1, pObj->iData2 );
226 assert( *pPlace == 0 );
227 *pPlace = i;
228 }
229 }
230 pPlace = Hsh_Int3ManLookup( p, iData0, iData1, iData2 );
231 if ( *pPlace )
232 return *pPlace;
233 *pPlace = nObjs;
234 Vec_IntPush( p->vObjs, iData0 );
235 Vec_IntPush( p->vObjs, iData1 );
236 Vec_IntPush( p->vObjs, iData2 );
237 Vec_IntPush( p->vObjs, 0 );
238 return nObjs;
239 }
240
241 /**Function*************************************************************
242
243 Synopsis [Test procedure.]
244
245 Description []
246
247 SideEffects []
248
249 SeeAlso []
250
251 ***********************************************************************/
Hash_IntManHashArrayTest()252 static inline void Hash_IntManHashArrayTest()
253 {
254 Hash_IntMan_t * p;
255 int RetValue;
256
257 p = Hash_IntManStart( 10 );
258
259 RetValue = Hash_Int2ManInsert( p, 10, 11, 12 );
260 assert( RetValue );
261
262 RetValue = Hash_Int2ManInsert( p, 20, 21, 22 );
263 assert( RetValue );
264
265 RetValue = Hash_Int2ManInsert( p, 10, 11, 12 );
266 assert( !RetValue );
267
268 Hash_IntManStop( p );
269 }
270
271
272
273 ////////////////////////////////////////////////////////////////////////
274 /// END OF FILE ///
275 ////////////////////////////////////////////////////////////////////////
276
277 ABC_NAMESPACE_HEADER_END
278
279 #endif
280
281