code wiki / (root) / sketch_hash_map.nx

sketch_hash_map.nx

buildroot/runtime/sketch_hash_map.nx

7771 B256 linesdepth 4pulls 4 transitivereach 9 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

syscalls.nx sketch_types.nx sketch_hash_map.nx sketch_cpc.nx sketch_entropy.nx sketch_hash_map_test.nx sketch_naive_bayes.nx

imports: syscalls.nxsketch_types.nx

imported by: sketch_cpc.nxsketch_entropy.nxsketch_hash_map_test.nxsketch_naive_bayes.nx

structs

35struct HashMapEntry {
40struct HashMap {

consts

30const NX_HMAP_EMPTY: i64 = 0
31const NX_HMAP_TOMBSTONE: i64 = -1
32const NX_HMAP_MIN_CAP: i64 = 16
33const NX_HMAP_MAX_CAP: i64 = 67108864 // 64M entries

functions

50func nx_hmap_is_pow2(n: i64) -> i64 {
called by 1: nx_hmap_alloc
57func nx_hmap_alloc(capacity: i64) -> *HashMap {
79func nx_hmap_hash(key: i64) -> i64 {
84func nx_hmap_entry_at(m: *HashMap, i: i64) -> *HashMapEntry {
94func nx_hmap_probe_find(m: *HashMap, key: i64) -> i64 {
117func nx_hmap_probe_insert(m: *HashMap, key: i64) -> i64 {
148func nx_hmap_put(m: *HashMap, key: i64, value: i64) -> i64 {
168func nx_hmap_get(m: *HashMap, key: i64) -> i64 {
177func nx_hmap_has(m: *HashMap, key: i64) -> i64 {
called by 2: nx_cpc_addmain calls 1: nx_hmap_probe_find
187func nx_hmap_remove(m: *HashMap, key: i64) -> i64 {
202func nx_hmap_size(m: *HashMap) -> i64 {
206func nx_hmap_capacity(m: *HashMap) -> i64 {
210func nx_hmap_load_ppt(m: *HashMap) -> i64 {
called by 1: main
215func nx_hmap_clear(m: *HashMap) -> i64 {
called by 1: main calls 1: nx_hmap_entry_at
233func nx_hmap_next(m: *HashMap, from: i64) -> i64 {
248func nx_hmap_memory_bytes(m: *HashMap) -> i64 {
252func nx_hmap_query_size(m: *HashMap) -> *ApproxI64 {
called by 1: main calls 1: nx_approx_new