16969983197

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

Build # 16969983197

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 6636736da 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/view.rs

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

use std::fmt::{Debug, Formatter};

use bitvec::prelude::*;
use vortex_error::{VortexError, vortex_err};

use crate::pipeline::N;

/// A borrowed 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, Copy)]
pub struct BitView<'a> {
    bits: &'a BitArray<[u64; N / 64], Msb0>,
    true_count: usize,
}

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

impl BitView<'static> {
    pub fn all_true() -> Self {
        unsafe { BitView::new_unchecked(std::mem::transmute(&[u64::MAX; N / 64]), N) }
    }

    pub fn all_false() -> Self {
        unsafe { BitView::new_unchecked(std::mem::transmute(&[0; N / 64]), 0) }
    }
}

impl<'a> BitView<'a> {
    pub fn new(bits: &[u64; N / 64]) -> Self {
        let true_count = bits.iter().map(|&word| word.count_ones() as usize).sum();
        let bits: &BitArray<[u64; N / 64], Msb0> = unsafe { std::mem::transmute(bits) };
        BitView { bits, true_count }
    }

    pub(crate) unsafe fn new_unchecked(
        bits: &'a BitArray<[u64; N / 64], Msb0>,
        true_count: usize,
    ) -> Self {
        BitView {
            bits: unsafe { std::mem::transmute(bits) },
            true_count,
        }
    }

    /// Returns the number of `true` bits in the view.
    pub fn true_count(&self) -> usize {
        self.true_count
    }

    /// Runs the provided function `f` for each index of a `true` bit in the view.
    pub fn iter_ones<F>(&self, mut f: F)
    where
        F: FnMut(usize),
    {
        match self.true_count {
            0 => {}
            N => (0..N).for_each(&mut f),
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    while raw != 0 {
                        let bit_pos = raw.trailing_zeros();
                        f(bit_idx + bit_pos as usize);
                        raw &= raw - 1; // Clear the bit at `bit_pos`
                    }
                    bit_idx += 64;
                }
            }
        }
    }

    /// Runs the provided function `f` for each index of a `true` bit in the view.
    pub fn iter_zeros<F>(&self, mut f: F)
    where
        F: FnMut(usize),
    {
        match self.true_count {
            0 => (0..N).for_each(&mut f),
            N => {}
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    while raw != u64::MAX {
                        let bit_pos = raw.trailing_ones();
                        f(bit_idx + bit_pos as usize);
                        raw |= 1u64 << bit_pos; // Set the zero bit to 1
                    }
                    bit_idx += 64;
                }
            }
        }
    }

    /// Runs the provided function `f` for each range of `true` bits in the view.
    ///
    /// The function `f` receives a tuple `(start, len)` where `start` is the index of the first
    /// `true` bit and `len` is the number of consecutive `true` bits.
    pub fn iter_slices<F>(&self, mut f: F)
    where
        F: FnMut((usize, usize)),
    {
        match self.true_count {
            0 => {}
            N => f((0, N)),
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    let mut offset = 0;
                    while raw != 0 {
                        // Skip leading zeros first
                        let zeros = raw.leading_zeros();
                        offset += zeros;
                        raw <<= zeros;

                        if offset >= 64 {
                            break;
                        }

                        // Count leading ones
                        let ones = raw.leading_ones();
                        if ones > 0 {
                            f((bit_idx + offset as usize, ones as usize));
                            offset += ones;
                            raw <<= ones;
                        }
                    }
                    bit_idx += 64; // Move to next word
                }
            }
        }
    }

    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]) }
    }
}

impl<'a> From<&'a [u64; N / 64]> for BitView<'a> {
    fn from(value: &'a [u64; N / 64]) -> Self {
        Self::new(value)
    }
}

impl<'a> From<&'a BitArray<[u64; N / 64], Msb0>> for BitView<'a> {
    fn from(bits: &'a BitArray<[u64; N / 64], Msb0>) -> Self {
        BitView::new(unsafe { std::mem::transmute(bits) })
    }
}

