1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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;
}
|
