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