]>
Commit | Line | Data |
---|---|---|
1d8fe1f7 MR |
1 | #include <string.h> |
2 | #include <stdio.h> | |
3 | #include <stdlib.h> | |
4 | #include "hashtable.h" | |
5 | ||
8c5be416 MR |
6 | typedef struct _Node { |
7 | void* key; | |
1d8fe1f7 | 8 | void* data; |
8c5be416 MR |
9 | struct _Node* next; |
10 | } Node; | |
1d8fe1f7 | 11 | |
8c5be416 | 12 | struct _Hashtable { |
1d8fe1f7 MR |
13 | uint32_t size; |
14 | HashFunc hash; | |
15 | EqualFunc compare; | |
8c5be416 MR |
16 | FreeFunc free; |
17 | Node** nodes; | |
18 | }; | |
19 | ||
20 | typedef struct { | |
21 | Hashtable* table; | |
22 | void* dummy2; | |
23 | void* dummy3; | |
24 | int64_t pos; | |
25 | } RealIter; | |
1d8fe1f7 MR |
26 | |
27 | static uint32_t hash_table_index(Hashtable* ht, const void* key) { | |
28 | return (ht->hash(key) % ht->size); | |
29 | } | |
30 | ||
31 | Hashtable* hash_table_create(HashFunc hf, EqualFunc ef) { | |
8c5be416 MR |
32 | return hash_table_create_full(hf, ef, TABLESIZE, NULL); |
33 | } | |
34 | ||
35 | Hashtable* hash_table_create_notify(HashFunc hf, EqualFunc ef, FreeFunc ff) { | |
36 | return hash_table_create_full(hf, ef, TABLESIZE, ff); | |
1d8fe1f7 MR |
37 | } |
38 | ||
8c5be416 | 39 | Hashtable* hash_table_create_full(HashFunc hf, EqualFunc ef, uint32_t size, FreeFunc ff) { |
1d8fe1f7 MR |
40 | Hashtable* ht = malloc(sizeof(*ht)); |
41 | ht->size = size; | |
42 | ht->hash = hf; | |
43 | ht->compare = ef; | |
8c5be416 MR |
44 | if (ff) { |
45 | ht->free = ff; | |
46 | } else { | |
47 | ht->free = free; | |
48 | } | |
49 | ht->nodes = calloc(sizeof(Node*), ht->size); | |
1d8fe1f7 MR |
50 | return ht; |
51 | } | |
52 | ||
53 | void hash_table_destroy(Hashtable* ht) { | |
54 | for (uint32_t i = 0; i < ht->size; i++) { | |
8c5be416 MR |
55 | while (ht->nodes[i]) { |
56 | Node* node = ht->nodes[i]; | |
57 | ht->nodes[i] = ht->nodes[i]->next; | |
58 | ht->free(node->data); | |
59 | free(node); | |
1d8fe1f7 MR |
60 | } |
61 | } | |
62 | hash_table_print(ht); | |
8c5be416 | 63 | free(ht->nodes); |
1d8fe1f7 MR |
64 | free(ht); |
65 | } | |
66 | ||
67 | void hash_table_print(Hashtable* ht) { | |
68 | printf("Start Table\n"); | |
69 | for (uint32_t i = 0; i < ht->size; i++) { | |
8c5be416 | 70 | if (ht->nodes[i] == NULL) { |
1d8fe1f7 MR |
71 | //printf("\t%i\t---\n", i); |
72 | } else { | |
73 | printf("\t%i\t\n", i); | |
8c5be416 MR |
74 | Node* node = ht->nodes[i]; |
75 | while (node != NULL) { | |
76 | printf("\"%p\" - (%p)", node->key, node->data); | |
77 | node = node->next; | |
1d8fe1f7 MR |
78 | } |
79 | printf("\n"); | |
80 | } | |
81 | } | |
82 | printf("End Table\n"); | |
83 | } | |
84 | ||
85 | bool hash_table_insert(Hashtable* ht, const void* key, void* obj) { | |
86 | if (key == NULL || obj == NULL || ht == NULL) return false; | |
87 | ||
88 | // implement chaning | |
8c5be416 | 89 | if (hash_table_lookup(ht, key) != NULL) return false; |
1d8fe1f7 MR |
90 | |
91 | uint32_t index = hash_table_index(ht, key); | |
92 | ||
8c5be416 MR |
93 | Node* node = malloc(sizeof(*node)); |
94 | node->data = obj; | |
95 | node->key = (void*)key; | |
1d8fe1f7 | 96 | |
8c5be416 MR |
97 | node->next = ht->nodes[index]; |
98 | ht->nodes[index] = node; | |
1d8fe1f7 MR |
99 | return true; |
100 | } | |
101 | ||
102 | void* hash_table_lookup(Hashtable* ht, const void* key) { | |
103 | if (key == NULL || ht == NULL) return false; | |
dd3da95a | 104 | uint32_t index = hash_table_index(ht, key); |
1d8fe1f7 | 105 | |
8c5be416 MR |
106 | Node* node = ht->nodes[index]; |
107 | while (node != NULL && ht->compare(node->data, key) == false) { | |
108 | node = node->next; | |
109 | } | |
110 | ||
111 | if (node == NULL) return NULL; | |
dd3da95a | 112 | //printf("find: %p -> found: %p\n", key, node->data); |
1d8fe1f7 | 113 | |
8c5be416 | 114 | return node->data; |
1d8fe1f7 MR |
115 | } |
116 | ||
117 | void* hash_table_delete(Hashtable* ht, const void* key) { | |
118 | if (key == NULL || ht == NULL) return false; | |
119 | uint64_t index = hash_table_index(ht, key); | |
120 | ||
8c5be416 MR |
121 | Node* node = ht->nodes[index]; |
122 | Node* prev = NULL; | |
123 | while (node != NULL && ht->compare(node->data, key) == false) { | |
124 | prev = node; | |
125 | node = node->next; | |
126 | } | |
127 | ||
128 | if (node == NULL) return NULL; | |
129 | if (prev == NULL) { | |
130 | ht->nodes[index] = node->next; | |
131 | } else{ | |
132 | prev->next = node->next; | |
133 | } | |
1d8fe1f7 | 134 | |
8c5be416 MR |
135 | void* result = node->data; |
136 | free(node); | |
1d8fe1f7 MR |
137 | return result; |
138 | } | |
139 | ||
8c5be416 MR |
140 | List* hash_table_keys(Hashtable* ht) { |
141 | List *keys, *head; | |
142 | keys = head = NULL; | |
143 | ||
144 | if (ht != NULL) { | |
145 | for (uint32_t i = 0; i < ht->size; i++) { | |
146 | if (ht->nodes[i] != NULL) { | |
147 | Node* node = ht->nodes[i]; | |
148 | while (node != NULL) { | |
149 | if (head == NULL) { | |
150 | head = calloc(sizeof(List*), 1); | |
151 | keys = head; | |
152 | } | |
153 | else { | |
154 | head->next = calloc(sizeof(List*), 1); | |
155 | head = head->next; | |
156 | } | |
157 | head->data = ht->nodes[i]->key; | |
158 | node = node->next; | |
159 | } | |
160 | } | |
161 | } | |
162 | } | |
163 | ||
164 | return keys; | |
165 | } | |
166 | ||
167 | List* hash_table_values(Hashtable* ht) { | |
168 | List *values, *head; | |
169 | values = head = NULL; | |
170 | ||
171 | if (ht != NULL) { | |
172 | for (uint32_t i = 0; i < ht->size; i++) { | |
173 | if (ht->nodes[i] != NULL) { | |
174 | Node* node = ht->nodes[i]; | |
175 | while (node != NULL) { | |
176 | if (head == NULL) { | |
177 | head = calloc(sizeof(List*), 1); | |
178 | values = head; | |
179 | } | |
180 | else { | |
181 | head->next = calloc(sizeof(List*), 1); | |
182 | head = head->next; | |
183 | } | |
184 | head->data = ht->nodes[i]->data; | |
185 | node = node->next; | |
186 | } | |
187 | } | |
188 | } | |
189 | } | |
190 | ||
191 | return values; | |
192 | } | |
193 | ||
194 | void hash_table_list_free(List* list) { | |
195 | while (list != NULL) { | |
196 | List* prev = list; | |
197 | list = list->next; | |
198 | free(prev); | |
199 | } | |
200 | } | |
201 | ||
202 | void hash_table_foreach(Hashtable* ht, ForeachFunc ff, void* userdata) { | |
203 | if (ht != NULL) { | |
204 | for (uint32_t i = 0; i < ht->size; i++) { | |
205 | if (ht->nodes[i] != NULL) { | |
206 | Node* node = ht->nodes[i]; | |
207 | while (node != NULL) { | |
208 | ff(node->key, node->data, userdata); | |
209 | node = node->next; | |
210 | } | |
211 | } | |
212 | } | |
213 | } | |
214 | } | |
215 | ||
216 | void hash_table_iter_init (HashtableIter* iter, Hashtable* ht) { | |
217 | RealIter* ri = (RealIter*) iter; | |
218 | ||
219 | if (ri != NULL && ht != NULL) { | |
220 | ri->table = ht; | |
221 | ri->pos = -1; | |
222 | } | |
223 | } | |
224 | ||
225 | bool hash_table_iter_next(HashtableIter* iter, void** key, void** value) { | |
226 | RealIter* ri = (RealIter*) iter; | |
227 | Node* node; | |
228 | int64_t pos; | |
229 | ||
230 | if (ri != NULL) { | |
231 | pos = ri->pos; | |
232 | ||
233 | do { | |
234 | pos++; | |
235 | if (pos >= ri->table->size) { | |
236 | ri->pos = pos; | |
237 | return false; | |
238 | } | |
239 | node = ri->table->nodes[pos]; | |
240 | } while (node == NULL); | |
241 | ||
242 | if (key != NULL) | |
243 | *key = node->key; | |
244 | if (value != NULL) | |
245 | *value = node->data; | |
246 | ||
247 | ri->pos = pos; | |
248 | return true; | |
249 | } | |
250 | return false; | |
251 | } | |
252 | ||
dd3da95a MR |
253 | bool hash_table_contains(Hashtable* ht, const void* key) { |
254 | if (ht == NULL || key == NULL) return false; | |
255 | ||
256 | if (hash_table_lookup(ht, key) == NULL) | |
257 | return false; | |
258 | return true; | |
259 | } | |
260 | ||
261 | uint64_t hash_table_size(Hashtable *ht) { | |
262 | uint64_t size = 0; | |
263 | ||
264 | if (ht == NULL) return size; | |
265 | ||
266 | for (uint32_t i = 0; i < ht->size; i++) { | |
267 | if (ht->nodes[i] != NULL) { | |
268 | Node* node = ht->nodes[i]; | |
269 | while (node != NULL) { | |
270 | size++; | |
271 | node = node->next; | |
272 | } | |
273 | } | |
274 | } | |
275 | ||
276 | return size; | |
277 | } | |
278 | ||
279 | bool hash_table_replace(Hashtable *ht, void* key, void* value) { | |
280 | if (ht == NULL || key == NULL || value == NULL) return false; | |
281 | ||
282 | uint32_t index = hash_table_index(ht, key); | |
283 | ||
284 | Node* node = ht->nodes[index]; | |
285 | while (node != NULL && ht->compare(node->data, key) == false) { | |
286 | node = node->next; | |
287 | } | |
288 | ||
289 | if (node == NULL) | |
290 | return hash_table_insert(ht, key, value); | |
291 | else { | |
292 | free(node->data); | |
293 | node->key = key; | |
294 | node->data = value; | |
295 | } | |
296 | ||
297 | return true; | |
298 | } | |
299 | ||
1d8fe1f7 MR |
300 | uint64_t int_hash(const void* key) { |
301 | return *(uint64_t*) key; | |
302 | } | |
303 | ||
304 | uint64_t str_hash(const void* key) { | |
305 | const signed char* p; | |
306 | uint64_t h = 5381; | |
307 | ||
308 | for (p = key; *p != '\0'; p++) { | |
309 | h = (h << 5) + h + *p; | |
310 | } | |
311 | ||
312 | return h; | |
313 | } | |
314 | ||
315 | uint64_t ptr_hash(const void* key) { | |
316 | return (uint64_t)key; | |
317 | } | |
318 | ||
319 | bool int_equal(const void* a, const void* b) { | |
320 | return *((const int*) a) == *((const int*) b); | |
321 | } | |
322 | ||
323 | bool str_equal(const void* a, const void* b) { | |
324 | const char *string1 = (const char*) a; | |
325 | const char *string2 = (const char*) b; | |
326 | ||
327 | return strcmp (string1, string2) == 0; | |
328 | } | |
329 | ||
330 | bool ptr_equal(const void* a, const void* b) { | |
331 | return a == b; | |
332 | } | |
333 |