lib: added simple hash table implemenation

1 files changed, 109 insertions, 0 deletions

diff --git a/lib/hashtable.h b/lib/hashtable.h
new file mode 100644
index 0000000..ff501cc
--- /dev/null
+++ b/lib/hashtable.h
@@ -0,0 +1,109 @@
+#ifndef __HASHMAP__
+#define __HASHMAP__
+
+#include <openssl/sha.h>
+#include <string.h>
+#include "circulardoublelinkedlist.h"
+#include "util.h"
+
+struct ht_item {
+	char *hash;
+	void *data;
+	unsigned int data_length;
+	struct list list;
+};
+
+struct hashtable {
+	struct ht_item **begin;
+	unsigned int length;
+	unsigned int hash_length;
+	void (*hash_function)(void *data, unsigned int data_length, char *res);
+};
+
+
+int __ht_init(struct hashtable *ht, unsigned int number_elem,
+		unsigned int hash_length, void (*func)(void *data,
+		unsigned int data_length, char *res))
+{
+	ht->begin = xmalloc(sizeof(struct ht_item)*number_elem);
+	ht->length = number_elem;
+	ht->hash_length = hash_length;
+	ht->hash_function = func;
+}
+
+void compute_hash_sha1(void *data, unsigned int data_length, char *res)
+{
+	SHA_CTX sha1;
+
+	SHA1_Init(&sha1);
+	SHA1_Update(&sha1, data, data_length);
+	SHA1_Final(res, &sha1);
+
+}
+
+int ht_init_sha1(struct hashtable *ht)
+{
+	__ht_init(ht, 300, 20, compute_hash_sha1);
+}
+
+void *ht_is_in_list(struct list *list, char *hash, int hash_length)
+{
+	struct list *head, *iter;
+	struct ht_item *res = NULL;
+
+	head = list;
+	res = CONTAINER_OF(head, struct ht_item, list);
+	if(memcmp(res->hash, hash, hash_length) == 0)
+		return res->data;
+
+	LIST_FOR_EACH(iter,head) {
+		res = CONTAINER_OF(iter, struct ht_item, list);
+		if(memcmp(res->hash, hash, hash_length) == 0)
+			return res->data;
+	}
+
+	return NULL;
+}
+
+void ht_add(struct hashtable *ht, void *data, unsigned int data_length,
+		void *key, unsigned int key_length)
+{
+	unsigned long index;
+	struct ht_item *new_elem = xmalloc(sizeof(struct ht_item));
+	new_elem->hash =  xmalloc(ht->hash_length);
+	new_elem->data = xmalloc(data_length);
+
+	memcpy(new_elem->data, data, data_length);
+	new_elem->data_length = data_length;
+	LIST_INIT(&new_elem->list);
+
+	ht->hash_function(key, key_length, new_elem->hash);
+	memcpy(&index, new_elem->hash, sizeof(unsigned long));
+	index = index % ht->length;
+
+	if(ht->begin[index] == NULL) {
+		ht->begin[index] = new_elem;
+		return;
+	}
+
+	if(ht_is_in_list(&(ht->begin[index]->list), new_elem->hash,
+			ht->hash_length) == NULL) {
+		list_insert_after(&(ht->begin[index]->list), &new_elem->list);
+		printf("kollision\n");
+		return;
+	}
+}
+
+void *ht_get(struct hashtable *ht, void *key, unsigned int key_length)
+{
+	char *hash = xmalloc(ht->hash_length);
+	unsigned long index;
+
+	ht->hash_function(key, key_length, hash);
+	memcpy(&index, hash, sizeof(unsigned long));
+	index = index % ht->length;
+
+	return ht_is_in_list(&(ht->begin[index]->list), hash, ht->hash_length);
+}
+
+#endif