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 
79 {
80  uint32_t i = 0;
81 
82  if (ht == NULL)
83  return;
84 
85  /* free the buckets */
86  for (i = 0; i < ht->array_size; i++) {
87  HashTableBucket *hashbucket = ht->array[i];
88  while (hashbucket != NULL) {
89  HashTableBucket *next_hashbucket = hashbucket->next;
90  if (ht->Free != NULL)
91  ht->Free(hashbucket->data);
92  SCFree(hashbucket);
93  hashbucket = next_hashbucket;
94  }
95  }
96 
97  /* free the array */
98  if (ht->array != NULL)
99  SCFree(ht->array);
100 
101  SCFree(ht);
102 }
103 
104 int HashTableAdd(HashTable *ht, void *data, uint16_t datalen)
105 {
106  if (ht == NULL || data == NULL)
107  return -1;
108 
109  uint32_t hash = ht->Hash(ht, data, datalen);
110 
111  HashTableBucket *hb = SCCalloc(1, sizeof(HashTableBucket));
112  if (unlikely(hb == NULL))
113  goto error;
114  hb->data = data;
115  hb->size = datalen;
116  hb->next = NULL;
117 
118  if (hash >= ht->array_size) {
119  SCLogWarning("attempt to insert element out of hash array\n");
120  goto error;
121  }
122 
123  if (ht->array[hash] == NULL) {
124  ht->array[hash] = hb;
125  } else {
126  hb->next = ht->array[hash];
127  ht->array[hash] = hb;
128  }
129 
130 #ifdef UNITTESTS
131  ht->count++;
132 #endif
133 
134  return 0;
135 
136 error:
137  if (hb != NULL)
138  SCFree(hb);
139  return -1;
140 }
141 
142 int HashTableRemove(HashTable *ht, void *data, uint16_t datalen)
143 {
144  uint32_t hash = ht->Hash(ht, data, datalen);
145 
146  if (ht->array[hash] == NULL) {
147  return -1;
148  }
149 
150  if (ht->array[hash]->next == NULL) {
151  if (ht->Free != NULL)
152  ht->Free(ht->array[hash]->data);
153  SCFree(ht->array[hash]);
154  ht->array[hash] = NULL;
155  return 0;
156  }
157 
158  HashTableBucket *hashbucket = ht->array[hash], *prev_hashbucket = NULL;
159  do {
160  if (ht->Compare(hashbucket->data,hashbucket->size,data,datalen) == 1) {
161  if (prev_hashbucket == NULL) {
162  /* root bucket */
163  ht->array[hash] = hashbucket->next;
164  } else {
165  /* child bucket */
166  prev_hashbucket->next = hashbucket->next;
167  }
168 
169  /* remove this */
170  if (ht->Free != NULL)
171  ht->Free(hashbucket->data);
172  SCFree(hashbucket);
173  return 0;
174  }
175 
176  prev_hashbucket = hashbucket;
177  hashbucket = hashbucket->next;
178  } while (hashbucket != NULL);
179 
180  return -1;
181 }
182 
183 void *HashTableLookup(HashTable *ht, void *data, uint16_t datalen)
184 {
185  uint32_t hash = 0;
186 
187  if (ht == NULL)
188  return NULL;
189 
190  hash = ht->Hash(ht, data, datalen);
191 
192  if (hash >= ht->array_size) {
193  SCLogWarning("attempt to access element out of hash array\n");
194  return NULL;
195  }
196 
197  if (ht->array[hash] == NULL)
198  return NULL;
199 
200  HashTableBucket *hashbucket = ht->array[hash];
201  do {
202  if (ht->Compare(hashbucket->data, hashbucket->size, data, datalen) == 1)
203  return hashbucket->data;
204 
205  hashbucket = hashbucket->next;
206  } while (hashbucket != NULL);
207 
208  return NULL;
209 }
210 
211 // CallbackFn is an iterator, first argument is the data, second is user auxilary data
212 void HashTableIterate(HashTable *ht, void (*CallbackFn)(void *, void *), void *aux)
213 {
214  if (ht == NULL || CallbackFn == NULL)
215  return;
216 
217  for (uint32_t i = 0; i < ht->array_size; i++) {
218  HashTableBucket *hashbucket = ht->array[i];
219  while (hashbucket != NULL) {
220  CallbackFn(hashbucket->data, aux);
221  hashbucket = hashbucket->next;
222  }
223  }
224 }
225 
226 uint32_t HashTableGenericHash(HashTable *ht, void *data, uint16_t datalen)
227 {
228  uint8_t *d = (uint8_t *)data;
229  uint32_t i;
230  uint32_t hash = 0;
231 
232  for (i = 0; i < datalen; i++) {
233  if (i == 0) hash += (((uint32_t)*d++));
234  else if (i == 1) hash += (((uint32_t)*d++) * datalen);
235  else hash *= (((uint32_t)*d++) * i) + datalen + i;
236  }
237 
238  hash *= datalen;
239  hash %= ht->array_size;
240  return hash;
241 }
242 
243 char HashTableDefaultCompare(void *data1, uint16_t len1, void *data2, uint16_t len2)
244 {
245  if (len1 != len2)
246  return 0;
247 
248  if (SCMemcmp(data1,data2,len1) != 0)
249  return 0;
250 
251  return 1;
252 }
253 
254 /*
255  * ONLY TESTS BELOW THIS COMMENT
256  */
257 
258 #ifdef UNITTESTS
259 static int HashTableTestInit01 (void)
260 {
261  HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
262  if (ht == NULL)
263  return 0;
264 
265  HashTableFree(ht);
266  return 1;
267 }
268 
269 /* no hash function, so it should fail */
270 static int HashTableTestInit02 (void)
271 {
272  HashTable *ht = HashTableInit(1024, NULL, NULL, NULL);
273  if (ht == NULL)
274  return 1;
275 
276  HashTableFree(ht);
277  return 0;
278 }
279 
280 static int HashTableTestInit03 (void)
281 {
282  int result = 0;
283  HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
284  if (ht == NULL)
285  return 0;
286 
287  if (ht->Hash == HashTableGenericHash)
288  result = 1;
289 
290  HashTableFree(ht);
291  return result;
292 }
293 
294 static int HashTableTestInit04 (void)
295 {
296  HashTable *ht = HashTableInit(0, HashTableGenericHash, NULL, NULL);
297  if (ht == NULL)
298  return 1;
299 
300  HashTableFree(ht);
301  return 0;
302 }
303 
304 static int HashTableTestInit05 (void)
305 {
306  int result = 0;
307  HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
308  if (ht == NULL)
309  return 0;
310 
311  if (ht->Compare == HashTableDefaultCompare)
312  result = 1;
313 
314  HashTableFree(ht);
315  return result;
316 }
317 
318 static char HashTableDefaultCompareTest(void *data1, uint16_t len1, void *data2, uint16_t len2)
319 {
320  if (len1 != len2)
321  return 0;
322 
323  if (SCMemcmp(data1,data2,len1) != 0)
324  return 0;
325 
326  return 1;
327 }
328 
329 static int HashTableTestInit06 (void)
330 {
331  int result = 0;
332  HashTable *ht = HashTableInit(1024, HashTableGenericHash, HashTableDefaultCompareTest, NULL);
333  if (ht == NULL)
334  return 0;
335 
336  if (ht->Compare == HashTableDefaultCompareTest)
337  result = 1;
338 
339  HashTableFree(ht);
340  return result;
341 }
342 
343 static int HashTableTestAdd01 (void)
344 {
345  int result = 0;
346  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
347  if (ht == NULL)
348  goto end;
349 
350  int r = HashTableAdd(ht, (char *)"test", 0);
351  if (r != 0)
352  goto end;
353 
354  /* all is good! */
355  result = 1;
356 end:
357  if (ht != NULL) HashTableFree(ht);
358  return result;
359 }
360 
361 static int HashTableTestAdd02 (void)
362 {
363  int result = 0;
364  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
365  if (ht == NULL)
366  goto end;
367 
368  int r = HashTableAdd(ht, NULL, 4);
369  if (r == 0)
370  goto end;
371 
372  /* all is good! */
373  result = 1;
374 end:
375  if (ht != NULL) HashTableFree(ht);
376  return result;
377 }
378 
379 static int HashTableTestFull01 (void)
380 {
381  int result = 0;
382  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
383  if (ht == NULL)
384  goto end;
385 
386  int r = HashTableAdd(ht, (char *)"test", 4);
387  if (r != 0)
388  goto end;
389 
390  char *rp = HashTableLookup(ht, (char *)"test", 4);
391  if (rp == NULL)
392  goto end;
393 
394  r = HashTableRemove(ht, (char *)"test", 4);
395  if (r != 0)
396  goto end;
397 
398  /* all is good! */
399  result = 1;
400 end:
401  if (ht != NULL) HashTableFree(ht);
402  return result;
403 }
404 
405 static int HashTableTestFull02 (void)
406 {
407  int result = 0;
408  HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
409  if (ht == NULL)
410  goto end;
411 
412  int r = HashTableAdd(ht, (char *)"test", 4);
413  if (r != 0)
414  goto end;
415 
416  char *rp = HashTableLookup(ht, (char *)"test", 4);
417  if (rp == NULL)
418  goto end;
419 
420  r = HashTableRemove(ht, (char *)"test2", 5);
421  if (r == 0)
422  goto end;
423 
424  /* all is good! */
425  result = 1;
426 end:
427  if (ht != NULL) HashTableFree(ht);
428  return result;
429 }
430 #endif
431 
433 {
434 #ifdef UNITTESTS
435  UtRegisterTest("HashTableTestInit01", HashTableTestInit01);
436  UtRegisterTest("HashTableTestInit02", HashTableTestInit02);
437  UtRegisterTest("HashTableTestInit03", HashTableTestInit03);
438  UtRegisterTest("HashTableTestInit04", HashTableTestInit04);
439  UtRegisterTest("HashTableTestInit05", HashTableTestInit05);
440  UtRegisterTest("HashTableTestInit06", HashTableTestInit06);
441 
442  UtRegisterTest("HashTableTestAdd01", HashTableTestAdd01);
443  UtRegisterTest("HashTableTestAdd02", HashTableTestAdd02);
444 
445  UtRegisterTest("HashTableTestFull01", HashTableTestFull01);
446  UtRegisterTest("HashTableTestFull02", HashTableTestFull02);
447 #endif
448 }
449 
HashTableDefaultCompare
char HashTableDefaultCompare(void *data1, uint16_t len1, void *data2, uint16_t len2)
Definition: util-hash.c:243
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:212
util-hash.h
HashTable_
Definition: util-hash.h:35
util-unittest.h
HashTableBucket_::size
uint16_t size
Definition: util-hash.h:30
HashTableFree
void HashTableFree(HashTable *ht)
Definition: util-hash.c:78
HashTable_::array_size
uint32_t array_size
Definition: util-hash.h:37
util-memcmp.h
HashTableBucket_
Definition: util-hash.h:28
util-debug.h
HashTable_::Compare
char(* Compare)(void *, uint16_t, void *, uint16_t)
Definition: util-hash.h:42
HashTableRegisterTests
void HashTableRegisterTests(void)
Definition: util-hash.c:432
HashTableLookup
void * HashTableLookup(HashTable *ht, void *data, uint16_t datalen)
Definition: util-hash.c:183
HashTableRemove
int HashTableRemove(HashTable *ht, void *data, uint16_t datalen)
Definition: util-hash.c:142
SCLogWarning
#define SCLogWarning(...)
Macro used to log WARNING messages.
Definition: util-debug.h:249
HashTableAdd
int HashTableAdd(HashTable *ht, void *data, uint16_t datalen)
Definition: util-hash.c:104
HashTable_::array
HashTableBucket ** array
Definition: util-hash.h:36
HashTableBucket_::next
struct HashTableBucket_ * next
Definition: util-hash.h:31
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:226
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