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 }