1 #include "utils/hashmap.h"
2 #include <stdint.h>
3 #include <stdlib.h>
4 #include <string.h>
5 #include <math.h>
6
7 #define FNV_32_PRIME ((uint32_t)0x01000193)
8 #define FNV1_32_INIT ((uint32_t)2166136261)
9 #define TINY_MASK(x) (((uint32_t)1<<(x))-1)
10 #define BUCKETS_SIZE(x) (pow(2,(x)))
11
12 #define AUTO_INC_CHECK() \
13 if(hm->flags & HASHMAP_AUTO_INC \
14 && hm->buckets_x < hm->buckets_x_max \
15 && hashmap_get_pressure(hm) > hm->max_pressure) \
16 { \
17 hashmap_resize(hm, hm->buckets_x+1); \
18 }
19
20 #define AUTO_DEC_CHECK() \
21 if(hm->flags & HASHMAP_AUTO_DEC \
22 && hm->buckets_x > hm->buckets_x_min \
23 && hashmap_get_pressure(hm) < hm->min_pressure) \
24 { \
25 hashmap_resize(hm, hm->buckets_x-1); \
26 }
27
28 // The rest
29
fnv_32a_buf(const void * buf,unsigned int len,unsigned int x)30 uint32_t fnv_32a_buf(const void *buf, unsigned int len, unsigned int x) {
31 unsigned char *bp = (unsigned char *)buf;
32 unsigned char *be = bp + len;
33 uint32_t hval = FNV1_32_INIT;
34 while(bp < be) {
35 hval ^= (uint32_t)*bp++;
36 hval *= FNV_32_PRIME;
37 }
38 return (((hval >> x) ^ hval) & TINY_MASK(x));
39 }
40
41 /** \brief Creates a new hashmap with an allocator
42 *
43 * Creates a new hashmap. This is just like hashmap_create, but
44 * allows the user to define the memory allocation functions.
45 *
46 * \param hm Allocated hashmap pointer
47 * \param n_size Size of the hashmap. Final size will be pow(2, n_size)
48 * \param alloc Allocation functions
49 */
hashmap_create_with_allocator(hashmap * hm,int n_size,allocator alloc)50 void hashmap_create_with_allocator(hashmap *hm, int n_size, allocator alloc) {
51 hm->alloc = alloc;
52 hm->buckets_x = n_size;
53 hm->buckets_x_min = 4;
54 hm->buckets_x_max = 31;
55 hm->min_pressure = 0.25;
56 hm->max_pressure = 0.75;
57 hm->flags = 0;
58 size_t b_size = hashmap_size(hm) * sizeof(hashmap_node*);
59 hm->buckets = hm->alloc.cmalloc(b_size);
60 memset(hm->buckets, 0, b_size);
61 hm->reserved = 0;
62 }
63
64
65 /** \brief Creates a new hashmap
66 *
67 * Creates a new hashmap. Note that the size parameter doesn't mean bucket count,
68 * but the bucket count is actually calculated pow(2, n_size). So for example value
69 * 8 means 256 buckets, and 9 would be 512 buckets.
70 *
71 * Note that if you are planning on using the autoresize feature with auto decrease option,
72 * the n_size should be the same as the min_buckets value in hashmap_set_opts() call.
73 * If you don't fill the hashmap to full size at the start before calling hashmap_del(),
74 * the delete function will start automatically decreasing the hashmap size.
75 *
76 * \todo Make a better create function
77 *
78 * \param hm Allocated hashmap pointer
79 * \param n_size Size of the hashmap. Final size will be pow(2, n_size)
80 */
hashmap_create(hashmap * hm,int n_size)81 void hashmap_create(hashmap *hm, int n_size) {
82 allocator alloc;
83 alloc.cmalloc = malloc;
84 alloc.crealloc = realloc;
85 alloc.cfree = free;
86 hashmap_create_with_allocator(hm, n_size, alloc);
87 }
88
89 /** \brief Set hashmap options
90 *
91 * Used to set hashmap resizing options and pressures.
92 *
93 * Available flags:
94 * - HASHMAP_AUTO_INC: Enables automatic hashmap size increasing (set pressure via max_pressure)
95 * - HASHMAP_AUTO_DEC: Enables automatic hashmap size decreasing (set pressure via min_pressure)
96 *
97 * Decent default for pressures might be 0.25 for minimum and 0.75 for maximum. These can and should
98 * of course be tweaked as necessary, since resizing is a rather expensive operation and should be
99 * avoided if necessary.
100 *
101 * buckets_min and buckets_max define the minimum and maximum amount of buckets available in the
102 * hashmap.
103 *
104 * min_pressure and max_pressure will only be used if HASHMAP_AUTO_INC and HASHMAP_AUTO_DEC are set,
105 * respectively. Same with buckets_min and buckets_max.
106 *
107 * \param hm Allocated hashmap pointer
108 * \param flags Feature flags (eg. HASHMAP_AUTO_INC|HASHMAP_AUTO_DEC)
109 * \param min_pressure Minimum pressure value for auto-resize (eg. 0.25)
110 * \param max_pressure Maximum pressure value for auto-resize (eg. 0.75)
111 * \param buckets_min Minimum amount of buckets (must be >= 2)
112 * \param buckets_max Maximum amount of buckets
113 */
hashmap_set_opts(hashmap * hm,unsigned int flags,float min_pressure,float max_pressure,int buckets_min,int buckets_max)114 void hashmap_set_opts(hashmap *hm,
115 unsigned int flags,
116 float min_pressure, float max_pressure,
117 int buckets_min, int buckets_max)
118 {
119 hm->flags = flags & 0x3;
120 hm->min_pressure = min_pressure;
121 hm->max_pressure = max_pressure;
122 hm->buckets_x_min = buckets_min >= 2 ? buckets_min : 2;
123 hm->buckets_x_max = buckets_max;
124 }
125
126 /** \brief Get current hashmap pressure
127 *
128 * Simply gets the current fill pressure for the hashmap.
129 * Calculated as reserved_buckets / total_buckets.
130 *
131 * \param hm Allocated hashmap pointer
132 */
hashmap_get_pressure(hashmap * hm)133 float hashmap_get_pressure(hashmap *hm) {
134 return ((float)hm->reserved) / ((float)BUCKETS_SIZE(hm->buckets_x));
135 }
136
137 /** \brief Runs pressure checks and resizes if necessary
138 *
139 * This function checks if either the minimun or maximum pressure checks are on
140 * and if the pressure values have been exceeded. If they are, resize operation
141 * will be run.
142 *
143 * \param hm Allocated hashmap pointer
144 */
hashmap_autoresize(hashmap * hm)145 void hashmap_autoresize(hashmap *hm) {
146 AUTO_INC_CHECK()
147 AUTO_DEC_CHECK()
148 }
149
150 /** \brief Resizes the hashmap
151 *
152 * Note! This is a very naive implementation. During the rehashing, a separate
153 * memory area is reserved, so memory usage will temporarily jump!
154 *
155 * \todo Make a better resize function
156 *
157 * \param hm Allocated hashmap pointer
158 * \param n_size Size of the hashmap. Final size will be pow(2, n_size)
159 */
hashmap_resize(hashmap * hm,int n_size)160 int hashmap_resize(hashmap *hm, int n_size) {
161 // Do not resize if equal size was requested
162 if(n_size == hm->buckets_x) {
163 return 1;
164 }
165
166 // Allocate and zero out a new memory blocks for the resized bucket list
167 size_t new_size = BUCKETS_SIZE(n_size) * sizeof(hashmap_node*);
168 hashmap_node **new_buckets = hm->alloc.cmalloc(new_size);
169 memset(new_buckets, 0, new_size);
170
171 // Rehash
172 hashmap_node *node = NULL;
173 hashmap_node *this = NULL;
174 unsigned int index;
175 for(unsigned int i = 0; i < hashmap_size(hm); i++) {
176 node = hm->buckets[i];
177 while(node != NULL) {
178 this = node;
179 node = node->next;
180
181 // Recalculate index, and prepend the new index to the bucket list
182 index = fnv_32a_buf(this->pair.key, this->pair.keylen, n_size);
183 this->next = new_buckets[index];
184 new_buckets[index] = this;
185 }
186 }
187
188 // Free old bucket list and assign new list and size of the hashmap
189 free(hm->buckets);
190 hm->buckets = new_buckets;
191 hm->buckets_x = n_size;
192 return 0;
193 }
194
195 /** \brief Clears hashmap entries
196 *
197 * This clears the hashmap of all entries. All contents will be freed.
198 * After this, the hashmap size will be 0.
199 *
200 * \param hm Hashmap to clear
201 */
hashmap_clear(hashmap * hm)202 void hashmap_clear(hashmap *hm) {
203 hashmap_node *node = NULL;
204 hashmap_node *tmp = NULL;
205 for(unsigned int i = 0; i < hashmap_size(hm); i++) {
206 node = hm->buckets[i];
207 while(node != NULL) {
208 tmp = node;
209 node = node->next;
210 hm->alloc.cfree(tmp->pair.key);
211 hm->alloc.cfree(tmp->pair.val);
212 hm->alloc.cfree(tmp);
213 hm->reserved--;
214 }
215 hm->buckets[i] = NULL;
216 }
217 }
218
219 /** \brief Free hashmap
220 *
221 * Frees the hasmap. All contents will be freed and hashmap will be deallocated.
222 * Any use of this hashmap after this will lead to undefined behaviour.
223 *
224 * \param hm Hashmap to free
225 */
hashmap_free(hashmap * hm)226 void hashmap_free(hashmap *hm) {
227 hashmap_clear(hm);
228 hm->alloc.cfree(hm->buckets);
229 hm->buckets = NULL;
230 hm->buckets_x = 0;
231 hm->reserved = 0;
232 }
233
234 /** \brief Gets hashmap size
235 *
236 * Returns the hashmap size. This is the amount of hashmap allocated buckets.
237 *
238 * \param hm Hashmap
239 * \return Amount of hashmap buckets
240 */
hashmap_size(const hashmap * hm)241 unsigned int hashmap_size(const hashmap *hm) {
242 return BUCKETS_SIZE(hm->buckets_x);
243 }
244
245 /** \brief Gets hashmap reserved buckets
246 *
247 * Returns the amount of items in the hashmap. Note that the item count
248 * can be larger than the bucket count, if the hashmap is full enough.
249 * If there are a lot more items than buckets, you should really consider
250 * growing your hashmap bucket count ...
251 *
252 * \param hm Hashmap
253 * \return Amount of items in the hashmap
254 */
hashmap_reserved(const hashmap * hm)255 unsigned int hashmap_reserved(const hashmap *hm) {
256 return hm->reserved;
257 }
258
259 /** \brief Puts an item to the hashmap
260 *
261 * Puts a new item to the hashmap. Note that the
262 * contents of the value memory block will be copied. However,
263 * any memory _pointed to_ by it will NOT be copied. So be careful!
264 *
265 * If autoresizing is on, this will check if the hashmap needs
266 * to be increased in size. If yes, size will be doubled and a full
267 * rehashing operation will be run. This will take time!
268 *
269 * This function does NOT automatically decrease size, even if HASHMAP_AUTO_DEC
270 * flag is enabled.
271 *
272 * \param hm Hashmap
273 * \param key Pointer to key memory block
274 * \param keylen Length of the key memory block
275 * \param val Pointer to value memory block
276 * \param vallen Length of the value memory block
277 * \return Returns a pointer to the newly reserved hashmap pair.
278 */
hashmap_put(hashmap * hm,const void * key,unsigned int keylen,const void * val,unsigned int vallen)279 void* hashmap_put(hashmap *hm,
280 const void *key, unsigned int keylen,
281 const void *val, unsigned int vallen)
282 {
283 unsigned int index = fnv_32a_buf(key, keylen, hm->buckets_x);
284 hashmap_node *root = hm->buckets[index];
285 hashmap_node *seek = root;
286
287 // See if the key already exists in the buckets list
288 int found = 0;
289 while(seek) {
290 if(seek->pair.keylen == keylen) {
291 if(memcmp(seek->pair.key, key, keylen) == 0) {
292 found = 1;
293 break;
294 }
295 }
296 seek = seek->next;
297 }
298
299 if(found) {
300 // The key is already in the hashmap, so just realloc and reset the contents.
301 seek->pair.val = hm->alloc.crealloc(seek->pair.val, vallen);
302 memcpy(seek->pair.val, val, vallen);
303 seek->pair.vallen = vallen;
304
305 AUTO_INC_CHECK()
306 return seek->pair.val;
307 } else {
308 // Key is not yet in the hashmap, so create a new node and set it
309 // as the first entry in the buckets list.
310 hashmap_node *node = hm->alloc.cmalloc(sizeof(hashmap_node));
311 node->pair.keylen = keylen;
312 node->pair.vallen = vallen;
313 node->pair.key = hm->alloc.cmalloc(keylen);
314 node->pair.val = hm->alloc.cmalloc(vallen);
315 memcpy(node->pair.key, key, keylen);
316 memcpy(node->pair.val, val, vallen);
317
318 node->next = root;
319 hm->buckets[index] = node;
320 hm->reserved++;
321
322 AUTO_INC_CHECK()
323 return node->pair.val;
324 }
325 }
326
327
328 /** \brief Deletes an item from the hashmap
329 *
330 * Deletes an item from the hashmap. Note: Using this function inside an
331 * iterator may lead to weird behavior. If you wish to delete inside an
332 * iterator, please use hashmap_delete.
333 *
334 * If autoresizing is on, this will check if the hashmap needs
335 * to be decreased in size. If yes, size will be cut in half and a full
336 * rehashing operation will be run. This will take time!
337 *
338 * This function does NOT automatically increase size, even if HASHMAP_AUTO_INC
339 * flag is enabled.
340 *
341 * \param hm Hashmap
342 * \param key Pointer to key memory block
343 * \param keylen Length of the key memory block
344 * \return Returns 0 on success, 1 on error (not found).
345 */
hashmap_del(hashmap * hm,const void * key,unsigned int keylen)346 int hashmap_del(hashmap *hm, const void *key, unsigned int keylen) {
347 unsigned int index = fnv_32a_buf(key, keylen, hm->buckets_x);
348
349 // Get node
350 hashmap_node *node = hm->buckets[index];
351 hashmap_node *prev = NULL;
352 if(node == NULL) return 1;
353
354 // Find the node we want to delete
355 int found = 0;
356 while(node) {
357 if(node->pair.keylen == keylen) {
358 if(memcmp(node->pair.key, key, keylen) == 0) {
359 found = 1;
360 break;
361 }
362 }
363 prev = node;
364 node = node->next;
365 }
366
367 // If node was found, handle delete
368 if(found) {
369 if(prev != NULL) {
370 // If node is not first in chain, set correct links
371 prev->next = node->next;
372 } else {
373 // If node is first in chain, set possible next entry as first
374 hm->buckets[index] = node->next;
375 }
376 hm->alloc.cfree(node->pair.key);
377 hm->alloc.cfree(node->pair.val);
378 hm->alloc.cfree(node);
379 hm->reserved--;
380
381 AUTO_DEC_CHECK()
382 return 0;
383 }
384 return 1;
385 }
386
387 /** \brief Gets an item from the hashmap
388 *
389 * Returns an item from the hashmap.
390 *
391 * \param hm Hashmap
392 * \param key Pointer to key memory block
393 * \param keylen Length of the key memory block
394 * \param val Pointer to value hashmap memory block
395 * \param vallen Length of the hashmap value memory block
396 * \return Returns 0 on success, 1 on error (not found).
397 */
hashmap_get(hashmap * hm,const void * key,unsigned int keylen,void ** val,unsigned int * vallen)398 int hashmap_get(hashmap *hm, const void *key, unsigned int keylen, void **val, unsigned int *vallen) {
399 unsigned int index = fnv_32a_buf(key, keylen, hm->buckets_x);
400
401 // Set defaults for error cases
402 *val = NULL;
403 *vallen = 0;
404
405 // Get node
406 hashmap_node *node = hm->buckets[index];
407 if(node == NULL) return 1;
408
409 // Find the node we want
410 while(node) {
411 if(node->pair.keylen == keylen) {
412 if(memcmp(node->pair.key, key, keylen) == 0) {
413 *val = node->pair.val;
414 *vallen = node->pair.vallen;
415 return 0;
416 }
417 }
418 node = node->next;
419 }
420
421 return 1;
422 }
423
hashmap_sput(hashmap * hm,const char * key,void * value,unsigned int value_len)424 void hashmap_sput(hashmap *hm, const char *key, void *value, unsigned int value_len) {
425 hashmap_put(hm, key, strlen(key)+1, value, value_len);
426 }
427
hashmap_iput(hashmap * hm,unsigned int key,void * value,unsigned int value_len)428 void hashmap_iput(hashmap *hm, unsigned int key, void *value, unsigned int value_len) {
429 hashmap_put(hm, (char*)&key, sizeof(unsigned int), value, value_len);
430 }
431
hashmap_sget(hashmap * hm,const char * key,void ** value,unsigned int * value_len)432 int hashmap_sget(hashmap *hm, const char *key, void **value, unsigned int *value_len) {
433 return hashmap_get(hm, (void*)key, strlen(key)+1, value, value_len);
434 }
435
hashmap_iget(hashmap * hm,unsigned int key,void ** value,unsigned int * value_len)436 int hashmap_iget(hashmap *hm, unsigned int key, void **value, unsigned int *value_len) {
437 return hashmap_get(hm, (void*)&key, sizeof(unsigned int), value, value_len);
438 }
439
hashmap_sdel(hashmap * hm,const char * key)440 void hashmap_sdel(hashmap *hm, const char *key) {
441 hashmap_del(hm, key, strlen(key)+1);
442 }
443
hashmap_idel(hashmap * hm,unsigned int key)444 void hashmap_idel(hashmap *hm, unsigned int key) {
445 hashmap_del(hm, (char*)&key, sizeof(unsigned int));
446 }
447
448 /** \brief Deletes an item from the hashmap by iterator key
449 *
450 * Deletes an item from the hashmap by a matching iterator key.
451 * This function is iterator safe. In theory, this function
452 * should not fail, as the iterable value should exist.
453 *
454 * Note! This function does NOT autoresize at all, even if the flags
455 * are enabled. This is to avoid trouble while iterating. If you do
456 * a large amount of deletions here and suspect the minimum limit has been
457 * reached, call hashmap_autoresize to run a check and resize operation.
458 *
459 * \param hm Hashmap
460 * \param iter Iterator
461 * \return Returns 0 on success, 1 on error (not found).
462 */
hashmap_delete(hashmap * hm,iterator * iter)463 int hashmap_delete(hashmap *hm, iterator *iter) {
464 int index = iter->inow - 1;
465
466 if (iter->ended) {
467 return 1;
468 }
469
470 // Find correct node
471 hashmap_node *node = hm->buckets[index];
472 hashmap_node *prev = NULL;
473 hashmap_node *seek = iter->vnow;
474 if(node == NULL || seek == NULL) return 1;
475
476 // Find the node we want to delete
477 int found = 0;
478 while(node) {
479 if(node == seek) {
480 found = 1;
481 break;
482 }
483 prev = node;
484 node = node->next;
485 }
486
487 // If node was found, handle delete
488 if(found) {
489 // If node is not first in chain, set correct links
490 // Otherwise set possible next entry as first
491 if(prev != NULL) {
492 prev->next = node->next;
493 iter->vnow = prev;
494 } else {
495 hm->buckets[index] = node->next;
496 iter->vnow = NULL;
497 iter->inow--;
498 }
499
500 // Alld one, free up memory.
501 hm->alloc.cfree(node->pair.key);
502 hm->alloc.cfree(node->pair.val);
503 hm->alloc.cfree(node);
504 hm->reserved--;
505 return 0;
506 }
507 return 1;
508 }
509
_hashmap_seek_next(hashmap * hm,iterator * iter)510 static void _hashmap_seek_next(hashmap *hm, iterator *iter) {
511 if(iter->inow >= hashmap_size(hm)) {
512 iter->vnow = NULL;
513 iter->ended = 1;
514 return;
515 }
516 do {
517 iter->vnow = hm->buckets[iter->inow++];
518 } while(iter->vnow == NULL && iter->inow < hashmap_size(hm));
519 }
520
hashmap_iter_next(iterator * iter)521 void* hashmap_iter_next(iterator *iter) {
522 hashmap_node *tmp = NULL;
523 hashmap *hm = (hashmap*)iter->data;
524
525 // Find next non-empty bucket
526 if(iter->vnow == NULL) {
527 _hashmap_seek_next(hm, iter);
528 if(iter->vnow == NULL) {
529 return NULL;
530 }
531 tmp = (hashmap_node*)iter->vnow;
532 return &tmp->pair;
533 }
534
535 // We already are in a non-empty bucket. See if it has any
536 // other non-empty buckets in list. If it does, return it.
537 tmp = (hashmap_node*)iter->vnow;
538 if(tmp->next != NULL) {
539 iter->vnow = tmp->next;
540 return &tmp->next->pair;
541 }
542
543 // We are in the end of the list for this bucket.
544 // Find next non-empty bucket.
545 _hashmap_seek_next(hm, iter);
546 if(iter->vnow == NULL) {
547 return NULL;
548 }
549 tmp = (hashmap_node*)iter->vnow;
550 return &tmp->pair;
551 }
552
hashmap_iter_begin(const hashmap * hm,iterator * iter)553 void hashmap_iter_begin(const hashmap *hm, iterator *iter) {
554 iter->data = hm;
555 iter->vnow = NULL;
556 iter->inow = 0;
557 iter->next = hashmap_iter_next;
558 iter->prev = NULL;
559 iter->ended = (hm->reserved == 0);
560 }
561