quill_sql/utils/
bitmap.rs

1#[derive(Debug, Clone, Eq, PartialEq)]
2pub struct DynamicBitmap {
3    map: Vec<u8>,
4}
5
6impl DynamicBitmap {
7    pub fn new() -> Self {
8        Self { map: Vec::new() }
9    }
10
11    pub fn set(&mut self, index: usize, value: bool) {
12        let byte_idx = index >> 3; // idx / 8
13        if byte_idx >= self.map.len() {
14            self.map.extend(vec![0; byte_idx - self.map.len() + 1])
15        }
16        let offset = index & 0b111; // idx % 8
17        let mut byte = self.map[byte_idx];
18
19        let curval = (byte >> (7 - offset)) & 1;
20        let mask = if value { 1 ^ curval } else { curval };
21        byte ^= mask << (7 - offset); // Bit flipping
22        self.map[byte_idx] = byte;
23    }
24
25    pub fn get(&self, index: usize) -> Option<bool> {
26        if index >= self.map.len() << 8 {
27            return None;
28        }
29        let byte_idx = index >> 3; // idx / 8
30        let offset = index & 0b111; // idx % 8
31        let byte = self.map[byte_idx];
32        Some((byte >> (7 - offset)) & 1 == 1)
33    }
34
35    pub fn to_bytes(&self) -> Vec<u8> {
36        self.map.clone()
37    }
38
39    pub fn from_bytes(bytes: &[u8]) -> Self {
40        Self {
41            map: bytes.to_vec(),
42        }
43    }
44}
45
46#[cfg(test)]
47mod tests {
48    use crate::utils::bitmap::DynamicBitmap;
49
50    #[test]
51    fn dynamic_bitmap() {
52        let mut bitmap = DynamicBitmap::new();
53        assert_eq!(bitmap.get(0), None);
54
55        bitmap.set(3, true);
56        assert_eq!(bitmap.map.len(), 1);
57
58        bitmap.set(10, true);
59        assert_eq!(bitmap.map.len(), 2);
60
61        assert_eq!(bitmap.get(0), Some(false));
62        assert_eq!(bitmap.get(3), Some(true));
63        assert_eq!(bitmap.get(10), Some(true));
64
65        let new_bitmap = DynamicBitmap::from_bytes(&bitmap.to_bytes());
66        assert_eq!(new_bitmap, bitmap);
67    }
68}
quill_sql/utils/bitmap.rs

quill_sql/utils/
bitmap.rs
