Struct bitvec::vec::BitVec

source ·

#[repr(C)]
pub struct BitVec<T = usize, O = Lsb0>where
    T: BitStore,
    O: BitOrder,{ /* private fields */ }

Expand description

Bit-Precision Dynamic Array

This is an analogue to Vec<bool> that stores its data using a compaction scheme to ensure that each bool takes exactly one bit of memory. It is similar to the C++ type std::vector<bool>, but uses bitvec’s type parameter system to provide more detailed control over the in-memory representation.

This is always a heap allocation. If you know your sizes at compile-time, you may prefer to use BitArray instead, which is able to store its data as an immediate value rather than through an indirection.

Documentation Practices

BitVec exactly replicates the API of the standard-library Vec type, including inherent methods, trait implementations, and relationships with the BitSlice slice analogue.

Items that are either direct ports, or renamed variants, of standard-library APIs will have a ## Original section that links to their standard-library documentation. Items that map to standard-library APIs but have a different API signature will also have an ## API Differences section that describes what the difference is, why it exists, and how to transform your code to fit it. For example:

Original

Vec<T>

API Differences

As with all bitvec data structures, this takes two type parameters <T, O> that govern the bit-vector’s storage representation in the underlying memory, and does not take a type parameter to govern what data type it stores (always bool)

Suggested Uses

BitVec is able to act as a compacted usize => bool dictionary, and is useful for holding large collections of truthiness. For instance, you might replace a Vec<Option<T>> with a (BitVec, Vec<MaybeUninit<T>>) to cut down on the resident size of the discriminant.

Through the BitField trait, BitVec is also able to act as a transport buffer for data that can be marshalled as integers. Serializing data to a narrower compacted form, or deserializing data from that form, can be easily accomplished by viewing subsets of a bit-vector and storing integers into, or loading integers out of, that subset. As an example, transporting four ten-bit integers can be done in five bytes instead of eight like so:

use bitvec::prelude::*;

let mut bv = bitvec![u8, Msb0; 0; 40];
bv[0 .. 10].store::<u16>(0x3A8);
bv[10 .. 20].store::<u16>(0x2F9);
bv[20 .. 30].store::<u16>(0x154);
bv[30 .. 40].store::<u16>(0x06D);

If you wish to use bit-field memory representations as struct fields rather than a transport buffer, consider BitArray instead: that type keeps its data as an immediate, and is more likely to act like a C struct with bitfields.

Examples

BitVec has exactly the same API as Vec<bool>, and even extends it with some of Vec<T>’s behaviors. As a brief tour:

Push and Pop

use bitvec::prelude::*;

let mut bv: BitVec = BitVec::new();
bv.push(false);
bv.push(true);

assert_eq!(bv.len(), 2);
assert_eq!(bv[0], false);

assert_eq!(bv.pop(), Some(true));
assert_eq!(bv.len(), 1);

Writing Into a Bit-Vector

The only Vec<bool> API that BitVec does not implement is IndexMut, because that is not yet possible. Instead, .get_mut() can produce a proxy reference, or .set() can take an index and a value to write.

use bitvec::prelude::*;

let mut bv: BitVec = BitVec::new();
bv.push(false);

*bv.get_mut(0).unwrap() = true;
assert!(bv[0]);
bv.set(0, false);
assert!(!bv[0]);

Macro Construction

Like Vec, BitVec also has a macro constructor: bitvec! takes a sequence of bit expressions and encodes them at compile-time into a suitable buffer. At run-time, this buffer is copied into the heap as a BitVec with no extra cost beyond the allocation.

use bitvec::prelude::*;

let bv = bitvec![0; 10];
let bv = bitvec![0, 1, 0, 0, 1];
let bv = bitvec![u16, Msb0; 1; 20];

Borrowing as `BitSlice`

BitVec lends its buffer as a BitSlice, so you can freely give permission to view or modify the contained data without affecting the allocation:

use bitvec::prelude::*;

fn read_bitslice(bits: &BitSlice) {
  // …
}

let bv = bitvec![0; 30];
read_bitslice(&bv);
let bs: &BitSlice = &bv;

Other Notes

The default type parameters are <usize, Lsb0>. This is the most performant pair when operating on memory, but likely does not match your needs if you are using BitVec to represent a transport buffer. See the user guide for more details on how the type parameters govern memory representation.

