1 /* Copyright (C) 2007-2010 Open Information Security Foundation
2 *
3 * You can copy, redistribute or modify this Program under the terms of
4 * the GNU General Public License version 2 as published by the Free
5 * Software Foundation.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * version 2 along with this program; if not, write to the Free Software
14 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15 * 02110-1301, USA.
16 */
17
18 /**
19 * \file
20 *
21 * \author Victor Julien <victor@inliniac.net>
22 *
23 * Chained hash table implementation
24 *
25 * The 'Free' pointer can be used to have the API free your
26 * hashed data. If it's NULL it's the callers responsebility
27 */
28
29 #include "suricata-common.h"
30 #include "util-hashlist.h"
31 #include "util-unittest.h"
32 #include "util-debug.h"
33 #include "util-memcmp.h"
34
HashListTableInit(uint32_t size,uint32_t (* Hash)(struct HashListTable_ *,void *,uint16_t),char (* Compare)(void *,uint16_t,void *,uint16_t),void (* Free)(void *))35 HashListTable* HashListTableInit(uint32_t size, uint32_t (*Hash)(struct HashListTable_ *, void *, uint16_t), char (*Compare)(void *, uint16_t, void *, uint16_t), void (*Free)(void *)) {
36
37 HashListTable *ht = NULL;
38
39 if (size == 0) {
40 goto error;
41 }
42
43 if (Hash == NULL) {
44 //printf("ERROR: HashListTableInit no Hash function\n");
45 goto error;
46 }
47
48 /* setup the filter */
49 ht = SCMalloc(sizeof(HashListTable));
50 if (unlikely(ht == NULL))
51 goto error;
52 memset(ht,0,sizeof(HashListTable));
53 ht->array_size = size;
54 ht->Hash = Hash;
55 ht->Free = Free;
56
57 if (Compare != NULL)
58 ht->Compare = Compare;
59 else
60 ht->Compare = HashListTableDefaultCompare;
61
62 /* setup the bitarray */
63 ht->array = SCMalloc(ht->array_size * sizeof(HashListTableBucket *));
64 if (ht->array == NULL)
65 goto error;
66 memset(ht->array,0,ht->array_size * sizeof(HashListTableBucket *));
67
68 ht->listhead = NULL;
69 ht->listtail = NULL;
70 return ht;
71
72 error:
73 if (ht != NULL) {
74 if (ht->array != NULL)
75 SCFree(ht->array);
76
77 SCFree(ht);
78 }
79 return NULL;
80 }
81
HashListTableFree(HashListTable * ht)82 void HashListTableFree(HashListTable *ht)
83 {
84 uint32_t i = 0;
85
86 if (ht == NULL)
87 return;
88
89 /* free the buckets */
90 for (i = 0; i < ht->array_size; i++) {
91 HashListTableBucket *hashbucket = ht->array[i];
92 while (hashbucket != NULL) {
93 HashListTableBucket *next_hashbucket = hashbucket->bucknext;
94 if (ht->Free != NULL)
95 ht->Free(hashbucket->data);
96 SCFree(hashbucket);
97 hashbucket = next_hashbucket;
98 }
99 }
100
101 /* free the array */
102 if (ht->array != NULL)
103 SCFree(ht->array);
104
105 SCFree(ht);
106 }
107
HashListTablePrint(HashListTable * ht)108 void HashListTablePrint(HashListTable *ht)
109 {
110 printf("\n----------- Hash Table Stats ------------\n");
111 printf("Buckets: %" PRIu32 "\n", ht->array_size);
112 printf("Hash function pointer: %p\n", ht->Hash);
113 printf("-----------------------------------------\n");
114 }
115
HashListTableAdd(HashListTable * ht,void * data,uint16_t datalen)116 int HashListTableAdd(HashListTable *ht, void *data, uint16_t datalen)
117 {
118 if (ht == NULL || data == NULL)
119 return -1;
120
121 uint32_t hash = ht->Hash(ht, data, datalen);
122
123 SCLogDebug("ht %p hash %"PRIu32"", ht, hash);
124
125 HashListTableBucket *hb = SCMalloc(sizeof(HashListTableBucket));
126 if (unlikely(hb == NULL))
127 goto error;
128 memset(hb, 0, sizeof(HashListTableBucket));
129 hb->data = data;
130 hb->size = datalen;
131 hb->bucknext = NULL;
132 hb->listnext = NULL;
133 hb->listprev = NULL;
134
135 if (ht->array[hash] == NULL) {
136 ht->array[hash] = hb;
137 } else {
138 hb->bucknext = ht->array[hash];
139 ht->array[hash] = hb;
140 }
141
142 if (ht->listtail == NULL) {
143 ht->listhead = hb;
144 ht->listtail = hb;
145 } else {
146 hb->listprev = ht->listtail;
147 ht->listtail->listnext = hb;
148 ht->listtail = hb;
149 }
150
151 return 0;
152
153 error:
154 return -1;
155 }
156
HashListTableRemove(HashListTable * ht,void * data,uint16_t datalen)157 int HashListTableRemove(HashListTable *ht, void *data, uint16_t datalen)
158 {
159 uint32_t hash = ht->Hash(ht, data, datalen);
160
161 SCLogDebug("ht %p hash %"PRIu32"", ht, hash);
162
163 if (ht->array[hash] == NULL) {
164 SCLogDebug("ht->array[hash] NULL");
165 return -1;
166 }
167
168 /* fast track for just one data part */
169 if (ht->array[hash]->bucknext == NULL) {
170 HashListTableBucket *hb = ht->array[hash];
171
172 if (ht->Compare(hb->data,hb->size,data,datalen) == 1) {
173 /* remove from the list */
174 if (hb->listprev == NULL) {
175 ht->listhead = hb->listnext;
176 } else {
177 hb->listprev->listnext = hb->listnext;
178 }
179 if (hb->listnext == NULL) {
180 ht->listtail = hb->listprev;
181 } else {
182 hb->listnext->listprev = hb->listprev;
183 }
184
185 if (ht->Free != NULL)
186 ht->Free(hb->data);
187
188 SCFree(ht->array[hash]);
189 ht->array[hash] = NULL;
190 return 0;
191 }
192
193 SCLogDebug("fast track default case");
194 return -1;
195 }
196
197 /* more data in this bucket */
198 HashListTableBucket *hashbucket = ht->array[hash], *prev_hashbucket = NULL;
199 do {
200 if (ht->Compare(hashbucket->data,hashbucket->size,data,datalen) == 1) {
201
202 /* remove from the list */
203 if (hashbucket->listprev == NULL) {
204 ht->listhead = hashbucket->listnext;
205 } else {
206 hashbucket->listprev->listnext = hashbucket->listnext;
207 }
208 if (hashbucket->listnext == NULL) {
209 ht->listtail = hashbucket->listprev;
210 } else {
211 hashbucket->listnext->listprev = hashbucket->listprev;
212 }
213
214 if (prev_hashbucket == NULL) {
215 /* root bucket */
216 ht->array[hash] = hashbucket->bucknext;
217 } else {
218 /* child bucket */
219 prev_hashbucket->bucknext = hashbucket->bucknext;
220 }
221
222 /* remove this */
223 if (ht->Free != NULL)
224 ht->Free(hashbucket->data);
225 SCFree(hashbucket);
226 return 0;
227 }
228
229 prev_hashbucket = hashbucket;
230 hashbucket = hashbucket->bucknext;
231 } while (hashbucket != NULL);
232
233 SCLogDebug("slow track default case");
234 return -1;
235 }
236
HashListTableDefaultCompare(void * data1,uint16_t len1,void * data2,uint16_t len2)237 char HashListTableDefaultCompare(void *data1, uint16_t len1, void *data2, uint16_t len2)
238 {
239 if (len1 != len2)
240 return 0;
241
242 if (SCMemcmp(data1,data2,len1) != 0)
243 return 0;
244
245 return 1;
246 }
247
HashListTableLookup(HashListTable * ht,void * data,uint16_t datalen)248 void *HashListTableLookup(HashListTable *ht, void *data, uint16_t datalen)
249 {
250
251 if (ht == NULL) {
252 SCLogDebug("Hash List table is NULL");
253 return NULL;
254 }
255
256 uint32_t hash = ht->Hash(ht, data, datalen);
257
258 if (ht->array[hash] == NULL) {
259 return NULL;
260 }
261
262 HashListTableBucket *hashbucket = ht->array[hash];
263 do {
264 if (ht->Compare(hashbucket->data,hashbucket->size,data,datalen) == 1)
265 return hashbucket->data;
266
267 hashbucket = hashbucket->bucknext;
268 } while (hashbucket != NULL);
269
270 return NULL;
271 }
272
HashListTableGenericHash(HashListTable * ht,void * data,uint16_t datalen)273 uint32_t HashListTableGenericHash(HashListTable *ht, void *data, uint16_t datalen)
274 {
275 uint8_t *d = (uint8_t *)data;
276 uint32_t i;
277 uint32_t hash = 0;
278
279 for (i = 0; i < datalen; i++) {
280 if (i == 0) hash += (((uint32_t)*d++));
281 else if (i == 1) hash += (((uint32_t)*d++) * datalen);
282 else hash *= (((uint32_t)*d++) * i) + datalen + i;
283 }
284
285 hash *= datalen;
286 hash %= ht->array_size;
287 return hash;
288 }
289
HashListTableGetListHead(HashListTable * ht)290 HashListTableBucket *HashListTableGetListHead(HashListTable *ht)
291 {
292 return ht->listhead;
293 }
294
295 /*
296 * ONLY TESTS BELOW THIS COMMENT
297 */
298
299 #ifdef UNITTESTS
HashListTableTestInit01(void)300 static int HashListTableTestInit01 (void)
301 {
302 HashListTable *ht = HashListTableInit(1024, HashListTableGenericHash, NULL, NULL);
303 if (ht == NULL)
304 return 0;
305
306 HashListTableFree(ht);
307 return 1;
308 }
309
310 /* no hash function, so it should fail */
HashListTableTestInit02(void)311 static int HashListTableTestInit02 (void)
312 {
313 HashListTable *ht = HashListTableInit(1024, NULL, NULL, NULL);
314 if (ht == NULL)
315 return 1;
316
317 HashListTableFree(ht);
318 return 0;
319 }
320
HashListTableTestInit03(void)321 static int HashListTableTestInit03 (void)
322 {
323 int result = 0;
324 HashListTable *ht = HashListTableInit(1024, HashListTableGenericHash, NULL, NULL);
325 if (ht == NULL)
326 return 0;
327
328 if (ht->Hash == HashListTableGenericHash)
329 result = 1;
330
331 HashListTableFree(ht);
332 return result;
333 }
334
HashListTableTestInit04(void)335 static int HashListTableTestInit04 (void)
336 {
337 HashListTable *ht = HashListTableInit(0, HashListTableGenericHash, NULL, NULL);
338 if (ht == NULL)
339 return 1;
340
341 HashListTableFree(ht);
342 return 0;
343 }
344
HashListTableTestAdd01(void)345 static int HashListTableTestAdd01 (void)
346 {
347 int result = 0;
348 HashListTable *ht = HashListTableInit(32, HashListTableGenericHash, NULL, NULL);
349 if (ht == NULL)
350 goto end;
351
352 int r = HashListTableAdd(ht, (char *)"test", 0);
353 if (r != 0)
354 goto end;
355
356 /* all is good! */
357 result = 1;
358 end:
359 if (ht != NULL) HashListTableFree(ht);
360 return result;
361 }
362
HashListTableTestAdd02(void)363 static int HashListTableTestAdd02 (void)
364 {
365 int result = 0;
366 HashListTable *ht = HashListTableInit(32, HashListTableGenericHash, NULL, NULL);
367 if (ht == NULL)
368 goto end;
369
370 int r = HashListTableAdd(ht, NULL, 4);
371 if (r == 0)
372 goto end;
373
374 /* all is good! */
375 result = 1;
376 end:
377 if (ht != NULL) HashListTableFree(ht);
378 return result;
379 }
380
HashListTableTestAdd03(void)381 static int HashListTableTestAdd03 (void)
382 {
383 int result = 0;
384 HashListTable *ht = HashListTableInit(32, HashListTableGenericHash, NULL, NULL);
385 if (ht == NULL)
386 goto end;
387
388 int r = HashListTableAdd(ht, (char *)"test", 0);
389 if (r != 0)
390 goto end;
391
392 if (ht->listhead == NULL) {
393 printf("ht->listhead == NULL: ");
394 goto end;
395 }
396
397 if (ht->listtail == NULL) {
398 printf("ht->listtail == NULL: ");
399 goto end;
400 }
401
402 /* all is good! */
403 result = 1;
404 end:
405 if (ht != NULL) HashListTableFree(ht);
406 return result;
407 }
408
HashListTableTestAdd04(void)409 static int HashListTableTestAdd04 (void)
410 {
411 int result = 0;
412 HashListTable *ht = HashListTableInit(32, HashListTableGenericHash, NULL, NULL);
413 if (ht == NULL)
414 goto end;
415
416 int r = HashListTableAdd(ht, (char *)"test", 4);
417 if (r != 0)
418 goto end;
419
420 char *rp = HashListTableLookup(ht, (char *)"test", 4);
421 if (rp == NULL)
422 goto end;
423
424 HashListTableBucket *htb = HashListTableGetListHead(ht);
425 if (htb == NULL) {
426 printf("htb == NULL: ");
427 goto end;
428 }
429
430 char *rp2 = HashListTableGetListData(htb);
431 if (rp2 == NULL) {
432 printf("rp2 == NULL: ");
433 goto end;
434 }
435
436 if (rp != rp2) {
437 printf("rp != rp2: ");
438 goto end;
439 }
440
441 /* all is good! */
442 result = 1;
443 end:
444 if (ht != NULL) HashListTableFree(ht);
445 return result;
446 }
447
HashListTableTestFull01(void)448 static int HashListTableTestFull01 (void)
449 {
450 int result = 0;
451 HashListTable *ht = HashListTableInit(32, HashListTableGenericHash, NULL, NULL);
452 if (ht == NULL)
453 goto end;
454
455 int r = HashListTableAdd(ht, (char *)"test", 4);
456 if (r != 0)
457 goto end;
458
459 char *rp = HashListTableLookup(ht, (char *)"test", 4);
460 if (rp == NULL)
461 goto end;
462
463 r = HashListTableRemove(ht, (char *)"test", 4);
464 if (r != 0)
465 goto end;
466
467 /* all is good! */
468 result = 1;
469 end:
470 if (ht != NULL) HashListTableFree(ht);
471 return result;
472 }
473
HashListTableTestFull02(void)474 static int HashListTableTestFull02 (void)
475 {
476 int result = 0;
477 HashListTable *ht = HashListTableInit(32, HashListTableGenericHash, NULL, NULL);
478 if (ht == NULL)
479 goto end;
480
481 int r = HashListTableAdd(ht, (char *)"test", 4);
482 if (r != 0)
483 goto end;
484
485 char *rp = HashListTableLookup(ht, (char *)"test", 4);
486 if (rp == NULL)
487 goto end;
488
489 r = HashListTableRemove(ht, (char *)"test2", 5);
490 if (r == 0)
491 goto end;
492
493 /* all is good! */
494 result = 1;
495 end:
496 if (ht != NULL) HashListTableFree(ht);
497 return result;
498 }
499 #endif /* UNITTESTS */
500
HashListTableRegisterTests(void)501 void HashListTableRegisterTests(void)
502 {
503 #ifdef UNITTESTS
504 UtRegisterTest("HashListTableTestInit01", HashListTableTestInit01);
505 UtRegisterTest("HashListTableTestInit02", HashListTableTestInit02);
506 UtRegisterTest("HashListTableTestInit03", HashListTableTestInit03);
507 UtRegisterTest("HashListTableTestInit04", HashListTableTestInit04);
508
509 UtRegisterTest("HashListTableTestAdd01", HashListTableTestAdd01);
510 UtRegisterTest("HashListTableTestAdd02", HashListTableTestAdd02);
511 UtRegisterTest("HashListTableTestAdd03", HashListTableTestAdd03);
512 UtRegisterTest("HashListTableTestAdd04", HashListTableTestAdd04);
513
514 UtRegisterTest("HashListTableTestFull01", HashListTableTestFull01);
515 UtRegisterTest("HashListTableTestFull02", HashListTableTestFull02);
516 #endif /* UNITTESTS */
517 }
518
519