Module cache 

A fixed-capacity cache with CLOCK eviction.

Clock is a bounded key-value cache that uses the CLOCK (second-chance) replacement policy, a lightweight approximation of LRU. Each slot carries a reference bit. Reading an entry sets its bit. When the cache is full and a new entry must be inserted, a clock hand sweeps the slots: every slot whose bit is set has it cleared and is skipped (granted a second chance), and the first slot whose bit is clear is evicted.

Why CLOCK Instead of Exact LRU

Exact LRU must move an entry to the front of a recency list on every read, which requires exclusive (&mut) access. CLOCK only needs to set a reference bit, which it does through a shared (&self) reference via an atomic. This lets concurrent readers share the cache without serializing on a write lock, at the cost of approximating (rather than exactly tracking) recency.

Allocation Reuse

Slots are allocated lazily as the cache grows to capacity and are then reused in place. Eviction, Clock::remove, and Clock::retain never free a slot’s value; they detach the key and keep the slot (and its allocation) for the next insert. Clock::get_or_insert_mut exposes the reused slot (and its index) so callers holding pooled buffers can overwrite in place instead of reallocating. The value-returning inserts (Clock::put, Clock::get_or_insert_with) drop the displaced value as usual.

Concurrency

Clock performs no internal locking. Clock::get takes &self and is the only lookup that records use, so the cache can be wrapped in a reader-writer lock and queried concurrently on the hit path. Misses, which must insert, take &mut self and therefore the write lock:

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

let cache = RwLock::new(Clock::<u64, u64>::new(NonZeroUsize::new(4).unwrap()));

// Hit path: shared read lock, runs concurrently with other readers.
if cache.read().unwrap().get(&7).is_none() {
    // Miss path: exclusive write lock, computes and inserts the value once.
    cache.write().unwrap().get_or_insert_with(7, || 7 * 7);
}
assert_eq!(cache.read().unwrap().get(&7).copied(), Some(49));

Example

use commonware_utils::cache::Clock;
use core::num::NonZeroUsize;

let mut cache = Clock::new(NonZeroUsize::new(2).unwrap());

// Compute an expensive value only on a miss.
let value = *cache.get_or_insert_with(1u64, || 1u64 * 1000);
assert_eq!(value, 1000);

// A second lookup is served from the cache.
assert_eq!(cache.get(&1).copied(), Some(1000));

Structs

Clock

A fixed-capacity key-value cache that evicts entries using the CLOCK (second-chance) replacement policy.