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.

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

• The cache is not thread-safe, and requires external synchronization.
• Cloning the cache will preserve the LRU order.

Implementations

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

pub fn new() -> 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_with_max_capacity(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 get<'a, 'b, Q>(&'a mut self, key: &Q) -> Option<&'a V>

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

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

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

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

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

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

Inserts a key-value pair into the cache, returning the old value if the key was already present.

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.

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.

This is O(2n) where n is the number of key-value pairs in the cache, as both the LRU list and key-value tree require iteration to be cleared.

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_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 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_lru(&self) -> impl DoubleEndedIterator<Item = (&K, &V)>

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

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

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

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> 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.