Sign In

bitvec

Package Overview
Dependencies
Maintainers
0
Versions
61
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

bitvec - cargo Package Compare versions

Package version was removed
This package version has been unpublished, mostly likely due to security reasons
Comparing version
0.2.0
 to
0.3.0
+41
CHANGELOG.md
# Changelog
All notable changes will be documented in this file.
## 0.3.0
Split `BitVec` off into `BitSlice` wherever possible.
### Added
- The `BitSlice` type is the `[T]` to `BitVec`'s `Vec<T>`. `BitVec` now `Deref`s
to it, and has offloaded all the work that does not require managing allocated
memory.
- Almost all of the public API on both types has documentation and example code.
### Changed
- The implementations of left- ard right- shift are now faster.
- `BitVec` can `Borrow` and `Deref` down to `BitSlice`, and offloads as much
work as possible to it.
- `Clone` is more intelligent.
## 0.2.0
Improved the `bitvec!` macro.
### Changed
- `bitvec!` takes more syntaxes to better match `vec!`, and has better
runtime performance. The increased static memory used by `bitvec!` should be
more than counterbalanced by the vastly better generated code.
## 0.1.0
Initial implementation and release.
### Added
- `Endian` and `Bits` traits
- `BitVec` type with basic `Vec` idioms and parallel trait implementations
- `bitvec!` generator macro
+88
examples/tour.rs
/*! Demonstrates construction and use of a big-endian, u8, `BitVec`
This example uses `bitvec!` to construct a `BitVec` from literals, then shows
a sample of the various operations that can be applied to it.
This example prints **a lot** of text to the console.
!*/
#[macro_use]
extern crate bitvec;
use bitvec::*;
use std::iter::repeat;
fn main() {
let bv = bitvec![
0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 1, 0,
];
println!("A BigEndian BitVec has the same layout in memory as it does semantically");
render(&bv);
// BitVec can turn into iterators, and be built from iterators.
let bv: BitVec<LittleEndian, u8> = bv.into_iter().collect();
println!("A LittleEndian BitVec has the opposite layout in memory as it does semantically");
render(&bv);
let bv: BitVec<BigEndian, u16> = bv.into_iter().collect();
println!("A BitVec can use storage other than u8");
render(&bv);
println!("BitVec can participate in Boolean arithmetic");
let full = bv.clone() | repeat(true);
render(&full);
let empty = full & repeat(false);
render(&empty);
let flip = bv ^ repeat(true);
render(&flip);
let bv = !flip;
render(&bv);
println!("\
Notice that ^ did not affect the parts of the tail that were not in use, while !
did affect them. ^ requires a second source, while ! can just flip all elements.
! is faster, but ^ is less likely to break your assumptions about what the
memory looks like.\
");
// Push and pop to the bitvec
let mut bv = bv;
for _ in 0 .. 12 {
bv.push(false);
}
for _ in 0 .. 12 {
bv.pop();
}
render(&bv);
println!("End example");
}
fn render<E: Endian, T: Bits>(bv: &BitVec<E, T>) {
println!("Memory information: {} {} {}", bv.elts(), bv.bits(), bv.len());
println!("Print out the semantic contents");
println!("{:#?}", bv);
println!("Print out the memory contents");
println!("{:?}", bv.as_ref());
println!("Show the bits in memory");
for elt in bv.as_ref() {
println!("{:0w$b} ", elt, w=::std::mem::size_of::<T>() * 8);
}
println!();
}
Justfile

Sorry, the diff of this file is not supported yet

+1069
src/slice.rs
/*! `BitSlice` Wide Reference
This module bears some explanation. Let's get *uncomfortable* here.
Safe Rust is very strict about concepts like lifetimes and size in memory. It
won't allow you to have arbitrary *references* to things where Rust doesn't feel
absolutely confident that the referent will outlive the reference, and it won't
let you have things *at all* that it can't size at compile time. This makes
dealing with runtime-sized memory of uncertain lifetime tricky to do, and the
language provides some tools out of the box for this: slice references, which
store a pointer and also a length, and do so in a manner vaguely obscured to the
rest of Rust code behind opaque stdlib types.
My first instinct was to define `BitSlice` as a newtype wrapper around an `&T`,
so that `BitSlice` would be sized and manageable directly. Unfortunately, this
parameterizes the lifetime of the reference into the `BitSlice` struct, making
it generic over a lifetime. When I tried to implement `Deref` on `BitVec` to
return a `BitSlice`, I realized I could not do so for two main reasons: one,
`Deref` requires returning a reference to a type, and it is impossible to tell
Rust "this type is a named reference", and two, ... the lifetime parameter of
`BitSlice` is not able to be provided by the `Deref` trait, the `deref` trait
function, or even by using Higher Ranked Trait Bounds because HRTB just allows
the creation of a lifetime parameter in items in the trait scope that were not
defined with that lifetime parameter, but without Generic Associated Types it is
impossible to add that lifetime parameter to the associated type `Target`!
Also this ran into mutability issues in regards to the interior reference vs the
wrapper.
So `BitSlice` is a newtype wrapper around `[T]`, and can only be touched as a
reference or mutable reference, and has the advantage that now it can be a
`Deref::Target`.
**DO NOT** create an `&BitSlice` yourself! A slice reference can be made to
count bits using `.into()`.
!*/
use super::{
Bits,
Endian,
BigEndian,
BitVec,
TRUE,
FALSE,
};
use std::borrow::ToOwned;
use std::cmp::{
Eq,
Ord,
PartialEq,
PartialOrd,
Ordering,
};
use std::convert::{
AsRef,
AsMut,
From,
};
use std::fmt::{
self,
Debug,
Display,
Formatter,
};
use std::iter::{
DoubleEndedIterator,
ExactSizeIterator,
Iterator,
IntoIterator,
};
use std::marker::PhantomData;
use std::mem;
use std::ops::{
BitAndAssign,
BitOrAssign,
BitXorAssign,
Index,
Not,
ShlAssign,
ShrAssign,
};
use std::ptr;
use std::slice;
/** A compact slice of bits, whose cursor and storage type can be customized.
`BitSlice` is a newtype wrapper over `[T]`, and as such can only be held by
reference. It is impossible to create a `Box<BitSlice<E, T>>` from this library,
and assembling one yourself is Undefined Behavior for which this library is not
responsible. **Do not try to create a `Box<BitSlice>`.** If you want an owned
bit collection, use `BitVec`.
`BitSlice` is strictly a reference type. The memory it governs must be owned by
some other type, and a shared or exclusive reference to it as `BitSlice` can be
created by using the `From` implementation on `&BitSlice` and `&mut BitSlice`.
`BitSlice` is to `BitVec` what `[T]` is to `Vec<T>`.
`BitSlice` takes two type parameters.
- `E: Endian` must be an implementor of the `Endian` trait. `BitVec` takes a
`PhantomData` marker for access to the associated functions, and will never
make use of an instance of the trait. The default implementations,
`LittleEndian` and `BigEndian`, are zero-sized, and any further
implementations should be as well, as the invoked functions will never receive
state.
- `T: Bits` must be a primitive type. Rust decided long ago to not provide a
unifying trait over the primitives, so `Bits` provides access to just enough
properties of the primitives for `BitVec` to use. This trait is sealed against
downstream implementation, and can only be implemented in this crate.
**/
#[cfg_attr(nightly, repr(transparent))]
pub struct BitSlice<E: Endian = BigEndian, T: Bits = u8> {
_endian: PhantomData<E>,
inner: [T],
}
impl<E, T> BitSlice<E, T>
where E: Endian, T: Bits {
/// Gets the bit value at the given position.
///
/// The index value is a semantic count, not a bit address. It converts to a
/// bit position internally to this function.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![0, 0, 1, 0, 0];
/// let bits: &BitSlice = &bv;
/// assert!(bits.get(2));
/// ```
pub fn get(&self, index: usize) -> bool {
assert!(index < self.len(), "Index out of range!");
let (elt, bit) = T::split(index);
self.as_ref()[elt].get(E::curr::<T>(bit))
}
/// Sets the bit value at the given position.
///
/// The index value is a semantic count, not a bit address. It converts to a
/// bit position internally to this function.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![0; 5];
/// let bits: &mut BitSlice = &mut bv;
/// bits.set(2, true);
/// assert!(bits.get(2));
/// ```
pub fn set(&mut self, index: usize, value: bool) {
assert!(index < self.len(), "Index out of range!");
let (elt, bit) = T::split(index);
self.as_mut()[elt].set(E::curr::<T>(bit), value);
}
/// Returns the number of bits contained in the `BitSlice`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![1; 10];
/// let bits: &BitSlice = &bv;
/// assert_eq!(bits.len(), 10);
/// ```
pub fn len(&self) -> usize {
self.inner.len()
}
/// Counts how many *whole* storage elements are in the `BitSlice`.
///
/// If the `BitSlice` length is not an even multiple of the width of `T`,
/// then the slice under this `BitSlice` is one element longer than this
/// method reports, and the number of bits in it are reported by `bits()`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![1; 10];
/// let bits: &BitSlice = &bv;
/// assert_eq!(bits.elts(), 1);
/// ```
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![1; 16];
/// let bits: &BitSlice = &bv;
/// assert_eq!(bits.elts(), 2);
/// ```
pub fn elts(&self) -> usize {
self.len() >> T::BITS
}
/// Counts how many bits are in the trailing partial storage element.
///
/// If the `BitSlice` length is an even multiple of the width of `T`, then
/// this returns 0 and the `BitSlice` does not consider its final element to
/// be partially used.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![1; 10];
/// let bits: &BitSlice = &bv;
/// assert_eq!(bits.bits(), 2);
/// ```
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![1; 16];
/// let bits: &BitSlice = &bv;
/// assert_eq!(bits.bits(), 0);
/// ```
pub fn bits(&self) -> u8 {
self.len() as u8 & T::MASK
}
/// Returns `true` if the slice contains no bits.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![];
/// let bits: &BitSlice = &bv;
/// assert!(bits.is_empty());
/// ```
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![0; 5];
/// let bits: &BitSlice = &bv;
/// assert!(!bits.is_empty());
/// ```
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Provides read-only iteration across the collection.
///
/// The iterator returned from this method implements `ExactSizeIterator`
/// and `DoubleEndedIterator` just as the consuming `.into_iter()` method’s
/// iterator does.
pub fn iter<'a>(&'a self) -> Iter<'a, E, T> {
self.into_iter()
}
/// Retrieves a read pointer to the start of the data slice.
pub(crate) fn as_ptr(&self) -> *const T {
self.inner.as_ptr()
}
/// Retrieves a write pointer to the start of the data slice.
pub(crate) fn as_mut_ptr(&mut self) -> *mut T {
self.inner.as_mut_ptr()
}
/// Computes the actual length of the data slice, including the partial tail
/// if any.
///
/// # Examples
///
/// ```rust,ignore
/// use bitvec::*;
/// let bv = bitvec![1; 10];
/// let bits: &BitSlice = &bv;
/// assert_eq!(bits.elts(), 1);
/// assert_eq!(bits.raw_len(), 2);
/// ```
pub(crate) fn raw_len(&self) -> usize {
self.elts() + if self.bits() > 0 { 1 } else { 0 }
}
/// Prints a type header into the Formatter.
pub(crate) fn fmt_header(&self, fmt: &mut Formatter) -> fmt::Result {
write!(fmt, "BitSlice<{}, {}>", E::TY, T::TY)
}
/// Formats the contents data slice.
///
/// The debug flag indicates whether to indent each line (`Debug` does,
/// `Display` does not).
pub(crate) fn fmt_body(&self, fmt: &mut Formatter, debug: bool) -> fmt::Result {
let (elts, bits) = T::split(self.len());
let len = self.raw_len();
let buf = self.as_ref();
let alt = fmt.alternate();
for idx in 0 .. elts {
Self::fmt_element(fmt, &buf[idx])?;
if idx < len - 1 {
match (alt, debug) {
// {}
(false, false) => fmt.write_str(" "),
// {:#}
(true, false) => writeln!(fmt),
// {:?}
(false, true) => fmt.write_str(", "),
// {:#?}
(true, true) => { writeln!(fmt, ",")?; fmt.write_str(" ") },
}?;
}
}
if bits > 0 {
Self::fmt_bits(fmt, &buf[elts], bits)?;
}
Ok(())
}
/// Formats a whole storage element of the data slice.
pub(crate) fn fmt_element(fmt: &mut Formatter, elt: &T) -> fmt::Result {
Self::fmt_bits(fmt, elt, T::WIDTH)
}
/// Formats a partial element of the data slice.
pub(crate) fn fmt_bits(fmt: &mut Formatter, elt: &T, bits: u8) -> fmt::Result {
use std::fmt::Write;
let mut out = String::with_capacity(bits as usize);
for bit in 0 .. bits {
let cur = E::curr::<T>(bit);
write!(out, "{}", if elt.get(cur) { "1" } else { "0" })?;
}
fmt.write_str(&out)
}
}
/// Gives write access to all elements in the underlying storage, including the
/// partially-filled tail element (if present).
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bytes: &mut [u8] = &mut [5, 10, 15, 20, 25];
/// let bits: &mut BitSlice = bytes.into();
/// for elt in bits.as_mut() {
/// *elt += 2;
/// }
/// assert_eq!(&[7, 12, 17, 22, 27], bits.as_ref());
/// ```
impl<E, T> AsMut<[T]> for BitSlice<E, T>
where E: Endian, T: Bits {
fn as_mut(&mut self) -> &mut [T] {
let (ptr, len): (*mut T, usize) = (self.as_mut_ptr(), self.raw_len());
unsafe { slice::from_raw_parts_mut(ptr, len) }
}
}
/// Gives read access to all elements in the underlying storage, including the
/// partially-filled tail element (if present).
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bytes: &[u8] = &[5, 10, 15, 20, 25];
/// let bits: &BitSlice = bytes.into();
/// assert_eq!(&[5, 10, 15, 20, 25], bits.as_ref());
/// ```
impl<E, T> AsRef<[T]> for BitSlice<E, T>
where E: Endian, T: Bits {
fn as_ref(&self) -> &[T] {
let (ptr, len): (*const T, usize) = (self.as_ptr(), self.raw_len());
unsafe { slice::from_raw_parts(ptr, len) }
}
}
/// Performs the Boolean AND operation against another bitstream and writes the
/// result into `self`. If the other bitstream ends before `self` does, it is
/// extended with zero, clearing all remaining bits in `self`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs: &mut BitSlice = &mut bitvec![0, 1, 0, 1, 0, 1];
/// let rhs = bitvec![0, 0, 1, 1];
/// *lhs &= rhs;
/// assert_eq!("000100", &format!("{}", lhs));
/// ```
impl<E, T, I> BitAndAssign<I> for BitSlice<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
fn bitand_assign(&mut self, rhs: I) {
use std::iter::repeat;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter().chain(repeat(false))) {
let val = self.get(idx) & other;
self.set(idx, val);
}
}
}
/// Performs the Boolear OR operation against another bitstream and writes the
/// result into `self`. If the other bitstream ends before `self` does, it is
/// extended with zero, leaving all remaining bits in `self` as they were.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs: &mut BitSlice = &mut bitvec![0, 1, 0, 1, 0, 1];
/// let rhs = bitvec![0, 0, 1, 1];
/// *lhs |= rhs;
/// assert_eq!("011101", &format!("{}", lhs));
/// ```
impl<E, T, I> BitOrAssign<I> for BitSlice<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
fn bitor_assign(&mut self, rhs: I) {
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) | other;
self.set(idx, val);
}
}
}
/// Performs the Boolean XOR operation against another bitstream and writes the
/// result into `self`. If the other bitstream ends before `self` does, it is
/// extended with zero, leaving all remaining bits in `self` as they were.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs: &mut BitSlice = &mut bitvec![0, 1, 0, 1, 0, 1];
/// let rhs = bitvec![0, 0, 1, 1];
/// *lhs ^= rhs;
/// assert_eq!("011001", &format!("{}", lhs));
/// ```
impl<E, T, I> BitXorAssign<I> for BitSlice<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
fn bitxor_assign(&mut self, rhs: I) {
use std::iter::repeat;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter().chain(repeat(false))) {
let val = self.get(idx) ^ other;
self.set(idx, val);
}
}
}
/// Prints the `BitSlice` for debugging.
///
/// The output is of the form `BitSlice<E, T> [ELT, *]` where `<E, T>` is the
/// endianness and element type, with square brackets on each end of the bits
/// and all the elements of the array printed in binary. The printout is always
/// in semantic order, and may not reflect the underlying buffer. To see the
/// underlying buffer, use `.as_ref()`.
///
/// The alternate character `{:#?}` prints each element on its own line, rather
/// than having all elements on the same line.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bits: &BitSlice<LittleEndian, u16> = &bitvec![
/// LittleEndian, u16;
/// 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1,
/// 0, 1
/// ];
/// assert_eq!("BitSlice<LittleEndian, u16> [0101000011110101, 01]", &format!("{:?}", bits));
/// ```
impl<E, T> Debug for BitSlice<E, T>
where E: Endian, T: Bits {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
let alt = fmt.alternate();
self.fmt_header(fmt)?;
fmt.write_str(" [")?;
if alt { writeln!(fmt)?; }
self.fmt_body(fmt, true)?;
if alt { writeln!(fmt)?; }
fmt.write_str("]")
}
}
/// Prints the `BitSlice` for displaying.
///
/// This prints each element in turn, formatted in binary in semantic order (so
/// the first bit seen is printed first and the last bit seen is printed last).
/// Each element of storage is separated by a space for ease of reading.
///
/// The alternate character `{:#}` prints each element on its own line.
///
/// To see the in-memory representation, use `.as_ref()` to get access to the
/// raw elements and print that slice instead.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bits: &BitSlice = &bitvec![0, 1, 0, 0, 1, 0, 1, 1, 0, 1];
/// assert_eq!("01001011 01", &format!("{}", bits));
/// ```
impl<E, T> Display for BitSlice<E, T>
where E: Endian, T: Bits {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
self.fmt_body(fmt, false)
}
}
/// Builds a `BitSlice` from a slice of elements. The resulting `BitSlice` will
/// always completely fill the original slice, and will not have a partial tail.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src = vec![1u8, 2, 3];
/// let borrow: &[u8] = &src;
/// let bits: &BitSlice = borrow.into();
/// assert_eq!(bits.len(), 24);
/// assert_eq!(bits.elts(), 3);
/// assert_eq!(bits.bits(), 0);
/// assert!(bits.get(7)); // src[0] == 0b0000_0001
/// assert!(bits.get(14)); // src[1] == 0b0000_0010
/// assert!(bits.get(22)); // src[2] == 0b0000_0011
/// assert!(bits.get(23));
/// ```
impl<'a, E, T> From<&'a [T]> for &'a BitSlice<E, T>
where E: Endian, T: 'a + Bits {
fn from(src: &'a [T]) -> Self {
let (ptr, len): (*const T, usize) = (src.as_ptr(), src.len());
assert!(len <= T::MAX_ELT, "Source slice length out of range!");
unsafe {
mem::transmute(
slice::from_raw_parts(ptr, len << T::BITS)
)
}
}
}
/// Builds a mutable `BitSlice` from a slice of mutable elements. The resulting
/// `BitSlice` will always completely fill the original slice, and will not have
/// a partial tail.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = vec![1u8, 2, 3];
/// let borrow: &mut [u8] = &mut src;
/// let bits: &mut BitSlice = borrow.into();
/// assert!(!bits.get(0));
/// bits.set(0, true);
/// assert!(bits.get(0));
/// ```
impl<'a, E, T> From<&'a mut [T]> for &'a mut BitSlice<E, T>
where E: Endian, T: 'a + Bits {
fn from(src: &'a mut [T]) -> Self {
let (ptr, len): (*mut T, usize) = (src.as_mut_ptr(), src.len());
assert!(len <= T::MAX_ELT, "Source slice length out of range!");
unsafe {
mem::transmute(
slice::from_raw_parts_mut(ptr, len << T::BITS)
)
}
}
}
/// Index a single bit by semantic count. The index must be less than the length
/// of the `BitSlice`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![0, 0, 1, 0, 0];
/// let bits: &BitSlice = &bv;
/// assert!(bits[2]);
/// assert!(!bits[3]);
/// ```
impl<'a, E, T> Index<usize> for &'a BitSlice<E, T>
where E: Endian, T: 'a + Bits {
type Output = bool;
fn index(&self, index: usize) -> &Self::Output {
match self.get(index) {
true => &TRUE,
false => &FALSE,
}
}
}
/// Index a single bit by element and bit index within the element. The element
/// index must be less than the length of the underlying store, and the bit
/// index must be less than the width of the underlying element.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![0; 10];
/// bv.push(true);
/// let bits: &BitSlice = &bv;
/// assert!(bits[(1, 2)]); // 10
/// assert!(!bits[(1, 1)]); // 9
/// ```
impl<'a, E, T> Index<(usize, u8)> for &'a BitSlice<E, T>
where E: Endian, T: 'a + Bits {
type Output = bool;
fn index(&self, (elt, bit): (usize, u8)) -> &Self::Output {
match self.get(T::join(elt, bit)) {
true => &TRUE,
false => &FALSE,
}
}
}
/// Produces a read-only iterator over all the bits in the `BitSlice`.
///
/// This iterator follows the ordering in the `BitSlice` type, and implements
/// `ExactSizeIterator` as `BitSlice` has a known, fixed length, and
/// `DoubleEndedIterator` as it has known ends.
impl<'a, E, T> IntoIterator for &'a BitSlice<E, T>
where E: Endian, T: 'a + Bits {
type Item = bool;
type IntoIter = Iter<'a, E, T>;
fn into_iter(self) -> Self::IntoIter {
self.into()
}
}
/// Flips all bits in the slice, in place.
///
/// This invokes the `!` operator on each element of the borrowed storage, and
/// so it will also flip bits in the tail that are outside the `BitSlice` length
/// if any. Use `^= repeat(true)` to flip only the bits actually inside the
/// `BitSlice` purview.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![0; 10];
/// let bits: &mut BitSlice = &mut bv;
/// let new_bits = !bits;
/// // The `bits` binding is consumed by the `!` operator, and a new reference
/// // is returned.
/// // assert_eq!(bits.as_ref(), &[!0, !0]);
/// assert_eq!(new_bits.as_ref(), &[!0, !0]);
/// ```
impl<'a, E, T> Not for &'a mut BitSlice<E, T>
where E: Endian, T: 'a + Bits {
type Output = Self;
fn not(self) -> Self::Output {
for elt in self.as_mut() {
*elt = !*elt;
}
self
}
}
/// Tests if two `BitSlice`s are semantically — not bitwise — equal.
///
/// It is valid to compare two slices of different endianness or element types.
///
/// The equality condition requires that they have the same number of total bits
/// and that each pair of bits in semantic order are identical.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let l: BitVec<LittleEndian, u16> = bitvec![LittleEndian, u16; 0, 1, 0, 1];
/// let r: BitVec<BigEndian, u32> = bitvec![BigEndian, u32; 0, 1, 0, 1];
///
/// let ls: &BitSlice<_, _> = &l;
/// let rs: &BitSlice<_, _> = &r;
/// assert!(ls == rs);
/// ```
impl<A, B, C, D> PartialEq<BitSlice<C, D>> for BitSlice<A, B>
where A: Endian, B: Bits, C: Endian, D: Bits {
fn eq(&self, rhs: &BitSlice<C, D>) -> bool {
let (l, r) = (self.iter(), rhs.iter());
if l.len() != r.len() {
return false;
}
l.zip(r).all(|(l, r)| l == r)
}
}
impl<E, T> Eq for BitSlice<E, T>
where E: Endian, T: Bits {}
/// Compares two `BitSlice`s by semantic — not bitwise — ordering.
///
/// The comparison sorts by testing each index for one slice to have a set bit
/// where the other has an unset bit. If the slices are different, the slice
/// with the set bit sorts greater than the slice with the unset bit.
///
/// If one of the slices is exhausted while the inspected part is identical,
/// then the slices sort by length.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let a = bitvec![0, 1, 0, 0];
/// let b = bitvec![0, 1, 0, 1];
/// let c = bitvec![0, 1, 0, 1, 1];
/// let aref: &BitSlice = &a;
/// let bref: &BitSlice = &b;
/// let cref: &BitSlice = &c;
/// assert!(aref < bref);
/// assert!(bref < cref);
/// ```
impl<A, B, C, D> PartialOrd<BitSlice<C, D>> for BitSlice<A, B>
where A: Endian, B: Bits, C: Endian, D: Bits {
fn partial_cmp(&self, rhs: &BitSlice<C, D>) -> Option<Ordering> {
for (l, r) in self.iter().zip(rhs.iter()) {
match (l, r) {
(true, false) => return Some(Ordering::Greater),
(false, true) => return Some(Ordering::Less),
_ => continue,
}
}
self.len().partial_cmp(&rhs.len())
}
}
impl<E, T> Ord for BitSlice<E, T>
where E: Endian, T: Bits {
fn cmp(&self, rhs: &Self) -> Ordering {
match self.partial_cmp(rhs) {
Some(ord) => ord,
None => unreachable!("`BitSlice` has a total ordering"),
}
}
}
__bitslice_shift!(u8, u16, u32, u64, i8, i16, i32, i64);
/// Shifts all bits in the array to the left — DOWN AND TOWARDS THE FRONT.
///
/// On primitives, the left-shift operator `<<` moves bits away from the origin
/// and towards the ceiling. This is because we label the bits in a primitive
/// with the minimum on the right and the maximum on the left, which is
/// big-endian bit order. This increases the value of the primitive being
/// shifted.
///
/// **THAT IS NOT HOW `BitSlice` WORKS!**
///
/// `BitSlice` defines its layout with the minimum on the left and the maximum
/// on the right! Thus, left-shifting moves bits towards the **minimum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `<<`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `>>` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effecs in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// left to their old value.
///
/// The shift amount is modulated against the array length, so it is not an
/// error to pass a shift amount greater than the array length.
///
/// A shift amount of zero is a no-op, and returns immediately.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![1, 1, 1, 0, 0, 0, 0, 0, 1];
/// let bits: &mut BitSlice = &mut bv;
/// *bits <<= 3;
/// assert_eq!("00000100 0", &format!("{}", bits));
/// // ^ former tail
/// ```
impl<E, T> ShlAssign<usize> for BitSlice<E, T>
where E: Endian, T: Bits {
fn shl_assign(&mut self, shamt: usize) {
let len = self.len();
// Bring the shift amount down into the slice's domain.
let shamt = shamt % len;
// If the shift amount was an even multiple of the length, exit.
if shamt == 0 {
return;
}
// If the shift amount is an even multiple of the element width, use
// ptr::copy instead of a bitwise crawl
if shamt & T::MASK as usize == 0 {
// Compute the shift distance measured in elements.
let offset = shamt >> T::BITS;
// Compute the number of elements that will remain.
let rem = self.raw_len() - offset;
// Memory model: suppose we have this slice of sixteen elements,
// that is shifted five elements to the left. We have three
// pointers and two lengths to manage.
// - rem is 11
// - offset is 5
// - head is [0]
// - body is [5; 11]
// - tail is [11]
// [ 0 1 2 3 4 5 6 7 8 9 a b c d e f ]
// | ^---------+---------^ <- before
// ^-------------------^ ^-------^ <- zero-filled
// after
// Pointer to the front of the slice
let head: *mut T = self.as_mut_ptr();
// Pointer to the front of the section that will move and be
// retained
let body: *const T = &self.as_ref()[offset];
// Pointer to the back of the slice that will be zero-filled.
let tail: *mut T = &mut self.as_mut()[rem];
unsafe {
ptr::copy(body, head, rem);
ptr::write_bytes(tail, 0, offset);
}
return;
}
// If the shift amount is not an even multiple, do a bitwise crawl and
// move bits forward, then zero-fill the back.
// Same general logic as above, but bit-level instead of element-level.
for (to, from) in (shamt .. len).enumerate() {
let val = self.get(from);
self.set(to, val);
}
for bit in (len - shamt) .. len {
self.set(bit, false);
}
}
}
/// Shifts all bits in the array to the right — UP AND TOWARDS THE BACK.
///
/// On primitives, the right-shift operator `>>` moves bits towards the origin
/// and away from the ceiling. This is because we label the bits in a primitive
/// with the minimum on the right and the maximum on the left, which is
/// big-endian bit order. This decreases the value of the primitive being
/// shifted.
///
/// **THAT IS NOT HOW `BitSlice` WORKS!**
///
/// `BitSlice` defines its layout with the minimum on the left and the maximum
/// on the right! Thus, right-shifting moves bits towards the **maximum**.
///
/// In Big-Endian order, the effect in memory will be what you expect the `>>`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `<<` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// left to their old value.
///
/// The shift amount is modulated against the array length, so it is not an
/// error to pass a shift amount greater than the array length.
///
/// A shift amount of zero is a no-op, and returns immediately.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![1, 0, 0, 0, 0, 0, 1, 1, 1];
/// let bits: &mut BitSlice = &mut bv;
/// *bits >>= 3;
/// assert_eq!("00010000 0", &format!("{}", bits));
/// // ^ former head
/// ```
impl<E, T> ShrAssign<usize> for BitSlice<E, T>
where E: Endian, T: Bits {
fn shr_assign(&mut self, shamt: usize) {
let len = self.len();
// Bring the shift amount down into the slice's domain.
let shamt = shamt % len;
// If the shift amount was an even multiple of the length, exit.
if shamt == 0 {
return;
}
// If the shift amount is an even multiple of the element width, use
// ptr::copy instead of a bitwise crawl.
if shamt & T::MASK as usize == 0 {
// Compute the shift amount measured in elements.
let offset = shamt >> T::BITS;
// Compute the number of elements that will remain.
let rem = self.raw_len() - offset;
// Memory model: suppose we have this slice of sixteen elements,
// that is shifted five elements to the right. We have two pointers
// and two lengths to manage.
// - rem is 11
// - offset is 5
// - head is [0; 11]
// - body is [5]
// [ 0 1 2 3 4 5 6 7 8 9 a b c d e f ]
// ^---------+---------^ | <- before
// ^-------^ ^-------------------^ <- after
// zero-filled
let head: *mut T = self.as_mut_ptr();
let body: *mut T = &mut self.as_mut()[offset];
unsafe {
ptr::copy(head, body, rem);
ptr::write_bytes(head, 0, offset);
}
return;
}
for (from, to) in (shamt .. len).enumerate().rev() {
let val = self.get(from);
self.set(to, val);
}
for bit in 0 .. shamt {
self.set(bit, false);
}
}
}
/// Clones a borrowed `BitSlice` into an owned `BitVec`.
impl<E, T> ToOwned for BitSlice<E, T>
where E: Endian, T: Bits {
type Owned = BitVec<E, T>;
fn to_owned(&self) -> Self::Owned {
let mut out = Self::Owned::with_capacity(self.len());
unsafe {
let src = self.as_ptr();
let dst = out.as_mut_ptr();
let len = self.raw_len();
ptr::copy_nonoverlapping(src, dst, len);
}
out
}
}
/// Permits iteration over a `BitSlice`
#[doc(hidden)]
pub struct Iter<'a, E: 'a + Endian, T: 'a + Bits> {
inner: &'a BitSlice<E, T>,
head: usize,
tail: usize,
}
impl<'a, E: 'a + Endian, T: 'a + Bits> Iter<'a, E, T> {
fn reset(&mut self) {
self.head = 0;
self.tail = self.inner.len();
}
}
impl<'a, E: 'a + Endian, T: 'a + Bits> DoubleEndedIterator for Iter<'a, E, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.tail > self.head {
self.tail -= 1;
Some(self.inner.get(self.tail))
}
else {
self.reset();
None
}
}
}
impl<'a, E: 'a + Endian, T: 'a + Bits> ExactSizeIterator for Iter<'a, E, T> {
fn len(&self) -> usize {
self.tail - self.head
}
}
impl<'a, E: 'a + Endian, T: 'a + Bits> From<&'a BitSlice<E, T>> for Iter<'a, E, T> {
fn from(src: &'a BitSlice<E, T>) -> Self {
let len = src.len();
Self {
inner: src,
head: 0,
tail: len,
}
}
}
impl<'a, E: 'a + Endian, T: 'a + Bits> Iterator for Iter<'a, E, T> {
type Item = bool;
fn next(&mut self) -> Option<Self::Item> {
if self.head < self.tail {
let ret = self.inner.get(self.head);
self.head += 1;
Some(ret)
}
else {
self.reset();
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let rem = ExactSizeIterator::len(self);
(rem, Some(rem))
}
/// Counts how many bits are live in the iterator, consuming it.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 1, 0, 1, 0];
/// assert_eq!(bv.iter().count(), 5);
/// ```
fn count(self) -> usize {
ExactSizeIterator::len(&self)
}
/// Advances the iterator by `n` bits, starting from zero.
///
/// It is not an error to advance past the end of the iterator! Doing so
/// returns `None`, and resets the iterator to its beginning.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1];
/// let mut bv_iter = bv.iter();
/// assert_eq!(bv_iter.len(), 4);
/// assert!(bv_iter.nth(3).unwrap());
/// ```
///
/// This example intentionally overshoots the iterator bounds, which causes
/// a reset to the initiol state. It then demonstrates that `nth` is
/// stateful, and is not an absolute index, by seeking ahead by two (to the
/// third zero bit) and then taking the bit immediately after it, which is
/// set. This shows that the argument to `nth` is how many bits to discard
/// before yielding the next.
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1];
/// let mut bv_iter = bv.iter();
/// assert!(bv_iter.nth(4).is_none());
/// assert!(!bv_iter.nth(2).unwrap());
/// assert!(bv_iter.nth(0).unwrap());
/// ```
fn nth(&mut self, n: usize) -> Option<bool> {
self.head += n;
self.next()
}
/// Consumes the iterator, returning only the last bit.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1];
/// assert!(bv.into_iter().last().unwrap());
/// ```
///
/// Empty iterators return `None`
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![];
/// assert!(bv.into_iter().last().is_none());
/// ```
fn last(mut self) -> Option<bool> {
self.next_back()
}
}
+1540
src/vec.rs
use super::{
BitSlice,
Bits,
Endian,
BigEndian,
LittleEndian,
TRUE,
FALSE,
};
use std::borrow::{
Borrow,
BorrowMut,
};
use std::clone::Clone;
use std::convert::{
AsMut,
AsRef,
From,
};
use std::fmt::{
self,
Debug,
Display,
Formatter,
};
use std::iter::{
DoubleEndedIterator,
ExactSizeIterator,
Extend,
FromIterator,
Iterator,
IntoIterator,
};
use std::marker::PhantomData;
use std::mem;
use std::ops::{
BitAnd,
BitAndAssign,
BitOr,
BitOrAssign,
BitXor,
BitXorAssign,
Deref,
DerefMut,
Index,
Not,
Shl,
ShlAssign,
Shr,
ShrAssign,
};
use std::ptr;
/** A compact `Vec` of bits, whose cursor and storage type can be customized.
`BitVec` is a newtype wrapper over `Vec`, and as such is exactly three words in
size on the stack.
**IMPORTANT NOTE:** It is **wildly** unsafe to use `mem::transmute` between
`Vec<T>` and `BitVec<_, T>`, because `BitVec` achieves its size by using the
length field of the underlying `Vec` to count bits, rather than elements. This
means that it has a fixed maximum bit width regardless of element type, and the
length field will always be horrifically wrong to be treated as a `Vec`. Safe
methods exist to move between `Vec` and `BitVec` – USE THEM.
`BitVec` takes two type parameters.
- `E: Endian` must be an implementor of the `Endian` trait. `BitVec` takes a
`PhantomData` marker for access to the associated functions, and will never
make use of an instance of the trait. The default implementations,
`LittleEndian` and `BigEndian`, are zero-sized, and any further
implementations should be as well, as the invoked functions will never receive
state.
- `T: Bits` must be a primitive type. Rust decided long ago to not provide a
unifying trait over the primitives, so `Bits` provides access to just enough
properties of the primitives for `BitVec` to use. This trait is sealed against
downstream implementation, and can only be implemented in this crate.
**/
pub struct BitVec<E = BigEndian, T = u8>
where E: Endian, T: Bits {
inner: Vec<T>,
_endian: PhantomData<E>,
}
impl<E, T> BitVec<E, T>
where E: Endian, T: Bits {
/// Constructs a new, empty, `BitVec<E, T>`.
///
/// The vector will not allocate until bits are pushed onto it.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv: BitVec = BitVec::new();
/// assert!(bv.is_empty());
/// assert_eq!(bv.capacity(), 0);
/// ```
pub fn new() -> Self {
Self {
inner: Vec::new(),
_endian: PhantomData,
}
}
/// Constructs a new, empty `BitVec<T>` with the specified capacity.
///
/// The vector will be able to hold exactly `capacity` elements without
/// reallocating. If `capacity` is 0, the vector will not allocate.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv: BitVec = BitVec::with_capacity(10);
/// assert!(bv.is_empty());
/// assert!(bv.capacity() >= 2);
/// ```
pub fn with_capacity(capacity: usize) -> Self {
let (elts, bits) = T::split(capacity);
let cap = elts + if bits > 0 { 1 } else { 0 };
Self {
inner: Vec::with_capacity(cap),
_endian: PhantomData,
}
}
/// Returns the number of bits the vector can hold without reallocating.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv: BitVec = BitVec::with_capacity(10);
/// assert!(bv.is_empty());
/// assert!(bv.capacity() >= 2);
/// ```
pub fn capacity(&self) -> usize {
assert!(self.inner.capacity() <= T::MAX_ELT, "Capacity overflow");
self.inner.capacity() << T::BITS
}
/// Appends a bit to the collection.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv: BitVec = BitVec::new();
/// assert!(bv.is_empty());
/// bv.push(true);
/// assert_eq!(bv.len(), 1);
/// assert!(bv[0]);
/// ```
pub fn push(&mut self, value: bool) {
assert!(self.len() < ::std::usize::MAX, "Vector will overflow!");
let bit = self.bits();
// Get a cursor to the bit that matches the semantic count.
let cursor = E::curr::<T>(bit);
// Insert `value` at the current cursor.
self.do_with_tail(|elt| elt.set(cursor, value));
// If the cursor is at the *end* of an element, this bit will finish it
// and the element count needs to be incremented.
if bit == T::MASK {
let elts = self.elts();
assert!(elts <= T::MAX_ELT, "Elements will overflow");
unsafe { self.set_elts(elts + 1) };
}
// Increment the bit counter, wrapping if need be.
unsafe { self.set_bits((bit + 1) & T::MASK); }
}
/// Removes the last bit from the collection.
///
/// Returns `None` if the collection is empty.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv: BitVec = BitVec::new();
/// assert!(bv.is_empty());
/// bv.push(true);
/// assert_eq!(bv.len(), 1);
/// assert!(bv[0]);
///
/// assert!(bv.pop().unwrap());
/// assert!(bv.is_empty());
/// assert!(bv.pop().is_none());
/// ```
pub fn pop(&mut self) -> Option<bool> {
if self.inner.is_empty() {
return None;
}
// Vec.pop never calls the allocator, it just decrements the length
// counter. Similarly, this just decrements the length counter and
// yields the bit underneath it.
let cur = self.len() - 1;
let ret = self.get(cur);
unsafe { self.inner.set_len(cur); }
Some(ret)
}
/// Returns a borrowing, read-only, iterator over the underlying `BitSlice`.
///
/// It is impossible to create an iterator that yields mutable references to
/// bits, so there is no corresponding `iter_mut` function.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![0, 1, 0, 1, 0];
/// let mut iter = bv.iter();
/// for bit in iter {
/// print!("{} ", bit as u8);
/// }
/// println!();
/// //> prints "0 1 0 1 0"
/// ```
pub fn iter(&self) -> <&BitSlice<E, T> as IntoIterator>::IntoIter {
(&*self as &BitSlice<E, T>).into_iter()
}
/// Empty out the `BitVec`, resetting it to length zero.
///
/// This does not affect the memory store! It will not zero the raw memory
/// nor will it deallocate.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![1; 30];
/// assert_eq!(bv.len(), 30);
/// assert!(bv.iter().all(|b| b));
/// bv.clear();
/// assert!(bv.is_empty());
/// ```
///
/// After `clear()`, `bv` will no longer show raw memory, so the above test
/// cannot show that the underlying memory is untouched. This is also an
/// implementation detail on which you should not rely.
pub fn clear(&mut self) {
self.do_with_vec(|v| v.clear());
}
/// Reserve capacity for additional bits.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![1; 5];
/// let cap = bv.capacity();
/// bv.reserve(10);
/// assert!(bv.capacity() >= cap + 10);
/// ```
pub fn reserve(&mut self, additional: usize) {
let (cur_elts, cur_bits) = T::split(self.raw_len());
let (new_elts, new_bits) = T::split(additional);
let (elts, bits) = (cur_elts + new_elts, cur_bits + new_bits);
let extra = elts + if bits > 0 { 1 } else { 0 };
assert!(self.raw_len() + extra <= T::MAX_ELT, "Capacity would overflow");
self.do_with_vec(|v| v.reserve(extra));
}
/// Shrink the capacity to fit at least as much as is needed, but with as
/// little or as much excess as the allocator chooses.
///
/// This may or may not deallocate tail space, as the allocator sees fit.
/// This does not zero the abandoned memory.
pub fn shrink_to_fit(&mut self) {
self.do_with_vec(|v| v.shrink_to_fit());
}
/// Shrinks the `BitVec` to the given size, dropping all excess storage.
///
/// This does not affect the memory store! It will not zero the raw memory
/// nor will it deallocate.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![1; 30];
/// assert_eq!(bv.len(), 30);
/// let cap = bv.capacity();
/// bv.truncate(10);
/// assert_eq!(bv.len(), 10);
/// assert_eq!(bv.capacity(), cap);
/// ```
pub fn truncate(&mut self, len: usize) {
let (elts, bits) = T::split(len);
let trunc = elts + if bits > 0 { 1 } else { 0 };
self.do_with_vec(|v| v.truncate(trunc));
unsafe { self.set_len(len); }
}
/// Convert the `BitVec` into a boxed slice of storage elements. This drops
/// all `BitVec` management semantics, including partial fill status of the
/// trailing element or endianness, and gives ownership the raw storage.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv: BitVec<BigEndian, u8> = bitvec![1; 64];
/// let bytes: Box<[u8]> = bv.into_boxed_slice();
/// assert_eq!(bytes.len(), 8);
/// for byte in bytes.iter() {
/// assert_eq!(*byte, !0);
/// }
/// ```
pub fn into_boxed_slice(self) -> Box<[T]> {
let raw = self.raw_len();
let buf = unsafe {
let mut buf = ptr::read(&self.inner);
mem::forget(self);
buf.set_len(raw);
buf
};
buf.into_boxed_slice()
}
/// Sets the bit count to a new value.
///
/// This utility function unconditionally sets the bottom `T::BITS` bits of
/// `inner.len` to reflect how many bits of the tail are live. It should
/// only be used when adjusting the liveness of the tail.
unsafe fn set_bits(&mut self, count: u8) {
assert!(count <= T::MASK, "Index out of range");
let elt = self.len() & !(T::MASK as usize);
self.inner.set_len(elt | count as usize);
}
/// Sets the element count to a new value.
///
/// This utility function unconditionally sets the rest of the bits of
/// `inner.len` to reflect how many elements in the `Vec` are fully filled.
/// It will always be one fewer than the number of elements the `Vec` would
/// consider live, were it consulted. It should only be used when adjusting
/// the liveness of the underlying `Vec`.
unsafe fn set_elts(&mut self, count: usize) {
assert!(count <= T::MAX_ELT, "Length out of range");
let bit = self.len() & (T::MASK as usize);
self.inner.set_len(T::join(count, bit as u8));
}
/// Set the length directly.
unsafe fn set_len(&mut self, len: usize) {
self.inner.set_len(len);
}
/// The actual number of live elements in the underlying store.
///
/// If `bits()` is 0, then the cursor is hovering over non-live memory, and
/// all the elements are full, so `elts()` is correct. If `bits()` is
/// non-zero, then a partial element exists about which `elts()` does not
/// know, and must be added.
fn raw_len(&self) -> usize {
self.elts() + if self.bits() > 0 { 1 } else { 0 }
}
/// Executes some operation with the storage `Vec` in sane condition.
///
/// The given function receives a sane `Vec<T>`, with the `len` attribute
/// set to reflect the reality of elements in use. The storage `Vec` is then
/// set back to the correct state for `BitVec` use after the given function
/// ends.
///
/// The given function may not return a reference into the `Vec`. It must
/// return a standalone value, or nothing. If access into the buffer is
/// needed, use `AsRef` or `AsMut`.
///
/// NOTE: If the operation changes the length of the underlying `Vec`, this
/// will assume that all elements are full, and the `bits()` cursor will be
/// wiped.
fn do_with_vec<F: Fn(&mut Vec<T>) -> R, R>(&mut self, op: F) -> R {
// Keep the old length in order to (maybe) restore it.
let len = self.len();
// Get the number of storage elements the `Vec` considers live.
let old = self.raw_len();
// `BitVec.inner.len` is used to store both element count and bit count
// which is a state that *cannot* be passed to operations on the `Vec`
// itself. Set the `Vec.len` member to be the number of live elements.
unsafe { self.inner.set_len(old); }
// Do the operation.
let ret = op(&mut self.inner);
// The operation may have changed how many elements are considered live
// so we must get the new count, manipulate it, and use that. (If the
// operation clears the `Vec`, then zero is a perfectly valid `len`.)
// There is not enough information in this call to set `bits()`
// correctly after a `Vec`-mutating call, so it is up to the caller to
// ensure that the `bits()` segment is correct after this returns.
let new = self.inner.len();
assert!(new <= T::MAX_ELT, "Length out of range!");
if new == old + 1 {
eprintln!("Did you just call `Vec.push` in `do_with_vec`? Don't do that! Use `BitVec.push_elt`.");
}
// If the length is unchanged before and after the call, restore the
// original bit length.
if new == old {
unsafe {
self.inner.set_len(len);
}
}
// If the length is different, give up and assume all the elements are
// full. Use `push_elt()` to manipulate allocations.
else {
unsafe {
self.set_bits(0);
self.set_elts(new);
}
}
ret
}
/// Executes some operation with the tail storage element.
///
/// If the bit cursor is at zero when this is called, then the current tail
/// element is not live, and one will be pushed onto the underlying `Vec`,
/// and this fresh element will be provided to the operation.
fn do_with_tail<F: Fn(&mut T) -> R, R>(&mut self, op: F) -> R {
// If the cursor is at zero, there is not necessarily an element
// allocated underneath it. Have the `Vec` try to push an element,
// allocating if need be, for use.
if self.bits() == 0 {
self.push_elt();
}
let old_len = self.inner.len();
let elts = self.elts();
// elts() counts how many elements are full. There is always one more
// element allocated and live than are full, so inform the `Vec` that
// it has `elts() + 1` elements live, act on the last one, and then
// restore the length to the correct value for `BitVec`'s purposes.
unsafe {
self.inner.set_len(elts + 1);
let ret = op(&mut self.inner[elts]);
self.inner.set_len(old_len);
ret
}
}
/// Push an element onto the end of the underlying store. This may or may
/// not call the allocator. After the element ensured to be allocated, the
/// old length is restored.
fn push_elt(&mut self) {
let len = self.len();
self.do_with_vec(|v| v.push(Default::default()));
unsafe {
self.inner.set_len(len);
}
}
/// Formats the debug header for the type
///
/// The body format is provided by `BitSlice`.
fn fmt_header(&self, fmt: &mut Formatter) -> fmt::Result {
// write!(fmt, "BitVec<{}, {}> {{ ptr: {:p}, len_bits: {}, cap_elts: {} }} [",
write!(fmt, "BitVec<{}, {}>",
E::TY,
T::TY,
// self.inner.as_ptr(),
// self.inner.len(),
// self.inner.capacity(),
)
}
}
/// Gives write access to all live elements in the underlying storage, including
/// the partially-filled tail.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: &[u8] = &[5, 10, 15, 20, 25];
/// let mut bv: BitVec = src.into();
/// for elt in bv.as_mut() {
/// *elt += 2;
/// }
/// assert_eq!(&[7, 12, 17, 22, 27], bv.as_ref());
/// ```
impl<E, T> AsMut<[T]> for BitVec<E, T>
where E: Endian, T: Bits {
fn as_mut(&mut self) -> &mut [T] {
let ptr = self.inner.as_ptr() as *mut T;
let raw = self.raw_len();
unsafe { ::std::slice::from_raw_parts_mut(ptr, raw) }
}
}
/// Gives read access to all live elements in the underlying storage, including
/// the partially-filled tail.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: &[u8] = &[5, 10, 15, 20, 25];
/// let bv: BitVec = src.into();
/// assert_eq!(&[5, 10, 15, 20, 25], bv.as_ref());
/// ```
impl<E, T> AsRef<[T]> for BitVec<E, T>
where E: Endian, T: Bits {
fn as_ref(&self) -> &[T] {
let ptr = self.inner.as_ptr();
let raw = self.raw_len();
unsafe { ::std::slice::from_raw_parts(ptr, raw) }
}
}
/// Performs the Boolean AND operation between each element of a `BitVec` and
/// anything that can provide a stream of `bool` values (such as another
/// `BitVec`, or any `bool` generator of your choice). The `BitVec` emitted will
/// have the length of the shorter sequence of bits -- if one is longer than the
/// other, the extra bits will be ignored.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// let rhs = bitvec![BigEndian, u8; 0, 0, 1, 1];
/// let and = lhs & rhs;
/// assert_eq!("0001", &format!("{}", and));
/// ```
impl<E, T, I> BitAnd<I> for BitVec<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
type Output = Self;
fn bitand(mut self, rhs: I) -> Self::Output {
self &= rhs;
self
}
}
/// Performs the Boolean AND operation in place on a `BitVec`, using a stream of
/// `bool` values as the other bit for each operation. If the other stream is
/// shorter than `self`, `self` will be truncated when the other stream expires.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// src &= bitvec![BigEndian, u8; 0, 0, 1, 1];
/// assert_eq!("0001", &format!("{}", src));
/// ```
impl<E, T, I> BitAndAssign<I> for BitVec<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
fn bitand_assign(&mut self, rhs: I) {
let mut len = 0;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) & other;
self.set(idx, val);
len += 1;
}
self.truncate(len);
}
}
/// Performs the Boolean OR operation between each element of a `BitVec` and
/// anything that can provide a stream of `bool` values (such as another
/// `BitVec`, or any `bool` generator of your choice). The `BitVec` emitted will
/// have the length of the shorter sequence of bits -- if one is longer than the
/// other, the extra bits will be ignored.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// let rhs = bitvec![BigEndian, u8; 0, 0, 1, 1];
/// let or = lhs | rhs;
/// assert_eq!("0111", &format!("{}", or));
/// ```
impl<E, T, I> BitOr<I> for BitVec<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
type Output = Self;
fn bitor(mut self, rhs: I) -> Self::Output {
self |= rhs;
self
}
}
/// Performs the Boolean OR operation in place on a `BitVec`, using a stream of
/// `bool` values as the other bit for each operation. If the other stream is
/// shorter than `self`, `self` will be truncated when the other stream expires.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// src |= bitvec![BigEndian, u8; 0, 0, 1, 1];
/// assert_eq!("0111", &format!("{}", src));
/// ```
impl<E, T, I> BitOrAssign<I> for BitVec<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
fn bitor_assign(&mut self, rhs: I) {
let mut len = 0;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) | other;
self.set(idx, val);
len += 1;
}
self.truncate(len);
}
}
/// Performs the Boolean XOR operation between each element of a `BitVec` and
/// anything that can provide a stream of `bool` values (such as another
/// `BitVec`, or any `bool` generator of your choice). The `BitVec` emitted will
/// have the length of the shorter sequence of bits -- if one is longer than the
/// other, the extra bits will be ignored.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// let rhs = bitvec![BigEndian, u8; 0, 0, 1, 1];
/// let xor = lhs ^ rhs;
/// assert_eq!("0110", &format!("{}", xor));
/// ```
impl<E, T, I> BitXor<I> for BitVec<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
type Output = Self;
fn bitxor(mut self, rhs: I) -> Self::Output {
self ^= rhs;
self
}
}
/// Performs the Boolean XOR operation in place on a `BitVec`, using a stream of
/// `bool` values as the other bit for each operation. If the other stream is
/// shorter than `self`, `self` will be truncated when the other stream expires.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// src ^= bitvec![BigEndian, u8; 0, 0, 1, 1];
/// assert_eq!("0110", &format!("{}", src));
/// ```
impl<E, T, I> BitXorAssign<I> for BitVec<E, T>
where E: Endian, T: Bits, I: IntoIterator<Item=bool> {
fn bitxor_assign(&mut self, rhs: I) {
let mut len = 0;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) ^ other;
self.set(idx, val);
len += 1;
}
self.truncate(len);
}
}
/// Signifies that `BitSlice` is the borrowed form of `BitVec`.
impl<E, T> Borrow<BitSlice<E, T>> for BitVec<E, T>
where E: Endian, T: Bits {
/// Borrows the `BitVec` as a `BitSlice`.
fn borrow(&self) -> &BitSlice<E, T> {
&*self
}
}
/// Signifies that `BitSlice` is the borrowed form of `BitVec`.
impl<E, T> BorrowMut<BitSlice<E, T>> for BitVec<E, T>
where E: Endian, T: Bits {
/// Mutably borows the `BitVec` as a `BitSlice`.
fn borrow_mut(&mut self) -> &mut BitSlice<E, T> {
&mut *self
}
}
impl<E, T> Clone for BitVec<E, T>
where E: Endian, T: Bits {
fn clone(&self) -> Self {
let mut out = Self::from(self.as_ref());
unsafe {
out.inner.set_len(self.len());
}
out
}
fn clone_from(&mut self, other: &Self) {
self.clear();
self.reserve(other.len());
unsafe {
let src = other.as_ptr();
let dst = self.as_mut_ptr();
let len = other.raw_len();
ptr::copy_nonoverlapping(src, dst, len);
}
}
}
/// Prints the `BitVec` for debugging.
///
/// The output is of the form `BitVec<E, T> [ELT, *]`, where `<E, T>` is the
/// endianness and element type, with square brackets on each end of the bits
/// and all the live elements in the vector printed in binary. The printout is
/// always in semantic order, and may not reflect the underlying store. To see
/// the underlying store, use `format!("{:?}", self.as_ref());` instead.
///
/// The alternate character `{:#?}` prints each element on its own line, rather
/// than separated by a space.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![LittleEndian, u16; 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1];
/// assert_eq!("BitVec<LittleEndian, u16> [0101000011110101]", &format!("{:?}", bv));
/// ```
impl<E, T> Debug for BitVec<E, T>
where E: Endian, T: Bits {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
let alt = fmt.alternate();
self.fmt_header(fmt)?;
fmt.write_str(" [")?;
if alt { writeln!(fmt)?; }
self.fmt_body(fmt, true)?;
if alt { writeln!(fmt)?; }
fmt.write_str("]")
}
}
/// Reborrow the `BitVec` as a `BitSlice`.
///
/// This mimics the separation between `Vec<T>` and `[T]`.
impl<E, T> Deref for BitVec<E, T>
where E: Endian, T: Bits {
type Target = BitSlice<E, T>;
fn deref(&self) -> &Self::Target {
// `BitVec`'s representation of its inner `Vec` matches exactly the
// invariants of how `BitSlice` references must look. This is fine.
unsafe { mem::transmute(&self.inner as &[T]) }
}
}
/// Reborrow the `BitVec` as a `BitSlice`.
///
/// This mimics the separation between `Vec<T>` and `[T]`.
impl<E, T> DerefMut for BitVec<E, T>
where E: Endian, T: Bits {
fn deref_mut(&mut self) -> &mut Self::Target {
unsafe { mem::transmute(&mut self.inner as &mut [T]) }
}
}
/// Prints the `BitVec` for displaying.
///
/// This prints each element in turn, formatted in binary in semantic order (so
/// the first bit seen is printed first and the last bit seen printed last).
/// Each element of storage is separated by a space for ease of reading.
///
/// The alternate character `{:#}` prints each element on its own line.
///
/// To see the in-memory representation, use `AsRef` to get access to the raw
/// elements and print that slice instead.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 1, 0, 0, 1, 0, 1, 1, 0, 1];
/// assert_eq!("01001011 01", &format!("{}", bv));
/// ```
impl<E, T> Display for BitVec<E, T>
where E: Endian, T: Bits {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
self.fmt_body(fmt, false)
}
}
/// Readies the underlying storage for Drop.
impl<E, T> Drop for BitVec<E, T>
where E: Endian, T: Bits {
fn drop(&mut self) {
// If the `Vec` is non-empty, set the length to the number of used
// elements as preparation for drop. The bits do not need to be wiped.
//
// If we don't do this, the `Vec` drop will treat the bit total as the
// number of elements and try to loop through all of them, which will
// not take 2 ** T::BITS times as long to run as expected, because
// it'll segfault.
let raw = self.raw_len();
unsafe { self.inner.set_len(raw); }
}
}
/// Extend a `BitVec` with the contents of another bitstream.
///
/// At present, this just calls `.push()` in a loop. When specialization becomes
/// available, it will be able to more intelligently perform bulk moves from the
/// source into `self` when the source is `BitSlice`-compatible.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![0; 4];
/// bv.extend(bitvec![1; 4]);
/// assert_eq!("00001111", &format!("{}", bv));
/// ```
impl<E, T> Extend<bool> for BitVec<E, T>
where E: Endian, T: Bits {
fn extend<I>(&mut self, src: I)
where I: IntoIterator<Item=bool> {
let iter = src.into_iter();
match iter.size_hint() {
(_, Some(hi)) => self.reserve(hi),
(lo, None) => self.reserve(lo),
}
for bit in iter {
self.push(bit);
}
self.shrink_to_fit();
}
}
/// Clones a `BitSlice` into an owned `BitVec`.
impl<'a, E, T> From<&'a BitSlice<E, T>> for BitVec<E, T>
where E: Endian, T: 'a + Bits {
fn from(src: &'a BitSlice<E, T>) -> Self {
src.to_owned()
}
}
/// Builds a `BitVec` out of a slice of `bool`.
impl<'a, E, T> From<&'a [bool]> for BitVec<E, T>
where E: Endian, T: 'a + Bits {
fn from(src: &'a [bool]) -> Self {
let mut out = Self::with_capacity(src.len());
for bit in src {
out.push(*bit);
}
out
}
}
/// Build a `BitVec` out of a borrowed slice of elements.
///
/// This copies the memory as-is from the source buffer into the new `BitVec`.
/// The source buffer will be unchanged by this operation, so you don't need to
/// worry about using the correct cursor type.
///
/// This operation does a copy from the source buffer into a new allocation, as
/// it can only borrow the source and not take ownership.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: &[u8] = &[5, 10];
/// let bv: BitVec = src.into();
/// assert_eq!("00000101 00001010", &format!("{}", bv));
impl<'a, E, T> From<&'a [T]> for BitVec<E, T>
where E: Endian, T: 'a + Bits {
fn from(src: &'a [T]) -> Self {
use std::ptr::copy_nonoverlapping;
let len = src.len();
assert!(len <= T::MAX_ELT, "Source slice too long!");
let mut out = Self::with_capacity(len << T::BITS);
out.do_with_vec(|v| unsafe {
copy_nonoverlapping(src.as_ptr(), v.as_ptr() as *mut T, len);
v.set_len(len);
});
out
}
}
/// Build a `BitVec` out of an owned slice of elements.
///
/// This moves the memory as-is from the source buffer into the new `BitVec`.
/// The source buffer will be unchanged by this operation, so you don't need to
/// worry about using the correct cursor type.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: Box<[u8]> = Box::new([3, 6, 9, 12, 15]);
/// let bv: BitVec = src.into();
/// assert_eq!("00000011 00000110 00001001 00001100 00001111", &format!("{}", bv));
/// ```
impl<E, T> From<Box<[T]>> for BitVec<E, T>
where E: Endian, T: Bits {
fn from(src: Box<[T]>) -> Self {
assert!(src.len() <= T::MAX_ELT, "Source slice too long!");
Self::from(Vec::from(src))
}
}
/// Build a `BitVec` out of a `Vec` of elements.
///
/// This moves the memory as-is from the source buffer into the new `BitVec`.
/// The source buffer will be unchanged by this operation, so you don't need to
/// worry about using the correct cursor type.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: Vec<u8> = vec![1, 2, 4, 8];
/// let bv: BitVec = src.into();
/// assert_eq!("00000001 00000010 00000100 00001000", &format!("{}", bv));
/// ```
impl<E, T> From<Vec<T>> for BitVec<E, T>
where E: Endian, T: Bits {
fn from(src: Vec<T>) -> Self {
let elts = src.len();
assert!(elts <= T::MAX_ELT, "Source vector too long!");
let mut out = Self {
inner: src,
_endian: PhantomData::<E>,
};
unsafe {
out.set_bits(0);
out.set_elts(elts);
}
out
}
}
/// Change cursors on a `BitVec` without mutating the underlying data.
///
/// I don't know why this would be useful at the time of writing, as the `From`
/// implementations on collections crawl the collection elements in the order
/// requested and so the source and destination storage collections will be
/// bitwise identical, but here's the option anyway.
///
/// If the tail element is partially filled, then this operation will shift the
/// tail element so that the edge of the filled section is on the correct edge
/// of the tail element.
impl<T: Bits> From<BitVec<LittleEndian, T>> for BitVec<BigEndian, T> {
fn from(mut src: BitVec<LittleEndian, T>) -> Self {
let bits = src.bits();
// If bits() is zero, then the tail is full and cannot shift.
// If bits() is nonzero, then the shamt is WIDTH - bits().
// E.g. a WIDTH of 32 and a bits() of 31 means bit 30 is the highest
// bit set, and the element should shl by 1 so that bit 31 is the
// highest bit set, and bit 0 will be empty.
if bits > 0 {
let shamt = T::WIDTH - bits;
src.do_with_tail(|elt| *elt <<= shamt);
}
// The cursor is stored in PhantomData, and known only to the complier.
// Transmutation is perfectly safe, since the only concrete item is the
// storage, which this explicitly does not alter.
unsafe { mem::transmute(src) }
}
}
/// Change cursors on a `BitVec` without mutating the underlying data.
///
/// I don't know why this would be useful at the time of writing, as the `From`
/// implementations on collections crawl the collection elements in the order
/// requested and so the source and destination storage collections will be
/// bitwise identical, but here's the option anyway.
///
/// If the tail element is partially filled, then this operation will shift the
/// tail element so that the edge of the filled section is on the correct edge
/// of the tail element.
impl<T: Bits> From<BitVec<BigEndian, T>> for BitVec<LittleEndian, T> {
fn from(mut src: BitVec<BigEndian, T>) -> Self {
let bits = src.bits();
if bits > 0 {
let shamt = T::WIDTH - bits;
src.do_with_tail(|elt| *elt >>= shamt);
}
unsafe { mem::transmute(src) }
}
}
/// Permits the construction of a `BitVec` by using `.collect()` on an iterator
/// of `bool`
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// use std::iter::repeat;
/// let bv: BitVec = repeat(true).take(4).chain(repeat(false).take(4)).collect();
/// assert_eq!("11110000", &format!("{}", bv));
/// ```
impl<E, T> FromIterator<bool> for BitVec<E, T>
where E: Endian, T: Bits {
fn from_iter<I: IntoIterator<Item=bool>>(src: I) -> Self {
let iter = src.into_iter();
let mut out = match iter.size_hint() {
(_, Some(len)) |
(len, _) if len > 0 => Self::with_capacity(len),
_ => Self::new(),
};
for bit in iter {
out.push(bit);
}
out
}
}
/// Get the bit at a specific index. The index must be less than the length of
/// the `BitVec`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 0, 0, 0, 0, 0, 1, 0];
/// assert!(!bv[7]); // ---------------------------------^ | |
/// assert!( bv[8]); //-------------------------------------^ |
/// assert!(!bv[9]); // ---------------------------------------^
/// ```
///
/// If the index is greater than or equal to the length, indexing will panic.
///
/// The below test will panic when accessing index 1, as only index 0 is valid.
///
/// ```rust,should_panic
/// use bitvec::*;
/// let mut bv: BitVec = BitVec::new();
/// bv.push(true);
/// bv[1];
/// ```
impl<E, T> Index<usize> for BitVec<E, T>
where E: Endian, T: Bits {
type Output = bool;
fn index(&self, cursor: usize) -> &Self::Output {
assert!(cursor < self.inner.len(), "Index out of range!");
self.index(T::split(cursor))
}
}
/// Get the bit in a specific element. The element index must be less than or
/// equal to the value returned by `elts()`, and the bit index must be less
/// than the width of the storage type.
///
/// If the `BitVec` has a partially-filled tail, then the value returned by
/// `elts()` is a valid index.
///
/// The element and bit indices are combined using `Bits::join` for the storage
/// type.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 1, 1, 1, 1, 0, 0, 0, 0, 0, 1];
/// assert!(bv[(1, 1)]); // -----------------------------------^
/// ```
impl<E, T> Index<(usize, u8)> for BitVec<E, T>
where E: Endian, T: Bits {
type Output = bool;
/// Index into a `BitVec` using a known element index and a count into that
/// element. The count must not be converted for endianness outside the call
fn index(&self, (elt, bit): (usize, u8)) -> &Self::Output {
assert!(T::join(elt, bit) < self.len(), "Index out of range!");
match (self.inner[elt]).get(E::curr::<T>(bit)) {
true => &TRUE,
false => &FALSE,
}
}
}
/// Produces an iterator over all the bits in the vector.
///
/// This iterator follows the ordering in the vector type, and implements
/// `ExactSizeIterator`, since `BitVec`s always know exactly how large they are,
/// and `DoubleEndedIterator`, since they have known ends.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 1, 1, 1, 1, 0, 0, 0, 0];
/// let mut count = 0;
/// for bit in bv {
/// if bit { count += 1; }
/// }
/// assert_eq!(count, 4);
/// ```
impl<E, T> IntoIterator for BitVec<E, T>
where E: Endian, T: Bits {
type Item = bool;
#[doc(hidden)]
type IntoIter = IntoIter<E, T>;
fn into_iter(self) -> Self::IntoIter {
Self::IntoIter::from(self)
}
}
/// Flips all bits in the vector.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv: BitVec<BigEndian, u32> = BitVec::from(&[0u32] as &[u32]);
/// let flip = !bv;
/// assert_eq!(!0u32, flip.as_ref()[0]);
/// ```
impl<E, T> Not for BitVec<E, T>
where E: Endian, T: Bits {
type Output = Self;
// Because self does not have to interact with any other `BitVec`, and bits
// beyond `BitVec.len()` are uninitialized and don't matter, this is free
// to simply negate the elements in place and then return self.
fn not(mut self) -> Self::Output {
for elt in self.as_mut() {
*elt = !*elt;
}
self
}
}
__bitvec_shift!(u8, u16, u32, u64, i8, i16, i32, i64);
/// Shifts all bits in the vector to the left – DOWN AND TOWARDS THE FRONT.
///
/// On primitives, the left-shift operator `<<` moves bits away from origin and
/// towards the ceiling. This is because we label the bits in a primitive with
/// the minimum on the right and the maximum on the left, which is big-endian
/// bit order. This increases the value of the primitive being shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, left-shifting moves bits towards the **minimum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `<<`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `>>` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// left to their old value.
///
/// The length of the vector is decreased by the shift amount.
///
/// If the shift amount is greater than the length, the vector calls `clear()`
/// and zeroes its memory. This is *not* an error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0001_1100, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// let ls = bv << 2usize;
/// assert_eq!("0111", &format!("{}", ls));
/// assert_eq!(0b0111_0000, ls.as_ref()[0]);
/// assert_eq!(ls.len(), 4);
/// ```
impl<E, T> Shl<usize> for BitVec<E, T>
where E: Endian, T: Bits {
type Output = Self;
fn shl(mut self, shamt: usize) -> Self::Output {
self <<= shamt;
self
}
}
/// Shifts all bits in the vector to the left – DOWN AND TOWARDS THE FRONT.
///
/// On primitives, the left-shift operator `<<` moves bits away from origin and
/// towards the ceiling. This is because we label the bits in a primitive with
/// the minimum on the right and the maximum on the left, which is big-endian
/// bit order. This increases the value of the primitive being shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, left-shifting moves bits towards the **minimum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `<<`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `>>` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// left to their old value.
///
/// The length of the vector is decreased by the shift amount.
///
/// If the shift amount is greater than the length, the vector calls `clear()`
/// and zeroes its memory. This is *not* an error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![LittleEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0011_1000, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// bv <<= 2;
/// assert_eq!("0111", &format!("{}", bv));
/// assert_eq!(0b0000_1110, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 4);
/// ```
impl<E, T> ShlAssign<usize> for BitVec<E, T>
where E: Endian, T: Bits {
fn shl_assign(&mut self, shamt: usize) {
let len = self.len();
if shamt >= len {
self.clear();
let buf = self.as_mut();
let ptr = buf.as_mut_ptr();
let len = buf.len();
unsafe { ::std::ptr::write_bytes(ptr, 0, len); }
return;
}
for idx in shamt .. len {
let val = self.get(idx);
self.set(idx - shamt, val);
}
let trunc = len - shamt;
for idx in trunc .. len {
self.set(idx, false);
}
self.truncate(trunc);
}
}
/// Shifts all bits in the vector to the right – UP AND TOWARDS THE BACK.
///
/// On primitives, the right-shift operator `>>` moves bits towards the origin
/// and away from the ceiling. This is because we label the bits in a primitive
/// with the minimum on the right and the maximum on the left, which is
/// big-endian bit order. This decreases the value of the primitive being
/// shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, right-shifting moves bits towards the **maximum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `>>`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `<<` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// left to their old value.
///
/// The length of the vector is increased by the shift amount.
///
/// If the new length of the vector would overflow, a panic occurs. This *is* an
/// error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0001_1100, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// let rs = bv >> 2usize;
/// assert_eq!("00000111", &format!("{}", rs));
/// assert_eq!(0b0000_0111, rs.as_ref()[0]);
/// assert_eq!(rs.len(), 8);
/// ```
impl<E, T> Shr<usize> for BitVec<E, T>
where E: Endian, T: Bits {
type Output = Self;
fn shr(mut self, shamt: usize) -> Self::Output {
self >>= shamt;
self
}
}
/// Shifts all bits in the vector to the right – UP AND TOWARDS THE BACK.
///
/// On primitives, the right-shift operator `>>` moves bits towards the origin
/// and away from the ceiling. This is because we label the bits in a primitive
/// with the minimum on the right and the maximum on the left, which is
/// big-endian bit order. This decreases the value of the primitive being
/// shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, right-shifting moves bits towards the **maximum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `>>`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `<<` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// left to their old value.
///
/// The length of the vector is increased by the shift amount.
///
/// If the new length of the vector would overflow, a panic occurs. This *is* an
/// error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![LittleEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0011_1000, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// bv >>= 2;
/// assert_eq!("00000111", &format!("{}", bv));
/// assert_eq!(0b1110_0000, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 8);
/// ```
impl<E, T> ShrAssign<usize> for BitVec<E, T>
where E: Endian, T: Bits {
fn shr_assign(&mut self, shamt: usize) {
let old_len = self.len();
// Implement `Extend` to make this more efficient
for _ in 0 .. shamt {
self.push(false);
}
for idx in (0 .. old_len).rev() {
let val = self.get(idx);
self.set(idx + shamt, val);
}
for idx in 0 .. shamt {
self.set(idx, false);
}
}
}
/// Iterates over an owned `BitVec`.
#[doc(hidden)]
pub struct IntoIter<E, T>
where E: Endian, T: Bits {
bv: BitVec<E, T>,
head: usize,
tail: usize,
}
impl<E, T> IntoIter<E, T>
where E: Endian, T: Bits {
fn new(bv: BitVec<E, T>) -> Self {
let tail = bv.len();
Self {
bv,
head: 0,
tail,
}
}
fn reset(&mut self) {
self.head = 0;
self.tail = self.bv.len();
}
}
impl<E, T> DoubleEndedIterator for IntoIter<E, T>
where E: Endian, T: Bits {
/// Yield the back-most bit of the collection.
///
/// This iterator is self-resetting; when the cursor reaches the front of
/// the collection, it returns None after setting the cursor to the length
/// of the underlying collection. If the collection is not empty when this
/// occurs, then the iterator will resume at the back if called again.
fn next_back(&mut self) -> Option<Self::Item> {
if self.tail > self.head && self.tail <= self.bv.len() {
self.tail -= 1;
Some(self.bv[self.tail])
}
else {
self.reset();
None
}
}
}
impl<E, T> ExactSizeIterator for IntoIter<E, T>
where E: Endian, T: Bits {
// Override the default implementation with a fixed calculation. The type
// is guaranteed to be well-behaved, so there is no point in building two
// copies of the remnant, checking an always-safe condition, and dropping
// one.
//
// THIS IS A LOAD BEARING OVERRIDE! IF IT IS REMOVED, THEN
// Iterator::size_hint MUST BE CHANGED TO NOT CALL THIS FUNCTION, BECAUSE
// THE DEFAULT IMPLEMENTATION CALLS Iterator::size_hint! FAILURE TO DO SO
// WILL RESULT IN A VALID COMPILE AND A BLOWN STACK AT RUNTIME DUE TO
// INFINITE MUTUAL RECURSION!
fn len(&self) -> usize {
self.tail - self.head
}
}
impl<E, T> From<BitVec<E, T>> for IntoIter<E, T>
where E: Endian, T: Bits {
fn from(bv: BitVec<E, T>) -> Self {
Self::new(bv)
}
}
impl<E, T> Iterator for IntoIter<E, T>
where E: Endian, T: Bits {
type Item = bool;
/// Advances the iterator forward, yielding the front-most bit.
///
/// This iterator is self-resetting: when the cursor reaches the back of the
/// collection, it returns None after setting the cursor to zero. If the
/// collection is not empty when this occurs, then the iterator will resume
/// at the front if called again.
fn next(&mut self) -> Option<Self::Item> {
if self.head < self.tail {
let ret = self.bv[self.head];
self.head += 1;
Some(ret)
}
else {
eprintln!("{} >= {}", self.head, self.tail);
self.reset();
None
}
}
// Note that the default ExactSizeIterator::len calls this method, so
// removing that implementation will cause an infinite mutual recursion,
// only detectable *at runtime* when the stack blows.
//
// THIS METHOD MUST BE CHANGED TO NOT CALL ExactSizeIterator::len BEFORE
// REMOVING THE SPECIALIZATION FOR ESI! THE DEFAULT IMPLEMENTATION OF ESI
// CALLS THIS FUNCTION, WHICH WILL COMPILE CLEANLY AND THEN BLOW THE STACK
// AT RUNTIME DUE TO INFINITE MUTUAL RECURSION!
fn size_hint(&self) -> (usize, Option<usize>) {
let rem = ExactSizeIterator::len(self);
(rem, Some(rem))
}
/// Counts how many bits are live in the iterator, consuming it.
///
/// You are probably looking to use this on a borrowed iterator rather than
/// an owning iterator. See `BitSlice`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 1, 0, 1, 0];
/// assert_eq!(bv.into_iter().count(), 5);
/// ```
fn count(self) -> usize {
ExactSizeIterator::len(&self)
}
/// Advances the iterator by `n` bits, starting from zero.
///
/// It is not an error to advance past the end of the iterator! Doing so
/// returns `None`, and resets the iterator to its beginning.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1];
/// let mut bv_iter = bv.into_iter();
/// assert_eq!(bv_iter.len(), 4);
/// assert!(bv_iter.nth(3).unwrap());
/// ```
///
/// This example intentionally overshoots the iterator bounds, which causes
/// a reset to the initiol state. It then demonstrates that `nth` is
/// stateful, and is not an absolute index, by seeking ahead by two (to the
/// third zero bit) and then taking the bit immediately after it, which is
/// set. This shows that the argument to `nth` is how many bits to discard
/// before yielding the next.
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1];
/// let mut bv_iter = bv.into_iter();
/// assert!(bv_iter.nth(4).is_none());
/// assert!(!bv_iter.nth(2).unwrap());
/// assert!(bv_iter.nth(0).unwrap());
/// ```
fn nth(&mut self, n: usize) -> Option<bool> {
self.head += n;
self.next()
}
/// Consumes the iterator, returning only the last bit.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1];
/// assert!(bv.into_iter().last().unwrap());
/// ```
///
/// Empty iterators return `None`
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![];
/// assert!(bv.into_iter().last().is_none());
/// ```
fn last(mut self) -> Option<bool> {
self.next_back()
}
}
+1
-1
Cargo.toml

