Not much of a C programmer, but here’s my ChatGPT assisted (painstakingly…) attempt at a lookup function. I think the log2 from math.h needs to be rewritten to

Not much of a C programmer, but here’s my ChatGPT assisted (painstakingly…) attempt at a lookup function. I think the log2 from math.h needs to be rewritten to use a fast bitwise implementation #include <stdint.h> #include <math.h> #include <stdbool.h> #define BASE_PAGE_BITS 14 #define MAX_PAGES 22 struct KeyValue { keytype key; valtype val; bool inUse; }; uint32_t hash(keytype key); int equals(keytype key1, keytype key2); struct HashTable { struct KeyValue pages[MAX_PAGES][]; uint8_t usedPages; }; typedef struct HashTable HashTable; struct KeyValue* lookup(HashTable* table, keytype key) { uint32_t hashed = hash(key); uint32_t lowerBits = hashed & ((1 << (BASE_PAGE_BITS + table->usedPages)) - 1); uint32_t pageIndex = (lowerBits == 0) ? 0 : (uint32_t)(log2(lowerBits >> BASE_PAGE_BITS) + 1); uint32_t entryIndex; for (;;) { uint32_t entryIndexRange = (pageIndex == 0) ? (1 << BASE_PAGE_BITS) : (1 << (pageIndex + BASE_PAGE_BITS - 1)); for (; entryIndex < entryIndexRange; entryIndex++) { struct KeyValue* page = table->pages[pageIndex]; if (!page[entryIndex].inUse) return &page[entryIndex]; if (equals(page[entryIndex].key, key)) return &page[entryIndex]; } pageIndex = (pageIndex + 1) % table->usedPages; entryIndex = 0; } }