bitvec/

vec.rs

#![doc = include_str!("../doc/vec.md")]
#![cfg(feature = "alloc")]

#[cfg(not(feature = "std"))]
use alloc::vec;
use alloc::vec::Vec;
use core::{
	mem::{
		self,
		ManuallyDrop,
	},
	ptr,
	slice,
};

use tap::Pipe;
use wyz::comu::{
	Const,
	Mut,
};

pub use self::iter::{
	Drain,
	Splice,
};
pub use crate::boxed::IntoIter;
use crate::{
	boxed::BitBox,
	index::BitIdx,
	mem::bits_of,
	order::{
		BitOrder,
		Lsb0,
	},
	ptr::{
		AddressExt,
		BitPtr,
		BitSpan,
		BitSpanError,
	},
	slice::BitSlice,
	store::BitStore,
	view::BitView,
};

mod api;
mod iter;
mod ops;
mod tests;
mod traits;

#[repr(C)]
#[doc = include_str!("../doc/vec/BitVec.md")]
pub struct BitVec<T = usize, O = Lsb0>
where
	T: BitStore,
	O: BitOrder,
{
	/// Span description of the live bits in the allocation.
	bitspan:  BitSpan<Mut, T, O>,
	/// Allocation capacity, measured in `T` elements.
	capacity: usize,
}

