Struct clru::CLruCache

pub struct CLruCache<K, V, S = RandomState, W: WeightScale<K, V> = ZeroWeightScale> { /* private fields */ }

A weighted LRU cache with mostly¹ constant time operations.

Each key-value pair in the cache can have a weight that is retrieved using the provided WeightScale implementation. The default scale is ZeroWeightScale and always return 0. The number of elements that can be stored in the cache is conditioned by the sum of CLruCache::len and CLruCache::weight:

CLruCache::len + CLruCache::weight <= CLruCache::capacity

Using the default ZeroWeightScale scale unlocks some useful APIs that can currently only be implemented for this scale. The most interesting ones are probably:

• CLruCache::put
• CLruCache::put_or_modify
• CLruCache::try_put_or_modify

But more generally, using ZeroWeightScale unlocks all methods that return a mutable reference to the value of an element. This is because modifying the value of an element can lead to a modification of its weight and therefore would put the cache into an incoherent state. For the same reason, it is a logic error for a value to change weight while being stored in the cache.

The cache requires the keys to be clonable because it will store 2 instances of each key in different internal data structures. If cloning a key can be expensive, you might want to consider using an Rc or an Arc.

Note 1: See CLruCache::put_with_weight

Implementations

impl<K: Eq + Hash, V> CLruCache<K, V>

pub fn new(capacity: NonZeroUsize) -> Self

Creates a new LRU cache that holds at most capacity elements.

pub fn with_memory(capacity: NonZeroUsize, reserve: usize) -> Self

Creates a new LRU cache that holds at most capacity elements and pre-allocates memory in order to hold at least reserve elements without reallocating.

impl<K: Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S>

pub fn with_hasher( capacity: NonZeroUsize, hash_builder: S ) -> CLruCache<K, V, S>

Creates a new LRU cache that holds at most capacity elements and uses the provided hash builder to hash keys.

impl<K: Eq + Hash, V, W: WeightScale<K, V>> CLruCache<K, V, RandomState, W>

pub fn with_scale( capacity: NonZeroUsize, scale: W ) -> CLruCache<K, V, RandomState, W>

Creates a new LRU cache that holds at most capacity elements and uses the provided scale to retrieve value’s weight.

impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> CLruCache<K, V, S, W>

pub fn with_config(config: CLruCacheConfig<K, V, S, W>) -> Self

Creates a new LRU cache using the provided configuration.

pub fn len(&self) -> usize

Returns the number of key-value pairs that are currently in the cache.

pub fn capacity(&self) -> usize

Returns the capacity of the cache. It serves as a limit for

• the number of elements that the cache can hold.
• the total weight of the elements in the cache.

pub fn weight(&self) -> usize

Returns the total weight of the elements in the cache.

pub fn is_empty(&self) -> bool

Returns a bool indicating whether the cache is empty or not.

pub fn is_full(&self) -> bool

Returns a bool indicating whether the cache is full or not.

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

Returns the value corresponding to the most recently used item or None if the cache is empty. Like peek, front does not update the LRU list so the item’s position will be unchanged.

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

Returns the value corresponding to the least recently used item or None if the cache is empty. Like peek, back does not update the LRU list so the item’s position will be unchanged.

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

Puts a key-value pair into cache taking it’s weight into account. If the weight of the new element is greater than what the cache can hold, it returns the provided key-value pair as an error. Otherwise, it removes enough elements for the new element to be inserted, thus making it a non constant time operation. If the key already exists in the cache, then it updates the key’s value and returns the old value. Otherwise, None is returned.

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

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

Returns a reference to the value of the key in the cache or None if it is not present in the cache. Moves the key to the head of the LRU list if it exists.

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

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

Removes and returns the value corresponding to the key from the cache or None if it does not exist.

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

Removes and returns the key and value corresponding to the most recently used item or None if the cache is empty.

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

Removes and returns the key and value corresponding to the least recently used item or None if the cache is empty.

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

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

Returns a reference to the value corresponding to the key in the cache or None if it is not present in the cache. Unlike get, peek does not update the LRU list so the key’s position will be unchanged.

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

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

