Module cache 

A fixed-capacity key-value cache using Clock2Q+ replacement.

Clock2Q+ separates residents into a Small probation queue and a Main CLOCK ring. New entries enter Small, where hits outside a correlation window earn promotion to Main. Main gives referenced entries a second chance before eviction. A bounded Ghost queue records keys evicted from Small. A later request for one of these keys consumes its history and enters Main directly. During warm-up, cold entries fill Small first and then Main.

For capacity C, Small is max(C / 10, 1) when C > 1, Main gets the remainder, and Ghost is C / 2. The newest half of Small, rounded up, forms the correlation window. Hits inside this window are ignored. Admission age advances even when entries are removed, so older survivors never become young again. At capacities 2 through 19, Small holds one always-correlated slot, so admission to a full Main requires a Ghost hit. Capacity one uses Main alone.

Stable Slots and Hints

A resident keeps its numeric slot until removal or eviction, including when it moves from Small to Main. Cache::get_at validates both liveness and the full key. Stale or out-of-bounds hints therefore return a miss, and callers can fall back to Cache::get.

Value Reuse

Slots grow lazily to capacity and are then reused in place. Cache::remove and Cache::retain keep detached values available for later insertion. Cache::get_or_insert_mut returns the selected slot and its existing value so buffer values can be overwritten without reallocating. Cache::prefill can allocate every value during construction. Value-returning methods such as Cache::put replace and drop displaced values as usual.

Resident and Ghost indexes store only slot IDs and read canonical keys from their respective slots. Each index reserves twice its independent entry limit, keeping its backing allocation fixed during insertion and eviction. Tombstone cleanup can still rehash the indexes in place. Keys, values, and other metadata can allocate separately.

Concurrency

Cache performs no internal locking. Shared lookups record hits in an inline atomic byte without accessing queue topology. Mutating operations require &mut self, so a reader-writer lock can serve hits concurrently:

use commonware_utils::cache::Cache;
use core::num::NonZeroUsize;
use std::sync::RwLock;

let cache = RwLock::new(Cache::<u64, u64>::new(NonZeroUsize::new(4).unwrap()));
if cache.read().unwrap().get(&7).is_none() {
    cache.write().unwrap().get_or_insert_with(7, || 7 * 7);
}
assert_eq!(cache.read().unwrap().get(&7).copied(), Some(49));

Structs

Cache

A fixed-capacity key-value cache using Clock2Q+ replacement.