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