17045413678

Committed 18 Aug 2025 03:43PM UTC coverage: 86.065% (-1.8%) from 87.913%

Build # 17045413678

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 2657b4c8e into cb2220961

Pull Request Pull Request #4215: Ji/vectors

Run Details

136 of 1803 new or added lines in 42 files covered. (7.54%)

127 existing lines in 26 files now uncovered.

56918 of 66134 relevant lines covered (86.06%)

612050.14 hits per line

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

0.0

/vortex-vector/src/bits/vector.rs

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

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

use std::fmt::{Debug, Formatter};
use std::ops::Not;
use std::sync::{Arc, LazyLock};

use bitvec::array::BitArray;
use bitvec::order::Lsb0;

use crate::SC;
use crate::bits::{BitView, BitViewMut};

static EMPTY: LazyLock<BitVector> = LazyLock::new(|| BitVector {
    bits: Arc::new(BitArray::ZERO),
    true_count: 0,
});

static FULL: LazyLock<BitVector> = LazyLock::new(|| BitVector {
    bits: Arc::new(BitArray::ZERO.not()),
    true_count: SC,
});

/// An owned fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
///
/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
/// it up for use within Vortex.
#[derive(Clone)]
pub struct BitVector {
    pub(super) bits: Arc<BitArray<[u64; SC / 64], Lsb0>>,
    pub(super) true_count: usize,
}

impl Debug for BitVector {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("BitVector")
            .field("true_count", &self.true_count)
            //.field("bits", &self.bits.as_raw_slice())
            .finish()
    }
}

impl PartialEq for BitVector {
    fn eq(&self, other: &Self) -> bool {
        Arc::ptr_eq(&self.bits, &other.bits)
            || (self.true_count == other.true_count && self.bits == other.bits)
    }
}

impl Eq for BitVector {}

impl BitVector {
    pub fn empty() -> &'static BitVector {
        &EMPTY
    }

    pub fn full() -> &'static BitVector {
        &FULL
    }

    pub fn true_until(n: usize) -> Self {
        assert!(n <= SC, "Cannot create a BitVector with more than N bits");

        let mut bits = Arc::new(BitArray::<[u64; SC / 64], Lsb0>::ZERO);
        let bits_mut = Arc::make_mut(&mut bits);

        let mut word = 0;
        let mut remaining = n;
        while remaining >= 64 {
            bits_mut.as_raw_mut_slice()[word] = u64::MAX;
            remaining -= 64;
            word += 1;
        }

        if remaining > 0 {
            // For LSB ordering, set the lower bits (0 to remaining-1)
            bits_mut.as_raw_mut_slice()[word] = (1u64 << remaining) - 1;
        }

        BitVector {
            bits,
            true_count: n,
        }
    }

    pub fn true_count(&self) -> usize {
        self.true_count
    }

    pub fn as_raw(&self) -> &[u64; SC / 64] {
        // It's actually remarkably hard to get a reference to the underlying array!
        let raw = self.bits.as_raw_slice();
        unsafe { &*(raw.as_ptr() as *const [u64; SC / 64]) }
    }

    pub fn as_raw_mut(&mut self) -> &mut [u64; SC / 64] {
        // SAFETY: We assume that the bits are mutable and that the view is valid.
        let raw = Arc::make_mut(&mut self.bits).as_raw_mut_slice();
        unsafe { &mut *(raw.as_mut_ptr() as *mut [u64; SC / 64]) }
    }

    pub fn fill_from<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = u64>,
    {
        let mut true_count = 0;
        for (dst, word) in self.as_raw_mut().iter_mut().zip(iter) {
            true_count += word.count_ones() as usize;
            *dst = word;
        }
        self.true_count = true_count;
    }

    pub fn as_view(&self) -> BitView<'_> {
        unsafe { BitView::new_unchecked(&self.bits, self.true_count) }
    }

    pub fn as_view_mut(&mut self) -> BitViewMut<'_> {
        unsafe { BitViewMut::new_unchecked(Arc::make_mut(&mut self.bits), self.true_count) }
    }
}

