sketch_hash_map.nx
buildroot/runtime/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: syscalls.nxsketch_types.nx
imported by: sketch_cpc.nxsketch_entropy.nxsketch_hash_map_test.nxsketch_naive_bayes.nx
structs
| 35 | struct HashMapEntry { |
| 40 | struct HashMap { |
consts
| 30 | const NX_HMAP_EMPTY: i64 = 0 |
| 31 | const NX_HMAP_TOMBSTONE: i64 = -1 |
| 32 | const NX_HMAP_MIN_CAP: i64 = 16 |
| 33 | const NX_HMAP_MAX_CAP: i64 = 67108864 // 64M entries |
functions
| 50 | func nx_hmap_is_pow2(n: i64) -> i64 {
called by 1: nx_hmap_alloc |
| 57 | func nx_hmap_alloc(capacity: i64) -> *HashMap { |
| 79 | func nx_hmap_hash(key: i64) -> i64 { |
| 84 | func nx_hmap_entry_at(m: *HashMap, i: i64) -> *HashMapEntry { |
| 94 | func nx_hmap_probe_find(m: *HashMap, key: i64) -> i64 { |
| 117 | func nx_hmap_probe_insert(m: *HashMap, key: i64) -> i64 { |
| 148 | func nx_hmap_put(m: *HashMap, key: i64, value: i64) -> i64 {
called by 4: nx_cpc_addnx_ent_addmainnx_nb_observe_feature calls 2: nx_hmap_probe_insertnx_hmap_entry_at |
| 168 | func nx_hmap_get(m: *HashMap, key: i64) -> i64 { |
| 177 | func nx_hmap_has(m: *HashMap, key: i64) -> i64 { |
| 187 | func nx_hmap_remove(m: *HashMap, key: i64) -> i64 { |
| 202 | func nx_hmap_size(m: *HashMap) -> i64 { |
| 206 | func nx_hmap_capacity(m: *HashMap) -> i64 { |
| 210 | func nx_hmap_load_ppt(m: *HashMap) -> i64 {
called by 1: main |
| 215 | func nx_hmap_clear(m: *HashMap) -> i64 { |
| 233 | func nx_hmap_next(m: *HashMap, from: i64) -> i64 { |
| 248 | func nx_hmap_memory_bytes(m: *HashMap) -> i64 { |
| 252 | func nx_hmap_query_size(m: *HashMap) -> *ApproxI64 { |