From d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d Mon Sep 17 00:00:00 2001
From: Jon Santmyer <jon@jonsantmyer.com>
Date: Mon, 11 Mar 2024 21:30:31 -0400
Subject: usermode capable kernel with logging syscall

---
 lib/hashtable.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 109 insertions(+)
 create mode 100644 lib/hashtable.c

(limited to 'lib/hashtable.c')

diff --git a/lib/hashtable.c b/lib/hashtable.c
new file mode 100644
index 0000000..17f1e74
--- /dev/null
+++ b/lib/hashtable.c
@@ -0,0 +1,109 @@
+#include "hashtable.h"
+#include "string.h"
+#include "mem/memory.h"
+
+static size_t
+s_hash_function_mul(const void *data, size_t len)
+{
+    size_t hash = 1;
+    const char *cdata = (const char*)data;
+    for(size_t i = 0; i < len; i++) {
+        hash *= ((size_t)cdata[i]) + 1;
+    }
+    return hash;
+}
+
+static size_t
+s_hash_function_mul_s(const void *data, size_t _)
+{
+    return s_hash_function_mul(data, strlen(data));
+}
+
+void
+_hashtable_new(struct HashTable *table, size_t obj_size, size_t key_size)
+{
+    *table = (struct HashTable){
+        .buckets = NULL,
+        .bucket_count = 0,
+        .bucket_capacity = 2,
+        .obj_size = obj_size,
+        .key_size = key_size,
+        .hash_function = s_hash_function_mul
+    };
+    table->buckets = mem_alloc(sizeof(struct SLinkedList) * 2);
+}
+
+void
+_hashtable_news(struct HashTable *table, size_t obj_size)
+{
+    *table = (struct HashTable){
+        .buckets = NULL,
+        .bucket_count = 0,
+        .bucket_capacity = 2,
+        .obj_size = obj_size,
+        .key_size = -1,
+        .hash_function = s_hash_function_mul_s
+    };
+    table->buckets = mem_alloc(sizeof(struct SLinkedList) * 2);
+}
+
+void
+hashtable_insert(struct HashTable *table, const void *key, void *data)
+{
+    size_t hash = table->hash_function(key, table->key_size);
+    if(table->bucket_capacity == table->bucket_count) {
+        struct SLinkedList *old_buckets = table->buckets;
+        size_t old_buckets_count = table->bucket_count;
+
+        table->bucket_capacity *= 2;
+        table->bucket_count = 0;
+        table->buckets = mem_alloc(sizeof(struct SLinkedList) * table->bucket_capacity);
+        for(size_t i = 0; i < old_buckets_count; i++) {
+            for(struct SLLNode *node = old_buckets[i].head; node != NULL; node = node->next) {
+                struct HashTableValue *value = (struct HashTableValue*)(&node->data);
+                hashtable_insert(table, value->key, value->value);
+                mem_free(node);
+            }
+        }
+    }
+
+    size_t index = hash % table->bucket_capacity;
+    struct SLinkedList *bucket = &table->buckets[index];
+    struct SLLNode *node = mem_alloc(sizeof(struct SLLNode) + sizeof(struct HashTableValue) + table->obj_size);
+    struct HashTableValue *value = (struct HashTableValue*)(node->data);
+    
+    value->key = key;
+    memcpy(value->value, data, table->obj_size);
+
+    table->bucket_count++;
+    if(bucket->count == 0) {
+        sll_new(bucket, table->obj_size);
+        sll_push(bucket, node);
+        return;
+    }
+    for(struct SLLNode *onode = bucket->head; onode != NULL; onode = onode->next)
+    {
+        struct HashTableValue *ovalue = (struct HashTableValue*)onode->data;
+        size_t keylen = table->key_size > 0 ? table->key_size : strlen((const char*)key) + 1;
+        if(memcmp(ovalue->key, value->key, keylen) == 0) {
+            memcpy(ovalue->value, value->value, table->obj_size);
+            return;
+        }
+    }
+    sll_push(bucket, node);
+}
+
+void*
+_hashtable_get(struct HashTable *table, const void *key)
+{
+    size_t hash = table->hash_function(key, table->key_size);
+    size_t index = hash % table->bucket_capacity;
+    struct SLinkedList *bucket = &table->buckets[index];
+    for(struct SLLNode *node = bucket->head; node != NULL; node = node->next)
+    {
+        struct HashTableValue *value = (struct HashTableValue*)node->data;
+        size_t keylen = table->key_size > 0 ? table->key_size : strlen((const char*)value->key);
+        if(memcmp(key, value->key, keylen) == 0) return value->value;
+    }
+    return NULL;
+}
-- 
cgit v1.2.1