le_bitset/
lib.rs

1//! A very simple bitset that is guaranteed to be stored
2//! in little-endian. If you can't think of a reason you
3//! need this, this crate probably isn't for you. Usage
4//! is pretty self-explanatory.
5
6#[cfg(feature = "serde")]
7use serde_derive::{Deserialize, Serialize};
8
9#[cfg(test)]
10mod test;
11
12const U32_BITS: usize = std::mem::size_of::<u32>() * 8;
13
14/// A little-endian bitset
15#[derive(Debug, Clone)]
16#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
17pub struct BitSet {
18    chunks: Vec<u32>,
19    num_bits: usize,
20}
21
22impl BitSet {
23    /// Calculates the number of chunks to store bits with
24    ///
25    /// # Arguments
26    ///
27    /// `num_bits`: The number of bits
28    #[inline]
29    fn calc_chunks(num_bits: usize) -> usize {
30        (num_bits + U32_BITS - 1) / U32_BITS
31    }
32
33    /// Calculates the mask of the last chunk's bits
34    ///
35    /// # Arguments
36    ///
37    /// `num_bits`: The number of bits
38    #[inline]
39    fn last_mask(num_bits: usize) -> u32 {
40        !(!1 << ((num_bits - 1) % U32_BITS))
41    }
42
43    /// Returns the chunks from the bitset
44    pub fn chunks(&self) -> &Vec<u32> {
45        &self.chunks
46    }
47
48    /// Creates a bitset from the chunks
49    ///
50    /// # Arguments
51    ///
52    /// `chunks`: The raw little-endian bit chunks
53    ///
54    /// `num_bits`: The number of bits
55    pub fn from_bits(chunks: Vec<u32>, num_bits: usize) -> Self {
56        #[cfg(debug_assertions)]
57        assert!(num_bits > 0);
58        #[cfg(debug_assertions)]
59        assert_eq!(Self::calc_chunks(num_bits), chunks.len());
60        #[cfg(debug_assertions)]
61        assert_eq!(chunks[chunks.len() - 1] & !Self::last_mask(num_bits), 0);
62        Self { chunks, num_bits }
63    }
64
65    /// Unsets a bit at the index
66    ///
67    /// # Arguments
68    ///
69    /// `idx`: The index
70    pub fn reset(&mut self, idx: usize) {
71        #[cfg(debug_assertions)]
72        assert!(idx / U32_BITS < self.chunks.len());
73        #[cfg(debug_assertions)]
74        assert!(idx < self.num_bits);
75        let chunk = &mut self.chunks[idx / U32_BITS];
76        let chunk_pos = idx % U32_BITS;
77        *chunk = (*chunk & !(1 << chunk_pos)).to_le();
78    }
79
80    /// Resets all bits to 0
81    pub fn reset_all(&mut self) {
82        for chunk in &mut self.chunks {
83            *chunk = 0;
84        }
85    }
86
87    /// Sets a bit at the index
88    ///
89    /// # Arguments
90    ///
91    /// `idx`: The index
92    pub fn set(&mut self, idx: usize) {
93        #[cfg(debug_assertions)]
94        assert!(idx / U32_BITS < self.chunks.len());
95        #[cfg(debug_assertions)]
96        assert!(idx < self.num_bits);
97        let chunk = &mut self.chunks[idx / U32_BITS];
98        let chunk_pos = idx % U32_BITS;
99        *chunk = (*chunk | 1 << chunk_pos).to_le();
100    }
101
102    /// Sets all bits to 1
103    pub fn set_all(&mut self) {
104        for chunk in &mut self.chunks {
105            *chunk = u32::MAX;
106        }
107        let num_chunks = self.chunks.len();
108        self.chunks[num_chunks - 1] = Self::last_mask(self.num_bits);
109    }
110
111    /// Tests the bit at the index
112    ///
113    /// # Arguments
114    ///
115    /// `idx`: The index
116    pub fn test(&self, idx: usize) -> bool {
117        #[cfg(debug_assertions)]
118        assert!(idx / U32_BITS < self.chunks.len());
119        #[cfg(debug_assertions)]
120        assert!(idx < self.num_bits);
121        let chunk = self.chunks[idx / U32_BITS].to_le();
122        let chunk_pos = idx % U32_BITS;
123        ((chunk >> chunk_pos) & 1) == 1
124    }
125
126    /// Creates an empty bitset with a capacity
127    ///
128    /// # Arguments
129    ///
130    /// `num_bits`: The number of bits to store
131    pub fn with_capacity(num_bits: usize) -> Self {
132        #[cfg(debug_assertions)]
133        assert!(num_bits > 0);
134        let num_chunks = Self::calc_chunks(num_bits);
135        let chunks = vec![0; num_chunks];
136        Self { chunks, num_bits }
137    }
138}
139
140impl From<BitSet> for Vec<u32> {
141    fn from(bitset: BitSet) -> Self {
142        bitset.chunks
143    }
144}
le_bitset/lib.rs

le_bitset/
lib.rs
