16980200873

Committed 15 Aug 2025 12:53AM UTC coverage: 49.805%. First build

Build # 16980200873

Build Type

Pull #2456

github

Committed by

web-flow

Commit Message

Merge aff477380 into aaf3e36ad

Pull Request Pull Request #2456: feat: basic BoolBuffer / BoolBufferMut

Coverage Stats

574 of 1074 new or added lines in 84 files covered. (53.45%)

20158 of 40474 relevant lines covered (49.8%)

238516.31 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

46.29

/vortex-buffer/src/bit/buf_mut.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::ops::Range;

use bitvec::prelude::Lsb0;
use bitvec::view::BitView;
use vortex_error::VortexExpect;

use crate::{BitBuffer, BufferMut, ByteBuffer, ByteBufferMut, buffer_mut, get_bit};

/// A mutable bitset buffer that allows random access to individual bits for set and get.
///
///
/// # Example
/// ```
/// use vortex_buffer::BitBufferMut;
///
/// let mut bools = BitBufferMut::new_unset(10);
/// bools.set_to(9, true);
/// for i in 0..9 {
///    assert!(!bools.value(i));
/// }
/// assert!(bools.value(9));
///
/// // Freeze into a new bools vector.
/// let bools = bools.freeze();
/// ```
///
/// See also: [`crate::BitBuffer`].
pub struct BitBufferMut {
    buffer: ByteBufferMut,
    len: usize,
}

impl BitBufferMut {
    /// Create new bit buffer from given byte buffer and logical bit length
    pub fn from_buffer(buffer: ByteBufferMut, len: usize) -> Self {
        assert!(
            len <= buffer.len() * 8,
            "Buffer len {} is too short for the given length {len}",
            buffer.len()
        );
        Self { buffer, len }
    }

    /// Create a new empty mutable bit buffer with requested capacity (in bits).
    pub fn new(capacity: usize) -> Self {
        Self {
            buffer: BufferMut::with_capacity(capacity.div_ceil(8)),
            len: 0,
        }
    }

    /// Create a new mutable buffer with requested `len` and all bits set to `true`.
    pub fn new_set(len: usize) -> Self {
        Self {
            buffer: buffer_mut![0xFF; len.div_ceil(8)],
            len,
        }
    }

    /// Create a new mutable buffer with requested `len` and all bits set to `false`.
    pub fn new_unset(len: usize) -> Self {
        Self {
            buffer: BufferMut::zeroed(len.div_ceil(8)),
            len,
        }
    }

    /// Create a new empty `BitBufferMut`.
    pub fn empty() -> Self {
        Self::new(0)
    }

    /// Get the current populated length of the buffer.
    pub fn len(&self) -> usize {
        self.len
    }

    /// True if the buffer has length 0.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Get the value at the requested index.
    pub fn value(&self, index: usize) -> bool {
        get_bit(&self.buffer, index)
    }

    /// Get the bit capacity of the buffer.
    pub fn capacity(&self) -> usize {
        self.buffer.capacity() * 8
    }

    /// Reserve additional bit capacity for the buffer.
    pub fn reserve(&mut self, additional: usize) {
        let capacity = self.len + additional;
        if capacity > self.capacity() {
            // convert differential to bytes
            let additional = capacity.div_ceil(8) - self.buffer.len();
            self.buffer.reserve(additional);
        }
    }

    /// Set the bit at `index` to the given boolean value.
    ///
    /// This operation is checked so if `index` exceeds the buffer length, this will panic.
    pub fn set_to(&mut self, index: usize, value: bool) {
        if value {
            self.set(index);
        } else {
            self.unset(index);
        }
    }

    /// Set a position to `true`.
    ///
    /// This operation is checked so if `index` exceeds the buffer length, this will panic.
    pub fn set(&mut self, index: usize) {
        assert!(index < self.len, "index {index} exceeds len {}", self.len);

        // SAFETY: checked by assertion
        unsafe { self.set_unchecked(index) };
    }

