Crate oxistore_cache 

oxistore-cache — Pure-Rust LRU, ARC, LFU, and W-TinyLFU eviction primitives.

This crate provides four cache implementations behind a unified Cache trait:

• LruCache — classic Least-Recently-Used cache backed by a hashlink::LinkedHashMap. O(1) amortised operations.

• ArcCache — Adaptive Replacement Cache (Megiddo & Modha, FAST’03), which balances recency and frequency by maintaining four lists (T1, T2, B1, B2) and an adaptive target p. ARC is scan-resistant.

• LfuCache — Least-Frequently-Used cache with O(1) operations using the Shah, Mitra & Matani (2010) algorithm.

• WTinyLfuCache — Window TinyLFU with Count-Min Sketch frequency estimation and a doorkeeper bloom filter, providing near-optimal hit rates on skewed (Zipfian) workloads.

All cache implementations support per-entry TTL (time-to-live) via the Cache::put_with_ttl method. Expiry is checked lazily on access.

Example

use oxistore_cache::{LruCache, ArcCache, LfuCache, WTinyLfuCache, Cache};

let mut lru = LruCache::new(3);
lru.put(1u32, "a");
lru.put(2u32, "b");
lru.put(3u32, "c");
lru.put(4u32, "d"); // evicts 1 (LRU)
assert!(lru.get(&1u32).is_none());
assert_eq!(lru.get(&2u32), Some(&"b"));

let mut arc = ArcCache::new(3);
arc.put(1u32, "a");
arc.put(2u32, "b");
arc.put(3u32, "c");

let mut lfu = LfuCache::new(3);
lfu.put(1u32, "a");
lfu.put(2u32, "b");
lfu.put(3u32, "c");

let mut wtlfu = WTinyLfuCache::new(3);
wtlfu.put(1u32, "a");
wtlfu.put(2u32, "b");
wtlfu.put(3u32, "c");

Re-exports

pub use arc::ArcCache;

pub use bounded::BoundedCache;

pub use builder::CacheBuilder;

pub use builder::CachePolicy;

pub use lfu::LfuCache;

pub use lru::LruCache;

pub use sharded::ShardedCache;

pub use stats::CacheStats;

pub use stats::StatsCache;

pub use sync::SyncCache;

pub use tinylfu::WTinyLfuCache;

pub use write_adapter::CacheableKvStore;

pub use write_adapter::WriteBackCache;

pub use write_adapter::WriteThroughCache;

Modules

arc

Adaptive Replacement Cache (ARC) — balances recency and frequency.

bounded

Bounded-memory cache wrapper — enforces a hard byte-budget cap. Bounded-memory cache wrapper.

builder

Cache builder — ergonomic constructor for all cache policies. Cache builder — ergonomic constructor for all cache policies.

lfu

Least-Frequently-Used (LFU) cache — O(1) frequency-based eviction.

lru

Least-Recently-Used (LRU) cache — evicts the least recently accessed entry.

sharded

Sharded concurrent cache — N LRU shards behind a Mutex for low contention. Sharded concurrent cache.

sketch

Count-Min Sketch and Doorkeeper bloom filter for W-TinyLFU. Count-Min Sketch with 4-bit packed counters and a Doorkeeper bloom filter.

stats

Cache hit/miss statistics tracking. Cache hit/miss statistics.

sync

Thread-safe cache wrapper — wraps any Cache impl behind a Mutex. Thread-safe cache wrapper backed by a std::sync::Mutex.

tinylfu

Window TinyLFU — state-of-the-art admission policy with CMS frequency estimator.

write_adapter

Write-through and write-back cache adapters. Write-through and write-back cache adapters.

Structs

CacheEntry

A cache entry that optionally expires at a given instant.

Traits

Cache

Unified interface for key-value caches with bounded capacity.

Functions

get_or_insert_async

Look up key in cache, returning the cached value if present.