1 /*
2 * Copyright 2008 The qDecoder Project. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE QDECODER PROJECT ``AS IS'' AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17 * DISCLAIMED. IN NO EVENT SHALL THE QDECODER PROJECT BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26 /**
27 * @file qHashtbl.c Hash-table Data Structure API
28 */
29
30 #ifndef DISABLE_DATASTRUCTURE
31
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <stdbool.h>
35 #include <string.h>
36 #include "qDecoder.h"
37 #include "qInternal.h"
38
39 static int _findEmpty(Q_HASHTBL *tbl, int startidx);
40 static int _getIdx(Q_HASHTBL *tbl, const char *key, int hash);
41 static bool _putData(Q_HASHTBL *tbl, int idx, int hash, const char *key, const void *value, int size, int count);
42 static bool _removeData(Q_HASHTBL *tbl, int idx);
43
44 /**
45 * Initialize dynamic-hash table
46 *
47 * @param max a number of maximum size of Q_HASHARR
48 *
49 * @return a pointer of malloced Q_HASHTBL, otherwise returns false
50 *
51 * @code
52 * Q_HASHTBL *hashtbl = qHashtblInit(1000);
53 * qHashtblFree(hashtbl);
54 * @endcode
55 */
56 Q_HASHTBL *qHashtblInit(int max) {
57 if(max <= 0) return NULL;
58
59 Q_HASHTBL *tbl = (Q_HASHTBL *)malloc(sizeof(Q_HASHTBL));
60 if(tbl == NULL) return NULL;
61
62 memset((void *)tbl, 0, sizeof(Q_HASHTBL));
63
64 tbl->count = (int *)malloc(sizeof(int) * max);
65 if(tbl->count != NULL) memset((void *)(tbl->count), 0, (sizeof(int) * max));
66 tbl->hash = (int *)malloc(sizeof(int) * max);
67 if(tbl->hash != NULL) memset((void *)(tbl->hash), 0, (sizeof(int) * max));
68
69 tbl->key = (char **)malloc(sizeof(char *) * max);
70 if(tbl->key != NULL) memset((void *)(tbl->key), 0, (sizeof(char *) * max));
71 tbl->value = (void **)malloc(sizeof(char *) * max);
72 if(tbl->value != NULL) memset((void *)(tbl->value), 0, (sizeof(void *) * max));
73 tbl->size = (int *)malloc(sizeof(int) * max);
74 if(tbl->size != NULL) memset((void *)(tbl->size), 0, (sizeof(int) * max));
75
76 if(tbl->count == NULL || tbl->hash == NULL || tbl->key == NULL || tbl->value == NULL || tbl->size == NULL) {
77 qHashtblFree(tbl);
78 return NULL;
79 }
80
81 tbl->max = max;
82 return tbl;
83 }
84
85 /**
86 * De-allocate hash table
87 *
88 * @param tbl a pointer of Q_HASHTBL
89 *
90 * @return true if successful, otherwise returns false
91 */
92 bool qHashtblFree(Q_HASHTBL *tbl) {
93 if(tbl == NULL) return false;
94
95 int idx, num;
96 for (idx = 0, num = 0; idx < tbl->max && num < tbl->num; idx++) {
97 if (tbl->count[idx] == 0) continue;
98 free(tbl->key[idx]);
99 free(tbl->value[idx]);
100
101 num++;
102 if(num >= tbl->num) break;
103 }
104
105 if(tbl->count != NULL) free(tbl->count);
106 if(tbl->hash != NULL) free(tbl->hash);
107 if(tbl->key != NULL) free(tbl->key);
108 if(tbl->value != NULL) free(tbl->value);
109 if(tbl->size != NULL) free(tbl->size);
110 free(tbl);
111
112 return true;
113 }
114
115 /**
116 * Put object into hash table
117 *
118 * @param tbl a pointer of Q_HASHTBL
119 * @param key key string
120 * @param value value object data
121 * @param size size of value
122 *
123 * @return true if successful, otherwise returns false
124 */
125 bool qHashtblPut(Q_HASHTBL *tbl, const char *key, const void *value, int size) {
126 if(tbl == NULL || key == NULL || value == NULL) return false;
127
128 // get hash integer
129 int hash = (int)qHashFnv32(tbl->max, key, strlen(key));
130
131 // check, is slot empty
132 if (tbl->count[hash] == 0) { // empty slot
133 // put data
134 _putData(tbl, hash, hash, key, value, size, 1);
135
136 DEBUG("hashtbl: put(new) %s (idx=%d,hash=%d,tot=%d)", key, hash, hash, tbl->num);
137 } else if (tbl->count[hash] > 0) { // same key exists or hash collision
138 // check same key;
139 int idx = _getIdx(tbl, key, hash);
140 if (idx >= 0) { // same key
141 // remove and recall
142 qHashtblRemove(tbl, key);
143 return qHashtblPut(tbl, key, value, size);
144 } else { // no same key, just hash collision
145 // find empty slot
146 int idx = _findEmpty(tbl, hash);
147 if (idx < 0) return false;
148
149 // put data
150 _putData(tbl, idx, hash, key, value, size, -1); // -1 is used for idx != hash;
151
152 // increase counter from leading slot
153 tbl->count[hash]++;
154
155 DEBUG("hashtbl: put(col) %s (idx=%d,hash=%d,tot=%d)", key, idx, hash, tbl->num);
156 }
157 } else { // in case of -1. used for dup data, move it
158 // find empty slot
159 int idx = _findEmpty(tbl, hash);
160 if (idx < 0) return false;
161
162 // move dup data
163 _putData(tbl, idx, tbl->hash[hash], tbl->key[hash], tbl->value[hash], tbl->size[hash], tbl->count[hash]);
164 _removeData(tbl, hash);
165
166 // store data
167 _putData(tbl, hash, hash, key, value, size, 1);
168
169 DEBUG("hashtbl: put(swp) %s (idx=%d,hash=%d,tot=%d)", key, hash, hash, tbl->num);
170 }
171
172 return true;
173 }
174
175 /**
176 * Put string into hash table
177 *
178 * @param tbl a pointer of Q_HASHTBL
179 * @param key key string
180 * @param value value string
181 *
182 * @return true if successful, otherwise returns false
183 */
184 bool qHashtblPutStr(Q_HASHTBL *tbl, const char *key, const char *value) {
185 int size = (value != NULL) ? (strlen(value) + 1) : 0;
186 return qHashtblPut(tbl, key, value, size);
187 }
188
189 /**
190 * Put integer into hash table
191 *
192 * @param tbl a pointer of Q_HASHTBL
193 * @param key key string
194 * @param value value integer
195 *
196 * @return true if successful, otherwise returns false
197 */
198 bool qHashtblPutInt(Q_HASHTBL *tbl, const char *key, const int value) {
199 char data[10+1];
200 sprintf(data, "%d", value);
201 return qHashtblPut(tbl, key, data, strlen(data) + 1);
202 }
203
204 /**
205 * Get object from hash table
206 *
207 * @param tbl a pointer of Q_HASHTBL
208 * @param key key string
209 * @param size if not NULL, oject size will be stored
210 *
211 * @return malloced object pointer if successful, otherwise(not found) returns NULL
212 *
213 * @note
214 * returned object must be freed after done using.
215 */
216 void *qHashtblGet(Q_HASHTBL *tbl, const char *key, int *size) {
217 if(tbl == NULL || key == NULL) return NULL;
218
219 int hash = (int)qHashFnv32(tbl->max, key, strlen(key));
220 int idx = _getIdx(tbl, key, hash);
221 if (idx < 0) return NULL;
222
223 void *value = (char *)malloc(tbl->size[idx]);
224 memcpy(value, tbl->value[idx], tbl->size[idx]);
225
226 if(size != NULL) *size = tbl->size[idx];
227 return value;
228 }
229
230 /**
231 * Get string from hash table
232 *
233 * @param tbl a pointer of Q_HASHTBL
234 * @param key key string
235 *
236 * @return string pointer if successful, otherwise(not found) returns NULL
237 *
238 * @note
239 * returned object must be freed after done using.
240 */
241 char *qHashtblGetStr(Q_HASHTBL *tbl, const char *key) {
242 return qHashtblGet(tbl, key, NULL);
243 }
244
245 /**
246 * Get integer from hash table
247 *
248 * @param tbl a pointer of Q_HASHARR
249 * @param key key string
250 *
251 * @return value integer if successful, otherwise(not found) returns 0
252 */
253 int qHashtblGetInt(Q_HASHTBL *tbl, const char *key) {
254 char *data = qHashtblGet(tbl, key, NULL);
255 if(data == NULL) return 0;
256
257 int value = atoi(data);
258 free(data);
259
260 return value;
261 }
262
263 /**
264 * Get first key name
265 *
266 * @param tbl a pointer of Q_HASHTBL
267 * @param idx index pointer
268 *
269 * @return key name string if successful, otherwise returns NULL
270 *
271 * @note
272 * Do not free returned key string.
273 *
274 * @code
275 * char *key;
276 * int idx;
277 * for(key = qHashtblGetFirstKey(tbl, &idx); key != NULL; key = qHashtblGetNextKey(tbl, &idx) {
278 * char *value = qHashtblGetStr(tbl, key);
279 * if(value != NULL) free(value);
280 * }
281 * @endcode
282 */
283 const char *qHashtblGetFirstKey(Q_HASHTBL *tbl, int *idx) {
284 if(idx != NULL) *idx = -1;
285 return qHashtblGetNextKey(tbl, idx);
286 }
287
288 /**
289 * Get next key name
290 *
291 * @param tbl a pointer of Q_HASHTBL
292 * @param idx index pointer
293 *
294 * @return key name string if successful, otherwise(end of table) returns NULL
295 *
296 * @note
297 * Do not free returned key string.
298 */
299 const char *qHashtblGetNextKey(Q_HASHTBL *tbl, int *idx) {
300 if(tbl == NULL || idx == NULL) return NULL;
301
302 for ((*idx)++; *idx < tbl->max; (*idx)++) {
303 if (tbl->count[*idx] == 0) continue;
304 return tbl->key[*idx];
305 }
306
307 *idx = tbl->max;
308 return NULL;
309 }
310
311 /**
312 * Remove key from hash table
313 *
314 * @param tbl a pointer of Q_HASHTBL
315 * @param key key string
316 *
317 * @return true if successful, otherwise(not found) returns false
318 */
319 bool qHashtblRemove(Q_HASHTBL *tbl, const char *key) {
320 if(tbl == NULL || key == NULL) return false;
321
322 int hash = (int)qHashFnv32(tbl->max, key, strlen(key));
323 int idx = _getIdx(tbl, key, hash);
324 if (idx < 0) return false;
325
326 if (tbl->count[idx] == 1) {
327 // just remove
328 _removeData(tbl, idx);
329
330 DEBUG("hashtbl: rem %s (idx=%d,tot=%d)", key, idx, tbl->num);
331 } else if (tbl->count[idx] > 1) { // leading slot and has dup
332 // find dup
333 int idx2;
334 for (idx2 = idx + 1; ; idx2++) {
335 if (idx2 >= tbl->max) idx2 = 0;
336 if (idx2 == idx) {
337 DEBUG("hashtbl: BUG remove failed %s. dup not found.", key);
338 return false;
339 }
340 if (tbl->count[idx2] == -1 && tbl->hash[idx2] == idx) break;
341 }
342
343 // move to leading slot
344 int backupcount = tbl->count[idx];
345 _removeData(tbl, idx); // remove leading slot
346 _putData(tbl, idx, tbl->hash[idx2], tbl->key[idx2], tbl->value[idx2], tbl->size[idx2], backupcount - 1); // copy to leading slot
347 _removeData(tbl, idx2); // remove dup slot
348
349 DEBUG("hashtbl: rem(lead) %s (idx=%d,tot=%d)", key, idx, tbl->num);
350 } else { // in case of -1. used for dup data
351 // decrease counter from leading slot
352 if(tbl->count[tbl->hash[idx]] <= 1) {
353 DEBUG("hashtbl: BUG remove failed %s. counter of leading slot mismatch.", key);
354 return false;
355 }
356 tbl->count[tbl->hash[idx]]--;
357
358 // remove dup
359 _removeData(tbl, idx);
360
361 DEBUG("hashtbl: rem(dup) %s (idx=%d,tot=%d)", key, idx, tbl->num);
362 }
363
364 return true;
365 }
366
367 /**
368 * Print hash table for debugging purpose
369 *
370 * @param tbl a pointer of Q_HASHTBL
371 * @param out output stream
372 * @param showvalue print out value if set to true
373 *
374 * @return true if successful, otherwise returns false
375 */
376 bool qHashtblPrint(Q_HASHTBL *tbl, FILE *out, bool showvalue) {
377 if(tbl == NULL || out == NULL) return false;
378
379 int idx, num;
380 for (idx = 0, num = 0; idx < tbl->max && num < tbl->num; idx++) {
381 if (tbl->count[idx] == 0) continue;
382 fprintf(out, "%s=%s (idx=%d,hash=%d,size=%d)\n", tbl->key[idx], (showvalue)?(char*)tbl->value[idx]:"_binary_", idx, tbl->hash[idx], tbl->size[idx]);
383 num++;
384 }
385
386 return true;
387 }
388
389 /**
390 * Get hash table internal status
391 *
392 * @param tbl a pointer of Q_HASHARR
393 * @param used if not NULL, a number of used keys will be stored
394 * @param max if not NULL, the maximum usable number of keys will be stored
395 *
396 * @return true if successful, otherwise returns false
397 */
398 bool qHashtblStatus(Q_HASHTBL *tbl, int *used, int *max) {
399 if(tbl == NULL) return false;
400
401 if(used != NULL) *used = tbl->num;
402 if(max != NULL) *max = tbl->max;
403
404 return true;
405 }
406
407 /////////////////////////////////////////////////////////////////////////
408 // PRIVATE FUNCTIONS
409 /////////////////////////////////////////////////////////////////////////
410
411 // find empty slot : return empty slow number, otherwise returns -1.
412 static int _findEmpty(Q_HASHTBL *tbl, int startidx) {
413 if (startidx >= tbl->max) startidx = 0;
414
415 int idx = startidx;
416 while (true) {
417 if (tbl->count[idx] == 0) return idx;
418
419 idx++;
420 if (idx >= tbl->max) idx = 0;
421 if(idx == startidx) break;
422 }
423
424 return -1;
425 }
426
427 static int _getIdx(Q_HASHTBL *tbl, const char *key, int hash) {
428 if (tbl->count[hash] > 0) {
429 int count, idx;
430 for (count = 0, idx = hash; count < tbl->count[hash]; ) {
431 // find same hash
432 while(true) {
433 if (idx >= tbl->max) idx = 0;
434
435 if (tbl->count[idx] != 0 && tbl->hash[idx] == hash) {
436 // found same hash
437 count++;
438 break;
439 }
440
441 idx++;
442 if(idx == hash) return -1;
443 }
444
445 // is same key?
446 if (!strcmp(tbl->key[idx], key)) return idx;
447
448 idx++;
449 if (idx >= tbl->max) idx = 0;
450 if(idx == hash) break;
451 }
452 }
453
454 return -1;
455 }
456
457 static bool _putData(Q_HASHTBL *tbl, int idx, int hash, const char *key, const void *value, int size, int count) {
458 // check if used
459 if(tbl->count[idx] != 0) return false;
460
461 // store
462 tbl->hash[idx] = hash;
463 tbl->key[idx] = strdup(key);
464 tbl->value[idx] = malloc(size);
465 if(tbl->value[idx] == NULL) {
466 free(tbl->key[idx]);
467 return false;
468 }
469 memcpy(tbl->value[idx], value, size);
470 tbl->size[idx] = size;
471 tbl->count[idx] = count;
472
473 // increase used counter
474 tbl->num++;
475
476 return true;
477 }
478
479 static bool _removeData(Q_HASHTBL *tbl, int idx) {
480 if(tbl->count[idx] == 0) return false;
481
482 free(tbl->key[idx]);
483 free(tbl->value[idx]);
484 tbl->count[idx] = 0;
485
486 // decrease used counter
487 tbl->num--;
488
489 return true;
490 }
491
492 #endif /* DISABLE_DATASTRUCTURE */
