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