Struct stack_map::StackMap

source ·

pub struct StackMap<K: Clone + Ord, V: Clone, const FANOUT: usize> { /* private fields */ }

Expand description

StackMap is a constant-size, zero-allocation associative container backed by an array. It can be used as a building block for various interesting higher-level data structures.

Implementations§

source §

impl<K: Clone + Ord, V: Clone, const FANOUT: usize> StackMap<K, V, FANOUT>

source

pub fn get<Q>(&self, key: &Q) -> Option<&V>where K: Borrow<Q>, Q: Ord + ?Sized,

source

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

Inserts an item and return the previous value if it exists.

Panics

This method will panic if called with a new key-value pair when already full.

The StackMap should be checked to ensure that it is not already full before calling this method. It is full when the self.is_full() method returns true, which happens when self.len() == FANOUT.

source

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>where K: Borrow<Q>, Q: Ord + ?Sized,

source

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

source

pub fn iter(&self) -> impl DoubleEndedIterator<Item = &(K, V)>

source

pub fn split_off(&mut self, split_idx: usize) -> (K, Self)

Splits this StackMap into two. self will retain all key-value pairs before the provided split index. Returns the split key at the given split index and a new StackMap created out of all key-value pairs at or after the provided split index.

source

pub fn get_index(&self, index: usize) -> Option<&(K, V)>

Get a key-value pair based on its internal relative index in the backing array.

source

pub fn get_less_than_or_equal<Q>(&self, key: &Q) -> Option<&(K, V)>where K: Borrow<Q>, Q: Ord + ?Sized,

Get the key-value pair that is less than or equal to the provided key. Useful for any least upper bound operation, such as MVCC lookups where the key is suffixed by a version or an internal b-tree index lookup where you are looking for the next node based on a node’s low key.

Examples

let mut map = stack_map::StackMap::<u8, u8, 64>::default();
map.insert(1, 1);
map.insert(2, 2);
map.insert(3, 3);

let lt = map.get_less_than_or_equal(&4).unwrap();
let expected = &(3, 3);
assert_eq!(expected, lt);

let lt = map.get_less_than_or_equal(&3).unwrap();
let expected = &(3, 3);
assert_eq!(expected, lt);

let lt = map.get_less_than_or_equal(&2).unwrap();
let expected = &(2, 2);
assert_eq!(expected, lt);

let lt = map.get_less_than_or_equal(&1).unwrap();
let expected = &(1, 1);
assert_eq!(expected, lt);

let lt = map.get_less_than_or_equal(&0);
let expected = None;
assert_eq!(expected, lt);

source

pub fn get_less_than<Q>(&self, key: &Q) -> Option<&(K, V)>where K: Borrow<Q>, Q: Ord + ?Sized,

Gets a kv pair that has a key that is less than the provided key.

Examples

let mut map = stack_map::StackMap::<u8, u8, 64>::default();
map.insert(1, 1);
map.insert(2, 2);
map.insert(3, 3);

let lt = map.get_less_than(&4).unwrap();
let expected = &(3, 3);
assert_eq!(expected, lt);

let lt = map.get_less_than(&3).unwrap();
let expected = &(2, 2);
assert_eq!(expected, lt);

let lt = map.get_less_than(&2).unwrap();
let expected = &(1, 1);
assert_eq!(expected, lt);

let lt = map.get_less_than(&1);
let expected = None;
assert_eq!(expected, lt);

let lt = map.get_less_than(&0);
let expected = None;
assert_eq!(expected, lt);