Last active
January 6, 2016 05:12
-
-
Save Vagabond/f4d44f376b22bb169c4c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| -: 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