Struct RsVec 

pub struct RsVec { /* private fields */ }

A bitvector that supports constant-time rank and select queries and is optimized for fast queries. The bitvector is stored as a vector of u64s. The bit-vector stores meta-data for constant-time rank and select queries, which takes sub-linear additional space. The space overhead is 28 bits per 512 bits of user data (~5.47%).

Example

use vers_vecs::{BitVec, RsVec};

let mut bit_vec = BitVec::new();
bit_vec.append_word(u64::MAX);

let rs_vec = RsVec::from_bit_vec(bit_vec);
assert_eq!(rs_vec.rank1(64), 64);
assert_eq!(rs_vec.select1(64), 64);

Implementations

impl RsVec

pub fn select_iter<const ZERO: bool>(&self) -> SelectIter<'_, ZERO>

Get an iterator over the bits in the vector. The iterator will return the indices of the 0-bits or the 1-bits in the vector, depending on the constant ZERO (if true, 0-bits are returned).

It uses the select data structure to speed up iteration. It is also faster than calling select on each rank, because the iterator exploits the linear access pattern.

This method has convenience methods iter0 and iter1.

pub fn into_select_iter<const ZERO: bool>(self) -> SelectIntoIter<ZERO>

Convert vector into an iterator over the bits in the vector. The iterator will return the indices of the 0-bits or the 1-bits in the vector, depending on the constant ZERO (if true, 0-bits are returned).

It uses the select data structure to speed up iteration. It is also faster than calling select on each rank, because the iterator exploits the linear access pattern.

This method has convenience methods into_iter0 and into_iter1.

pub fn iter0(&self) -> SelectIter<'_, true>

Get an iterator over the 0-bits in the vector that uses the select data structure to speed up iteration. It is faster than calling select0 on each rank, because the iterator exploits the linear access pattern.

See SelectIter for more information.

pub fn iter1(&self) -> SelectIter<'_, false>

Get an iterator over the 1-bits in the vector that uses the select data structure to speed up iteration. It is faster than calling select1 on each rank, because the iterator exploits the linear access pattern.

See SelectIter for more information.

pub fn into_iter0(self) -> SelectIntoIter<true>

Convert vector into an iterator over the 0-bits in the vector that uses the select data structure to speed up iteration. It is faster than calling select0 on each rank, because the iterator exploits the linear access pattern.

See SelectIntoIter for more information.

pub fn into_iter1(self) -> SelectIntoIter<false>

Convert vector into an iterator over the 1-bits in the vector that uses the select data structure to speed up iteration. It is faster than calling select1 on each rank, because the iterator exploits the linear access pattern.

See SelectIntoIter for more information.

impl RsVec

pub fn select0(&self, rank: usize) -> usize

Return the position of the 0-bit with the given rank. See rank0. The following holds for all pos with 0-bits: select0(rank0(pos)) == pos

If the rank is larger than the number of 0-bits in the vector, the vector length is returned.

pub fn select1(&self, rank: usize) -> usize

Return the position of the 1-bit with the given rank. See rank1. The following holds for all pos with 1-bits: select1(rank1(pos)) == pos

If the rank is larger than the number of 1-bits in the bit-vector, the vector length is returned.

pub fn successor0(&self, pos: usize) -> Option<u64>

Returns the position of the next 0-bit after the given index pos. If there is no 0-bit after the given index, None is returned.

The function is in principle equivalent to calling select0(rank0(pos) + 1) (excluding edge cases). However, this method exploits the fact that on average, the position is expected to be near pos. If this assumption is known to be false, calling select0(rank0(pos) + 1) is more efficient.

Example

use vers_vecs::{BitVec, RsVec};

let mut bv = BitVec::from_ones(8);
bv.flip_bit(1);
bv.flip_bit(4);
let rs = RsVec::from(bv);

assert_eq!(rs.successor0(0), Some(1));
assert_eq!(rs.successor0(1), Some(4));
assert_eq!(rs.successor0(4), None);

