containers.tngl.sh
A Vec of Bits
blackson.tngl.sh
1# stackoverflow question
2
3Rust: Mark the method as unsafe, or just add "unsafe" to its name? Dilemma with library API design.
4
5Hi. I am maintaining a dynamic array of bits just like C++'s `vector<bool>`.
6
7The thing in question, is the method for getting access to the underlying `Vec<u32>`, which may let the caller mess up the dynamic array. It's not inherently memory-unsafe, but currently marked as such. My idea is to change this unsafe fn to be marked as safe, while adding a prefix `unsafe_` to its name.
8
9# code review request
10
11maintainer of `bit-vec` here. It's a Rust library for lists of booleans.
12
13The library is used by a couple thousand people, so I'd appreciate thorough review. You have a compact dynamic arrays of bits like `vector<bool>` in C++ and fill all elements with the given value, or remove one of the elements at the given index. This is basically it. But I had to deprecate `fn clear` by renaming it to `fn fill` because the name was inconsistent with other collections having `clear` truncate the list to zero elements: https://github.com/contain-rs/bit-vec/issues/16
14
15You may see the code here: https://github.com/contain-rs/bit-vec/pull/134/changes https://github.com/contain-rs/bit-vec/pull/135/changes All of it except the tests is included below.
16
17```rust
18 /// Assigns all bits in this vector to the given boolean value.
19 ///
20 /// # Invariants
21 ///
22 /// - After a call to `.fill(true)`, the result of [`all`] is `true`.
23 /// - After a call to `.fill(false)`, the result of [`none`] is `true`.
24 ///
25 /// [`all`]: Self::all
26 /// [`none`]: Self::none
27 #[inline]
28 pub fn fill(&mut self, bit: bool) {
29 self.ensure_invariant();
30 let block = if bit { !B::zero() } else { B::zero() };
31 for w in &mut self.storage {
32 *w = block;
33 }
34 if bit {
35 self.fix_last_block();
36 }
37 }
38
39 /// Clears all bits in this vector.
40 #[inline]
41 #[deprecated(since = "0.9.0", note = "please use `.fill(false)` instead")]
42 pub fn clear(&mut self) {
43 self.ensure_invariant();
44 for w in &mut self.storage {
45 *w = B::zero();
46 }
47 }
48
49 /// Remove a bit at index `at`, shifting all bits after by one.
50 ///
51 /// # Panics
52 /// Panics if `at` is out of bounds for `BitVec`'s length (that is, if `at >= BitVec::len()`)
53 ///
54 /// # Examples
55 ///```
56 /// use bit_vec::BitVec;
57 ///
58 /// let mut b = BitVec::new();
59 ///
60 /// b.push(true);
61 /// b.push(false);
62 /// b.push(false);
63 /// b.push(true);
64 /// assert!(!b.remove(1));
65 ///
66 /// assert!(b.eq_vec(&[true, false, true]));
67 ///```
68 ///
69 /// # Time complexity
70 /// Takes O([`len`]) time. All items after the removal index must be
71 /// shifted to the left. In the worst case, all elements are shifted when
72 /// the removal index is 0.
73 ///
74 /// [`len`]: Self::len
75 pub fn remove(&mut self, at: usize) -> bool {
76 assert!(
77 at < self.nbits,
78 "removal index (is {at}) should be < len (is {nbits})",
79 nbits = self.nbits
80 );
81 self.ensure_invariant();
82
83 self.nbits -= 1;
84
85 let last_block_bits = self.nbits % B::bits();
86 let block_at = at / B::bits(); // needed block
87 let bit_at = at % B::bits(); // index within the block
88
89 let lsbits_mask = (B::one() << bit_at) - B::one();
90
91 let mut carry = B::zero();
92
93 for block_ref in self.storage[block_at + 1..].iter_mut().rev() {
94 let curr_carry = *block_ref & B::one();
95 *block_ref = *block_ref >> 1 | (carry << (B::bits() - 1));
96 carry = curr_carry;
97 }
98
99 // Safety: thanks to the assert above.
100 let result = unsafe { self.get_unchecked(at) };
101
102 self.storage[block_at] = (self.storage[block_at] & lsbits_mask)
103 | ((self.storage[block_at] & (!lsbits_mask << 1)) >> 1)
104 | carry << (B::bits() - 1);
105
106 if last_block_bits == 0 {
107 self.storage.pop();
108 }
109
110 result
111 }
112```
113
114```rust
115pub struct BitVec<B = u32> {
116 /// Internal representation of the bit vector
117 storage: Vec<B>,
118 /// The number of valid bits in the internal representation
119 nbits: usize,
120}
121
122/// Abstracts over a pile of bits (basically unsigned primitives)
123pub trait BitBlock:
124 Copy
125 + Add<Self, Output = Self>
126 + Sub<Self, Output = Self>
127 + Shl<usize, Output = Self>
128 + Shr<usize, Output = Self>
129 + Not<Output = Self>
130 + BitAnd<Self, Output = Self>
131 + BitOr<Self, Output = Self>
132 + BitXor<Self, Output = Self>
133 + Rem<Self, Output = Self>
134 + Eq
135 + Ord
136 + hash::Hash
137{
138 /// How many bits it has
139 fn bits() -> usize;
140 /// How many bytes it has
141 #[inline]
142 fn bytes() -> usize {
143 Self::bits() / 8
144 }
145 /// Convert a byte into this type (lowest-order bits set)
146 fn from_byte(byte: u8) -> Self;
147 /// Count the number of 1's in the bitwise repr
148 fn count_ones(self) -> usize;
149 /// Count the number of 0's in the bitwise repr
150 fn count_zeros(self) -> usize {
151 Self::bits() - self.count_ones()
152 }
153 /// Get `0`
154 fn zero() -> Self;
155 /// Get `1`
156 fn one() -> Self;
157}
158
159macro_rules! bit_block_impl {
160 ($(($t: ident, $size: expr)),*) => ($(
161 impl BitBlock for $t {
162 #[inline]
163 fn bits() -> usize { $size }
164 #[inline]
165 fn from_byte(byte: u8) -> Self { $t::from(byte) }
166 #[inline]
167 fn count_ones(self) -> usize { self.count_ones() as usize }
168 #[inline]
169 fn count_zeros(self) -> usize { self.count_zeros() as usize }
170 #[inline]
171 fn one() -> Self { 1 }
172 #[inline]
173 fn zero() -> Self { 0 }
174 }
175 )*)
176}
177
178bit_block_impl! {
179 (u8, 8),
180 (u16, 16),
181 (u32, 32),
182 (u64, 64),
183 (usize, core::mem::size_of::<usize>() * 8)
184}
185```