sketch_counting_bloom_test.nx source
↩ module page · 144 lines · 4881 B
1// sketch_counting_bloom_test.nx -- Counting Bloom with delete + multi-set.
2
3import "syscalls.nx"
4import "sketch_counting_bloom.nx"
5import "sketch_types.nx"
6
7func main() -> i64 {
8 // ---- alloc ----
9 let cb: *CountingBloom = nx_cb_alloc(8192, 5)
10 if cb == (0 as *CountingBloom) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
11 // Reject non-power-of-2.
12 if nx_cb_alloc(100, 4) != (0 as *CountingBloom) {
13 return __syscall(93, 6, 0, 0, 0, 0, 0)
14 }
15 if nx_cb_alloc(16, 0) != (0 as *CountingBloom) {
16 return __syscall(93, 7, 0, 0, 0, 0, 0)
17 }
18
19 // ---- empty contains 0 ----
20 if nx_cb_contains(cb, "alice", 5) != 0 {
21 return __syscall(93, 10, 0, 0, 0, 0, 0)
22 }
23
24 // ---- insert + contains ----
25 nx_cb_insert(cb, "alice", 5)
26 nx_cb_insert(cb, "bob", 3)
27 if nx_cb_contains(cb, "alice", 5) != 1 {
28 return __syscall(93, 20, 0, 0, 0, 0, 0)
29 }
30 if nx_cb_contains(cb, "bob", 3) != 1 {
31 return __syscall(93, 21, 0, 0, 0, 0, 0)
32 }
33 if cb.n_inserted != 2 {
34 return __syscall(93, 22, 0, 0, 0, 0, 0)
35 }
36
37 // ---- DELETE: removes presence ----
38 if nx_cb_delete(cb, "alice", 5) != 0 {
39 return __syscall(93, 30, 0, 0, 0, 0, 0)
40 }
41 if nx_cb_contains(cb, "alice", 5) != 0 {
42 return __syscall(93, 31, 0, 0, 0, 0, 0)
43 }
44 // bob still present.
45 if nx_cb_contains(cb, "bob", 3) != 1 {
46 return __syscall(93, 32, 0, 0, 0, 0, 0)
47 }
48 if cb.n_inserted != 1 {
49 return __syscall(93, 33, 0, 0, 0, 0, 0)
50 }
51 // Re-delete returns -1 (was already removed).
52 if nx_cb_delete(cb, "alice", 5) != -1 {
53 return __syscall(93, 34, 0, 0, 0, 0, 0)
54 }
55
56 // ---- MULTI-SET: multiplicity tracking ----
57 let cb2: *CountingBloom = nx_cb_alloc(8192, 5)
58 // Insert "alice" 7 times.
59 var i: i64 = 0
60 while i < 7 {
61 nx_cb_insert(cb2, "alice", 5)
62 i = i + 1
63 }
64 let mult_alice: i64 = nx_cb_estimate_multiplicity(cb2, "alice", 5)
65 if mult_alice != 7 {
66 return __syscall(93, 40, 0, 0, 0, 0, 0)
67 }
68 // Item not inserted -> multiplicity 0 (or false-positive cap).
69 let mult_carol: i64 = nx_cb_estimate_multiplicity(cb2, "carol", 5)
70 if mult_carol > 1 { // small chance of FP collision, but should be 0
71 return __syscall(93, 41, 0, 0, 0, 0, 0)
72 }
73
74 // ---- SATURATION: insert 16+ times to trigger saturation ----
75 let cb3: *CountingBloom = nx_cb_alloc(8192, 5)
76 i = 0
77 while i < 20 {
78 nx_cb_insert(cb3, "saturated", 9)
79 i = i + 1
80 }
81 // Saturation events tracked (insertions beyond max counter value).
82 // For k=5 counters each saturating at 15, items 16..20 each cause
83 // 5 saturation events -> total saturations = 5 * 5 = 25.
84 if cb3.saturations < 5 {
85 return __syscall(93, 50, 0, 0, 0, 0, 0)
86 }
87 // Multiplicity capped at MAX (15) even though true mult = 20.
88 let m_sat: i64 = nx_cb_estimate_multiplicity(cb3, "saturated", 9)
89 if m_sat != 15 {
90 return __syscall(93, 51, 0, 0, 0, 0, 0)
91 }
92 // Contains still returns 1.
93 if nx_cb_contains(cb3, "saturated", 9) != 1 {
94 return __syscall(93, 52, 0, 0, 0, 0, 0)
95 }
96
97 // ---- typed envelope ----
98 let q: *ApproxI64 = nx_cb_query(cb2, "alice", 5)
99 if q.envelope_kind != NX_ENV_ABS {
100 return __syscall(93, 60, 0, 0, 0, 0, 0)
101 }
102 // param_a tracks saturations.
103 if q.param_a != 0 { // cb2 has no saturation
104 return __syscall(93, 61, 0, 0, 0, 0, 0)
105 }
106 // alice is present.
107 if q.value != 1 {
108 return __syscall(93, 62, 0, 0, 0, 0, 0)
109 }
110
111 // Saturated filter query: param_a > 0.
112 let q_sat: *ApproxI64 = nx_cb_query(cb3, "saturated", 9)
113 if q_sat.param_a == 0 { // should reflect cb3 saturation count
114 return __syscall(93, 63, 0, 0, 0, 0, 0)
115 }
116
117 // ---- merge ----
118 let m_a: *CountingBloom = nx_cb_alloc(8192, 5)
119 let m_b: *CountingBloom = nx_cb_alloc(8192, 5)
120 nx_cb_insert(m_a, "x", 1)
121 nx_cb_insert(m_a, "x", 1)
122 nx_cb_insert(m_b, "x", 1)
123 nx_cb_insert(m_b, "y", 1)
124 let merged: *CountingBloom = nx_cb_merge(m_a, m_b)
125 if merged == (0 as *CountingBloom) {
126 return __syscall(93, 70, 0, 0, 0, 0, 0)
127 }
128 // x: 2 + 1 = 3.
129 let m_x: i64 = nx_cb_estimate_multiplicity(merged, "x", 1)
130 if m_x != 3 {
131 return __syscall(93, 71, 0, 0, 0, 0, 0)
132 }
133 let m_y: i64 = nx_cb_estimate_multiplicity(merged, "y", 1)
134 if m_y != 1 {
135 return __syscall(93, 72, 0, 0, 0, 0, 0)
136 }
137 // Mismatched cap -> NULL.
138 let m_c: *CountingBloom = nx_cb_alloc(16384, 5)
139 if nx_cb_merge(m_a, m_c) != (0 as *CountingBloom) {
140 return __syscall(93, 73, 0, 0, 0, 0, 0)
141 }
142
143 return 0
144}