pub fn successor1(&self, pos: usize) -> Option<u64>

Returns the position of the next 1-bit after the given index pos. If there is no 1-bit after the given index, None is returned.

The function is in principle equivalent to calling select1(rank1(pos) + 1) (excluding edge cases). However, this method exploits the fact that on average, the position is expected to be near pos. If this assumption is known to be false, calling select1(rank1(pos) + 1) is more efficient.

Example

use vers_vecs::{BitVec, RsVec};

let mut bv = BitVec::from_zeros(8);
bv.flip_bit(1);
bv.flip_bit(4);
let rs = RsVec::from(bv);

assert_eq!(rs.successor1(0), Some(1));
assert_eq!(rs.successor1(1), Some(4));
assert_eq!(rs.successor1(4), None);

pub fn predecessor0(&self, pos: usize) -> Option<u64>

Returns the position of the last 0-bit before the given index pos. If there is no 0-bit before the given index, None is returned.

The function is in principle equivalent to calling select0(rank0(pos) - 1) (excluding edge cases). However, this method exploits the fact that on average, the position is expected to be near pos. If this assumption is known to be false, calling select0(rank0(pos) - 1) is more efficient.

Example

use vers_vecs::{BitVec, RsVec};

let mut bv = BitVec::from_ones(8);
bv.flip_bit(1);
bv.flip_bit(4);
let rs = RsVec::from(bv);

assert_eq!(rs.predecessor0(5), Some(4));
assert_eq!(rs.predecessor0(4), Some(1));
assert_eq!(rs.predecessor0(1), None);

pub fn predecessor1(&self, pos: usize) -> Option<u64>

Returns the position of the last 1-bit before the given index pos. If there is no 1-bit before the given index, None is returned.

The function is in principle equivalent to calling select1(rank1(pos) - 1) (excluding edge cases). However, this method exploits the fact that on average, the position is expected to be near pos. If this assumption is known to be false, calling select1(rank1(pos) - 1) is more efficient.

Example

use vers_vecs::{BitVec, RsVec};

let mut bv = BitVec::from_zeros(8);
bv.flip_bit(1);
bv.flip_bit(4);
let rs = RsVec::from(bv);

assert_eq!(rs.predecessor1(5), Some(4));
assert_eq!(rs.predecessor1(4), Some(1));
assert_eq!(rs.predecessor1(1), None);

impl RsVec

pub fn bit_set_iter0(&self) -> BitSetIter<'_, true>

Available on x86-64 and target feature avx2 and target feature avx512bw and target feature avx512f and target feature avx and crate feature simd only.

Get an iterator over the 0-bits in the vector. The iterator returns the indices of the 0-bits in the vector, just as iter0 and select0 do.

This method is faster than iter0 for dense vectors, but slower for sparse vectors.

See BitSetIter for more information.

pub fn bit_set_iter1(&self) -> BitSetIter<'_, false>

Available on x86-64 and target feature avx2 and target feature avx512bw and target feature avx512f and target feature avx and crate feature simd only.

Get an iterator over the 1-bits in the vector. The iterator returns the indices of the 1-bits in the vector, just as iter1 and select1 do.

This method is faster than iter1 for dense vectors, but slower for sparse vectors.

See BitSetIter for more information.

impl RsVec

pub fn from_bit_vec(vec: BitVec) -> RsVec

Build an RsVec from a BitVec. This will consume the BitVec. Since RsVecs are immutable, this is the only way to construct an RsVec.

Example

See the example for RsVec.

pub fn rank0(&self, pos: usize) -> usize

Return the 0-rank of the bit at the given position. The 0-rank is the number of 0-bits in the vector up to but excluding the bit at the given position. Calling this function with an index larger than the length of the bit-vector will report the total number of 0-bits in the bit-vector.

Parameters

• pos: The position of the bit to return the rank of.

