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