#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;
}