Struct LfuCache

Source

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

Expand description

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

// Create an LFU cache with capacity 3
let config = LfuCacheConfig {
    capacity: NonZeroUsize::new(3).unwrap(),
    max_size: u64::MAX,
};
let mut cache = LfuCache::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 a new item, which will evict the least frequently used item
cache.put("d", 4, 1);
assert_eq!(cache.get(&"b"), None); // "b" was evicted as it had frequency 0

Implementations§

Source §

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

Source

pub fn cap(&self) -> NonZeroUsize

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

Source

pub fn len(&self) -> usize

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

Source

pub fn is_empty(&self) -> bool

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

Source

pub fn current_size(&self) -> u64

Returns the current total size of cached content.

Source

pub fn max_size(&self) -> u64

Returns the maximum content size the cache can hold.

Source

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.

Source

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.

Source

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 least frequently used item is evicted. Ties are broken by evicting the least recently used item among those with the same frequency.

New items are inserted with a frequency of 1.

§Arguments

key - The key to insert
value - The value to cache
size - Size of this entry for capacity tracking. 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)

Source

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.

Source

pub fn clear(&mut self)

Clears the cache, removing all key-value pairs.

Source

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

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

Source

pub fn contains<Q>(&self, key: &Q) -> bool
where K: Borrow<Q>, Q: ?Sized + Hash + Eq,

Check if key exists without updating its frequency.

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

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

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

Source

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 frequency or access metadata.

Unlike get(), this does NOT increment the entry’s frequency or change its position in any frequency list.

§Example

use cache_rs::LfuCache;
use cache_rs::config::LfuCacheConfig;
use core::num::NonZeroUsize;

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

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

Source §

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

Source

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

Creates a new LFU cache from a configuration.

This is the recommended way to create an LFU cache. All configuration is specified through the LfuCacheConfig struct.

§Arguments

config - Configuration specifying capacity and optional size limit
hasher - Optional custom hash builder (uses default if None)

§Example

use cache_rs::LfuCache;
use cache_rs::config::LfuCacheConfig;
use core::num::NonZeroUsize;

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

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