@@ -15,3 +15,3 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO

name = "bitvec"
version = "0.2.0"
version = "0.3.0"
authors = ["myrrlyn <myrrlyn@outlook.com>"]

@@ -18,0 +18,0 @@ description = "A crate for manipulating memory, bit by bit"

+39
-9
README.md

@@ -1,7 +0,14 @@

# `BitVec` – `Vec<bool>` in overdrive
# `BitVec` – Managing memory bit by bit
This crate provides a type, `BitVec`, which allows bitwise access to a region of
memory. This can be used to implement simple sets or to permit fine-grained
control over the values in regions of memory.
This crate provides packed bit-level analogues to `[T]` and `Vec<T>`. The slice
type `BitSlice` and the vector type `BitVec` allow bitwise access to a region of
memory in any endian ordering or underlying primitive type. This permits
construction of space-efficient sets or fine-grained control over the values in
a region of memory.
`BitVec` is a strict expansion of `BitSlice` to include allocation management.
Since `BitVec` is shorter to type, the rest of this document will use it by
default, and mark out sections that apply *only* to the vector type and not to
the slice type. Unless marked, assume that the text applies to both.
`BitVec` is generic over an ordering cursor, using the trait `Endian`, and the

@@ -49,2 +56,13 @@ primitive type, using the trait `Bits`. This means that `BitVec` structures can

