Struct StackMap

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

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

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

pub const fn new() -> Self

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

where K: Borrow<Q>, Q: Ord + ?Sized,

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.

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

where K: Borrow<Q>, Q: Ord + ?Sized,

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

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

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

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

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.

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);

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);

pub fn first(&self) -> Option<&(K, V)>

Returns the first kv pair in the StackMap, if any exists

Examples

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

let expected = Some(&(1, 1));
let actual = sm.first();
assert_eq!(expected, actual);

pub fn last(&self) -> Option<&(K, V)>

Returns the last kv pair in the StackMap, if any exists

Examples

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

let expected = Some(&(3, 3));
let actual = sm.last();
assert_eq!(expected, actual);

pub const fn is_full(&self) -> bool

Returns true if this StackMap is at its maximum capacity and unable to receive additional data.

Examples

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

let expected = true;
let actual = sm.is_full();
assert_eq!(expected, actual);

pub const fn len(&self) -> usize

pub const fn is_empty(&self) -> bool

Trait Implementations

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

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<K: Ord, V, const FANOUT: usize> Default for StackMap<K, V, FANOUT>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Ord, V, const FANOUT: usize> Drop for StackMap<K, V, FANOUT>

fn drop(&mut self)

Executes the destructor for this type.

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

fn eq(&self, other: &Self) -> 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.