map.nx
buildroot/runtime/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 · 2 importers
imports: syscalls.nx
imported by: lru.nxmap_test.nx
structs
| 25 | struct MapEntry { |
| 34 | struct Map { |
consts
| 32 | const MAP_ENTRY_BYTES: i64 = 32 |
| 44 | const FNV_OFFSET: i64 = 0xcbf29ce484222325 |
| 45 | const FNV_PRIME: i64 = 1099511628211 // 0x100000001b3 |
functions
| 47 | func map_hash_i64(k: i64) -> i64 { |
| 61 | func map_hash_bytes(buf: *u8, n: i64) -> i64 { |
| 73 | func map_grow(m: *Map) -> i64;
called by 1: map_insert |
| 75 | func map_entry_at(m: *Map, i: i64) -> *MapEntry { |
| 83 | func map_new(cap_hint: i64) -> *Map { |
| 95 | func map_len(m: *Map) -> i64 { return m.len }
called by 1: main |
| 101 | func map_insert(m: *Map, key: i64, val: i64) -> i64 { |
| 169 | func map_get(m: *Map, key: i64, out: *i64) -> i64 { |
| 204 | func map_remove(m: *Map, key: i64) -> i64 { |
| 236 | func map_grow(m: *Map) -> i64 {
calls 1: map_insert |