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