code wiki / (root) / nx_sketch_hash_map.nx

nx_sketch_hash_map.nx

buildroot/runtime/nx_sketch_hash_map.nx

7772 B262 linesdepth 3pulls 3 transitivereach 22 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

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

nx_syscalls.nx nx_sketch_types.nx nx_sketch_hash_map.nx nx_eqsat.nx nx_sketch_cpc.nx nx_sketch_entropy.nx nx_sketch_naive_bayes.nx

imports: nx_syscalls.nxnx_sketch_types.nx

imported by: nx_eqsat.nxnx_sketch_cpc.nxnx_sketch_entropy.nxnx_sketch_naive_bayes.nx

structs

41struct HashMapEntry
46struct HashMap

consts

36const NX_HMAP_EMPTY: i64 = 0
37const NX_HMAP_TOMBSTONE: i64 = -1
38const NX_HMAP_MIN_CAP: i64 = 16
39const NX_HMAP_MAX_CAP: i64 = 67108864 // 64M entries

functions

56func nx_hmap_is_pow2(n: i64) -> i64
called by 1: nx_hmap_alloc
63func nx_hmap_alloc(capacity: i64) -> *HashMap
85func nx_hmap_hash(key: i64) -> i64
90func nx_hmap_entry_at(m: *HashMap, i: i64) -> *HashMapEntry
100func nx_hmap_probe_find(m: *HashMap, key: i64) -> i64
123func nx_hmap_probe_insert(m: *HashMap, key: i64) -> i64
154func nx_hmap_put(m: *HashMap, key: i64, value: i64) -> i64
174func nx_hmap_get(m: *HashMap, key: i64) -> i64
183func nx_hmap_has(m: *HashMap, key: i64) -> i64
193func nx_hmap_remove(m: *HashMap, key: i64) -> i64
208func nx_hmap_size(m: *HashMap) -> i64
212func nx_hmap_capacity(m: *HashMap) -> i64
216func nx_hmap_load_ppt(m: *HashMap) -> i64
221func nx_hmap_clear(m: *HashMap) -> i64
239func nx_hmap_next(m: *HashMap, from: i64) -> i64
called by 1: nx_ent_bits_ppm calls 1: nx_hmap_entry_at
254func nx_hmap_memory_bytes(m: *HashMap) -> i64
258func nx_hmap_query_size(m: *HashMap) -> *ApproxI64
calls 1: nx_approx_new