Struct HeaplessLruCache 

pub struct HeaplessLruCache<K, V, const N: usize, I: IndexType = u8> {
    pub map: FnvIndexMap<K, I, N>,
    pub keys: [MaybeUninit<K>; N],
    pub values: [MaybeUninit<V>; N],
    pub prevs: [I; N],
    pub nexts: [I; N],
    pub free_head: I,
    pub head: I,
    pub tail: I,
    pub num_entries: I,
}

A stack-allocated LRU cache with $O(1)$ performance.

Architecture & Pseudocode

This cache uses a Struct-of-Arrays (SoA) layout combined with an intrusive doubly-linked list and a free list, all residing entirely on the stack.

• map: A heapless::IndexMap<K, I, N> mapping keys to their physical slot indices.
• keys, values: Storage slots for the actual data (MaybeUninit to avoid generic Default bounds).
• prevs, nexts: Parallel arrays representing the doubly-linked list of LRU order. The nexts array also doubles as the singly-linked free list for available slots.
• head, tail: Pointers to the Most Recently Used (MRU) and Least Recently Used (LRU) slots.
• free_head: Pointer to the first available empty slot.

Put Algorithm

1. If key exists in `map` at `idx`:
   a. Update `values[idx]`.
   b. Promote `idx` to `head` (MRU).
2. Else (new key):
   a. If cache is logically full (`len >= cap`), call `pop_lru_internal()`:
      i.  Read `idx = tail`.
      ii. Remove `keys[idx]` from `map`.
      iii. Detach `idx` from LRU list, push to `free_head`.
   b. If `len == N` (absolute stack capacity), return Err (triggers heap spill in wrapper).
   c. Pop `idx` from `free_head`.
   d. Write `key` to `keys[idx]` and `value` to `values[idx]`.
   e. Insert `key -> idx` into `map`.
   f. Attach `idx` to `head` (MRU).

Fields

map: FnvIndexMap<K, I, N>

Automatically generated documentation for this item.

keys: [MaybeUninit<K>; N]

Automatically generated documentation for this item.

values: [MaybeUninit<V>; N]

Automatically generated documentation for this item.

prevs: [I; N]

Automatically generated documentation for this item.

nexts: [I; N]

Automatically generated documentation for this item.

free_head: I

Automatically generated documentation for this item.

head: I

Automatically generated documentation for this item.

tail: I

Automatically generated documentation for this item.

num_entries: I

Automatically generated documentation for this item.

Implementations

impl<K, V, const N: usize, I: IndexType> HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Clone,

pub fn new() -> Self

Automatically generated documentation for this item.

pub fn len(&self) -> usize

Returns the number of elements.

pub fn is_empty(&self) -> bool

Returns true if the collection is empty.

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key.

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key.

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the next item.

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

Returns a reference to the next item.

pub fn iter(&self) -> Iter<'_, K, V, N, I>

Returns an iterator over the elements.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V, N, I>

Returns an iterator over the elements.

pub fn put( &mut self, key: K, value: V, cap: usize, ) -> (Option<V>, Result<(), (K, V)>)

Pushes a key-value pair, updating the LRU list.

Trait Implementations

impl<K, V, const N: usize, I: IndexType> AnyLruCache<K, V> for HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Ord + Clone,

fn len(&self) -> usize

Returns the number of key-value pairs that are currently on this backend.

fn cap(&self) -> NonZeroUsize

Returns the logical maximum capacity of this cache backend.

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

Inserts a key-value pair, updating the value if the key already exists. Returns the old value if the key was present.

fn put_with_cap( &mut self, key: K, value: V, cap: NonZeroUsize, ) -> (Option<V>, Result<(), (K, V)>)

Inserts a key-value pair with a specific maximum capacity enforcement. Returns (old_value, Result<(), (key, value)>). The result is an error if capacity is reached and the backend cannot grow.

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

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

Returns a reference to the value corresponding to the key, moving it to the MRU position.

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

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

Returns a mutable reference to the value corresponding to the key, moving it to the MRU position.

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

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

Returns a reference to the value corresponding to the key without updating the LRU state.

fn clear(&mut self)

Clears the cache, removing all values.

fn pop_lru(&mut self) -> Option<(K, V)>

Removes and returns the explicitly Least Recently Used key-value pair.

fn contains<Q>(&self, key: &Q) -> bool

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

Checks if the cache contains the given key.

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

Pushes a key-value pair into the cache. If the key already exists, updates the value. If pushing causes the capacity to be exceeded, returns the evicted LRU entry.

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

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

Removes the given key from the cache and returns its associated value.

fn pop_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>

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

Removes the given key from the cache and returns the (key, value) pair.

fn promote<Q>(&mut self, key: &Q)

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

Explicitly marks the given key as the Most Recently Used.

fn demote<Q>(&mut self, key: &Q)

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

Explicitly marks the given key as the Least Recently Used.

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

Returns a reference to the Least Recently Used pair without removing it.

fn is_empty(&self) -> bool

Returns true if the cache is empty.

impl<K, V, const N: usize, I: IndexType> Clone for HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Clone, V: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V, const N: usize, I: IndexType> Debug for HeaplessLruCache<K, V, N, I>

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

Formats the value using the given formatter.

impl<K: Hash + Eq + Clone, V, const N: usize, I: IndexType> Default for HeaplessLruCache<K, V, N, I>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, const N: usize, I: IndexType> Drop for HeaplessLruCache<K, V, N, I>

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V, const N: usize, I> Extend<(K, V)> for HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Ord + Clone, I: IndexType,

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, const N: usize, I> FromIterator<(K, V)> for HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Ord + Clone, I: IndexType,

fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self

Creates a value from an iterator.

impl<'a, K, V, const N: usize, I: IndexType> IntoIterator for &'a HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Clone,

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, N, I>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, const N: usize, I: IndexType> IntoIterator for &'a mut HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Clone,

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V, N, I>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, const N: usize, I: IndexType> IntoIterator for HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Ord + Clone,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, N, I>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, const N: usize, I: IndexType> LruIteratorSupport<'a, K, V> for HeaplessLruCache<K, V, N, I>

where K: Hash + Eq + Ord + Clone + 'a, V: 'a,

type Iter = Iter<'a, K, V, N, I>

The associated specific type.

type IterMut = IterMut<'a, K, V, N, I>

The associated specific type.

fn iter(&'a self) -> Self::Iter

Returns an iterator over the elements.

fn iter_mut(&'a mut self) -> Self::IterMut

Returns an iterator over the elements.