Add dynamic font atlas creation (not finished)

1 files changed, 214 insertions, 0 deletions

diff --git a/src/graphics/font_char_map.c b/src/graphics/font_char_map.c
new file mode 100644
index 0000000..abaa56a
--- /dev/null
+++ b/src/graphics/font_char_map.c
@@ -0,0 +1,214 @@
+#include "../../include/mgl/graphics/font_char_map.h"
+#include <stdlib.h>
+
+/* TODO: Optimize % to & */
+
+/* Optimized div by sizeof(mgl_font_char_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
+
+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;
+    }
+}
+
+static void mgl_font_char_entry_deinit(mgl_font_char_entry *self) {
+    mgl_font_char_entry *next = self->next;
+    while(next) {
+        mgl_font_char_entry *next_next = next->next;
+        free(next);
+        next = next_next;
+    }
+}
+
+static void mgl_font_char_map_insert_entry(mgl_font_char_map *self, size_t index, uint32_t key, const mgl_font_glyph *value, mgl_font_char_entry *entry) {
+    entry->key = key;
+    entry->value = *value;
+    entry->next = self->entries[index];
+    self->entries[index] = entry;
+}
+
+static void mgl_font_char_map_reorder_nodes(mgl_font_char_map *self, size_t prev_capacity) {
+    for(size_t i = 0; i < CAP_NUM_ENTRIES(prev_capacity); ++i) {
+        mgl_font_char_entry *entry = self->entries[i];
+        if(!entry)
+            continue;
+
+        mgl_font_char_entry *prev_entry = NULL;
+        while(entry) {
+            const uint32_t hash = entry->key;
+            const size_t index = hash % CAP_NUM_ENTRIES(self->capacity);
+            mgl_font_char_entry *next_entry = entry->next; /* store next here so the next insert below doesn't cause an infinite loop */
+
+            if(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 */
+                mgl_font_char_map_insert_entry(self, index, entry->key, &entry->value, entry);
+            } else {
+                prev_entry = entry;
+            }
+
+            entry = next_entry;
+        }
+    }
+}
+
+static int mgl_font_char_map_ensure_capacity(mgl_font_char_map *self, size_t target_capacity) {
+    if(self->capacity >= target_capacity)
+        return 0;
+
+    size_t capacity = self->capacity;
+    if(capacity == 0)
+        capacity = 8;
+
+    while(capacity < target_capacity) {
+        capacity = capacity + (capacity >> 1); /* *= 1.5 = 1 + 0.5 */
+    }
+
+    capacity = align_to(capacity, sizeof(mgl_font_char_entry*));
+    void *new_data = realloc(self->entries, capacity);
+    if(!new_data)
+        return -1;
+
+    const size_t prev_capacity = self->capacity;
+    self->entries = new_data;
+    self->capacity = capacity;
+
+    for(size_t i = CAP_NUM_ENTRIES(prev_capacity); i < CAP_NUM_ENTRIES(self->capacity); ++i) {
+        self->entries[i] = NULL;
+    }
+
+    mgl_font_char_map_reorder_nodes(self, prev_capacity);
+    return 0;
+}
+
+void mgl_font_char_map_init(mgl_font_char_map *self) {
+    self->entries = NULL;
+    self->size = 0;
+    self->capacity = 0;
+}
+
+void mgl_font_char_map_deinit(mgl_font_char_map *self) {
+    if(self->entries) {
+        for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) {
+            if(self->entries[i]) {
+                mgl_font_char_entry_deinit(self->entries[i]);
+                free(self->entries[i]);
+            }
+        }
+        free(self->entries);
+        self->entries = NULL;
+    }
+    self->size = 0;
+    self->capacity = 0;
+}
+
+int mgl_font_char_map_insert(mgl_font_char_map *self, uint32_t key, const mgl_font_glyph *value, mgl_font_char_entry **inserted_entry) {
+    if(mgl_font_char_map_ensure_capacity(self, (self->size + 1) * sizeof(mgl_font_char_entry*)) != 0)
+        return -1;
+
+    ++self->size;
+    const uint32_t hash = key;
+    const size_t index = hash % CAP_NUM_ENTRIES(self->capacity);
+
+    mgl_font_char_entry *entry = malloc(sizeof(mgl_font_char_entry));
+    if(!entry)
+        return -1;
+    
+    mgl_font_char_map_insert_entry(self, index, key, value, entry);
+    entry->render_offset = (mgl_vec2i){ 0, 0 };
+    entry->rendered = false;
+    if(inserted_entry)
+        *inserted_entry = entry;
+
+    return 0;
+}
+
+mgl_font_char_entry* mgl_font_char_map_get(const mgl_font_char_map *self, uint32_t key) {
+    if(self->capacity == 0)
+        return NULL;
+
+    const uint32_t hash = key;
+    const size_t index = hash % CAP_NUM_ENTRIES(self->capacity);
+
+    mgl_font_char_entry *entry = self->entries[index];
+    while(entry) {
+        if(entry->key == key)
+            return entry;
+        entry = entry->next;
+    }
+
+    return NULL;
+}
+
+void mgl_font_char_map_clear_rendered(mgl_font_char_map *self) {
+    if(!self->entries)
+        return;
+
+    for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) {
+        mgl_font_char_entry *entry = self->entries[i];
+        if(!entry)
+            continue;
+        
+        while(entry) {
+            entry->rendered = false;
+            entry = entry->next;
+        }
+    }
+}
+
+mgl_font_char_iterator mgl_font_char_map_begin(mgl_font_char_map *self) {
+    mgl_font_char_iterator it;
+    it.char_map = self;
+    it.index = 0;
+    it.value = NULL;
+
+    if(!self->entries)
+        return it;
+
+    for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) {
+        mgl_font_char_entry *entry = self->entries[i];
+        if(entry) {
+            it.index = i;
+            it.value = entry;
+            break;
+        }
+    }
+
+    return it;
+}
+
+void mgl_font_char_iterator_next(mgl_font_char_iterator *self) {
+    if(!self->value)
+        return;
+
+    if(self->value->next) {
+        self->value = self->value->next;
+        return;
+    }
+
+    for(size_t i = self->index + 1; i < CAP_NUM_ENTRIES(self->char_map->capacity); ++i) {
+        mgl_font_char_entry *entry = self->char_map->entries[i];
+        if(entry) {
+            self->index = i;
+            self->value = entry;
+            return;
+        }
+    }
+
+    self->value = NULL;
+}