nostd_bv/bit_vec/
impls.rs

1use super::BitVec;
2use crate::iter::BlockIter;
3use crate::storage::Address;
4use crate::{BitSlice, BitSliceMut, BitSliceable, Bits, BitsMut, BitsPush, BlockType};
5
6use crate::traits::get_masked_block;
7
8use crate::range_compat::*;
9
10use alloc::{boxed::Box, vec::Vec};
11use core::cmp::Ordering;
12use core::fmt;
13use core::hash::{Hash, Hasher};
14
15impl<Block: BlockType> Bits for BitVec<Block> {
16    type Block = Block;
17
18    fn bit_len(&self) -> u64 {
19        self.len()
20    }
21
22    fn get_bit(&self, position: u64) -> bool {
23        assert!(position < self.len(), "BitVec::get_bit: out of bounds");
24        let address = Address::new::<Block>(position);
25        // We know this is safe because we just did a bounds check.
26        let block = unsafe { self.bits.get_block(address.block_index) };
27        block.get_bit(address.bit_offset)
28    }
29
30    fn get_block(&self, position: usize) -> Block {
31        get_masked_block(self, position)
32    }
33
34    fn get_raw_block(&self, position: usize) -> Block {
35        assert!(
36            position < self.block_len(),
37            "BitVec::get_block: out of bounds"
38        );
39        // We know this is safe because we just did a bounds check.
40        unsafe { self.bits.get_block(position) }
41    }
42}
43
44impl<Block: BlockType> BitsMut for BitVec<Block> {
45    fn set_bit(&mut self, position: u64, value: bool) {
46        assert!(position < self.len(), "BitVec::set_bit: out of bounds");
47        let address = Address::new::<Block>(position);
48        // We know this is safe because we just did a bounds check.
49        let old_block = unsafe { self.bits.get_block(address.block_index) };
50        let new_block = old_block.with_bit(address.bit_offset, value);
51        unsafe {
52            self.bits.set_block(address.block_index, new_block);
53        }
54    }
55
56    fn set_block(&mut self, position: usize, value: Block) {
57        assert!(
58            position < self.block_len(),
59            "BitVec::set_block: out of bounds"
60        );
61        // We know this is safe because we just did a bounds check, and
62        // position is in bounds. This may set extra bits in the last
63        // block, but that's okay because such bits are never observed.
64        unsafe {
65            self.bits.set_block(position, value);
66        }
67    }
68}
69
70impl<Block: BlockType> BitsPush for BitVec<Block> {
71    fn push_bit(&mut self, value: bool) {
72        self.push(value);
73    }
74
75    fn pop_bit(&mut self) -> Option<bool> {
76        self.pop()
77    }
78
79    fn align_block(&mut self, value: bool) {
80        let keep_bits = Block::mod_nbits(self.len);
81        if keep_bits > 0 {
82            // We know the next line doesn't overflow because if
83            // there are bits to keep then there must be at least
84            // one blck.
85            let last_index = self.block_len() - 1;
86            // Then this is safe because `last_index` is the index
87            // of the last block, which certainly exists at this point.
88            unsafe {
89                let old_last = self.bits.get_block(last_index);
90                let new_last = if value {
91                    old_last | !Block::low_mask(keep_bits)
92                } else {
93                    old_last & Block::low_mask(keep_bits)
94                };
95                self.bits.set_block(last_index, new_last);
96            }
97            self.len += (Block::nbits() - keep_bits) as u64;
98        }
99    }
100
101    fn push_block(&mut self, value: Block) {
102        self.align_block(false);
103        self.block_reserve(1);
104        self.len += Block::nbits() as u64;
105        let last = self.block_len() - 1;
106        self.set_block(last, value);
107    }
108}
109
110impl<'a, Block: BlockType> BitSliceable<Range<u64>> for &'a BitVec<Block> {
111    type Slice = BitSlice<'a, Block>;
112
113    fn bit_slice(self, range: Range<u64>) -> BitSlice<'a, Block> {
114        self.as_slice().bit_slice(range)
115    }
116}
117
118impl<'a, Block: BlockType> BitSliceable<Range<u64>> for &'a mut BitVec<Block> {
119    type Slice = BitSliceMut<'a, Block>;
120
121    fn bit_slice(self, range: Range<u64>) -> BitSliceMut<'a, Block> {
122        self.as_mut_slice().bit_slice(range)
123    }
124}
125
126impl<'a, Block: BlockType> BitSliceable<RangeInclusive<u64>> for &'a BitVec<Block> {
127    type Slice = BitSlice<'a, Block>;
128
129    fn bit_slice(self, range: RangeInclusive<u64>) -> BitSlice<'a, Block> {
130        self.as_slice().bit_slice(range)
131    }
132}
133
134impl<'a, Block: BlockType> BitSliceable<RangeInclusive<u64>> for &'a mut BitVec<Block> {
135    type Slice = BitSliceMut<'a, Block>;
136
137    fn bit_slice(self, range: RangeInclusive<u64>) -> BitSliceMut<'a, Block> {
138        self.as_mut_slice().bit_slice(range)
139    }
140}
141
142impl<'a, Block: BlockType> BitSliceable<RangeFrom<u64>> for &'a BitVec<Block> {
143    type Slice = BitSlice<'a, Block>;
144
145    fn bit_slice(self, range: RangeFrom<u64>) -> BitSlice<'a, Block> {
146        self.as_slice().bit_slice(range)
147    }
148}
149
150impl<'a, Block: BlockType> BitSliceable<RangeFrom<u64>> for &'a mut BitVec<Block> {
151    type Slice = BitSliceMut<'a, Block>;
152
153    fn bit_slice(self, range: RangeFrom<u64>) -> BitSliceMut<'a, Block> {
154        self.as_mut_slice().bit_slice(range)
155    }
156}
157
158impl<'a, Block: BlockType> BitSliceable<RangeTo<u64>> for &'a BitVec<Block> {
159    type Slice = BitSlice<'a, Block>;
160
161    fn bit_slice(self, range: RangeTo<u64>) -> BitSlice<'a, Block> {
162        self.as_slice().bit_slice(range)
163    }
164}
165
166impl<'a, Block: BlockType> BitSliceable<RangeTo<u64>> for &'a mut BitVec<Block> {
167    type Slice = BitSliceMut<'a, Block>;
168
169    fn bit_slice(self, range: RangeTo<u64>) -> BitSliceMut<'a, Block> {
170        self.as_mut_slice().bit_slice(range)
171    }
172}
173
174impl<'a, Block: BlockType> BitSliceable<RangeToInclusive<u64>> for &'a BitVec<Block> {
175    type Slice = BitSlice<'a, Block>;
176
177    fn bit_slice(self, range: RangeToInclusive<u64>) -> BitSlice<'a, Block> {
178        self.as_slice().bit_slice(range)
179    }
180}
181
182impl<'a, Block: BlockType> BitSliceable<RangeToInclusive<u64>> for &'a mut BitVec<Block> {
183    type Slice = BitSliceMut<'a, Block>;
184
185    fn bit_slice(self, range: RangeToInclusive<u64>) -> BitSliceMut<'a, Block> {
186        self.as_mut_slice().bit_slice(range)
187    }
188}
189
190impl<'a, Block: BlockType> BitSliceable<RangeFull> for &'a BitVec<Block> {
191    type Slice = BitSlice<'a, Block>;
192
193    fn bit_slice(self, _: RangeFull) -> BitSlice<'a, Block> {
194        self.as_slice()
195    }
196}
197
198impl<'a, Block: BlockType> BitSliceable<RangeFull> for &'a mut BitVec<Block> {
199    type Slice = BitSliceMut<'a, Block>;
200
201    fn bit_slice(self, _: RangeFull) -> BitSliceMut<'a, Block> {
202        self.as_mut_slice()
203    }
204}
205
206impl_index_from_bits! {
207    impl[Block: BlockType] Index<u64> for BitVec<Block>;
208}
209
210impl<Other: Bits> PartialEq<Other> for BitVec<Other::Block> {
211    fn eq(&self, other: &Other) -> bool {
212        BlockIter::new(self) == BlockIter::new(other)
213    }
214}
215
216#[allow(clippy::non_canonical_partial_ord_impl)]
217impl<Block: BlockType> PartialOrd for BitVec<Block> {
218    fn partial_cmp(&self, other: &BitVec<Block>) -> Option<Ordering> {
219        let iter1 = BlockIter::new(self);
220        let iter2 = BlockIter::new(other);
221        iter1.partial_cmp(iter2)
222    }
223}
224
225impl<Block: BlockType> Eq for BitVec<Block> {}
226
227impl<Block: BlockType> Ord for BitVec<Block> {
228    fn cmp(&self, other: &Self) -> Ordering {
229        let iter1 = BlockIter::new(self);
230        let iter2 = BlockIter::new(other);
231        iter1.cmp(iter2)
232    }
233}
234
235impl<Block: BlockType + Hash> Hash for BitVec<Block> {
236    fn hash<H: Hasher>(&self, state: &mut H) {
237        self.as_slice().hash(state);
238    }
239}
240
241impl<Block: BlockType> fmt::Debug for BitVec<Block> {
242    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
243        self.as_slice().fmt(f)
244    }
245}
246
247impl<Block: BlockType> From<Box<[Block]>> for BitVec<Block> {
248    fn from(bb: Box<[Block]>) -> Self {
249        let len = Block::mul_nbits(bb.len());
250        BitVec {
251            bits: bb.into(),
252            len,
253        }
254    }
255}
256
257impl<Block: BlockType> From<Vec<Block>> for BitVec<Block> {
258    fn from(vec: Vec<Block>) -> Self {
259        vec.into_boxed_slice().into()
260    }
261}
nostd_bv/bit_vec/impls.rs

nostd_bv/bit_vec/
impls.rs
