kit

pool.c (8322B)

---

 /* Interned strings. Open-addressed hash table keyed by FNV-1a
  * over the string body; the table holds Sym ids that index into a
  * heap-allocated `entries` array. Strings live in a per-Pool arena
  * (block-allocated), so str_data pointers are stable for the Pool's
  * lifetime. */
 
 #include "core/pool.h"
 
 #include <string.h>
 
 #include "core/arena.h"
 
 /* struct Pool is defined in pool.h so callers can size it (Compiler embeds
  * a Pool* allocated through Heap, and core.c needs sizeof(Pool)). */
 
 #define POOL_INITIAL_TABLE_CAP 256
 #define POOL_INITIAL_ENTRIES 64
 #define POOL_TABLE_LOAD_NUM 3
 #define POOL_TABLE_LOAD_DEN 4 /* grow when used*4 >= cap*3 */
 
 /* Cheap fold of (len + the first up-to-4 bytes) into a u32 cache key. This is
  * deliberately NOT FNV: the whole point of the accelerator cache is to skip the
  * full hash on repeats, so the key must be a couple of shifts/multiplies, not a
  * per-byte hash. Collisions are harmless — every cache hit byte-verifies. */
 static u32 pool_icache_fold(const char* s, size_t len) {
   u32 f = (u32)len * 0x9E3779B1u;
   if (len > 0) f = (f ^ (u8)s[0]) * 0x01000193u;
   if (len > 1) f = (f ^ (u8)s[1]) * 0x01000193u;
   if (len > 2) f = (f ^ (u8)s[2]) * 0x01000193u;
   if (len > 3) f = (f ^ (u8)s[3]) * 0x01000193u;
   return f;
 }
 
 static u32 fnv1a(const char* s, size_t len) {
   u32 h = 0x811C9DC5u;
   size_t i;
   for (i = 0; i < len; ++i) {
     h ^= (u8)s[i];
     h *= 0x01000193u;
   }
   return h ? h : 1; /* avoid 0 (also reserved as "none") */
 }
 
 static int sym_eq(const PoolEntry* e, const char* s, size_t len, u32 h) {
   /* Inline byte loop instead of memcmp: the library is built -ffreestanding,
    * under which clang emits a real memcmp libcall for a runtime length rather
    * than inlining it. For the short identifiers the frontend interns, the call
    * dispatch dominates the few-byte compare. The hash+len guards reject almost
    * all non-matches before any byte is read. No word-at-a-time read: `s` points
    * into the borrowed lexer buffer with no trailing-NUL/padding guarantee, so an
    * over-wide load could overread at EOF; the byte loop is the safe form (and
    * matches include/kit/core.h kit_slice_eq). */
   size_t i;
   if (e->hash != h || e->len != (u32)len) return 0;
   for (i = 0; i < len; ++i)
     if (e->data[i] != s[i]) return 0;
   return 1;
 }
 
 static void table_rehash(Pool* p, u32 new_cap) {
   Sym* new_table =
       (Sym*)p->heap->alloc(p->heap, sizeof(Sym) * new_cap, _Alignof(Sym));
   u32 i;
   if (!new_table) return;
   memset(new_table, 0, sizeof(Sym) * new_cap);
   for (i = 0; i < p->cap; ++i) {
     Sym sym = p->table[i];
     if (!sym) continue;
     const PoolEntry* e = &p->entries[sym];
     u32 mask = new_cap - 1;
     u32 j = e->hash & mask;
     while (new_table[j]) j = (j + 1) & mask;
     new_table[j] = sym;
   }
   if (p->table) p->heap->free(p->heap, p->table, sizeof(Sym) * p->cap);
   p->table = new_table;
   p->cap = new_cap;
   /* Precompute the grow trigger so the per-intern load-factor test is a single
    * compare (no multiplies). cap is always a power of two >= INITIAL_TABLE_CAP,
    * so cap*LOAD_NUM is divisible by LOAD_DEN and this is exact: the trigger
    * `used >= grow_threshold` fires at the same point as `used*DEN >= cap*NUM`.
    * u64 in the product avoids overflow when cap is large. */
   p->grow_threshold =
       (u32)((u64)new_cap * POOL_TABLE_LOAD_NUM / POOL_TABLE_LOAD_DEN);
 }
 
 static int entries_grow(Pool* p) {
   u32 new_cap;
   PoolEntry* ne;
   if (p->nentries < p->entries_cap) return 0;
   new_cap = p->entries_cap ? p->entries_cap * 2 : POOL_INITIAL_ENTRIES;
   ne = (PoolEntry*)p->heap->realloc(
       p->heap, p->entries, sizeof(*p->entries) * p->entries_cap,
       sizeof(*p->entries) * new_cap, _Alignof(PoolEntry));
   if (!ne) return 1;
   p->entries = ne;
   p->entries_cap = new_cap;
   return 0;
 }
 
 void pool_init(Pool* p, Heap* h) {
   p->heap = h;
   arena_init(&p->arena, h, 0);
   p->table = NULL;
   p->cap = 0;
   p->used = 0;
   p->entries = NULL;
   p->nentries = 0;
   p->entries_cap = 0;
   /* Direct-mapped intern accelerator, zero-init (sym 0 = empty slot). If the
    * allocation fails the cache stays NULL and intern simply runs the normal
    * hash+probe path — it is a pure accelerator. */
   p->icache = (PoolICacheSlot*)h->alloc(
       h, sizeof(PoolICacheSlot) * POOL_ICACHE_SIZE, _Alignof(PoolICacheSlot));
   if (p->icache)
     memset(p->icache, 0, sizeof(PoolICacheSlot) * POOL_ICACHE_SIZE);
   table_rehash(p, POOL_INITIAL_TABLE_CAP);
   /* Reserve entry 0 as the "none" sentinel. */
   if (entries_grow(p) == 0) {
     p->entries[0].data = NULL;
     p->entries[0].len = 0;
     p->entries[0].hash = 0;
     p->nentries = 1;
   }
 }
 
 void pool_fini(Pool* p) {
   if (p->table) p->heap->free(p->heap, p->table, sizeof(Sym) * p->cap);
   if (p->entries)
     p->heap->free(p->heap, p->entries, sizeof(*p->entries) * p->entries_cap);
   if (p->icache)
     p->heap->free(p->heap, p->icache,
                   sizeof(PoolICacheSlot) * POOL_ICACHE_SIZE);
   arena_fini(&p->arena);
   p->table = NULL;
   p->entries = NULL;
   p->icache = NULL;
 }
 
 Sym pool_intern_cstr(Pool* p, const char* z) {
   return pool_intern_slice(p, slice_from_cstr(z));
 }
 
 Sym pool_intern_slice(Pool* p, Slice in) {
   const char* s = in.s;
   size_t len = in.len;
   u32 h, mask, i;
   u32 fold = 0, cidx = 0;
   Sym sym;
 
   if (!s || len == 0) return 0;
 
   /* Direct-mapped accelerator: try to short-circuit BEFORE FNV+probe. On a hit
    * we byte-verify against the interned bytes (same compare sym_eq does), so
    * this can never return a wrong Sym. Misses/mismatches fall through to the
    * normal path and then re-prime this slot from the result. */
   if (p->icache) {
     fold = pool_icache_fold(s, len);
     cidx = fold & (POOL_ICACHE_SIZE - 1);
     {
       const PoolICacheSlot* slot = &p->icache[cidx];
       if (slot->keyhash == fold && slot->sym != 0) {
         const PoolEntry* e = &p->entries[slot->sym];
         if (e->len == (u32)len) {
           size_t k = 0;
           while (k < len && e->data[k] == s[k]) ++k;
           if (k == len) return slot->sym;
         }
       }
     }
   }
 
   if (p->used >= p->grow_threshold) {
     table_rehash(p, p->cap * 2);
   }
   h = fnv1a(s, len);
   mask = p->cap - 1;
   i = h & mask;
   /* Hoist the table/entries bases: they are stable across the probe (a grow
    * only happens after a miss, below), so the compiler need not reload them
    * from the Pool each iteration. This is the per-identifier intern probe. */
   {
     const Sym* table = p->table;
     const PoolEntry* ents = p->entries;
     while ((sym = table[i]) != 0) {
       if (sym_eq(&ents[sym], s, len, h)) {
         /* Prime the accelerator so the next occurrence skips FNV+probe. */
         if (p->icache) {
           p->icache[cidx].keyhash = fold;
           p->icache[cidx].sym = sym;
         }
         return sym;
       }
       i = (i + 1) & mask;
     }
   }
   /* Not found: allocate a new entry. The stored buffer carries a trailing
    * NUL so a returned slice's pointer can be handed to a NUL-terminated
    * boundary API; the recorded `len` is the logical length, exclusive of the
    * terminator. The strtab content may carry embedded NULs, so exact-byte
    * consumers compare via (len, memcmp). */
   if (entries_grow(p)) return 0;
   {
     char* dst = (char*)arena_alloc(&p->arena, len + 1, 1);
     if (!dst) return 0;
     /* Inline copy for the short-string common case: under -ffreestanding the
      * memcpy is a libcall, and interned spellings are short (a few bytes), so
      * the inline loop wins the call dispatch. Fall back to memcpy for the rare
      * long spelling (e.g. a big string-literal token routed through intern). */
     if (len <= 32) {
       size_t i;
       for (i = 0; i < len; ++i) dst[i] = s[i];
     } else {
       memcpy(dst, s, len);
     }
     dst[len] = '\0';
     sym = (Sym)p->nentries++;
     p->entries[sym].data = dst;
     p->entries[sym].len = (u32)len;
     p->entries[sym].hash = h;
     p->table[i] = sym;
     p->used++;
   }
   /* Prime the accelerator with the freshly interned spelling. */
   if (p->icache) {
     p->icache[cidx].keyhash = fold;
     p->icache[cidx].sym = sym;
   }
   return sym;
 }
 
 Slice pool_slice(Pool* p, Sym sym) {
   if (sym == 0 || sym >= p->nentries) return SLICE_NULL;
   return (Slice){.s = p->entries[sym].data, .len = p->entries[sym].len};
 }