# cache-mod v0.3.0 — LFU eviction policy

**The second policy lands.** 0.2.0 set the public API surface; 0.3.0 fills it out with the Least-Frequently-Used (LFU) cache — the natural complement to the LRU reference implementation. Existing `0.2.0` call-sites compile and behave identically; LFU is purely additive.

## What is cache-mod?

High-performance in-process caching for Rust with multiple eviction policies (LRU, LFU now; TinyLFU, TTL, size-bounded coming). Async-safe (`&self` everywhere, `Send + Sync` cache instances), lock-minimized internals. Typed key-value API. No dependency on any external store.

## What's in 0.3.0

- **`LfuCache<K, V>`.** Bounded, thread-safe Least-Frequently-Used cache. Each entry carries a counter that increments 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 the **least-recently-accessed** entry (so the freshest of multiple equally-cold entries survives). [`contains_key`] is a query and never touches the counter or access stamp, in line with the [`Cache`] trait contract — this is observable: you can probe for membership without disturbing the eviction order.

  Same `&self`-everywhere shape as `LruCache`: a single instance is `Send + Sync` and usable across threads or across `.await` points without external locking. Poison-tolerant: a panic inside any operation does not brick the cache. No new external dependencies.

  The 0.3.0 reference implementation uses `Mutex<HashMap<K, Entry { value, count, last_access }>>` and an O(n) scan to locate the eviction victim — correctness over speed at this milestone. The O(1) bucket-based replacement lands in 0.5.0 without changing this public surface.

- **Constructors that mirror `LruCache`.** `LfuCache::new(usize) -> Result<Self, CacheError>` (fallible, rejects zero) and `LfuCache::with_capacity(NonZeroUsize) -> Self` (infallible). No new error variants — `CacheError::InvalidCapacity` already covers the precondition.

- **Eight new integration tests.** Counter-based eviction order, LRU tie-break when counters match, `contains_key` non-promotion (verified by checking that repeated probes do not save a key from eviction), replacement returns the old value, removal returns the value, `clear` preserves capacity, capacity reporting, and `Send + Sync` static-assertion. Three new doctests on the type + both constructors. Total test suite is now 19 integration + 9 doctests.

## What's not in 0.3.0

By design, deferred to subsequent minors:

- **TTL eviction.** Lands in 0.4.0 — `TtlCache<K, V>` with per-entry expiration and lazy expiry on access.
- **TinyLFU and `SizedCache`.** Land in 0.5.0 alongside the lock-free arena-backed rewrites of `LruCache` and `LfuCache`. The current LFU implementation's frequency-tracking machinery informs TinyLFU's admission-filter design but does not block on it.
- **Shared abstraction between `LruCache` and `LfuCache`.** With only two policies the duplication is minor and the cost of premature abstraction is real. Refactor target: when the third concrete cache type lands and the pattern is clear.
- **`Borrow<Q>`-generic lookups.** Additive; can land at any point without breaking 0.3.0 call-sites.

## Breaking changes

**None.** `LfuCache` is a new public type alongside `LruCache`; the `Cache` trait, `CacheError`, and `LruCache` signatures are unchanged. Every 0.2.0 call-site compiles and behaves identically against 0.3.0.

The crate remains pre-1.0; minor versions may break in the future. Pin exact versions.

## Verification

Local run on Windows x86_64, Rust stable; identical commands pass on Linux and via the configured CI matrix (Linux / macOS / Windows on stable + MSRV 1.75):

```bash
cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo clippy --all-targets --no-default-features -- -D warnings
cargo test --all-features
cargo doc --no-deps --all-features
```

All green. Test totals:

- Integration tests: **19 passed** (11 from 0.2.0 + 8 new for LFU).
- Doctests: **9 passed** (6 from 0.2.0 + 3 new for `LfuCache`, `::new`, `::with_capacity`).

REPS lint surface declared in `src/lib.rs` is honored: every `deny(...)` clippy/rustc lint from 0.2.0 still holds. No `unsafe` is introduced in this release.

## What's next

`0.4.0` adds `TtlCache<K, V>` — bounded, lazy-expiry, per-entry TTL with an optional per-call override (`insert_with_ttl`). `0.5.0` lands the remaining policies (TinyLFU, `SizedCache`) **and** is the implementation-quality milestone — the `Mutex`-guarded reference implementations of `LruCache` and `LfuCache` are replaced by lock-free, arena-backed versions while keeping the public surface identical; property tests and Criterion benchmarks land here. `0.9.0` is the hardening + audit pass; `1.0.0` is the API freeze.

## Installation

```toml
[dependencies]
cache-mod = "0.3"
```

MSRV: Rust 1.75. Edition 2021. `default-features = ["std"]`.

```rust
use cache_mod::{Cache, LfuCache};

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

cache.insert("hot", 1);
cache.insert("cold", 0);

// Repeatedly hit "hot" so its counter dwarfs "cold"'s.
for _ in 0..16 { let _ = cache.get(&"hot"); }

// On overflow, "cold" goes first.
assert!(cache.contains_key(&"cold"));
```

## Documentation

- [README](https://github.com/jamesgober/cache-mod/blob/main/README.md)
- [CHANGELOG](https://github.com/jamesgober/cache-mod/blob/main/CHANGELOG.md)
- [REPS standards](https://github.com/jamesgober/cache-mod/blob/main/REPS.md)
- [API reference](https://docs.rs/cache-mod/0.3.0)

---

**Full diff:** [`v0.2.0...v0.3.0`](https://github.com/jamesgober/cache-mod/compare/v0.2.0...v0.3.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/cache-mod/blob/main/CHANGELOG.md#030---2026-05-20).

[`Cache`]: https://docs.rs/cache-mod/0.3.0/cache_mod/trait.Cache.html
[`get`]: https://docs.rs/cache-mod/0.3.0/cache_mod/trait.Cache.html#tymethod.get
[`insert`]: https://docs.rs/cache-mod/0.3.0/cache_mod/trait.Cache.html#tymethod.insert
[`contains_key`]: https://docs.rs/cache-mod/0.3.0/cache_mod/trait.Cache.html#tymethod.contains_key
