1 /*
2 *
3 * Copyright (c) 2014, Red Hat, Inc.
4 * Copyright (c) 2014, Masatake YAMATO
5 *
6 * This source code is released for free distribution under the terms of the
7 * GNU General Public License version 2 or (at your option) any later version.
8 *
9 * Defines hashtable
10 */
11
12 #include "general.h"
13 #include "htable.h"
14
15 #ifndef MAIN
16 #include <stdio.h>
17 #include "routines.h"
18 #else
19 #include <stdlib.h>
20 #ifndef xCalloc
21 #define xCalloc(n,Type) (Type *)calloc((size_t)(n), sizeof (Type))
22 #endif
23 #ifndef xMalloc
24 #define xMalloc(n,Type) (Type *)malloc((size_t)(n) * sizeof (Type))
25 #endif
26 #ifndef eFree
27 #define eFree(x) free(x)
28 #endif
29 #endif /* MAIN */
30
31 #include <string.h>
32
33
34 typedef struct sHashEntry hentry;
35 struct sHashEntry {
36 void *key;
37 void *value;
38 hentry *next;
39 };
40
41 struct sHashTable {
42 hentry** table;
43 unsigned int size;
44 hashTableHashFunc hashfn;
45 hashTableEqualFunc equalfn;
46 hashTableDeleteFunc keyfreefn;
47 hashTableDeleteFunc valfreefn;
48 void *valForNotUnknownKey;
49 hashTableDeleteFunc valForNotUnknownKeyfreefn;
50 };
51
52 struct chainTracker {
53 const void *const target_key;
54 hashTableForeachFunc user_proc;
55 void *user_data;
56 hashTableEqualFunc equalfn;
57 };
58
entry_new(void * key,void * value,hentry * next)59 static hentry* entry_new (void *key, void *value, hentry* next)
60 {
61 hentry* entry = xMalloc (1, hentry);
62
63 entry->key = key;
64 entry->value = value;
65 entry->next = next;
66
67 return entry;
68 }
69
entry_reset(hentry * entry,void * newkey,void * newval,hashTableDeleteFunc keyfreefn,hashTableDeleteFunc valfreefn)70 static void entry_reset (hentry* entry,
71 void *newkey,
72 void *newval,
73 hashTableDeleteFunc keyfreefn,
74 hashTableDeleteFunc valfreefn)
75 {
76 if (keyfreefn)
77 keyfreefn (entry->key);
78 if (valfreefn)
79 valfreefn (entry->value);
80 entry->key = newkey;
81 entry->value = newval;
82 }
83
entry_destroy(hentry * entry,hashTableDeleteFunc keyfreefn,hashTableDeleteFunc valfreefn)84 static hentry* entry_destroy (hentry* entry,
85 hashTableDeleteFunc keyfreefn,
86 hashTableDeleteFunc valfreefn)
87 {
88 hentry* tmp;
89
90 entry_reset (entry, NULL, NULL, keyfreefn, valfreefn);
91 tmp = entry->next;
92 eFree (entry);
93
94 return tmp;
95 }
96
entry_reclaim(hentry * entry,hashTableDeleteFunc keyfreefn,hashTableDeleteFunc valfreefn)97 static void entry_reclaim (hentry* entry,
98 hashTableDeleteFunc keyfreefn,
99 hashTableDeleteFunc valfreefn)
100 {
101 while (entry)
102 entry = entry_destroy (entry, keyfreefn, valfreefn);
103 }
104
entry_find(hentry * entry,const void * const key,hashTableEqualFunc equalfn,void * valForNotUnknownKey)105 static void *entry_find (hentry* entry, const void* const key, hashTableEqualFunc equalfn,
106 void *valForNotUnknownKey)
107 {
108 while (entry)
109 {
110 if (equalfn( key, entry->key))
111 return entry->value;
112 entry = entry->next;
113 }
114 return valForNotUnknownKey;
115 }
116
entry_delete(hentry ** entry,const void * key,hashTableEqualFunc equalfn,hashTableDeleteFunc keyfreefn,hashTableDeleteFunc valfreefn)117 static bool entry_delete (hentry **entry, const void *key, hashTableEqualFunc equalfn,
118 hashTableDeleteFunc keyfreefn, hashTableDeleteFunc valfreefn)
119 {
120 while (*entry)
121 {
122 if (equalfn (key, (*entry)->key))
123 {
124 *entry = entry_destroy (*entry, keyfreefn, valfreefn);
125 return true;
126 }
127 entry = &((*entry)->next);
128 }
129 return false;
130 }
131
entry_update(hentry * entry,void * key,void * value,hashTableEqualFunc equalfn,hashTableDeleteFunc keyfreefn,hashTableDeleteFunc valfreefn)132 static bool entry_update (hentry *entry, void *key, void *value, hashTableEqualFunc equalfn,
133 hashTableDeleteFunc keyfreefn, hashTableDeleteFunc valfreefn)
134 {
135 while (entry)
136 {
137 if (equalfn (key, entry->key))
138 {
139 entry_reset (entry, key, value, keyfreefn, valfreefn);
140 return true;
141 }
142 entry = entry->next;
143 }
144 return false;
145 }
146
entry_foreach(hentry * entry,hashTableForeachFunc proc,void * user_data)147 static bool entry_foreach (hentry *entry, hashTableForeachFunc proc, void *user_data)
148 {
149 while (entry)
150 {
151 if (!proc (entry->key, entry->value, user_data))
152 return false;
153 entry = entry->next;
154 }
155 return true;
156 }
157
hashTableNew(unsigned int size,hashTableHashFunc hashfn,hashTableEqualFunc equalfn,hashTableDeleteFunc keyfreefn,hashTableDeleteFunc valfreefn)158 extern hashTable *hashTableNew (unsigned int size,
159 hashTableHashFunc hashfn,
160 hashTableEqualFunc equalfn,
161 hashTableDeleteFunc keyfreefn,
162 hashTableDeleteFunc valfreefn)
163 {
164 hashTable *htable;
165
166 htable = xMalloc (1, hashTable);
167 htable->size = size;
168 htable->table = xCalloc (size, hentry*);
169
170 htable->hashfn = hashfn;
171 htable->equalfn = equalfn;
172 htable->keyfreefn = keyfreefn;
173 htable->valfreefn = valfreefn;
174 htable->valForNotUnknownKey = NULL;
175 htable->valForNotUnknownKeyfreefn = NULL;
176
177 return htable;
178 }
179
hashTableSetValueForUnknownKey(hashTable * htable,void * val,hashTableDeleteFunc valfreefn)180 extern void hashTableSetValueForUnknownKey (hashTable *htable,
181 void *val,
182 hashTableDeleteFunc valfreefn)
183 {
184 if (htable->valfreefn)
185 htable->valfreefn (htable->valForNotUnknownKey);
186
187 htable->valForNotUnknownKey = val;
188 htable->valForNotUnknownKeyfreefn = valfreefn;
189 }
190
hashTableDelete(hashTable * htable)191 extern void hashTableDelete (hashTable *htable)
192 {
193 if (!htable)
194 return;
195
196 hashTableClear (htable);
197
198 if (htable->valForNotUnknownKeyfreefn)
199 htable->valForNotUnknownKeyfreefn (htable->valForNotUnknownKey);
200 eFree (htable->table);
201 eFree (htable);
202 }
203
hashTableClear(hashTable * htable)204 extern void hashTableClear (hashTable *htable)
205 {
206 unsigned int i;
207 if (!htable)
208 return;
209
210 for (i = 0; i < htable->size; i++)
211 {
212 hentry *entry;
213
214 entry = htable->table[i];
215 entry_reclaim (entry, htable->keyfreefn, htable->valfreefn);
216 htable->table[i] = NULL;
217 }
218 }
219
hashTablePutItem(hashTable * htable,void * key,void * value)220 extern void hashTablePutItem (hashTable *htable, void *key, void *value)
221 {
222 unsigned int i;
223
224 i = htable->hashfn (key) % htable->size;
225 htable->table[i] = entry_new(key, value, htable->table[i]);
226 }
227
hashTableGetItem(hashTable * htable,const void * key)228 extern void* hashTableGetItem (hashTable *htable, const void * key)
229 {
230 unsigned int i;
231
232 i = htable->hashfn (key) % htable->size;
233 return entry_find(htable->table[i], key, htable->equalfn, htable->valForNotUnknownKey);
234 }
235
hashTableDeleteItem(hashTable * htable,const void * key)236 extern bool hashTableDeleteItem (hashTable *htable, const void *key)
237 {
238 unsigned int i;
239
240 i = htable->hashfn (key) % htable->size;
241 return entry_delete(&htable->table[i], key,
242 htable->equalfn, htable->keyfreefn, htable->valfreefn);
243 }
244
hashTableUpdateItem(hashTable * htable,void * key,void * value)245 extern bool hashTableUpdateItem (hashTable *htable, void *key, void *value)
246 {
247 unsigned int i;
248
249 i = htable->hashfn (key) % htable->size;
250 bool r = entry_update(htable->table[i], key, value,
251 htable->equalfn, htable->keyfreefn, htable->valfreefn);
252 if (!r)
253 htable->table[i] = entry_new(key, value, htable->table[i]);
254 return r;
255 }
256
hashTableHasItem(hashTable * htable,const void * key)257 extern bool hashTableHasItem (hashTable *htable, const void *key)
258 {
259 return hashTableGetItem (htable, key) == htable->valForNotUnknownKey? false: true;
260 }
261
hashTableForeachItem(hashTable * htable,hashTableForeachFunc proc,void * user_data)262 extern bool hashTableForeachItem (hashTable *htable, hashTableForeachFunc proc, void *user_data)
263 {
264 unsigned int i;
265
266 for (i = 0; i < htable->size; i++)
267 if (!entry_foreach(htable->table[i], proc, user_data))
268 return false;
269 return true;
270 }
271
track_chain(const void * const key,void * value,void * chain_data)272 static bool track_chain (const void *const key, void *value, void *chain_data)
273 {
274 struct chainTracker *chain_tracker = chain_data;
275
276 if (chain_tracker->equalfn (chain_tracker->target_key, key))
277 {
278 if (! chain_tracker->user_proc (key, value, chain_tracker->user_data))
279 return false;
280 }
281 return true;
282 }
283
hashTableForeachItemOnChain(hashTable * htable,const void * key,hashTableForeachFunc proc,void * user_data)284 extern bool hashTableForeachItemOnChain (hashTable *htable, const void *key, hashTableForeachFunc proc, void *user_data)
285 {
286 unsigned int i;
287 struct chainTracker chain_tracker = {
288 .target_key = key,
289 .user_proc = proc,
290 .user_data = user_data,
291 .equalfn = htable->equalfn,
292 };
293
294 i = htable->hashfn (key) % htable->size;
295 if (!entry_foreach(htable->table[i], track_chain, &chain_tracker))
296 return false;
297 return true;
298 }
299
count(const void * const key CTAGS_ATTR_UNUSED,void * value CTAGS_ATTR_UNUSED,void * data)300 static bool count (const void *const key CTAGS_ATTR_UNUSED, void *value CTAGS_ATTR_UNUSED, void *data)
301 {
302 int *c = data;
303 ++*c;
304 return true;
305 }
306
hashTableCountItem(hashTable * htable)307 extern unsigned int hashTableCountItem (hashTable *htable)
308 {
309 int c = 0;
310 hashTableForeachItem (htable, count, &c);
311 return c;
312 }
313
hashPtrhash(const void * const x)314 unsigned int hashPtrhash (const void * const x)
315 {
316 union {
317 const void * ptr;
318 unsigned int ui;
319 } v;
320 v.ui = 0;
321 v.ptr = x;
322
323 return v.ui;
324 }
325
hashPtreq(const void * const a,const void * const b)326 bool hashPtreq (const void *const a, const void *const b)
327 {
328 return (a == b)? true: false;
329 }
330
331
332 /* http://www.cse.yorku.ca/~oz/hash.html */
333 static unsigned long
djb2(const unsigned char * str)334 djb2(const unsigned char *str)
335 {
336 unsigned long hash = 5381;
337 int c;
338
339 while ((c = *str++))
340 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
341
342 return hash;
343 }
344
345 static unsigned long
casedjb2(const unsigned char * str)346 casedjb2(const unsigned char *str)
347 {
348 unsigned long hash = 5381;
349 int c;
350
351 while ((c = *str++))
352 {
353 if (('a' <= c) && (c <= 'z'))
354 c += ('A' - 'a');
355 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
356 }
357
358 return hash;
359 }
360
361
hashCstrhash(const void * const x)362 unsigned int hashCstrhash (const void *const x)
363 {
364 const char *const s = x;
365 return (unsigned int)djb2((const unsigned char *)s);
366 }
367
hashCstreq(const void * const a,const void * const b)368 bool hashCstreq (const void * const a, const void *const b)
369 {
370 return !!(strcmp (a, b) == 0);
371 }
372
hashInthash(const void * const x)373 unsigned int hashInthash (const void *const x)
374 {
375 union tmp {
376 unsigned int u;
377 int i;
378 } x0;
379
380 x0.u = 0;
381 x0.i = *(int *)x;
382 return x0.u;
383 }
384
hashInteq(const void * const a,const void * const b)385 bool hashInteq (const void *const a, const void *const b)
386 {
387 int ai = *(int *)a;
388 int bi = *(int *)b;
389
390 return !!(ai == bi);
391 }
392
393
hashCstrcasehash(const void * const x)394 unsigned int hashCstrcasehash (const void *const x)
395 {
396 const char *const s = x;
397 return (unsigned int)casedjb2((const unsigned char *)s);
398 }
399
hashCstrcaseeq(const void * const a,const void * const b)400 bool hashCstrcaseeq (const void *const a, const void *const b)
401 {
402 return !!(strcasecmp (a, b) == 0);
403 }
404