pub struct CLruCache<K, V, S = RandomState, W: WeightScale<K, V> = ZeroWeightScale> { /* private fields */ }
Expand description
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:
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§
source§impl<K: Eq + Hash, V> CLruCache<K, V>
impl<K: Eq + Hash, V> CLruCache<K, V>
sourcepub fn new(capacity: NonZeroUsize) -> Self
pub fn new(capacity: NonZeroUsize) -> Self
Creates a new LRU cache that holds at most capacity
elements.
sourcepub fn with_memory(capacity: NonZeroUsize, reserve: usize) -> Self
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.
source§impl<K: Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S>
impl<K: Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S>
sourcepub fn with_hasher(capacity: NonZeroUsize, hash_builder: S) -> 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.
source§impl<K: Eq + Hash, V, W: WeightScale<K, V>> CLruCache<K, V, RandomState, W>
impl<K: Eq + Hash, V, W: WeightScale<K, V>> CLruCache<K, V, RandomState, W>
sourcepub fn with_scale(
capacity: NonZeroUsize,
scale: W
) -> 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.
source§impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> CLruCache<K, V, S, W>
impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> CLruCache<K, V, S, W>
sourcepub fn with_config(config: CLruCacheConfig<K, V, S, W>) -> Self
pub fn with_config(config: CLruCacheConfig<K, V, S, W>) -> Self
Creates a new LRU cache using the provided configuration.
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of key-value pairs that are currently in the cache.
sourcepub fn capacity(&self) -> usize
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.
sourcepub fn front(&self) -> Option<(&K, &V)>
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.
sourcepub fn back(&self) -> Option<(&K, &V)>
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.
sourcepub fn put_with_weight(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)>
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.
sourcepub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Hash + Eq,
pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Hash + Eq,
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.
sourcepub fn pop<Q: ?Sized>(&mut self, key: &Q) -> Option<V>where
K: Borrow<Q>,
Q: Hash + Eq,
pub fn pop<Q: ?Sized>(&mut self, key: &Q) -> Option<V>where
K: Borrow<Q>,
Q: Hash + Eq,
Removes and returns the value corresponding to the key from the cache or None
if it does not exist.
sourcepub fn pop_front(&mut self) -> Option<(K, V)>
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.
sourcepub fn pop_back(&mut self) -> Option<(K, V)>
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.
sourcepub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Hash + Eq,
pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Hash + Eq,
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.
sourcepub fn contains<Q: ?Sized>(&mut self, key: &Q) -> boolwhere
K: Borrow<Q>,
Q: Hash + Eq,
pub fn contains<Q: ?Sized>(&mut self, key: &Q) -> boolwhere
K: Borrow<Q>,
Q: Hash + Eq,
Returns a bool indicating whether the given key is in the cache. Does not update the LRU list.
sourcepub fn resize(&mut self, capacity: NonZeroUsize)
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.
source§impl<K, V, S, W: WeightScale<K, V>> CLruCache<K, V, S, W>
impl<K, V, S, W: WeightScale<K, V>> CLruCache<K, V, S, W>
sourcepub fn iter(&self) -> CLruCacheIter<'_, K, V> ⓘ
pub fn iter(&self) -> CLruCacheIter<'_, K, V> ⓘ
Returns an iterator visiting all entries in order.
The iterator element type is (&'a K, &'a V)
.
source§impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S>
impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S>
sourcepub fn put(&mut self, key: K, value: V) -> Option<V>
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.
sourcepub 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
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.
sourcepub 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>
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
.
sourcepub fn front_mut(&mut self) -> Option<(&K, &mut V)>
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.
sourcepub fn back_mut(&mut self) -> Option<(&K, &mut V)>
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.
sourcepub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: Hash + Eq,
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: Hash + Eq,
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.
sourcepub fn peek_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: Hash + Eq,
pub fn peek_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: Hash + Eq,
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.
Trait Implementations§
source§impl<K: Debug, V: Debug, S: Debug, W: Debug + WeightScale<K, V>> Debug for CLruCache<K, V, S, W>
impl<K: Debug, V: Debug, S: Debug, W: Debug + WeightScale<K, V>> Debug for CLruCache<K, V, S, W>
source§impl<K: Clone + Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for CLruCache<K, V, S>
impl<K: Clone + Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for CLruCache<K, V, S>
source§fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)