Struct LruCache

pub struct LruCache<K: Eq + Hash, V, S: BuildHasher = DefaultHashBuilder, M: Meter<K, V> = Count> { /* private fields */ }

An LRU cache.

Implementations

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

pub fn new(max_items: usize) -> Self

Creates an empty cache that can hold at most max_items items.

Examples

let mut cache: LruCache<i32, &str> = LruCache::new(10);

impl<K: Eq + Hash, V, M: Meter<K, V>> LruCache<K, V, DefaultHashBuilder, M>

pub fn with_meter( max_items: usize, capacity: M::Measure, meter: M, ) -> LruCache<K, V, DefaultHashBuilder, M>

Creates an empty cache that can hold at most capacity as measured by Meter.

You can implement the Meter trait to allow custom metrics.

Examples

/// Measure Vec items by their length
struct VecLen;

impl<K, T> Meter<K, Vec<T>> for VecLen {
    type Measure = usize;
    fn measure<Q: ?Sized>(&self, _: &Q, v: &Vec<T>) -> usize
        where K: Borrow<Q>
    {
        v.len()
    }
}

let mut cache = LruCache::with_meter(100, 5, VecLen);

cache.insert(1, vec![1, 2]);
assert_eq!(cache.size(), 2);

cache.insert(2, vec![3, 4]);
cache.insert(3, vec![5, 6]);
assert_eq!(cache.size(), 4);
assert_eq!(cache.len(), 2);

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

pub fn with_hasher(capacity: usize, hash_builder: S) -> LruCache<K, V, S, Count>

Creates an empty cache that can hold at most capacity items with the given hash builder.

impl<K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> LruCache<K, V, S, M>

pub fn with_meter_and_hasher( max_items: usize, capacity: M::Measure, meter: M, hash_builder: S, ) -> Self

Creates an empty cache that can hold at most capacity as measured by Meter with the given hash builder.

pub fn is_empty(&self) -> bool

Returns true if the cache contains no key-value pairs.

pub fn len(&self) -> usize

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

pub fn max_items(&self) -> usize

pub fn set_max_items(&mut self, max_items: usize)

Sets the max number of items the cache can hold.

Removes least-recently-used key-value pairs if necessary.

Examples

let mut cache = LruCache::new(2);
cache.set_capacity(100);

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

assert_eq!(cache.get(&1), None);
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));

cache.set_max_items(3);
cache.insert(1, "a");
cache.insert(2, "b");

assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));

cache.set_max_items(1);

assert_eq!(cache.get(&1), None);
assert_eq!(cache.get(&2), None);
assert_eq!(cache.get(&3), Some(&"c"));

pub fn size(&self) -> M::Measure

Returns the size in Meter::Measure of all the key-value pairs in the cache.

pub fn capacity(&self) -> M::Measure

Returns the maximum size of the key-value pairs the cache can hold, as measured by the Meter used by the cache.

Examples

let mut cache: LruCache<i32, &str> = LruCache::new(2);
assert_eq!(cache.capacity(), 2);

pub fn set_capacity(&mut self, capacity: M::Measure)

Sets the size of the key-value pairs the cache can hold, as measured by the Meter used by the cache.

Removes least-recently-used key-value pairs if necessary.

Examples

let mut cache = LruCache::new(2);
cache.set_max_items(100);

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

assert_eq!(cache.get(&1), None);
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));

cache.set_capacity(3);
cache.insert(1, "a");
cache.insert(2, "b");

assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));
assert_eq!(cache.get(&3), Some(&"c"));

cache.set_capacity(1);

assert_eq!(cache.get(&1), None);
assert_eq!(cache.get(&2), None);
assert_eq!(cache.get(&3), Some(&"c"));

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

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

Checks if the map contains the given key.

Examples

let mut cache = LruCache::new(1);

cache.insert(1, "a");
assert!(cache.contains_key(&1));

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

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

Returns a reference to the value corresponding to the given key in the cache, if any. Do not put the accessed item to the back.

Examples

let mut cache = LruCache::new(2);

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

assert_eq!(cache.peek(&1), None);
assert_eq!(cache.peek(&2), Some(&"c"));

pub fn peek_mut<'a, Q>( &'a mut self, k: &'a Q, ) -> Option<PeekMut<'a, K, V, S, M>>

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

