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