pub fn rank1(&self, pos: usize) -> usize

Return the 1-rank of the bit at the given position. The 1-rank is the number of 1-bits in the vector up to but excluding the bit at the given position. Calling this function with an index larger than the length of the bit-vector will report the total number of 1-bits in the bit-vector.

Parameters

• pos: The position of the bit to return the rank of.

pub fn len(&self) -> usize

Return the length of the vector, i.e. the number of bits it contains.

pub fn is_empty(&self) -> bool

Return whether the vector is empty.

pub fn get(&self, pos: usize) -> Option<u64>

Return the bit at the given position. The bit takes the least significant bit of the returned u64 word. If the position is larger than the length of the vector, None is returned.

pub fn get_unchecked(&self, pos: usize) -> u64

Return the bit at the given position. The bit takes the least significant bit of the returned u64 word.

Panics

This function may panic if pos >= self.len() (alternatively, it may return garbage).

pub fn get_bits(&self, pos: usize, len: usize) -> Option<u64>

Return multiple bits at the given position. The number of bits to return is given by len. At most 64 bits can be returned. If the position at the end of the query is larger than the length of the vector, None is returned (even if the query partially overlaps with the vector). If the length of the query is larger than 64, None is returned.

pub fn get_bits_unchecked(&self, pos: usize, len: usize) -> u64

Return multiple bits at the given position. The number of bits to return is given by len. At most 64 bits can be returned.

This function is always inlined, because it gains a lot from loop optimization and can utilize the processor pre-fetcher better if it is.

Errors

If the length of the query is larger than 64, unpredictable data will be returned. Use get_bits to properly handle this case with an Option.

Panics

If the position or interval is larger than the length of the vector, the function will either return unpredictable data, or panic.

pub fn into_bit_vec(self) -> BitVec

Convert the RsVec into a BitVec. This consumes the RsVec, and discards all meta-data. Since RsVecs are innately immutable, this conversion is the only way to modify the underlying data.

Example

use vers_vecs::{BitVec, RsVec};

let mut bit_vec = BitVec::new();
bit_vec.append_word(u64::MAX);

let rs_vec = RsVec::from_bit_vec(bit_vec);
assert_eq!(rs_vec.rank1(64), 64);

let mut bit_vec = rs_vec.into_bit_vec();
bit_vec.flip_bit(32);
let rs_vec = RsVec::from_bit_vec(bit_vec);
assert_eq!(rs_vec.rank1(64), 63);
assert_eq!(rs_vec.select0(0), 32);

pub fn sparse_equals<const ZERO: bool>(&self, other: &Self) -> bool

Check if two RsVecs are equal. For sparse vectors (either sparsely filled with 1-bits or 0-bits), this is faster than comparing the vectors bit by bit. Choose the value of ZERO depending on which bits are more sparse.

This method is faster than full_equals for sparse vectors beginning at roughly 1 million bits. Above 4 million bits, this method becomes faster than full equality in general.

Parameters

• other: The other RsVec to compare to.
• ZERO: Whether to compare the sparse 0-bits (true) or the sparse 1-bits (false).

Returns

true if the vectors’ contents are equal, false otherwise.

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

Check if two RsVecs are equal. This compares limb by limb. This is usually faster than a sparse_equals call for small vectors.

Parameters

• other: The other RsVec to compare to.

Returns

true if the vectors’ contents are equal, false otherwise.

pub fn heap_size(&self) -> usize

Returns the number of bytes used on the heap for this vector. This does not include allocated space that is not used (e.g. by the allocation behavior of Vec).

impl RsVec

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

Returns an iterator over the elements of RsVec. The iterator returns u64 elements.

Trait Implementations

impl Clone for RsVec

fn clone(&self) -> RsVec

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for RsVec

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for RsVec

Available on crate feature serde only.

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl FlatType for RsVec

