quill_sql/utils/
bitmap.rs

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

quill_sql/utils/
bitmap.rs
