Struct ZeroMap

pub struct ZeroMap<'a, K, V>
where
    K: ZeroMapKV<'a> + ?Sized,
    V: ZeroMapKV<'a> + ?Sized,
{ /* private fields */ }

A zero-copy map datastructure, built on sorted binary-searchable ZeroVec and VarZeroVec.

This type, like ZeroVec and VarZeroVec, is able to zero-copy deserialize from appropriately formatted byte buffers. It is internally copy-on-write, so it can be mutated afterwards as necessary.

Internally, a ZeroMap is a zero-copy vector for keys paired with a zero-copy vector for values, sorted by the keys. Therefore, all types used in ZeroMap need to work with either ZeroVec or VarZeroVec.

This does mean that for fixed-size data, one must use the regular type (u32, u8, char, etc), whereas for variable-size data, ZeroMap will use the dynamically sized version (str not String, ZeroSlice not ZeroVec, FooULE not Foo for custom types)

Examples

use zerovec::ZeroMap;

#[derive(serde::Serialize, serde::Deserialize)]
struct Data<'a> {
    #[serde(borrow)]
    map: ZeroMap<'a, u32, str>,
}

let mut map = ZeroMap::new();
map.insert(&1, "one");
map.insert(&2, "two");
map.insert(&4, "four");

let data = Data { map };

let bincode_bytes =
    bincode::serialize(&data).expect("Serialization should be successful");

// Will deserialize without any allocations
let deserialized: Data = bincode::deserialize(&bincode_bytes)
    .expect("Deserialization should be successful");

assert_eq!(data.map.get(&1), Some("one"));
assert_eq!(data.map.get(&2), Some("two"));

Implementations

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized,

pub fn new() -> Self

Creates a new, empty ZeroMap<K, V>.

Examples

use zerovec::ZeroMap;

let zm: ZeroMap<u16, str> = ZeroMap::new();
assert!(zm.is_empty());

pub fn with_capacity(capacity: usize) -> Self

Construct a new ZeroMap with a given capacity

pub fn as_borrowed(&'a self) -> ZeroMapBorrowed<'a, K, V>

Obtain a borrowed version of this map

pub fn len(&self) -> usize

The number of elements in the ZeroMap

pub fn is_empty(&self) -> bool

Whether the ZeroMap is empty

pub fn clear(&mut self)

Remove all elements from the ZeroMap

pub fn reserve(&mut self, additional: usize)

Reserve capacity for additional more elements to be inserted into the ZeroMap to avoid frequent reallocations.

See Vec::reserve() for more information.

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized + Ord, V: ZeroMapKV<'a> + ?Sized,

pub fn get(&self, key: &K) -> Option<&V::GetType>

Get the value associated with key, if it exists.

For fixed-size (AsULE) V types, this will return their corresponding AsULE::ULE type. If you wish to work with the V type directly, Self::get_copied() exists for convenience.

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, "one");
map.insert(&2, "two");
assert_eq!(map.get(&1), Some("one"));
assert_eq!(map.get(&3), None);

pub fn get_by( &self, predicate: impl FnMut(&K) -> Ordering, ) -> Option<&V::GetType>

Binary search the map with predicate to find a key, returning the value.

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, "one");
map.insert(&2, "two");
assert_eq!(map.get_by(|probe| probe.cmp(&1)), Some("one"));
assert_eq!(map.get_by(|probe| probe.cmp(&3)), None);

pub fn contains_key(&self, key: &K) -> bool

Returns whether key is contained in this map

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, "one");
map.insert(&2, "two");
assert!(map.contains_key(&1));
assert!(!map.contains_key(&3));

pub fn insert(&mut self, key: &K, value: &V) -> Option<V::OwnedType>

Insert value with key, returning the existing value if it exists.

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, "one");
map.insert(&2, "two");
assert_eq!(map.get(&1), Some("one"));
assert_eq!(map.get(&3), None);

pub fn remove(&mut self, key: &K) -> Option<V::OwnedType>

Remove the value at key, returning it if it exists.

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, "one");
map.insert(&2, "two");
assert_eq!(map.remove(&1), Some("one".to_owned().into_boxed_str()));
assert_eq!(map.get(&1), None);

pub fn try_append<'b>( &mut self, key: &'b K, value: &'b V, ) -> Option<(&'b K, &'b V)>

