lib/ext2fs/hashmap.c

   1 #include "hashmap.h"
   2 #include <string.h>
   3
   4 uint32_t ext2fs_djb2_hash(const void *str, size_t size)
   5 {
   6         int c;
   7         const char *s = str;
   8         uint32_t hash = 5381;
   9
  10         while (size-- > 0) {
  11                 c = *s++;
  12                 hash = ((hash << 5) + hash) + c;
  13         }
  14         return hash;
  15 }
  16
  17 struct ext2fs_hashmap *ext2fs_hashmap_create(
  18                                 uint32_t(*hash_fct)(const void*, size_t),
  19                                 void(*free_fct)(void*), size_t size)
  20 {
  21         struct ext2fs_hashmap *h = calloc(sizeof(struct ext2fs_hashmap) +
  22                                 sizeof(struct ext2fs_hashmap_entry) * size, 1);
  23         h->size = size;
  24         h->free = free_fct;
  25         h->hash = hash_fct;
  26         h->first = h->last = NULL;
  27         return h;
  28 }
  29
  30 void ext2fs_hashmap_add(struct ext2fs_hashmap *h, void *data, const void *key,
  31                         size_t key_len)
  32 {
  33         uint32_t hash = h->hash(key, key_len) % h->size;
  34         struct ext2fs_hashmap_entry *e = malloc(sizeof(*e));
  35
  36         e->data = data;
  37         e->key = key;
  38         e->key_len = key_len;
  39         e->next = h->entries[hash];
  40         h->entries[hash] = e;
  41
  42         e->list_prev = NULL;
  43         e->list_next = h->first;
  44         if (h->first)
  45                 h->first->list_prev = e;
  46         h->first = e;
  47         if (!h->last)
  48                 h->last = e;
  49 }
  50
  51 void *ext2fs_hashmap_lookup(struct ext2fs_hashmap *h, const void *key,
  52                             size_t key_len)
  53 {
  54         struct ext2fs_hashmap_entry *iter;
  55         uint32_t hash = h->hash(key, key_len) % h->size;
  56
  57         for (iter = h->entries[hash]; iter; iter = iter->next)
  58                 if (iter->key_len == key_len && !memcmp(iter->key, key, key_len))
  59                         return iter->data;
  60         return NULL;
  61 }
  62
  63 void *ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap *h,
  64                                    struct ext2fs_hashmap_entry **it)
  65 {
  66         *it = *it ? (*it)->list_next : h->first;
  67         return *it ? (*it)->data : NULL;
  68 }
  69
  70 void ext2fs_hashmap_free(struct ext2fs_hashmap *h)
  71 {
  72         for (size_t i = 0; i < h->size; ++i) {
  73                 struct ext2fs_hashmap_entry *it = h->entries[i];
  74                 while (it) {
  75                         struct ext2fs_hashmap_entry *tmp = it->next;
  76                         if (h->free)
  77                                 h->free(it->data);
  78                         free(it);
  79                         it = tmp;
  80                 }
  81         }
  82         free(h);
  83 }