Returns a bool indicating whether the given key is in the cache. Like peek, contains does not update the LRU list so the key’s position will be unchanged.

pub fn clear(&mut self)

Clears the contents of the cache.

pub fn resize(&mut self, capacity: NonZeroUsize)

Resizes the cache. If the new capacity is smaller than the size of the current cache any entries past the new capacity are discarded.

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &V) -> bool,

Retains only the elements specified by the predicate. In other words, remove all pairs (k, v) such that f(&k, &v) returns false.

impl<K, V, S, W: WeightScale<K, V>> CLruCache<K, V, S, W>

pub fn iter(&self) -> CLruCacheIter<'_, K, V>

Returns an iterator visiting all entries in order. The iterator element type is (&'a K, &'a V).

impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S>

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

Puts a key-value pair into cache. If the key already exists in the cache, then it updates the key’s value and returns the old value. Otherwise, None is returned.

pub fn put_or_modify<T, P: FnMut(&K, T) -> V, M: FnMut(&K, &mut V, T)>( &mut self, key: K, put_op: P, modify_op: M, data: T ) -> &mut V

Puts a new key-value pair or modify an already existing value. If the key already exists in the cache, then modify_op supplied function is called. Otherwise, put_op supplied function is called. Returns a mutable reference to the value.

The additional data argument can be used to pass extra information to the supplied functions. This can useful when both functions need to access the same variable.

pub fn try_put_or_modify<T, E, P: FnMut(&K, T) -> Result<V, E>, M: FnMut(&K, &mut V, T) -> Result<(), E>>( &mut self, key: K, put_op: P, modify_op: M, data: T ) -> Result<&mut V, E>

Puts a new key-value pair or modify an already existing value. If the key already exists in the cache, then modify_op supplied function is called. Otherwise, put_op supplied function is called. Returns a mutable reference to the value or an error.

The additional data argument can be used to pass extra information to the supplied functions. This can useful when both functions need to access the same variable.

This is the fallible version of CLruCache::put_or_modify.

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

Returns the value corresponding to the most recently used item or None if the cache is empty. Like peek, font does not update the LRU list so the item’s position will be unchanged.

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

Returns the value corresponding to the least recently used item or None if the cache is empty. Like peek, back does not update the LRU list so the item’s position will be unchanged.

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

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

Returns a mutable reference to the value of the key in the cache or None if it is not present in the cache. Moves the key to the head of the LRU list if it exists.

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

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

Returns a mutable reference to the value corresponding to the key in the cache or None if it is not present in the cache. Unlike get_mut, peek_mut does not update the LRU list so the key’s position will be unchanged.

pub fn retain_mut<F>(&mut self, f: F)

where F: FnMut(&K, &mut V) -> bool,

Retains only the elements specified by the predicate. In other words, remove all pairs (k, v) such that f(&k, &mut v) returns false.

impl<K, V, S> CLruCache<K, V, S>

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

Returns an iterator visiting all entries in order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Trait Implementations

impl<K: Debug, V: Debug, S: Debug, W: Debug + WeightScale<K, V>> Debug for CLruCache<K, V, S, W>

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

Formats the value using the given formatter.

impl<K: Clone + Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for CLruCache<K, V, S>

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: Clone + Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for CLruCache<K, V, S>

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

Creates a value from an iterator.

impl<'a, K, V, S, W: WeightScale<K, V>> IntoIterator for &'a CLruCache<K, V, S, W>

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

The type of the elements being iterated over.

type IntoIter = CLruCacheIter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> CLruCacheIter<'a, K, V>

Creates an iterator from a value.

impl<'a, K, V, S> IntoIterator for &'a mut CLruCache<K, V, S>

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

The type of the elements being iterated over.

type IntoIter = CLruCacheIterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> CLruCacheIterMut<'a, K, V>

Creates an iterator from a value.

impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> IntoIterator for CLruCache<K, V, S, W>

fn into_iter(self) -> CLruCacheIntoIter<K, V, S, W>

Consumes the cache into an iterator yielding elements by value.

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = CLruCacheIntoIter<K, V, S, W>

Which kind of iterator are we turning this into?