Re:An easy-to-implement, arena-friendly hash map
by fovc on Sunday October 01, 2023 @11:47AM
(#37727022)
Not much of a C programmer, but here’s my ChatGPT assisted (painstakingly…) attempt at a lookup function:
#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;
}
}
Re:An easy-to-implement, arena-friendly hash map
by MaxBarraclough on Sunday October 01, 2023 @01:58PM
(#37728590)
entryIndex is read before being assigned.
The original series of articles had me thinking about how to implement the normal hash table without leaking. I think it’s possible:
First consider a hash table using linear probing with a dedicated arena (restriction will be lifted later). That means memory can grow for free. However, resizing is still tricky because we need to rehash in place while ensuring we don’t “strand” any entries. This can be accomplished by iterating through the hash table entries in order, but starting at an empty entry and looping around. (Proof left as an exercise for the reader)
So now we have a hash table that can use realloc to grow. How to generalize for arenas? The key is that the HT will maintain a page map of sorts. The first page is of size M, the second is of size M, and thereafter they’ll be of size 2^n * M. Basically on each resize we double the total capacity by adding a new page. Since the pages are of variable width, though, how to map indexes to pages quickly? The key is to use ffs or ctz to get a rounded log2.