suricata
util-hash.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-hash.h"
31 #include "util-unittest.h"
32 #include "util-memcmp.h"
33 #include "util-debug.h"
34 
35 HashTable* HashTableInit(uint32_t size, uint32_t (*Hash)(struct HashTable_ *, void *, uint16_t), char (*Compare)(void *, uint16_t, void *, uint16_t), void (*Free)(void *)) {
36 
37  HashTable *ht = NULL;
38 
39  if (size == 0) {
40  goto error;
41  }
42 
43  if (Hash == NULL) {
44  //printf("ERROR: HashTableInit no Hash function\n");
45  goto error;
46  }
47 
48  /* setup the filter */
49  ht = SCCalloc(1, sizeof(HashTable));
50  if (unlikely(ht == NULL))
51  goto error;
52  ht->array_size = size;
53  ht->Hash = Hash;
54  ht->Free = Free;
55 
56  if (Compare != NULL)
57  ht->Compare = Compare;
58  else
60 
61  /* setup the bitarray */
62  ht->array = SCCalloc(ht->array_size, sizeof(HashTableBucket *));
63  if (ht->array == NULL)
64  goto error;
65 
66  return ht;
67 
68 error:
69  if (ht != NULL) {
70  if (ht->array != NULL)
71  SCFree(ht->array);
72 
73  SCFree(ht);
74  }
75  return NULL;
76 }
77 
78 /**
79  * \brief Free a HashTableBucket and return the next bucket
80  * \param ht Pointer to the HashTable
81  * \param htb Pointer to the HashTableBucket to free
82  * \return HashTableBucket* Pointer to the next HashTableBucket or NULL
83  */
84 static HashTableBucket *HashTableBucketFree(HashTable *ht, HashTableBucket *htb)
85 {
86  HashTableBucket *next_hashbucket = htb->next;
87  if (ht->Free != NULL)
88  ht->Free(htb->data);
89  SCFree(htb);
90  return next_hashbucket;
91 }
92 
93 /**
94  * \brief Free a HashTable and all its contents
95  * \details This function will free all the buckets and the array of buckets.
96  * \note If the Free function is set, it will be called for each data item in the hash table.
97  * \param ht Pointer to the HashTable to free
98  * \return void
99  */
101 {
102  if (ht == NULL)
103  return;
104 
105  /* free the buckets */
106  for (uint32_t i = 0; i < ht->array_size; i++) {
107  HashTableBucket *hashbucket = ht->array[i];
108  while (hashbucket != NULL) {
109  hashbucket = HashTableBucketFree(ht, hashbucket);
110  }
111  }
112 
113  /* free the array */
114  if (ht->array != NULL)
115  SCFree(ht->array);
116 
117  SCFree(ht);
118 }
119 
120 int HashTableAdd(HashTable *ht, void *data, uint16_t datalen)
121 {
122  if (ht == NULL || data == NULL)
123  return -1;
124 
125  uint32_t hash = ht->Hash(ht, data, datalen);
126 
127  HashTableBucket *hb = SCCalloc(1, sizeof(HashTableBucket));
128  if (unlikely(hb == NULL))
129  goto error;
130  hb->data = data;
131  hb->size = datalen;
132  hb->next = NULL;
133 
134  if (hash >= ht->array_size) {
135  SCLogWarning("attempt to insert element out of hash array\n");
136  goto error;
137  }
138 
139  if (ht->array[hash] == NULL) {
140  ht->array[hash] = hb;
141  } else {
142  hb->next = ht->array[hash];
143  ht->array[hash] = hb;
144  }
145 
146 #ifdef UNITTESTS
147  ht->count++;
148 #endif
149 
150  return 0;
151 
152 error:
153  if (hb != NULL)
154  SCFree(hb);
155  return -1;
156 }
157 /**
158  * \brief Remove an item from the hash table
159  * \details This function will search for the item in the hash table and remove it if found
160  * \note If the Free function is set, it will be called for the data item being removed.
161  * \param ht Pointer to the HashTable
162  * \param data Pointer to the data to remove
163  * \param datalen Length of the data to remove
164  * \return int 0 on success, -1 if the item was not found or an error occurred
165  */
166 int HashTableRemove(HashTable *ht, void *data, uint16_t datalen)
167 {
168  uint32_t hash = ht->Hash(ht, data, datalen);
169 
170  HashTableBucket **hashbucket = &(ht->array[hash]);
171  while (*hashbucket != NULL) {
172  if (ht->Compare((*hashbucket)->data, (*hashbucket)->size, data, datalen)) {
173  *hashbucket = HashTableBucketFree(ht, *hashbucket);
174  return 0;
175  }
176  hashbucket = &((*hashbucket)->next);
177  }
178 
179  return -1;
180 }
181 
182 void *HashTableLookup(HashTable *ht, void *data, uint16_t datalen)
183 {
184  uint32_t hash = 0;
185 
186  if (ht == NULL)
187  return NULL;
188 
189  hash = ht->Hash(ht, data, datalen);
190 
191  if (hash >= ht->array_size) {
192  SCLogWarning("attempt to access element out of hash array\n");
193  return NULL;
194  }
195 
196  if (ht->array[hash] == NULL)
197  return NULL;
198 
199  HashTableBucket *hashbucket = ht->array[hash];
200  do {
201  if (ht->Compare(hashbucket->data, hashbucket->size, data, datalen) == 1)
202  return hashbucket->data;
203 
204  hashbucket = hashbucket->next;
205  } while (hashbucket != NULL);
206 
207  return NULL;
208 }
209 
210 // CallbackFn is an iterator, first argument is the data, second is user auxilary data
211 void HashTableIterate(HashTable *ht, void (*CallbackFn)(void *, void *), void *aux)
212 {
213  if (ht == NULL || CallbackFn == NULL)
214  return;
215 
216  for (uint32_t i = 0; i < ht->array_size; i++) {
217  HashTableBucket *hashbucket = ht->array[i];
218  while (hashbucket != NULL) {
219  CallbackFn(hashbucket->data, aux);
220  hashbucket = hashbucket->next;
221  }
222  }
223 }
224 
225 uint32_t HashTableGenericHash(HashTable *ht, void *data, uint16_t datalen)
226 {
227  uint8_t *d = (uint8_t *)data;
228  uint32_t i;
229  uint32_t hash = 0;
230 
231  for (i = 0; i < datalen; i++) {
232  if (i == 0) hash += (((uint32_t)*d++));
233  else if (i == 1) hash += (((uint32_t)*d++) * datalen);
234  else hash *= (((uint32_t)*d++) * i) + datalen + i;
235  }
236 
237  hash *= datalen;
238  hash %= ht->array_size;
239  return hash;
240 }
241 
242 char HashTableDefaultCompare(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 /*
254  * ONLY TESTS BELOW THIS COMMENT
255  */
256 
257 #ifdef UNITTESTS
258 static int HashTableTestInit01 (void)
259 {
260  HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
261  if (ht == NULL)
262  return 0;
263 
264  HashTableFree(ht);
265  return 1;
266 }
267 
268 /* no hash function, so it should fail */
269 static int HashTableTestInit02 (void)
270 {
271  HashTable *ht = HashTableInit(1024, NULL, NULL, NULL);
272  if (ht == NULL)
273  return 1;
274 
275  HashTableFree(ht);
276  return 0;
277 }
278 
279 static int HashTableTestInit03 (void)
280 {
281  int result = 0;
282  HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
283  if (ht == NULL)
284  return 0;
285 
286  if (ht->Hash == HashTableGenericHash)
287  result = 1;
288 
289  HashTableFree(ht);
290  return result;
291 }
292 
293 static int HashTableTestInit04 (void)
294 {
295  HashTable *ht = HashTableInit(0, HashTableGenericHash, NULL, NULL);
296  if (ht == NULL)
297  return 1;
298 
299  HashTableFree(ht);
300  return 0;
301 }
302 
303 static int HashTableTestInit05 (void)
304 {
305  int result = 0;
306  HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
307  if (ht == NULL)
308  return 0;
309 
310  if (ht->Compare == HashTableDefaultCompare)
311  result = 1;
312 
313  HashTableFree(ht);
314  return result;
315 }
316 
317 static char HashTableDefaultCompareTest(void *data1, uint16_t len1, void *data2, uint16_t len2)
318 {
319  if (len1 != len2)
320  return 0;
321 
322  if (SCMemcmp(data1,data2,len1) != 0)
323  return 0;
324 
325  return 1;
326 }
327 
328 static int HashTableTestInit06 (void)
329 {
330  int result = 0;
331  HashTable *ht = HashTableInit(1024, HashTableGenericHash, HashTableDefaultCompareTest, NULL);
332  if (ht == NULL)
333  return 0;
334 
335  if (ht->Compare == HashTableDefaultCompareTest)
336  result = 1;
337 
338  HashTableFree(ht);
339  return result;
340 }
341 
342 static int HashTableTestAdd01 (void)
343 {
344  int result = 0;
345  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
346  if (ht == NULL)
347  goto end;
348 
349  int r = HashTableAdd(ht, (char *)"test", 0);
350  if (r != 0)
351  goto end;
352 
353  /* all is good! */
354  result = 1;
355 end:
356  if (ht != NULL) HashTableFree(ht);
357  return result;
358 }
359 
360 static int HashTableTestAdd02 (void)
361 {
362  int result = 0;
363  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
364  if (ht == NULL)
365  goto end;
366 
367  int r = HashTableAdd(ht, NULL, 4);
368  if (r == 0)
369  goto end;
370 
371  /* all is good! */
372  result = 1;
373 end:
374  if (ht != NULL) HashTableFree(ht);
375  return result;
376 }
377 
378 static int HashTableTestFull01 (void)
379 {
380  int result = 0;
381  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
382  if (ht == NULL)
383  goto end;
384 
385  int r = HashTableAdd(ht, (char *)"test", 4);
386  if (r != 0)
387  goto end;
388 
389  char *rp = HashTableLookup(ht, (char *)"test", 4);
390  if (rp == NULL)
391  goto end;
392 
393  r = HashTableRemove(ht, (char *)"test", 4);
394  if (r != 0)
395  goto end;
396 
397  /* all is good! */
398  result = 1;
399 end:
400  if (ht != NULL) HashTableFree(ht);
401  return result;
402 }
403 
404 static int HashTableTestFull02 (void)
405 {
406  int result = 0;
407  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
408  if (ht == NULL)
409  goto end;
410 
411  int r = HashTableAdd(ht, (char *)"test", 4);
412  if (r != 0)
413  goto end;
414 
415  char *rp = HashTableLookup(ht, (char *)"test", 4);
416  if (rp == NULL)
417  goto end;
418 
419  r = HashTableRemove(ht, (char *)"test2", 5);
420  if (r == 0)
421  goto end;
422 
423  /* all is good! */
424  result = 1;
425 end:
426  if (ht != NULL) HashTableFree(ht);
427  return result;
428 }
429 
430 static int HashTableTestCollisionBug(void)
431 {
432  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
433  FAIL_IF_NULL(ht);
434 
435  FAIL_IF_NOT(HashTableGenericHash(ht, (void *)"abc", 3) ==
436  HashTableGenericHash(ht, (void *)"iln", 3));
437 
438  // Add two strings that collide in the same bucket
439  FAIL_IF_NOT(HashTableAdd(ht, (char *)"abc", 3) == 0);
440  FAIL_IF_NOT(HashTableAdd(ht, (char *)"iln", 3) == 0);
441 
442  // Verify both keys are present
443  FAIL_IF_NULL(HashTableLookup(ht, (char *)"abc", 3));
444  FAIL_IF_NULL(HashTableLookup(ht, (char *)"iln", 3));
445 
446  // Remove first key once
447  FAIL_IF_NOT(HashTableRemove(ht, (char *)"abc", 3) == 0);
448 
449  // Verify first key is gone, second key remains
450  FAIL_IF_NOT_NULL(HashTableLookup(ht, (char *)"abc", 3));
451  FAIL_IF_NULL(HashTableLookup(ht, (char *)"iln", 3));
452 
453  // Remove first key again (should not affect "iln")
454  FAIL_IF(HashTableRemove(ht, (char *)"abc", 3) == 0);
455 
456  // Verify second key is still present (correct behavior)
457  FAIL_IF_NULL(HashTableLookup(ht, (char *)"iln", 3));
458 
459  HashTableFree(ht);
460  PASS;
461 }
462 #endif
463 
465 {
466 #ifdef UNITTESTS
467  UtRegisterTest("HashTableTestInit01", HashTableTestInit01);
468  UtRegisterTest("HashTableTestInit02", HashTableTestInit02);
469  UtRegisterTest("HashTableTestInit03", HashTableTestInit03);
470  UtRegisterTest("HashTableTestInit04", HashTableTestInit04);
471  UtRegisterTest("HashTableTestInit05", HashTableTestInit05);
472  UtRegisterTest("HashTableTestInit06", HashTableTestInit06);
473 
474  UtRegisterTest("HashTableTestAdd01", HashTableTestAdd01);
475  UtRegisterTest("HashTableTestAdd02", HashTableTestAdd02);
476 
477  UtRegisterTest("HashTableTestFull01", HashTableTestFull01);
478  UtRegisterTest("HashTableTestFull02", HashTableTestFull02);
479  UtRegisterTest("HashTableTestCollisionBug", HashTableTestCollisionBug);
480 #endif
481 }
FAIL_IF_NULL
#define FAIL_IF_NULL(expr)
Fail a test if expression evaluates to NULL.
Definition: util-unittest.h:89
HashTableDefaultCompare
char HashTableDefaultCompare(void *data1, uint16_t len1, void *data2, uint16_t len2)
Definition: util-hash.c:242
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
HashTableIterate
void HashTableIterate(HashTable *ht, void(*CallbackFn)(void *, void *), void *aux)
Definition: util-hash.c:211
util-hash.h
HashTable_
Definition: util-hash.h:35
util-unittest.h
FAIL_IF_NOT
#define FAIL_IF_NOT(expr)
Fail a test if expression evaluates to false.
Definition: util-unittest.h:82
HashTableBucket_::size
uint16_t size
Definition: util-hash.h:30
HashTableFree
void HashTableFree(HashTable *ht)
Free a HashTable and all its contents.
Definition: util-hash.c:100
HashTable_::array_size
uint32_t array_size
Definition: util-hash.h:37
util-memcmp.h
HashTableBucket_
Definition: util-hash.h:28
FAIL_IF_NOT_NULL
#define FAIL_IF_NOT_NULL(expr)
Fail a test if expression evaluates to non-NULL.
Definition: util-unittest.h:96
util-debug.h
PASS
#define PASS
Pass the test.
Definition: util-unittest.h:105
HashTable_::Compare
char(* Compare)(void *, uint16_t, void *, uint16_t)
Definition: util-hash.h:42
HashTableRegisterTests
void HashTableRegisterTests(void)
Definition: util-hash.c:464
HashTableLookup
void * HashTableLookup(HashTable *ht, void *data, uint16_t datalen)
Definition: util-hash.c:182
HashTableRemove
int HashTableRemove(HashTable *ht, void *data, uint16_t datalen)
Remove an item from the hash table.
Definition: util-hash.c:166
SCLogWarning
#define SCLogWarning(...)
Macro used to log WARNING messages.
Definition: util-debug.h:255
HashTableAdd
int HashTableAdd(HashTable *ht, void *data, uint16_t datalen)
Definition: util-hash.c:120
HashTable_::array
HashTableBucket ** array
Definition: util-hash.h:36
HashTableBucket_::next
struct HashTableBucket_ * next
Definition: util-hash.h:31
FAIL_IF
#define FAIL_IF(expr)
Fail a test if expression evaluates to true.
Definition: util-unittest.h:71
suricata-common.h
HashTable_::count
uint32_t count
Definition: util-hash.h:39
SCFree
#define SCFree(p)
Definition: util-mem.h:61
HashTableInit
HashTable * HashTableInit(uint32_t size, uint32_t(*Hash)(struct HashTable_ *, void *, uint16_t), char(*Compare)(void *, uint16_t, void *, uint16_t), void(*Free)(void *))
Definition: util-hash.c:35
HashTableBucket_::data
void * data
Definition: util-hash.h:29
HashTableGenericHash
uint32_t HashTableGenericHash(HashTable *ht, void *data, uint16_t datalen)
Definition: util-hash.c:225
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