16970635821

Committed 14 Aug 2025 04:13PM UTC coverage: 85.882% (-1.8%) from 87.693%

Build # 16970635821

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 5182504a6 into f547cbca5

Pull Request Pull Request #4215: Ji/vectors

Run Details

80 of 1729 new or added lines in 38 files covered. (4.63%)

117 existing lines in 25 files now uncovered.

56994 of 66363 relevant lines covered (85.88%)

609331.7 hits per line

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

0.0

/vortex-array/src/pipeline/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::Msb0;

use crate::pipeline::N;
use crate::pipeline::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: N,
});

/// 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; N / 64], Msb0>>,
    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 <= N, "Cannot create a BitVector with more than N bits");

        let mut bits = Arc::new(BitArray::<[u64; N / 64], Msb0>::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 {
            bits_mut.as_raw_mut_slice()[word] = u64::MAX << (64 - remaining);
        }

        BitVector {
            bits,
            true_count: n,
        }
    }

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

    pub fn as_raw(&self) -> &[u64; N / 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; N / 64]) }
    }

    pub fn as_raw_mut(&mut self) -> &mut [u64; N / 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; N / 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; N / 64], Msb0>::from(*value.as_raw()));
        BitVector { bits, true_count }
    }
}

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::Msb0;
13
14	use crate::pipeline::N;
15	use crate::pipeline::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: N,
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; N / 64], Msb0>>,
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 <= N, "Cannot create a BitVector with more than N bits");	×
67
NEW 68	let mut bits = Arc::new(BitArray::<[u64; N / 64], Msb0>::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	bits_mut.as_raw_mut_slice()[word] = u64::MAX << (64 - remaining);	×
NEW 81	}	×
82
NEW 83	BitVector {	×
NEW 84	bits,	×
NEW 85	true_count: n,	×
NEW 86	}	×
NEW 87	}	×
88
NEW 89	pub fn true_count(&self) -> usize {	×
NEW 90	self.true_count	×
NEW 91	}	×
92
NEW 93	pub fn as_raw(&self) -> &[u64; N / 64] {	×
94	// It's actually remarkably hard to get a reference to the underlying array!
NEW 95	let raw = self.bits.as_raw_slice();	×
NEW 96	unsafe { &(raw.as_ptr() as const [u64; N / 64]) }	×
NEW 97	}	×
98
NEW 99	pub fn as_raw_mut(&mut self) -> &mut [u64; N / 64] {	×
100	// SAFETY: We assume that the bits are mutable and that the view is valid.
NEW 101	let raw = Arc::make_mut(&mut self.bits).as_raw_mut_slice();	×
NEW 102	unsafe { &mut (raw.as_mut_ptr() as mut [u64; N / 64]) }	×
NEW 103	}	×
104
NEW 105	pub fn fill_from<I>(&mut self, iter: I)	×
NEW 106	where	×
NEW 107	I: IntoIterator<Item = u64>,	×
108	{
NEW 109	let mut true_count = 0;	×
NEW 110	for (dst, word) in self.as_raw_mut().iter_mut().zip(iter) {	×
NEW 111	true_count += word.count_ones() as usize;	×
NEW 112	*dst = word;	×
NEW 113	}	×
NEW 114	self.true_count = true_count;	×
NEW 115	}	×
116
NEW 117	pub fn as_view(&self) -> BitView<'_> {	×
NEW 118	unsafe { BitView::new_unchecked(&self.bits, self.true_count) }	×
NEW 119	}	×
120
NEW 121	pub fn as_view_mut(&mut self) -> BitViewMut<'_> {	×
NEW 122	unsafe { BitViewMut::new_unchecked(Arc::make_mut(&mut self.bits), self.true_count) }	×
NEW 123	}	×
124	}
125
126	impl From<BitView<'_>> for BitVector {
NEW 127	fn from(value: BitView<'_>) -> Self {	×
NEW 128	let true_count = value.true_count();	×
NEW 129	let bits = Arc::new(BitArray::<[u64; N / 64], Msb0>::from(*value.as_raw()));	×
NEW 130	BitVector { bits, true_count }	×
NEW 131	}	×
132	}

vortex-data / vortex / 16970635821

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