diff options
author | Jon Santmyer <jon@jonsantmyer.com> | 2024-03-11 21:30:31 -0400 |
---|---|---|
committer | Jon Santmyer <jon@jonsantmyer.com> | 2024-03-11 21:30:31 -0400 |
commit | d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d (patch) | |
tree | 8f0b5cd8aad31089131785dc6e37b659490f9955 /lib/hashtable.c | |
download | jove-kernel-d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d.tar.gz jove-kernel-d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d.tar.bz2 jove-kernel-d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d.zip |
usermode capable kernel with logging syscall
Diffstat (limited to 'lib/hashtable.c')
-rw-r--r-- | lib/hashtable.c | 109 |
1 files changed, 109 insertions, 0 deletions
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; +} |