Struct LRUCache

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

LRU Cache implementation using intrusive collections.

This cache uses an intrusive_collections::LinkedList to maintain the LRU order, and an intrusive_collections::RBTree to allow for efficient lookups by key, while maintaining only one allocation per key-value pair. Unfortunately, this is a linked structure, so cache locality is likely poor, but memory usage and flexibility are improved.

The cache is unbounded by default, but can be limited to a maximum capacity.

The smart_* methods allow for reading or updating the LRU order at the same time, based on how the value is accessed. The get method always updates the LRU order, and the peek_* methods allow for reading without updating the LRU order.

Example

use intrusive_lru_cache::LRUCache;

let mut lru: LRUCache<&'static str, &'static str> = LRUCache::default();

lru.insert("a", "1");
lru.insert("b", "2");
lru.insert("c", "3");

let _ = lru.get("b"); // updates LRU order

assert_eq!(lru.pop(), Some(("a", "1")));
assert_eq!(lru.pop(), Some(("c", "3")));
assert_eq!(lru.pop(), Some(("b", "2")));
assert_eq!(lru.pop(), None);

NOTES:

• Cloning preserves LRU order.
• If the atomic crate feature is enabled, the cache is thread-safe if K and V are Send/Sync.

Implementations

impl<K, V> LRUCache<K, V>

pub fn unbounded() -> Self

Creates a new unbounded LRU cache.

This cache has no limit on the number of entries it can hold, so entries must be manually removed via pop, or you can use set_max_capacity to set a limit.

pub fn new(max_capacity: usize) -> Self

Creates a new LRU cache with a maximum capacity, after which old entries will be evicted to make room for new ones.

This does not preallocate any memory, only sets an upper limit.

impl<K, V> LRUCache<K, V>

where K: Ord + 'static,

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

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

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

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

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

Returns a reference to the value corresponding to the key, and bumps the key to the front of the LRU list.

pub fn smart_get<'a, Q>(&'a mut self, key: &Q) -> Option<SmartEntry<'a, K, V>>

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

Returns a smart reference to the value corresponding to the key, allowing for reading and updating the LRU order at the same time, with or without updating the LRU order.

This does not immediately update the LRU order; only when the value is accessed via SmartEntry::get or SmartEntry::deref_mut.

Immutable access via SmartEntry::peek or SmartEntry::deref does not update the LRU order.

pub fn peek_range<'a, MIN, MAX>( &'a self, min: &MIN, max: &MAX, ) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)>

where K: Borrow<MIN> + Borrow<MAX>, MIN: Ord + ?Sized, MAX: Ord + ?Sized,

Returns an iterator over the key-value pairs in the cache described by the range, without updating the LRU order. The order of iteration is dependent on the order of the keys in the tree via Ord.

The range follows [min, max), where min is inclusive and max is exclusive.

pub fn range<'a, MIN, MAX>( &'a mut self, min: &MIN, max: &MAX, ) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)>

where K: Borrow<MIN> + Borrow<MAX>, MIN: Ord + ?Sized, MAX: Ord + ?Sized,

Returns an iterator over the key-value pairs in the cache described by the range, and updates the LRU order as they are yielded. The order of iteration is dependent on the order of the keys in the tree via Ord.

The range follows [min, max), where min is inclusive and max is exclusive.

pub fn smart_range<'a, MIN, MAX>( &'a mut self, min: &MIN, max: &MAX, ) -> impl DoubleEndedIterator<Item = SmartEntry<'a, K, V>>

where K: Borrow<MIN> + Borrow<MAX>, MIN: Ord + ?Sized, MAX: Ord + ?Sized,

Returns an iterator over the key-value pairs in the cache described by the range, which allows for reading and updating the LRU order at the same time, only bumping the LRU order when the value is accessed mutably via either SmartEntry::get or SmartEntry::deref_mut.

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

Inserts a key-value pair into the cache, replacing the existing value if the key was already present, and then returning it. In both cases, the entry is moved to the front of the LRU list.

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

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

Removes the value corresponding to the key from the cache, and returning it if it was present. This has no effect on the order of other entries in the LRU list.

pub fn insert_or_get(&mut self, key: K, value: V) -> InsertOrGetResult<'_, K, V>

Inserts a key-value pair into the cache only if it wasn’t already present, otherwise update the LRU order for this element and return a reference to the value.

The returned value contains a mutable reference to the value, and if the key already existed, it also contains the key and value that were passed in.

impl<K, V> LRUCache<K, V>

pub fn set_max_capacity(&mut self, max_capacity: usize)

Sets the maximum capacity of the cache.

This does not remove any entries, but will cause the cache to evict entries when inserting new ones if the length exceeds the new capacity.

Use shrink to manually trigger removal of entries to meet the new capacity.

pub fn clear(&mut self)

Clears the cache, removing all key-value pairs.

pub fn shrink(&mut self)

Removes the oldest entries from the cache until the length is less than or equal to the maximum capacity.

pub fn shrink_by(&mut self, amount: usize)

Removes up to amount of the oldest entries from the cache.

pub fn shrink_with<F>(&mut self, cb: F)

where F: FnMut(K, V),

Removes the oldest entries from the cache until the length is less than or equal to the maximum capacity, and calls the provided closure with the removed key-value pairs.

Example

let mut lru: LRUCache<&'static str, &'static str> = LRUCache::default();

lru.insert("a", "1");
lru.insert("b", "2");
lru.insert("c", "3");

lru.set_max_capacity(1);

let mut removed = Vec::new();

lru.shrink_with(|key, value| {
   removed.push((key, value));
});

assert_eq!(removed, vec![("a", "1"), ("b", "2")]);

pub fn shrink_by_with<F>(&mut self, amount: usize, cb: F)

where F: FnMut(K, V),

Removes up to amount of the oldest entries from the cache, and calls the provided closure with the removed key-value pairs.

pub const fn len(&self) -> usize

Returns the number of key-value pairs in the cache.

pub fn is_empty(&self) -> bool

Returns true if the cache is empty.

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

Removes and returns the least recently used key-value pair.

This is an O(1) operation.

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

Returns an iterator over immutable key-value pairs in the cache, in order of most recently used to least recently used.

NOTE: This does not update the LRU order.

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

Returns an iterator over immutable key-value pairs in the cache, in order of key Ord order.

NOTE: This does not update the LRU order.

pub fn smart_iter( &mut self, ) -> impl DoubleEndedIterator<Item = SmartEntry<'_, K, V>>

Returns an iterator over mutable key-value pairs in the cache, in the order determined by the Ord implementation of the keys.

Trait Implementations

impl<K, V> Clone for LRUCache<K, V>

where K: Clone + Ord + 'static, V: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V> Default for LRUCache<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Drop for LRUCache<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V> Extend<(K, V)> for LRUCache<K, V>

where K: Ord + 'static,

fn extend<T>(&mut self, iter: T)

where T: IntoIterator<Item = (K, V)>,

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> FromIterator<(K, V)> for LRUCache<K, V>

where K: Ord + 'static,

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

where T: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<K, V> IntoIterator for LRUCache<K, V>

where K: Ord + 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.