- `BitSlice<E: Endian, T: Bits>` – the actual bit-slice reference type It is
generic over a cursor type (`E`) and storage type (`T`). Note that `BitSlice`
is unsized, and can never be held directly; it must always be behind a
reference such as `&BitSlice` or `&mut BitSlice`.
Furthermore, it is *impossible* to put `BitSlice` into any kind of intelligent
pointer such as a `Box` or `Rc`! Any work that involves managing the memory
behind a bitwise type *must* go through `BitVec` instead. This may change in
the future as I learn how to better manage this library, but for now this
limitation stands.
- `BitVec<E: Endian, T: Bits>` – the actual bit-vector structure type. It is

@@ -107,3 +125,4 @@ generic over a cursor type (`E`) and storage type (`T`).

fn main() {
let mut bv = bitvec![BigEndian, u8, 0, 1, 0, 1];
let mut bv = bitvec![BigEndian, u8; 0, 1, 0, 1];
bv.reserve(8);
for bit in repeat(false).take(4).chain(repeat(true).take(4)) {

@@ -135,8 +154,19 @@ bv.push(bit);

At this time, `BitVec` does not offer any way to relinquish owership of its
memory. It is able to take ownership of boxed slices or vectors of suitable
types, or to copy from slices, in addition to construction by macro.
Immutable and mutable access to the underlying memory is provided by the `AsRef`
and `AsMut` implementations, so the `BitVec` can be readily passed to transport
functions.
`BitVec` implements `Borrow` down to `BitSlice`, and `BitSlice` implements
`ToOwned` up to `BitVec`, so they can be used in a `Cow` or wherever this API
is desired. Any case where a `Vec`/`[T]` pair cannot be replaced with a
`BitVec`/`BitSlice` pair is a bug in this library, and a bug report is
appropriate.
`BitVec` can relinquish its owned memory as a `Box<[T]>` via the
`.into_boxed_slice()` method, and `BitSlice` can relinquish access to its memory
simply by going out of scope.
## Planned Features
`#![no_std]` support that uses core libraries for allocation, and `#![no_core]`
support that strips the vector type entirely and only provides the slice type.
+6
-1364
src/lib.rs

@@ -36,42 +36,9 @@ /*! `BitVec` – `Vec<bool>` in overdrive.

use std::clone::Clone;
use std::convert::{
AsMut,
AsRef,
From,
};
use std::fmt::{
self,
Debug,
Display,
Formatter,
};
use std::iter::{
DoubleEndedIterator,
ExactSizeIterator,
FromIterator,
Iterator,
IntoIterator,
};
use std::marker::PhantomData;
use std::mem;
use std::ops::{
BitAnd,
BitAndAssign,
BitOr,
BitOrAssign,
BitXor,
BitXorAssign,
Index,
Not,
Shl,
ShlAssign,
Shr,
ShrAssign,
};
use std::ptr;
#[macro_use]
mod macros;
mod bits;
mod endian;
mod macros;
mod slice;
mod vec;

@@ -81,2 +48,4 @@ pub use bits::Bits;

pub use macros::*;
pub use slice::BitSlice;
pub use vec::BitVec;

@@ -90,1328 +59,1 @@ // The Index trait returns references to bools, and it is impossible to make an

static FALSE: bool = false;
/** A `Vec` of bits, whose cursor and storage type can be customized.
`BitVec` is a newtype wrapper over `Vec`, and as such is exactly three words in
size on the stack.
**IMPORTANT NOTE:** It is **wildly** unsafe to use `mem::transmute` between
`Vec<T>` and `BitVec<_, T>`, because `BitVec` achieves its size by using the
length field of the underlying `Vec` to count bits, rather than elements. This
means that it has a fixed maximum bit width regardless of element type, and the
length field will always be horrifically wrong to be treated as a `Vec`. Safe
methods exist to move between `Vec` and `BitVec` – USE THEM.
`BitVec` takes two type parameters.
- `E: Endian` must be an implementor of the `Endian` trait. `BitVec` takes a
`PhantomData` marker for access to the associated functions, and will never
make use of an instance of the trait. The default implementations,
`LittleEndian` and `BigEndian`, are zero-sized, and any further
implementations should be as well, as the invoked functions will never receive
state.
- `T: Bits` must be a primitive type. Rust decided long ago to not provide a
unifying trait over the primitives, so `Bits` provides access to just enough
properties of the primitives for `BitVec` to use. This trait is sealed against
downstream implementation, and can only be implemented in this crate.
**/
pub struct BitVec<E: Endian = BigEndian, T: Bits = u8> {
inner: Vec<T>,
_endian: PhantomData<E>,
}
impl<E: Endian, T: Bits> BitVec<E, T> {
/// Constructs a new, empty, `BitVec<E, T>`.
///
/// The vector will not allocate until bits are pushed onto it.
pub fn new() -> Self {
Self {
inner: Vec::new(),
_endian: PhantomData,
}
}
/// Constructs a new, empty `BitVec<T>` with the specified capacity.
///
/// The vector will be able to hold exactly `capacity` elements without
/// reallocating. If `capacity` is 0, the vector will not allocate.
pub fn with_capacity(capacity: usize) -> Self {
let (elts, bits) = T::split(capacity);
let cap = elts + if bits > 0 { 1 } else { 0 };
Self {
inner: Vec::with_capacity(cap),
_endian: PhantomData,
}
}
/// Returns the number of bits the vector can hold without reallocating.
pub fn capacity(&self) -> usize {
assert!(self.inner.capacity() <= T::MAX_ELT, "Capacity overflow");
self.inner.capacity() << T::BITS
}
/// Returns the number of bits stored in the vector.
pub fn len(&self) -> usize {
self.inner.len()
}
/// Counts how many bits are used in the tail storage element.
///
/// This has no relation to how many elements are filled. To see the total
/// number of bits stored, use `.len()`.
///
/// The return value of this function must be passed into `E::curr::<T>` in
/// order to index the tail element directly. It is a semantic count,
/// **not** a bit index.
pub fn bits(&self) -> u8 {
(self.inner.len() & (T::MASK as usize)) as u8
}
/// Counts how many storage elements are *filled*.
///
/// This is one fewer than the number of elements *in use*, because the tail
/// element is always partially filled or empty. It will be zero when the
/// storage `Vec` is empty, or when the `BitVec` has begun filling but is
/// not yet greater than `T::MASK` bits in size.
///
/// Incidentally, this means that this is a valid index into the underlying
/// store in order to reach the tail element.
pub fn elts(&self) -> usize {
self.inner.len() >> T::BITS
}
/// Appends a bit to the collection.
pub fn push(&mut self, value: bool) {
assert!(self.len() < ::std::usize::MAX, "Vector will overflow!");
let bit = self.bits();
// Get a cursor to the bit that matches the semantic count.
let cursor = E::curr::<T>(bit);
// Insert `value` at the current cursor.
self.do_with_tail(|elt| elt.set(cursor, value));
// If the cursor is at the *end* of an element, this bit will finish it
// and the element count needs to be incremented.
if bit == T::MASK {
let elts = self.elts();
assert!(elts <= T::MAX_ELT, "Elements will overflow");
unsafe { self.set_elts(elts + 1) };
}
// Increment the bit counter, wrapping if need be.
unsafe { self.set_bits((bit + 1) & T::MASK); }
}
/// Removes the last bit from the collection.
///
/// Returns `None` if the collection is empty.
pub fn pop(&mut self) -> Option<bool> {
if self.inner.is_empty() {
return None;
}
// Vec.pop never calls the allocator, it just decrements the length
// counter. Similarly, this just decrements the length counter and
// yields the bit underneath it.
let cur = self.len() - 1;
let ret = self.get(cur);
unsafe { self.inner.set_len(cur); }
Some(ret)
}
/// Gets a bit at the given position.
pub fn get(&self, index: usize) -> bool {
assert!(index < self.len(), "Index out of range!");
self[index]
}
/// Sets a bit at the given position to the given value.
pub fn set(&mut self, index: usize, value: bool) {
assert!(index < self.len(), "Index out of range!");
let (elt, bit) = T::split(index);
self.as_mut()[elt].set(E::curr::<T>(bit), value);
}
/// Empty out the `BitVec`, resetting it to length zero.
///
/// This will not affect the allocated capacity.
pub fn clear(&mut self) {
self.do_with_vec(|v| v.clear());
}
/// Returns `true` if the vector contains no bits.
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Provides read-only iteration across the collection.
///
/// The iterator returned from this method implements `ExactSizeIterator`
/// and `DoubleEndedIterator` just as the consuming `.into_iter()` method’s
/// iterator does.
pub fn iter<'a>(&'a self) -> Iter<'a, E, T> {
self.into_iter()
}
/// Reserve capacity for additional bits.
pub fn reserve(&mut self, additional: usize) {
let (elts, bits) = T::split(additional);
let extra = elts + if bits > 0 { 1 } else { 0 };
assert!(self.raw_elts() + extra <= T::MAX_ELT, "Capacity would overflow");
self.do_with_vec(|v| v.reserve(extra));
}
/// Shrink the capacity to fit at least as much as is needed, but with as
/// little excess as the allocator chooses.
pub fn shrink_to_fit(&mut self) {
self.do_with_vec(|v| v.shrink_to_fit());
}
/// Shrinks the `BitVec` to the given size, dropping all excess storage.
///
/// This will not affect the allocated capacity.
pub fn truncate(&mut self, len: usize) {
let (elts, bits) = T::split(len);
let trunc = elts + if bits > 0 { 1 } else { 0 };
self.do_with_vec(|v| v.truncate(trunc));
unsafe { self.set_bits(bits); }
}
/// Convert the `BitVec` into a boxed slice of storage elements. This drops
/// all `BitVec` management semantics, including partial fill status of the
/// trailing element or endianness, and gives ownership the raw storage.
pub fn into_boxed_slice(self) -> Box<[T]> {
let raw = self.raw_elts();
unsafe {
let mut buf = ptr::read(&self.inner);
mem::forget(self);
buf.set_len(raw);
buf.into_boxed_slice()
}
}
/// Sets the bit count to a new value.
///
/// This utility function unconditionally sets the bottom `T::BITS` bits of
/// `inner.len` to reflect how many bits of the tail are live. It should
/// only be used when adjusting the liveness of the tail.
unsafe fn set_bits(&mut self, count: u8) {
assert!(count <= T::MASK, "Index out of range");
let elt = self.len() & !(T::MASK as usize);
self.inner.set_len(elt | count as usize);
}
/// Sets the element count to a new value.
///
/// This utility function unconditionally sets the rest of the bits of
/// `inner.len` to reflect how many elements in the `Vec` are fully filled.
/// It will always be one fewer than the number of elements the `Vec` would
/// consider live, were it consulted. It should only be used when adjusting
/// the liveness of the underlying `Vec`.
unsafe fn set_elts(&mut self, count: usize) {
assert!(count <= T::MAX_ELT, "Length out of range");
let bit = self.len() & (T::MASK as usize);
self.inner.set_len(T::join(count, bit as u8));
}
/// The actual number of live elements in the underlying store.
///
/// If `bits()` is 0, then the cursor is hovering over non-live memory, and
/// all the elements are full, so `elts()` is correct. If `bits()` is
/// non-zero, then a partial element exists about which `elts()` does not
/// know, and must be added.
fn raw_elts(&self) -> usize {
self.elts() + if self.bits() > 0 { 1 } else { 0 }
}
/// Executes some operation with the storage `Vec` in sane condition.
///
/// The given function receives a sane `Vec<T>`, with the `len` attribute
/// set to reflect the reality of elements in use. The storage `Vec` is then
/// set back to the correct state for `BitVec` use after the given function
/// ends.
///
/// The given function may not return a reference into the `Vec`. It must
/// return a standalone value, or nothing. If access into the buffer is
/// needed, use `AsRef` or `AsMut`.
///
/// NOTE: If the operation changes the length of the underlying `Vec`, this
/// will assume that all elements are full, and the `bits()` cursor will be
/// wiped.
fn do_with_vec<F: Fn(&mut Vec<T>) -> R, R>(&mut self, op: F) -> R {
// Keep the old length in order to (maybe) restore it.
let len = self.len();
// Get the number of storage elements the `Vec` considers live.
let old = self.raw_elts();
// `BitVec.inner.len` is used to store both element count and bit count
// which is a state that *cannot* be passed to operations on the `Vec`
// itself. Set the `Vec.len` member to be the number of live elements.
unsafe { self.inner.set_len(old); }
// Do the operation.
let ret = op(&mut self.inner);
// The operation may have changed how many elements are considered live
// so we must get the new count, decrement it, and use that. (If the
// operation clears the `Vec`, then zero is a perfectly valid `len`.)
// There is not enough information in this call to set `bits()`
// correctly after a `Vec`-mutating call, so it is up to the caller to
// ensure that the `bits()` segment is correct after this returns.
let new = self.inner.len();
assert!(new <= T::MAX_ELT, "Length out of range!");
// If the length is unchanged before and after the call, restore the
// original bit length.
if new == old {
unsafe {
self.inner.set_len(len);
}
}
// If the length is different, give up and assume all the elements are
// full. Use `push_elt()` and `pop_elt()` to manipulate allocations.
else {
unsafe {
self.set_bits(0);
self.set_elts(new);
}
}
ret
}
/// Executes some operation with the tail storage element.
///
/// If the bit cursor is at zero when this is called, then the current tail
/// element is not live, and one will be pushed onto the underlying `Vec`,
/// and this fresh element will be provided to the operation.
fn do_with_tail<F: Fn(&mut T) -> R, R>(&mut self, op: F) -> R {
// If the cursor is at zero, there is not necessarily an element
// allocated underneath it. Have the `Vec` try to push an element,
// allocating if need be, for use.
if self.bits() == 0 {
self.push_elt();
}
let old_len = self.inner.len();
let elts = self.elts();
// elts() counts how many elements are full. There is always one more
// element allocated and live than are full, so inform the `Vec` that
// it has `elts() + 1` elements live, act on the last one, and then
// restore the length to the correct value for `BitVec`'s purposes.
unsafe {
self.inner.set_len(elts + 1);
let ret = op(&mut self.inner[elts]);
self.inner.set_len(old_len);
ret
}
}
/// Push an element onto the end of the underlying store. This may or may
/// not call the allocator. After the element ensured to be allocated, the
/// old length is restored.
fn push_elt(&mut self) {
let len = self.len();
self.do_with_vec(|v| v.push(Default::default()));
unsafe {
self.inner.set_len(len);
}
}
fn fmt_header(&self, fmt: &mut Formatter) -> fmt::Result {
// write!(fmt, "BitVec<{}, {}> {{ ptr: {:p}, len_bits: {}, cap_elts: {} }} [",
write!(fmt, "BitVec<{}, {}> [",
E::TY,
T::TY,
// self.inner.as_ptr(),
// self.inner.len(),
// self.inner.capacity(),
)
}
/// Formats a completely-filled element into a Formatter.
fn fmt_element(fmt: &mut Formatter, elt: &T) -> fmt::Result {
Self::fmt_bits(fmt, elt, T::WIDTH)
}
/// Formats a partially-filled element into a Formatter.
fn fmt_bits(fmt: &mut Formatter, elt: &T, bits: u8) -> fmt::Result {
use std::fmt::Write;
let mut out = String::with_capacity(bits as usize);
for bit in 0 .. bits {
let cur = E::curr::<T>(bit as u8);
write!(out, "{}", if elt.get(cur) { "1" } else { "0" })?;
}
fmt.write_str(&out)
}
}
/// Gives write access to all live elements in the underlying storage, including
/// the partially-filled tail.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: &[u8] = &[5, 10, 15, 20, 25];
/// let mut bv: BitVec = src.into();
/// for elt in bv.as_mut() {
/// *elt += 2;
/// }
/// assert_eq!(&[7, 12, 17, 22, 27], bv.as_ref());
/// ```
impl<E: Endian, T: Bits> AsMut<[T]> for BitVec<E, T> {
fn as_mut(&mut self) -> &mut [T] {
let ptr = self.inner.as_ptr() as *mut T;
let raw = self.raw_elts();
unsafe { ::std::slice::from_raw_parts_mut(ptr, raw) }
}
}
/// Gives read access to all live elements in the underlying storage, including
/// the partially-filled tail.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: &[u8] = &[5, 10, 15, 20, 25];
/// let bv: BitVec = src.into();
/// assert_eq!(&[5, 10, 15, 20, 25], bv.as_ref());
impl<E: Endian, T: Bits> AsRef<[T]> for BitVec<E, T> {
fn as_ref(&self) -> &[T] {
let ptr = self.inner.as_ptr();
let raw = self.raw_elts();
unsafe { ::std::slice::from_raw_parts(ptr, raw) }
}
}
/// Performs the Boolean AND operation between each element of a `BitVec` and
/// anything that can provide a stream of `bool` values (such as another
/// `BitVec`, or any `bool` generator of your choice). The `BitVec` emitted will
/// have the length of the shorter sequence of bits -- if one is longer than the
/// other, the extra bits will be ignored.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// let rhs = bitvec![BigEndian, u8; 0, 0, 1, 1];
/// let and = lhs & rhs;
/// assert_eq!("0001", &format!("{}", and));
/// ```
impl<E: Endian, T: Bits, I: IntoIterator<Item=bool>> BitAnd<I> for BitVec<E, T> {
type Output = Self;
fn bitand(mut self, rhs: I) -> Self::Output {
self &= rhs;
self
}
}
/// Performs the Boolean AND operation in place on a `BitVec`, using a stream of
/// `bool` values as the other bit for each operation. If the other stream is
/// shorter than `self`, `self` will be truncated when the other stream expires.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// src &= bitvec![BigEndian, u8; 0, 0, 1, 1];
/// assert_eq!("0001", &format!("{}", src));
/// ```
impl<E: Endian, T: Bits, I: IntoIterator<Item=bool>> BitAndAssign<I> for BitVec<E, T> {
fn bitand_assign(&mut self, rhs: I) {
let mut len = 0;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) & other;
self.set(idx, val);
len += 1;
}
self.truncate(len);
}
}
/// Performs the Boolean OR operation between each element of a `BitVec` and
/// anything that can provide a stream of `bool` values (such as another
/// `BitVec`, or any `bool` generator of your choice). The `BitVec` emitted will
/// have the length of the shorter sequence of bits -- if one is longer than the
/// other, the extra bits will be ignored.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// let rhs = bitvec![BigEndian, u8; 0, 0, 1, 1];
/// let or = lhs | rhs;
/// assert_eq!("0111", &format!("{}", or));
/// ```
impl<E: Endian, T: Bits, I: IntoIterator<Item=bool>> BitOr<I> for BitVec<E, T> {
type Output = Self;
fn bitor(mut self, rhs: I) -> Self::Output {
self |= rhs;
self
}
}
/// Performs the Boolean OR operation in place on a `BitVec`, using a stream of
/// `bool` values as the other bit for each operation. If the other stream is
/// shorter than `self`, `self` will be truncated when the other stream expires.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// src |= bitvec![BigEndian, u8; 0, 0, 1, 1];
/// assert_eq!("0111", &format!("{}", src));
/// ```
impl<E: Endian, T: Bits, I: IntoIterator<Item=bool>> BitOrAssign<I> for BitVec<E, T> {
fn bitor_assign(&mut self, rhs: I) {
let mut len = 0;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) | other;
self.set(idx, val);
len += 1;
}
self.truncate(len);
}
}
/// Performs the Boolean XOR operation between each element of a `BitVec` and
/// anything that can provide a stream of `bool` values (such as another
/// `BitVec`, or any `bool` generator of your choice). The `BitVec` emitted will
/// have the length of the shorter sequence of bits -- if one is longer than the
/// other, the extra bits will be ignored.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let lhs = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// let rhs = bitvec![BigEndian, u8; 0, 0, 1, 1];
/// let xor = lhs ^ rhs;
/// assert_eq!("0110", &format!("{}", xor));
/// ```
impl<E: Endian, T: Bits, I: IntoIterator<Item=bool>> BitXor<I> for BitVec<E, T> {
type Output = Self;
fn bitxor(mut self, rhs: I) -> Self::Output {
self ^= rhs;
self
}
}
/// Performs the Boolean XOR operation in place on a `BitVec`, using a stream of
/// `bool` values as the other bit for each operation. If the other stream is
/// shorter than `self`, `self` will be truncated when the other stream expires.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut src = bitvec![BigEndian, u8; 0, 1, 0, 1];
/// src ^= bitvec![BigEndian, u8; 0, 0, 1, 1];
/// assert_eq!("0110", &format!("{}", src));
/// ```
impl<E: Endian, T: Bits, I: IntoIterator<Item=bool>> BitXorAssign<I> for BitVec<E, T> {
fn bitxor_assign(&mut self, rhs: I) {
let mut len = 0;
for (idx, other) in (0 .. self.len()).zip(rhs.into_iter()) {
let val = self.get(idx) ^ other;
self.set(idx, val);
len += 1;
}
self.truncate(len);
}
}
impl<E: Endian, T: Bits> Clone for BitVec<E, T> {
fn clone(&self) -> Self {
let mut out = Self::from(self.as_ref());
unsafe {
out.inner.set_len(self.len());
}
out
}
}
/// Prints the `BitVec` for debugging.
///
/// The output is of the form `BitVec<E, T> [ELT, *]`, where `<E, T>` is the
/// endianness and element type, with square brackets on each end of the bits
/// and all the live elements in the vector printed in binary. The printout is
/// always in semantic order, and may not reflect the underlying store. To see
/// the underlying store, use `format!("{:?}", self.as_ref());` instead.
///
/// The alternate character `{:#?}` prints each element on its own line, rather
/// than separated by a space.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![LittleEndian, u16; 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1];
/// assert_eq!("BitVec<LittleEndian, u16> [0101000011110101]", &format!("{:?}", bv));
/// ```
impl<E: Endian, T: Bits> Debug for BitVec<E, T> {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
let (elts, bits) = (self.elts(), self.bits());
let store = self.as_ref();
let alt = fmt.alternate();
self.fmt_header(fmt)?;
for idx in 0 .. elts {
if alt {
writeln!(fmt)?;
fmt.write_str(" ")?;
}
Self::fmt_element(fmt, &store[idx])?;
if idx < elts - 1 {
fmt.write_str(", ")?;
}
}
if bits > 0 {
fmt.write_str(", ")?;
if alt {
writeln!(fmt)?;
fmt.write_str(" ")?;
}
Self::fmt_bits(fmt, &store[elts], bits)?;
}
if alt {
writeln!(fmt)?;
}
fmt.write_str("]")
}
}
/// Prints the `BitVec` for displaying.
///
/// This prints each element in turn, formatted in binary in semantic order (so
/// the first bit seen is printed first and the last bit seen printed last).
/// Each element of storage is separated by a space for ease of reading.
///
/// The alternate character `{:#}` prints each element on its own line.
///
/// To see the in-memory representation, use `AsRef` to get access to the raw
/// elements and print that slice instead.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 1, 0, 0, 1, 0, 1, 1, 0, 1];
/// assert_eq!("01001011 01", &format!("{}", bv));
impl<E: Endian, T: Bits> Display for BitVec<E, T> {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
let elts = self.elts();
let store = self.as_ref();
let alt = fmt.alternate();
// Write the filled elements
for idx in 0 .. elts {
Self::fmt_element(fmt, &store[idx])?;
if idx < elts - 1 {
if alt {
writeln!(fmt)?;
}
else {
fmt.write_str(" ")?;
}
}
}
let bits = self.bits();
if bits > 0 {
if elts > 0 {
if alt {
writeln!(fmt)?;
}
else {
fmt.write_str(" ")?;
}
}
// Write the tail
Self::fmt_bits(fmt, &store[elts], bits)?;
}
Ok(())
}
}
/// Readies the underlying storage for Drop.
impl<E: Endian, T: Bits> Drop for BitVec<E, T> {
fn drop(&mut self) {
// If the `Vec` is non-empty, set the length to the number of used
// elements as preparation for drop. The bits do not need to be wiped.
//
// If we don't do this, the `Vec` drop will treat the bit total as the
// number of elements and try to loop through all of them, which will
// not take 2 ** T::BITS times as long to run as expected, because
// it'll segfault.
let raw = self.raw_elts();
unsafe { self.inner.set_len(raw); }
}
}
impl<'a, E: Endian, T: Bits> From<&'a [bool]> for BitVec<E, T> {
fn from(src: &'a [bool]) -> Self {
let mut out = Self::with_capacity(src.len());
for bit in src {
out.push(*bit);
}
out
}
}
/// Build a `BitVec` out of a borrowed slice of elements.
///
/// This copies the memory as-is from the source buffer into the new `BitVec`.
/// The source buffer will be unchanged by this operation, so you don't need to
/// worry about using the correct cursor type.
///
/// This operation does a copy from the source buffer into a new allocation, as
/// it can only borrow the source and not take ownership.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: &[u8] = &[5, 10];
/// let bv: BitVec = src.into();
/// assert_eq!("00000101 00001010", &format!("{}", bv));
impl<'a, E: Endian, T: Bits> From<&'a [T]> for BitVec<E, T> {
fn from(src: &'a [T]) -> Self {
use std::ptr::copy_nonoverlapping;
let len = src.len();
assert!(len <= T::MAX_ELT, "Source slice too long!");
let mut out = Self::with_capacity(len << T::BITS);
out.do_with_vec(|v| unsafe {
copy_nonoverlapping(src.as_ptr(), v.as_ptr() as *mut T, len);
v.set_len(len);
});
out
}
}
/// Build a `BitVec` out of an owned slice of elements.
///
/// This moves the memory as-is from the source buffer into the new `BitVec`.
/// The source buffer will be unchanged by this operation, so you don't need to
/// worry about using the correct cursor type.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: Box<[u8]> = Box::new([3, 6, 9, 12, 15]);
/// let bv: BitVec = src.into();
/// assert_eq!("00000011 00000110 00001001 00001100 00001111", &format!("{}", bv));
/// ```
impl<E: Endian, T: Bits> From<Box<[T]>> for BitVec<E, T> {
fn from(src: Box<[T]>) -> Self {
assert!(src.len() <= T::MAX_ELT, "Source slice too long!");
Self::from(Vec::from(src))
}
}
/// Build a `BitVec` out of a `Vec` of elements.
///
/// This moves the memory as-is from the source buffer into the new `BitVec`.
/// The source buffer will be unchanged by this operation, so you don't need to
/// worry about using the correct cursor type.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let src: Vec<u8> = vec![1, 2, 4, 8];
/// let bv: BitVec = src.into();
/// assert_eq!("00000001 00000010 00000100 00001000", &format!("{}", bv));
impl<E: Endian, T: Bits> From<Vec<T>> for BitVec<E, T> {
fn from(src: Vec<T>) -> Self {
let elts = src.len();
assert!(elts <= T::MAX_ELT, "Source vector too long!");
let mut out = Self {
inner: src,
_endian: PhantomData::<E>,
};
unsafe {
out.set_bits(0);
out.set_elts(elts);
}
out
}
}
/// Change cursors on a `BitVec` without mutating the underlying data.
///
/// I don't know why this would be useful at the time of writing, as the `From`
/// implementations on collections crawl the collection elements in the order
/// requested and so the source and destination storage collections will be
/// bitwise identical, but here's the option anyway.
///
/// If the tail element is partially filled, then this operation will shift the
/// tail element so that the edge of the filled section is on the correct edge
/// of the tail element.
impl<T: Bits> From<BitVec<LittleEndian, T>> for BitVec<BigEndian, T> {
fn from(mut src: BitVec<LittleEndian, T>) -> Self {
let bits = src.bits();
// If bits() is zero, then the tail is full and cannot shift.
// If bits() is nonzero, then the shamt is WIDTH - bits().
// E.g. a WIDTH of 32 and a bits() of 31 means bit 30 is the highest
// bit set, and the element should shl by 1 so that bit 31 is the
// highest bit set, and bit 0 will be empty.
if bits > 0 {
let shamt = T::WIDTH - bits;
src.do_with_tail(|elt| *elt <<= shamt);
}
// The cursor is stored in PhantomData, and known only to the complier.
// Transmutation is perfectly safe, since the only concrete item is the
// storage, which this explicitly does not alter.
unsafe { mem::transmute(src) }
}
}
/// Change cursors on a `BitVec` without mutating the underlying data.
///
/// I don't know why this would be useful at the time of writing, as the `From`
/// implementations on collections crawl the collection elements in the order
/// requested and so the source and destination storage collections will be
/// bitwise identical, but here's the option anyway.
///
/// If the tail element is partially filled, then this operation will shift the
/// tail element so that the edge of the filled section is on the correct edge
/// of the tail element.
impl<T: Bits> From<BitVec<BigEndian, T>> for BitVec<LittleEndian, T> {
fn from(mut src: BitVec<BigEndian, T>) -> Self {
let bits = src.bits();
if bits > 0 {
let shamt = T::WIDTH - bits;
src.do_with_tail(|elt| *elt >>= shamt);
}
unsafe { mem::transmute(src) }
}
}
/// Permits the construction of a `BitVec` by using `.collect()` on an iterator
/// of `bool`
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// use std::iter::repeat;
/// let bv: BitVec = repeat(true).take(4).chain(repeat(false).take(4)).collect();
/// assert_eq!("11110000", &format!("{}", bv));
/// ```
impl<E: Endian, T: Bits> FromIterator<bool> for BitVec<E, T> {
fn from_iter<I: IntoIterator<Item=bool>>(src: I) -> Self {
let iter = src.into_iter();
let mut out = match iter.size_hint() {
(_, Some(len)) |
(len, _) if len > 0 => Self::with_capacity(len),
_ => Self::new(),
};
for bit in iter {
out.push(bit);
}
out
}
}
/// Get the bit at a specific index. The index must be less than the length of
/// the `BitVec`.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 0, 0, 0, 0, 0, 1, 0];
/// assert!(!bv[7]); // ---------------------------------^ | |
/// assert!( bv[8]); //-------------------------------------^ |
/// assert!(!bv[9]); // ---------------------------------------^
/// ```
///
/// If the index is greater than or equal to the length, indexing will panic.
///
/// The below test will panic when accessing index 1, as only index 0 is valid.
///
/// ```rust,should_panic
/// use bitvec::*;
/// let mut bv: BitVec = BitVec::new();
/// bv.push(true);
/// bv[1];
/// ```
impl<E: Endian, T: Bits> Index<usize> for BitVec<E, T> {
type Output = bool;
fn index(&self, cursor: usize) -> &Self::Output {
assert!(cursor < self.inner.len(), "Index out of range!");
self.index(T::split(cursor))
}
}
/// Get the bit in a specific element. The element index must be less than or
/// equal to the value returned by `elts()`, and the bit index must be less
/// than the width of the storage type.
///
/// If the `BitVec` has a partially-filled tail, then the value returned by
/// `elts()` is a valid index.
///
/// The element and bit indices are combined using `Bits::join` for the storage
/// type.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 1, 1, 1, 1, 0, 0, 0, 0, 0, 1];
/// assert!(bv[(1, 1)]); // -----------------------------------^
/// ```
impl<E: Endian, T: Bits> Index<(usize, u8)> for BitVec<E, T> {
type Output = bool;
/// Index into a `BitVec` using a known element index and a count into that
/// element. The count must not be converted for endianness outside the call
fn index(&self, (elt, bit): (usize, u8)) -> &Self::Output {
assert!(T::join(elt, bit) < self.len(), "Index out of range!");
match (self.inner[elt]).get(E::curr::<T>(bit)) {
true => &TRUE,
false => &FALSE,
}
}
}
/// Produces an iterator over all the bits in the vector.
///
/// This iterator follows the ordering in the vector type, and implements
/// `ExactSizeIterator`, since `BitVec`s always know exactly how large they are,
/// and `DoubleEndedIterator`, since they have known ends.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 1, 1, 1, 1, 0, 0, 0, 0];
/// let mut count = 0;
/// for bit in bv {
/// if bit { count += 1; }
/// }
/// assert_eq!(count, 4);
/// ```
impl<E: Endian, T: Bits> IntoIterator for BitVec<E, T> {
type Item = bool;
#[doc(hidden)]
type IntoIter = IntoIter<E, T>;
fn into_iter(self) -> Self::IntoIter {
let tail = self.len();
Self::IntoIter {
bv: self,
head: 0,
tail,
}
}
}
/// Flips all bits in the vector.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv: BitVec<BigEndian, u32> = BitVec::from(&[0u32] as &[u32]);
/// let flip = !bv;
/// assert_eq!(!0u32, flip.as_ref()[0]);
/// ```
impl<E: Endian, T: Bits> Not for BitVec<E, T> {
type Output = Self;
// Because self does not have to interact with any other `BitVec`, and bits
// beyond `BitVec.len()` are uninitialized and don't matter, this is free
// to simply negate the elements in place and then return self.
fn not(mut self) -> Self::Output {
for elt in self.as_mut() {
*elt = !*elt;
}
self
}
}
/// Shifts all bits in the vector to the left – DOWN AND TOWARDS THE FRONT.
///
/// On primitives, the left-shift operator `<<` moves bits away from origin and
/// towards the ceiling. This is because we label the bits in a primitive with
/// the minimum on the right and the maximum on the left, which is big-endian
/// bit order. This increases the value of the primitive being shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, left-shifting moves bits towards the **minimum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `<<`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `>>` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// being left to their old value.
///
/// The length of the vector is decreased by the shift amount.
///
/// If the shift amount is greater than the length, the vector calls `clear()`
/// and zeroes its memory. This is *not* an error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0001_1100, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// let ls = bv << 2;
/// assert_eq!("0111", &format!("{}", ls));
/// assert_eq!(0b0111_0000, ls.as_ref()[0]);
/// assert_eq!(ls.len(), 4);
/// ```
impl<E: Endian, T: Bits> Shl<usize> for BitVec<E, T> {
type Output = Self;
fn shl(mut self, shamt: usize) -> Self {
self <<= shamt;
self
}
}
/// Shifts all bits in the vector to the left – DOWN AND TOWARDS THE FRONT.
///
/// On primitives, the left-shift operator `<<` moves bits away from origin and
/// towards the ceiling. This is because we label the bits in a primitive with
/// the minimum on the right and the maximum on the left, which is big-endian
/// bit order. This increases the value of the primitive being shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, left-shifting moves bits towards the **minimum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `<<`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `>>` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// being left to their old value.
///
/// The length of the vector is decreased by the shift amount.
///
/// If the shift amount is greater than the length, the vector calls `clear()`
/// and zeroes its memory. This is *not* an error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![LittleEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0011_1000, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// bv <<= 2;
/// assert_eq!("0111", &format!("{}", bv));
/// assert_eq!(0b0000_1110, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 4);
impl<'a, E: Endian, T: Bits> ShlAssign<usize> for BitVec<E, T> {
fn shl_assign(&mut self, shamt: usize) {
let len = self.len();
if shamt >= len {
self.clear();
let buf = self.as_mut();
let ptr = buf.as_mut_ptr();
let len = buf.len();
unsafe { ::std::ptr::write_bytes(ptr, 0, len); }
return;
}
for idx in shamt .. len {
let val = self.get(idx);
self.set(idx - shamt, val);
}
let trunc = len - shamt;
for idx in trunc .. len {
self.set(idx, false);
}
self.truncate(trunc);
}
}
/// Shifts all bits in the vector to the right – UP AND TOWARDS THE RIGHT.
///
/// On primitives, the right-shift operator `>>` moves bits towards the origin
/// and away from the ceiling. This is because we label the bits in a primitive with
/// the minimum on the right and the maximum on the left, which is big-endian
/// bit order. This decreases the value of the primitive being shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, rightt-shifting moves bits towards the **maximum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `>>`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `<<` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// being left to their old value.
///
/// The length of the vector is increased by the shift amount.
///
/// If the new length of the vector would overflow, a panic occurs. This *is* an
/// error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let bv = bitvec![BigEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0001_1100, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// let rs = bv >> 2;
/// assert_eq!("00000111", &format!("{}", rs));
/// assert_eq!(0b0000_0111, rs.as_ref()[0]);
/// assert_eq!(rs.len(), 8);
/// ```
impl<E: Endian, T: Bits> Shr<usize> for BitVec<E, T> {
type Output = Self;
fn shr(mut self, shamt: usize) -> Self {
self >>= shamt;
self
}
}
/// Shifts all bits in the vector to the right – UP AND TOWARDS THE RIGHT.
///
/// On primitives, the right-shift operator `>>` moves bits towards the origin
/// and away from the ceiling. This is because we label the bits in a primitive with
/// the minimum on the right and the maximum on the left, which is big-endian
/// bit order. This decreases the value of the primitive being shifted.
///
/// **THAT IS NOT HOW `BITVEC` WORKS!**
///
/// `BitVec` defines its layout with the minimum on the left and the maximum on
/// the right! Thus, rightt-shifting moves bits towards the **maximum**.
///
/// In BigEndian order, the effect in memory will be what you expect the `>>`
/// operator to do.
///
/// **In LittleEndian order, the effect will be equivalent to using `<<` on**
/// **the primitives in memory!**
///
/// # Notes
///
/// In order to preserve the effects in memory that this operator traditionally
/// expects, the bits that are emptied by this operation are zeroed rather than
/// being left to their old value.
///
/// The length of the vector is increased by the shift amount.
///
/// If the new length of the vector would overflow, a panic occurs. This *is* an
/// error.
///
/// # Examples
///
/// ```rust
/// use bitvec::*;
/// let mut bv = bitvec![LittleEndian, u8; 0, 0, 0, 1, 1, 1];
/// assert_eq!("000111", &format!("{}", bv));
/// assert_eq!(0b0011_1000, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 6);
/// bv >>= 2;
/// assert_eq!("00000111", &format!("{}", bv));
/// assert_eq!(0b1110_0000, bv.as_ref()[0]);
/// assert_eq!(bv.len(), 8);
impl<'a, E: Endian, T: Bits> ShrAssign<usize> for BitVec<E, T> {
fn shr_assign(&mut self, shamt: usize) {
let old_len = self.len();
// Implement `Extend` to make this more efficient
for _ in 0 .. shamt {
self.push(false);
}
for idx in (0 .. old_len).rev() {
let val = self.get(idx);
self.set(idx + shamt, val);
}
for idx in 0 .. shamt {
self.set(idx, false);
}
}
}
/// Permits iteration over a borrowed `BitVec`.
impl<'a, E: Endian, T: Bits> IntoIterator for &'a BitVec<E, T> {
type Item = bool;
#[doc(hidden)]
type IntoIter = Iter<'a, E, T>;
fn into_iter(self) -> Self::IntoIter {
Iter {
bv: self,
head: 0,
tail: self.len(),
}
}
}
/// Iterates over an owned `BitVec`.
#[doc(hidden)]
pub struct IntoIter<E: Endian, T: Bits> {
bv: BitVec<E, T>,
head: usize,
tail: usize,
}
impl<E: Endian, T: Bits> DoubleEndedIterator for IntoIter<E, T> {
/// Yield the back-most bit of the collection.
///
/// This iterator is self-resetting; when the cursor reaches the front of
/// the collection, it returns None after setting the cursor to the length
/// of the underlying collection. If the collection is not empty when this
/// occurs, then the iterator will resume at the back if called again.
fn next_back(&mut self) -> Option<Self::Item> {
if self.tail > self.head && self.tail <= self.bv.len() {
self.tail -= 1;
Some(self.bv[self.tail])
}
else {
self.head = 0;
self.tail = self.bv.len();
None
}
}
}
impl<E: Endian, T: Bits> ExactSizeIterator for IntoIter<E, T> {
// Override the default implementation with a fixed calculation. The type
// is guaranteed to be well-behaved, so there is no point in building two
// copies of the remnant, checking an always-safe condition, and dropping
// one.
//
// THIS IS A LOAD BEARING OVERRIDE! IF IT IS REMOVED, THEN
// Iterator::size_hint MUST BE CHANGED TO NOT CALL THIS FUNCTION, BECAUSE
// THE DEFAULT IMPLEMENTATION CALLS Iterator::size_hint! FAILURE TO DO SO
// WILL RESULT IN A VALID COMPILE AND A BLOWN STACK AT RUNTIME DUE TO
// INFINITE MUTUAL RECURSION!
fn len(&self) -> usize {
self.tail - self.head
}
}
impl<E: Endian, T: Bits> Iterator for IntoIter<E, T> {
type Item = bool;
/// Advances the iterator forward, yielding the front-most bit.
///
/// This iterator is self-resetting: when the cursor reaches the back of the
/// collection, it returns None after setting the cursor to zero. If the
/// collection is not empty when this occurs, then the iterator will resume
/// at the front if called again.
fn next(&mut self) -> Option<Self::Item> {
if self.head < self.tail {
let ret = self.bv[self.head];
self.head += 1;
Some(ret)
}
else {
self.head = 0;
self.tail = self.bv.len();
None
}
}
// Note that the default ExactSizeIterator::len calls this method, so
// removing that implementation will cause an infinite mutual recursion,
// only detectable *at runtime* when the stack blows.
//
// THIS METHOD MUST BE CHANGED TO NOT CALL ExactSizeIterator::len BEFORE
// REMOVING THE SPECIALIZATION FOR ESI! THE DEFAULT IMPLEMENTATION OF ESI
// CALLS THIS FUNCTION, WHICH WILL COMPILE CLEANLY AND THEN BLOW THE STACK
// AT RUNTIME DUE TO INFINITE MUTUAL RECURSION!
fn size_hint(&self) -> (usize, Option<usize>) {
let rem = ExactSizeIterator::len(self);
(rem, Some(rem))
}
}
/// Iterates over a borrowed `BitVector`.
#[doc(hidden)]
pub struct Iter<'a, E: 'a + Endian, T: 'a + Bits> {
bv: &'a BitVec<E, T>,
head: usize,
tail: usize,
}
impl<'a, E: Endian, T: Bits> DoubleEndedIterator for Iter<'a, E, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.tail > self.head && self.tail <= self.bv.len() {
self.tail -= 1;
Some(self.bv[self.tail])
}
else {
self.head = 0;
self.tail = self.bv.len();
None
}
}
}
impl<'a, E: Endian, T: Bits> ExactSizeIterator for Iter<'a, E, T> {
// Override the default implementation with a fixed calculation. The type
// is guaranteed to be well-behaved, so there is no point in building two
// copies of the remnant, checking an always-safe condition, and dropping
// one.
//
// THIS IS A LOAD BEARING OVERRIDE! IF IT IS REMOVED, THEN
// Iterator::size_hint MUST BE CHANGED TO NOT CALL THIS FUNCTION, BECAUSE
// THE DEFAULT IMPLEMENTATION CALLS Iterator::size_hint! FAILURE TO DO SO
// WILL RESULT IN A VALID COMPILE AND A BLOWN STACK AT RUNTIME DUE TO
// INFINITE MUTUAL RECURSION!
fn len(&self) -> usize {
self.tail - self.head
}
}
impl<'a, E: Endian, T: Bits> Iterator for Iter<'a, E, T> {
type Item = bool;
fn next(&mut self) -> Option<Self::Item> {
if self.head < self.tail {
let ret = self.bv[self.head];
self.head += 1;
Some(ret)
}
else {
self.head = 0;
self.tail = self.bv.len();
None
}
}
// Note that the default ExactSizeIterator::len calls this method, so
// removing that implementation will cause an infinite mutual recursion,
// only detectable *at runtime* when the stack blows.
//
// THIS METHOD MUST BE CHANGED TO NOT CALL ExactSizeIterator::len BEFORE
// REMOVING THE SPECIALIZATION FOR ESI! THE DEFAULT IMPLEMENTATION OF ESI
// CALLS THIS FUNCTION, WHICH WILL COMPILE CLEANLY AND THEN BLOW THE STACK
// AT RUNTIME DUE TO INFINITE MUTUAL RECURSION!
fn size_hint(&self) -> (usize, Option<usize>) {
let rem = ExactSizeIterator::len(self);
(rem, Some(rem))
}
}
+56
-0
src/macros.rs

