Struct zerovec::map2d::map::ZeroMap2d

pub struct ZeroMap2d<'a, K0, K1, V>
where
    K0: ZeroMapKV<'a> + ?Sized,
    K1: ZeroMapKV<'a> + ?Sized,
    V: ZeroMapKV<'a> + ?Sized,
{
    pub(crate) keys0: K0::Container,
    pub(crate) joiner: ZeroVec<'a, u32>,
    pub(crate) keys1: K1::Container,
    pub(crate) values: V::Container,
}

A zero-copy, two-dimensional map datastructure .

This is an extension of ZeroMap that supports two layers of keys. For example, to map a pair of an integer and a string to a buffer, you can write:

let _: ZeroMap2d<u32, str, [u8]> = unimplemented!();

Internally, ZeroMap2d stores four zero-copy vectors, one for each type argument plus one more to match between the two vectors of keys.

Examples

use zerovec::ZeroMap2d;

// Example byte buffer representing the map { 1: {2: "three" } }
let BINCODE_BYTES: &[u8; 51] = &[
    2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0,
    0, 0, 0, 0, 0, 0, 2, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116,
    104, 114, 101, 101,
];

// Deserializing to ZeroMap requires no heap allocations.
let zero_map: ZeroMap2d<u16, u16, str> =
    bincode::deserialize(BINCODE_BYTES)
        .expect("Should deserialize successfully");
assert_eq!(zero_map.get_2d(&1, &2), Some("three"));

Fields

keys0: K0::Container

joiner: ZeroVec<'a, u32>

keys1: K1::Container

values: V::Container

Implementations

impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>

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

pub fn new() -> Self

Creates a new, empty ZeroMap2d.

Examples

use zerovec::ZeroMap2d;

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

pub fn with_capacity(capacity: usize) -> Self

Construct a new ZeroMap2d with a given capacity

pub fn as_borrowed(&'a self) -> ZeroMap2dBorrowed<'a, K0, K1, V>

Obtain a borrowed version of this map

pub fn len(&self) -> usize

The number of values in the ZeroMap2d

pub fn is_empty(&self) -> bool

Whether the ZeroMap2d is empty

pub fn clear(&mut self)

Remove all elements from the ZeroMap2d

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

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

See Vec::reserve() for more information.

pub fn iter0<'l>( &'l self, ) -> impl Iterator<Item = ZeroMap2dCursor<'l, 'a, K0, K1, V>> + 'l

Produce an ordered iterator over keys0, which can then be used to get an iterator over keys1 for a particular key0.

Example

Loop over all elements of a ZeroMap2d:

use zerovec::ZeroMap2d;

let mut map: ZeroMap2d<u16, u16, str> = ZeroMap2d::new();
map.insert(&1, &1, "foo");
map.insert(&2, &3, "bar");
map.insert(&2, &4, "baz");

let mut total_value = 0;

for cursor in map.iter0() {
    for (key1, value) in cursor.iter1() {
        // This code runs for every (key0, key1) pair
        total_value += cursor.key0().as_unsigned_int() as usize;
        total_value += key1.as_unsigned_int() as usize;
        total_value += value.len();
    }
}

assert_eq!(total_value, 22);

fn get_range_for_key0_index(&self, key0_index: usize) -> Range<usize>

Given an index into the joiner array, returns the corresponding range of keys1

fn remove_key0_index(&mut self, key0_index: usize)

Removes key0_index from the keys0 array and the joiner array

fn joiner_expand(&mut self, key0_index: usize)

Shifts all joiner ranges from key0_index onward one index up

fn joiner_shrink(&mut self, key0_index: usize)

Shifts all joiner ranges from key0_index onward one index down

impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>

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

pub fn get_2d(&self, key0: &K0, key1: &K1) -> Option<&V::GetType>

Get the value associated with key0 and key1, if it exists.

For more fine-grained error handling, use ZeroMap2d::get0.

use zerovec::ZeroMap2d;

let mut map = ZeroMap2d::new();
map.insert(&1, "one", "foo");
map.insert(&2, "one", "bar");
map.insert(&2, "two", "baz");
assert_eq!(map.get_2d(&1, "one"), Some("foo"));
assert_eq!(map.get_2d(&1, "two"), None);
assert_eq!(map.get_2d(&2, "one"), Some("bar"));
assert_eq!(map.get_2d(&2, "two"), Some("baz"));
assert_eq!(map.get_2d(&3, "three"), None);

pub fn insert( &mut self, key0: &K0, key1: &K1, value: &V, ) -> Option<V::OwnedType>

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

use zerovec::ZeroMap2d;

let mut map = ZeroMap2d::new();
assert_eq!(map.insert(&0, "zero", "foo"), None,);
assert_eq!(map.insert(&1, "one", "bar"), None,);
assert_eq!(map.insert(&1, "one", "baz").as_deref(), Some("bar"),);
assert_eq!(map.get_2d(&1, "one").as_deref(), Some("baz"));
assert_eq!(map.len(), 2);

