Enum zerovec::vecs::FlexZeroVec

#[non_exhaustive]
pub enum FlexZeroVec<'a> {
    Owned(FlexZeroVecOwned),
    Borrowed(&'a FlexZeroSlice),
}

A zero-copy data structure that efficiently stores integer values.

FlexZeroVec automatically increases or decreases its storage capacity based on the largest integer stored in the vector. It therefore results in lower memory usage when smaller numbers are usually stored, but larger values must sometimes also be stored.

The maximum value that can be stored in FlexZeroVec is usize::MAX on the current platform.

FlexZeroVec is the data structure for storing usize in a ZeroMap.

FlexZeroVec derefs to FlexZeroSlice, which contains most of the methods.

Examples

Storing a vec of usizes in a zero-copy way:

use zerovec::vecs::FlexZeroVec;

// Create a FlexZeroVec and add a few numbers to it
let mut zv1 = FlexZeroVec::new();
zv1.to_mut().push(55);
zv1.to_mut().push(33);
zv1.to_mut().push(999);
assert_eq!(zv1.to_vec(), vec![55, 33, 999]);

// Convert it to bytes and back
let bytes = zv1.as_bytes();
let zv2 =
    FlexZeroVec::parse_byte_slice(bytes).expect("bytes should round-trip");
assert_eq!(zv2.to_vec(), vec![55, 33, 999]);

// Verify the compact storage
assert_eq!(7, bytes.len());
assert!(matches!(zv2, FlexZeroVec::Borrowed(_)));

Storing a map of usize to usize in a zero-copy way:

use zerovec::ZeroMap;

// Append some values to the ZeroMap
let mut zm = ZeroMap::<usize, usize>::new();
assert!(zm.try_append(&29, &92).is_none());
assert!(zm.try_append(&38, &83).is_none());
assert!(zm.try_append(&56, &65).is_none());
assert_eq!(zm.len(), 3);

// Insert another value into the middle
assert!(zm.try_append(&47, &74).is_some());
assert!(zm.insert(&47, &74).is_none());
assert_eq!(zm.len(), 4);

// Verify that the values are correct
assert_eq!(zm.get_copied(&0), None);
assert_eq!(zm.get_copied(&29), Some(92));
assert_eq!(zm.get_copied(&38), Some(83));
assert_eq!(zm.get_copied(&47), Some(74));
assert_eq!(zm.get_copied(&56), Some(65));
assert_eq!(zm.get_copied(&usize::MAX), None);

Variants (Non-exhaustive)

Non-exhaustive enums could have additional variants added in future. Therefore, when matching against variants of non-exhaustive enums, an extra wildcard arm must be added to account for any future variants.

Owned(FlexZeroVecOwned)