@@ -96,2 +96,58 @@ /// Construct a `BitVec` out of a literal array in source code, analagous to

#[doc(hidden)]
macro_rules! __bitslice_shift {
( $( $t:ty ),+ ) => { $(
#[doc(hidden)]
impl<E: $crate::Endian, T: $crate::Bits> ShlAssign< $t > for $crate::BitSlice<E, T> {
fn shl_assign(&mut self, shamt: $t ) {
ShlAssign::<usize>::shl_assign(self, shamt as usize);
}
}
#[doc(hidden)]
impl<E: $crate::Endian, T: $crate::Bits> ShrAssign< $t > for $crate::BitSlice<E, T> {
fn shr_assign(&mut self, shamt: $t ) {
ShrAssign::<usize>::shr_assign(self, shamt as usize);
}
}
)+ };
}
#[doc(hidden)]
macro_rules! __bitvec_shift {
( $( $t:ty ),+ ) => { $(
#[doc(hidden)]
impl<E: $crate::Endian, T: $crate::Bits> Shl< $t > for $crate::BitVec<E, T> {
type Output = <Self as Shl<usize>>::Output;
fn shl(self, shamt: $t ) -> Self::Output {
Shl::<usize>::shl(self, shamt as usize)
}
}
#[doc(hidden)]
impl<E: $crate::Endian, T: $crate::Bits> ShlAssign< $t > for $crate::BitVec<E, T> {
fn shl_assign(&mut self, shamt: $t ) {
ShlAssign::<usize>::shl_assign(self, shamt as usize)
}
}
#[doc(hidden)]
impl<E: $crate::Endian, T: $crate::Bits> Shr< $t > for $crate::BitVec<E, T> {
type Output = <Self as Shr<usize>>::Output;
fn shr(self, shamt: $t ) -> Self::Output {
Shr::<usize>::shr(self, shamt as usize)
}
}
#[doc(hidden)]
impl<E: $crate::Endian, T: $crate::Bits> ShrAssign< $t > for $crate::BitVec<E, T> {
fn shr_assign(&mut self, shamt: $t ) {
ShrAssign::<usize>::shr_assign(self, shamt as usize)
}
}
)+ };
}
#[cfg(test)]

