code wiki / (root) / map.nx

map.nx

buildroot/runtime/map.nx

7947 B255 linesdepth 3pulls 3 transitivereach 2 importersview sourcekind librarytopic map
docsdependenciesstructsconstsfunctions

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

syscalls.nx map.nx lru.nx map_test.nx

imports: syscalls.nx

imported by: lru.nxmap_test.nx

structs

25struct MapEntry {
34struct Map {

consts

32const MAP_ENTRY_BYTES: i64 = 32
44const FNV_OFFSET: i64 = 0xcbf29ce484222325
45const FNV_PRIME: i64 = 1099511628211 // 0x100000001b3

functions

47func map_hash_i64(k: i64) -> i64 {
61func map_hash_bytes(buf: *u8, n: i64) -> i64 {
73func map_grow(m: *Map) -> i64;
called by 1: map_insert
75func map_entry_at(m: *Map, i: i64) -> *MapEntry {
83func map_new(cap_hint: i64) -> *Map {
called by 2: lru_newmain
95func map_len(m: *Map) -> i64 { return m.len }
called by 1: main
101func map_insert(m: *Map, key: i64, val: i64) -> i64 {
169func map_get(m: *Map, key: i64, out: *i64) -> i64 {
204func map_remove(m: *Map, key: i64) -> i64 {
236func map_grow(m: *Map) -> i64 {
calls 1: map_insert