1 /***************************************************************************
2
3 file : hash.cpp
4 created : Sat Dec 14 16:40:15 CET 2002
5 copyright : (C) 2002-2014 by Eric Espie, Bernhard Wymann
6 email : eric.espie@torcs.org
7 version : $Id: hash.cpp,v 1.4.2.4 2014/05/20 14:07:09 berniw Exp $
8
9 ***************************************************************************/
10
11 /***************************************************************************
12 * *
13 * This program is free software; you can redistribute it and/or modify *
14 * it under the terms of the GNU General Public License as published by *
15 * the Free Software Foundation; either version 2 of the License, or *
16 * (at your option) any later version. *
17 * *
18 ***************************************************************************/
19
20 /** @file
21 Hash API
22 @author Bernhard Wymann, Eric Espie
23 @version $Id: hash.cpp,v 1.4.2.4 2014/05/20 14:07:09 berniw Exp $
24 */
25
26 #include <tgf.h>
27
28 typedef struct HashElem
29 {
30 char *key;
31 int size;
32 const void *data;
33 GF_TAILQ_ENTRY(struct HashElem) link;
34 } tHashElem;
35
36 GF_TAILQ_HEAD(HashHead, tHashElem);
37
38 typedef struct HashHeader
39 {
40 int type;
41 int size;
42 int nbElem;
43 /* for table traversal */
44 int curIndex;
45 tHashElem *curElem;
46 tHashHead *hashHead;
47 } tHashHeader;
48
49
50 #define HASH_BYTE(x, y) (((y) + ((x) << 4) + ((x) >> 4)) * 11)
51 #define DEFAULT_SIZE 32
52
53
hash_str(tHashHeader * hash,const char * sstr)54 static unsigned int hash_str (tHashHeader *hash, const char *sstr)
55 {
56 const unsigned char *str = (const unsigned char *)sstr;
57 unsigned int val = 0;
58
59 if (!str) {
60 return 0;
61 }
62
63 /* Hash courtesy of the R5 hash in reiserfs modulo sign bits */
64 while (*str)
65 {
66 val = (val + (*str >> 4) + (*str << 4)) * 11;
67 str++;
68 }
69
70 return val % hash->size;
71 }
72
73
hash_buf(tHashHeader * hash,char * sdata,int len)74 static unsigned int hash_buf (tHashHeader *hash, char *sdata, int len)
75 {
76 unsigned int val = 0;
77 unsigned char *data = (unsigned char *)sdata;
78 int i;
79
80 if (!data) return 0;
81
82 /* Hash courtesy of the R5 hash in reiserfs modulo sign bits */
83 for (i = 0; i < len; i++)
84 val = (val + (data[i] >> 4) + (data[i] << 4)) * 11;
85
86 return val % hash->size;
87 }
88
89
90 /** Create a new hash table
91 * @ingroup hash
92 * @param type Type of key used (#GF_HASH_TYPE_STR or #GF_HASH_TYPE_BUF)
93 * @return Handle on new hash table
94 * <br>0 if Error
95 * @see GF_HASH_TYPE_STR
96 * @see GF_HASH_TYPE_BUF
97 */
GfHashCreate(int type)98 void *GfHashCreate(int type)
99 {
100 tHashHeader *curHeader;
101 int i;
102
103 curHeader = (tHashHeader*)malloc(sizeof(tHashHeader));
104 if (!curHeader) {
105 return NULL;
106 }
107
108 curHeader->type = type;
109 curHeader->size = DEFAULT_SIZE;
110 curHeader->nbElem = 0;
111 curHeader->curIndex = 0;
112 curHeader->curElem = NULL;
113 curHeader->hashHead = (tHashHead *)malloc(DEFAULT_SIZE * sizeof(tHashHead));
114 for (i = 0; i < DEFAULT_SIZE; i++) {
115 GF_TAILQ_INIT(&(curHeader->hashHead[i]));
116 }
117 return (void*)curHeader;
118 }
119
120
121 /** Double the size of the hash table */
gfIncreaseHash(tHashHeader * curHeader)122 static void gfIncreaseHash(tHashHeader *curHeader)
123 {
124 tHashHead *oldHashHead;
125 tHashElem *curElem;
126 int oldSize;
127 int hindex;
128 int i;
129
130 oldHashHead = curHeader->hashHead;
131 oldSize = curHeader->size;
132
133 curHeader->size *= 2;
134 curHeader->hashHead = (tHashHead *)malloc(curHeader->size * sizeof(tHashHead));
135 for (i = 0; i < curHeader->size; i++) {
136 GF_TAILQ_INIT(&(curHeader->hashHead[i]));
137 }
138
139 /* copy the elements */
140 for (i = 0; i < oldSize; i++) {
141 while ((curElem = GF_TAILQ_FIRST(&(oldHashHead[i]))) != NULL) {
142 /* remove from old list */
143 GF_TAILQ_REMOVE(&(oldHashHead[i]), curElem, link);
144 /* insert in new list */
145 switch (curHeader->type) {
146 case GF_HASH_TYPE_STR:
147 hindex = hash_str(curHeader, curElem->key);
148 break;
149 case GF_HASH_TYPE_BUF:
150 hindex = hash_buf(curHeader, curElem->key, curElem->size);
151 break;
152 default:
153 hindex = 0; /* for the compiler... */
154 break;
155 }
156 GF_TAILQ_INSERT_TAIL(&(curHeader->hashHead[hindex]), curElem, link);
157 }
158 }
159 free(oldHashHead);
160 }
161
162
163 /** Add an element with a string key to a hash table.
164 * @ingroup hash
165 * @param hash Current hash table handle
166 * @param key Key string to hash
167 * @param data User data
168 * @return 0 OK, 1 NOK
169 */
GfHashAddStr(void * hash,const char * key,const void * data)170 int GfHashAddStr(void *hash, const char *key, const void *data)
171 {
172 tHashHeader *curHeader = (tHashHeader *)hash;
173 tHashElem *newElem;
174 unsigned int index;
175
176 if (curHeader->type != GF_HASH_TYPE_STR) {
177 return 1;
178 }
179
180 if ((curHeader->nbElem + 1) > (2 * curHeader->size)) {
181 gfIncreaseHash(curHeader);
182 }
183
184 index = hash_str(curHeader, key);
185 newElem = (tHashElem*)malloc(sizeof(tHashElem));
186 if (!newElem) {
187 return 1;
188 }
189
190 newElem->key = strdup(key);
191 newElem->size = strlen(key) + 1;
192 newElem->data = data;
193 GF_TAILQ_INSERT_TAIL(&(curHeader->hashHead[index]), newElem, link);
194 curHeader->nbElem++;
195
196 return 0;
197 }
198
199
200 /** Remove a table element */
gfRemElem(tHashHead * hashHead,tHashElem * elem)201 static const void *gfRemElem(tHashHead *hashHead, tHashElem *elem)
202 {
203 const void *data;
204
205 data = elem->data;
206 free(elem->key);
207 GF_TAILQ_REMOVE(hashHead, elem, link);
208 free(elem);
209 return data;
210 }
211
212
213 /** Remove an element with a string key from a hash table.
214 * @ingroup hash
215 * @param hash Current hash table handle
216 * @param key Key string to hash
217 * @return User data or NULL if not found
218 */
GfHashRemStr(void * hash,char * key)219 const void *GfHashRemStr(void *hash, char *key)
220 {
221 tHashHeader *curHeader = (tHashHeader *)hash;
222 tHashElem *curElem;
223 unsigned int index;
224
225 index = hash_str(curHeader, key);
226 curElem = GF_TAILQ_FIRST(&(curHeader->hashHead[index]));
227 while (curElem) {
228 if (!strcmp(curElem->key, key)) {
229 curHeader->nbElem--;
230 return gfRemElem(&(curHeader->hashHead[index]), curElem);
231 }
232 curElem = GF_TAILQ_NEXT(curElem, link);
233 }
234
235 return NULL;
236 }
237
238
239 /** Get the user data associated with a string key.
240 * @ingroup hash
241 * @param hash Current hash table handle.
242 * @param key Key string to hash.
243 * @return User data or NULL if not found
244 */
GfHashGetStr(void * hash,const char * key)245 const void *GfHashGetStr(void *hash, const char *key)
246 {
247 tHashHeader *curHeader = (tHashHeader *)hash;
248 tHashElem *curElem;
249 unsigned int index;
250
251 index = hash_str(curHeader, key);
252 curElem = GF_TAILQ_FIRST(&(curHeader->hashHead[index]));
253 while (curElem) {
254 if (!strcmp(curElem->key, key)) {
255 return curElem->data;
256 }
257 curElem = GF_TAILQ_NEXT(curElem, link);
258 }
259
260 return NULL;
261 }
262
263
264 /** Add an element with a memory buffer key to a hash table.
265 * @ingroup hash
266 * @param hash Current hash table handle
267 * @param key Key buffer to hash
268 * @param sz Size of the buffer
269 * @param data User data
270 */
GfHashAddBuf(void * hash,char * key,size_t sz,void * data)271 void GfHashAddBuf(void *hash, char *key, size_t sz, void *data)
272 {
273 tHashHeader *curHeader = (tHashHeader *)hash;
274 tHashElem *newElem;
275 unsigned int index;
276
277 if (curHeader->type != GF_HASH_TYPE_BUF) {
278 return;
279 }
280
281 if ((curHeader->nbElem + 1) > (2 * curHeader->size)) {
282 gfIncreaseHash(curHeader);
283 }
284
285 index = hash_buf(curHeader, key, sz);
286 newElem = (tHashElem*)malloc(sizeof(tHashElem));
287 newElem->key = (char *)malloc(sz);
288 memcpy(newElem->key, key, sz);
289 newElem->size = sz;
290 newElem->data = data;
291 GF_TAILQ_INSERT_TAIL(&(curHeader->hashHead[index]), newElem, link);
292 curHeader->nbElem++;
293 }
294
295
296 /** Remove an element with a memory buffer key from a hash table.
297 * @ingroup hash
298 * @param hash Current hash table handle
299 * @param key Key buffer to hash
300 * @param sz Size of the buffer
301 * @return User data or NULL if not found
302 */
GfHashRemBuf(void * hash,char * key,size_t sz)303 const void *GfHashRemBuf(void *hash, char *key, size_t sz)
304 {
305 tHashHeader *curHeader = (tHashHeader *)hash;
306 tHashElem *curElem;
307 unsigned int index;
308
309 index = hash_buf(curHeader, key, sz);
310 curElem = GF_TAILQ_FIRST(&(curHeader->hashHead[index]));
311 while (curElem) {
312 if (!memcmp(curElem->key, key, sz)) {
313 curHeader->nbElem--;
314 return gfRemElem(&(curHeader->hashHead[index]), curElem);
315 }
316 curElem = GF_TAILQ_NEXT(curElem, link);
317 }
318
319 return NULL;
320 }
321
322
323 /** Get the user data associated with a memory buffer key.
324 * @ingroup hash
325 * @param hash Current hash table handle
326 * @param key Key buffer to hash
327 * @param sz Size of the buffer
328 * @return User data or NULL if not found
329 */
GfHashGetBuf(void * hash,char * key,size_t sz)330 const void *GfHashGetBuf(void *hash, char *key, size_t sz)
331 {
332 tHashHeader *curHeader = (tHashHeader *)hash;
333 tHashElem *curElem;
334 unsigned int index;
335
336 index = hash_buf(curHeader, key, sz);
337 curElem = GF_TAILQ_FIRST(&(curHeader->hashHead[index]));
338 while (curElem) {
339 if (!memcmp(curElem->key, key, sz)) {
340 return curElem->data;
341 }
342 curElem = GF_TAILQ_NEXT(curElem, link);
343 }
344
345 return NULL;
346 }
347
348 /** Release a hash table.
349 * @ingroup hash
350 * @param hash Current hash table handle
351 * @param hashFree Pointer on user function used to free the user data (NULL if not used)
352 */
GfHashRelease(void * hash,tfHashFree hashFree)353 void GfHashRelease(void *hash, tfHashFree hashFree)
354 {
355 tHashHeader *curHeader = (tHashHeader *)hash;
356 tHashElem *curElem;
357 const void *data;
358 int i;
359
360 for (i = 0; i < curHeader->size; i++) {
361 while ((curElem = GF_TAILQ_FIRST(&(curHeader->hashHead[i]))) != NULL) {
362 data = gfRemElem(&(curHeader->hashHead[i]), curElem);
363 if (hashFree) {
364 hashFree(data);
365 }
366 }
367 }
368
369 free(curHeader->hashHead);
370 free(curHeader);
371 }
372
373 /** Get the first user data of a hash table, this is used for table scans
374 * @ingroup hash
375 * @param hash Current hash table handle
376 * @return User data or NULL if empty
377 * @see GfHashGetNext
378 */
GfHashGetFirst(void * hash)379 const void * GfHashGetFirst(void *hash)
380 {
381 tHashHeader *curHeader = (tHashHeader *)hash;
382
383 curHeader->curIndex = -1;
384 curHeader->curElem = NULL;
385
386 return GfHashGetNext(hash);
387 }
388
389
390 /** Get the next user data of a hash table, this is used for table scans
391 * @ingroup hash
392 * @param hash Current hash table handle
393 * @return User data or NULL if we have reached the end
394 * @see GfHashGetFirst
395 */
GfHashGetNext(void * hash)396 const void *GfHashGetNext(void *hash)
397 {
398 tHashHeader *curHeader = (tHashHeader *)hash;
399
400 if (curHeader->curElem) {
401 curHeader->curElem = GF_TAILQ_NEXT(curHeader->curElem, link);
402 }
403
404 while (!curHeader->curElem) {
405 curHeader->curIndex++;
406 if (curHeader->curIndex == curHeader->size) {
407 return NULL;
408 }
409 curHeader->curElem = GF_TAILQ_FIRST(&(curHeader->hashHead[curHeader->curIndex]));
410 }
411
412 return curHeader->curElem->data;
413 }
414