Struct Recency 

pub struct Recency<K> { /* private fields */ }

A recency queue with lazy deletion.

A hit appends the key with a fresh stamp in constant time and leaves its old position behind as a ghost. The caller stores the returned stamp on its own entry and answers is_live from it, so this holds no second copy of the entry table and never duplicates whatever hangs off a key. Eviction skips ghosts as it pops them, and ghosts are dropped in bulk once they outnumber the live entries they shadow — amortized constant, like a vector reallocation. Nothing is scheduled.

Implementations

impl<K: Clone> Recency<K>

pub fn touch(&mut self, key: &K) -> u64

Records an access and returns the stamp the caller must store on its entry before calling anything else here: until the entry carries it, the position just appended reads as a ghost.

Stamps start at 1, so an entry that has never been touched can carry 0 and read as a ghost.

pub fn pop_oldest(&mut self, is_live: impl FnMut(&K, u64) -> bool) -> Option<K>

Removes and returns the least recently used live key.

None means the queue holds no live position at all, so an eviction loop must stop: popping again cannot make progress.

pub fn compact(&mut self, live_len: usize, is_live: impl FnMut(&K, u64) -> bool)

Drops ghost positions in place once they outnumber the live_len entries they shadow. Cheap enough to call on every touch.

pub fn positions(&self) -> usize

Queue positions held, live and ghost alike.

Trait Implementations

impl<K: Debug> Debug for Recency<K>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K> Default for Recency<K>

fn default() -> Self

Returns the “default value” for a type.