kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

pool.c (4083B)

      1 /* Interned strings. Open-addressed hash table keyed by FNV-1a
      2  * over the string body; the table holds Sym ids that index into a
      3  * heap-allocated `entries` array. Strings live in a per-Pool arena
      4  * (block-allocated), so str_data pointers are stable for the Pool's
      5  * lifetime. */
      6 
      7 #include "core/pool.h"
      8 
      9 #include <string.h>
     10 
     11 #include "core/arena.h"
     12 
     13 /* struct Pool is defined in pool.h so callers can size it (Compiler embeds
     14  * a Pool* allocated through Heap, and core.c needs sizeof(Pool)). */
     15 
     16 #define POOL_INITIAL_TABLE_CAP 256
     17 #define POOL_INITIAL_ENTRIES 64
     18 #define POOL_TABLE_LOAD_NUM 3
     19 #define POOL_TABLE_LOAD_DEN 4 /* grow when used*4 >= cap*3 */
     20 
     21 static u32 fnv1a(const char* s, size_t len) {
     22   u32 h = 0x811C9DC5u;
     23   size_t i;
     24   for (i = 0; i < len; ++i) {
     25     h ^= (u8)s[i];
     26     h *= 0x01000193u;
     27   }
     28   return h ? h : 1; /* avoid 0 (also reserved as "none") */
     29 }
     30 
     31 static int sym_eq(const PoolEntry* e, const char* s, size_t len, u32 h) {
     32   return e->hash == h && e->len == (u32)len && memcmp(e->data, s, len) == 0;
     33 }
     34 
     35 static void table_rehash(Pool* p, u32 new_cap) {
     36   Sym* new_table =
     37       (Sym*)p->heap->alloc(p->heap, sizeof(Sym) * new_cap, _Alignof(Sym));
     38   u32 i;
     39   if (!new_table) return;
     40   memset(new_table, 0, sizeof(Sym) * new_cap);
     41   for (i = 0; i < p->cap; ++i) {
     42     Sym sym = p->table[i];
     43     if (!sym) continue;
     44     const PoolEntry* e = &p->entries[sym];
     45     u32 mask = new_cap - 1;
     46     u32 j = e->hash & mask;
     47     while (new_table[j]) j = (j + 1) & mask;
     48     new_table[j] = sym;
     49   }
     50   if (p->table) p->heap->free(p->heap, p->table, sizeof(Sym) * p->cap);
     51   p->table = new_table;
     52   p->cap = new_cap;
     53 }
     54 
     55 static int entries_grow(Pool* p) {
     56   u32 new_cap;
     57   PoolEntry* ne;
     58   if (p->nentries < p->entries_cap) return 0;
     59   new_cap = p->entries_cap ? p->entries_cap * 2 : POOL_INITIAL_ENTRIES;
     60   ne = (PoolEntry*)p->heap->realloc(
     61       p->heap, p->entries, sizeof(*p->entries) * p->entries_cap,
     62       sizeof(*p->entries) * new_cap, _Alignof(PoolEntry));
     63   if (!ne) return 1;
     64   p->entries = ne;
     65   p->entries_cap = new_cap;
     66   return 0;
     67 }
     68 
     69 void pool_init(Pool* p, Heap* h) {
     70   p->heap = h;
     71   arena_init(&p->arena, h, 0);
     72   p->table = NULL;
     73   p->cap = 0;
     74   p->used = 0;
     75   p->entries = NULL;
     76   p->nentries = 0;
     77   p->entries_cap = 0;
     78   p->type_cache = NULL;
     79   table_rehash(p, POOL_INITIAL_TABLE_CAP);
     80   /* Reserve entry 0 as the "none" sentinel. */
     81   if (entries_grow(p) == 0) {
     82     p->entries[0].data = NULL;
     83     p->entries[0].len = 0;
     84     p->entries[0].hash = 0;
     85     p->nentries = 1;
     86   }
     87 }
     88 
     89 void pool_fini(Pool* p) {
     90   if (p->table) p->heap->free(p->heap, p->table, sizeof(Sym) * p->cap);
     91   if (p->entries)
     92     p->heap->free(p->heap, p->entries, sizeof(*p->entries) * p->entries_cap);
     93   arena_fini(&p->arena);
     94   p->table = NULL;
     95   p->entries = NULL;
     96 }
     97 
     98 Sym pool_intern_slice(Pool* p, Slice in) {
     99   const char* s = in.s;
    100   size_t len = in.len;
    101   u32 h, mask, i;
    102   Sym sym;
    103 
    104   if (!s || len == 0) return 0;
    105   if (p->used * POOL_TABLE_LOAD_DEN >= p->cap * POOL_TABLE_LOAD_NUM) {
    106     table_rehash(p, p->cap * 2);
    107   }
    108   h = fnv1a(s, len);
    109   mask = p->cap - 1;
    110   i = h & mask;
    111   while ((sym = p->table[i]) != 0) {
    112     if (sym_eq(&p->entries[sym], s, len, h)) return sym;
    113     i = (i + 1) & mask;
    114   }
    115   /* Not found: allocate a new entry. The stored buffer carries a trailing
    116    * NUL so a returned slice's pointer can be handed to a NUL-terminated
    117    * boundary API; the recorded `len` is the logical length, exclusive of the
    118    * terminator. The strtab content may carry embedded NULs, so exact-byte
    119    * consumers compare via (len, memcmp). */
    120   if (entries_grow(p)) return 0;
    121   {
    122     char* dst = (char*)arena_alloc(&p->arena, len + 1, 1);
    123     if (!dst) return 0;
    124     memcpy(dst, s, len);
    125     dst[len] = '\0';
    126     sym = (Sym)p->nentries++;
    127     p->entries[sym].data = dst;
    128     p->entries[sym].len = (u32)len;
    129     p->entries[sym].hash = h;
    130     p->table[i] = sym;
    131     p->used++;
    132   }
    133   return sym;
    134 }
    135 
    136 Slice pool_slice(Pool* p, Sym sym) {
    137   if (sym == 0 || sym >= p->nentries) return SLICE_NULL;
    138   return (Slice){.s = p->entries[sym].data, .len = p->entries[sym].len};
    139 }