libpetri_runtime/
bitmap.rs

1/// Number of bits per word.
2pub const WORD_BITS: usize = 64;
3/// Shift amount to convert bit index to word index.
4pub const WORD_SHIFT: usize = 6;
5/// Mask to extract bit position within a word.
6pub const WORD_MASK: usize = 63;
7
8/// Returns the number of u64 words needed to represent `n` bits.
9#[inline]
10pub fn word_count(n: usize) -> usize {
11    (n + WORD_BITS - 1) >> WORD_SHIFT
12}
13
14/// Sets bit `i` in the bitmap.
15#[inline]
16pub fn set_bit(words: &mut [u64], i: usize) {
17    words[i >> WORD_SHIFT] |= 1u64 << (i & WORD_MASK);
18}
19
20/// Clears bit `i` in the bitmap.
21#[inline]
22pub fn clear_bit(words: &mut [u64], i: usize) {
23    words[i >> WORD_SHIFT] &= !(1u64 << (i & WORD_MASK));
24}
25
26/// Tests if bit `i` is set.
27#[inline]
28pub fn test_bit(words: &[u64], i: usize) -> bool {
29    (words[i >> WORD_SHIFT] & (1u64 << (i & WORD_MASK))) != 0
30}
31
32/// Returns true if all bits set in `mask` are also set in `snapshot`.
33/// Equivalent to: (snapshot & mask) == mask
34#[inline]
35pub fn contains_all(snapshot: &[u64], mask: &[u64]) -> bool {
36    debug_assert_eq!(snapshot.len(), mask.len());
37    match mask.len() {
38        0 => true,
39        1 => (snapshot[0] & mask[0]) == mask[0],
40        _ => scalar_contains_all(snapshot, mask),
41    }
42}
43
44#[inline]
45fn scalar_contains_all(snapshot: &[u64], mask: &[u64]) -> bool {
46    for i in 0..mask.len() {
47        if (snapshot[i] & mask[i]) != mask[i] {
48            return false;
49        }
50    }
51    true
52}
53
54/// Returns true if any bit set in `mask` is also set in `snapshot`.
55/// Equivalent to: (snapshot & mask) != 0
56#[inline]
57pub fn intersects(snapshot: &[u64], mask: &[u64]) -> bool {
58    debug_assert_eq!(snapshot.len(), mask.len());
59    match mask.len() {
60        0 => false,
61        1 => (snapshot[0] & mask[0]) != 0,
62        _ => scalar_intersects(snapshot, mask),
63    }
64}
65
66#[inline]
67fn scalar_intersects(snapshot: &[u64], mask: &[u64]) -> bool {
68    for i in 0..mask.len() {
69        if (snapshot[i] & mask[i]) != 0 {
70            return true;
71        }
72    }
73    false
74}
75
76/// Iterates over all set bits in the bitmap, calling `f` for each bit index.
77/// Uses Kernighan's trick with trailing zero count for efficient iteration.
78#[inline]
79pub fn for_each_set_bit(words: &[u64], mut f: impl FnMut(usize)) {
80    for (word_idx, &word) in words.iter().enumerate() {
81        let base = word_idx << WORD_SHIFT;
82        let mut w = word;
83        while w != 0 {
84            let tz = w.trailing_zeros() as usize;
85            f(base + tz);
86            w &= w - 1; // clear lowest set bit
87        }
88    }
89}
90
91/// Copies `src` bitmap OR'd into `dst`.
92#[inline]
93pub fn or_into(dst: &mut [u64], src: &[u64]) {
94    debug_assert_eq!(dst.len(), src.len());
95    for i in 0..dst.len() {
96        dst[i] |= src[i];
97    }
98}
99
100/// Returns true if all bits are zero.
101#[inline]
102pub fn is_empty(words: &[u64]) -> bool {
103    words.iter().all(|&w| w == 0)
104}
105
106/// Clears all bits.
107#[inline]
108pub fn clear_all(words: &mut [u64]) {
109    for w in words.iter_mut() {
110        *w = 0;
111    }
112}
113
114/// Swaps contents of two bitmaps of the same length.
115#[inline]
116pub fn swap(a: &mut [u64], b: &mut [u64]) {
117    debug_assert_eq!(a.len(), b.len());
118    for i in 0..a.len() {
119        std::mem::swap(&mut a[i], &mut b[i]);
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn word_count_values() {
129        assert_eq!(word_count(0), 0);
130        assert_eq!(word_count(1), 1);
131        assert_eq!(word_count(64), 1);
132        assert_eq!(word_count(65), 2);
133        assert_eq!(word_count(128), 2);
134        assert_eq!(word_count(129), 3);
135    }
136
137    #[test]
138    fn set_clear_test_bit() {
139        let mut bm = vec![0u64; 2];
140        set_bit(&mut bm, 0);
141        assert!(test_bit(&bm, 0));
142        assert!(!test_bit(&bm, 1));
143
144        set_bit(&mut bm, 65);
145        assert!(test_bit(&bm, 65));
146
147        clear_bit(&mut bm, 0);
148        assert!(!test_bit(&bm, 0));
149        assert!(test_bit(&bm, 65));
150    }
151
152    #[test]
153    fn contains_all_works() {
154        let snapshot = vec![0b1111u64];
155        let mask = vec![0b0101u64];
156        assert!(contains_all(&snapshot, &mask));
157
158        let mask2 = vec![0b10000u64];
159        assert!(!contains_all(&snapshot, &mask2));
160    }
161
162    #[test]
163    fn contains_all_empty() {
164        let empty: Vec<u64> = vec![];
165        assert!(contains_all(&empty, &empty));
166    }
167
168    #[test]
169    fn intersects_works() {
170        let snapshot = vec![0b1010u64];
171        let mask = vec![0b0010u64];
172        assert!(intersects(&snapshot, &mask));
173
174        let mask2 = vec![0b0101u64];
175        assert!(!intersects(&snapshot, &mask2));
176    }
177
178    #[test]
179    fn for_each_set_bit_works() {
180        let bm = vec![0b1010_0101u64, 0u64];
181        let mut bits = Vec::new();
182        for_each_set_bit(&bm, |i| bits.push(i));
183        assert_eq!(bits, vec![0, 2, 5, 7]);
184    }
185
186    #[test]
187    fn for_each_set_bit_multi_word() {
188        let mut bm = vec![0u64; 2];
189        set_bit(&mut bm, 0);
190        set_bit(&mut bm, 63);
191        set_bit(&mut bm, 64);
192        set_bit(&mut bm, 127);
193        let mut bits = Vec::new();
194        for_each_set_bit(&bm, |i| bits.push(i));
195        assert_eq!(bits, vec![0, 63, 64, 127]);
196    }
197
198    #[test]
199    fn or_into_works() {
200        let mut dst = vec![0b1010u64];
201        let src = vec![0b0101u64];
202        or_into(&mut dst, &src);
203        assert_eq!(dst[0], 0b1111);
204    }
205
206    #[test]
207    fn is_empty_works() {
208        assert!(is_empty(&[0u64, 0u64]));
209        assert!(!is_empty(&[0u64, 1u64]));
210    }
211}
libpetri_runtime/bitmap.rs

libpetri_runtime/
bitmap.rs
