Skip to main content

Bitmap

Struct Bitmap 

Source
pub struct Bitmap { /* private fields */ }
Expand description

An immutable, LSB-numbered bit sequence over a shared Buffer.

Used as the validity map of every nullable array and as the value buffer of crate::array::BooleanArray.

The set-bit count is computed lazily and cached in an atomic, so count_set is O(len / 64) once and O(1) afterwards, while the type stays Send + Sync with no locks.

Implementations§

Source§

impl Bitmap

Source

pub fn try_new(buffer: Buffer, offset: usize, len: usize) -> Result<Self>

Wraps a byte window as a bitmap.

§Errors

DataError::BufferTooSmall when the buffer cannot cover offset + len bits.

use astrs_data::{Bitmap, Buffer};

let bits = Bitmap::try_new(Buffer::from_slice(&[0b1010_1010]), 1, 7)?;
assert_eq!(bits.len(), 7);
assert!(bits.value(0));
assert!(Bitmap::try_new(Buffer::from_slice(&[0]), 0, 9).is_err());
Source

pub fn from_buffer(buffer: Buffer) -> Self

Wraps a byte window, using every bit it holds.

use astrs_data::{Bitmap, Buffer};

assert_eq!(Bitmap::from_buffer(Buffer::from_slice(&[0, 0])).len(), 16);
Source

pub fn new_set(len: usize) -> Self

An all-valid bitmap of len bits.

Source

pub fn new_unset(len: usize) -> Self

An all-null bitmap of len bits.

Source

pub const fn len(&self) -> usize

Number of logical bits.

Source

pub const fn is_empty(&self) -> bool

Returns true when the bitmap covers no bits.

Source

pub const fn bit_offset(&self) -> usize

Logical bit offset of the first bit inside the backing buffer.

Source

pub const fn buffer(&self) -> &Buffer

The backing byte window.

Source

pub fn get(&self, index: usize) -> Option<bool>

Reads bit index, returning None when out of range.

Source

pub fn value(&self, index: usize) -> bool

Reads bit index, treating out-of-range indices as false.

This is the hot accessor used by every array’s is_valid.

Source

pub fn count_set(&self) -> usize

Number of set (valid) bits. Computed once, then cached.

use astrs_data::Bitmap;

let bits: Bitmap = [true, false, true].into_iter().collect();
assert_eq!(bits.count_set(), 2);
assert_eq!(bits.count_unset(), 1);
Source

pub fn count_unset(&self) -> usize

Number of unset (null) bits.

Source

pub fn all_set(&self) -> bool

Returns true when every bit is set.

Source

pub fn none_set(&self) -> bool

Returns true when no bit is set.

Source

pub fn slice(&self, offset: usize, len: usize) -> Self

A zero-copy sub-range, clamped to the available range (the crate-wide slicing convention).

use astrs_data::Bitmap;

let bits: Bitmap = (0..20).map(|i| i % 3 == 0).collect();
let window = bits.slice(5, 5);
assert_eq!(window.iter().collect::<Vec<_>>(), vec![false, true, false, false, true]);
assert_eq!(bits.slice(18, 99).len(), 2, "slices clamp");
Source

pub fn try_slice(&self, offset: usize, len: usize) -> Result<Self>

Checked Bitmap::slice.

Source

pub fn iter(&self) -> BitmapIter<'_> ⓘ

Iterates over the bits, low index first.

Source

pub fn set_indices(&self) -> impl Iterator<Item = usize> + '_

Iterates over the indices of the set bits.

use astrs_data::Bitmap;

let bits: Bitmap = [false, true, false, true].into_iter().collect();
assert_eq!(bits.set_indices().collect::<Vec<_>>(), vec![1, 3]);
Source

pub fn unset_indices(&self) -> impl Iterator<Item = usize> + '_

Iterates over the indices of the unset (null) bits.

Source

pub fn to_canonical(&self) -> Self

Copies the bits into a fresh, zero-offset, tightly packed bitmap.

Stage 2 needs this before writing a validity buffer into an IPC body: the wire format has no bit-offset field.

use astrs_data::Bitmap;

let bits: Bitmap = (0..20).map(|i| i % 2 == 0).collect();
let window = bits.slice(3, 9);
let packed = window.to_canonical();
assert_eq!(packed.bit_offset(), 0);
assert_eq!(packed.iter().collect::<Vec<_>>(), window.iter().collect::<Vec<_>>());
Source

pub fn and(&self, other: &Self) -> Result<Self>

Bitwise AND of two equal-length bitmaps.

This is how a parent’s validity is pushed into a child’s: a value is valid only when both maps say so. Operand bit offsets may differ.

§Errors

DataError::BitmapLengthMismatch when the lengths differ.

use astrs_data::Bitmap;

let a: Bitmap = [true, true, false, false].into_iter().collect();
let b: Bitmap = [true, false, true, false].into_iter().collect();
assert_eq!(a.and(&b)?.iter().collect::<Vec<_>>(), vec![true, false, false, false]);
Source

pub fn or(&self, other: &Self) -> Result<Self>

Bitwise OR of two equal-length bitmaps.

§Errors

DataError::BitmapLengthMismatch when the lengths differ.

Source

pub fn xor(&self, other: &Self) -> Result<Self>

Bitwise XOR of two equal-length bitmaps.

§Errors

DataError::BitmapLengthMismatch when the lengths differ.

Source

pub fn not(&self) -> Self

Bitwise NOT.

use astrs_data::Bitmap;

let bits: Bitmap = [true, false, true].into_iter().collect();
assert_eq!(bits.not().iter().collect::<Vec<_>>(), vec![false, true, false]);
Source

pub fn intersect( left: Option<&Self>, right: Option<&Self>, ) -> Result<Option<Self>>

Combines two optional validity maps the way nested arrays need.

None means “everything valid”, so the result is None only when both inputs are None.

§Errors

DataError::BitmapLengthMismatch when both are present with different lengths.

use astrs_data::Bitmap;

let a: Bitmap = [true, false].into_iter().collect();
assert!(Bitmap::intersect(None, None)?.is_none());
assert_eq!(Bitmap::intersect(Some(&a), None)?, Some(a));
Source

pub fn repeat_each(&self, factor: usize) -> Self

Expands the bitmap so each bit is repeated factor times.

FixedSizeList uses this to push a parent’s validity down onto the child values it covers.

use astrs_data::Bitmap;

let parent: Bitmap = [true, false].into_iter().collect();
let child = parent.repeat_each(3);
assert_eq!(child.iter().collect::<Vec<_>>(), vec![true, true, true, false, false, false]);

Trait Implementations§

Source§

impl Clone for Bitmap

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for Bitmap

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Eq for Bitmap

Source§

impl FromIterator<bool> for Bitmap

Source§

fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self

Creates a value from an iterator. Read more
Source§

impl Hash for Bitmap

Source§

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
Source§

impl<'a> IntoIterator for &'a Bitmap

Source§

type Item = bool

The type of the elements being iterated over.
Source§

type IntoIter = BitmapIter<'a>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> BitmapIter<'a> ⓘ

Creates an iterator from a value. Read more
Source§

impl PartialEq for Bitmap

Source§

fn eq(&self, other: &Self) -> bool

Compares logical bits, so two bitmaps at different offsets over different buffers compare equal when their bit sequences match.

1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.