Module bit_vec 

Bit vector implementations.

There are two flavors: BitVec, a mutable bit vector, and AtomicBitVec, a mutable, thread-safe bit vector.

Operations on these structures are provided by the extension traits BitVecOps, BitVecOpsMut, and AtomicBitVecOps, which must be pulled in scope as needed. There are also operations that are specific to certain implementations, such as push.

These flavors depend on a backend with a word type W, and presently we provide:

• BitVec<Vec<W>>: a mutable, growable and resizable bit vector;
• BitVec<AsRef<[W]>>: an immutable bit vector, useful for ε-serde support;
• BitVec<AsRef<[W]> + AsMut<[W]>>: a mutable (but not resizable) bit vector;
• AtomicBitVec<AsRef<[Atomic<W>]>>: a thread-safe, mutable (but not resizable) bit vector.

Note that nothing is assumed about the content of the backend outside the bits of the bit vector. Moreover, the content of the backend outside of the bit vector is never modified by the methods of this structure.

It is possible to juggle between all flavors using From/Into, and with TryFrom/TryInto when going from a non-atomic to an atomic bit vector.

Type annotations

Both BitVec and AtomicBitVec have default type parameters for their backends. However, Rust does not apply struct default type parameters in expression position, so constructor calls like BitVec::new(n) or AtomicBitVec::new(n) leave the backend type unconstrained.

The fix is to annotate the binding with the bare type alias, which does apply defaults:

let mut b: BitVec = BitVec::new(10);     // OK: B = Vec<usize>
let a: AtomicBitVec = AtomicBitVec::new(10); // OK: B = Box<[Atomic<usize>]>

The bit_vec! macro and FromIterator / Extend do not need annotations because the word type is determined by the output context.

Examples

use sux::prelude::*;
use sux::traits::bit_vec_ops::*;
use std::sync::atomic::Ordering;

// Convenience macro
let b = bit_vec![0, 1, 0, 1, 1, 0, 1, 0];
assert_eq!(b.len(), 8);
// Not constant time
assert_eq!(b.count_ones(), 4);
assert_eq!(b[0], false);
assert_eq!(b[1], true);
assert_eq!(b[2], false);

let b: AddNumBits<_> = b.into();
// Constant time, but now b is immutable
assert_eq!(b.num_ones(), 4);

let mut b: BitVec = BitVec::new(0);
b.push(true);
b.push(false);
b.push(true);
assert_eq!(b.len(), 3);

// Let's make it atomic
let mut a: AtomicBitVec = b.into();
a.set(1, true, Ordering::Relaxed);
assert!(a.get(0, Ordering::Relaxed));

// Back to normal, but immutable size
let b: BitVec<Vec<usize>> = a.into();
let mut b: BitVec<Box<[usize]>> = b.into();
b.set(2, false);

// If we create an artificially dirty bit vector, everything still works.
let ones = [usize::MAX; 2];
assert_eq!(unsafe { BitVec::from_raw_parts(ones.as_slice(), 1) }.count_ones(), 1);

Structs

AtomicBitVec

A thread-safe bit vector.

BitVec

A bit vector.

BitVecU

A wrapper around BitVec that implements BitVecValueOps using unaligned reads.