device_driver_common/
bitset.rs

1#[derive(Debug, Clone, Default, PartialEq, Eq)]
2pub struct BitSet {
3    words: Vec<usize>,
4    len: usize,
5}
6
7impl BitSet {
8    pub const fn new() -> Self {
9        Self {
10            words: Vec::new(),
11            len: 0,
12        }
13    }
14
15    pub fn push(&mut self, value: bool) {
16        let (next_word, next_bit) = Self::index_to_word_index(self.len);
17
18        let word = if next_word == self.words.len() {
19            self.words.push_mut(0)
20        } else {
21            &mut self.words[next_word]
22        };
23
24        *word |= (value as usize) << next_bit;
25
26        self.len += 1;
27    }
28
29    pub fn get(&self, index: usize) -> Option<bool> {
30        if index >= self.len {
31            return None;
32        }
33
34        let (word, bit) = Self::index_to_word_index(index);
35
36        Some((self.words[word] & (1 << bit)) > 0)
37    }
38
39    #[track_caller]
40    pub fn set(&mut self, index: usize, value: bool) {
41        if index >= self.len {
42            panic!(
43                "index out of range, tried to get element {index} from a set with len {}",
44                self.len
45            );
46        }
47
48        let (word, bit) = Self::index_to_word_index(index);
49
50        if value {
51            self.words[word] |= 1 << bit;
52        } else {
53            self.words[word] &= !(1 << bit);
54        }
55    }
56
57    pub fn len(&self) -> usize {
58        self.len
59    }
60
61    pub fn is_empty(&self) -> bool {
62        self.len == 0
63    }
64
65    fn index_to_word_index(index: usize) -> (usize, usize) {
66        let word = index / usize::BITS as usize;
67        let bits = index % usize::BITS as usize;
68        (word, bits)
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn bitset() {
78        let mut set = BitSet::new();
79        set.push(true);
80        set.push(false);
81        set.push(true);
82        set.push(false);
83
84        assert_eq!(set.len(), 4);
85
86        assert_eq!(set.get(0), Some(true));
87        assert_eq!(set.get(1), Some(false));
88        assert_eq!(set.get(2), Some(true));
89        assert_eq!(set.get(3), Some(false));
90        assert_eq!(set.get(4), None);
91    }
92
93    #[test]
94    fn bitset_long() {
95        const SIZE: usize = 1000;
96
97        let mut set = BitSet::new();
98
99        for i in 0..SIZE {
100            set.push(i.is_power_of_two());
101        }
102
103        for i in 0..SIZE {
104            assert_eq!(set.get(i), Some(i.is_power_of_two()));
105        }
106
107        for i in 0..SIZE {
108            set.set(i, !i.is_power_of_two());
109        }
110
111        for i in 0..SIZE {
112            assert_eq!(set.get(i), Some(!i.is_power_of_two()));
113        }
114
115        assert_eq!(set.get(SIZE), None);
116    }
117
118    #[test]
119    #[should_panic = "index out of range, tried to get element 1 from a set with len 1"]
120    fn bitset_set_panics() {
121        let mut set = BitSet::new();
122        set.push(true);
123
124        set.set(1, false);
125    }
126}
device_driver_common/bitset.rs

device_driver_common/
bitset.rs
