summaryrefslogtreecommitdiffstats
path: root/src/util-hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util-hash.c')
-rw-r--r--src/util-hash.c445
1 files changed, 445 insertions, 0 deletions
diff --git a/src/util-hash.c b/src/util-hash.c
new file mode 100644
index 0000000..d94d46f
--- /dev/null
+++ b/src/util-hash.c
@@ -0,0 +1,445 @@
+/* Copyright (C) 2007-2010 Open Information Security Foundation
+ *
+ * You can copy, redistribute or modify this Program under the terms of
+ * the GNU General Public License version 2 as published by the Free
+ * Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * version 2 along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+/**
+ * \file
+ *
+ * \author Victor Julien <victor@inliniac.net>
+ *
+ * Chained hash table implementation
+ *
+ * The 'Free' pointer can be used to have the API free your
+ * hashed data. If it's NULL it's the callers responsibility
+ */
+
+#include "suricata-common.h"
+#include "util-hash.h"
+#include "util-unittest.h"
+#include "util-memcmp.h"
+#include "util-debug.h"
+
+HashTable* HashTableInit(uint32_t size, uint32_t (*Hash)(struct HashTable_ *, void *, uint16_t), char (*Compare)(void *, uint16_t, void *, uint16_t), void (*Free)(void *)) {
+
+ HashTable *ht = NULL;
+
+ if (size == 0) {
+ goto error;
+ }
+
+ if (Hash == NULL) {
+ //printf("ERROR: HashTableInit no Hash function\n");
+ goto error;
+ }
+
+ /* setup the filter */
+ ht = SCMalloc(sizeof(HashTable));
+ if (unlikely(ht == NULL))
+ goto error;
+ memset(ht,0,sizeof(HashTable));
+ ht->array_size = size;
+ ht->Hash = Hash;
+ ht->Free = Free;
+
+ if (Compare != NULL)
+ ht->Compare = Compare;
+ else
+ ht->Compare = HashTableDefaultCompare;
+
+ /* setup the bitarray */
+ ht->array = SCMalloc(ht->array_size * sizeof(HashTableBucket *));
+ if (ht->array == NULL)
+ goto error;
+ memset(ht->array,0,ht->array_size * sizeof(HashTableBucket *));
+
+ return ht;
+
+error:
+ if (ht != NULL) {
+ if (ht->array != NULL)
+ SCFree(ht->array);
+
+ SCFree(ht);
+ }
+ return NULL;
+}
+
+void HashTableFree(HashTable *ht)
+{
+ uint32_t i = 0;
+
+ if (ht == NULL)
+ return;
+
+ /* free the buckets */
+ for (i = 0; i < ht->array_size; i++) {
+ HashTableBucket *hashbucket = ht->array[i];
+ while (hashbucket != NULL) {
+ HashTableBucket *next_hashbucket = hashbucket->next;
+ if (ht->Free != NULL)
+ ht->Free(hashbucket->data);
+ SCFree(hashbucket);
+ hashbucket = next_hashbucket;
+ }
+ }
+
+ /* free the array */
+ if (ht->array != NULL)
+ SCFree(ht->array);
+
+ SCFree(ht);
+}
+
+void HashTablePrint(HashTable *ht)
+{
+ printf("\n----------- Hash Table Stats ------------\n");
+ printf("Buckets: %" PRIu32 "\n", ht->array_size);
+ printf("Hash function pointer: %p\n", ht->Hash);
+ printf("-----------------------------------------\n");
+}
+
+int HashTableAdd(HashTable *ht, void *data, uint16_t datalen)
+{
+ if (ht == NULL || data == NULL)
+ return -1;
+
+ uint32_t hash = ht->Hash(ht, data, datalen);
+
+ HashTableBucket *hb = SCMalloc(sizeof(HashTableBucket));
+ if (unlikely(hb == NULL))
+ goto error;
+ memset(hb, 0, sizeof(HashTableBucket));
+ hb->data = data;
+ hb->size = datalen;
+ hb->next = NULL;
+
+ if (hash >= ht->array_size) {
+ SCLogWarning("attempt to insert element out of hash array\n");
+ goto error;
+ }
+
+ if (ht->array[hash] == NULL) {
+ ht->array[hash] = hb;
+ } else {
+ hb->next = ht->array[hash];
+ ht->array[hash] = hb;
+ }
+
+#ifdef UNITTESTS
+ ht->count++;
+#endif
+
+ return 0;
+
+error:
+ if (hb != NULL)
+ SCFree(hb);
+ return -1;
+}
+
+int HashTableRemove(HashTable *ht, void *data, uint16_t datalen)
+{
+ uint32_t hash = ht->Hash(ht, data, datalen);
+
+ if (ht->array[hash] == NULL) {
+ return -1;
+ }
+
+ if (ht->array[hash]->next == NULL) {
+ if (ht->Free != NULL)
+ ht->Free(ht->array[hash]->data);
+ SCFree(ht->array[hash]);
+ ht->array[hash] = NULL;
+ return 0;
+ }
+
+ HashTableBucket *hashbucket = ht->array[hash], *prev_hashbucket = NULL;
+ do {
+ if (ht->Compare(hashbucket->data,hashbucket->size,data,datalen) == 1) {
+ if (prev_hashbucket == NULL) {
+ /* root bucket */
+ ht->array[hash] = hashbucket->next;
+ } else {
+ /* child bucket */
+ prev_hashbucket->next = hashbucket->next;
+ }
+
+ /* remove this */
+ if (ht->Free != NULL)
+ ht->Free(hashbucket->data);
+ SCFree(hashbucket);
+ return 0;
+ }
+
+ prev_hashbucket = hashbucket;
+ hashbucket = hashbucket->next;
+ } while (hashbucket != NULL);
+
+ return -1;
+}
+
+void *HashTableLookup(HashTable *ht, void *data, uint16_t datalen)
+{
+ uint32_t hash = 0;
+
+ if (ht == NULL)
+ return NULL;
+
+ hash = ht->Hash(ht, data, datalen);
+
+ if (hash >= ht->array_size) {
+ SCLogWarning("attempt to access element out of hash array\n");
+ return NULL;
+ }
+
+ if (ht->array[hash] == NULL)
+ return NULL;
+
+ HashTableBucket *hashbucket = ht->array[hash];
+ do {
+ if (ht->Compare(hashbucket->data, hashbucket->size, data, datalen) == 1)
+ return hashbucket->data;
+
+ hashbucket = hashbucket->next;
+ } while (hashbucket != NULL);
+
+ return NULL;
+}
+
+uint32_t HashTableGenericHash(HashTable *ht, void *data, uint16_t datalen)
+{
+ uint8_t *d = (uint8_t *)data;
+ uint32_t i;
+ uint32_t hash = 0;
+
+ for (i = 0; i < datalen; i++) {
+ if (i == 0) hash += (((uint32_t)*d++));
+ else if (i == 1) hash += (((uint32_t)*d++) * datalen);
+ else hash *= (((uint32_t)*d++) * i) + datalen + i;
+ }
+
+ hash *= datalen;
+ hash %= ht->array_size;
+ return hash;
+}
+
+char HashTableDefaultCompare(void *data1, uint16_t len1, void *data2, uint16_t len2)
+{
+ if (len1 != len2)
+ return 0;
+
+ if (SCMemcmp(data1,data2,len1) != 0)
+ return 0;
+
+ return 1;
+}
+
+/*
+ * ONLY TESTS BELOW THIS COMMENT
+ */
+
+#ifdef UNITTESTS
+static int HashTableTestInit01 (void)
+{
+ HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ return 0;
+
+ HashTableFree(ht);
+ return 1;
+}
+
+/* no hash function, so it should fail */
+static int HashTableTestInit02 (void)
+{
+ HashTable *ht = HashTableInit(1024, NULL, NULL, NULL);
+ if (ht == NULL)
+ return 1;
+
+ HashTableFree(ht);
+ return 0;
+}
+
+static int HashTableTestInit03 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ return 0;
+
+ if (ht->Hash == HashTableGenericHash)
+ result = 1;
+
+ HashTableFree(ht);
+ return result;
+}
+
+static int HashTableTestInit04 (void)
+{
+ HashTable *ht = HashTableInit(0, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ return 1;
+
+ HashTableFree(ht);
+ return 0;
+}
+
+static int HashTableTestInit05 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(1024, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ return 0;
+
+ if (ht->Compare == HashTableDefaultCompare)
+ result = 1;
+
+ HashTableFree(ht);
+ return result;
+}
+
+static char HashTableDefaultCompareTest(void *data1, uint16_t len1, void *data2, uint16_t len2)
+{
+ if (len1 != len2)
+ return 0;
+
+ if (SCMemcmp(data1,data2,len1) != 0)
+ return 0;
+
+ return 1;
+}
+
+static int HashTableTestInit06 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(1024, HashTableGenericHash, HashTableDefaultCompareTest, NULL);
+ if (ht == NULL)
+ return 0;
+
+ if (ht->Compare == HashTableDefaultCompareTest)
+ result = 1;
+
+ HashTableFree(ht);
+ return result;
+}
+
+static int HashTableTestAdd01 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ goto end;
+
+ int r = HashTableAdd(ht, (char *)"test", 0);
+ if (r != 0)
+ goto end;
+
+ /* all is good! */
+ result = 1;
+end:
+ if (ht != NULL) HashTableFree(ht);
+ return result;
+}
+
+static int HashTableTestAdd02 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ goto end;
+
+ int r = HashTableAdd(ht, NULL, 4);
+ if (r == 0)
+ goto end;
+
+ /* all is good! */
+ result = 1;
+end:
+ if (ht != NULL) HashTableFree(ht);
+ return result;
+}
+
+static int HashTableTestFull01 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ goto end;
+
+ int r = HashTableAdd(ht, (char *)"test", 4);
+ if (r != 0)
+ goto end;
+
+ char *rp = HashTableLookup(ht, (char *)"test", 4);
+ if (rp == NULL)
+ goto end;
+
+ r = HashTableRemove(ht, (char *)"test", 4);
+ if (r != 0)
+ goto end;
+
+ /* all is good! */
+ result = 1;
+end:
+ if (ht != NULL) HashTableFree(ht);
+ return result;
+}
+
+static int HashTableTestFull02 (void)
+{
+ int result = 0;
+ HashTable *ht = HashTableInit(32, HashTableGenericHash, NULL, NULL);
+ if (ht == NULL)
+ goto end;
+
+ int r = HashTableAdd(ht, (char *)"test", 4);
+ if (r != 0)
+ goto end;
+
+ char *rp = HashTableLookup(ht, (char *)"test", 4);
+ if (rp == NULL)
+ goto end;
+
+ r = HashTableRemove(ht, (char *)"test2", 5);
+ if (r == 0)
+ goto end;
+
+ /* all is good! */
+ result = 1;
+end:
+ if (ht != NULL) HashTableFree(ht);
+ return result;
+}
+#endif
+
+void HashTableRegisterTests(void)
+{
+#ifdef UNITTESTS
+ UtRegisterTest("HashTableTestInit01", HashTableTestInit01);
+ UtRegisterTest("HashTableTestInit02", HashTableTestInit02);
+ UtRegisterTest("HashTableTestInit03", HashTableTestInit03);
+ UtRegisterTest("HashTableTestInit04", HashTableTestInit04);
+ UtRegisterTest("HashTableTestInit05", HashTableTestInit05);
+ UtRegisterTest("HashTableTestInit06", HashTableTestInit06);
+
+ UtRegisterTest("HashTableTestAdd01", HashTableTestAdd01);
+ UtRegisterTest("HashTableTestAdd02", HashTableTestAdd02);
+
+ UtRegisterTest("HashTableTestFull01", HashTableTestFull01);
+ UtRegisterTest("HashTableTestFull02", HashTableTestFull02);
+#endif
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-16 05:25:57 +0000