nx_map.nx
buildroot/runtime/nx_map.nx
about
map.nx -- Robin-hood hashmap with FNV-1a (Phase G8).
Research: Celis 1986 (robin-hood hashing), Noll 1991 (FNV-1a).
Robin-hood hashing levels probe-distance variance so worst-case
lookup stays close to average. FNV-1a is simple, fast, and good
enough for integer + byte-string keys we'll hash in practice.
Specialised to (i64, i64) entries for now — generalises to
Map<K, V> once parse.nx's multi-param generics ship. Use cases:
* Symbol tables in nxasm/nxld (name-hash → offset)
* Route tables in runtime/http.nx (path-hash → handler id)
* JSON object parse tables (key-hash → value index)
* Config stores (key-hash → value)
Open addressing with linear probing; load-factor cap 0.75; power-
of-2 bucket count for AND-mask indexing. Deletions use tombstone
markers (so subsequent probes still find displaced entries).
dependencies 1 imports · 1 importers
imports: nx_syscalls.nx
imported by: nx_lru.nx
structs
| 31 | struct MapEntry |
| 40 | struct Map |
consts
| 38 | const MAP_ENTRY_BYTES: i64 = 32 |
| 50 | const FNV_OFFSET: i64 = 0xcbf29ce484222325 |
| 51 | const FNV_PRIME: i64 = 1099511628211 // 0x100000001b3 |
functions
| 53 | func map_hash_i64(k: i64) -> i64 |
| 67 | func map_hash_bytes(buf: *u8, n: i64) -> i64 |
| 79 | func map_grow(m: *Map) -> i64; called by 1: map_insert |
| 81 | func map_entry_at(m: *Map, i: i64) -> *MapEntry |
| 89 | func map_new(cap_hint: i64) -> *Map |
| 101 | func map_len(m: *Map) -> i64 { return m.len } |
| 107 | func map_insert(m: *Map, key: i64, val: i64) -> i64 |
| 175 | func map_get(m: *Map, key: i64, out: *i64) -> i64 |
| 210 | func map_remove(m: *Map, key: i64) -> i64 |
| 242 | func map_grow(m: *Map) -> i64 |