Applications, or single-purpose libraries, built atop bitvec will likely want to create a type alias with specific type parameters for their usage. bitvec is fully generic over the ordering/storage types, but this generality is rarely useful for client crates to propagate. <usize, Lsb0> is fastest; <u8, Msb0> matches what most debugger views of memory will print, and the rest are documented in the guide.

Safety

Unlike the other data structures in this crate, BitVec is uniquely able to hold uninitialized memory and produce pointers into it. As described in the BitAccess documentation, this crate is categorically unable to operate on uninitialized memory in any way. In particular, you may not allocate a buffer using ::with_capacity(), then use .as_mut_bitptr() to create a pointer used to write into the uninitialized buffer.

You must always initialize the buffer contents of a BitVec before attempting to view its contents. You can accomplish this through safe APIs such as .push(), .extend(), or .reserve(). These are all guaranteed to safely initialize the memory elements underlying the BitVec buffer without incurring undefined behavior in their operation.

Struct bitvec::vec::BitVec

Implementations§

impl<T, O> BitVec<T, O>where T: BitStore, O: BitOrder,

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

pub unsafe fn from_raw_parts( bitptr: BitPtr<Mut, T, O>, length: usize, capacity: usize ) -> Self

pub fn into_raw_parts(self) -> (BitPtr<Mut, T, O>, usize, usize)

pub fn capacity(&self) -> usize

pub fn reserve(&mut self, additional: usize)

pub fn reserve_exact(&mut self, additional: usize)

pub fn shrink_to_fit(&mut self)

pub fn into_boxed_slice(self) -> BitBox<T, O>

pub fn truncate(&mut self, new_len: usize)

pub fn as_slice(&self) -> &BitSlice<T, O> ⓘ

pub fn as_mut_slice(&mut self) -> &mut BitSlice<T, O> ⓘ

pub fn as_ptr(&self) -> BitPtr<Const, T, O>

pub fn as_mut_ptr(&mut self) -> BitPtr<Mut, T, O>

pub unsafe fn set_len(&mut self, new_len: usize)

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

pub fn insert(&mut self, index: usize, value: bool)

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

pub fn retain<F>(&mut self, func: F)where F: FnMut(usize, &bool) -> bool,

pub fn push(&mut self, value: bool)

pub fn pop(&mut self) -> Option<bool>

pub fn append<T2, O2>(&mut self, other: &mut BitVec<T2, O2>)where T2: BitStore, O2: BitOrder,

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, O> ⓘwhere R: RangeBounds<usize>,

pub fn clear(&mut self)

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn split_off(&mut self, at: usize) -> Self

pub fn resize_with<F>(&mut self, new_len: usize, func: F)where F: FnMut(usize) -> bool,

pub fn leak<'a>(self) -> &'a mut BitSlice<T, O> ⓘ

pub fn resize(&mut self, new_len: usize, value: bool)

pub fn extend_from_slice<T2, O2>(&mut self, other: &BitSlice<T2, O2>)where T2: BitStore, O2: BitOrder,

pub fn extend_from_within<R>(&mut self, src: R)where R: RangeExt<usize>,

pub fn splice<R, I>( &mut self, range: R, replace_with: I ) -> Splice<'_, T, O, I::IntoIter> ⓘwhere R: RangeBounds<usize>, I: IntoIterator<Item = bool>,

impl<T, O> BitVec<T, O>where T: BitStore, O: BitOrder,

pub const EMPTY: Self = _

pub fn repeat(bit: bool, len: usize) -> Self

pub fn from_bitslice(slice: &BitSlice<T, O>) -> Self

pub fn from_element(elem: T) -> Self

pub fn from_slice(slice: &[T]) -> Self

pub fn try_from_slice(slice: &[T]) -> Result<Self, BitSpanError<T>>

pub fn from_vec(vec: Vec<T>) -> Self

pub fn try_from_vec(vec: Vec<T>) -> Result<Self, Vec<T>>

pub fn extend_from_bitslice<T2, O2>(&mut self, other: &BitSlice<T2, O2>)where T2: BitStore, O2: BitOrder,

pub fn extend_from_raw_slice(&mut self, slice: &[T])

impl<T, O> BitVec<T, O>where T: BitStore, O: BitOrder,

pub fn as_bitslice(&self) -> &BitSlice<T, O> ⓘ

pub fn as_mut_bitslice(&mut self) -> &mut BitSlice<T, O> ⓘ