code wiki / (root) / nx_map.nx

nx_map.nx

buildroot/runtime/nx_map.nx

7946 B261 linesdepth 2pulls 2 transitivereach 1 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 · 1 importers

nx_syscalls.nx nx_map.nx nx_lru.nx

imports: nx_syscalls.nx

imported by: nx_lru.nx

structs

31struct MapEntry
40struct Map

consts

38const MAP_ENTRY_BYTES: i64 = 32
50const FNV_OFFSET: i64 = 0xcbf29ce484222325
51const FNV_PRIME: i64 = 1099511628211 // 0x100000001b3

functions

53func map_hash_i64(k: i64) -> i64
67func map_hash_bytes(buf: *u8, n: i64) -> i64
79func map_grow(m: *Map) -> i64;
called by 1: map_insert
81func map_entry_at(m: *Map, i: i64) -> *MapEntry
89func map_new(cap_hint: i64) -> *Map
called by 1: lru_new calls 1: sys_mmap
101func map_len(m: *Map) -> i64 { return m.len }
107func map_insert(m: *Map, key: i64, val: i64) -> i64
175func map_get(m: *Map, key: i64, out: *i64) -> i64
210func map_remove(m: *Map, key: i64) -> i64
242func map_grow(m: *Map) -> i64