diff options
| m--------- | depends/mgl | 0 | ||||
| -rw-r--r-- | include/hashmap.h | 38 | ||||
| -rw-r--r-- | src/hashmap.c | 155 |
3 files changed, 193 insertions, 0 deletions
diff --git a/depends/mgl b/depends/mgl -Subproject 08b27c7854cf38d3f03b0607f06c0140d6dc795 +Subproject 4537803743e51ecb01925e9c5b4bef44aad8386 diff --git a/include/hashmap.h b/include/hashmap.h new file mode 100644 index 0000000..0928081 --- /dev/null +++ b/include/hashmap.h @@ -0,0 +1,38 @@ +#ifndef MGUI_HASHMAP_H +#define MGUI_HASHMAP_H + +#include <stdint.h> +#include <stddef.h> +#include <stdbool.h> + +typedef struct mgui_hashmap_entry mgui_hashmap_entry; + +struct mgui_hashmap_entry { + mgui_hashmap_entry *next; + uint64_t hash; + void *value; + size_t key_size; + /* char key[...]; Dynamically size string of size |key_size|. Allocated directly in the struct (sizeof(mgui_hashmap_entry) + key_size) */ +}; + +typedef struct { + mgui_hashmap_entry **entries; + size_t capacity; + size_t size; +} mgui_hashmap; + +void mgui_hashmap_init(mgui_hashmap *self); +void mgui_hashmap_deinit(mgui_hashmap *self); + +/* + Note: stores the |value| itself, and does not copy the content of |value|. + Note: inserting the same value multiple times in the hash map is undefined behavior. + Note: |hash| can be NULL. +*/ +void mgui_hashmap_insert(mgui_hashmap *self, const char *key, size_t key_size, void *value, uint64_t *hash_out); +bool mgui_hashmap_get(mgui_hashmap *self, const char *key, size_t key_size, void **value_out); +/* Note: |hash| has to be the hash for |key|, which you can get by using calling |mgui_hashmap_hash| with |key| or as a result of |mgui_hashmap_insert| */ +bool mgui_hashmap_get_by_hash(mgui_hashmap *self, const char *key, size_t key_size, uint64_t hash, void **value_out); +uint64_t mgui_hashmap_hash(const char *key, size_t key_size); + +#endif /* MGUI_HASHMAP_H */ diff --git a/src/hashmap.c b/src/hashmap.c new file mode 100644 index 0000000..1625101 --- /dev/null +++ b/src/hashmap.c @@ -0,0 +1,155 @@ +#include "../include/hashmap.h" +#include "../include/alloc.h" +#include <string.h> +#include <assert.h> + +/* Optimized div by sizeof(mgui_hashmap_entry*) */ +#if INTPTR_MAX == INT64_MAX +#define CAP_NUM_ENTRIES(cap) ((cap) >> 3) +#elif INTPTR_MAX == INT32_MAX +#define CAP_NUM_ENTRIES(cap) ((cap) >> 2) +#else +#error Unsupported system. Only systems where a pointer is 32-bits or 64-bits are supported. +#endif + +#define HASH_TO_INDEX(hash) (hash & (CAP_NUM_ENTRIES(self->capacity)-1)) +#define HASHMAP_ENTRY_GET_KEY(entry) ((char*)entry + sizeof(mgui_hashmap_entry) + (entry->key_size)) + +/* |align| should be a multiple of 2 */ +static size_t align_to(size_t value, size_t align) { + const size_t is_aligned = (value & (align - 1)); + if(is_aligned == 0) { + return value; + } else { + return (value & ~(align - 1)) + align; + } +} + +void mgui_hashmap_init(mgui_hashmap *self) { + self->entries = NULL; + self->capacity = 0; + self->size = 0; +} + +void mgui_hashmap_deinit(mgui_hashmap *self) { + if(self->entries) { + for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) { + mgui_hashmap_entry *entry = self->entries[i]; + while(entry) { + mgui_hashmap_entry *next = entry->next; + mgui_free(next); + entry = next; + } + } + + mgui_free(self->entries); + self->entries = NULL; + } + self->capacity = 0; + self->size = 0; +} + +static void mgui_hashmap_move_entry_to_front(mgui_hashmap *self, size_t index, mgui_hashmap_entry *new_entry) { + new_entry->next = self->entries[index]; + self->entries[index] = new_entry; +} + +static void mgui_hashmap_reorder_nodes(mgui_hashmap *self, size_t prev_capacity) { + for(size_t i = 0; i < CAP_NUM_ENTRIES(prev_capacity); ++i) { + mgui_hashmap_entry *entry = self->entries[i]; + mgui_hashmap_entry *prev_entry = NULL; + while(entry) { + const uint64_t new_index = HASH_TO_INDEX(entry->hash); + mgui_hashmap_entry *next_entry = entry->next; + + if(new_index != i) { + /* Remove entry by replacing this entry with the next entry */ + if(prev_entry) + prev_entry->next = next_entry; + else + self->entries[i] = next_entry; + + /* Insert the entry at the new index */ + mgui_hashmap_move_entry_to_front(self, new_index, entry); + } else { + prev_entry = entry; + } + + entry = next_entry; + } + } +} + +static void mgui_hashmap_ensure_capacity(mgui_hashmap *self, size_t new_capacity) { + if(self->capacity > new_capacity) + return; + + size_t cap = self->capacity; + if(cap == 0) + cap = 8; + + while(cap < new_capacity) { + cap = cap + (cap >> 1); /* *= 1.5 */ + } + + size_t prev_capacity = self->capacity; + self->capacity = align_to(cap, sizeof(mgui_hashmap_entry*)); + self->entries = mgui_realloc(self->entries, self->capacity); + + memset((char*)self->entries + prev_capacity, 0, self->capacity - prev_capacity); + mgui_hashmap_reorder_nodes(self, prev_capacity); +} + +void mgui_hashmap_insert(mgui_hashmap *self, const char *key, size_t key_size, void *value, uint64_t *hash_out) { + mgui_hashmap_ensure_capacity(self, (self->size + 1) * sizeof(mgui_hashmap_entry*)); + ++self->size; + + const uint64_t hash = mgui_hashmap_hash(key, key_size); + const size_t index = HASH_TO_INDEX(hash); + +#ifndef NDEBUG + void *value_out; + assert(!mgui_hashmap_get_by_hash(self, key, key_size, hash, &value_out)); +#endif + + if(hash_out) + *hash_out = hash; + + mgui_hashmap_entry *new_entry = mgui_alloc(sizeof(mgui_hashmap_entry) + key_size); + new_entry->hash = hash; + new_entry->value = value; + new_entry->key_size = key_size; + memcpy(HASHMAP_ENTRY_GET_KEY(new_entry), key, key_size); + mgui_hashmap_move_entry_to_front(self, index, new_entry); +} + +bool mgui_hashmap_get(mgui_hashmap *self, const char *key, size_t key_size, void **value_out) { + return mgui_hashmap_get_by_hash(self, key, key_size, mgui_hashmap_hash(key, key_size), value_out); +} + +bool mgui_hashmap_get_by_hash(mgui_hashmap *self, const char *key, size_t key_size, uint64_t hash, void **value_out) { + assert(hash == mgui_hashmap_hash(key, key_size)); + const size_t index = HASH_TO_INDEX(hash); + + mgui_hashmap_entry *entry = self->entries[index]; + while(entry) { + if(hash == entry->hash && key_size == entry->key_size && memcmp(key, HASHMAP_ENTRY_GET_KEY(entry), key_size) == 0) { + *value_out = entry->value; + return true; + } + entry = entry->next; + } + return false; +} + +/* TODO: Optimize by using xxHash instead */ +/* fnv-1 hash */ +uint64_t mgui_hashmap_hash(const char *data, size_t size) { + const unsigned char *unsigned_data = (const unsigned char*)data; + uint64_t hash = 14695981039346656037ULL; + for(size_t i = 0; i < size; ++i) { + hash *= 1099511628211ULL; + hash ^= unsigned_data[i]; + } + return hash; +} |