    /// Set a position to `false`.
    ///
    /// This operation is checked so if `index` exceeds the buffer length, this will panic.
    pub fn unset(&mut self, index: usize) {
        assert!(index < self.len, "index {index} exceeds len {}", self.len);

        // SAFETY: checked by assertion
        unsafe { self.unset_unchecked(index) };
    }

    /// Set the bit at `index` to `true` without checking bounds.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `index` does not exceed the largest bit index in the backing buffer.
    pub unsafe fn set_unchecked(&mut self, index: usize) {
        let word_index = index / 8;
        let bit_index = index % 8;
        // SAFETY: checked by caller
        unsafe {
            let word = self.buffer.as_mut_ptr().add(word_index);
            word.write(*word | 1 << bit_index);
        }
    }

    /// Unset the bit at `index` without checking bounds.
    ///
    /// # Safety
    ///
    /// The caller must ensure that `index` does not exceed the largest bit index in the backing buffer.
    pub unsafe fn unset_unchecked(&mut self, index: usize) {
        let word_index = index / 8;
        let bit_index = index % 8;

        // SAFETY: checked by caller
        unsafe {
            let word = self.buffer.as_mut_ptr().add(word_index);
            word.write(*word & !(1 << bit_index));
        }
    }

    /// Truncate the buffer to the given length.
    pub fn truncate(&mut self, len: usize) {
        if len > self.len {
            return;
        }

        let new_len_bytes = len.div_ceil(8);
        self.buffer.truncate(new_len_bytes);
        self.len = len;

        let remainder = self.len % 8;
        if remainder != 0 {
            let mask = (1u8 << remainder).wrapping_sub(1);
            *self.buffer.as_mut().last_mut().vortex_expect("non empty") &= mask;
        }
    }

    /// Append a new boolean into the bit buffer, incrementing the length.
    ///
    /// Panics if the buffer is full.
    pub fn append(&mut self, value: bool) {
        if value {
            self.append_true()
        } else {
            self.append_false()
        }
    }

    /// Append a new true value to the buffer.
    ///
    /// Panics if there is no remaining capacity.
    pub fn append_true(&mut self) {
        if self.len % 8 == 0 {
            // Push a new word that starts with 1
            self.buffer.push(1u8);
        } else {
            // Push a 1 bit into the current word.
            let word = self.buffer.last_mut().vortex_expect("buffer is not empty");
            *word |= 1 << (self.len % 8);
        }

        self.len += 1;
    }

    /// Append a new false value to the buffer.
    ///
    /// Panics if there is no remaining capacity.
    pub fn append_false(&mut self) {
        if self.len % 8 == 0 {
            // push new word that starts with 0
            self.buffer.push(0u8);
        }

        self.len += 1;
    }
    /// Append several boolean values into the bit buffer. After this operation,
    /// the length will be incremented by `n`.
    ///
    /// Panics if the buffer does not have `n` slots left.
    pub fn append_n(&mut self, value: bool, n: usize) {
        match value {
            true => {
                let new_len = self.len + n;
                let new_len_bytes = new_len.div_ceil(8);
                let cur_remainder = self.len % 8;
                let new_remainder = new_len % 8;

                if cur_remainder != 0 {
                    // Pad cur_remainder high bits with 1s
                    *self
                        .buffer
                        .as_mut_slice()
                        .last_mut()
                        .vortex_expect("buffer is not empty") |= !((1 << cur_remainder) - 1);
                }

                // Push several full bytes.
                if new_len_bytes > self.buffer.len() {
                    // Push full bytes, except for the final byte.
                    self.buffer.push_n(0xFF, new_len_bytes - self.buffer.len());
                }

                // Patch zeros into remainder of last byte pushed
                if new_remainder > 0 {
                    // Set the new_remainder LSB to 1
                    *self
                        .buffer
                        .as_mut_slice()
                        .last_mut()
                        .vortex_expect("buffer is not empty") &= (1 << new_remainder) - 1;
                }
            }
            false => {
                let new_len = self.len + n;
                let new_len_bytes = new_len.div_ceil(8);

                // push new 0 bytes.
                if new_len_bytes > self.buffer.len() {
                    self.buffer.push_n(0, new_len_bytes - self.buffer.len());
                }
            }
        }

        self.len += n;
    }