impl From<BitView<'_>> for BitVector {
    fn from(value: BitView<'_>) -> Self {
        let true_count = value.true_count();
        let bits = Arc::new(BitArray::<[u64; SC / 64], Lsb0>::from(*value.as_raw()));
        BitVector { bits, true_count }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fill_from() {
        let mut vec = BitVector::empty().clone();

        // Fill with a pattern
        let pattern = [0b1010101010101010u64, 0b1111000011110000u64, u64::MAX, 0];

        vec.fill_from(pattern.iter().copied());

        let raw = vec.as_raw();
        assert_eq!(raw[0], 0b1010101010101010u64);
        assert_eq!(raw[1], 0b1111000011110000u64);
        assert_eq!(raw[2], u64::MAX);
        assert_eq!(raw[3], 0);

        // Check true_count is updated correctly
        let expected_count = 0b1010101010101010u64.count_ones() as usize
            + 0b1111000011110000u64.count_ones() as usize
            + u64::MAX.count_ones() as usize;
        assert_eq!(vec.true_count(), expected_count);
    }

    #[test]
    fn test_as_view() {
        let vec = BitVector::true_until(100);
        let view = vec.as_view();

        assert_eq!(view.true_count(), 100);

        // Verify the view sees the same bits
        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));
        assert_eq!(ones, (0..100).collect::<Vec<_>>());
    }

    #[test]
    fn test_as_view_mut() {
        let mut vec = BitVector::true_until(64);
        {
            let view_mut = vec.as_view_mut();
            // BitViewMut would allow modifications
            // This test just verifies we can create a mutable view
            assert_eq!(view_mut.true_count(), 64);
        }
        assert_eq!(vec.true_count(), 64);
    }

    #[test]
    fn test_from_bitview() {
        // Create a BitView from raw data
        let mut raw = [0u64; SC / 64];
        raw[0] = 0b11111111;
        raw[1] = 0b11110000;

        let view = BitView::new(&raw);
        let vec = BitVector::from(view);

        assert_eq!(vec.true_count(), view.true_count());
        assert_eq!(vec.as_raw()[0], 0b11111111);
        assert_eq!(vec.as_raw()[1], 0b11110000);
    }

    #[test]
    fn test_lsb_ordering_verification() {
        // Verify LSB ordering by setting specific bits
        let vec = BitVector::true_until(5);
        let view = vec.as_view();

        // Collect which bits are set
        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        // With LSB ordering, bits 0-4 should be set
        assert_eq!(ones, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_as_raw_mut() {
        let mut vec = BitVector::empty().clone();

        // Modify through as_raw_mut
        let raw_mut = vec.as_raw_mut();
        raw_mut[0] = 0b1111;
        raw_mut[2] = u64::MAX;

        // Note: true_count is NOT automatically updated when using as_raw_mut
        // This is a low-level API, so the user must manage true_count
        vec.true_count = 4 + 64; // Update manually

        assert_eq!(vec.as_raw()[0], 0b1111);
        assert_eq!(vec.as_raw()[2], u64::MAX);
        assert_eq!(vec.true_count(), 68);
    }

    #[test]
    fn test_boundary_conditions() {
        // Test various boundary values
        let boundaries = [1, 31, 32, 33, 63, 64, 65, 127, 128, 129, SC - 1, SC];

        for &n in &boundaries {
            let vec = BitVector::true_until(n);
            assert_eq!(vec.true_count(), n);

            // Verify correct bits are set via view
            let view = vec.as_view();
            let mut ones = Vec::new();
            view.iter_ones(|idx| ones.push(idx));
            assert_eq!(ones.len(), n);
            if n > 0 {
                assert_eq!(ones[0], 0); // First bit should be 0 (LSB)
                assert_eq!(ones[n - 1], n - 1); // Last bit should be n-1
            }
        }
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	// SPDX-License-Identifier: Apache-2.0
5	// SPDX-FileCopyrightText: Copyright the Vortex contributors
6
7	use std::fmt::{Debug, Formatter};
8	use std::ops::Not;
9	use std::sync::{Arc, LazyLock};
10
11	use bitvec::array::BitArray;
12	use bitvec::order::Lsb0;
13
14	use crate::SC;
15	use crate::bits::{BitView, BitViewMut};
16
17	static EMPTY: LazyLock<BitVector> = LazyLock::new(\|\| BitVector {
NEW 18	bits: Arc::new(BitArray::ZERO),	×
19	true_count: 0,
NEW 20	});	×
21
22	static FULL: LazyLock<BitVector> = LazyLock::new(\|\| BitVector {
NEW 23	bits: Arc::new(BitArray::ZERO.not()),	×
24	true_count: SC,
NEW 25	});	×
26
27	/// An owned fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
28	///
29	/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
30	/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
31	/// it up for use within Vortex.
32	#[derive(Clone)]
33	pub struct BitVector {
34	pub(super) bits: Arc<BitArray<[u64; SC / 64], Lsb0>>,
35	pub(super) true_count: usize,
36	}
37
38	impl Debug for BitVector {
NEW 39	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
NEW 40	f.debug_struct("BitVector")	×
NEW 41	.field("true_count", &self.true_count)	×
42	//.field("bits", &self.bits.as_raw_slice())
NEW 43	.finish()	×
NEW 44	}	×
45	}
46
47	impl PartialEq for BitVector {
NEW 48	fn eq(&self, other: &Self) -> bool {	×
NEW 49	Arc::ptr_eq(&self.bits, &other.bits)	×
NEW 50	\|\| (self.true_count == other.true_count && self.bits == other.bits)	×
NEW 51	}	×
52	}
53
54	impl Eq for BitVector {}
55
56	impl BitVector {
NEW 57	pub fn empty() -> &'static BitVector {	×
NEW 58	&EMPTY	×
NEW 59	}	×
60
NEW 61	pub fn full() -> &'static BitVector {	×
NEW 62	&FULL	×
NEW 63	}	×
64
NEW 65	pub fn true_until(n: usize) -> Self {	×
NEW 66	assert!(n <= SC, "Cannot create a BitVector with more than N bits");	×
67
NEW 68	let mut bits = Arc::new(BitArray::<[u64; SC / 64], Lsb0>::ZERO);	×
NEW 69	let bits_mut = Arc::make_mut(&mut bits);	×
70
NEW 71	let mut word = 0;	×
NEW 72	let mut remaining = n;	×
NEW 73	while remaining >= 64 {	×
NEW 74	bits_mut.as_raw_mut_slice()[word] = u64::MAX;	×
NEW 75	remaining -= 64;	×
NEW 76	word += 1;	×
NEW 77	}	×
78
NEW 79	if remaining > 0 {	×
NEW 80	// For LSB ordering, set the lower bits (0 to remaining-1)	×
NEW 81	bits_mut.as_raw_mut_slice()[word] = (1u64 << remaining) - 1;	×
NEW 82	}	×
83
NEW 84	BitVector {	×
NEW 85	bits,	×
NEW 86	true_count: n,	×
NEW 87	}	×
NEW 88	}	×
89
NEW 90	pub fn true_count(&self) -> usize {	×
NEW 91	self.true_count	×
NEW 92	}	×
93
NEW 94	pub fn as_raw(&self) -> &[u64; SC / 64] {	×
95	// It's actually remarkably hard to get a reference to the underlying array!
NEW 96	let raw = self.bits.as_raw_slice();	×
NEW 97	unsafe { &(raw.as_ptr() as const [u64; SC / 64]) }	×
NEW 98	}	×
99
NEW 100	pub fn as_raw_mut(&mut self) -> &mut [u64; SC / 64] {	×
101	// SAFETY: We assume that the bits are mutable and that the view is valid.
NEW 102	let raw = Arc::make_mut(&mut self.bits).as_raw_mut_slice();	×
NEW 103	unsafe { &mut (raw.as_mut_ptr() as mut [u64; SC / 64]) }	×
NEW 104	}	×
105
NEW 106	pub fn fill_from<I>(&mut self, iter: I)	×
NEW 107	where	×
NEW 108	I: IntoIterator<Item = u64>,	×
109	{
NEW 110	let mut true_count = 0;	×
NEW 111	for (dst, word) in self.as_raw_mut().iter_mut().zip(iter) {	×
NEW 112	true_count += word.count_ones() as usize;	×
NEW 113	*dst = word;	×
NEW 114	}	×
NEW 115	self.true_count = true_count;	×
NEW 116	}	×
117
NEW 118	pub fn as_view(&self) -> BitView<'_> {	×
NEW 119	unsafe { BitView::new_unchecked(&self.bits, self.true_count) }	×
NEW 120	}	×
121
NEW 122	pub fn as_view_mut(&mut self) -> BitViewMut<'_> {	×
NEW 123	unsafe { BitViewMut::new_unchecked(Arc::make_mut(&mut self.bits), self.true_count) }	×
NEW 124	}	×
125	}
126
127	impl From<BitView<'_>> for BitVector {
NEW 128	fn from(value: BitView<'_>) -> Self {	×
NEW 129	let true_count = value.true_count();	×
NEW 130	let bits = Arc::new(BitArray::<[u64; SC / 64], Lsb0>::from(*value.as_raw()));	×
NEW 131	BitVector { bits, true_count }	×
NEW 132	}	×
133	}
134
135	#[cfg(test)]
136	mod tests {
137	use super::*;
138
139	#[test]
140	fn test_fill_from() {
141	let mut vec = BitVector::empty().clone();
142
143	// Fill with a pattern
144	let pattern = [0b1010101010101010u64, 0b1111000011110000u64, u64::MAX, 0];
145
146	vec.fill_from(pattern.iter().copied());
147
148	let raw = vec.as_raw();
149	assert_eq!(raw[0], 0b1010101010101010u64);
150	assert_eq!(raw[1], 0b1111000011110000u64);
151	assert_eq!(raw[2], u64::MAX);
152	assert_eq!(raw[3], 0);
153
154	// Check true_count is updated correctly
155	let expected_count = 0b1010101010101010u64.count_ones() as usize
156	+ 0b1111000011110000u64.count_ones() as usize
157	+ u64::MAX.count_ones() as usize;
158	assert_eq!(vec.true_count(), expected_count);
159	}
160
161	#[test]
162	fn test_as_view() {
163	let vec = BitVector::true_until(100);
164	let view = vec.as_view();
165
166	assert_eq!(view.true_count(), 100);
167
168	// Verify the view sees the same bits
169	let mut ones = Vec::new();
170	view.iter_ones(\|idx\| ones.push(idx));
171	assert_eq!(ones, (0..100).collect::<Vec<_>>());
172	}
173
174	#[test]
175	fn test_as_view_mut() {
176	let mut vec = BitVector::true_until(64);
177	{
178	let view_mut = vec.as_view_mut();
179	// BitViewMut would allow modifications
180	// This test just verifies we can create a mutable view
181	assert_eq!(view_mut.true_count(), 64);
182	}
183	assert_eq!(vec.true_count(), 64);
184	}
185
186	#[test]
187	fn test_from_bitview() {
188	// Create a BitView from raw data
189	let mut raw = [0u64; SC / 64];
190	raw[0] = 0b11111111;
191	raw[1] = 0b11110000;
192
193	let view = BitView::new(&raw);
194	let vec = BitVector::from(view);
195
196	assert_eq!(vec.true_count(), view.true_count());
197	assert_eq!(vec.as_raw()[0], 0b11111111);
198	assert_eq!(vec.as_raw()[1], 0b11110000);
199	}
200
201	#[test]
202	fn test_lsb_ordering_verification() {
203	// Verify LSB ordering by setting specific bits
204	let vec = BitVector::true_until(5);
205	let view = vec.as_view();
206
207	// Collect which bits are set
208	let mut ones = Vec::new();
209	view.iter_ones(\|idx\| ones.push(idx));
210
211	// With LSB ordering, bits 0-4 should be set
212	assert_eq!(ones, vec![0, 1, 2, 3, 4]);
213	}
214
215	#[test]
216	fn test_as_raw_mut() {
217	let mut vec = BitVector::empty().clone();
218
219	// Modify through as_raw_mut
220	let raw_mut = vec.as_raw_mut();
221	raw_mut[0] = 0b1111;
222	raw_mut[2] = u64::MAX;
223
224	// Note: true_count is NOT automatically updated when using as_raw_mut
225	// This is a low-level API, so the user must manage true_count
226	vec.true_count = 4 + 64; // Update manually
227
228	assert_eq!(vec.as_raw()[0], 0b1111);
229	assert_eq!(vec.as_raw()[2], u64::MAX);
230	assert_eq!(vec.true_count(), 68);
231	}
232
233	#[test]
234	fn test_boundary_conditions() {
235	// Test various boundary values
236	let boundaries = [1, 31, 32, 33, 63, 64, 65, 127, 128, 129, SC - 1, SC];
237
238	for &n in &boundaries {
239	let vec = BitVector::true_until(n);
240	assert_eq!(vec.true_count(), n);
241
242	// Verify correct bits are set via view
243	let view = vec.as_view();
244	let mut ones = Vec::new();
245	view.iter_ones(\|idx\| ones.push(idx));
246	assert_eq!(ones.len(), n);
247	if n > 0 {
248	assert_eq!(ones[0], 0); // First bit should be 0 (LSB)
249	assert_eq!(ones[n - 1], n - 1); // Last bit should be n-1
250	}
251	}
252	}
253	}

vortex-data / vortex / 17045413678

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