/// Constructors.
impl<T, O> BitVec<T, O>
where
	T: BitStore,
	O: BitOrder,
{
	/// An empty bit-vector with no backing allocation.
	pub const EMPTY: Self = Self {
		bitspan:  BitSpan::EMPTY,
		capacity: 0,
	};

	/// Creates a new bit-vector by repeating a bit for the desired length.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let zeros = BitVec::<u8, Msb0>::repeat(false, 50);
	/// let ones = BitVec::<u16, Lsb0>::repeat(true, 50);
	/// ```
	#[inline]
	pub fn repeat(bit: bool, len: usize) -> Self {
		let mut out = Self::with_capacity(len);
		unsafe {
			out.set_len(len);
			out.as_raw_mut_slice().fill_with(|| {
				BitStore::new(if bit { !<T::Mem>::ZERO } else { <T::Mem>::ZERO })
			});
		}
		out
	}

	/// Copies the contents of a bit-slice into a new heap allocation.
	///
	/// This copies the raw underlying elements into a new allocation, and sets
	/// the produced bit-vector to use the same memory layout as the originating
	/// bit-slice. This means that it may begin at any bit in the first element,
	/// not just the zeroth bit. If you require this property, call
	/// [`.force_align()`].
	///
	/// Dead bits in the copied memory elements are guaranteed to be zeroed.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bits = bits![0, 1, 0, 0, 1];
	/// let bv = BitVec::from_bitslice(bits);
	/// assert_eq!(bv, bits);
	/// ```
	///
	/// [`.force_align()`]: Self::force_align
	#[inline]
	pub fn from_bitslice(slice: &BitSlice<T, O>) -> Self {
		let bitspan = slice.as_bitspan();

		let mut vec = bitspan
			.elements()
			.pipe(Vec::with_capacity)
			.pipe(ManuallyDrop::new);
		vec.extend(slice.domain());

		let bitspan = unsafe {
			BitSpan::new_unchecked(
				vec.as_mut_ptr().cast::<T>().into_address(),
				bitspan.head(),
				bitspan.len(),
			)
		};
		let capacity = vec.capacity();
		Self { bitspan, capacity }
	}

	/// Constructs a new bit-vector from a single element.
	///
	/// This copies `elem` into a new heap allocation, and sets the bit-vector
	/// to cover it entirely.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bv = BitVec::<_, Msb0>::from_element(1u8);
	/// assert!(bv[7]);
	/// ```
	#[inline]
	pub fn from_element(elem: T) -> Self {
		Self::from_vec(vec![elem])
	}

	/// Constructs a new bit-vector from a slice of memory elements.
	///
	/// This copies `slice` into a new heap allocation, and sets the bit-vector
	/// to cover it entirely.
	///
	/// ## Panics
	///
	/// This panics if `slice` exceeds bit-vector capacity.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let slice = &[0u8, 1, 2, 3];
	/// let bv = BitVec::<_, Lsb0>::from_slice(slice);
	/// assert_eq!(bv.len(), 32);
	/// ```
	#[inline]
	pub fn from_slice(slice: &[T]) -> Self {
		Self::try_from_slice(slice).unwrap()
	}

	/// Fallibly constructs a new bit-vector from a slice of memory elements.
	///
	/// This fails early if `slice` exceeds bit-vector capacity. If it is not,
	/// then `slice` is copied into a new heap allocation and fully spanned by
	/// the returned bit-vector.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let slice = &[0u8, 1, 2, 3];
	/// let bv = BitVec::<_, Lsb0>::try_from_slice(slice).unwrap();
	/// assert_eq!(bv.len(), 32);
	/// ```
	#[inline]
	pub fn try_from_slice(slice: &[T]) -> Result<Self, BitSpanError<T>> {
		BitSlice::<T, O>::try_from_slice(slice).map(Self::from_bitslice)
	}

	/// Converts a regular vector in-place into a bit-vector.
	///
	/// The produced bit-vector spans every bit in the original vector. No
	/// reällocation occurs; this is purely a transform of the handle.
	///
	/// ## Panics
	///
	/// This panics if the source vector is too long to view as a bit-slice.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let v = vec![0u8, 1, 2, 3];
	/// let bv = BitVec::<_, Msb0>::from_vec(v);
	/// assert_eq!(bv.len(), 32);
	/// ```
	#[inline]
	pub fn from_vec(vec: Vec<T>) -> Self {
		Self::try_from_vec(vec)
			.expect("vector was too long to be converted into a `BitVec`")
	}

	/// Attempts to convert a regular vector in-place into a bit-vector.
	///
	/// This fails if the source vector is too long to view as a bit-slice. On
	/// success, the produced bit-vector spans every bit in the original vector.
	/// No reällocation occurs; this is purely a transform of the handle.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let v = vec![0u8; 20];
	/// assert_eq!(BitVec::<_, Msb0>::try_from_vec(v).unwrap().len(), 160);
	/// ```
	///
	/// It is not practical to allocate a vector that will fail this conversion.
	#[inline]
	pub fn try_from_vec(vec: Vec<T>) -> Result<Self, Vec<T>> {
		let mut vec = ManuallyDrop::new(vec);
		let capacity = vec.capacity();

		BitPtr::from_mut_slice(vec.as_mut_slice())
			.span(vec.len() * bits_of::<T::Mem>())
			.map(|bitspan| Self { bitspan, capacity })
			.map_err(|_| ManuallyDrop::into_inner(vec))
	}

	/// Appends the contents of a bit-slice to a bit-vector.
	///
	/// This can extend from a bit-slice of any type parameters; it is not
	/// restricted to using the same parameters as `self`. However, when the
	/// type parameters *do* match, it is possible for this to use a batch-copy
	/// optimization to go faster than the individual-bit crawl that is
	/// necessary when they differ.
	///
	/// Until Rust provides extensive support for specialization in trait
	/// implementations, you should use this method whenever you are extending
	/// from a `BitSlice` proper, and only use the general [`.extend()`]
	/// implementation if you are required to use a generic `bool` source.
	///
	/// ## Original
	///
	/// [`Vec::extend_from_slice`](alloc::vec::Vec::extend_from_slice)
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let mut bv = bitvec![0, 1];
	/// bv.extend_from_bitslice(bits![0, 1, 0, 0, 1]);
	/// assert_eq!(bv, bits![0, 1, 0, 1, 0, 0, 1]);
	/// ```
	///
	/// [`.extend()`]: https://docs.rs/bitvec/latest/bitvec/vec/struct.Vec.html#impl-Extend
	#[inline]
	pub fn extend_from_bitslice<T2, O2>(&mut self, other: &BitSlice<T2, O2>)
	where
		T2: BitStore,
		O2: BitOrder,
	{
		let len = self.len();
		let olen = other.len();
		self.resize(len + olen, false);
		unsafe { self.get_unchecked_mut(len ..) }.clone_from_bitslice(other);
	}

	/// Appends a slice of `T` elements to a bit-vector.
	///
	/// The slice is viewed as a `BitSlice<T, O>`, then appended directly to the
	/// bit-vector.
	///
	/// ## Original
	///
	/// [`Vec::extend_from_slice`](alloc::vec::Vec::extend_from_slice)
	#[inline]
	pub fn extend_from_raw_slice(&mut self, slice: &[T]) {
		self.extend_from_bitslice(slice.view_bits::<O>());
	}
}

