1 /**CFile****************************************************************
2
3 FileName [hashFlt.h]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Hash maps.]
8
9 Synopsis [Hash maps.]
10
11 Author [Aaron P. Hurst]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 16, 2006.]
16
17 Revision [$Id: vecInt.h,v 1.00 2005/06/20 00:00:00 ahurst Exp $]
18
19 ***********************************************************************/
20
21 #ifndef ABC__misc__hash__hashPtr_h
22 #define ABC__misc__hash__hashPtr_h
23
24
25 ////////////////////////////////////////////////////////////////////////
26 /// INCLUDES ///
27 ////////////////////////////////////////////////////////////////////////
28
29 #include <stdio.h>
30 #include "misc/extra/extra.h"
31
32 ABC_NAMESPACE_HEADER_START
33
34
35 extern int Hash_DefaultHashFunc(int key, int nBins);
36
37 ////////////////////////////////////////////////////////////////////////
38 /// PARAMETERS ///
39 ////////////////////////////////////////////////////////////////////////
40
41 ////////////////////////////////////////////////////////////////////////
42 /// BASIC TYPES ///
43 ////////////////////////////////////////////////////////////////////////
44
45 typedef struct Hash_Ptr_t_ Hash_Ptr_t;
46 typedef struct Hash_Ptr_Entry_t_ Hash_Ptr_Entry_t;
47
48 struct Hash_Ptr_Entry_t_
49 {
50 int key;
51 void * data;
52 struct Hash_Ptr_Entry_t_ * pNext;
53 };
54
55 struct Hash_Ptr_t_
56 {
57 int nSize;
58 int nBins;
59 int (* fHash)(int key, int nBins);
60 Hash_Ptr_Entry_t ** pArray;
61 };
62
63
64
65 ////////////////////////////////////////////////////////////////////////
66 /// MACRO DEFINITIONS ///
67 ////////////////////////////////////////////////////////////////////////
68
69 #define Hash_PtrForEachEntry( pHash, pEntry, bin ) \
70 for(bin=-1, pEntry=NULL; bin < pHash->nBins; (!pEntry)?(pEntry=pHash->pArray[++bin]):(pEntry=pEntry->pNext)) \
71 if (pEntry)
72
73 ////////////////////////////////////////////////////////////////////////
74 /// FUNCTION DEFINITIONS ///
75 ////////////////////////////////////////////////////////////////////////
76
77 /**Function*************************************************************
78
79 Synopsis [Allocates a hash map with the given number of bins.]
80
81 Description []
82
83 SideEffects []
84
85 SeeAlso []
86
87 ***********************************************************************/
Hash_PtrAlloc(int nBins)88 static inline Hash_Ptr_t * Hash_PtrAlloc( int nBins )
89 {
90 Hash_Ptr_t * p;
91 int i;
92 assert(nBins > 0);
93 p = ABC_ALLOC( Hash_Ptr_t, 1);
94 p->nBins = nBins;
95 p->fHash = Hash_DefaultHashFunc;
96 p->nSize = 0;
97 p->pArray = ABC_ALLOC( Hash_Ptr_Entry_t *, nBins );
98 for(i=0; i<nBins; i++)
99 p->pArray[i] = NULL;
100
101 return p;
102 }
103
104 /**Function*************************************************************
105
106 Synopsis [Returns 1 if a key already exists.]
107
108 Description []
109
110 SideEffects []
111
112 SeeAlso []
113
114 ***********************************************************************/
Hash_PtrExists(Hash_Ptr_t * p,int key)115 static inline int Hash_PtrExists( Hash_Ptr_t *p, int key )
116 {
117 int bin;
118 Hash_Ptr_Entry_t *pEntry;
119
120 // find the bin where this key would live
121 bin = (*(p->fHash))(key, p->nBins);
122
123 // search for key
124 pEntry = p->pArray[bin];
125 while(pEntry) {
126 if (pEntry->key == key) {
127 return 1;
128 }
129 pEntry = pEntry->pNext;
130 }
131
132 return 0;
133 }
134
135 /**Function*************************************************************
136
137 Synopsis [Finds or creates an entry with a key and writes value.]
138
139 Description []
140
141 SideEffects []
142
143 SeeAlso []
144
145 ***********************************************************************/
Hash_PtrWriteEntry(Hash_Ptr_t * p,int key,void * data)146 static inline void Hash_PtrWriteEntry( Hash_Ptr_t *p, int key, void * data )
147 {
148 int bin;
149 Hash_Ptr_Entry_t *pEntry, **pLast;
150
151 // find the bin where this key would live
152 bin = (*(p->fHash))(key, p->nBins);
153
154 // search for key
155 pLast = &(p->pArray[bin]);
156 pEntry = p->pArray[bin];
157 while(pEntry) {
158 if (pEntry->key == key) {
159 pEntry->data = data;
160 return;
161 }
162 pLast = &(pEntry->pNext);
163 pEntry = pEntry->pNext;
164 }
165
166 // this key does not currently exist
167 // create a new entry and add to bin
168 p->nSize++;
169 (*pLast) = pEntry = ABC_ALLOC( Hash_Ptr_Entry_t, 1 );
170 pEntry->pNext = NULL;
171 pEntry->key = key;
172 pEntry->data = data;
173
174 return;
175 }
176
177
178 /**Function*************************************************************
179
180 Synopsis [Finds or creates an entry with a key.]
181
182 Description [fCreate specifies whether a new entry should be created.]
183
184 SideEffects []
185
186 SeeAlso []
187
188 ***********************************************************************/
Hash_PtrEntry(Hash_Ptr_t * p,int key,int fCreate)189 static inline void * Hash_PtrEntry( Hash_Ptr_t *p, int key, int fCreate )
190 {
191 int bin;
192 Hash_Ptr_Entry_t *pEntry, **pLast;
193
194 // find the bin where this key would live
195 bin = (*(p->fHash))(key, p->nBins);
196
197 // search for key
198 pLast = &(p->pArray[bin]);
199 pEntry = p->pArray[bin];
200 while(pEntry) {
201 if (pEntry->key == key)
202 return pEntry->data;
203 pLast = &(pEntry->pNext);
204 pEntry = pEntry->pNext;
205 }
206
207 // this key does not currently exist
208 if (fCreate) {
209 // create a new entry and add to bin
210 p->nSize++;
211 (*pLast) = pEntry = ABC_ALLOC( Hash_Ptr_Entry_t, 1 );
212 pEntry->pNext = NULL;
213 pEntry->key = key;
214 pEntry->data = NULL;
215 return pEntry->data;
216 }
217
218 return NULL;
219 }
220
221
222 /**Function*************************************************************
223
224 Synopsis [Finds or creates an entry with a key and returns the pointer to it.]
225
226 Description []
227
228 SideEffects []
229
230 SeeAlso []
231
232 ***********************************************************************/
Hash_PtrEntryPtr(Hash_Ptr_t * p,int key)233 static inline void** Hash_PtrEntryPtr( Hash_Ptr_t *p, int key )
234 {
235 int bin;
236 Hash_Ptr_Entry_t *pEntry, **pLast;
237
238 // find the bin where this key would live
239 bin = (*(p->fHash))(key, p->nBins);
240
241 // search for key
242 pLast = &(p->pArray[bin]);
243 pEntry = p->pArray[bin];
244 while(pEntry) {
245 if (pEntry->key == key)
246 return &(pEntry->data);
247 pLast = &(pEntry->pNext);
248 pEntry = pEntry->pNext;
249 }
250
251 // this key does not currently exist
252 // create a new entry and add to bin
253 p->nSize++;
254 (*pLast) = pEntry = ABC_ALLOC( Hash_Ptr_Entry_t, 1 );
255 pEntry->pNext = NULL;
256 pEntry->key = key;
257 pEntry->data = NULL;
258
259 return &(pEntry->data);
260 }
261
262 /**Function*************************************************************
263
264 Synopsis [Deletes an entry.]
265
266 Description [Returns data, if there was any.]
267
268 SideEffects []
269
270 SeeAlso []
271
272 ***********************************************************************/
Hash_PtrRemove(Hash_Ptr_t * p,int key)273 static inline void* Hash_PtrRemove( Hash_Ptr_t *p, int key )
274 {
275 int bin;
276 void * data;
277 Hash_Ptr_Entry_t *pEntry, **pLast;
278
279 // find the bin where this key would live
280 bin = (*(p->fHash))(key, p->nBins);
281
282 // search for key
283 pLast = &(p->pArray[bin]);
284 pEntry = p->pArray[bin];
285 while(pEntry) {
286 if (pEntry->key == key) {
287 p->nSize--;
288 data = pEntry->data;
289 *pLast = pEntry->pNext;
290 return data;
291 }
292 pLast = &(pEntry->pNext);
293 pEntry = pEntry->pNext;
294 }
295
296 // could not find key
297 return NULL;
298 }
299
300 /**Function*************************************************************
301
302 Synopsis [Frees the hash.]
303
304 Description []
305
306 SideEffects []
307
308 SeeAlso []
309
310 ***********************************************************************/
Hash_PtrFree(Hash_Ptr_t * p)311 static inline void Hash_PtrFree( Hash_Ptr_t *p )
312 {
313 int bin;
314 Hash_Ptr_Entry_t *pEntry, *pTemp;
315
316 // free bins
317 for(bin = 0; bin < p->nBins; bin++) {
318 pEntry = p->pArray[bin];
319 while(pEntry) {
320 pTemp = pEntry;
321 pEntry = pEntry->pNext;
322 ABC_FREE( pTemp );
323 }
324 }
325
326 // free hash
327 ABC_FREE( p->pArray );
328 ABC_FREE( p );
329 }
330
331 ////////////////////////////////////////////////////////////////////////
332 /// END OF FILE ///
333 ////////////////////////////////////////////////////////////////////////
334
335
336
337 ABC_NAMESPACE_HEADER_END
338
339 #endif
340