Returns a mutable reference to the value corresponding to the given key in the cache, if any. Do put the accessed item to the back.

When the mutable reference is dropped, the cache will be evicted by policy if the measure of the updated value changes.

Examples

let mut cache = LruCache::new(2);

cache.insert(1, "a");
cache.insert(2, "b");

{
    let mut a = cache.peek_mut(&1).unwrap();
    *a = "c";
}

assert_eq!(cache.get(&1).unwrap(), &"c");
assert_eq!(cache.get(&2).unwrap(), &"b");

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

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

Returns a reference to the value corresponding to the given key in the cache, if any. And put the accessed item to the back.

Examples

let mut cache = LruCache::new(2);

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

assert_eq!(cache.get(&1), None);
assert_eq!(cache.get(&2), Some(&"c"));

pub fn get_mut<'a, Q>(&'a mut self, k: &'a Q) -> Option<PeekMut<'a, K, V, S, M>>

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

Returns a mutable reference to the value corresponding to the given key in the cache, if any.

Examples

let mut cache = LruCache::new(2);

cache.insert(1, "a");
cache.insert(2, "b");

{
    let mut a = cache.get_mut(&1).unwrap();
    *a = "c";
}

assert_eq!(cache.get(&1).unwrap(), &"c");
assert_eq!(cache.get(&2).unwrap(), &"b");

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

Inserts a key-value pair into the cache and put it to the back. If the key already existed, the old value is returned.

Examples

let mut cache = LruCache::new(2);

cache.insert(1, "a");
cache.insert(2, "b");
assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"b"));

let evicted = cache.insert(2, "c");
assert_eq!(evicted, Some("b"));
assert_eq!(cache.get(&2), Some(&"c"));

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

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

Removes the given key from the cache and returns its corresponding value.

Examples

let mut cache = LruCache::new(2);

cache.insert(2, "a");

assert_eq!(cache.remove(&1), None);
assert_eq!(cache.remove(&2), Some("a"));
assert_eq!(cache.remove(&2), None);
assert_eq!(cache.len(), 0);

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

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

Examples

let mut cache = LruCache::new(2);

cache.insert(1, "a");
cache.insert(2, "b");

assert_eq!(cache.remove_lru(), Some((1, "a")));
assert_eq!(cache.len(), 1);

pub fn clear(&mut self)

Removes all key-value pairs from the cache.

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

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

Accessing the cache through the iterator does not affect the cache’s LRU state.

Examples

let mut cache = LruCache::new(2);

cache.insert(1, 10);
cache.insert(2, 20);
cache.insert(3, 30);

let kvs: Vec<_> = cache.iter().collect();
assert_eq!(kvs, [(&2, &20), (&3, &30)]);

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

Returns an iterator over the cache’s key-value pairs in least- to most-recently-used order, with mutable references to the values.

Accessing the cache through the iterator does not affect the cache’s LRU state. Note that this method is not available for cache objects using Meter implementations. other than Count.

Examples

let mut cache = LruCache::new(2);

cache.insert(1, 10);
cache.insert(2, 20);
cache.insert(3, 30);

let mut n = 2;

for (k, v) in cache.iter_mut() {
    assert_eq!(*k, n);
    assert_eq!(*v, n * 10);
    *v *= 10;
    n += 1;
}

assert_eq!(n, 4);
assert_eq!(cache.get(&2), Some(&200));
assert_eq!(cache.get(&3), Some(&300));

Trait Implementations

impl<K: Clone + Eq + Hash, V: Clone, S: Clone + BuildHasher, M: Clone + Meter<K, V>> Clone for LruCache<K, V, S, M>

where M::Measure: Clone,

fn clone(&self) -> LruCache<K, V, S, M>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug + Eq + Hash, V: Debug, S: BuildHasher, M: Meter<K, V>> Debug for LruCache<K, V, S, M>

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

Formats the value using the given formatter.

impl<K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> Extend<(K, V)> for LruCache<K, V, S, M>

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

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<'a, K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> IntoIterator for &'a LruCache<K, V, S, M>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

impl<'a, K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> IntoIterator for &'a mut LruCache<K, V, S, M>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

impl<K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> IntoIterator for LruCache<K, V, S, M>

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) -> IntoIter<K, V>

Creates an iterator from a value.