nx_hash.nx source
↩ module page · 202 lines · 6868 B
1// nx_hash.nx -- open-addressing hash table (linear probing, fnv-1a).
2//
3// FOUNDATION primitive. Any code that needs O(1) lookup uses this:
4// * Symbol table during link
5// * String interning in lex
6// * Deduplication in opt
7// * Visited-set in graph algorithms
8//
9// Today every NishiLang module that needs lookup either does
10// linear scan or builds an ad-hoc table. Centralising removes
11// ~hundred lines of repeated code across the runtime.
12//
13// Algorithm: open-addressing with linear probing. Power-of-two
14// capacity for fast modulo (mask = cap - 1). Hash via FNV-1a
15// (Fowler-Noll-Vo, public domain, well-distributed).
16//
17// Load factor: caller-controlled; resize is a TODO (v0.0.1 expects
18// caller to size the table appropriately).
19//
20// API:
21// nx_hash_new(cap_pow2) -- construct
22// nx_hash_put(t, key, val) -- insert / overwrite
23// nx_hash_get(t, key) -- lookup; -1 = not found
24// nx_hash_has(t, key) -- 1 = present
25// nx_hash_count(t) -- number of entries
26//
27// Keys are i64 (use the FNV-1a hash); values are i64.
28// String interning users compute the FNV-1a of their string and
29// use that as the i64 key.
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "syscalls.nx"
38const NX_MAGIC_1490: i64 = 1490
39
40// ---- FNV-1a 64-bit ------------------------------------------------
41
42const NX_HASH_FNV_OFFSET: i64 = 0xCBF29CE484222325
43const NX_HASH_FNV_PRIME: i64 = 0x100000001B3
44
45func nx_hash_fnv1a_bytes(buf: *u8, len: i64) -> i64 {
46 var h: i64 = NX_HASH_FNV_OFFSET
47 var i: i64 = 0
48 while i < len {
49 h = h ^ buf[i]
50 h = h * NX_HASH_FNV_PRIME
51 i = i + 1
52 }
53 return h
54}
55
56// FNV-1a of an i64 (treated as 8 little-endian bytes).
57func nx_hash_fnv1a_i64(x: i64) -> i64 {
58 var h: i64 = NX_HASH_FNV_OFFSET
59 var i: i64 = 0
60 while i < 8 {
61 let b: i64 = (x >> (i * 8)) & 0xFF
62 h = h ^ b
63 h = h * NX_HASH_FNV_PRIME
64 i = i + 1
65 }
66 return h
67}
68
69// ---- table struct -------------------------------------------------
70
71// Sentinel: a key of NX_HASH_EMPTY (= 0) marks an empty slot.
72// Callers should NOT use 0 as a real key (or should remap it).
73const NX_HASH_EMPTY: i64 = 0
74const NX_HASH_TOMBSTONE: i64 = -1
75
76struct NxHash {
77 keys: *i64, // capacity i64 slots
78 vals: *i64, // capacity i64 slots
79 cap: i64, // power-of-two
80 mask: i64, // cap - 1
81 n: i64, // entries used
82}
83
84const NX_HASH_BYTES: i64 = 40
85
86func nx_hash_new(cap_pow2: i64) -> *NxHash {
87 let raw: *u8 = sys_mmap(NX_HASH_BYTES)
88 let t: *NxHash = raw as *NxHash
89 t.keys = sys_mmap(cap_pow2 * 8) as *i64
90 t.vals = sys_mmap(cap_pow2 * 8) as *i64
91 t.cap = cap_pow2
92 t.mask = cap_pow2 - 1
93 t.n = 0
94 // sys_mmap returns zero pages, so keys[i] = 0 = NX_HASH_EMPTY.
95 return t
96}
97
98// ---- core ops ----------------------------------------------------
99
100// Returns the slot index where `key` lives or where it would be
101// inserted (the first empty / tombstone slot in its probe chain).
102// Probe is bounded by cap to avoid infinite loops on full tables.
103func nx_hash_probe(t: *NxHash, key: i64) -> i64 {
104 let h: i64 = nx_hash_fnv1a_i64(key)
105 var slot: i64 = h & t.mask
106 var tries: i64 = 0
107 while tries < t.cap {
108 let k: i64 = t.keys[slot]
109 if k == NX_HASH_EMPTY { return slot }
110 if k == key { return slot }
111 slot = (slot + 1) & t.mask
112 tries = tries + 1
113 }
114 return -1 // table full
115}
116
117// Insert / overwrite. Returns 0 on success, -1 on full.
118func nx_hash_put(t: *NxHash, key: i64, val: i64) -> i64 {
119 let slot: i64 = nx_hash_probe(t, key)
120 if slot < 0 { return -1 }
121 if t.keys[slot] == NX_HASH_EMPTY { t.n = t.n + 1 }
122 t.keys[slot] = key
123 t.vals[slot] = val
124 return 0
125}
126
127// Lookup. Returns the value, or -1 if not found.
128func nx_hash_get(t: *NxHash, key: i64) -> i64 {
129 let slot: i64 = nx_hash_probe(t, key)
130 if slot < 0 { return -1 }
131 if t.keys[slot] != key { return -1 }
132 return t.vals[slot]
133}
134
135// Existence check. Returns 1 if key is present, 0 otherwise.
136func nx_hash_has(t: *NxHash, key: i64) -> i64 {
137 let slot: i64 = nx_hash_probe(t, key)
138 if slot < 0 { return 0 }
139 if t.keys[slot] != key { return 0 }
140 return 1
141}
142
143func nx_hash_count(t: *NxHash) -> i64 { return t.n }
144
145// ---- self-test ---------------------------------------------------
146
147func main() -> i64 {
148 let t: *NxHash = nx_hash_new(64)
149
150 // Empty table.
151 if nx_hash_count(t) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
152 if nx_hash_has(t, 42) != 0 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
153 if nx_hash_get(t, 42) != -1 { return __syscall(93, 12, 0, 0, 0, 0, 0) }
154
155 // Insert some entries.
156 nx_hash_put(t, 1, 100)
157 nx_hash_put(t, 2, 200)
158 nx_hash_put(t, 3, 300)
159 if nx_hash_count(t) != 3 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
160
161 // Lookups return the right values.
162 if nx_hash_get(t, 1) != 100 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
163 if nx_hash_get(t, 2) != 200 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
164 if nx_hash_get(t, 3) != 300 { return __syscall(93, 32, 0, 0, 0, 0, 0) }
165 if nx_hash_get(t, 99) != -1 { return __syscall(93, 33, 0, 0, 0, 0, 0) }
166
167 // has() is correct.
168 if nx_hash_has(t, 1) != 1 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
169 if nx_hash_has(t, 99) != 0 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
170
171 // Overwrite.
172 nx_hash_put(t, 2, 222)
173 if nx_hash_get(t, 2) != 222 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
174 if nx_hash_count(t) != 3 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
175
176 // Stress: insert 50 keys (cap 64; load factor 0.78).
177 var k: i64 = 100
178 while k < 150 {
179 nx_hash_put(t, k, k * 10)
180 k = k + 1
181 }
182 if nx_hash_count(t) != 53 { return __syscall(93, 60, 0, 0, 0, 0, 0) }
183 // Spot-check a few.
184 if nx_hash_get(t, 100) != 1000 { return __syscall(93, 61, 0, 0, 0, 0, 0) }
185 if nx_hash_get(t, 149) != NX_MAGIC_1490 { return __syscall(93, 62, 0, 0, 0, 0, 0) }
186
187 // FNV-1a stable + non-trivially distributed.
188 let h1: i64 = nx_hash_fnv1a_i64(1)
189 let h2: i64 = nx_hash_fnv1a_i64(2)
190 if h1 == h2 { return __syscall(93, 70, 0, 0, 0, 0, 0) }
191 // Same input, same output (deterministic).
192 if nx_hash_fnv1a_i64(1) != h1 { return __syscall(93, 71, 0, 0, 0, 0, 0) }
193
194 // Bytes-form FNV-1a.
195 let str: *u8 = sys_mmap(8)
196 str[0] = 0x4E; str[1] = 0x49; str[2] = 0x53; str[3] = 0x48
197 let hb: i64 = nx_hash_fnv1a_bytes(str, 4)
198 if hb == 0 { return __syscall(93, 80, 0, 0, 0, 0, 0) }
199 if nx_hash_fnv1a_bytes(str, 4) != hb { return __syscall(93, 81, 0, 0, 0, 0, 0) }
200
201 return 0
202}