From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- third_party/rust/smallbitvec/src/lib.rs | 1061 +++++++++++++++++++++++++++++++ 1 file changed, 1061 insertions(+) create mode 100644 third_party/rust/smallbitvec/src/lib.rs (limited to 'third_party/rust/smallbitvec/src/lib.rs') diff --git a/third_party/rust/smallbitvec/src/lib.rs b/third_party/rust/smallbitvec/src/lib.rs new file mode 100644 index 0000000000..49c443d668 --- /dev/null +++ b/third_party/rust/smallbitvec/src/lib.rs @@ -0,0 +1,1061 @@ +// Copyright 2017 Matt Brubeck. See the COPYRIGHT file at the top-level +// directory of this distribution and at http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! [`SmallBitVec`] is a bit vector, a vector of single-bit values stored compactly in memory. +//! +//! SmallBitVec grows dynamically, like the standard `Vec` type. It can hold up to about one +//! word of bits inline (without a separate heap allocation). If the number of bits exceeds this +//! inline capacity, it will allocate a buffer on the heap. +//! +//! [`SmallBitVec`]: struct.SmallBitVec.html +//! +//! # Example +//! +//! ``` +//! use smallbitvec::SmallBitVec; +//! +//! let mut v = SmallBitVec::new(); +//! v.push(true); +//! v.push(false); +//! +//! assert_eq!(v[0], true); +//! assert_eq!(v[1], false); +//! ``` + +#![no_std] + +extern crate alloc; + +use alloc::{vec, vec::Vec, boxed::Box}; + +use core::cmp::max; +use core::fmt; +use core::hash; +use core::iter::{DoubleEndedIterator, ExactSizeIterator, FromIterator}; +use core::mem::{forget, replace, size_of}; +use core::ops::{Index, Range}; +use core::slice; + +/// Creates a [`SmallBitVec`] containing the arguments. +/// +/// `sbvec!` allows `SmallBitVec`s to be defined with the same syntax as array expressions. +/// There are two forms of this macro: +/// +/// - Create a [`SmallBitVec`] containing a given list of elements: +/// +/// ``` +/// # #[macro_use] extern crate smallbitvec; +/// # use smallbitvec::SmallBitVec; +/// # fn main() { +/// let v = sbvec![true, false, true]; +/// assert_eq!(v[0], true); +/// assert_eq!(v[1], false); +/// assert_eq!(v[2], true); +/// # } +/// ``` +/// +/// - Create a [`SmallBitVec`] from a given element and size: +/// +/// ``` +/// # #[macro_use] extern crate smallbitvec; +/// # use smallbitvec::SmallBitVec; +/// # fn main() { +/// let v = sbvec![true; 3]; +/// assert!(v.into_iter().eq(vec![true, true, true].into_iter())); +/// # } +/// ``` + +#[macro_export] +macro_rules! sbvec { + ($elem:expr; $n:expr) => ( + $crate::SmallBitVec::from_elem($n, $elem) + ); + ($($x:expr),*) => ( + [$($x),*].iter().cloned().collect::<$crate::SmallBitVec>() + ); + ($($x:expr,)*) => ( + sbvec![$($x),*] + ); +} + + +// FIXME: replace this with `debug_assert!` when it’s usable in `const`: +// * https://github.com/rust-lang/rust/issues/49146 +// * https://github.com/rust-lang/rust/issues/51999 +macro_rules! const_debug_assert_le { + ($left: ident <= $right: expr) => { + #[cfg(debug_assertions)] + // Causes an `index out of bounds` panic if `$left` is too large + [(); $right + 1][$left]; + } +} + +#[cfg(test)] +mod tests; + +/// A resizable bit vector, optimized for size and inline storage. +/// +/// `SmallBitVec` is exactly one word wide. Depending on the required capacity, this word +/// either stores the bits inline, or it stores a pointer to a separate buffer on the heap. +pub struct SmallBitVec { + data: usize, +} + +/// Total number of bits per word. +#[inline(always)] +const fn inline_bits() -> usize { + size_of::() * 8 +} + +/// For an inline vector, all bits except two can be used as storage capacity: +/// +/// - The rightmost bit is set to zero to signal an inline vector. +/// - The position of the rightmost nonzero bit encodes the length. +#[inline(always)] +const fn inline_capacity() -> usize { + inline_bits() - 2 +} + +/// Left shift amount to access the nth bit +#[inline(always)] +const fn inline_shift(n: usize) -> usize { + const_debug_assert_le!(n <= inline_capacity()); + // The storage starts at the leftmost bit. + inline_bits() - 1 - n +} + +/// An inline vector with the nth bit set. +#[inline(always)] +const fn inline_index(n: usize) -> usize { + 1 << inline_shift(n) +} + +/// An inline vector with the leftmost `n` bits set. +#[inline(always)] +fn inline_ones(n: usize) -> usize { + if n == 0 { + 0 + } else { + !0 << (inline_bits() - n) + } +} + +/// If the rightmost bit of `data` is set, then the remaining bits of `data` +/// are a pointer to a heap allocation. +const HEAP_FLAG: usize = 1; + +/// The allocation will contain a `Header` followed by a [Storage] buffer. +type Storage = usize; + +/// The number of bits in one `Storage`. +#[inline(always)] +fn bits_per_storage() -> usize { + size_of::() * 8 +} + +/// Data stored at the start of the heap allocation. +/// +/// `Header` must have the same alignment as `Storage`. +struct Header { + /// The number of bits in this bit vector. + len: Storage, + + /// The number of elements in the [usize] buffer that follows this header. + buffer_len: Storage, +} + +impl Header { + /// Create a heap allocation with enough space for a header, + /// plus a buffer of at least `cap` bits, each initialized to `val`. + fn new(cap: usize, len: usize, val: bool) -> *mut Header { + let alloc_len = header_len() + buffer_len(cap); + let init = if val { !0 } else { 0 }; + + let v: Vec = vec![init; alloc_len]; + + let buffer_len = v.capacity() - header_len(); + let header_ptr = v.as_ptr() as *mut Header; + + forget(v); + + unsafe { + (*header_ptr).len = len; + (*header_ptr).buffer_len = buffer_len; + } + header_ptr + } +} + +/// The number of `Storage` elements to allocate to hold a header. +#[inline(always)] +fn header_len() -> usize { + size_of::
() / size_of::() +} + +/// The minimum number of `Storage` elements to hold at least `cap` bits. +#[inline(always)] +fn buffer_len(cap: usize) -> usize { + (cap + bits_per_storage() - 1) / bits_per_storage() +} + +/// A typed representation of a `SmallBitVec`'s internal storage. +/// +/// The layout of the data inside both enum variants is a private implementation detail. +pub enum InternalStorage { + /// The internal representation of a `SmallBitVec` that has not spilled to a + /// heap allocation. + Inline(usize), + + /// The contents of the heap allocation of a spilled `SmallBitVec`. + Spilled(Box<[usize]>), +} + +impl SmallBitVec { + /// Create an empty vector. + #[inline] + pub const fn new() -> SmallBitVec { + SmallBitVec { + data: inline_index(0), + } + } + + /// Create a vector containing `len` bits, each set to `val`. + #[inline] + pub fn from_elem(len: usize, val: bool) -> SmallBitVec { + if len <= inline_capacity() { + return SmallBitVec { + data: if val { + inline_ones(len + 1) + } else { + inline_index(len) + }, + }; + } + let header_ptr = Header::new(len, len, val); + SmallBitVec { + data: (header_ptr as usize) | HEAP_FLAG, + } + } + + /// Create an empty vector with enough storage pre-allocated to store at least `cap` bits + /// without resizing. + #[inline] + pub fn with_capacity(cap: usize) -> SmallBitVec { + // Use inline storage if possible. + if cap <= inline_capacity() { + return SmallBitVec::new(); + } + + // Otherwise, allocate on the heap. + let header_ptr = Header::new(cap, 0, false); + SmallBitVec { + data: (header_ptr as usize) | HEAP_FLAG, + } + } + + /// The number of bits stored in this bit vector. + #[inline] + pub fn len(&self) -> usize { + if self.is_inline() { + // The rightmost nonzero bit is a sentinel. All bits to the left of + // the sentinel bit are the elements of the bit vector. + inline_bits() - self.data.trailing_zeros() as usize - 1 + } else { + self.header().len + } + } + + /// Returns `true` if this vector contains no bits. + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// The number of bits that can be stored in this bit vector without re-allocating. + #[inline] + pub fn capacity(&self) -> usize { + if self.is_inline() { + inline_capacity() + } else { + self.header().buffer_len * bits_per_storage() + } + } + + /// Get the nth bit in this bit vector. + #[inline] + pub fn get(&self, n: usize) -> Option { + if n < self.len() { + Some(unsafe { self.get_unchecked(n) }) + } else { + None + } + } + + /// Get the last bit in this bit vector. + #[inline] + pub fn last(&self) -> Option { + self.len().checked_sub(1).map(|n| unsafe { self.get_unchecked(n) }) + } + + /// Get the nth bit in this bit vector, without bounds checks. + #[inline] + pub unsafe fn get_unchecked(&self, n: usize) -> bool { + if self.is_inline() { + self.data & inline_index(n) != 0 + } else { + let buffer = self.buffer(); + let i = n / bits_per_storage(); + let offset = n % bits_per_storage(); + *buffer.get_unchecked(i) & (1 << offset) != 0 + } + } + + /// Set the nth bit in this bit vector to `val`. Panics if the index is out of bounds. + #[inline] + pub fn set(&mut self, n: usize, val: bool) { + assert!(n < self.len(), "Index {} out of bounds", n); + unsafe { + self.set_unchecked(n, val); + } + } + + /// Set the nth bit in this bit vector to `val`, without bounds checks. + #[inline] + pub unsafe fn set_unchecked(&mut self, n: usize, val: bool) { + if self.is_inline() { + if val { + self.data |= inline_index(n); + } else { + self.data &= !inline_index(n); + } + } else { + let buffer = self.buffer_mut(); + let i = n / bits_per_storage(); + let offset = n % bits_per_storage(); + if val { + *buffer.get_unchecked_mut(i) |= 1 << offset; + } else { + *buffer.get_unchecked_mut(i) &= !(1 << offset); + } + } + } + + /// Append a bit to the end of the vector. + /// + /// ``` + /// use smallbitvec::SmallBitVec; + /// let mut v = SmallBitVec::new(); + /// v.push(true); + /// + /// assert_eq!(v.len(), 1); + /// assert_eq!(v.get(0), Some(true)); + /// ``` + #[inline] + pub fn push(&mut self, val: bool) { + let idx = self.len(); + if idx == self.capacity() { + self.reserve(1); + } + unsafe { + self.set_len(idx + 1); + self.set_unchecked(idx, val); + } + } + + /// Remove the last bit from the vector and return it, if there is one. + /// + /// ``` + /// use smallbitvec::SmallBitVec; + /// let mut v = SmallBitVec::new(); + /// v.push(false); + /// + /// assert_eq!(v.pop(), Some(false)); + /// assert_eq!(v.len(), 0); + /// assert_eq!(v.pop(), None); + /// ``` + #[inline] + pub fn pop(&mut self) -> Option { + self.len().checked_sub(1).map(|last| unsafe { + let val = self.get_unchecked(last); + self.set_len(last); + val + }) + } + + /// Remove and return the bit at index `idx`, shifting all later bits toward the front. + /// + /// Panics if the index is out of bounds. + #[inline] + pub fn remove(&mut self, idx: usize) -> bool { + let len = self.len(); + let val = self[idx]; + + if self.is_inline() { + // Shift later bits, including the length bit, toward the front. + let mask = !inline_ones(idx); + let new_vals = (self.data & mask) << 1; + self.data = (self.data & !mask) | (new_vals & mask); + } else { + let first = idx / bits_per_storage(); + let offset = idx % bits_per_storage(); + let count = buffer_len(len); + { + // Shift bits within the first storage block. + let buf = self.buffer_mut(); + let mask = !0 << offset; + let new_vals = (buf[first] & mask) >> 1; + buf[first] = (buf[first] & !mask) | (new_vals & mask); + } + // Shift bits in subsequent storage blocks. + for i in (first + 1)..count { + // Move the first bit into the previous block. + let bit_idx = i * bits_per_storage(); + unsafe { + let first_bit = self.get_unchecked(bit_idx); + self.set_unchecked(bit_idx - 1, first_bit); + } + // Shift the remaining bits. + self.buffer_mut()[i] >>= 1; + } + // Decrement the length. + unsafe { + self.set_len(len - 1); + } + } + val + } + + /// Remove all elements from the vector, without deallocating its buffer. + #[inline] + pub fn clear(&mut self) { + unsafe { + self.set_len(0); + } + } + + /// Reserve capacity for at least `additional` more elements to be inserted. + /// + /// May reserve more space than requested, to avoid frequent reallocations. + /// + /// Panics if the new capacity overflows `usize`. + /// + /// Re-allocates only if `self.capacity() < self.len() + additional`. + #[inline] + pub fn reserve(&mut self, additional: usize) { + let old_cap = self.capacity(); + let new_cap = self.len() + .checked_add(additional) + .expect("capacity overflow"); + if new_cap <= old_cap { + return; + } + // Ensure the new capacity is at least double, to guarantee exponential growth. + let double_cap = old_cap.saturating_mul(2); + self.reallocate(max(new_cap, double_cap)); + } + + /// Set the length of the vector. The length must not exceed the capacity. + /// + /// If this makes the vector longer, then the values of its new elements + /// are not specified. + #[inline] + unsafe fn set_len(&mut self, len: usize) { + debug_assert!(len <= self.capacity()); + if self.is_inline() { + let sentinel = inline_index(len); + let mask = !(sentinel - 1); + self.data |= sentinel; + self.data &= mask; + } else { + self.header_mut().len = len; + } + } + + /// Returns an iterator that yields the bits of the vector in order, as `bool` values. + #[inline] + pub fn iter(&self) -> Iter { + Iter { + vec: self, + range: 0..self.len(), + } + } + + /// Returns an immutable view of a range of bits from this vec. + /// ``` + /// #[macro_use] extern crate smallbitvec; + /// let v = sbvec![true, false, true]; + /// let r = v.range(1..3); + /// assert_eq!(r[1], true); + /// ``` + #[inline] + pub fn range(&self, range: Range) -> VecRange { + assert!(range.end <= self.len(), "range out of bounds"); + VecRange { vec: &self, range } + } + + /// Returns true if all the bits in the vec are set to zero/false. + /// + /// On an empty vector, returns true. + #[inline] + pub fn all_false(&self) -> bool { + let mut len = self.len(); + if len == 0 { + return true; + } + + if self.is_inline() { + let mask = inline_ones(len); + self.data & mask == 0 + } else { + for &storage in self.buffer() { + if len >= bits_per_storage() { + if storage != 0 { + return false; + } + len -= bits_per_storage(); + } else { + let mask = (1 << len) - 1; + if storage & mask != 0 { + return false; + } + break; + } + } + true + } + } + + /// Returns true if all the bits in the vec are set to one/true. + /// + /// On an empty vector, returns true. + #[inline] + pub fn all_true(&self) -> bool { + let mut len = self.len(); + if len == 0 { + return true; + } + + if self.is_inline() { + let mask = inline_ones(len); + self.data & mask == mask + } else { + for &storage in self.buffer() { + if len >= bits_per_storage() { + if storage != !0 { + return false; + } + len -= bits_per_storage(); + } else { + let mask = (1 << len) - 1; + if storage & mask != mask { + return false; + } + break; + } + } + true + } + } + + /// Shorten the vector, keeping the first `len` elements and dropping the rest. + /// + /// If `len` is greater than or equal to the vector's current length, this has no + /// effect. + /// + /// This does not re-allocate. + pub fn truncate(&mut self, len: usize) { + unsafe { + if len < self.len() { + self.set_len(len); + } + } + } + + /// Resizes the vector so that its length is equal to `len`. + /// + /// If `len` is less than the current length, the vector simply truncated. + /// + /// If `len` is greater than the current length, `value` is appended to the + /// vector until its length equals `len`. + pub fn resize(&mut self, len: usize, value: bool) { + let old_len = self.len(); + + if len > old_len { + unsafe { + self.reallocate(len); + self.set_len(len); + for i in old_len..len { + self.set(i, value); + } + } + } else { + self.truncate(len); + } + } + + /// Resize the vector to have capacity for at least `cap` bits. + /// + /// `cap` must be at least as large as the length of the vector. + fn reallocate(&mut self, cap: usize) { + let old_cap = self.capacity(); + if cap <= old_cap { + return; + } + assert!(self.len() <= cap); + + if self.is_heap() { + let old_buffer_len = self.header().buffer_len; + let new_buffer_len = buffer_len(cap); + + let old_alloc_len = header_len() + old_buffer_len; + let new_alloc_len = header_len() + new_buffer_len; + + let old_ptr = self.header_raw() as *mut Storage; + let mut v = unsafe { Vec::from_raw_parts(old_ptr, old_alloc_len, old_alloc_len) }; + v.resize(new_alloc_len, 0); + v.shrink_to_fit(); + self.data = v.as_ptr() as usize | HEAP_FLAG; + forget(v); + + self.header_mut().buffer_len = new_buffer_len; + } else { + let old_self = replace(self, SmallBitVec::with_capacity(cap)); + unsafe { + self.set_len(old_self.len()); + for i in 0..old_self.len() { + self.set_unchecked(i, old_self.get_unchecked(i)); + } + } + } + } + + /// If the vector owns a heap allocation, returns a pointer to the start of the allocation. + /// + /// The layout of the data at this allocation is a private implementation detail. + #[inline] + pub fn heap_ptr(&self) -> Option<*const usize> { + if self.is_heap() { + Some((self.data & !HEAP_FLAG) as *const Storage) + } else { + None + } + } + + /// Converts this `SmallBitVec` into its internal representation. + /// + /// The layout of the data inside both enum variants is a private implementation detail. + #[inline] + pub fn into_storage(self) -> InternalStorage { + if self.is_heap() { + let alloc_len = header_len() + self.header().buffer_len; + let ptr = self.header_raw() as *mut Storage; + let slice = unsafe { Box::from_raw(slice::from_raw_parts_mut(ptr, alloc_len)) }; + forget(self); + InternalStorage::Spilled(slice) + } else { + InternalStorage::Inline(self.data) + } + } + + /// Creates a `SmallBitVec` directly from the internal storage of another + /// `SmallBitVec`. + /// + /// # Safety + /// + /// This is highly unsafe. `storage` needs to have been previously generated + /// via `SmallBitVec::into_storage` (at least, it's highly likely to be + /// incorrect if it wasn't.) Violating this may cause problems like corrupting the + /// allocator's internal data structures. + /// + /// # Examples + /// + /// ``` + /// # use smallbitvec::{InternalStorage, SmallBitVec}; + /// + /// fn main() { + /// let v = SmallBitVec::from_elem(200, false); + /// + /// // Get the internal representation of the SmallBitVec. + /// // unless we transfer its ownership somewhere else. + /// let storage = v.into_storage(); + /// + /// /// Make a copy of the SmallBitVec's data. + /// let cloned_storage = match storage { + /// InternalStorage::Spilled(vs) => InternalStorage::Spilled(vs.clone()), + /// inline => inline, + /// }; + /// + /// /// Create a new SmallBitVec from the coped storage. + /// let v = unsafe { SmallBitVec::from_storage(cloned_storage) }; + /// } + /// ``` + pub unsafe fn from_storage(storage: InternalStorage) -> SmallBitVec { + match storage { + InternalStorage::Inline(data) => SmallBitVec { data }, + InternalStorage::Spilled(vs) => { + let ptr = Box::into_raw(vs); + SmallBitVec { + data: (ptr as *mut usize as usize) | HEAP_FLAG, + } + } + } + } + + /// If the rightmost bit is set, then we treat it as inline storage. + #[inline] + fn is_inline(&self) -> bool { + self.data & HEAP_FLAG == 0 + } + + /// Otherwise, `data` is a pointer to a heap allocation. + #[inline] + fn is_heap(&self) -> bool { + !self.is_inline() + } + + /// Get the header of a heap-allocated vector. + #[inline] + fn header_raw(&self) -> *mut Header { + assert!(self.is_heap()); + (self.data & !HEAP_FLAG) as *mut Header + } + + #[inline] + fn header_mut(&mut self) -> &mut Header { + unsafe { &mut *self.header_raw() } + } + + #[inline] + fn header(&self) -> &Header { + unsafe { &*self.header_raw() } + } + + /// Get the buffer of a heap-allocated vector. + #[inline] + fn buffer_raw(&self) -> *mut [Storage] { + unsafe { + let header_ptr = self.header_raw(); + let buffer_len = (*header_ptr).buffer_len; + let buffer_ptr = (header_ptr as *mut Storage) + .offset((size_of::
() / size_of::()) as isize); + slice::from_raw_parts_mut(buffer_ptr, buffer_len) + } + } + + #[inline] + fn buffer_mut(&mut self) -> &mut [Storage] { + unsafe { &mut *self.buffer_raw() } + } + + #[inline] + fn buffer(&self) -> &[Storage] { + unsafe { &*self.buffer_raw() } + } +} + +// Trait implementations: + +impl fmt::Debug for SmallBitVec { + #[inline] + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_list() + .entries(self.iter().map(|b| b as u8)) + .finish() + } +} + +impl Default for SmallBitVec { + #[inline] + fn default() -> Self { + Self::new() + } +} + +impl PartialEq for SmallBitVec { + fn eq(&self, other: &Self) -> bool { + // Compare by inline representation + if self.is_inline() && other.is_inline() { + return self.data == other.data; + } + + let len = self.len(); + if len != other.len() { + return false; + } + + // Compare by heap representation + if self.is_heap() && other.is_heap() { + let buf0 = self.buffer(); + let buf1 = other.buffer(); + + let full_blocks = len / bits_per_storage(); + let remainder = len % bits_per_storage(); + + if buf0[..full_blocks] != buf1[..full_blocks] { + return false; + } + + if remainder != 0 { + let mask = (1 << remainder) - 1; + if buf0[full_blocks] & mask != buf1[full_blocks] & mask { + return false; + } + } + return true; + } + + // Representations differ; fall back to bit-by-bit comparison + Iterator::eq(self.iter(), other.iter()) + } +} + +impl Eq for SmallBitVec {} + +impl Drop for SmallBitVec { + fn drop(&mut self) { + if self.is_heap() { + unsafe { + let header_ptr = self.header_raw(); + let alloc_ptr = header_ptr as *mut Storage; + let alloc_len = header_len() + (*header_ptr).buffer_len; + Vec::from_raw_parts(alloc_ptr, alloc_len, alloc_len); + } + } + } +} + +impl Clone for SmallBitVec { + fn clone(&self) -> Self { + if self.is_inline() { + return SmallBitVec { data: self.data }; + } + + let buffer_len = self.header().buffer_len; + let alloc_len = header_len() + buffer_len; + let ptr = self.header_raw() as *mut Storage; + let raw_allocation = unsafe { slice::from_raw_parts(ptr, alloc_len) }; + + let v = raw_allocation.to_vec(); + let header_ptr = v.as_ptr() as *mut Header; + forget(v); + SmallBitVec { + data: (header_ptr as usize) | HEAP_FLAG, + } + } +} + +impl Index for SmallBitVec { + type Output = bool; + + #[inline(always)] + fn index(&self, i: usize) -> &bool { + assert!(i < self.len(), "index out of range"); + if self.get(i).unwrap() { + &true + } else { + &false + } + } +} + +impl hash::Hash for SmallBitVec { + #[inline] + fn hash(&self, state: &mut H) { + let len = self.len(); + len.hash(state); + if self.is_inline() { + reverse_bits(self.data & inline_ones(len)).hash(state); + } else { + let full_blocks = len / bits_per_storage(); + let remainder = len % bits_per_storage(); + let buffer = self.buffer(); + if full_blocks != 0 { + buffer[..full_blocks].hash(state); + } + if remainder != 0 { + let mask = (1 << remainder) - 1; + (buffer[full_blocks] & mask).hash(state); + } + } + } +} + +impl Extend for SmallBitVec { + #[inline] + fn extend>(&mut self, iter: I) { + let iter = iter.into_iter(); + + let (min, _) = iter.size_hint(); + assert!(min <= usize::max_value(), "capacity overflow"); + self.reserve(min); + + for element in iter { + self.push(element) + } + } +} + +impl FromIterator for SmallBitVec { + #[inline] + fn from_iter>(iter: I) -> Self { + let mut v = SmallBitVec::new(); + v.extend(iter); + v + } +} + +impl IntoIterator for SmallBitVec { + type Item = bool; + type IntoIter = IntoIter; + + #[inline] + fn into_iter(self) -> IntoIter { + IntoIter { + range: 0..self.len(), + vec: self, + } + } +} + +impl<'a> IntoIterator for &'a SmallBitVec { + type Item = bool; + type IntoIter = Iter<'a>; + + #[inline] + fn into_iter(self) -> Iter<'a> { + self.iter() + } +} + +/// An iterator that owns a SmallBitVec and yields its bits as `bool` values. +/// +/// Returned from [`SmallBitVec::into_iter`][1]. +/// +/// [1]: struct.SmallBitVec.html#method.into_iter +pub struct IntoIter { + vec: SmallBitVec, + range: Range, +} + +impl Iterator for IntoIter { + type Item = bool; + + #[inline] + fn next(&mut self) -> Option { + self.range + .next() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.range.size_hint() + } +} + +impl DoubleEndedIterator for IntoIter { + #[inline] + fn next_back(&mut self) -> Option { + self.range + .next_back() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } +} + +impl ExactSizeIterator for IntoIter {} + +/// An iterator that borrows a SmallBitVec and yields its bits as `bool` values. +/// +/// Returned from [`SmallBitVec::iter`][1]. +/// +/// [1]: struct.SmallBitVec.html#method.iter +pub struct Iter<'a> { + vec: &'a SmallBitVec, + range: Range, +} + +impl<'a> Default for Iter<'a> { + #[inline] + fn default() -> Self { + const EMPTY: &'static SmallBitVec = &SmallBitVec::new(); + Self { + vec: EMPTY, + range: 0..0, + } + } +} + +impl<'a> Iterator for Iter<'a> { + type Item = bool; + + #[inline] + fn next(&mut self) -> Option { + self.range + .next() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.range.size_hint() + } +} + +impl<'a> DoubleEndedIterator for Iter<'a> { + #[inline] + fn next_back(&mut self) -> Option { + self.range + .next_back() + .map(|i| unsafe { self.vec.get_unchecked(i) }) + } +} + +impl<'a> ExactSizeIterator for Iter<'a> {} + +/// An immutable view of a range of bits from a borrowed SmallBitVec. +/// +/// Returned from [`SmallBitVec::range`][1]. +/// +/// [1]: struct.SmallBitVec.html#method.range +#[derive(Debug, Clone)] +pub struct VecRange<'a> { + vec: &'a SmallBitVec, + range: Range, +} + +impl<'a> VecRange<'a> { + #[inline] + pub fn iter(&self) -> Iter<'a> { + Iter { + vec: self.vec, + range: self.range.clone(), + } + } +} + +impl<'a> Index for VecRange<'a> { + type Output = bool; + + #[inline] + fn index(&self, i: usize) -> &bool { + let vec_i = i + self.range.start; + assert!(vec_i < self.range.end, "index out of range"); + &self.vec[vec_i] + } +} + +fn reverse_bits(mut value: usize) -> usize { + let mut result = 0; + for _ in 0..inline_bits() { + result <<= 1; + result |= value & 1; + value >>= 1; + } + result +} -- cgit v1.2.3