lib/ext2fs/hashmap.c

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