    /// Append bits defined by range from values to this buffer
    pub fn append_packed_range(&mut self, range: Range<usize>, values: &ByteBuffer) {
        let bit_len = range.end - range.start;
        self.buffer.reserve(bit_len.div_ceil(8));
        // SAFETY: The copy below will populate the values
        unsafe { self.buffer.set_len((self.len + bit_len).div_ceil(8)) };

        let self_slice = self.buffer.as_mut_slice().view_bits_mut::<Lsb0>();
        let other_slice = values.as_slice().view_bits::<Lsb0>();

        let other_sliced = &other_slice[range.start..range.end];
        let sliced = &mut self_slice[self.len..][..bit_len];
        sliced.copy_from_bitslice(other_sliced);
        self.len += bit_len;
    }

    /// Append a [`BitBuffer`] to this [`BitBufferMut`]
    pub fn append_buffer(&mut self, buffer: &BitBuffer) {
        let buffer_range = buffer.offset()..buffer.offset() + buffer.len();
        self.append_packed_range(buffer_range, buffer.inner())
    }

    /// Freeze the buffer in its current state into an immutable `BoolBuffer`.
    pub fn freeze(self) -> BitBuffer {
        BitBuffer::new(self.buffer.freeze().into_byte_buffer(), self.len)
    }

    /// Get the underlying bytes as a slice
    pub fn as_slice(&self) -> &[u8] {
        self.buffer.as_slice()
    }

    /// Get the underlying bytes as a mutable slice
    pub fn as_mut_slice(&mut self) -> &mut [u8] {
        self.buffer.as_mut_slice()
    }
}

impl Default for BitBufferMut {
    fn default() -> Self {
        Self::new(0)
    }
}

#[cfg(test)]
mod tests {
    use crate::bit::buf_mut::BitBufferMut;

    #[test]
    fn test_bits_mut() {
        let mut bools = BitBufferMut::new_unset(10);
        bools.set_to(0, true);
        bools.set_to(9, true);

        let bools = bools.freeze();
        assert!(bools.value(0));
        for i in 1..=8 {
            assert!(!bools.value(i));
        }
        assert!(bools.value(9));
    }

