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