sketch_hash_map.nx source
↩ module page · 256 lines · 7771 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
27import "syscalls.nx"
28import "sketch_types.nx"
29
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
34
35struct HashMapEntry {
36 key: i64,
37 value: i64,
38}
39
40struct HashMap {
41 entries: *HashMapEntry,
42 capacity: i64, // power of 2
43 mask: i64,
44 size: i64,
45 tombstones: i64, // count for diagnostic
46}
47
48// === construction =================================================
49
50func nx_hmap_is_pow2(n: i64) -> i64 {
51 if n < NX_HMAP_MIN_CAP { return 0 }
52 if n > NX_HMAP_MAX_CAP { return 0 }
53 if (n & (n - 1)) != 0 { return 0 }
54 return 1
55}
56
57func nx_hmap_alloc(capacity: i64) -> *HashMap {
58 if nx_hmap_is_pow2(capacity) != 1 { return 0 as *HashMap }
59 let raw: *u8 = sys_mmap(48)
60 let m: *HashMap = raw as *HashMap
61 let ent_raw: *u8 = sys_mmap(capacity * 16)
62 m.entries = ent_raw as *HashMapEntry
63 var i: i64 = 0
64 while i < capacity {
65 let e: *HashMapEntry = (m.entries as i64 + i * 16) as *HashMapEntry
66 e.key = NX_HMAP_EMPTY
67 e.value = 0
68 i = i + 1
69 }
70 m.capacity = capacity
71 m.mask = capacity - 1
72 m.size = 0
73 m.tombstones = 0
74 return m
75}
76
77// === hash + probe =================================================
78
79func nx_hmap_hash(key: i64) -> i64 {
80 let mixed: i64 = (key * 0x9E3779B97F4A7C15) & 0xFFFFFFFFFFFFFFFF
81 return mixed
82}
83
84func nx_hmap_entry_at(m: *HashMap, i: i64) -> *HashMapEntry {
85 return (m.entries as i64 + i * 16) as *HashMapEntry
86}
87
88// Probe for key. Returns:
89// - index of existing entry with this key, OR
90// - index of first empty slot (or tombstone) for insertion.
91// We always pick the first tombstone we see on the probe chain for
92// insertions, but continue past tombstones to find an existing key.
93
94func nx_hmap_probe_find(m: *HashMap, key: i64) -> i64 {
95 // Returns index of key, or -1 if absent. Stops at first EMPTY.
96 var i: i64 = nx_hmap_hash(key) & m.mask
97 var done: i64 = 0
98 var found: i64 = -1
99 while done == 0 {
100 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
101 if e.key == NX_HMAP_EMPTY {
102 done = 1
103 }
104 if done == 0 {
105 if e.key == key {
106 found = i
107 done = 1
108 }
109 }
110 if done == 0 {
111 i = (i + 1) & m.mask
112 }
113 }
114 return found
115}
116
117func nx_hmap_probe_insert(m: *HashMap, key: i64) -> i64 {
118 // Returns the slot to insert/update at, traversing tombstones.
119 var i: i64 = nx_hmap_hash(key) & m.mask
120 var first_tomb: i64 = -1
121 var done: i64 = 0
122 var slot: i64 = -1
123 while done == 0 {
124 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
125 if e.key == NX_HMAP_EMPTY {
126 if first_tomb >= 0 { slot = first_tomb }
127 if first_tomb < 0 { slot = i }
128 done = 1
129 }
130 if done == 0 {
131 if e.key == NX_HMAP_TOMBSTONE {
132 if first_tomb < 0 { first_tomb = i }
133 }
134 if e.key == key {
135 slot = i
136 done = 1
137 }
138 }
139 if done == 0 {
140 i = (i + 1) & m.mask
141 }
142 }
143 return slot
144}
145
146// === put ==========================================================
147
148func nx_hmap_put(m: *HashMap, key: i64, value: i64) -> i64 {
149 if key == NX_HMAP_EMPTY { return -1 }
150 if key == NX_HMAP_TOMBSTONE { return -1 }
151 let slot: i64 = nx_hmap_probe_insert(m, key)
152 if slot < 0 { return -1 }
153 let e: *HashMapEntry = nx_hmap_entry_at(m, slot)
154 if e.key != key {
155 // New insert: enforce load-factor cap.
156 let load_after: i64 = ((m.size + m.tombstones + 1) * 100) / m.capacity
157 if load_after > 70 { return -2 }
158 if e.key == NX_HMAP_TOMBSTONE { m.tombstones = m.tombstones - 1 }
159 m.size = m.size + 1
160 }
161 e.key = key
162 e.value = value
163 return 0
164}
165
166// === get / has ====================================================
167
168func nx_hmap_get(m: *HashMap, key: i64) -> i64 {
169 if key == NX_HMAP_EMPTY { return 0 }
170 if key == NX_HMAP_TOMBSTONE { return 0 }
171 let idx: i64 = nx_hmap_probe_find(m, key)
172 if idx < 0 { return 0 }
173 let e: *HashMapEntry = nx_hmap_entry_at(m, idx)
174 return e.value
175}
176
177func nx_hmap_has(m: *HashMap, key: i64) -> i64 {
178 if key == NX_HMAP_EMPTY { return 0 }
179 if key == NX_HMAP_TOMBSTONE { return 0 }
180 let idx: i64 = nx_hmap_probe_find(m, key)
181 if idx < 0 { return 0 }
182 return 1
183}
184
185// === remove =======================================================
186
187func nx_hmap_remove(m: *HashMap, key: i64) -> i64 {
188 if key == NX_HMAP_EMPTY { return -1 }
189 if key == NX_HMAP_TOMBSTONE { return -1 }
190 let idx: i64 = nx_hmap_probe_find(m, key)
191 if idx < 0 { return -1 }
192 let e: *HashMapEntry = nx_hmap_entry_at(m, idx)
193 e.key = NX_HMAP_TOMBSTONE
194 e.value = 0
195 m.size = m.size - 1
196 m.tombstones = m.tombstones + 1
197 return 0
198}
199
200// === introspection ================================================
201
202func nx_hmap_size(m: *HashMap) -> i64 {
203 return m.size
204}
205
206func nx_hmap_capacity(m: *HashMap) -> i64 {
207 return m.capacity
208}
209
210func nx_hmap_load_ppt(m: *HashMap) -> i64 {
211 if m.capacity == 0 { return 0 }
212 return (m.size * 1000) / m.capacity
213}
214
215func nx_hmap_clear(m: *HashMap) -> i64 {
216 var i: i64 = 0
217 while i < m.capacity {
218 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
219 e.key = NX_HMAP_EMPTY
220 e.value = 0
221 i = i + 1
222 }
223 m.size = 0
224 m.tombstones = 0
225 return 0
226}
227
228// === iteration ====================================================
229//
230// Caller-driven iteration: provide a start index, get back the next
231// non-empty/tombstone slot. Returns -1 when exhausted.
232
233func nx_hmap_next(m: *HashMap, from: i64) -> i64 {
234 var i: i64 = from
235 if i < 0 { i = 0 }
236 while i < m.capacity {
237 let e: *HashMapEntry = nx_hmap_entry_at(m, i)
238 if e.key != NX_HMAP_EMPTY {
239 if e.key != NX_HMAP_TOMBSTONE {
240 return i
241 }
242 }
243 i = i + 1
244 }
245 return -1
246}
247
248func nx_hmap_memory_bytes(m: *HashMap) -> i64 {
249 return 48 + m.capacity * 16
250}
251
252func nx_hmap_query_size(m: *HashMap) -> *ApproxI64 {
253 return nx_approx_new(m.size, NX_ENV_ABS, 0, 1000000000,
254 NX_MATURITY_PRODUCTION,
255 NX_ADV_HONEST)
256}