hashmap.c.gcov

        -:    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:}