/// Converters.
impl<T, O> BitVec<T, O>
where
	T: BitStore,
	O: BitOrder,
{
	/// Explicitly views the bit-vector as a bit-slice.
	#[inline]
	pub fn as_bitslice(&self) -> &BitSlice<T, O> {
		unsafe { self.bitspan.into_bitslice_ref() }
	}

	/// Explicitly views the bit-vector as a mutable bit-slice.
	#[inline]
	pub fn as_mut_bitslice(&mut self) -> &mut BitSlice<T, O> {
		unsafe { self.bitspan.into_bitslice_mut() }
	}

	/// Views the bit-vector as a slice of its underlying memory elements.
	#[inline]
	pub fn as_raw_slice(&self) -> &[T] {
		let (data, len) =
			(self.bitspan.address().to_const(), self.bitspan.elements());
		unsafe { slice::from_raw_parts(data, len) }
	}

	/// Views the bit-vector as a mutable slice of its underlying memory
	/// elements.
	#[inline]
	pub fn as_raw_mut_slice(&mut self) -> &mut [T] {
		let (data, len) =
			(self.bitspan.address().to_mut(), self.bitspan.elements());
		unsafe { slice::from_raw_parts_mut(data, len) }
	}

	/// Creates an unsafe shared bit-pointer to the start of the buffer.
	///
	/// ## Original
	///
	/// [`Vec::as_ptr`](alloc::vec::Vec::as_ptr)
	///
	/// ## Safety
	///
	/// You must initialize the contents of the underlying buffer before
	/// accessing memory through this pointer. See the `BitPtr` documentation
	/// for more details.
	#[inline]
	pub fn as_bitptr(&self) -> BitPtr<Const, T, O> {
		self.bitspan.to_bitptr().to_const()
	}

	/// Creates an unsafe writable bit-pointer to the start of the buffer.
	///
	/// ## Original
	///
	/// [`Vec::as_mut_ptr`](alloc::vec::Vec::as_mut_ptr)
	///
	/// ## Safety
	///
	/// You must initialize the contents of the underlying buffer before
	/// accessing memory through this pointer. See the `BitPtr` documentation
	/// for more details.
	#[inline]
	pub fn as_mut_bitptr(&mut self) -> BitPtr<Mut, T, O> {
		self.bitspan.to_bitptr()
	}

	/// Converts a bit-vector into a boxed bit-slice.
	///
	/// This may cause a reällocation to drop any excess capacity.
	///
	/// ## Original
	///
	/// [`Vec::into_boxed_slice`](alloc::vec::Vec::into_boxed_slice)
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bv = bitvec![0, 1, 0, 0, 1];
	/// let bb = bv.into_boxed_bitslice();
	/// ```
	#[inline]
	pub fn into_boxed_bitslice(self) -> BitBox<T, O> {
		let mut bitspan = self.bitspan;
		let mut boxed =
			self.into_vec().into_boxed_slice().pipe(ManuallyDrop::new);
		unsafe {
			bitspan.set_address(boxed.as_mut_ptr().into_address());
			BitBox::from_raw(bitspan.into_bitslice_ptr_mut())
		}
	}

	/// Converts a bit-vector into a `Vec` of its underlying storage.
	///
	/// The produced vector contains all elements that contained live bits. Dead
	/// bits have an unspecified value; you should call [`.set_uninitialized()`]
	/// before converting into a vector.
	///
	/// This does not affect the allocated memory; it is purely a conversion of
	/// the handle.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bv = bitvec![u8, Msb0; 0, 1, 0, 0, 1];
	/// let v = bv.into_vec();
	/// assert_eq!(v[0] & 0xF8, 0b01001_000);
	/// ```
	///
	/// [`.set_uninitialized()`]: Self::set_uninitialized
	#[inline]
	pub fn into_vec(self) -> Vec<T> {
		let (bitspan, capacity) = (self.bitspan, self.capacity);
		mem::forget(self);
		unsafe {
			Vec::from_raw_parts(
				bitspan.address().to_mut(),
				bitspan.elements(),
				capacity,
			)
		}
	}
}

