Struct uluru::LRUCache

pub struct LRUCache<T, const N: usize> {
    pub(crate) entries: ArrayVec<Entry<T>, N>,
    pub(crate) head: u16,
    pub(crate) tail: u16,
}

A LRU cache using a statically-sized array for storage.

LRUCache uses a fixed-capacity array for storage. It provides O(1) insertion, and O(n) lookup.

All items are stored inline within the LRUCache, so it does not impose any heap allocation or indirection. 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 uluru::LRUCache;

struct MyValue {
    id: u32,
    name: &'static str,
}

// A cache with a capacity of three.
type MyCache = LRUCache<MyValue, 3>;

// Create an empty cache, then insert some items.
let mut cache = MyCache::default();
cache.insert(MyValue { id: 1, name: "Mercury" });
cache.insert(MyValue { id: 2, name: "Venus" });
cache.insert(MyValue { id: 3, name: "Earth" });

// Use the `find` method to retrieve an item from the cache.
// This also "touches" the item, marking it most-recently-used.
let item = cache.find(|x| x.id == 1);
assert_eq!(item.unwrap().name, "Mercury");

// If the cache is full, inserting a new item evicts the least-recently-used item:
cache.insert(MyValue { id: 4, name: "Mars" });
assert!(cache.find(|x| x.id == 2).is_none());

Fields

entries: ArrayVec<Entry<T>, N>

The most-recently-used entry is at index head. The entries form a linked list, linked to each other by indices within the entries array. After an entry is added to the array, its index never changes, so these links are never invalidated.

head: u16

Index of the first entry. If the cache is empty, ignore this field.

tail: u16

Index of the last entry. If the cache is empty, ignore this field.

Implementations

impl<T, const N: usize> LRUCache<T, N>

pub const fn new() -> Self

Create an empty cache.

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

Insert a given key in the cache.

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

pub fn find<F>(&mut self, pred: F) -> Option<&mut T>

where F: FnMut(&T) -> bool,

Returns the first item in the cache that matches the given predicate. Touches the result (makes it most-recently-used) on a hit.

pub fn lookup<F, R>(&mut self, pred: F) -> Option<R>

where F: FnMut(&mut T) -> Option<R>,

Performs a lookup on the cache with the given test routine. Touches the result on a hit.

pub fn len(&self) -> usize

Returns the number of elements in the cache.

pub fn is_empty(&self) -> bool

Returns true if the cache is empty.

pub fn clear(&mut self)

Evict all elements from the cache.

pub fn front(&self) -> Option<&T>

Returns the front entry in the list (most recently used).

pub fn front_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the front entry in the list (most recently used).

pub fn get(&self, index: usize) -> Option<&T>

Returns the n-th entry in the list (most recently used).

pub fn touch<F>(&mut self, pred: F) -> bool

where F: FnMut(&T) -> bool,

Touches the first item in the cache that matches the given predicate (marks it as most-recently-used). Returns true on a hit, false if no matches.

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

Iterate over the contents of this cache in order from most-recently-used to least-recently-used.

pub(crate) fn iter_mut(&mut self) -> IterMut<'_, T, N>

Iterate mutably over the contents of this cache in order from most-recently-used to least-recently-used.

pub(crate) fn touch_index(&mut self, i: u16)

Touch a given entry, putting it first in the list.

pub(crate) fn entry(&mut self, i: u16) -> &mut Entry<T>

pub(crate) fn remove(&mut self, i: u16)

Remove an entry from the linked list.

Note: This only unlinks the entry from the list; it does not remove it from the array.

pub(crate) fn push_front(&mut self, i: u16)

Insert a new entry at the head of the list.

pub(crate) fn pop_back(&mut self) -> u16

Remove the last entry from the linked list. Returns the index of the removed entry.

Note: This only unlinks the entry from the list; it does not remove it from the array.

Trait Implementations

impl<T: Clone, const N: usize> Clone for LRUCache<T, N>

fn clone(&self) -> LRUCache<T, N>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, const N: usize> Debug for LRUCache<T, N>

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

Formats the value using the given formatter.

impl<T, const N: usize> Default for LRUCache<T, N>

fn default() -> Self

Returns the “default value” for a type.