Struct BoundedLruCache 

pub struct BoundedLruCache<K, V> { /* private fields */ }

A small bounded LRU cache for hot-path caches.

Hits update recency in place, so the common path is a single hash lookup. Eviction unlinks the oldest entry, which costs the same whether the cache holds ten entries or ten thousand.

The recency order is a linked list rather than a timestamp per entry because a timestamp makes eviction a scan for the minimum. These caches are large – thousands of glyph masks – and the workloads that need them most are the ones that miss steadily: text whose size animates re-rasterises every glyph of every frame, and every one of those inserts was walking the whole table to decide what to drop.

The index holds slot numbers only and compares a probe against the key in its slot, so each key is stored once: a full text cache’s index takes five bytes an entry instead of a second copy of every key.

The index and slots grow with the entries rather than reserving the bound: most caches of a process never come near it, and a table sized for thousands of entries each is megabytes a small screen never touches.

Implementations

impl<K, V> BoundedLruCache<K, V>

where K: Eq + Hash,

pub fn new(cap: NonZeroUsize) -> Self

pub fn with_capacity_at_least_one(cap: usize) -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn cap(&self) -> NonZeroUsize

pub fn set_cap(&mut self, cap: NonZeroUsize)

Sets the bound, evicting the least recently used entries past it.

pub fn clear(&mut self)

Drops every entry and gives back the storage they took.

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

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

The lookups take any form of the key the stored key borrows as, so a caller can probe with a borrowed view instead of building an owned key.

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

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

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

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

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

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

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

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

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

The least recently used entry, without touching its recency.

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

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

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

Entries most recently used first.