/// Utilities.
impl<T, O> BitVec<T, O>
where
	T: BitStore,
	O: BitOrder,
{
	/// Overwrites each element (visible in [`.as_raw_mut_slice()`]) with a new
	/// bit-pattern.
	///
	/// This unconditionally writes `element` into each element in the backing
	/// slice, without altering the bit-vector’s length or capacity.
	///
	/// This guarantees that dead bits visible in [`.as_raw_slice()`] but not
	/// [`.as_bitslice()`] are initialized according to the bit-pattern of
	/// `element.` The elements not visible in the raw slice, but present in the
	/// allocation, do *not* specify a value. You may not rely on them being
	/// zeroed *or* being set to the `element` bit-pattern.
	///
	/// ## Parameters
	///
	/// - `&mut self`
	/// - `element`: The bit-pattern with which each live element in the backing
	///   store is initialized.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let mut bv = bitvec![u8, Msb0; 0; 20];
	/// assert_eq!(bv.as_raw_slice(), [0; 3]);
	/// bv.set_elements(0xA5);
	/// assert_eq!(bv.as_raw_slice(), [0xA5; 3]);
	/// ```
	///
	/// [`.as_bitslice()`]: Self::as_bitslice
	/// [`.as_raw_mut_slice()`]: Self::as_raw_mut_slice
	/// [`.as_raw_slice()`]: Self::as_raw_slice
	#[inline]
	pub fn set_elements(&mut self, element: T::Mem) {
		self.as_raw_mut_slice()
			.iter_mut()
			.for_each(|elt| elt.store_value(element));
	}

	/// Sets the uninitialized bits of a bit-vector to a known value.
	///
	/// This method modifies all bits that are observable in [`.as_raw_slice()`]
	/// but *not* observable in [`.as_bitslice()`] to a known value.
	/// Memory beyond the raw-slice view, but still within the allocation, is
	/// considered fully dead and will never be seen.
	///
	/// This can be used to zero the unused memory so that when viewed as a raw
	/// slice, unused bits have a consistent and predictable value.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let mut bv = 0b1101_1100u8.view_bits::<Lsb0>().to_bitvec();
	/// assert_eq!(bv.as_raw_slice()[0], 0b1101_1100u8);
	///
	/// bv.truncate(4);
	/// assert_eq!(bv.count_ones(), 2);
	/// assert_eq!(bv.as_raw_slice()[0], 0b1101_1100u8);
	///
	/// bv.set_uninitialized(false);
	/// assert_eq!(bv.as_raw_slice()[0], 0b0000_1100u8);
	///
	/// bv.set_uninitialized(true);
	/// assert_eq!(bv.as_raw_slice()[0], 0b1111_1100u8);
	/// ```
	///
	/// [`.as_bitslice()`]: Self::as_bitslice
	/// [`.as_raw_slice()`]: Self::as_raw_slice
	#[inline]
	pub fn set_uninitialized(&mut self, value: bool) {
		let head = self.bitspan.head().into_inner() as usize;
		let last = head + self.len();
		let all = self.as_raw_mut_slice().view_bits_mut::<O>();
		unsafe {
			all.get_unchecked_mut(.. head).fill(value);
			all.get_unchecked_mut(last ..).fill(value);
		}
	}

	/// Ensures that the live region of the bit-vector’s contents begin at the
	/// front edge of the buffer.
	///
	/// `BitVec` has performance optimizations where it moves its view of its
	/// buffer contents in order to avoid needless moves of its data within the
	/// buffer. This can lead to unexpected contents of the raw memory values,
	/// so this method ensures that the semantic contents of the bit-vector
	/// match its in-memory storage.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let data = 0b00_1111_00u8;
	/// let bits = data.view_bits::<Msb0>();
	///
	/// let mut bv = bits[2 .. 6].to_bitvec();
	/// assert_eq!(bv, bits![1; 4]);
	/// assert_eq!(bv.as_raw_slice()[0], data);
	///
	/// bv.force_align();
	/// assert_eq!(bv, bits![1; 4]);
	/// // BitVec does not specify the value of dead bits in its buffer.
	/// assert_eq!(bv.as_raw_slice()[0] & 0xF0, 0xF0);
	/// ```
	#[inline]
	pub fn force_align(&mut self) {
		let mut bitspan = self.bitspan;
		let len = bitspan.len();
		let head = self.bitspan.head();
		if head == BitIdx::MIN {
			return;
		}
		let head = head.into_inner() as usize;
		let last = head + len;
		unsafe {
			bitspan.set_head(BitIdx::MIN);
			bitspan.set_len(last);
			bitspan
				.into_bitslice_mut()
				.copy_within_unchecked(head .., 0);
			bitspan.set_len(len);
		}
		self.bitspan = bitspan;
	}

	/// Sets the starting-bit index of the span descriptor.
	///
	/// ## Safety
	///
	/// The new `head` value must not cause the final bits of the bit-vector to
	/// depart allocated memory.
	pub(crate) unsafe fn set_head(&mut self, new_head: BitIdx<T::Mem>) {
		self.bitspan.set_head(new_head);
	}

	/// Sets a bit-vector’s length without checking that it fits in the
	/// allocated capacity.
	///
	/// ## Safety
	///
	/// `new_len` must not exceed `self.capacity()`.
	pub(crate) unsafe fn set_len_unchecked(&mut self, new_len: usize) {
		self.bitspan.set_len(new_len);
	}

	/// Asserts that a length can be encoded into the bit-vector handle.
	///
	/// ## Panics
	///
	/// This panics if `len` is too large to encode into a `BitSpan`.
	#[inline]
	fn assert_len_encodable(len: usize) {
		assert!(
			BitSpan::<Const, T, O>::len_encodable(len),
			"bit-vector capacity exceeded: {} > {}",
			len,
			BitSlice::<T, O>::MAX_BITS,
		);
	}

	/// Reserves some memory through the underlying vector.
	///
	/// ## Parameters
	///
	/// - `&mut self`
	/// - `additional`: The amount of additional space required after
	///   `self.len()` in the allocation.
	/// - `func`: A function that manipulates the memory reservation of the
	///   underlying vector.
	///
	/// ## Behavior
	///
	/// `func` should perform the appropriate action to allocate space for at
	/// least `additional` more bits. After it returns, the underlying vector is
	/// extended with zero-initialized elements until `self.len() + additional`
	/// bits have been given initialized memory.
	#[inline]
	fn do_reservation(
		&mut self,
		additional: usize,
		func: impl FnOnce(&mut Vec<T>, usize),
	) {
		let len = self.len();
		let new_len = len.saturating_add(additional);
		Self::assert_len_encodable(new_len);

		let (head, elts) = (self.bitspan.head(), self.bitspan.elements());
		let new_elts =
			crate::mem::elts::<T>(head.into_inner() as usize + new_len);

		let extra_elts = new_elts - elts;
		self.with_vec(|vec| {
			func(&mut **vec, extra_elts);
			//  Ensure that any new elements are initialized.
			vec.resize_with(new_elts, || <T as BitStore>::ZERO);
		});
	}

	/// Briefly constructs an ordinary `Vec` controlling the buffer, allowing
	/// operations to be applied to the memory allocation.
	///
	/// ## Parameters
	///
	/// - `&mut self`
	/// - `func`: A function which may interact with the memory allocation.
	///
	/// After `func` runs, `self` is updated with the temporary `Vec`’s address
	/// and capacity.
	#[inline]
	fn with_vec<F, R>(&mut self, func: F) -> R
	where F: FnOnce(&mut ManuallyDrop<Vec<T>>) -> R {
		let mut vec = unsafe { ptr::read(self) }
			.into_vec()
			.pipe(ManuallyDrop::new);
		let out = func(&mut vec);

		unsafe {
			self.bitspan.set_address(vec.as_mut_ptr().into_address());
		}
		self.capacity = vec.capacity();
		out
	}
}