Struct LfudaCache

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

An implementation of a Least Frequently Used with Dynamic Aging (LFUDA) cache.

LFUDA improves upon LFU by adding an aging mechanism that prevents old frequently-used items from blocking new items indefinitely. Each item’s effective priority is calculated as (access_frequency + age_at_insertion), where age_at_insertion is the global age value when the item was first inserted.

When an item is evicted, the global age is set to the evicted item’s effective priority, ensuring that new items start with a competitive priority.

Examples

use cache_rs::lfuda::LfudaCache;
use core::num::NonZeroUsize;

// Create an LFUDA cache with capacity 3
let mut cache = LfudaCache::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 more items to trigger aging
cache.put("d", 4); // This will evict an item and increase global age
cache.put("e", 5); // New items benefit from the increased age

Implementations

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

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

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

Examples

use cache_rs::lfuda::LfudaCache;
use core::num::NonZeroUsize;
use std::collections::hash_map::RandomState;

let cache: LfudaCache<&str, u32, _> = LfudaCache::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 global_age(&self) -> usize

Returns the current global age value.

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<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 item with the lowest effective priority is evicted. The global age is updated to the evicted item’s effective priority.

New items are inserted with a frequency of 1 and age_at_insertion set to the current global_age.

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. Resets the global age to 0.

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

where V: Clone,

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

Creates a new LFUDA cache with the specified capacity.

Examples

use cache_rs::lfuda::LfudaCache;
use core::num::NonZeroUsize;

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

Trait Implementations

impl<K, V, S> CacheMetrics for LfudaCache<K, V, S>

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

Returns all LFUDA cache metrics as key-value pairs in deterministic order

Returns

A BTreeMap containing all metrics tracked by this LFUDA cache instance

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

Returns the algorithm name for this cache implementation

Returns

“LFUDA” - identifying this as a Least Frequently Used with Dynamic Aging cache

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

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

Formats the value using the given formatter.