Add hash table implementation

uoo723 · Jun 22, 2017 · 242bcc6 · 242bcc6
1 parent ec4f378
commit 242bcc6
Show file tree

Hide file tree

Showing 5 changed files with 163 additions and 1 deletion.
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -7,3 +7,4 @@ file(GLOB SOURCES "src/*.c")
 
 add_executable(main ${SOURCES})
 add_executable(node_test "test/node_test.c" "src/node.c")
+add_executable(hash_test "test/hash_test.c" "src/node.c" "src/hashtable.c")
diff --git a/include/hashtable.h b/include/hashtable.h
@@ -0,0 +1,18 @@
+#ifndef HASHTABLE_H
+#define HASHTABLE_H
+
+#include "node.h"
+#include "msg.h"
+
+typedef struct hastable {
+    int size;
+    node_t **table;
+} hashtable_t;
+
+hashtable_t *ht_create(int);
+int ht_hash(hashtable_t *, unsigned int);
+int ht_set(hashtable_t *, unsigned int, char *);
+int ht_remove(hashtable_t *, unsigned int);
+node_t *ht_get(hashtable_t *, unsigned int);
+
+#endif
diff --git a/src/hashtable.c b/src/hashtable.c
@@ -0,0 +1,100 @@
+#include <stdlib.h>
+
+#include "hashtable.h"
+#include "node.h"
+
+hashtable_t *ht_create(int size) {
+    hashtable_t *hashtable = NULL;
+
+    if (size < 1) {
+        return NULL;
+    }
+
+    if ((hashtable = malloc(sizeof(hashtable_t))) == NULL) {
+        return NULL;
+    }
+
+    if ((hashtable->table = malloc(sizeof(node_t *) * size)) == NULL) {
+        return NULL;
+    }
+
+    hashtable->size = size;
+
+    return hashtable;
+}
+
+int ht_hash(hashtable_t *hashtable, unsigned int key) {
+    return key % hashtable->size;
+}
+
+int ht_set(hashtable_t *hashtable, unsigned int key, char *value) {
+    int index;
+    node_t *head;
+
+    if (hashtable == NULL) {
+        return -1;
+    }
+
+    index = ht_hash(hashtable, key);
+    head = hashtable->table[index];
+
+    if (head == NULL) {
+        if ((head = ll_create()) == NULL) {
+            return -1;
+        }
+
+        hashtable->table[index] = head;
+    }
+
+    if (ll_insert(head, key, value) < 0) {
+        return -1;
+    }
+
+    return 0;
+}
+
+node_t *ht_get(hashtable_t *hashtable, unsigned int key) {
+    int index;
+    node_t *head;
+    node_t *node;
+
+    if (hashtable == NULL) {
+        return NULL;
+    }
+
+    index = ht_hash(hashtable, key);
+
+    if ((head = hashtable->table[index]) == NULL) {
+        return NULL;
+    }
+
+    if ((node = ll_get(head, key)) == NULL) {
+        return NULL;
+    }
+
+    return node;
+}
+
+#include <stdio.h>
+
+int ht_remove(hashtable_t *hashtable, unsigned int key) {
+    int index;
+    node_t *head;
+
+    if (hashtable == NULL) {
+        return -1;
+    }
+
+    index = ht_hash(hashtable, key);
+
+    if ((head = hashtable->table[index]) == NULL) {
+        return -1;
+    }
+
+    if (ll_remove(head, key) < 0) {
+        printf("key: %d", key);
+        return -1;
+    }
+
+    return 0;
+}
diff --git a/src/node.c b/src/node.c
@@ -47,7 +47,7 @@ int ll_remove(node_t *head, unsigned int key) {
         return -1;
     }
 
-    node_t *iter = head->next;
+    node_t *iter = head;
 
     while (iter != NULL) {
         if (iter->next != NULL && iter->next->key == key) {

diff --git a/test/hash_test.c b/test/hash_test.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include "hashtable.h"
+#include "node.h"
+
+void print_node(node_t *);
+
+int main() {
+    hashtable_t *hashtable;
+
+    printf("Start hash test\n");
+    if ((hashtable = ht_create(1000000)) == NULL) {
+        printf("Failed allocating hashtable\n");
+        return 0;
+    }
+
+    printf("ht_set test\n");
+    ht_set(hashtable, 238, "Han");
+    ht_set(hashtable, 2880, "Sang");
+    ht_set(hashtable, 23023, "Woo");
+    ht_set(hashtable, 23023, "W");
+
+    print_node(ht_get(hashtable, 238));
+    print_node(ht_get(hashtable, 2880));
+    print_node(ht_get(hashtable, 23023));
+    print_node(ht_get(hashtable, 3));
+
+    printf("ht_remove test\n");
+    ht_remove(hashtable, 3);
+    if (ht_remove(hashtable, 2880) < 0) {
+        printf("remove failed\n");
+    }
+    print_node(ht_get(hashtable, 2880));
+    return 0;
+}
+
+void print_node(node_t *node) {
+    if (node == NULL) {
+        printf("node is null\n");
+        return;
+    }
+    printf("key: %d, value: %s\n", node->key, node->value);
+}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -7,3 +7,4 @@ file(GLOB SOURCES "src/*.c")

		add_executable(main ${SOURCES})
		add_executable(node_test "test/node_test.c" "src/node.c")
		add_executable(hash_test "test/hash_test.c" "src/node.c" "src/hashtable.c")