nx_sketch_hash_map.nx source
↩ module page · 262 lines · 7772 B
1// sketch_hash_map.nx -- open-addressing hash map (i64 -> i64).
2//
3// Foundational data-structure primitive. Linear-probing open-addressing
4// with power-of-2 capacity and 70%-load resize trigger (v1: no resize --
5// caller sizes correctly). Stores (key, value) pairs where key != 0
6// (zero reserved as empty sentinel).
7//
8// API:
9// nx_hmap_put(m, key, value) upsert
10// nx_hmap_get(m, key) return value or 0 if absent
11// nx_hmap_has(m, key) 1 or 0
12// nx_hmap_remove(m, key) delete; returns 0/-1
13// nx_hmap_size(m) active entries
14// nx_hmap_clear(m) empty without freeing
15//
16// Many sketches in this branch use ad-hoc linear-probe hash tables
17// (HllMap, LossyCounting, etc.). Promoting this to a sovereign
18// primitive lets future sketches compose against it instead of
19// re-implementing.
20//
21// Production tier, exact semantics. No envelope returned.
22//
23// DELETION: tombstone-based. Removed slots stay marked with a
24// special sentinel until the next put rebuilds the chain. This
25// keeps lookups O(1) average without rehashing.
26
27// nx_safety_envelope:
28// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
29// sil_target: SIL1
30// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
31// verdict: NOT_YET_EVALUATED
32
33import "nx_syscalls.nx"
34import "nx_sketch_types.nx"
35
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
40
41struct HashMapEntry {
42 key: i64,
43 value: i64,
44}
45
46struct HashMap {
47 entries: *HashMapEntry,
48 capacity: i64, // power of 2
49 mask: i64,
50 size: i64,
51 tombstones: i64, // count for diagnostic
52}
53
54// === construction =================================================
55
56func nx_hmap_is_pow2(n: i64) -> i64 {
57 if n < NX_HMAP_MIN_CAP { return 0 }
58 if n > NX_HMAP_MAX_CAP { return 0 }
59 if (n & (n - 1)) != 0 { return 0 }
60 return 1
61}
62
63func nx_hmap_alloc(capacity: i64) -> *HashMap {
64 if nx_hmap_is_pow2(capacity) != 1 { return 0 as *HashMap }
65 let raw: *u8 = sys_mmap(48)
66 let m: *HashMap = raw as *HashMap
67 let ent_raw: *u8 = sys_mmap(capacity * 16)
68 m.entries = ent_raw as *HashMapEntry
69 var i: i64 = 0
70 while i < capacity {
71 let e: *HashMapEntry = (m.entries as i64 + i * 16) as *HashMapEntry
72 e.key = NX_HMAP_EMPTY
73 e.value = 0
74 i = i + 1
75 }
76 m.capacity = capacity
77 m.mask = capacity - 1
78 m.size = 0
79 m.tombstones = 0
80 return m
81}
82
83// === hash + probe =================================================
84
85func nx_hmap_hash(key: i64) -> i64 {
86 let mixed: i64 = (key * 0x9E3779B97F4A7C15) & 0xFFFFFFFFFFFFFFFF
87 return mixed
88}
89
90func nx_hmap_entry_at(m: *HashMap, i: i64) -> *HashMapEntry {
91 return (m.entries as i64 + i * 16) as *HashMapEntry
92}
93
94// Probe for key. Returns:
95// - index of existing entry with this key, OR
96// - index of first empty slot (or tombstone) for insertion.
97// We always pick the first tombstone we see on the probe chain for
98// insertions, but continue past tombstones to find an existing key.
99
100func nx_hmap_probe_find(m: *HashMap, key: i64) -> i64 {
101 // Returns index of key, or -1 if absent. Stops at first EMPTY.
102 var i: i64 = nx_hmap_hash(key) & m.mask
103 var done: i64 = 0
104 var found: i64 = -1
105 while done == 0 {
106 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
107 if e.key == NX_HMAP_EMPTY {
108 done = 1
109 }
110 if done == 0 {
111 if e.key == key {
112 found = i
113 done = 1
114 }
115 }
116 if done == 0 {
117 i = (i + 1) & m.mask
118 }
119 }
120 return found
121}
122
123func nx_hmap_probe_insert(m: *HashMap, key: i64) -> i64 {
124 // Returns the slot to insert/update at, traversing tombstones.
125 var i: i64 = nx_hmap_hash(key) & m.mask
126 var first_tomb: i64 = -1
127 var done: i64 = 0
128 var slot: i64 = -1
129 while done == 0 {
130 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
131 if e.key == NX_HMAP_EMPTY {
132 if first_tomb >= 0 { slot = first_tomb }
133 if first_tomb < 0 { slot = i }
134 done = 1
135 }
136 if done == 0 {
137 if e.key == NX_HMAP_TOMBSTONE {
138 if first_tomb < 0 { first_tomb = i }
139 }
140 if e.key == key {
141 slot = i
142 done = 1
143 }
144 }
145 if done == 0 {
146 i = (i + 1) & m.mask
147 }
148 }
149 return slot
150}
151
152// === put ==========================================================
153
154func nx_hmap_put(m: *HashMap, key: i64, value: i64) -> i64 {
155 if key == NX_HMAP_EMPTY { return -1 }
156 if key == NX_HMAP_TOMBSTONE { return -1 }
157 let slot: i64 = nx_hmap_probe_insert(m, key)
158 if slot < 0 { return -1 }
159 let e: *HashMapEntry = nx_hmap_entry_at(m, slot)
160 if e.key != key {
161 // New insert: enforce load-factor cap.
162 let load_after: i64 = ((m.size + m.tombstones + 1) * 100) / m.capacity
163 if load_after > 70 { return -2 }
164 if e.key == NX_HMAP_TOMBSTONE { m.tombstones = m.tombstones - 1 }
165 m.size = m.size + 1
166 }
167 e.key = key
168 e.value = value
169 return 0
170}
171
172// === get / has ====================================================
173
174func nx_hmap_get(m: *HashMap, key: i64) -> i64 {
175 if key == NX_HMAP_EMPTY { return 0 }
176 if key == NX_HMAP_TOMBSTONE { return 0 }
177 let idx: i64 = nx_hmap_probe_find(m, key)
178 if idx < 0 { return 0 }
179 let e: *HashMapEntry = nx_hmap_entry_at(m, idx)
180 return e.value
181}
182
183func nx_hmap_has(m: *HashMap, key: i64) -> i64 {
184 if key == NX_HMAP_EMPTY { return 0 }
185 if key == NX_HMAP_TOMBSTONE { return 0 }
186 let idx: i64 = nx_hmap_probe_find(m, key)
187 if idx < 0 { return 0 }
188 return 1
189}
190
191// === remove =======================================================
192
193func nx_hmap_remove(m: *HashMap, key: i64) -> i64 {
194 if key == NX_HMAP_EMPTY { return -1 }
195 if key == NX_HMAP_TOMBSTONE { return -1 }
196 let idx: i64 = nx_hmap_probe_find(m, key)
197 if idx < 0 { return -1 }
198 let e: *HashMapEntry = nx_hmap_entry_at(m, idx)
199 e.key = NX_HMAP_TOMBSTONE
200 e.value = 0
201 m.size = m.size - 1
202 m.tombstones = m.tombstones + 1
203 return 0
204}
205
206// === introspection ================================================
207
208func nx_hmap_size(m: *HashMap) -> i64 {
209 return m.size
210}
211
212func nx_hmap_capacity(m: *HashMap) -> i64 {
213 return m.capacity
214}
215
216func nx_hmap_load_ppt(m: *HashMap) -> i64 {
217 if m.capacity == 0 { return 0 }
218 return (m.size * 1000) / m.capacity
219}
220
221func nx_hmap_clear(m: *HashMap) -> i64 {
222 var i: i64 = 0
223 while i < m.capacity {
224 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
225 e.key = NX_HMAP_EMPTY
226 e.value = 0
227 i = i + 1
228 }
229 m.size = 0
230 m.tombstones = 0
231 return 0
232}
233
234// === iteration ====================================================
235//
236// Caller-driven iteration: provide a start index, get back the next
237// non-empty/tombstone slot. Returns -1 when exhausted.
238
239func nx_hmap_next(m: *HashMap, from: i64) -> i64 {
240 var i: i64 = from
241 if i < 0 { i = 0 }
242 while i < m.capacity {
243 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
244 if e.key != NX_HMAP_EMPTY {
245 if e.key != NX_HMAP_TOMBSTONE {
246 return i
247 }
248 }
249 i = i + 1
250 }
251 return -1
252}
253
254func nx_hmap_memory_bytes(m: *HashMap) -> i64 {
255 return 48 + m.capacity * 16
256}
257
258func nx_hmap_query_size(m: *HashMap) -> *ApproxI64 {
259 return nx_approx_new(m.size, NX_ENV_ABS, 0, 1000000000,
260 NX_MATURITY_PRODUCTION,
261 NX_ADV_HONEST)
262}