@@ -98,0 +154,0 @@ mod tests {

-88
examples/basic.rs
/*! Demonstrates construction and use of a big-endian, u8, `BitVec`
This example uses `bitvec!` to construct a `BitVec` from literals, then shows
a sample of the various operations that can be applied to it.
This example prints **a lot** of text to the console.
!*/
#[macro_use]
extern crate bitvec;
use bitvec::*;
use std::iter::repeat;
fn main() {
let bv = bitvec![
0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 1, 0,
];
println!("A BigEndian BitVec has the same layout in memory as it does semantically");
render(&bv);
// BitVec can turn into iterators, and be built from iterators.
let bv: BitVec<LittleEndian, u8> = bv.into_iter().collect();
println!("A LittleEndian BitVec has the opposite layout in memory as it does semantically");
render(&bv);
let bv: BitVec<BigEndian, u16> = bv.into_iter().collect();
println!("A BitVec can use storage other than u8");
render(&bv);
println!("BitVec can participate in Boolean arithmetic");
let full = bv.clone() | repeat(true);
render(&full);
let empty = full & repeat(false);
render(&empty);
let flip = bv ^ repeat(true);
render(&flip);
let bv = !flip;
render(&bv);
println!("\
Notice that ^ did not affect the parts of the tail that were not in use, while !
did affect them. ^ requires a second source, while ! can just flip all elements.
! is faster, but ^ is less likely to break your assumptions about what the
memory looks like.\
");
// Push and pop to the bitvec
let mut bv = bv;
for _ in 0 .. 12 {
bv.push(false);
}
for _ in 0 .. 12 {
bv.pop();
}
render(&bv);
println!("End example");
}
fn render<E: Endian, T: Bits>(bv: &BitVec<E, T>) {
println!("Memory information: {} {} {}", bv.elts(), bv.bits(), bv.len());
println!("Print out the semantic contents");
println!("{:#?}", bv);
println!("Print out the memory contents");
println!("{:?}", bv.as_ref());
println!("Show the bits in memory");
for elt in bv.as_ref() {
println!("{:0w$b} ", elt, w=::std::mem::size_of::<T>() * 8);
}
println!();
}
Cargo.toml.orig

Sorry, the diff of this file is not supported yet