Struct LfuCache 

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

Available on crate feature std only.

A bounded, thread-safe LFU cache.

Each entry carries a counter that is incremented on every get or insert of an already-present key. On overflow, the entry with the lowest counter is evicted; ties are broken in favour of evicting the least-recently-accessed entry.

contains_key is a query and does not increment the counter or touch access order.

Implementation

Sharded into up to 16 independent stores keyed by hash of K. Each shard pairs a HashMap<K, Entry<V>> for value lookup with a BTreeMap<(count, age), K> ordered priority index for O(log n) eviction.

Eviction is per-shard approximate LFU — the entry evicted on overflow is the lowest-counter entry in the affected shard, not necessarily the lowest-counter entry globally. Tiny caches (< 32 entries) use a single shard and retain strict global semantics.

Example

use cache_mod::{Cache, LfuCache};

let cache: LfuCache<&'static str, u32> = LfuCache::new(2).expect("capacity > 0");

cache.insert("a", 1);
cache.insert("b", 2);

assert_eq!(cache.get(&"a"), Some(1));
assert_eq!(cache.get(&"a"), Some(1));

cache.insert("c", 3);
assert_eq!(cache.get(&"b"), None);
assert_eq!(cache.get(&"a"), Some(1));
assert_eq!(cache.get(&"c"), Some(3));

Implementations

impl<K, V> LfuCache<K, V>

where K: Eq + Hash + Clone, V: Clone,

pub fn new(capacity: usize) -> Result<Self, CacheError>

Creates a cache with the given capacity.

Returns CacheError::InvalidCapacity if capacity == 0.

Example

use cache_mod::LfuCache;

let cache: LfuCache<String, u32> = LfuCache::new(128).expect("capacity > 0");

pub fn with_capacity(capacity: NonZeroUsize) -> Self

Creates a cache with the given non-zero capacity. Infallible.

Example

use std::num::NonZeroUsize;
use cache_mod::LfuCache;

let cap = NonZeroUsize::new(64).expect("64 != 0");
let cache: LfuCache<String, u32> = LfuCache::with_capacity(cap);

Trait Implementations

impl<K, V> Cache<K, V> for LfuCache<K, V>

where K: Eq + Hash + Clone, V: Clone,

fn get(&self, key: &K) -> Option<V>

Returns the value associated with key, if any, and counts as an access for the purposes of the eviction policy.

fn insert(&self, key: K, value: V) -> Option<V>

Inserts value under key. Returns the previously-stored value if key was already present.

fn remove(&self, key: &K) -> Option<V>

Removes the entry for key and returns the value if present.

fn contains_key(&self, key: &K) -> bool

Returns true if the cache currently holds an entry for key.

fn len(&self) -> usize

Number of entries currently stored.

fn clear(&self)

Removes every entry. Capacity is preserved.

fn capacity(&self) -> usize

Configured capacity bound.

fn is_empty(&self) -> bool

Returns true when the cache holds no entries.