nx_set.nx source
↩ module page · 95 lines · 3011 B
1// nx_set.nx -- unordered set of i64 elements.
2//
3// Thin wrapper over nx_hash that uses the value as both key and a
4// sentinel "1" payload. Foundation for:
5//
6// * Visited-set in graph traversals (DFS/BFS)
7// * Reachable-block analysis in opt
8// * Used-symbol tracking in nxld
9// * Dedup of result lists
10//
11// API:
12// nx_set_new(cap_pow2)
13// nx_set_add(s, x) -- 1 if newly added, 0 if already present
14// nx_set_has(s, x) -- 1 / 0
15// nx_set_count(s)
16//
17// Caller invariant (inherited from nx_hash): element 0 is reserved
18// (collides with empty-slot sentinel). If you need to track 0, use
19// nx_intern instead (which has its own remapping).
20
21// nx_safety_envelope:
22// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
23// sil_target: SIL1
24// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
25// verdict: NOT_YET_EVALUATED
26
27import "syscalls.nx"
28import "nx_hash.nx"
29
30struct NxSet {
31 h: *NxHash,
32}
33
34const NX_SET_BYTES: i64 = 8
35
36func nx_set_new(cap_pow2: i64) -> *NxSet {
37 let raw: *u8 = sys_mmap(NX_SET_BYTES)
38 let s: *NxSet = raw as *NxSet
39 s.h = nx_hash_new(cap_pow2)
40 return s
41}
42
43// Add `x`. Returns 1 if newly added, 0 if already present, -1 on full.
44func nx_set_add(s: *NxSet, x: i64) -> i64 {
45 if x == 0 { return -1 } // sentinel collision
46 if nx_hash_has(s.h, x) == 1 { return 0 }
47 let r: i64 = nx_hash_put(s.h, x, 1)
48 if r < 0 { return -1 }
49 return 1
50}
51
52func nx_set_has(s: *NxSet, x: i64) -> i64 {
53 if x == 0 { return 0 }
54 return nx_hash_has(s.h, x)
55}
56
57func nx_set_count(s: *NxSet) -> i64 { return nx_hash_count(s.h) }
58
59// ---- self-test ----------------------------------------------------
60
61func main() -> i64 {
62 let s: *NxSet = nx_set_new(64)
63 if nx_set_count(s) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
64
65 // First add returns 1; duplicate add returns 0.
66 if nx_set_add(s, 42) != 1 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
67 if nx_set_add(s, 42) != 0 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
68 if nx_set_count(s) != 1 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
69
70 // has() works.
71 if nx_set_has(s, 42) != 1 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
72 if nx_set_has(s, 99) != 0 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
73
74 // Add 30 distinct elements; count == 31.
75 var k: i64 = 1
76 while k <= 30 {
77 if nx_set_add(s, k) != 1 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
78 k = k + 1
79 }
80 if nx_set_count(s) != 31 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
81
82 // All present.
83 var j: i64 = 1
84 while j <= 30 {
85 if nx_set_has(s, j) != 1 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
86 j = j + 1
87 }
88 if nx_set_has(s, 42) != 1 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
89
90 // Element 0 is reserved -- rejected.
91 if nx_set_add(s, 0) != -1 { return __syscall(93, 60, 0, 0, 0, 0, 0) }
92 if nx_set_has(s, 0) != 0 { return __syscall(93, 61, 0, 0, 0, 0, 0) }
93
94 return 0
95}