pub fn remove(&mut self, key0: &K0, key1: &K1) -> Option<V::OwnedType>

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

use zerovec::ZeroMap2d;

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

pub fn try_append<'b>( &mut self, key0: &'b K0, key1: &'b K1, value: &'b V, ) -> Option<(&'b K0, &'b K1, &'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::ZeroMap2d;

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

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

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

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

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

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

pub(crate) fn check_invariants(&self)

impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>

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

pub fn get0<'l>( &'l self, key0: &K0, ) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>>

Gets a cursor for key0. If None, then key0 is not in the map. If Some, then key0 is in the map, and key1 can be queried.

use zerovec::ZeroMap2d;

let mut map = ZeroMap2d::new();
map.insert(&1u32, "one", "foo");
map.insert(&2, "one", "bar");
map.insert(&2, "two", "baz");
assert_eq!(map.get0(&1).unwrap().get1("one").unwrap(), "foo");
assert_eq!(map.get0(&1).unwrap().get1("two"), None);
assert_eq!(map.get0(&2).unwrap().get1("one").unwrap(), "bar");
assert_eq!(map.get0(&2).unwrap().get1("two").unwrap(), "baz");
assert_eq!(map.get0(&3), None);

pub fn get0_by<'l>( &'l self, predicate: impl FnMut(&K0) -> Ordering, ) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>>

Binary search the map for key0, returning a cursor.

use zerovec::ZeroMap2d;

let mut map = ZeroMap2d::new();
map.insert(&1, "one", "foo");
map.insert(&2, "two", "bar");
assert!(matches!(map.get0_by(|probe| probe.cmp(&1)), Some(_)));
assert!(matches!(map.get0_by(|probe| probe.cmp(&3)), None));

pub fn contains_key0(&self, key0: &K0) -> bool

Returns whether key0 is contained in this map

use zerovec::ZeroMap2d;

let mut map = ZeroMap2d::new();
map.insert(&1, "one", "foo");
map.insert(&2, "two", "bar");
assert!(map.contains_key0(&1));
assert!(!map.contains_key0(&3));

fn get_or_insert_range_for_key0(&mut self, key0: &K0) -> (usize, Range<usize>)

Same as get_range_for_key0, but creates key0 if it doesn’t already exist

impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>

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

pub fn get_copied_2d(&self, key0: &K0, key1: &K1) -> Option<V>

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

Examples

let mut map: ZeroMap2d<u16, u16, u16> = ZeroMap2d::new();
map.insert(&1, &2, &3);
map.insert(&1, &4, &5);
map.insert(&6, &7, &8);

assert_eq!(map.get_copied_2d(&6, &7), Some(8));

Trait Implementations

impl<'a, K0, K1, V> Clone for ZeroMap2d<'a, K0, K1, V>

where K0: ZeroMapKV<'a> + ?Sized, K1: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized, <K0 as ZeroMapKV<'a>>::Container: Clone, <K1 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, K0, K1, V> Debug for ZeroMap2d<'a, K0, K1, V>

where K0: ZeroMapKV<'a> + ?Sized, K1: ZeroMapKV<'a> + ?Sized, V: ZeroMapKV<'a> + ?Sized, <K0 as ZeroMapKV<'a>>::Container: Debug, <K1 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, K0, K1, V> Default for ZeroMap2d<'a, K0, K1, V>

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

fn default() -> Self

Returns the “default value” for a type.

impl<'a, K0, K1, V> From<ZeroMap2dBorrowed<'a, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>

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

fn from(other: ZeroMap2dBorrowed<'a, K0, K1, V>) -> Self

Converts to this type from the input type.

impl<'a, A, B, C, K0, K1, V> FromIterator<(A, B, C)> for ZeroMap2d<'a, K0, K1, V>

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

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

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

Creates a value from an iterator.

impl<'a, 'b, K0, K1, V> PartialEq<ZeroMap2d<'b, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>

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

fn eq(&self, other: &ZeroMap2d<'b, K0, K1, V>) -> 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, K0, K1, V> Yokeable<'a> for ZeroMap2d<'static, K0, K1, V>

where K0: 'static + for<'b> ZeroMapKV<'b> + ?Sized, K1: 'static + for<'b> ZeroMapKV<'b> + ?Sized, V: 'static + for<'b> ZeroMapKV<'b> + ?Sized, <K0 as ZeroMapKV<'static>>::Container: for<'b> Yokeable<'b>, <K1 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 = ZeroMap2d<'a, K0, K1, 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, K0, K1, V> ZeroFrom<'zf, ZeroMap2d<'s, K0, K1, V>> for ZeroMap2d<'zf, K0, K1, V>

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

fn zero_from(other: &'zf ZeroMap2d<'s, K0, K1, V>) -> Self

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