nostd_bv/traits/
bits_mut.rs

1use super::Bits;
2use crate::storage::{Address, BlockType};
3use alloc::{boxed::Box, vec::Vec};
4
5/// Mutable bit vector operations that don’t affect the length.
6///
7/// Minimal complete definition is `set_bit` or `set_block`, since each
8/// is defined in terms of the other. Note that `set_block` in terms of
9/// `set_bit` is inefficient, and thus you should implement `set_block`
10/// directly if possible.
11pub trait BitsMut: Bits {
12    /// Sets the bit at `position` to `value`.
13    ///
14    /// The default implementation uses `get_raw_block` and `set_block`.
15    ///
16    /// # Panics
17    ///
18    /// Panics if `position` is out of bounds.
19    fn set_bit(&mut self, position: u64, value: bool) {
20        assert!(position < self.bit_len(), "BitsMut::set_bit: out of bounds");
21
22        let address = Address::new::<Self::Block>(position);
23        let old_block = self.get_raw_block(address.block_index);
24        let new_block = old_block.with_bit(address.bit_offset, value);
25        self.set_block(address.block_index, new_block);
26    }
27
28    /// Sets the block at `position` to `value`.
29    ///
30    /// The bits are laid out `Block::nbits()` per block, with the notional
31    /// zeroth bit in the least significant position. If `self.bit_len()` is
32    /// not a multiple of `Block::nbits()` then the last block will
33    /// contain extra bits that are not part of the bit vector. Implementations
34    /// of `set_block` should not change those trailing bits.
35    ///
36    /// The default implementation sets a block by setting each of its bits
37    /// in turn. Consider it a slow reference implementation, and override it.
38    ///
39    /// # Panics
40    ///
41    /// Panics if `position` is out of bounds.
42    fn set_block(&mut self, position: usize, mut value: Self::Block) {
43        let offset = Self::Block::mul_nbits(position);
44        let count = Self::Block::block_bits(self.bit_len(), position);
45
46        for i in 0..count as u64 {
47            let bit = value & Self::Block::one() != Self::Block::zero();
48            self.set_bit(offset + i, bit);
49            value = value >> 1;
50        }
51    }
52
53    /// Sets `count` bits starting at bit index `start`, interpreted as a
54    /// little-endian integer.
55    ///
56    /// # Panics
57    ///
58    /// Panics if the bit span goes out of bounds.
59    fn set_bits(&mut self, start: u64, count: usize, value: Self::Block) {
60        let limit = start + count as u64;
61        assert!(limit <= self.bit_len(), "BitsMut::set_bits: out of bounds");
62
63        let address = Address::new::<Self::Block>(start);
64        let margin = Self::Block::nbits() - address.bit_offset;
65
66        if margin >= count {
67            let old_block = self.get_raw_block(address.block_index);
68            let new_block = old_block.with_bits(address.bit_offset, count, value);
69            self.set_block(address.block_index, new_block);
70            return;
71        }
72
73        let extra = count - margin;
74
75        let old_block1 = self.get_raw_block(address.block_index);
76        let old_block2 = self.get_raw_block(address.block_index + 1);
77
78        let high_bits = value >> margin;
79
80        let new_block1 = old_block1.with_bits(address.bit_offset, margin, value);
81        let new_block2 = old_block2.with_bits(0, extra, high_bits);
82        self.set_block(address.block_index, new_block1);
83        self.set_block(address.block_index + 1, new_block2);
84    }
85}
86
87impl<T: BitsMut + ?Sized> BitsMut for &mut T {
88    fn set_bit(&mut self, position: u64, value: bool) {
89        T::set_bit(*self, position, value);
90    }
91
92    fn set_block(&mut self, position: usize, value: Self::Block) {
93        T::set_block(*self, position, value);
94    }
95
96    fn set_bits(&mut self, start: u64, count: usize, value: Self::Block) {
97        T::set_bits(*self, start, count, value);
98    }
99}
100
101impl<Block: BlockType> BitsMut for Box<dyn BitsMut<Block = Block>> {
102    fn set_bit(&mut self, position: u64, value: bool) {
103        (**self).set_bit(position, value);
104    }
105
106    fn set_block(&mut self, position: usize, value: Block) {
107        (**self).set_block(position, value);
108    }
109
110    fn set_bits(&mut self, start: u64, len: usize, value: Block) {
111        (**self).set_bits(start, len, value);
112    }
113}
114
115impl<Block: BlockType> BitsMut for [Block] {
116    fn set_bit(&mut self, position: u64, value: bool) {
117        let address = Address::new::<Block>(position);
118        let block = &mut self[address.block_index];
119        *block = block.with_bit(address.bit_offset, value);
120    }
121
122    fn set_block(&mut self, position: usize, value: Block) {
123        self[position] = value;
124    }
125}
126
127impl<Block: BlockType> BitsMut for Vec<Block> {
128    fn set_bit(&mut self, position: u64, value: bool) {
129        <[Block]>::set_bit(&mut *self, position, value);
130    }
131
132    fn set_block(&mut self, position: usize, value: Block) {
133        <[Block]>::set_block(&mut *self, position, value);
134    }
135}
136
137impl BitsMut for [bool] {
138    fn set_bit(&mut self, position: u64, value: bool) {
139        let position = position.to_usize().expect("Vec<bool>::set_bit: overflow");
140        self[position] = value;
141    }
142}
143
144impl BitsMut for Vec<bool> {
145    #[inline]
146    fn set_bit(&mut self, position: u64, value: bool) {
147        self.as_mut_slice().set_bit(position, value)
148    }
149}
nostd_bv/traits/bits_mut.rs

nostd_bv/traits/
bits_mut.rs
