nx_sketch_hash_map.nx
buildroot/runtime/nx_sketch_hash_map.nx
about
sketch_hash_map.nx -- open-addressing hash map (i64 -> i64).
Foundational data-structure primitive. Linear-probing open-addressing
with power-of-2 capacity and 70%-load resize trigger (v1: no resize --
caller sizes correctly). Stores (key, value) pairs where key != 0
(zero reserved as empty sentinel).
API:
nx_hmap_put(m, key, value) upsert
nx_hmap_get(m, key) return value or 0 if absent
nx_hmap_has(m, key) 1 or 0
nx_hmap_remove(m, key) delete; returns 0/-1
nx_hmap_size(m) active entries
nx_hmap_clear(m) empty without freeing
Many sketches in this branch use ad-hoc linear-probe hash tables
(HllMap, LossyCounting, etc.). Promoting this to a sovereign
primitive lets future sketches compose against it instead of
re-implementing.
Production tier, exact semantics. No envelope returned.
DELETION: tombstone-based. Removed slots stay marked with a
special sentinel until the next put rebuilds the chain. This
keeps lookups O(1) average without rehashing.
dependencies 2 imports · 4 importers
imports: nx_syscalls.nxnx_sketch_types.nx
imported by: nx_eqsat.nxnx_sketch_cpc.nxnx_sketch_entropy.nxnx_sketch_naive_bayes.nx
structs
| 41 | struct HashMapEntry |
| 46 | struct HashMap |
consts
| 36 | const NX_HMAP_EMPTY: i64 = 0 |
| 37 | const NX_HMAP_TOMBSTONE: i64 = -1 |
| 38 | const NX_HMAP_MIN_CAP: i64 = 16 |
| 39 | const NX_HMAP_MAX_CAP: i64 = 67108864 // 64M entries |
functions
| 56 | func nx_hmap_is_pow2(n: i64) -> i64 called by 1: nx_hmap_alloc |
| 63 | func nx_hmap_alloc(capacity: i64) -> *HashMap |
| 85 | func nx_hmap_hash(key: i64) -> i64 |
| 90 | func nx_hmap_entry_at(m: *HashMap, i: i64) -> *HashMapEntry |
| 100 | func nx_hmap_probe_find(m: *HashMap, key: i64) -> i64 |
| 123 | func nx_hmap_probe_insert(m: *HashMap, key: i64) -> i64 |
| 154 | func nx_hmap_put(m: *HashMap, key: i64, value: i64) -> i64 |
| 174 | func nx_hmap_get(m: *HashMap, key: i64) -> i64 |
| 183 | func nx_hmap_has(m: *HashMap, key: i64) -> i64 |
| 193 | func nx_hmap_remove(m: *HashMap, key: i64) -> i64 |
| 208 | func nx_hmap_size(m: *HashMap) -> i64 |
| 212 | func nx_hmap_capacity(m: *HashMap) -> i64 |
| 216 | func nx_hmap_load_ppt(m: *HashMap) -> i64 |
| 221 | func nx_hmap_clear(m: *HashMap) -> i64 calls 1: nx_hmap_entry_at |
| 239 | func nx_hmap_next(m: *HashMap, from: i64) -> i64 |
| 254 | func nx_hmap_memory_bytes(m: *HashMap) -> i64 |
| 258 | func nx_hmap_query_size(m: *HashMap) -> *ApproxI64 calls 1: nx_approx_new |