1 /**CFile****************************************************************
2
3 FileName [hashInt.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__hashInt_h
22 #define ABC__misc__hash__hashInt_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_Int_t_ Hash_Int_t;
46 typedef struct Hash_Int_Entry_t_ Hash_Int_Entry_t;
47
48 struct Hash_Int_Entry_t_
49 {
50 int key;
51 int data;
52 struct Hash_Int_Entry_t_ * pNext;
53 };
54
55 struct Hash_Int_t_
56 {
57 int nSize;
58 int nBins;
59 int (* fHash)(int key, int nBins);
60 Hash_Int_Entry_t ** pArray;
61 };
62
63
64
65 ////////////////////////////////////////////////////////////////////////
66 /// MACRO DEFINITIONS ///
67 ////////////////////////////////////////////////////////////////////////
68
69 #define Hash_IntForEachEntry( 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_IntAlloc(int nBins)88 static inline Hash_Int_t * Hash_IntAlloc( int nBins )
89 {
90 Hash_Int_t * p;
91 int i;
92 assert(nBins > 0);
93 p = ABC_ALLOC( Hash_Int_t, 1);
94 p->nBins = nBins;
95 p->fHash = Hash_DefaultHashFunc;
96 p->nSize = 0;
97 p->pArray = ABC_ALLOC( Hash_Int_Entry_t *, nBins+1 );
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_IntExists(Hash_Int_t * p,int key)115 static inline int Hash_IntExists( Hash_Int_t *p, int key)
116 {
117 int bin;
118 Hash_Int_Entry_t *pEntry, **pLast;
119
120 // find the bin where this key would live
121 bin = (*(p->fHash))(key, p->nBins);
122
123 // search for key
124 pLast = &(p->pArray[bin]);
125 pEntry = p->pArray[bin];
126 while(pEntry) {
127 if (pEntry->key == key) {
128 return 1;
129 }
130 pLast = &(pEntry->pNext);
131 pEntry = pEntry->pNext;
132 }
133
134 return 0;
135 }
136
137 /**Function*************************************************************
138
139 Synopsis [Finds or creates an entry with a key and writes value.]
140
141 Description []
142
143 SideEffects []
144
145 SeeAlso []
146
147 ***********************************************************************/
Hash_IntWriteEntry(Hash_Int_t * p,int key,int data)148 static inline void Hash_IntWriteEntry( Hash_Int_t *p, int key, int data )
149 {
150 int bin;
151 Hash_Int_Entry_t *pEntry, **pLast;
152
153 // find the bin where this key would live
154 bin = (*(p->fHash))(key, p->nBins);
155
156 // search for key
157 pLast = &(p->pArray[bin]);
158 pEntry = p->pArray[bin];
159 while(pEntry) {
160 if (pEntry->key == key) {
161 pEntry->data = data;
162 return;
163 }
164 pLast = &(pEntry->pNext);
165 pEntry = pEntry->pNext;
166 }
167
168 // this key does not currently exist
169 // create a new entry and add to bin
170 p->nSize++;
171 (*pLast) = pEntry = ABC_ALLOC( Hash_Int_Entry_t, 1 );
172 pEntry->pNext = NULL;
173 pEntry->key = key;
174 pEntry->data = data;
175
176 return;
177 }
178
179
180 /**Function*************************************************************
181
182 Synopsis [Finds or creates an entry with a key.]
183
184 Description [fCreate specifies whether new entries will be created.]
185
186 SideEffects []
187
188 SeeAlso []
189
190 ***********************************************************************/
Hash_IntEntry(Hash_Int_t * p,int key,int fCreate)191 static inline int Hash_IntEntry( Hash_Int_t *p, int key, int fCreate )
192 {
193 int bin;
194 Hash_Int_Entry_t *pEntry, **pLast;
195
196 // find the bin where this key would live
197 bin = (*(p->fHash))(key, p->nBins);
198
199 // search for key
200 pLast = &(p->pArray[bin]);
201 pEntry = p->pArray[bin];
202 while(pEntry) {
203 if (pEntry->key == key)
204 return pEntry->data;
205 pLast = &(pEntry->pNext);
206 pEntry = pEntry->pNext;
207 }
208
209 // this key does not currently exist
210 if (fCreate) {
211 // create a new entry and add to bin
212 p->nSize++;
213 (*pLast) = pEntry = ABC_ALLOC( Hash_Int_Entry_t, 1 );
214 pEntry->pNext = NULL;
215 pEntry->key = key;
216 pEntry->data = 0;
217 return pEntry->data;
218 }
219
220 return 0;
221 }
222
223
224 /**Function*************************************************************
225
226 Synopsis [Finds or creates an entry with a key and returns the pointer to it.]
227
228 Description []
229
230 SideEffects []
231
232 SeeAlso []
233
234 ***********************************************************************/
Hash_IntEntryPtr(Hash_Int_t * p,int key)235 static inline int* Hash_IntEntryPtr( Hash_Int_t *p, int key )
236 {
237 int bin;
238 Hash_Int_Entry_t *pEntry, **pLast;
239
240 // find the bin where this key would live
241 bin = (*(p->fHash))(key, p->nBins);
242
243 // search for key
244 pLast = &(p->pArray[bin]);
245 pEntry = p->pArray[bin];
246 while(pEntry) {
247 if (pEntry->key == key)
248 return &(pEntry->data);
249 pLast = &(pEntry->pNext);
250 pEntry = pEntry->pNext;
251 }
252
253 // this key does not currently exist
254 // create a new entry and add to bin
255 p->nSize++;
256 (*pLast) = pEntry = ABC_ALLOC( Hash_Int_Entry_t, 1 );
257 pEntry->pNext = NULL;
258 pEntry->key = key;
259 pEntry->data = 0;
260
261 return &(pEntry->data);
262 }
263
264 /**Function*************************************************************
265
266 Synopsis [Frees the hash.]
267
268 Description []
269
270 SideEffects []
271
272 SeeAlso []
273
274 ***********************************************************************/
Hash_IntFree(Hash_Int_t * p)275 static inline void Hash_IntFree( Hash_Int_t *p ) {
276 int bin;
277 Hash_Int_Entry_t *pEntry, *pTemp;
278
279 // free bins
280 for(bin = 0; bin < p->nBins; bin++) {
281 pEntry = p->pArray[bin];
282 while(pEntry) {
283 pTemp = pEntry;
284 pEntry = pEntry->pNext;
285 ABC_FREE( pTemp );
286 }
287 }
288
289 // free hash
290 ABC_FREE( p->pArray );
291 ABC_FREE( p );
292 }
293
294 ////////////////////////////////////////////////////////////////////////
295 /// END OF FILE ///
296 ////////////////////////////////////////////////////////////////////////
297
298
299
300 ABC_NAMESPACE_HEADER_END
301
302 #endif
303