nx_map.nx source

1// map.nx -- Robin-hood hashmap with FNV-1a (Phase G8). 2// 3// Research: Celis 1986 (robin-hood hashing), Noll 1991 (FNV-1a). 4// Robin-hood hashing levels probe-distance variance so worst-case 5// lookup stays close to average. FNV-1a is simple, fast, and good 6// enough for integer + byte-string keys we'll hash in practice. 7// 8// Specialised to (i64, i64) entries for now — generalises to 9// Map<K, V> once parse.nx's multi-param generics ship. Use cases: 10// * Symbol tables in nxasm/nxld (name-hash → offset) 11// * Route tables in runtime/http.nx (path-hash → handler id) 12// * JSON object parse tables (key-hash → value index) 13// * Config stores (key-hash → value) 14// 15// Open addressing with linear probing; load-factor cap 0.75; power- 16// of-2 bucket count for AND-mask indexing. Deletions use tombstone 17// markers (so subsequent probes still find displaced entries). 18 19// nx_safety_envelope: 20// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 21// sil_target: SIL1 22// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 23// verdict: NOT_YET_EVALUATED 24 25import "nx_syscalls.nx" 26 27// Per-bucket metadata: 28// kind = 0: empty 29// kind = 1: occupied with (key, val) 30// kind = 2: tombstone 31struct MapEntry { 32 kind: i64, 33 key: i64, 34 val: i64, 35 probe: i64, // distance from ideal slot (for robin-hood) 36} 37 38const MAP_ENTRY_BYTES: i64 = 32 39 40struct Map { 41 entries: *MapEntry, 42 cap: i64, // power of 2 43 len: i64, // occupied entries (not counting tombstones) 44 mask: i64, // cap - 1 45} 46 47// FNV-1a 64-bit hash of an i64 key. Treats the key as 8 bytes LE. 48// Officially defined over byte streams; for i64 we mix each byte 49// through the standard offset-basis / prime. 50const FNV_OFFSET: i64 = 0xcbf29ce484222325 51const FNV_PRIME: i64 = 1099511628211 // 0x100000001b3 52 53func map_hash_i64(k: i64) -> i64 { 54 var h: i64 = FNV_OFFSET 55 var i: i64 = 0 56 while i < 8 { 57 let byte: i64 = (k >> (i * 8)) & 0xFF 58 h = h ^ byte 59 h = h * FNV_PRIME 60 i = i + 1 61 } 62 return h 63} 64 65// FNV-1a over a byte slice. Use for string-keyed maps (route 66// tables, config). Keys get pre-hashed by the caller. 67func map_hash_bytes(buf: *u8, n: i64) -> i64 { 68 var h: i64 = FNV_OFFSET 69 var i: i64 = 0 70 while i < n { 71 h = h ^ buf[i] 72 h = h * FNV_PRIME 73 i = i + 1 74 } 75 return h 76} 77 78// Forward decl: map_insert calls map_grow which is defined after it. 79func map_grow(m: *Map) -> i64; 80 81func map_entry_at(m: *Map, i: i64) -> *MapEntry { 82 let base: i64 = m.entries as i64 83 return (base + i * MAP_ENTRY_BYTES) as *MapEntry 84} 85 86// Allocate a map with at least `cap_hint` buckets (rounded up to a 87// power of 2, min 8). All entries start in kind=0 (empty) since 88// sys_mmap zeros the region. 89func map_new(cap_hint: i64) -> *Map { 90 var cap: i64 = 8 91 while cap < cap_hint { cap = cap * 2 } 92 let raw: *u8 = sys_mmap(64 + cap * MAP_ENTRY_BYTES + 16) 93 let m: *Map = raw as *Map 94 m.entries = (raw as i64 + 64) as *MapEntry 95 m.cap = cap 96 m.len = 0 97 m.mask = cap - 1 98 return m 99} 100 101func map_len(m: *Map) -> i64 { return m.len } 102 103// Insert (key, val). If key exists, overwrite. Robin-hood swap 104// rule: if the entry we're trying to place has travelled further 105// than the one currently in this slot, displace the resident and 106// continue probing with its data. Levels worst-case probe length. 107func map_insert(m: *Map, key: i64, val: i64) -> i64 { 108 // Grow if load factor would exceed 0.75. 109 if (m.len + 1) * 4 > m.cap * 3 { 110 map_grow(m) 111 } 112 var k: i64 = key 113 var v: i64 = val 114 var probe: i64 = 0 115 var idx: i64 = map_hash_i64(k) & m.mask 116 117 var placed: i64 = 0 118 while placed == 0 { 119 let e: *MapEntry = map_entry_at(m, idx) 120 if e.kind == 0 { 121 // Empty slot — place. 122 e.kind = 1 123 e.key = k 124 e.val = v 125 e.probe = probe 126 m.len = m.len + 1 127 placed = 1 128 } 129 if placed == 0 { 130 if e.kind == 1 { 131 if e.key == k { 132 // Update existing key. 133 e.val = v 134 placed = 1 135 } 136 } 137 } 138 if placed == 0 { 139 if e.kind == 2 { 140 // Reuse tombstone for this key iff not already present 141 // further down the probe chain — but simpler path: 142 // just fill it. Rare pathological rewrites can leave 143 // duplicate keys; caller should treat as first-wins 144 // (matches most robin-hood implementations). 145 e.kind = 1 146 e.key = k 147 e.val = v 148 e.probe = probe 149 m.len = m.len + 1 150 placed = 1 151 } 152 } 153 if placed == 0 { 154 // e.kind == 1 and e.key != k — robin-hood swap? 155 if e.probe < probe { 156 // Steal this slot; displace the existing entry. 157 let tk: i64 = e.key 158 let tv: i64 = e.val 159 let tp: i64 = e.probe 160 e.key = k 161 e.val = v 162 e.probe = probe 163 k = tk 164 v = tv 165 probe = tp 166 } 167 probe = probe + 1 168 idx = (idx + 1) & m.mask 169 } 170 } 171 return 0 172} 173 174// Return 1 and write value to *out if key present; 0 otherwise. 175func map_get(m: *Map, key: i64, out: *i64) -> i64 { 176 var probe: i64 = 0 177 var idx: i64 = map_hash_i64(key) & m.mask 178 var found: i64 = 0 179 var stop: i64 = 0 180 while stop == 0 { 181 let e: *MapEntry = map_entry_at(m, idx) 182 if e.kind == 0 { 183 stop = 1 184 } 185 if stop == 0 { 186 if e.kind == 1 { 187 if e.key == key { 188 *out = e.val 189 found = 1 190 stop = 1 191 } 192 } 193 } 194 if stop == 0 { 195 // Robin-hood invariant: if we've probed further than this 196 // entry did, the key can't be further along. 197 if probe > e.probe { 198 stop = 1 199 } 200 } 201 if stop == 0 { 202 probe = probe + 1 203 idx = (idx + 1) & m.mask 204 } 205 } 206 return found 207} 208 209// Returns 1 if the key was present and removed, 0 otherwise. 210func map_remove(m: *Map, key: i64) -> i64 { 211 var probe: i64 = 0 212 var idx: i64 = map_hash_i64(key) & m.mask 213 var removed: i64 = 0 214 var stop: i64 = 0 215 while stop == 0 { 216 let e: *MapEntry = map_entry_at(m, idx) 217 if e.kind == 0 { stop = 1 } 218 if stop == 0 { 219 if e.kind == 1 { 220 if e.key == key { 221 e.kind = 2 // tombstone 222 m.len = m.len - 1 223 removed = 1 224 stop = 1 225 } 226 } 227 } 228 if stop == 0 { 229 if probe > e.probe { stop = 1 } 230 } 231 if stop == 0 { 232 probe = probe + 1 233 idx = (idx + 1) & m.mask 234 } 235 } 236 return removed 237} 238 239// Double capacity + rehash. Called transparently by map_insert when 240// load factor would exceed threshold. Preserves all keys; tombstones 241// are dropped. 242func map_grow(m: *Map) -> i64 { 243 let old_entries: *MapEntry = m.entries 244 let old_cap: i64 = m.cap 245 let new_cap: i64 = old_cap * 2 246 let raw: *u8 = sys_mmap(new_cap * MAP_ENTRY_BYTES + 64) 247 m.entries = raw as *MapEntry 248 m.cap = new_cap 249 m.mask = new_cap - 1 250 m.len = 0 251 var i: i64 = 0 252 while i < old_cap { 253 let base: i64 = old_entries as i64 254 let e: *MapEntry = (base + i * MAP_ENTRY_BYTES) as *MapEntry 255 if e.kind == 1 { 256 map_insert(m, e.key, e.val) 257 } 258 i = i + 1 259 } 260 return 0 261}