Appends value with key to the end of the underlying vector, returning key and value if it failed. Useful for extending with an existing sorted list.

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
assert!(map.try_append(&1, "uno").is_none());
assert!(map.try_append(&3, "tres").is_none());

let unsuccessful = map.try_append(&3, "tres-updated");
assert!(unsuccessful.is_some(), "append duplicate of last key");

let unsuccessful = map.try_append(&2, "dos");
assert!(unsuccessful.is_some(), "append out of order");

assert_eq!(map.get(&1), Some("uno"));

// contains the original value for the key: 3
assert_eq!(map.get(&3), Some("tres"));

// not appended since it wasn't in order
assert_eq!(map.get(&2), None);

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized,

pub fn iter<'b>( &'b self, ) -> impl ExactSizeIterator<Item = (&'b <K as ZeroMapKV<'a>>::GetType, &'b <V as ZeroMapKV<'a>>::GetType)>

Produce an ordered iterator over key-value pairs

pub fn iter_keys<'b>( &'b self, ) -> impl ExactSizeIterator<Item = &'b <K as ZeroMapKV<'a>>::GetType>

Produce an ordered iterator over keys

pub fn iter_values<'b>( &'b self, ) -> impl ExactSizeIterator<Item = &'b <V as ZeroMapKV<'a>>::GetType>

Produce an iterator over values, ordered by keys

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a, Container = ZeroVec<'a, K>> + ?Sized + AsULE, V: ZeroMapKV<'a> + ?Sized,

pub fn cast_zv_k_unchecked<P>(self) -> ZeroMap<'a, P, V>

where P: AsULE<ULE = K::ULE> + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,

Cast a ZeroMap<K, V> to ZeroMap<P, V> where K and P are AsULE types with the same representation.

Unchecked Invariants

If K and P have different ordering semantics, unexpected behavior may occur.

pub fn try_convert_zv_k_unchecked<P>( self, ) -> Result<ZeroMap<'a, P, V>, ZeroVecError>

where P: AsULE + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,

Convert a ZeroMap<K, V> to ZeroMap<P, V> where K and P are AsULE types with the same size.

Unchecked Invariants

If K and P have different ordering semantics, unexpected behavior may occur.

Panics

Panics if K::ULE and P::ULE are not the same size.

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized + AsULE,

pub fn cast_zv_v_unchecked<P>(self) -> ZeroMap<'a, K, P>

where P: AsULE<ULE = V::ULE> + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,

Cast a ZeroMap<K, V> to ZeroMap<K, P> where V and P are AsULE types with the same representation.

Unchecked Invariants

If V and P have different ordering semantics, unexpected behavior may occur.

pub fn try_convert_zv_v_unchecked<P>( self, ) -> Result<ZeroMap<'a, K, P>, ZeroVecError>

where P: AsULE + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,

Convert a ZeroMap<K, V> to ZeroMap<K, P> where V and P are AsULE types with the same size.

Unchecked Invariants

If V and P have different ordering semantics, unexpected behavior may occur.

Panics

Panics if V::ULE and P::ULE are not the same size.

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized + Ord, V: ZeroMapKV<'a, Container = VarZeroVec<'a, V>> + ?Sized + VarULE,

pub fn insert_var_v<VE: EncodeAsVarULE<V>>( &mut self, key: &K, value: &VE, ) -> Option<Box<V>>

Same as insert(), but allows using EncodeAsVarULE types with the value to avoid an extra allocation when dealing with custom ULE types.

use std::borrow::Cow;
use zerovec::ZeroMap;

#[zerovec::make_varule(PersonULE)]
#[derive(Clone, Eq, PartialEq, Ord, PartialOrd)]
struct Person<'a> {
    age: u8,
    name: Cow<'a, str>,
}

let mut map: ZeroMap<u32, PersonULE> = ZeroMap::new();
map.insert_var_v(
    &1,
    &Person {
        age: 20,
        name: "Joseph".into(),
    },
);
map.insert_var_v(
    &1,
    &Person {
        age: 35,
        name: "Carla".into(),
    },
);
assert_eq!(&map.get(&1).unwrap().name, "Carla");
assert!(map.get(&3).is_none());

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized + Ord, V: ZeroMapKV<'a> + ?Sized + Copy,

