bloom2/bitmap/
vec.rs

1use crate::Bitmap;
2
3use super::{bitmask_for_key, index_for_key};
4
5/// A plain, heap-allocated, `O(1)` indexed bitmap.
6///
7/// This bitmap requires `O(n)` space and can be read and wrote to in `O(1)`
8/// time.
9///
10/// This type is fast for both read and writes, but trades additional space for
11/// the additional performance.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct VecBitmap {
14    bitmap: Vec<usize>,
15    max_key: usize,
16}
17
18impl VecBitmap {
19    pub(crate) fn into_parts(self) -> (Vec<usize>, usize) {
20        (self.bitmap, self.max_key)
21    }
22}
23
24impl Bitmap for VecBitmap {
25    fn set(&mut self, key: usize, value: bool) {
26        let offset = index_for_key(key);
27
28        if value {
29            self.bitmap[offset] |= bitmask_for_key(key);
30        } else {
31            self.bitmap[offset] &= !bitmask_for_key(key);
32        }
33    }
34
35    fn get(&self, key: usize) -> bool {
36        let offset = index_for_key(key);
37
38        self.bitmap[offset] & bitmask_for_key(key) != 0
39    }
40
41    fn byte_size(&self) -> usize {
42        self.bitmap.len() * std::mem::size_of::<usize>()
43    }
44
45    fn or(&self, other: &Self) -> Self {
46        // Invariant: the block maps are of equal length, meaning the zipped
47        // iters yield both sides to completion.
48        assert_eq!(self.bitmap.len(), other.bitmap.len());
49
50        let bitmap = self
51            .bitmap
52            .iter()
53            .zip(&other.bitmap)
54            .map(|(a, b)| a | b)
55            .collect();
56
57        Self {
58            bitmap,
59            max_key: self.max_key,
60        }
61    }
62
63    fn new_with_capacity(max_key: usize) -> Self {
64        let bitmap = vec![0; index_for_key(max_key) + 1];
65        Self { bitmap, max_key }
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use proptest::prelude::*;
72
73    use super::*;
74
75    const MAX_KEY: usize = 1028;
76
77    proptest! {
78        #[test]
79        fn prop_insert_contains(
80            values in prop::collection::hash_set(0..MAX_KEY, 0..20),
81        ) {
82            let mut b = VecBitmap::new_with_capacity(MAX_KEY);
83
84            for v in &values {
85                b.set(*v, true);
86            }
87
88            // Ensure all values are equal in the test range.
89            for i in 0..MAX_KEY {
90                assert_eq!(b.get(i), values.contains(&i));
91            }
92        }
93
94        #[test]
95        fn prop_or(
96            a in prop::collection::vec(0..MAX_KEY, 0..20),
97            b in prop::collection::vec(0..MAX_KEY, 0..20),
98        ) {
99            let mut a_bitmap = VecBitmap::new_with_capacity(MAX_KEY);
100            let mut b_bitmap = VecBitmap::new_with_capacity(MAX_KEY);
101            let mut combined_bitmap = VecBitmap::new_with_capacity(MAX_KEY);
102
103            for v in a.iter() {
104                a_bitmap.set(*v, true);
105                combined_bitmap.set(*v, true);
106            }
107
108            for v in b.iter() {
109                b_bitmap.set(*v, true);
110                combined_bitmap.set(*v, true);
111            }
112
113            let union = a_bitmap.or(&b_bitmap);
114
115            // Invariant: the union and the combined construction must be equal.
116            assert_eq!(union, combined_bitmap);
117
118            // Invariant: the key space contains true entries only when the
119            // value appears in a or b.
120            for i in 0..MAX_KEY {
121                assert_eq!(union.get(i), a_bitmap.get(i) || b_bitmap.get(i));
122
123                // Invariant: the key presence matches the combined bitmap.
124                assert_eq!(union.get(i), combined_bitmap.get(i));
125            }
126        }
127    }
128}
bloom2/bitmap/vec.rs

bloom2/bitmap/
vec.rs
