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, per the Cache contract.

This is the 0.3.0 reference implementation: correct and &self-everywhere, Mutex-guarded. Eviction is O(n) — a scan for the minimum on overflow. An O(1) bucket-based implementation lands in 0.5.0 without changing this public surface.

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);

// Bump "a"'s frequency above "b"'s.
assert_eq!(cache.get(&"a"), Some(1));
assert_eq!(cache.get(&"a"), Some(1));

// Inserting "c" should evict "b" (lowest counter).
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 maximum number of entries.

fn is_empty(&self) -> bool

Returns true when the cache holds no entries.