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 cache_rs::config::LfudaCacheConfig;
use core::num::NonZeroUsize;

// Create an LFUDA cache with capacity 3
let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(3).unwrap(),
    initial_age: 0,
    max_size: u64::MAX,
};
let mut cache = LfudaCache::init(config, None);

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

// 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, 1); // This will evict an item and increase global age
cache.put("e", 5, 1); // New items benefit from the increased age

Implementations

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

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 current_size(&self) -> u64

Returns the current total size of cached content.

pub fn max_size(&self) -> u64

Returns the maximum content size the cache can hold.

pub fn global_age(&self) -> u64

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, size: u64) -> Option<Vec<(K, V)>>

where K: Clone,

Inserts a key-value pair into the cache.

If the key already exists, it is replaced. If at capacity, the item with the lowest effective priority is evicted and 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.

Arguments

• key - The key to insert
• value - The value to insert
• size - Optional size in bytes for size-aware caching. Use SIZE_UNIT (1) for count-based caching.

Returns

• Some(vec) containing evicted entries (not replaced entries)
• None if no entries were evicted (zero allocation)

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.

pub fn contains<Q>(&self, key: &Q) -> bool

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

Check if key exists without updating its priority or access metadata.

Unlike get(), this method does NOT update the entry’s frequency or access metadata. Useful for existence checks without affecting cache eviction order.

Example

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

let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(2).unwrap(),
    initial_age: 0,
    max_size: u64::MAX,
};
let mut cache = LfudaCache::init(config, None);
cache.put("a", 1, 1);
cache.put("b", 2, 1);

// contains() does NOT update priority
assert!(cache.contains(&"a"));

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

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

Returns a reference to the value without updating priority or access metadata.

Unlike get(), this does NOT increment the entry’s frequency, change its priority, or move it between priority lists.

Example

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

let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(3).unwrap(),
    initial_age: 0,
    max_size: u64::MAX,
};
let mut cache = LfudaCache::init(config, None);
cache.put("a", 1, 1);

// peek does not change priority
assert_eq!(cache.peek(&"a"), Some(&1));
assert_eq!(cache.peek(&"missing"), None);

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

where V: Clone,

pub fn init( config: LfudaCacheConfig, hasher: Option<DefaultHashBuilder>, ) -> LfudaCache<K, V, DefaultHashBuilder>

Creates a new LFUDA cache from a configuration.

This is the recommended way to create an LFUDA cache. All configuration is specified through the LfudaCacheConfig struct, which uses a builder pattern for optional parameters.

Arguments

• config - Configuration specifying capacity and optional size limit/initial age

Example

use cache_rs::LfudaCache;
use cache_rs::config::LfudaCacheConfig;
use core::num::NonZeroUsize;

// Simple capacity-only cache
let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(100).unwrap(),
    initial_age: 0,
    max_size: u64::MAX,
};
let mut cache: LfudaCache<&str, i32> = LfudaCache::init(config, None);
cache.put("key", 42, 1);

// Cache with size limit
let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    initial_age: 100,
    max_size: 10 * 1024 * 1024,  // 10MB
};
let cache: LfudaCache<String, Vec<u8>> = LfudaCache::init(config, None);

Trait Implementations

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

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

Formats the value using the given formatter.