var_bitmap/
lib.rs

1pub struct Bitmap {
2    size: usize,
3    bits: Vec<u8>,
4}
5
6impl Bitmap {
7    /// Create a new bitmap with initial size of 0
8    pub fn new() -> Self {
9        Self::with_size(0)
10    }
11    
12    /// Create a new bitmap with initial size `size`
13    pub fn with_size(size: usize) -> Self {
14        let mut bits = Vec::new();
15        let bits_size;
16        if size == 0 {
17            bits_size = 0;
18        } else {
19            bits_size = (size - 1) / 8 + 1;
20        }
21        for _ in 0..bits_size {
22            bits.push(0);
23        }
24        
25        Self {
26            size,
27            bits,
28        }
29    }
30    
31    /// Get bitmap size
32    pub fn size(&self) -> usize {
33        self.size
34    }
35    
36    /// Get bit at index `idx`, panic if `idx` out of bound
37    pub fn get(&self, idx: usize) -> bool {
38        if idx >= self.size {
39            panic!("Out of bound error");
40        }
41        let byte_idx = idx >> 3;    // idx / 8
42        let offset = idx & 0b111;   // idx % 8
43        let byte = self.bits[byte_idx];
44        (byte >> (7 - offset)) & 1 == 1
45    }
46    
47    /// Set bit at index `idx`
48    pub fn set(&mut self, idx: usize, value: bool) {
49        if idx >= self.size {
50            panic!("Out of bound error");
51        }
52        let byte_idx = idx >> 3;    // idx / 8
53        let offset = idx & 0b111;   // idx % 8
54        let mut byte = self.bits[byte_idx];
55        
56        let curval = (byte >> (7 - offset)) & 1;
57        let mask;
58        if value {
59            mask = 1 ^ curval;
60        } else {
61            mask = 0 ^ curval;
62        }
63        byte = byte ^ (mask << (7 - offset)); // Bit flipping
64        self.bits[byte_idx] = byte;
65    }
66    
67    /// Push a bit
68    pub fn push(&mut self, value: bool) {
69        if self.size & 0b111 == 0 { // size % 8 == 0
70            // Add new byte
71            self.bits.push(0);
72        }
73        let idx = self.size;
74        self.size += 1;
75        self.set(idx, value);
76    }
77    
78    #[allow(dead_code)]
79    // For debugging / testing purpose
80    fn dump(&self) -> String {
81        let mut s = vec![];
82        for byte in &self.bits {
83            s.push(format!("{:08b}", byte));
84        }
85        s.join("")[0..self.size].to_string()
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    
93    #[test]
94    fn test_push() {
95        let mut bm = Bitmap::new();
96        bm.push(false);
97        bm.push(true);
98        bm.push(false);
99        assert_eq!(bm.dump(), "010");
100    }
101    
102    #[test]
103    fn test_get_and_set() {
104        let mut bm = Bitmap::with_size(24);
105        bm.set(13, true);
106        assert_eq!(bm.dump(), "000000000000010000000000");
107        bm.set(13, false);
108        assert_eq!(bm.dump(), "000000000000000000000000");
109    }
110}
var_bitmap/lib.rs

var_bitmap/
lib.rs
