sans_io_runtime/collections/
bit_vec.rs

1//! A bit vector implementation. which is used inside task switcher
2
3#[derive(Debug)]
4pub struct BitVec {
5    bytes: Vec<u8>,
6    len: usize,
7}
8
9impl BitVec {
10    pub fn news(len: usize) -> Self {
11        Self {
12            bytes: vec![0; len / 8 + 1].to_vec(),
13            len,
14        }
15    }
16
17    pub fn set_len(&mut self, len: usize) {
18        if len > self.bytes.len() * 8 {
19            self.bytes.resize(len / 8 + 1, 0);
20        }
21        self.len = len;
22    }
23
24    pub fn len(&self) -> usize {
25        self.len
26    }
27
28    pub fn is_empty(&self) -> bool {
29        self.len == 0
30    }
31
32    pub fn get_bit(&self, index: usize) -> bool {
33        assert!(
34            self.len > index,
35            "index out of bounds {index} vs bytes {}",
36            self.bytes.len()
37        );
38        let byte_index = index / 8;
39        let bit_index = index % 8;
40        self.bytes[byte_index] & (1 << bit_index) != 0
41    }
42
43    pub fn set_bit(&mut self, index: usize, value: bool) {
44        assert!(
45            self.len > index,
46            "index out of bounds {index} vs bytes {}",
47            self.bytes.len()
48        );
49        let byte_index = index / 8;
50        let bit_index = index % 8;
51        if value {
52            self.bytes[byte_index] |= 1 << bit_index;
53        } else {
54            self.bytes[byte_index] &= !(1 << bit_index);
55        }
56    }
57
58    // TODO: optimize this
59    pub fn first_set_index(&self) -> Option<usize> {
60        for (byte_index, &byte) in self.bytes.iter().enumerate() {
61            if byte != 0 {
62                for bit_index in 0..8 {
63                    let index = byte_index * 8 + bit_index;
64                    if index >= self.len {
65                        return None;
66                    }
67                    if byte & (1 << bit_index) != 0 {
68                        return Some(index);
69                    }
70                }
71            }
72        }
73        None
74    }
75
76    pub fn set_all(&mut self, value: bool) {
77        self.bytes.fill(if value { 0xff } else { 0 });
78    }
79}
80
81#[cfg(test)]
82mod test {
83    #[test]
84    fn simple_work() {
85        let mut bit_vec = super::BitVec::news(8);
86        assert_eq!(bit_vec.first_set_index(), None);
87        bit_vec.set_bit(0, true);
88        assert_eq!(bit_vec.first_set_index(), Some(0));
89        bit_vec.set_bit(0, false);
90        assert_eq!(bit_vec.first_set_index(), None);
91        bit_vec.set_bit(7, true);
92        assert_eq!(bit_vec.get_bit(7), true);
93        assert_eq!(bit_vec.first_set_index(), Some(7));
94        bit_vec.set_bit(7, false);
95        assert_eq!(bit_vec.first_set_index(), None);
96        bit_vec.set_bit(0, true);
97        bit_vec.set_bit(7, true);
98        assert_eq!(bit_vec.first_set_index(), Some(0));
99        bit_vec.set_all(true);
100        assert_eq!(bit_vec.first_set_index(), Some(0));
101        bit_vec.set_all(false);
102        assert_eq!(bit_vec.first_set_index(), None);
103    }
104
105    #[test]
106    fn extend_bytes() {
107        let mut bit_vec = super::BitVec::news(0);
108        bit_vec.set_len(9); //to new byte
109        assert_eq!(bit_vec.get_bit(8), false);
110        bit_vec.set_bit(8, true);
111        assert_eq!(bit_vec.get_bit(8), true);
112    }
113}
sans_io_runtime/collections/bit_vec.rs

sans_io_runtime/collections/
bit_vec.rs