where Vec<u64>: MemSize + FlatType, usize: MemSize + FlatType, Vec<BlockDescriptor>: MemSize + FlatType, Vec<SuperBlockDescriptor>: MemSize + FlatType, Vec<SelectSuperBlockDescriptor>: MemSize + FlatType,

Available on crate feature mem_dbg only.

type Flat = False

Whether the type is flat (True) or not (False).

impl From<BitVec> for RsVec

fn from(vec: BitVec) -> Self

Build an RsVec from a BitVec. This will consume the BitVec. Since RsVecs are immutable, this is the only way to construct an RsVec.

Example

See the example for RsVec.

impl<const BLOCK_SIZE: usize> From<BpTree<BLOCK_SIZE>> for RsVec

fn from(value: BpTree<BLOCK_SIZE>) -> Self

Converts to this type from the input type.

impl From<RsVec> for BitVec

fn from(value: RsVec) -> Self

Converts to this type from the input type.

impl IntoIterator for RsVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = RsVecIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a> IntoIterator for &'a RsVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = RsVecRefIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a> IntoIterator for &'a mut RsVec

type Item = u64

The type of the elements being iterated over.

type IntoIter = RsVecRefIter<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl MemDbgImpl for RsVec

where Vec<u64>: MemDbgImpl + FlatType, usize: MemDbgImpl + FlatType, Vec<BlockDescriptor>: MemDbgImpl + FlatType, Vec<SuperBlockDescriptor>: MemDbgImpl + FlatType, Vec<SelectSuperBlockDescriptor>: MemDbgImpl + FlatType,

Available on crate feature mem_dbg only.

fn _mem_dbg_rec_on( &self, _memdbg_writer: &mut impl Write, _memdbg_total_size: usize, _memdbg_max_depth: usize, _memdbg_prefix: &mut String, _memdbg_is_last: bool, _memdbg_flags: DbgFlags, _memdbg_refs: &mut HashSet<usize>, ) -> Result

Recursively displays the fields of self below the current line.

fn _mem_dbg_depth_on( &self, writer: &mut impl Write, total_size: usize, max_depth: usize, prefix: &mut String, field_name: Option<&str>, is_last: bool, padded_size: usize, flags: DbgFlags, dbg_refs: &mut HashSet<usize>, ) -> Result<(), Error>

Displays self at the given depth without any reference-address annotation; forwards to _mem_dbg_depth_on_impl with RefDisplay::None.

fn _mem_dbg_depth_on_impl( &self, writer: &mut impl Write, total_size: usize, max_depth: usize, prefix: &mut String, field_name: Option<&str>, is_last: bool, padded_size: usize, flags: DbgFlags, dbg_refs: &mut HashSet<usize>, ref_display: RefDisplay, ) -> Result<(), Error>

Internal implementation for depth display.

impl MemSize for RsVec

where Vec<u64>: MemSize + FlatType, usize: MemSize + FlatType, Vec<BlockDescriptor>: MemSize + FlatType, Vec<SuperBlockDescriptor>: MemSize + FlatType, Vec<SelectSuperBlockDescriptor>: MemSize + FlatType,

Available on crate feature mem_dbg only.

fn mem_size_rec( &self, _memsize_flags: SizeFlags, _memsize_refs: &mut HashMap<usize, usize>, ) -> usize

Recursive implementation that tracks visited references for deduplication.

fn mem_size(&self, flags: SizeFlags) -> usize

Returns the (recursively computed) overall memory size of the structure in bytes.

impl PartialEq for RsVec

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

Check if two RsVecs are equal. This method calls sparse_equals if the vector has more than 4’000’000 bits, and full_equals otherwise.

This was determined with benchmarks on an x86_64 machine, on which sparse_equals outperforms full_equals consistently above this threshold.

Parameters

• other: The other RsVec to compare to.

Returns

true if the vectors’ contents are equal, false otherwise.

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

Inequality operator !=.

impl Serialize for RsVec

Available on crate feature serde only.

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.