Skip to content

Instantly share code, notes, and snippets.

@Vagabond
Last active January 6, 2016 05:12
Show Gist options
  • Save Vagabond/f4d44f376b22bb169c4c to your computer and use it in GitHub Desktop.
Save Vagabond/f4d44f376b22bb169c4c to your computer and use it in GitHub Desktop.
-: 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:// The rest
-: 13:
287922: 14:uint32_t fnv_32a_buf(const void *buf, unsigned int len, unsigned int x) {
287922: 15: unsigned char *bp = (unsigned char *)buf;
287922: 16: unsigned char *be = bp + len;
287922: 17: uint32_t hval = FNV1_32_INIT;
2122399: 18: while(bp < be) {
1546555: 19: hval ^= (uint32_t)*bp++;
1546555: 20: hval *= FNV_32_PRIME;
-: 21: }
287922: 22: return (((hval >> x) ^ hval) & TINY_MASK(x));
-: 23:}
-: 24:
-: 25:/** \brief Creates a new hashmap with an allocator
-: 26: *
-: 27: * Creates a new hashmap. This is just like hashmap_create, but
-: 28: * allows the user to define the memory allocation functions.
-: 29: *
-: 30: * \param hm Allocated memory pointer
-: 31: * \param n_size Size of the hashmap. Final size will be pow(w, n_size)
-: 32: * \param alloc Allocation functions
-: 33: */
34823: 34:void hashmap_create_with_allocator(hashmap *hm, int n_size, allocator alloc) {
34823: 35: hm->alloc = alloc;
34823: 36: hm->buckets_x = n_size;
34823: 37: size_t b_size = hashmap_size(hm) * sizeof(hashmap_node*);
34823: 38: hm->buckets = hm->alloc.cmalloc(b_size);
34823: 39: memset(hm->buckets, 0, b_size);
34823: 40: hm->reserved = 0;
34823: 41:}
-: 42:
-: 43:
-: 44:/** \brief Creates a new hashmap
-: 45: *
-: 46: * Creates a new hashmap. Note that the size parameter doesn't mean bucket count,
-: 47: * but the bucket count is actually calculated pow(2, n_size). So for example value
-: 48: * 8 means 256 buckets, and 9 would be 512 buckets.
-: 49: *
-: 50: * \todo Make a better create function
-: 51: *
-: 52: * \param hm Allocated memory pointer
-: 53: * \param n_size Size of the hashmap. Final size will be pow(w, n_size)
-: 54: */
34823: 55:void hashmap_create(hashmap *hm, int n_size) {
-: 56: allocator alloc;
34823: 57: alloc.cmalloc = malloc;
34823: 58: alloc.crealloc = realloc;
34823: 59: alloc.cfree = free;
34823: 60: hashmap_create_with_allocator(hm, n_size, alloc);
34823: 61:}
-: 62:
-: 63:/** \brief Clears hashmap entries
-: 64: *
-: 65: * This clears the hashmap of all entries. All contents will be freed.
-: 66: * After this, the hashmap size will be 0.
-: 67: *
-: 68: * \param hm Hashmap to clear
-: 69: */
122372: 70:void hashmap_clear(hashmap *hm) {
122372: 71: hashmap_node *node = NULL;
122372: 72: hashmap_node *tmp = NULL;
36077396: 73: for(unsigned int i = 0; i < hashmap_size(hm); i++) {
35955024: 74: node = hm->buckets[i];
71968629: 75: while(node != NULL) {
58581: 76: tmp = node;
58581: 77: node = node->next;
58581: 78: hm->alloc.cfree(tmp->pair.key);
58581: 79: hm->alloc.cfree(tmp->pair.val);
58581: 80: hm->alloc.cfree(tmp);
58581: 81: hm->reserved--;
-: 82: }
35955024: 83: hm->buckets[i] = NULL;
-: 84: }
122372: 85:}
-: 86:
-: 87:/** \brief Free hashmap
-: 88: *
-: 89: * Frees the hasmap. All contents will be freed and hashmap will be deallocated.
-: 90: * Any use of this hashmap after this will lead to undefined behaviour.
-: 91: *
-: 92: * \param hm Hashmap to free
-: 93: */
34823: 94:void hashmap_free(hashmap *hm) {
34823: 95: hashmap_clear(hm);
34823: 96: hm->alloc.cfree(hm->buckets);
34823: 97: hm->buckets = NULL;
34823: 98: hm->buckets_x = 0;
34823: 99: hm->reserved = 0;
34823: 100:}
-: 101:
-: 102:/** \brief Gets hashmap size
-: 103: *
-: 104: * Returns the hashmap size. This is the amount of hashmap allocated buckets.
-: 105: *
-: 106: * \param hm Hashmap
-: 107: * \return Amount of hashmap buckets
-: 108: */
50374657: 109:unsigned int hashmap_size(const hashmap *hm) {
50374657: 110: return BUCKETS_SIZE(hm->buckets_x);
-: 111:}
-: 112:
-: 113:/** \brief Gets hashmap reserved buckets
-: 114: *
-: 115: * Returns the amount of items in the hashmap. Note that the item count
-: 116: * can be larger than the bucket count, if the hashmap is full enough.
-: 117: * If there are a lot more items than buckets, you should really consider
-: 118: * growing your hashmap bucket count ...
-: 119: *
-: 120: * \param hm Hashmap
-: 121: * \return Amount of items in the hashmap
-: 122: */
#####: 123:unsigned int hashmap_reserved(const hashmap *hm) {
#####: 124: return hm->reserved;
-: 125:}
-: 126:
-: 127:/** \brief Puts an item to the hashmap
-: 128: *
-: 129: * Puts a new item to the hashmap. Note that the
-: 130: * contents of the value memory block will be copied. However,
-: 131: * any memory _pointed to_ by it will NOT be copied. So be careful!
-: 132: *
-: 133: * \param hm Hashmap
-: 134: * \param key Pointer to key memory block
-: 135: * \param keylen Length of the key memory block
-: 136: * \param val Pointer to value memory block
-: 137: * \param vallen Length of the value memory block
-: 138: * \return Returns a pointer to the newly reserved hashmap pair.
-: 139: */
114161: 140:void* hashmap_put(hashmap *hm,
-: 141: const void *key, unsigned int keylen,
-: 142: const void *val, unsigned int vallen) {
114161: 143: unsigned int index = fnv_32a_buf(key, keylen, hm->buckets_x);
114161: 144: hashmap_node *root = hm->buckets[index];
114161: 145: hashmap_node *seek = root;
-: 146:
-: 147: // See if the key already exists in the buckets list
114161: 148: int found = 0;
229168: 149: while(seek) {
28586: 150: if(seek->pair.keylen == keylen) {
27877: 151: if(memcmp(seek->pair.key, key, keylen) == 0) {
27740: 152: found = 1;
27740: 153: break;
-: 154: }
-: 155: }
846: 156: seek = seek->next;
-: 157: }
-: 158:
114161: 159: if(found) {
-: 160: // The key is already in the hashmap, so just realloc and reset the contents.
27740: 161: seek->pair.val = hm->alloc.crealloc(seek->pair.val, vallen);
27740: 162: memcpy(seek->pair.val, val, vallen);
27740: 163: seek->pair.vallen = vallen;
27740: 164: return seek->pair.val;
-: 165: } else {
-: 166: // Key is not yet in the hashmap, so create a new node and set it
-: 167: // as the first entry in the buckets list.
86421: 168: hashmap_node *node = hm->alloc.cmalloc(sizeof(hashmap_node));
86421: 169: node->pair.keylen = keylen;
86421: 170: node->pair.vallen = vallen;
86421: 171: node->pair.key = hm->alloc.cmalloc(keylen);
86421: 172: node->pair.val = hm->alloc.cmalloc(vallen);
86421: 173: memcpy(node->pair.key, key, keylen);
86421: 174: memcpy(node->pair.val, val, vallen);
-: 175:
86421: 176: node->next = root;
86421: 177: hm->buckets[index] = node;
86421: 178: hm->reserved++;
-: 179:
86421: 180: return node->pair.val;
-: 181: }
-: 182:}
-: 183:
-: 184:
-: 185:/** \brief Deletes an item from the hashmap
-: 186: *
-: 187: * Deletes an item from the hashmap. Note: Using this function inside an
-: 188: * iterator may lead to weird behavior. If you wish to delete inside an
-: 189: * iterator, please use hashmap_delete.
-: 190: *
-: 191: * \param hm Hashmap
-: 192: * \param key Pointer to key memory block
-: 193: * \param keylen Length of the key memory block
-: 194: * \return Returns 0 on success, 1 on error (not found).
-: 195: */
86869: 196:int hashmap_del(hashmap *hm, const void *key, unsigned int keylen) {
86869: 197: unsigned int index = fnv_32a_buf(key, keylen, hm->buckets_x);
-: 198:
-: 199: // Get node
86869: 200: hashmap_node *node = hm->buckets[index];
86869: 201: hashmap_node *prev = NULL;
86869: 202: if(node == NULL) return 1;
-: 203:
-: 204: // Find the node we want to delete
14299: 205: int found = 0;
28981: 206: while(node) {
14358: 207: if(node->pair.keylen == keylen) {
14028: 208: if(memcmp(node->pair.key, key, keylen) == 0) {
13975: 209: found = 1;
13975: 210: break;
-: 211: }
-: 212: }
383: 213: prev = node;
383: 214: node = node->next;
-: 215: }
-: 216:
-: 217: // If node was found, handle delete
14299: 218: if(found) {
13975: 219: if(prev != NULL) {
-: 220: // If node is not first in chain, set correct links
52: 221: prev->next = node->next;
-: 222: } else {
-: 223: // If node is first in chain, set possible next entry as first
13923: 224: hm->buckets[index] = node->next;
-: 225: }
13975: 226: hm->alloc.cfree(node->pair.key);
13975: 227: hm->alloc.cfree(node->pair.val);
13975: 228: hm->alloc.cfree(node);
13975: 229: hm->reserved--;
13975: 230: return 0;
-: 231: }
324: 232: return 1;
-: 233:}
-: 234:
-: 235:/** \brief Gets an item from the hashmap
-: 236: *
-: 237: * Returns an item from the hashmap.
-: 238: *
-: 239: * \param hm Hashmap
-: 240: * \param key Pointer to key memory block
-: 241: * \param keylen Length of the key memory block
-: 242: * \param val Pointer to value hashmap memory block
-: 243: * \param vallen Length of the hashmap value memory block
-: 244: * \return Returns 0 on success, 1 on error (not found).
-: 245: */
86892: 246:int hashmap_get(hashmap *hm, const void *key, unsigned int keylen, void **val, unsigned int *vallen) {
86892: 247: unsigned int index = fnv_32a_buf(key, keylen, hm->buckets_x);
-: 248:
-: 249: // Set defaults for error cases
86892: 250: *val = NULL;
86892: 251: *vallen = 0;
-: 252:
-: 253: // Get node
86892: 254: hashmap_node *node = hm->buckets[index];
86892: 255: if(node == NULL) return 1;
-: 256:
-: 257: // Find the node we want
28990: 258: while(node) {
14352: 259: if(node->pair.keylen == keylen) {
14035: 260: if(memcmp(node->pair.key, key, keylen) == 0) {
13940: 261: *val = node->pair.val;
13940: 262: *vallen = node->pair.vallen;
13940: 263: return 0;
-: 264: }
-: 265: }
412: 266: node = node->next;
-: 267: }
-: 268:
349: 269: return 1;
-: 270:}
-: 271:
#####: 272:void hashmap_sput(hashmap *hm, const char *key, void *value, unsigned int value_len) {
#####: 273: hashmap_put(hm, key, strlen(key)+1, value, value_len);
#####: 274:}
-: 275:
#####: 276:void hashmap_iput(hashmap *hm, unsigned int key, void *value, unsigned int value_len) {
#####: 277: hashmap_put(hm, (char*)&key, sizeof(unsigned int), value, value_len);
#####: 278:}
-: 279:
#####: 280:int hashmap_sget(hashmap *hm, const char *key, void **value, unsigned int *value_len) {
#####: 281: return hashmap_get(hm, (void*)key, strlen(key)+1, value, value_len);
-: 282:}
-: 283:
#####: 284:int hashmap_iget(hashmap *hm, unsigned int key, void **value, unsigned int *value_len) {
#####: 285: return hashmap_get(hm, (void*)&key, sizeof(unsigned int), value, value_len);
-: 286:}
-: 287:
#####: 288:void hashmap_sdel(hashmap *hm, const char *key) {
#####: 289: hashmap_del(hm, key, strlen(key)+1);
#####: 290:}
-: 291:
#####: 292:void hashmap_idel(hashmap *hm, unsigned int key) {
#####: 293: hashmap_del(hm, (char*)&key, sizeof(unsigned int));
#####: 294:}
-: 295:
-: 296:/** \brief Deletes an item from the hashmap by iterator key
-: 297: *
-: 298: * Deletes an item from the hashmap by a matching iterator key.
-: 299: * This function is iterator safe. In theory, this function
-: 300: * should not fail, as the iterable value should exist.
-: 301: *
-: 302: * \param hm Hashmap
-: 303: * \param iter Iterator
-: 304: * \return Returns 0 on success, 1 on error (not found).
-: 305: */
87123: 306:int hashmap_delete(hashmap *hm, iterator *iter) {
87123: 307: int index = iter->inow - 1;
-: 308:
-: 309: // Find correct node
87123: 310: hashmap_node *node = hm->buckets[index];
87123: 311: hashmap_node *prev = NULL;
87123: 312: hashmap_node *seek = iter->vnow;
87123: 313: if(node == NULL || seek == NULL) return 1;
-: 314:
-: 315: // Find the node we want to delete
13865: 316: int found = 0;
27794: 317: while(node) {
13929: 318: if(node == seek) {
13865: 319: found = 1;
13865: 320: break;
-: 321: }
64: 322: prev = node;
64: 323: node = node->next;
-: 324: }
-: 325:
-: 326: // If node was found, handle delete
13865: 327: if(found) {
-: 328: // If node is not first in chain, set correct links
-: 329: // Otherwise set possible next entry as first
13865: 330: if(prev != NULL) {
64: 331: prev->next = node->next;
64: 332: iter->vnow = prev;
-: 333: } else {
13801: 334: hm->buckets[index] = node->next;
13801: 335: iter->vnow = NULL;
13801: 336: iter->inow--;
-: 337: }
-: 338:
-: 339: // Alld one, free up memory.
13865: 340: hm->alloc.cfree(node->pair.key);
13865: 341: hm->alloc.cfree(node->pair.val);
13865: 342: hm->alloc.cfree(node);
13865: 343: hm->reserved--;
13865: 344: return 0;
-: 345: }
#####: 346: return 1;
-: 347:}
-: 348:
120378: 349:static void _hashmap_seek_next(hashmap *hm, iterator *iter) {
120378: 350: if(iter->inow >= hashmap_size(hm)) {
1034: 351: iter->vnow = NULL;
1034: 352: iter->ended = 1;
1034: 353: return;
-: 354: }
-: 355: do {
14220399: 356: iter->vnow = hm->buckets[iter->inow++];
14220399: 357: } while(iter->vnow == NULL && iter->inow < hashmap_size(hm));
-: 358:}
-: 359:
120995: 360:void* hashmap_iter_next(iterator *iter) {
120995: 361: hashmap_node *tmp = NULL;
120995: 362: hashmap *hm = (hashmap*)iter->data;
-: 363:
-: 364: // Find next non-empty bucket
120995: 365: if(iter->vnow == NULL) {
55904: 366: _hashmap_seek_next(hm, iter);
55904: 367: if(iter->vnow == NULL) {
#####: 368: return NULL;
-: 369: }
55904: 370: tmp = (hashmap_node*)iter->vnow;
55904: 371: return &tmp->pair;
-: 372: }
-: 373:
-: 374: // We already are in a non-empty bucket. See if it has any
-: 375: // other non-empty buckets in list. If it does, return it.
65091: 376: tmp = (hashmap_node*)iter->vnow;
65091: 377: if(tmp->next != NULL) {
617: 378: iter->vnow = tmp->next;
617: 379: return &tmp->next->pair;
-: 380: }
-: 381:
-: 382: // We are in the end of the list for this bucket.
-: 383: // Find next non-empty bucket.
64474: 384: _hashmap_seek_next(hm, iter);
64474: 385: if(iter->vnow == NULL) {
42039: 386: return NULL;
-: 387: }
22435: 388: tmp = (hashmap_node*)iter->vnow;
22435: 389: return &tmp->pair;
-: 390:}
-: 391:
174630: 392:void hashmap_iter_begin(const hashmap *hm, iterator *iter) {
174630: 393: iter->data = hm;
174630: 394: iter->vnow = NULL;
174630: 395: iter->inow = 0;
174630: 396: iter->next = hashmap_iter_next;
174630: 397: iter->prev = NULL;
174630: 398: iter->ended = (hm->reserved == 0);
174630: 399:}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment