From e52886f8bea55fb3c9ff973b16ed812549cd1f22 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Wed, 8 Dec 2021 03:36:16 +0100 Subject: Optimize hash map % to & --- src/graphics/font_char_map.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/src/graphics/font_char_map.c b/src/graphics/font_char_map.c index 64c4674..fc1c2e5 100644 --- a/src/graphics/font_char_map.c +++ b/src/graphics/font_char_map.c @@ -1,8 +1,6 @@ #include "../../include/mgl/graphics/font_char_map.h" #include -/* TODO: Optimize % to & */ - /* Optimized div by sizeof(mgl_font_char_entry*) */ #if INTPTR_MAX == INT64_MAX #define CAP_NUM_ENTRIES(cap) ((cap) >> 3) @@ -12,6 +10,8 @@ #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)) + /* |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)); @@ -47,7 +47,7 @@ static void mgl_font_char_map_reorder_nodes(mgl_font_char_map *self, size_t prev 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); + const size_t index = HASH_TO_INDEX(hash); 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) { @@ -77,7 +77,7 @@ static int mgl_font_char_map_ensure_capacity(mgl_font_char_map *self, size_t tar capacity = 8; while(capacity < target_capacity) { - capacity = capacity + (capacity >> 1); /* *= 1.5 = 1 + 0.5 */ + capacity = capacity + (capacity >> 1); /* *= 1.5 */ } capacity = align_to(capacity, sizeof(mgl_font_char_entry*)); @@ -124,7 +124,7 @@ int mgl_font_char_map_insert(mgl_font_char_map *self, uint32_t key, const mgl_fo ++self->size; const uint32_t hash = key; - const size_t index = hash % CAP_NUM_ENTRIES(self->capacity); + const size_t index = HASH_TO_INDEX(hash); mgl_font_char_entry *entry = malloc(sizeof(mgl_font_char_entry)); if(!entry) @@ -144,7 +144,7 @@ mgl_font_char_entry* mgl_font_char_map_get(const mgl_font_char_map *self, uint32 return NULL; const uint32_t hash = key; - const size_t index = hash % CAP_NUM_ENTRIES(self->capacity); + const size_t index = HASH_TO_INDEX(hash); mgl_font_char_entry *entry = self->entries[index]; while(entry) { -- cgit v1.2.3