Struct elaru::LRUCache

pub struct LRUCache<T> { /* fields omitted */ }

A LRU cache builds on top of the HashMap from standard library.

LRUCache uses std::collections::HashMap for storage. It provides O(1) performance on insert, get, remove_lru and many other APIs.

All entries are linked inlined within the LRUCache without raw pointer manipulation, so it is complete memory safe and doesn't suffer any undefined behavior. A linked list is used to record the cache order, so the items themselves do not need to be moved when the order changes. (This is important for speed if the items are large.)

Example

use elaru::{LRUCache, Entry};

// Create an empty cache, then insert some items.
let mut cache = LRUCache::new(3);
cache.insert(1, "Mercury");
cache.insert(2, "Venus");
cache.insert(3, "Earth");

// Use the `get` method to retrieve the value from the cache with given key.
// This also "touches" the entry, marking it most-recently-used.
let item = cache.get(&1).unwrap();
assert_eq!(item, &"Mercury");

// If the cache is full, inserting a new item evicts the least-recently-used item:
cache.insert(4, "Mars");
assert!(cache.get(&2).is_none());

Implementations

impl<T> LRUCache<T>

pub fn new(capacity: usize) -> Self

Create a new LRU cache that can hold capacity of entries.

pub fn len(&self) -> usize

Returns the number of elements in the cache.

pub fn capacity(&self) -> usize

Returns the capacity of the cache.

pub fn get(&mut self, key: &u16) -> Option<&T>

Returns the entry in the list with given key.

pub fn get_mut(&mut self, key: &u16) -> Option<&mut T>

Returns a mutable reference to the entry in the list with given key.

pub fn insert(&mut self, key: u16, val: T) -> Option<T>

Insert a given key in the cache. Return old value if the key is present.

This item becomes the front (most-recently-used) item in the cache. If the cache is full, the back (least-recently-used) item will be removed.

pub fn remove_lru(&mut self) -> Option<(u16, T)>

Remove an entry from the linked list.

pub fn clear(&mut self)

Clear all elements from the cache.

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

Iterate over the contents of this cache.

Trait Implementations

impl<T: Clone> Clone for LRUCache<T>

pub fn clone(&self) -> LRUCache<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for LRUCache<T>

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

Formats the value using the given formatter.