Borrowed(&'a FlexZeroSlice)

Implementations

impl<'a> FlexZeroVec<'a>

pub const fn new() -> Self

Creates a new, borrowed, empty FlexZeroVec.

Examples

use zerovec::vecs::FlexZeroVec;

let zv: FlexZeroVec = FlexZeroVec::new();
assert!(zv.is_empty());

pub fn parse_byte_slice(bytes: &'a [u8]) -> Result<Self, ZeroVecError>

Parses a &[u8] buffer into a FlexZeroVec.

The bytes within the byte buffer must remain constant for the life of the FlexZeroVec.

Endianness

The byte buffer must be encoded in little-endian, even if running in a big-endian environment. This ensures a consistent representation of data across platforms.

Max Value

The bytes will fail to parse if the high value is greater than the capacity of usize on this platform. For example, a FlexZeroVec created on a 64-bit platform might fail to deserialize on a 32-bit platform.

Example

use zerovec::vecs::FlexZeroVec;

let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid slice");

assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
assert_eq!(zv.get(2), Some(421));

pub fn into_owned(self) -> FlexZeroVec<'static>

Converts a borrowed FlexZeroVec to an owned FlexZeroVec. No-op if already owned.

Example

use zerovec::vecs::FlexZeroVec;

let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
assert!(matches!(zv, FlexZeroVec::Borrowed(_)));

let owned = zv.into_owned();
assert!(matches!(owned, FlexZeroVec::Owned(_)));

pub fn to_mut(&mut self) -> &mut FlexZeroVecOwned

Allows the FlexZeroVec to be mutated by converting it to an owned variant, and producing a mutable FlexZeroVecOwned.

Example

use zerovec::vecs::FlexZeroVec;

let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
let mut zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
assert!(matches!(zv, FlexZeroVec::Borrowed(_)));

zv.to_mut().push(12);
assert!(matches!(zv, FlexZeroVec::Owned(_)));
assert_eq!(zv.get(4), Some(12));

pub fn clear(&mut self)

Remove all elements from this FlexZeroVec and reset it to an empty borrowed state.

Examples

use zerovec::vecs::FlexZeroVec;

let mut zv: FlexZeroVec = [1, 2, 3].iter().copied().collect();
assert!(!zv.is_empty());
zv.clear();
assert!(zv.is_empty());

Methods from Deref<Target = FlexZeroSlice>

pub fn as_bytes(&self) -> &[u8]

Returns this slice as its underlying &[u8] byte buffer representation.

Useful for serialization.

Example

use zerovec::vecs::FlexZeroSlice;

let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x80];
let fzv = FlexZeroSlice::parse_byte_slice(bytes).expect("valid bytes");

assert_eq!(bytes, fzv.as_bytes());

pub fn as_flexzerovec(&self) -> FlexZeroVec<'_>

Borrows this FlexZeroSlice as a FlexZeroVec::Borrowed.

pub fn len(&self) -> usize

Returns the number of elements in the FlexZeroSlice.

pub(crate) fn get_width(&self) -> usize

pub fn is_empty(&self) -> bool

Returns whether there are zero elements in the FlexZeroSlice.

pub fn get(&self, index: usize) -> Option<usize>

Gets the element at index, or None if index >= self.len().

Examples

use zerovec::vecs::FlexZeroVec;

let fzv: FlexZeroVec = [22, 33].iter().copied().collect();
assert_eq!(fzv.get(0), Some(22));
assert_eq!(fzv.get(1), Some(33));
assert_eq!(fzv.get(2), None);

pub(crate) fn get_chunk(&self, index: usize) -> Option<&[u8]>

Gets the element at index as a chunk of bytes, or None if index >= self.len().

pub unsafe fn get_unchecked(&self, index: usize) -> usize

Gets the element at index without checking bounds.

Safety

index must be in-range.

pub fn first(&self) -> Option<usize>

Gets the first element of the slice, or None if the slice is empty.

pub fn last(&self) -> Option<usize>

Gets the last element of the slice, or None if the slice is empty.

pub fn iter( &self, ) -> impl DoubleEndedIterator<Item = usize> + '_ + ExactSizeIterator<Item = usize>

Gets an iterator over the elements of the slice as usize.

pub fn iter_pairs(&self) -> impl Iterator<Item = (usize, Option<usize>)> + '_

Gets an iterator over pairs of elements.

The second element of the final pair is None.

Examples

use zerovec::vecs::FlexZeroVec;

let nums: &[usize] = &[211, 281, 421, 461];
let fzv: FlexZeroVec = nums.iter().copied().collect();

let mut pairs_it = fzv.iter_pairs();

assert_eq!(pairs_it.next(), Some((211, Some(281))));
assert_eq!(pairs_it.next(), Some((281, Some(421))));
assert_eq!(pairs_it.next(), Some((421, Some(461))));
assert_eq!(pairs_it.next(), Some((461, None)));
assert_eq!(pairs_it.next(), None);

pub fn to_vec(&self) -> Vec<usize>

Creates a Vec<usize> from a FlexZeroSlice (or FlexZeroVec).

Examples

use zerovec::vecs::FlexZeroVec;

let nums: &[usize] = &[211, 281, 421, 461];
let fzv: FlexZeroVec = nums.iter().copied().collect();
let vec: Vec<usize> = fzv.to_vec();

assert_eq!(nums, vec.as_slice());

pub fn binary_search(&self, needle: usize) -> Result<usize, usize>

Binary searches a sorted FlexZeroSlice for the given usize value.

Examples

use zerovec::vecs::FlexZeroVec;

let nums: &[usize] = &[211, 281, 421, 461];
let fzv: FlexZeroVec = nums.iter().copied().collect();

assert_eq!(fzv.binary_search(0), Err(0));
assert_eq!(fzv.binary_search(211), Ok(0));
assert_eq!(fzv.binary_search(250), Err(1));
assert_eq!(fzv.binary_search(281), Ok(1));
assert_eq!(fzv.binary_search(300), Err(2));
assert_eq!(fzv.binary_search(421), Ok(2));
assert_eq!(fzv.binary_search(450), Err(3));
assert_eq!(fzv.binary_search(461), Ok(3));
assert_eq!(fzv.binary_search(462), Err(4));

pub fn binary_search_in_range( &self, needle: usize, range: Range<usize>, ) -> Option<Result<usize, usize>>

Binary searches a sorted range of a FlexZeroSlice for the given usize value.

The indices in the return value are relative to the start of the range.

Examples

use zerovec::vecs::FlexZeroVec;

// Make a FlexZeroVec with two sorted ranges: 0..3 and 3..5
let nums: &[usize] = &[111, 222, 444, 333, 555];
let fzv: FlexZeroVec = nums.iter().copied().collect();

// Search in the first range:
assert_eq!(fzv.binary_search_in_range(0, 0..3), Some(Err(0)));
assert_eq!(fzv.binary_search_in_range(111, 0..3), Some(Ok(0)));
assert_eq!(fzv.binary_search_in_range(199, 0..3), Some(Err(1)));
assert_eq!(fzv.binary_search_in_range(222, 0..3), Some(Ok(1)));
assert_eq!(fzv.binary_search_in_range(399, 0..3), Some(Err(2)));
assert_eq!(fzv.binary_search_in_range(444, 0..3), Some(Ok(2)));
assert_eq!(fzv.binary_search_in_range(999, 0..3), Some(Err(3)));

// Search in the second range:
assert_eq!(fzv.binary_search_in_range(0, 3..5), Some(Err(0)));
assert_eq!(fzv.binary_search_in_range(333, 3..5), Some(Ok(0)));
assert_eq!(fzv.binary_search_in_range(399, 3..5), Some(Err(1)));
assert_eq!(fzv.binary_search_in_range(555, 3..5), Some(Ok(1)));
assert_eq!(fzv.binary_search_in_range(999, 3..5), Some(Err(2)));

// Out-of-bounds range:
assert_eq!(fzv.binary_search_in_range(0, 4..6), None);

pub fn binary_search_by( &self, predicate: impl FnMut(usize) -> Ordering, ) -> Result<usize, usize>

Binary searches a sorted FlexZeroSlice according to a predicate function.

pub fn binary_search_in_range_by( &self, predicate: impl FnMut(usize) -> Ordering, range: Range<usize>, ) -> Option<Result<usize, usize>>

Binary searches a sorted range of a FlexZeroSlice according to a predicate function.

The indices in the return value are relative to the start of the range.

pub fn binary_search_with_index( &self, predicate: impl FnMut(usize) -> Ordering, ) -> Result<usize, usize>

Binary searches a FlexZeroSlice by its indices.

The predicate function is passed in-bounds indices into the FlexZeroSlice.

pub fn binary_search_in_range_with_index( &self, predicate: impl FnMut(usize) -> Ordering, range: Range<usize>, ) -> Option<Result<usize, usize>>

Binary searches a range of a FlexZeroSlice by its indices.

The predicate function is passed in-bounds indices into the FlexZeroSlice, which are relative to the start of the entire slice.

The indices in the return value are relative to the start of the range.

fn binary_search_impl( &self, predicate: impl FnMut(usize) -> Ordering, scaled_slice: &[u8], ) -> Result<usize, usize>

Safety

scaled_slice must be a subslice of self.data

fn binary_search_with_index_impl( &self, predicate: impl FnMut(usize) -> Ordering, scaled_slice: &[u8], ) -> Result<usize, usize>

predicate is passed a valid index as an argument.

Safety

scaled_slice must be a subslice of self.data

pub(crate) fn get_insert_info(&self, new_item: usize) -> InsertInfo

Compute the InsertInfo for inserting the specified item anywhere into the vector.

Panics

Panics if inserting the element would require allocating more than usize::MAX bytes.

pub(crate) fn get_remove_info(&self, remove_index: usize) -> RemoveInfo

Compute the RemoveInfo for removing the item at the specified index.

pub(crate) fn get_sorted_pop_info(&self) -> RemoveInfo

Returns the RemoveInfo for removing the last element. Should be called on a slice sorted in ascending order.

This is more efficient than get_remove_info() because it doesn’t require a linear traversal of the vector in order to calculate new_width.

Trait Implementations

impl<'a> AsRef<FlexZeroSlice> for FlexZeroVec<'a>

fn as_ref(&self) -> &FlexZeroSlice

Converts this type into a shared reference of the (usually inferred) input type.

impl<'a> Debug for FlexZeroVec<'a>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'a> Default for FlexZeroVec<'a>

fn default() -> Self

Returns the “default value” for a type.

impl<'a> Deref for FlexZeroVec<'a>

type Target = FlexZeroSlice

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl FromIterator<usize> for FlexZeroVec<'_>

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = usize>,

Creates a FlexZeroVec::Owned from an iterator of usize.

impl<'a> MutableZeroVecLike<'a, usize> for FlexZeroVec<'a>

type OwnedType = usize

The type returned by Self::remove() and Self::replace()

fn zvl_insert(&mut self, index: usize, value: &usize)

Insert an element at index

fn zvl_remove(&mut self, index: usize) -> usize

Remove the element at index (panicking if nonexistant)

fn zvl_replace(&mut self, index: usize, value: &usize) -> usize

Replace the element at index with another one, returning the old element

fn zvl_push(&mut self, value: &usize)

Push an element to the end of this vector

fn zvl_with_capacity(_cap: usize) -> Self

Create a new, empty vector, with given capacity

fn zvl_clear(&mut self)

Remove all elements from the vector

fn zvl_reserve(&mut self, _addl: usize)

Reserve space for addl additional elements

fn owned_as_t(o: &Self::OwnedType) -> &usize

Convert an owned value to a borrowed T

fn zvl_from_borrowed(b: &'a FlexZeroSlice) -> Self

Construct from the borrowed version of the type

fn zvl_as_borrowed_inner(&self) -> Option<&'a FlexZeroSlice>

Extract the inner borrowed variant if possible. Returns None if the data is owned.

fn zvl_permute(&mut self, permutation: &mut [usize])

Applies the permutation such that before.zvl_get(permutation[i]) == after.zvl_get(i).

impl<'a> Ord for FlexZeroVec<'a>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized + PartialOrd,

Restrict a value to a certain interval.

impl<'a, 'b> PartialEq<FlexZeroVec<'b>> for FlexZeroVec<'a>

fn eq(&self, other: &FlexZeroVec<'b>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a> PartialOrd for FlexZeroVec<'a>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<'a> Yokeable<'a> for FlexZeroVec<'static>

This impl requires enabling the optional yoke Cargo feature of the zerovec crate

type Output = FlexZeroVec<'a>

This type MUST be Self with the 'static replaced with 'a, i.e. Self<'a>

fn transform(&'a self) -> &'a Self::Output

This method must cast self between &'a Self<'static> and &'a Self<'a>.

fn transform_owned(self) -> Self::Output

This method must cast self between Self<'static> and Self<'a>.

unsafe fn make(from: Self::Output) -> Self

This method can be used to cast away Self<'a>’s lifetime.

fn transform_mut<F>(&'a mut self, f: F)

where F: 'static + for<'b> FnOnce(&'b mut Self::Output),

This method must cast self between &'a mut Self<'static> and &'a mut Self<'a>, and pass it to f.

impl<'zf> ZeroFrom<'zf, FlexZeroSlice> for FlexZeroVec<'zf>

fn zero_from(other: &'zf FlexZeroSlice) -> Self

Clone the other C into a struct that may retain references into C.

impl<'zf> ZeroFrom<'zf, FlexZeroVec<'_>> for FlexZeroVec<'zf>

fn zero_from(other: &'zf FlexZeroVec<'_>) -> Self

Clone the other C into a struct that may retain references into C.

impl<'a> ZeroVecLike<usize> for FlexZeroVec<'a>

type GetType = [u8]

The type returned by Self::get()

type SliceVariant = FlexZeroSlice

A fully borrowed version of this

fn zvl_new_borrowed() -> &'static Self::SliceVariant

Create a new, empty borrowed variant

fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize>

Search for a key in a sorted vector, returns Ok(index) if found, returns Err(insert_index) if not found, where insert_index is the index where it should be inserted to maintain sort order.

fn zvl_binary_search_in_range( &self, k: &usize, range: Range<usize>, ) -> Option<Result<usize, usize>>

Search for a key within a certain range in a sorted vector. Returns None if the range is out of bounds, and Ok or Err in the same way as zvl_binary_search. Indices are returned relative to the start of the range.

fn zvl_binary_search_by( &self, predicate: impl FnMut(&usize) -> Ordering, ) -> Result<usize, usize>

Search for a key in a sorted vector by a predicate, returns Ok(index) if found, returns Err(insert_index) if not found, where insert_index is the index where it should be inserted to maintain sort order.

fn zvl_binary_search_in_range_by( &self, predicate: impl FnMut(&usize) -> Ordering, range: Range<usize>, ) -> Option<Result<usize, usize>>

Search for a key within a certain range in a sorted vector by a predicate. Returns None if the range is out of bounds, and Ok or Err in the same way as zvl_binary_search. Indices are returned relative to the start of the range.

fn zvl_get(&self, index: usize) -> Option<&[u8]>

Get element at index

fn zvl_len(&self) -> usize

The length of this vector

fn zvl_as_borrowed(&self) -> &FlexZeroSlice

Construct a borrowed variant by borrowing from &self.

fn zvl_get_as_t<R>(g: &[u8], f: impl FnOnce(&usize) -> R) -> R

Obtain a reference to T, passed to a closure

fn zvl_is_ascending(&self) -> bool

where T: Ord,

Check if this vector is in ascending order according to Ts Ord impl

fn zvl_is_empty(&self) -> bool

Check if this vector is empty

fn t_cmp_get(t: &T, g: &Self::GetType) -> Ordering

where T: Ord,

Compare this type with a Self::GetType. This must produce the same result as if g were converted to Self

fn get_cmp_get(a: &Self::GetType, b: &Self::GetType) -> Ordering

where T: Ord,

Compare two values of Self::GetType. This must produce the same result as if both a and b were converted to Self

impl Eq for FlexZeroVec<'_>