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 
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
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 
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 
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 
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 
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 
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 
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 
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 
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 
291 {
292  return ht->listhead;
293 }
294 
295 /*
296  * ONLY TESTS BELOW THIS COMMENT
297  */
298 
299 #ifdef UNITTESTS
300 static int HashListTableTestInit01 (void)
301 {
303  if (ht == NULL)
304  return 0;
305 
306  HashListTableFree(ht);
307  return 1;
308 }
309 
310 /* no hash function, so it should fail */
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 
321 static int HashListTableTestInit03 (void)
322 {
323  int result = 0;
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 
335 static int HashListTableTestInit04 (void)
336 {
338  if (ht == NULL)
339  return 1;
340 
341  HashListTableFree(ht);
342  return 0;
343 }
344 
345 static int HashListTableTestAdd01 (void)
346 {
347  int result = 0;
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 
363 static int HashListTableTestAdd02 (void)
364 {
365  int result = 0;
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 
381 static int HashListTableTestAdd03 (void)
382 {
383  int result = 0;
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 
409 static int HashListTableTestAdd04 (void)
410 {
411  int result = 0;
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 
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 
448 static int HashListTableTestFull01 (void)
449 {
450  int result = 0;
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 
474 static int HashListTableTestFull02 (void)
475 {
476  int result = 0;
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 
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 
HashListTableBucket * listtail
Definition: util-hashlist.h:40
struct HashListTableBucket_ * bucknext
Definition: util-hashlist.h:31
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:369
#define SCLogDebug(...)
Definition: util-debug.h:335
HashListTableBucket * HashListTableGetListHead(HashListTable *ht)
uint32_t(* Hash)(struct HashListTable_ *, void *, uint16_t)
Definition: util-hashlist.h:42
HashListTableBucket * listhead
Definition: util-hashlist.h:39
#define unlikely(expr)
Definition: util-optimize.h:35
#define HashListTableGetListData(hb)
Definition: util-hashlist.h:59
void(* Free)(void *)
Definition: util-hash.h:43
HashListTableBucket ** array
Definition: util-hashlist.h:38
struct HashListTableBucket_ * listprev
Definition: util-hashlist.h:33
void * HashListTableLookup(HashListTable *ht, void *data, uint16_t datalen)
uint32_t(* Hash)(struct HashTable_ *, void *, uint16_t)
Definition: util-hash.h:41
char(* Compare)(void *, uint16_t, void *, uint16_t)
Definition: util-hash.h:42
void HashListTablePrint(HashListTable *ht)
int HashListTableAdd(HashListTable *ht, void *data, uint16_t datalen)
char HashListTableDefaultCompare(void *data1, uint16_t len1, void *data2, uint16_t len2)
uint32_t HashListTableGenericHash(HashListTable *ht, void *data, uint16_t datalen)
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
struct HashListTableBucket_ * listnext
Definition: util-hashlist.h:32
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
void HashListTableRegisterTests(void)
#define SCMalloc(a)
Definition: util-mem.h:166
void(* Free)(void *)
Definition: util-hashlist.h:44
#define SCFree(a)
Definition: util-mem.h:228
uint32_t array_size
Definition: util-hashlist.h:41
void HashListTableFree(HashListTable *ht)
Definition: util-hashlist.c:82
char(* Compare)(void *, uint16_t, void *, uint16_t)
Definition: util-hashlist.h:43
int HashListTableRemove(HashListTable *ht, void *data, uint16_t datalen)