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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
#include <stdlib.h>
#include <errno.h>
#include "common.h"
#include "hashtable.h"
#include "mempool.h"
MEMPOOL_GENERATE(ht, struct hashtable, 32)
MEMPOOL_GENERATE(hi, struct hashtable_item, 128)
// TODO:
// - insertion options
#define HASH(ht, key) (ht->hash_func(key) % ht->cap)
static int hashtable_grow(hashtable_t ht, size_t cap);
static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev);
static void hashtable_table_append_item(struct hashtable_item ** table, size_t idx, struct hashtable_item *item);
hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func)
{
hashtable_t ht;
// ERR_Z(ht = malloc(sizeof(*ht)), goto fail);
ht = ht_mempool_allocate();
ht->hash_func = hash_func;
ht->equal_func = equal_func;
ht->cap = 0;
ht->size = 0;
ERR_ERRNO_SET(hashtable_grow(ht, cap), goto fail);
return ht;
fail:
hashtable_destroy(ht);
return NULL;
}
void hashtable_destroy(hashtable_t ht)
{
if(!ht) return;
if(ht->table) {
hashtable_for_each_item_safe(ht, item, i) {
// free(item);
hi_mempool_free(item);
}
free(ht->table);
}
// free(ht);
ht_mempool_free(ht);
}
void hashtable_reset(hashtable_t ht)
{
if(!ht) return;
if(ht->table) {
hashtable_for_each_item_safe(ht, item, i) {
// free(item);
hi_mempool_free(item);
}
}
ht->size = 0;
}
int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void **prevdata)
{
size_t idx = HASH(ht, key);
struct hashtable_item *item, *prev;
hashtable_find_item(ht, idx, key, &item, &prev);
if(item) {
if(prevkey) *prevkey = item->key;
if(prevdata) *prevdata = item->data;
item->key = key;
item->data = data;
return 0;
}
// ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM);
item = hi_mempool_allocate();
item->key = key;
item->data = data;
item->next = NULL;
hashtable_table_append_item(ht->table, idx, item);
ht->size++;
if(ht->size > (ht->cap * 3/4)) {
return hashtable_grow(ht, ht->cap << 1);
}
return 0;
}
int hashtable_query(hashtable_t ht, void *key, void **data)
{
size_t idx = HASH(ht, key);
struct hashtable_item *item;
ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, NULL));
*data = item->data;
return 0;
}
int hashtable_delete(hashtable_t ht, void *key)
{
size_t idx = HASH(ht, key);
struct hashtable_item *item, *prev;
ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, &prev));
if(prev)
prev->next = item->next;
else
ht->table[idx] = item->next;
free(item);
return 0;
}
static int hashtable_grow(hashtable_t ht, size_t cap)
{
struct hashtable_item **new_table;
ERR_Z(new_table = calloc(cap, sizeof(*new_table)), return -ENOMEM);
if(ht->cap > 0) {
hashtable_for_each_item_safe(ht, item, i) {
// hash but with the new cap
size_t idx = ht->hash_func(item->key) % cap;
hashtable_table_append_item(new_table, idx, item);
}
free(ht->table);
}
ht->table = new_table;
ht->cap = cap;
return 0;
}
static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev)
{
if(item) *item = NULL;
if(prev) *prev = NULL;
hashtable_for_each_item_on_index(ht, _item, idx) {
if(ht->equal_func(_item->key, key)) {
if(item) *item = _item;
return 0;
}
if(prev) *prev = _item;
}
return -ENOENT;
}
static void hashtable_table_append_item(struct hashtable_item **table, size_t idx, struct hashtable_item *item)
{
item->next = table[idx];
table[idx] = item;
}
|