    #[test]
    fn test_append_n() {
        let mut bools = BitBufferMut::new(10);
        assert_eq!(bools.len(), 0);
        assert!(bools.is_empty());

        bools.append(true);
        bools.append_n(false, 8);
        bools.append_n(true, 1);

        let bools = bools.freeze();

        assert_eq!(bools.true_count(), 2);
        assert!(bools.value(0));
        assert!(bools.value(9));
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::ops::Range;
5
6	use bitvec::prelude::Lsb0;
7	use bitvec::view::BitView;
8	use vortex_error::VortexExpect;
9
10	use crate::{BitBuffer, BufferMut, ByteBuffer, ByteBufferMut, buffer_mut, get_bit};
11
12	/// A mutable bitset buffer that allows random access to individual bits for set and get.
13	///
14	///
15	/// # Example
16	/// ```
17	/// use vortex_buffer::BitBufferMut;
18	///
19	/// let mut bools = BitBufferMut::new_unset(10);
20	/// bools.set_to(9, true);
21	/// for i in 0..9 {
22	/// assert!(!bools.value(i));
23	/// }
24	/// assert!(bools.value(9));
25	///
26	/// // Freeze into a new bools vector.
27	/// let bools = bools.freeze();
28	/// ```
29	///
30	/// See also: [`crate::BitBuffer`].
31	pub struct BitBufferMut {
32	buffer: ByteBufferMut,
33	len: usize,
34	}
35
36	impl BitBufferMut {
37	/// Create new bit buffer from given byte buffer and logical bit length
NEW 38	pub fn from_buffer(buffer: ByteBufferMut, len: usize) -> Self {	×
NEW 39	assert!(	×
NEW 40	len <= buffer.len() * 8,	×
NEW 41	"Buffer len {} is too short for the given length {len}",	×
NEW 42	buffer.len()	×
43	);
NEW 44	Self { buffer, len }	×
NEW 45	}	×
46
47	/// Create a new empty mutable bit buffer with requested capacity (in bits).
48	pub fn new(capacity: usize) -> Self {	1,512✔
49	Self {	1,512✔
50	buffer: BufferMut::with_capacity(capacity.div_ceil(8)),	1,512✔
51	len: 0,	1,512✔
52	}	1,512✔
53	}	1,512✔
54
55	/// Create a new mutable buffer with requested `len` and all bits set to `true`.
NEW 56	pub fn new_set(len: usize) -> Self {	×
NEW 57	Self {	×
NEW 58	buffer: buffer_mut![0xFF; len.div_ceil(8)],	×
NEW 59	len,	×
NEW 60	}	×
NEW 61	}	×
62
63	/// Create a new mutable buffer with requested `len` and all bits set to `false`.
64	pub fn new_unset(len: usize) -> Self {	498✔
65	Self {	498✔
66	buffer: BufferMut::zeroed(len.div_ceil(8)),	498✔
67	len,	498✔
68	}	498✔
69	}	498✔
70
71	/// Create a new empty `BitBufferMut`.
NEW 72	pub fn empty() -> Self {	×
NEW 73	Self::new(0)	×
NEW 74	}	×
75
76	/// Get the current populated length of the buffer.
77	pub fn len(&self) -> usize {	882✔
78	self.len	882✔
79	}	882✔
80
81	/// True if the buffer has length 0.
NEW 82	pub fn is_empty(&self) -> bool {	×
NEW 83	self.len == 0	×
NEW 84	}	×
85
86	/// Get the value at the requested index.
NEW 87	pub fn value(&self, index: usize) -> bool {	×
NEW 88	get_bit(&self.buffer, index)	×
NEW 89	}	×
90
91	/// Get the bit capacity of the buffer.
NEW 92	pub fn capacity(&self) -> usize {	×
NEW 93	self.buffer.capacity() * 8	×
NEW 94	}	×
95
96	/// Reserve additional bit capacity for the buffer.
NEW 97	pub fn reserve(&mut self, additional: usize) {	×
NEW 98	let capacity = self.len + additional;	×
NEW 99	if capacity > self.capacity() {	×
NEW 100	// convert differential to bytes	×
NEW 101	let additional = capacity.div_ceil(8) - self.buffer.len();	×
NEW 102	self.buffer.reserve(additional);	×
NEW 103	}	×
NEW 104	}	×
105
106	/// Set the bit at `index` to the given boolean value.
107	///
108	/// This operation is checked so if `index` exceeds the buffer length, this will panic.
NEW 109	pub fn set_to(&mut self, index: usize, value: bool) {	×
NEW 110	if value {	×
NEW 111	self.set(index);	×
NEW 112	} else {	×
NEW 113	self.unset(index);	×
NEW 114	}	×
NEW 115	}	×
116
117	/// Set a position to `true`.
118	///
119	/// This operation is checked so if `index` exceeds the buffer length, this will panic.
120	pub fn set(&mut self, index: usize) {	782,385✔
121	assert!(index < self.len, "index {index} exceeds len {}", self.len);	782,385✔
122
123	// SAFETY: checked by assertion
124	unsafe { self.set_unchecked(index) };	782,385✔
125	}	782,385✔
126
127	/// Set a position to `false`.
128	///
129	/// This operation is checked so if `index` exceeds the buffer length, this will panic.
NEW 130	pub fn unset(&mut self, index: usize) {	×
NEW 131	assert!(index < self.len, "index {index} exceeds len {}", self.len);	×
132
133	// SAFETY: checked by assertion
NEW 134	unsafe { self.unset_unchecked(index) };	×
NEW 135	}	×
136
137	/// Set the bit at `index` to `true` without checking bounds.
138	///
139	/// # Safety
140	///
141	/// The caller must ensure that `index` does not exceed the largest bit index in the backing buffer.
142	pub unsafe fn set_unchecked(&mut self, index: usize) {	782,385✔
143	let word_index = index / 8;	782,385✔
144	let bit_index = index % 8;	782,385✔
145	// SAFETY: checked by caller
146	unsafe {	782,385✔
147	let word = self.buffer.as_mut_ptr().add(word_index);	782,385✔
148	word.write(*word \| 1 << bit_index);	782,385✔
149	}	782,385✔
150	}	782,385✔
151
152	/// Unset the bit at `index` without checking bounds.
153	///
154	/// # Safety
155	///
156	/// The caller must ensure that `index` does not exceed the largest bit index in the backing buffer.
NEW 157	pub unsafe fn unset_unchecked(&mut self, index: usize) {	×
NEW 158	let word_index = index / 8;	×
NEW 159	let bit_index = index % 8;	×
160
161	// SAFETY: checked by caller
NEW 162	unsafe {	×
NEW 163	let word = self.buffer.as_mut_ptr().add(word_index);	×
NEW 164	word.write(*word & !(1 << bit_index));	×
NEW 165	}	×
NEW 166	}	×
167
168	/// Truncate the buffer to the given length.
NEW 169	pub fn truncate(&mut self, len: usize) {	×
NEW 170	if len > self.len {	×
NEW 171	return;	×
NEW 172	}	×
173
NEW 174	let new_len_bytes = len.div_ceil(8);	×
NEW 175	self.buffer.truncate(new_len_bytes);	×
NEW 176	self.len = len;	×
177
NEW 178	let remainder = self.len % 8;	×
NEW 179	if remainder != 0 {	×
NEW 180	let mask = (1u8 << remainder).wrapping_sub(1);	×
NEW 181	*self.buffer.as_mut().last_mut().vortex_expect("non empty") &= mask;	×
NEW 182	}	×
NEW 183	}	×
184
185	/// Append a new boolean into the bit buffer, incrementing the length.
186	///
187	/// Panics if the buffer is full.
NEW 188	pub fn append(&mut self, value: bool) {	×
NEW 189	if value {	×
NEW 190	self.append_true()	×
191	} else {
NEW 192	self.append_false()	×
193	}
NEW 194	}	×
195
196	/// Append a new true value to the buffer.
197	///
198	/// Panics if there is no remaining capacity.
NEW 199	pub fn append_true(&mut self) {	×
NEW 200	if self.len % 8 == 0 {	×
NEW 201	// Push a new word that starts with 1	×
NEW 202	self.buffer.push(1u8);	×
NEW 203	} else {	×
NEW 204	// Push a 1 bit into the current word.	×
NEW 205	let word = self.buffer.last_mut().vortex_expect("buffer is not empty");	×
NEW 206	*word \|= 1 << (self.len % 8);	×
NEW 207	}	×
208
NEW 209	self.len += 1;	×
NEW 210	}	×
211
212	/// Append a new false value to the buffer.
213	///
214	/// Panics if there is no remaining capacity.
NEW 215	pub fn append_false(&mut self) {	×
NEW 216	if self.len % 8 == 0 {	×
NEW 217	// push new word that starts with 0	×
NEW 218	self.buffer.push(0u8);	×
NEW 219	}	×
220
NEW 221	self.len += 1;	×
NEW 222	}	×
223	/// Append several boolean values into the bit buffer. After this operation,
224	/// the length will be incremented by `n`.
225	///
226	/// Panics if the buffer does not have `n` slots left.
227	pub fn append_n(&mut self, value: bool, n: usize) {	7,680✔
228	match value {	7,680✔
229	true => {
230	let new_len = self.len + n;	4,353✔
231	let new_len_bytes = new_len.div_ceil(8);	4,353✔
232	let cur_remainder = self.len % 8;	4,353✔
233	let new_remainder = new_len % 8;	4,353✔
234
235	if cur_remainder != 0 {	4,353✔
236	// Pad cur_remainder high bits with 1s	576✔
237	*self	576✔
238	.buffer	576✔
239	.as_mut_slice()	576✔
240	.last_mut()	576✔
241	.vortex_expect("buffer is not empty") \|= !((1 << cur_remainder) - 1);	576✔
242	}	3,777✔
243
244	// Push several full bytes.
245	if new_len_bytes > self.buffer.len() {	4,353✔
246	// Push full bytes, except for the final byte.	4,287✔
247	self.buffer.push_n(0xFF, new_len_bytes - self.buffer.len());	4,287✔
248	}	4,287✔
249
250	// Patch zeros into remainder of last byte pushed
251	if new_remainder > 0 {	4,353✔
252	// Set the new_remainder LSB to 1	933✔
253	*self	933✔
254	.buffer	933✔
255	.as_mut_slice()	933✔
256	.last_mut()	933✔
257	.vortex_expect("buffer is not empty") &= (1 << new_remainder) - 1;	933✔
258	}	3,420✔
259	}
260	false => {
261	let new_len = self.len + n;	3,327✔
262	let new_len_bytes = new_len.div_ceil(8);	3,327✔
263
264	// push new 0 bytes.
265	if new_len_bytes > self.buffer.len() {	3,327✔
266	self.buffer.push_n(0, new_len_bytes - self.buffer.len());	909✔
267	}	2,418✔
268	}
269	}
270
271	self.len += n;	7,680✔
272	}	7,680✔
273
274	/// Append bits defined by range from values to this buffer
275	pub fn append_packed_range(&mut self, range: Range<usize>, values: &ByteBuffer) {	12✔
276	let bit_len = range.end - range.start;	12✔
277	self.buffer.reserve(bit_len.div_ceil(8));	12✔
278	// SAFETY: The copy below will populate the values
279	unsafe { self.buffer.set_len((self.len + bit_len).div_ceil(8)) };	12✔
280
281	let self_slice = self.buffer.as_mut_slice().view_bits_mut::<Lsb0>();	12✔
282	let other_slice = values.as_slice().view_bits::<Lsb0>();	12✔
283
284	let other_sliced = &other_slice[range.start..range.end];	12✔
285	let sliced = &mut self_slice[self.len..][..bit_len];	12✔
286	sliced.copy_from_bitslice(other_sliced);	12✔
287	self.len += bit_len;	12✔
288	}	12✔
289
290	/// Append a [`BitBuffer`] to this [`BitBufferMut`]
291	pub fn append_buffer(&mut self, buffer: &BitBuffer) {	12✔
292	let buffer_range = buffer.offset()..buffer.offset() + buffer.len();	12✔
293	self.append_packed_range(buffer_range, buffer.inner())	12✔
294	}	12✔
295
296	/// Freeze the buffer in its current state into an immutable `BoolBuffer`.
297	pub fn freeze(self) -> BitBuffer {	1,650✔
298	BitBuffer::new(self.buffer.freeze().into_byte_buffer(), self.len)	1,650✔
299	}	1,650✔
300
301	/// Get the underlying bytes as a slice
NEW 302	pub fn as_slice(&self) -> &[u8] {	×
NEW 303	self.buffer.as_slice()	×
NEW 304	}	×
305
306	/// Get the underlying bytes as a mutable slice
NEW 307	pub fn as_mut_slice(&mut self) -> &mut [u8] {	×
NEW 308	self.buffer.as_mut_slice()	×
NEW 309	}	×
310	}
311
312	impl Default for BitBufferMut {
313	fn default() -> Self {	360✔
314	Self::new(0)	360✔
315	}	360✔
316	}
317
318	#[cfg(test)]
319	mod tests {
320	use crate::bit::buf_mut::BitBufferMut;
321
322	#[test]
323	fn test_bits_mut() {
324	let mut bools = BitBufferMut::new_unset(10);
325	bools.set_to(0, true);
326	bools.set_to(9, true);
327
328	let bools = bools.freeze();
329	assert!(bools.value(0));
330	for i in 1..=8 {
331	assert!(!bools.value(i));
332	}
333	assert!(bools.value(9));
334	}
335
336	#[test]
337	fn test_append_n() {
338	let mut bools = BitBufferMut::new(10);
339	assert_eq!(bools.len(), 0);
340	assert!(bools.is_empty());
341
342	bools.append(true);
343	bools.append_n(false, 8);
344	bools.append_n(true, 1);
345
346	let bools = bools.freeze();
347
348	assert_eq!(bools.true_count(), 2);
349	assert!(bools.value(0));
350	assert!(bools.value(9));
351	}
352	}

vortex-data / vortex / 16980200873

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous