primal_bit/
inner.rs

1//! Internals that unsafely rely on consistency between `BitVec` fields,
2//! encapsulated in a module to reduce scope.
3#![allow(unsafe_code)]
4
5use crate::BITS;
6
7/// The bitvector type.
8pub struct BitVec {
9    /// Internal representation of the bit vector
10    storage: Vec<u8>,
11    /// The number of valid bits in the internal representation
12    nbits: usize,
13}
14
15impl BitVec {
16    /// Creates an empty `BitVec`.
17    ///
18    /// # Examples
19    ///
20    /// ```ignore
21    /// use std::collections::BitVec;
22    /// let mut bv = BitVec::new();
23    /// ```
24    #[inline]
25    pub fn new() -> BitVec {
26        BitVec {
27            storage: Vec::new(),
28            nbits: 0,
29        }
30    }
31
32    /// Creates a `BitVec` from the given bytes.
33    #[inline]
34    pub fn from_bytes(data: Vec<u8>, nbits: usize) -> BitVec {
35        let nbytes = nbits / BITS + usize::from(nbits % BITS != 0);
36        assert_eq!(nbytes, data.len());
37        let mut ret = BitVec {
38            storage: data,
39            nbits,
40        };
41        ret.fix_last_block();
42        ret
43    }
44
45    /// Creates a `BitVec` that holds `nbits` elements, setting each element
46    /// to `bit`.
47    ///
48    /// # Examples
49    ///
50    /// ```ignore
51    /// use std::collections::BitVec;
52    ///
53    /// let mut bv = BitVec::from_elem(10, false);
54    /// assert_eq!(bv.len(), 10);
55    /// for x in bv.iter() {
56    ///     assert_eq!(x, false);
57    /// }
58    /// ```
59    pub fn from_elem(nbits: usize, bit: bool) -> BitVec {
60        let nbytes = nbits / BITS + usize::from(nbits % BITS != 0);
61        let out_vec = vec![if bit { !0 } else { 0 }; nbytes];
62
63        let mut bit_vec = BitVec {
64            storage: out_vec,
65            nbits,
66        };
67
68        if bit {
69            bit_vec.fix_last_block();
70        }
71        bit_vec
72    }
73
74    /// An operation might screw up the unused bits in the last block of the
75    /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up.
76    pub(crate) fn fix_last_block(&mut self) {
77        let extra_bits = self.nbits % BITS;
78        if extra_bits > 0 {
79            let mask = (1 << extra_bits) - 1;
80            let last = self.storage.last_mut().unwrap();
81            *last &= mask;
82        }
83    }
84
85    #[inline]
86    pub fn as_bytes_mut(&mut self) -> &mut [u8] {
87        &mut self.storage
88    }
89
90    #[inline]
91    pub fn as_bytes(&self) -> &[u8] {
92        &self.storage
93    }
94
95    #[inline]
96    pub(crate) fn into_bytes(self) -> Vec<u8> {
97        self.storage
98    }
99
100    /// Returns the total number of bits in this vector
101    #[inline]
102    pub fn len(&self) -> usize {
103        self.nbits
104    }
105
106    /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
107    ///
108    /// # Examples
109    ///
110    /// ```ignore
111    /// use std::collections::BitVec;
112    ///
113    /// let bv = BitVec::from_bytes(&[0b01100000]);
114    /// assert_eq!(bv.get(0), Some(false));
115    /// assert_eq!(bv.get(1), Some(true));
116    /// assert_eq!(bv.get(100), None);
117    ///
118    /// // Can also use array indexing
119    /// assert_eq!(bv[1], true);
120    /// ```
121    #[inline]
122    pub fn get(&self, i: usize) -> Option<bool> {
123        if i >= self.nbits {
124            return None;
125        }
126        let w = i / BITS;
127        let b = i % BITS;
128        let mask = 1 << b;
129        unsafe {
130            let block = *self.storage.get_unchecked(w);
131            Some(block & mask != 0)
132        }
133    }
134
135    /// Sets the value of a bit at an index `i`.
136    ///
137    /// # Panics
138    ///
139    /// Panics if `i` is out of bounds.
140    ///
141    /// # Examples
142    ///
143    /// ```ignore
144    /// use std::collections::BitVec;
145    ///
146    /// let mut bv = BitVec::from_elem(5, false);
147    /// bv.set(3, true);
148    /// assert_eq!(bv[3], true);
149    /// ```
150    #[inline]
151    pub fn set(&mut self, i: usize, x: bool) {
152        assert!(i < self.nbits, "index out of bounds");
153        let w = i / BITS;
154        let b = i % BITS;
155        let mask = 1 << b;
156        let bit = u8::from(x) << b;
157        unsafe {
158            let ptr = self.storage.get_unchecked_mut(w);
159            *ptr = (*ptr & !mask) | bit;
160        }
161    }
162}
163
164impl Clone for BitVec {
165    #[inline]
166    fn clone(&self) -> BitVec {
167        BitVec {
168            storage: self.storage.clone(),
169            nbits: self.nbits,
170        }
171    }
172
173    #[inline]
174    fn clone_from(&mut self, source: &BitVec) {
175        self.nbits = 0; // safe default while storage is modified
176        self.storage.clone_from(&source.storage);
177        self.nbits = source.nbits;
178    }
179}
primal_bit/inner.rs

primal_bit/
inner.rs