pub fn get_copied(&self, key: &K) -> Option<V>

For cases when V is fixed-size, obtain a direct copy of V instead of V::ULE.

Examples

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, &'a');
map.insert(&2, &'b');
assert_eq!(map.get_copied(&1), Some('a'));
assert_eq!(map.get_copied(&3), None);

pub fn get_copied_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<V>

Binary search the map with predicate to find a key, returning the value.

For cases when V is fixed-size, use this method to obtain a direct copy of V instead of V::ULE.

Examples

use zerovec::ZeroMap;

let mut map = ZeroMap::new();
map.insert(&1, &'a');
map.insert(&2, &'b');
assert_eq!(map.get_copied_by(|probe| probe.cmp(&1)), Some('a'));
assert_eq!(map.get_copied_by(|probe| probe.cmp(&3)), None);

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized + AsULE + Copy,

pub fn iter_copied_values<'b>( &'b self, ) -> impl Iterator<Item = (&'b <K as ZeroMapKV<'a>>::GetType, V)>

Similar to Self::iter() except it returns a direct copy of the values instead of references to V::ULE, in cases when V is fixed-size

impl<'a, K, V> ZeroMap<'a, K, V>

where K: ZeroMapKV<'a, Container = ZeroVec<'a, K>> + ?Sized + AsULE + Copy, V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized + AsULE + Copy,

pub fn iter_copied<'b>(&'b self) -> impl Iterator<Item = (K, V)> + 'b

Similar to Self::iter() except it returns a direct copy of the keys values instead of references to K::ULE and V::ULE, in cases when K and V are fixed-size

Trait Implementations

impl<'a, K, V> Clone for ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized, <K as ZeroMapKV<'a>>::Container: Clone, <V as ZeroMapKV<'a>>::Container: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a, K, V> Debug for ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized, <K as ZeroMapKV<'a>>::Container: Debug, <V as ZeroMapKV<'a>>::Container: Debug,

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

Formats the value using the given formatter.

impl<'a, K, V> Default for ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized,

fn default() -> Self

Returns the “default value” for a type.

impl<'a, K, V> From<ZeroMapBorrowed<'a, K, V>> for ZeroMap<'a, K, V>

where K: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized,

fn from(other: ZeroMapBorrowed<'a, K, V>) -> Self

Converts to this type from the input type.

impl<'a, A, B, K, V> FromIterator<(A, B)> for ZeroMap<'a, K, V>

where A: Borrow<K>, B: Borrow<V>, K: ZeroMapKV<'a> + ?Sized + Ord, V: ZeroMapKV<'a> + ?Sized,

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

where T: IntoIterator<Item = (A, B)>,

Creates a value from an iterator.

impl<'a, 'b, K, V> PartialEq<ZeroMap<'b, K, V>> for ZeroMap<'a, K, V>

where K: for<'c> ZeroMapKV<'c> + ?Sized, V: for<'c> ZeroMapKV<'c> + ?Sized, <K as ZeroMapKV<'a>>::Container: PartialEq<<K as ZeroMapKV<'b>>::Container>, <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>,

fn eq(&self, other: &ZeroMap<'b, K, V>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<'a, K, V> Yokeable<'a> for ZeroMap<'static, K, V>

where K: 'static + for<'b> ZeroMapKV<'b> + ?Sized, V: 'static + for<'b> ZeroMapKV<'b> + ?Sized, <K as ZeroMapKV<'static>>::Container: for<'b> Yokeable<'b>, <V as ZeroMapKV<'static>>::Container: for<'b> Yokeable<'b>,

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

type Output = ZeroMap<'a, K, V>

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, 's, K, V> ZeroFrom<'zf, ZeroMap<'s, K, V>> for ZeroMap<'zf, K, V>

where K: 'static + for<'b> ZeroMapKV<'b> + ?Sized, V: 'static + for<'b> ZeroMapKV<'b> + ?Sized, <K as ZeroMapKV<'zf>>::Container: ZeroFrom<'zf, <K as ZeroMapKV<'s>>::Container>, <V as ZeroMapKV<'zf>>::Container: ZeroFrom<'zf, <V as ZeroMapKV<'s>>::Container>,

fn zero_from(other: &'zf ZeroMap<'s, K, V>) -> Self

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