impl<'a> TryFrom<&'a BitSlice<u64, Msb0>> for BitView<'a> {
    type Error = VortexError;

    fn try_from(value: &'a BitSlice<u64, Msb0>) -> Result<Self, Self::Error> {
        let bits: &BitArray<[u64; N / 64], Msb0> = value
            .try_into()
            .map_err(|e| vortex_err!("Failed to convert BitSlice to BitArray: {}", e))?;
        Ok(BitView::new(unsafe { std::mem::transmute(bits) }))
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::fmt::{Debug, Formatter};
5
6	use bitvec::prelude::*;
7	use vortex_error::{VortexError, vortex_err};
8
9	use crate::pipeline::N;
10
11	/// A borrowed fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
12	///
13	/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
14	/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
15	/// it up for use within Vortex.
16	#[derive(Clone, Copy)]
17	pub struct BitView<'a> {
18	bits: &'a BitArray<[u64; N / 64], Msb0>,
19	true_count: usize,
20	}
21
22	impl Debug for BitView<'_> {
NEW 23	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
NEW 24	f.debug_struct("BitView")	×
NEW 25	.field("true_count", &self.true_count)	×
NEW 26	.field("bits", &self.as_raw())	×
NEW 27	.finish()	×
NEW 28	}	×
29	}
30
31	impl BitView<'static> {
NEW 32	pub fn all_true() -> Self {	×
NEW 33	unsafe { BitView::new_unchecked(std::mem::transmute(&[u64::MAX; N / 64]), N) }	×
NEW 34	}	×
35
NEW 36	pub fn all_false() -> Self {	×
NEW 37	unsafe { BitView::new_unchecked(std::mem::transmute(&[0; N / 64]), 0) }	×
NEW 38	}	×
39	}
40
41	impl<'a> BitView<'a> {
NEW 42	pub fn new(bits: &[u64; N / 64]) -> Self {	×
NEW 43	let true_count = bits.iter().map(\|&word\| word.count_ones() as usize).sum();	×
NEW 44	let bits: &BitArray<[u64; N / 64], Msb0> = unsafe { std::mem::transmute(bits) };	×
NEW 45	BitView { bits, true_count }	×
NEW 46	}	×
47
NEW 48	pub(crate) unsafe fn new_unchecked(	×
NEW 49	bits: &'a BitArray<[u64; N / 64], Msb0>,	×
NEW 50	true_count: usize,	×
NEW 51	) -> Self {	×
NEW 52	BitView {	×
NEW 53	bits: unsafe { std::mem::transmute(bits) },	×
NEW 54	true_count,	×
NEW 55	}	×
NEW 56	}	×
57
58	/// Returns the number of `true` bits in the view.
NEW 59	pub fn true_count(&self) -> usize {	×
NEW 60	self.true_count	×
NEW 61	}	×
62
63	/// Runs the provided function `f` for each index of a `true` bit in the view.
NEW 64	pub fn iter_ones<F>(&self, mut f: F)	×
NEW 65	where	×
NEW 66	F: FnMut(usize),	×
67	{
NEW 68	match self.true_count {	×
NEW 69	0 => {}	×
NEW 70	N => (0..N).for_each(&mut f),	×
71	_ => {
NEW 72	let mut bit_idx = 0;	×
NEW 73	for mut raw in self.bits.into_inner() {	×
NEW 74	while raw != 0 {	×
NEW 75	let bit_pos = raw.trailing_zeros();	×
NEW 76	f(bit_idx + bit_pos as usize);	×
NEW 77	raw &= raw - 1; // Clear the bit at `bit_pos`	×
NEW 78	}	×
NEW 79	bit_idx += 64;	×
80	}
81	}
82	}
NEW 83	}	×
84
85	/// Runs the provided function `f` for each index of a `true` bit in the view.
NEW 86	pub fn iter_zeros<F>(&self, mut f: F)	×
NEW 87	where	×
NEW 88	F: FnMut(usize),	×
89	{
NEW 90	match self.true_count {	×
NEW 91	0 => (0..N).for_each(&mut f),	×
NEW 92	N => {}	×
93	_ => {
NEW 94	let mut bit_idx = 0;	×
NEW 95	for mut raw in self.bits.into_inner() {	×
NEW 96	while raw != u64::MAX {	×
NEW 97	let bit_pos = raw.trailing_ones();	×
NEW 98	f(bit_idx + bit_pos as usize);	×
NEW 99	raw \|= 1u64 << bit_pos; // Set the zero bit to 1	×
NEW 100	}	×
NEW 101	bit_idx += 64;	×
102	}
103	}
104	}
NEW 105	}	×
106
107	/// Runs the provided function `f` for each range of `true` bits in the view.
108	///
109	/// The function `f` receives a tuple `(start, len)` where `start` is the index of the first
110	/// `true` bit and `len` is the number of consecutive `true` bits.
NEW 111	pub fn iter_slices<F>(&self, mut f: F)	×
NEW 112	where	×
NEW 113	F: FnMut((usize, usize)),	×
114	{
NEW 115	match self.true_count {	×
NEW 116	0 => {}	×
NEW 117	N => f((0, N)),	×
118	_ => {
NEW 119	let mut bit_idx = 0;	×
NEW 120	for mut raw in self.bits.into_inner() {	×
NEW 121	let mut offset = 0;	×
NEW 122	while raw != 0 {	×
123	// Skip leading zeros first
NEW 124	let zeros = raw.leading_zeros();	×
NEW 125	offset += zeros;	×
NEW 126	raw <<= zeros;	×
127
NEW 128	if offset >= 64 {	×
NEW 129	break;	×
NEW 130	}	×
131
132	// Count leading ones
NEW 133	let ones = raw.leading_ones();	×
NEW 134	if ones > 0 {	×
NEW 135	f((bit_idx + offset as usize, ones as usize));	×
NEW 136	offset += ones;	×
NEW 137	raw <<= ones;	×
NEW 138	}	×
139	}
NEW 140	bit_idx += 64; // Move to next word	×
141	}
142	}
143	}
NEW 144	}	×
145
NEW 146	pub fn as_raw(&self) -> &[u64; N / 64] {	×
147	// It's actually remarkably hard to get a reference to the underlying array!
NEW 148	let raw = self.bits.as_raw_slice();	×
NEW 149	unsafe { &(raw.as_ptr() as const [u64; N / 64]) }	×
NEW 150	}	×
151	}
152
153	impl<'a> From<&'a [u64; N / 64]> for BitView<'a> {
NEW 154	fn from(value: &'a [u64; N / 64]) -> Self {	×
NEW 155	Self::new(value)	×
NEW 156	}	×
157	}
158
159	impl<'a> From<&'a BitArray<[u64; N / 64], Msb0>> for BitView<'a> {
NEW 160	fn from(bits: &'a BitArray<[u64; N / 64], Msb0>) -> Self {	×
NEW 161	BitView::new(unsafe { std::mem::transmute(bits) })	×
NEW 162	}	×
163	}
164
165	impl<'a> TryFrom<&'a BitSlice<u64, Msb0>> for BitView<'a> {
166	type Error = VortexError;
167
NEW 168	fn try_from(value: &'a BitSlice<u64, Msb0>) -> Result<Self, Self::Error> {	×
NEW 169	let bits: &BitArray<[u64; N / 64], Msb0> = value	×
NEW 170	.try_into()	×
NEW 171	.map_err(\|e\| vortex_err!("Failed to convert BitSlice to BitArray: {}", e))?;	×
NEW 172	Ok(BitView::new(unsafe { std::mem::transmute(bits) }))	×
NEW 173	}	×
174	}

vortex-data / vortex / 16969983197

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