#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 = 0; 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;
        }
    }