Struct LfuCache

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

An implementation of a Least Frequently Used (LFU) cache.

The cache tracks the frequency of access for each item and evicts the least frequently used items when the cache reaches capacity. In case of a tie in frequency, the least recently used item among those with the same frequency is evicted.

Examples

use cache_rs::lfu::LfuCache;
use core::num::NonZeroUsize;

// Create an LFU cache with capacity 3
let mut cache = LfuCache::new(NonZeroUsize::new(3).unwrap());

// Add some items
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

// Access "a" multiple times to increase its frequency
assert_eq!(cache.get(&"a"), Some(&1));
assert_eq!(cache.get(&"a"), Some(&1));

// Add a new item, which will evict the least frequently used item
cache.put("d", 4);
assert_eq!(cache.get(&"b"), None); // "b" was evicted as it had frequency 0

Implementations

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

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

Creates a new LFU cache with the specified capacity and hash builder.

Examples

use cache_rs::lfu::LfuCache;
use core::num::NonZeroUsize;
use std::collections::hash_map::RandomState;

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

pub fn cap(&self) -> NonZeroUsize

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

pub fn len(&self) -> usize

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

pub fn is_empty(&self) -> bool

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

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

where K: Borrow<Q> + Clone, 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.

Accessing an item increases its frequency count.

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

where K: Borrow<Q> + Clone, 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.

Accessing an item increases its frequency count.

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

where K: 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 frequently used item is evicted. In case of a tie in frequency, the least recently used item among those with the same frequency is evicted.

New items are inserted with a frequency of 1.

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.

pub fn clear(&mut self)

Clears the cache, removing all key-value pairs.

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

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

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

where V: Clone,

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

Creates a new LFU cache with the specified capacity.

Examples

use cache_rs::lfu::LfuCache;
use core::num::NonZeroUsize;

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

Trait Implementations

impl<K: Hash + Eq, V, S: BuildHasher> CacheMetrics for LfuCache<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 LfuCache<K, V, S>

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

Formats the value using the given formatter.