bitset.nx source
↩ module page · 185 lines · 5376 B
1// bitset.nx -- packed bit array with O(1) get / set / clear.
2//
3// Stores N boolean flags in ceil(N/64) i64 words. 8x denser
4// than bool[] (which nxc stores as i64 per element). Used for:
5// - SSA liveness (each block × each variable)
6// - garbage-collection mark bits (one bit per object)
7// - compiler dominance-frontier frontier sets
8// - simple set<i64> for small universes (port/file-descriptor tables)
9// - bloom filter internals (bitset + k hashes)
10//
11// Not a drop-in Set<K> -- that's what map.nx is for. Bitset is
12// for dense bit-vectors where the universe is bounded and small.
13//
14// Operations:
15// bitset_new(n) allocate n-bit bitset (all zeros)
16// bitset_set(bs, i) set bit i
17// bitset_clear(bs, i) clear bit i
18// bitset_get(bs, i) read bit i (0 or 1)
19// bitset_count(bs) popcount over all bits
20// bitset_union(dst, src) dst |= src, same capacity
21// bitset_intersect(dst, src) dst &= src
22// bitset_equal(a, b) byte-exact compare
23//
24// Invariants:
25// BS1 bitset_new zeros the backing store -- no uninit reads.
26// BS2 get/set do NOT bounds-check (hot path); caller ensures
27// i < capacity. Debug wrapper could add that.
28// BS3 All *_in-place ops require both bitsets to share the
29// same capacity (word count).
30
31import "syscalls.nx"
32
33struct Bitset {
34 bits: *i64, // packed storage
35 cap: i64, // capacity in bits
36 words: i64, // ceil(cap / 64)
37}
38
39// Allocate an n-bit bitset initialised to all zeros.
40func bitset_new(n: i64) -> *Bitset {
41 let bs_raw: *u8 = sys_mmap(32)
42 let bs: *Bitset = bs_raw as *Bitset
43 let words: i64 = (n + 63) / 64
44 bs.bits = sys_mmap(words * 8 + 16) as *i64
45 bs.cap = n
46 bs.words = words
47 var i: i64 = 0
48 while i < words {
49 bs.bits[i] = 0
50 i = i + 1
51 }
52 return bs
53}
54
55// Set bit i to 1.
56func bitset_set(bs: *Bitset, i: i64) -> i64 {
57 let w: i64 = i / 64
58 let b: i64 = i % 64
59 bs.bits[w] = bs.bits[w] | (1 << b)
60 return 0
61}
62
63// Clear bit i.
64func bitset_clear(bs: *Bitset, i: i64) -> i64 {
65 let w: i64 = i / 64
66 let b: i64 = i % 64
67 let mask: i64 = 1 << b
68 bs.bits[w] = bs.bits[w] & (mask ^ (0 - 1)) // ~mask
69 return 0
70}
71
72// Read bit i (0 or 1).
73func bitset_get(bs: *Bitset, i: i64) -> i64 {
74 let w: i64 = i / 64
75 let b: i64 = i % 64
76 return (bs.bits[w] >> b) & 1
77}
78
79// Hamming weight of a single 64-bit word (Kernighan loop;
80// keeps code small, branchless popcount is a future win).
81func bitset_popcount_word(x: i64) -> i64 {
82 var v: i64 = x
83 var c: i64 = 0
84 while v != 0 {
85 v = v & (v - 1)
86 c = c + 1
87 }
88 return c
89}
90
91// Count set bits across the whole bitset.
92func bitset_count(bs: *Bitset) -> i64 {
93 var total: i64 = 0
94 var w: i64 = 0
95 while w < bs.words {
96 total = total + bitset_popcount_word(bs.bits[w])
97 w = w + 1
98 }
99 return total
100}
101
102// In-place union: dst |= src. Requires dst.words == src.words.
103func bitset_union(dst: *Bitset, src: *Bitset) -> i64 {
104 if dst.words != src.words { return -1 }
105 var w: i64 = 0
106 while w < dst.words {
107 dst.bits[w] = dst.bits[w] | src.bits[w]
108 w = w + 1
109 }
110 return 0
111}
112
113// In-place intersection: dst &= src.
114func bitset_intersect(dst: *Bitset, src: *Bitset) -> i64 {
115 if dst.words != src.words { return -1 }
116 var w: i64 = 0
117 while w < dst.words {
118 dst.bits[w] = dst.bits[w] & src.bits[w]
119 w = w + 1
120 }
121 return 0
122}
123
124// Byte-exact equality. Returns 1 if equal, 0 otherwise.
125func bitset_equal(a: *Bitset, b: *Bitset) -> i64 {
126 if a.cap != b.cap { return 0 }
127 var w: i64 = 0
128 while w < a.words {
129 if a.bits[w] != b.bits[w] { return 0 }
130 w = w + 1
131 }
132 return 1
133}
134
135// Clear every bit.
136func bitset_zero(bs: *Bitset) -> i64 {
137 var w: i64 = 0
138 while w < bs.words {
139 bs.bits[w] = 0
140 w = w + 1
141 }
142 return 0
143}
144
145// Compile-only smoke.
146func main() -> i64 {
147 let bs: *Bitset = bitset_new(200)
148 if bs.cap != 200 { return 1 }
149 if bs.words != 4 { return 2 } // ceil(200/64) = 4
150
151 bitset_set(bs, 0)
152 bitset_set(bs, 63)
153 bitset_set(bs, 64)
154 bitset_set(bs, 199)
155
156 if bitset_get(bs, 0) != 1 { return 3 }
157 if bitset_get(bs, 1) != 0 { return 4 }
158 if bitset_get(bs, 63) != 1 { return 5 }
159 if bitset_get(bs, 64) != 1 { return 6 }
160 if bitset_get(bs, 199) != 1 { return 7 }
161 if bitset_count(bs) != 4 { return 8 }
162
163 bitset_clear(bs, 63)
164 if bitset_get(bs, 63) != 0 { return 9 }
165 if bitset_count(bs) != 3 { return 10 }
166
167 // Union / intersect.
168 let b2: *Bitset = bitset_new(200)
169 bitset_set(b2, 0)
170 bitset_set(b2, 100)
171
172 let b_union_raw: *Bitset = bitset_new(200)
173 bitset_union(b_union_raw, bs)
174 bitset_union(b_union_raw, b2)
175 // Bits set: 0, 64, 100, 199 -> 4.
176 if bitset_count(b_union_raw) != 4 { return 11 }
177
178 // Intersect bs with b2: both have bit 0.
179 let inter: *Bitset = bitset_new(200)
180 bitset_union(inter, bs)
181 bitset_intersect(inter, b2)
182 if bitset_count(inter) != 1 { return 12 }
183 if bitset_get(inter, 0) != 1 { return 13 }
184 return 0
185}