Struct LruCache

pub struct LruCache<K, V, S = DefaultHashBuilder> { /* private fields */ }

An implementation of a Least Recently Used (LRU) cache.

The cache has a fixed capacity and supports O(1) operations for inserting, retrieving, and updating entries. When the cache reaches capacity, the least recently used entry will be evicted to make room for new entries.

Examples

use cache_rs::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());

// Add items to the cache
cache.put("apple", 1);
cache.put("banana", 2);

// Accessing items updates their recency
assert_eq!(cache.get(&"apple"), Some(&1));

// Adding beyond capacity evicts the least recently used item
// In this case "banana" is evicted because "apple" was just accessed
cache.put("cherry", 3);
assert_eq!(cache.get(&"banana"), None);
assert_eq!(cache.get(&"apple"), Some(&1));
assert_eq!(cache.get(&"cherry"), Some(&3));

Memory Usage

The memory usage of this cache is approximately:

• 16 bytes for the cache struct itself
• (32 + size_of(K) + size_of(V)) bytes per entry
• Plus HashMap overhead

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());

// Insert some items
cache.put("apple", 1);
cache.put("banana", 2);

// Most recently used is banana, then apple
assert_eq!(cache.get(&"apple"), Some(&1));
// Now most recently used is apple, then banana

// Add a new item, evicting the least recently used (banana)
cache.put("cherry", 3);

// Banana was evicted
assert_eq!(cache.get(&"banana"), None);
assert_eq!(cache.get(&"apple"), Some(&1));
assert_eq!(cache.get(&"cherry"), Some(&3));

Implementations

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

pub fn with_hasher(cap: NonZeroUsize, hash_builder: S) -> Self

Creates a new LRU cache that holds at most cap items using the specified hash builder.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;
use std::collections::hash_map::RandomState;

let cache: LruCache<&str, u32, _> = LruCache::with_hasher(
    NonZeroUsize::new(10).unwrap(),
    RandomState::new()
);

pub fn with_hasher_and_size( cap: NonZeroUsize, hash_builder: S, max_size_bytes: u64, ) -> Self

Creates a new LRU cache with specified capacity, hash builder, and size limit in bytes.

pub fn cap(&self) -> NonZeroUsize

Returns the maximum number of key-value pairs the cache can hold.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let cache: LruCache<&str, u32> = LruCache::new(NonZeroUsize::new(10).unwrap());
assert_eq!(cache.cap().get(), 10);

pub fn len(&self) -> usize

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

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
assert_eq!(cache.len(), 0);

cache.put("apple", 1);
assert_eq!(cache.len(), 1);

cache.put("banana", 2);
assert_eq!(cache.len(), 2);

pub fn is_empty(&self) -> bool

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

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
assert!(cache.is_empty());

cache.put("apple", 1);
assert!(!cache.is_empty());

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

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

Returns a reference to the value corresponding to the key.

The key may be any borrowed form of the cache’s key type, but Hash and Eq on the borrowed form must match those for the key type.

If a value is returned, that key-value pair becomes the most recently used pair in the cache.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple", 1);
cache.put("banana", 2);

assert_eq!(cache.get(&"apple"), Some(&1));
assert_eq!(cache.get(&"banana"), Some(&2));
assert_eq!(cache.get(&"cherry"), None);

pub fn record_miss(&mut self, object_size: u64)

Records a cache miss for metrics tracking (to be called by simulation system)

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

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

Returns a mutable reference to the value corresponding to the key.

The key may be any borrowed form of the cache’s key type, but Hash and Eq on the borrowed form must match those for the key type.

If a value is returned, that key-value pair becomes the most recently used pair in the cache.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple", 1);

if let Some(v) = cache.get_mut(&"apple") {
    *v = 4;
}

assert_eq!(cache.get(&"apple"), Some(&4));

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

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

where V: Clone,

Inserts a key-value pair into the cache.

If the cache already contained this key, the old value is replaced and returned. Otherwise, if the cache is at capacity, the least recently used key-value pair will be evicted and returned.

The inserted key-value pair becomes the most recently used pair in the cache.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());

assert_eq!(cache.put("apple", 1), None); // No previous value
assert_eq!(cache.put("apple", 4).unwrap().1, 1); // Replaced existing value

// At capacity, adding new item evicts least recently used
cache.put("banana", 2);
assert_eq!(cache.put("cherry", 3).unwrap().1, 4); // Evicted "apple"
assert_eq!(cache.get(&"apple"), None); // "apple" was evicted

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

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

Removes a key from the cache, returning the value at the key if the key was previously in the cache.

The key may be any borrowed form of the cache’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple", 1);

assert_eq!(cache.remove(&"apple"), Some(1));
assert_eq!(cache.remove(&"apple"), None);

pub fn clear(&mut self)

Clears the cache, removing all key-value pairs.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("apple", 1);
cache.put("banana", 2);

assert!(!cache.is_empty());
cache.clear();
assert!(cache.is_empty());

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

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

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;
use std::prelude::v1::*;

let mut cache = LruCache::new(NonZeroUsize::new(3).unwrap());
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

// Access "a" to move it to the front
assert_eq!(cache.get(&"a"), Some(&1));

let items: Vec<_> = cache.iter().collect();
assert_eq!(items, [(&"b", &2), (&"c", &3), (&"a", &1)]);

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

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

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;
use std::prelude::v1::*;

let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
cache.put("a", 1);
cache.put("b", 2);

for (_, v) in cache.iter_mut() {
    *v += 10;
}

assert_eq!(cache.get(&"a"), Some(&11));
assert_eq!(cache.get(&"b"), Some(&12));

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

where V: Clone,

pub fn new(cap: NonZeroUsize) -> LruCache<K, V, DefaultHashBuilder>

Creates a new LRU cache that holds at most cap items.

Examples

use cache_rs::lru::LruCache;
use core::num::NonZeroUsize;

let cache: LruCache<&str, u32> = LruCache::new(NonZeroUsize::new(10).unwrap());

Trait Implementations

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

fn metrics(&self) -> BTreeMap<String, f64>

Returns all metrics as key-value pairs in deterministic order

fn algorithm_name(&self) -> &'static str

Algorithm name for identification

impl<K: Debug, V: Debug, S: Debug> Debug for LruCache<K, V, S>

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

Formats the value using the given formatter.