aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
m---------depends/mgl0
-rw-r--r--include/hashmap.h38
-rw-r--r--src/hashmap.c155
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;
+}