Struct Bitmap

pub struct Bitmap {
    num_bits: usize,
    count_ones: usize,
    bits: Option<Box<[usize]>>,
}

An immutable bitmap. Use BitmapBuilder to build it.

Fields

num_bits: usize

The useful bits in the bitmap. The total number of bits will usually be larger than the useful bits due to byte-padding.

count_ones: usize

The number of high bits in the bitmap.

bits: Option<Box<[usize]>>

Bits are stored in a compact form. They are packed into usizes.

Optimization: If all bits are set to 0 or 1, this field MUST be None.

Implementations

impl Bitmap

pub fn zeros(num_bits: usize) -> Self

Creates a new bitmap with all bits set to 0.

pub fn ones(num_bits: usize) -> Self

Creates a new bitmap with all bits set to 1.

fn from_vec_with_len(buf: Vec<usize>, num_bits: usize) -> Self

Creates a new bitmap from vector.

pub fn from_bytes(buf: &[u8]) -> Self

Creates a new bitmap from bytes.

fn from_bytes_with_len(buf: &[u8], num_bits: usize) -> Self

Creates a new bitmap from bytes and length.

pub fn from_bool_slice(bools: &[bool]) -> Self

Creates a new bitmap from a slice of bool.

pub fn next_set_bit(&self, bit_idx: usize) -> Option<usize>

Return the next set bit index on or after bit_idx.

pub fn count_ones(&self) -> usize

Counts the number of bits set to 1.

pub fn any(&self) -> bool

Returns true if any bit is set to 1.

fn vec_len(num_bits: usize) -> usize

Returns the length of vector to store num_bits bits.

pub fn len(&self) -> usize

Returns the number of valid bits in the bitmap, also referred to its ‘length’.

pub fn is_empty(&self) -> bool

Returns true if the Bitmap has a length of 0.

pub unsafe fn is_set_unchecked(&self, idx: usize) -> bool

Returns true if the bit at idx is set, without doing bounds checking.

Safety

Index must be in range.

pub fn is_set(&self, idx: usize) -> bool

Returns true if the bit at idx is set.

pub fn all(&self) -> bool

Tests if every bit is set to 1.

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

Produces an iterator over each bit.

pub fn iter_ones(&self) -> BitmapOnesIter<'_>

Enumerates the index of each bit set to 1.

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

Returns an iterator which yields the position ranges of continuous high bits.

pub fn from_range(num_bits: usize, range: Range<usize>) -> Self

Creates a new bitmap with all bits in range set to 1.

Example

use risingwave_common::bitmap::Bitmap;
let bitmap = Bitmap::from_range(200, 100..180);
assert_eq!(bitmap.count_ones(), 80);
for i in 0..200 {
    assert_eq!(bitmap.is_set(i), i >= 100 && i < 180);
}

impl Bitmap

pub fn to_protobuf(&self) -> PbBuffer

Trait Implementations

impl<'b> BitAnd<&'b Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: &'b Bitmap) -> Bitmap

Performs the & operation.

impl<'b> BitAnd<&'b Bitmap> for Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: &'b Bitmap) -> Self::Output

Performs the & operation.

impl BitAnd<Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: Bitmap) -> Self::Output

Performs the & operation.

impl BitAnd for Bitmap

type Output = Bitmap

The resulting type after applying the & operator.

fn bitand(self, rhs: Bitmap) -> Self::Output

Performs the & operation.

impl BitAndAssign<&Bitmap> for Bitmap

fn bitand_assign(&mut self, rhs: &Bitmap)

Performs the &= operation.

impl BitAndAssign for Bitmap

fn bitand_assign(&mut self, rhs: Bitmap)

Performs the &= operation.

impl<'b> BitOr<&'b Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the | operator.

fn bitor(self, rhs: &'b Bitmap) -> Bitmap

Performs the | operation.

impl<'b> BitOr<&'b Bitmap> for Bitmap

type Output = Bitmap

The resulting type after applying the | operator.

fn bitor(self, rhs: &'b Bitmap) -> Self::Output

Performs the | operation.

impl BitOr<Bitmap> for &Bitmap

type Output = Bitmap

The resulting type after applying the | operator.

fn bitor(self, rhs: Bitmap) -> Self::Output

Performs the | operation.

impl BitOr for Bitmap

type Output = Bitmap

The resulting type after applying the | operator.

fn bitor(self, rhs: Bitmap) -> Self::Output

Performs the | operation.

impl BitOrAssign<&Bitmap> for Bitmap

fn bitor_assign(&mut self, rhs: &Bitmap)

Performs the |= operation.

impl BitOrAssign for Bitmap

fn bitor_assign(&mut self, rhs: Bitmap)

Performs the |= operation.

impl BitXor for &Bitmap

type Output = Bitmap

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: &Bitmap) -> Self::Output

Performs the ^ operation.

impl Clone for Bitmap

fn clone(&self) -> Bitmap

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Bitmap

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

Formats the value using the given formatter.

impl EstimateSize for Bitmap

fn estimated_heap_size(&self) -> usize

The estimated heap size of the current struct in bytes.

fn estimated_size(&self) -> usize

where Self: Sized,

The estimated total size of the current struct in bytes, including the estimated_heap_size and the size of Self.

impl From<&Bitmap> for NullBuffer

fn from(bitmap: &Bitmap) -> Self

Converts to this type from the input type.

impl From<&Bitmap> for NullBuffer

fn from(bitmap: &Bitmap) -> Self

Converts to this type from the input type.

impl From<&Buffer> for Bitmap

fn from(buf: &PbBuffer) -> Self

Converts to this type from the input type.

impl From<Bitmap> for BitmapBuilder

fn from(bitmap: Bitmap) -> Self

Converts to this type from the input type.

impl From<Buffer> for Bitmap

fn from(buf: PbBuffer) -> Self

Converts to this type from the input type.

impl From<usize> for Bitmap

fn from(val: usize) -> Self

Converts to this type from the input type.

impl FromIterator<Option<bool>> for Bitmap

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

Creates a value from an iterator.

impl FromIterator<bool> for Bitmap

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

Creates a value from an iterator.

impl Not for &Bitmap

type Output = Bitmap

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl Not for Bitmap

type Output = Bitmap

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl PartialEq for Bitmap

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl VnodeBitmapExt for Bitmap

fn iter_vnodes(&self) -> impl Iterator<Item = VirtualNode> + '_

Enumerates the virtual nodes set to 1 in the bitmap.

fn iter_vnodes_scalar(&self) -> impl Iterator<Item = i16> + '_

Enumerates the virtual nodes set to 1 in the bitmap.

fn vnode_ranges(&self) -> impl Iterator<Item = RangeInclusive<VirtualNode>> + '_

Returns an iterator which yields the position ranges of continuous virtual nodes set to 1 in the bitmap.

fn is_singleton(&self) -> bool

Returns whether only the SINGLETON_VNODE is set in the bitmap.

fn singleton() -> &'static Self

Get the reference to a vnode bitmap for singleton actor or table, i.e., with length 1 and the only SINGLETON_VNODE set to true.

fn singleton_arc() -> &'static Arc<Self>

Get the reference to a vnode bitmap for singleton actor or table, i.e., with length 1 and the only SINGLETON_VNODE set to true.

impl Eq for Bitmap

impl StructuralPartialEq for Bitmap