Crate evictor 

evictor

Generic in‑memory caches with pluggable eviction policies. One uniform API, generic over key + value, O(1) average core ops, and interchangeable eviction behavior chosen by a type alias.

Policies at a glance

Policy	Evicts	Primary signal	Notes
Lru	Least recently used	Recency	Doubly linked list of entries
Mru	Most recently used	Recency (inverted)	Same structure as LRU, opposite victim
Lfu	Least frequently used	Frequency + recency tie break	Frequency buckets; O(1) amortized updates
Fifo	Oldest inserted	Insertion order	Queue semantics (head victim)
Lifo	Newest inserted	Insertion order	Stack semantics (head victim)
Random	Random entry	RNG	Requires rand feature (default)
Sieve	First unvisited (2nd chance)	Visited bit pass	Implements NSDI’24 SIEVE (see paper)

Max Capacity

The maximum capacity of a cache must be specified at creation time (minimum 1, maximum 2^32 - 1), although it may later be changed with set_capacity(). Insertion of a new entry when at capacity evicts an existing entry according to the policy.

Size overhead

All policies use a custom linked hash map implementation, which has a per-entry overhead of 4 u32s (16 bytes) plus the size of the key + value. LFU has additional overhead for frequency buckets, which is small compared to the entry overhead unless there are many unique frequencies.

The four u32s are for the doubly linked list (2), an index into a compressed list of linked list pointers, and of course, the actual entry in the reverse mapping. These are needed to achieve O(1) updates for all policies.

Quick start

LRU example (API identical for all policies)

use std::num::NonZeroUsize;
use evictor::Lru;

let mut cache = Lru::<i32, &'static str>::new(NonZeroUsize::new(3).unwrap());
cache.insert(1, "one");
cache.insert(2, "two");
cache.insert(3, "three");
cache.get(&1);           // mark as recently used
cache.insert(4, "four"); // evicts key 2
assert!(!cache.contains_key(&2));

Swap Lru for Mru, Lfu, Fifo, Lifo, Random, or Sieve to change behavior.

Policy nuances

use std::num::NonZeroUsize;
use evictor::{Mru, Lfu, Fifo, Lifo, Sieve};
#[cfg(feature = "rand")]
use evictor::Random;

let mut mru = Mru::new(NonZeroUsize::new(2).unwrap());
mru.insert('a', 1);
mru.insert('b', 2);
mru.get(&'a');         // 'a' now MRU
mru.insert('c', 3);    // evicts 'a'

let mut lfu = Lfu::new(NonZeroUsize::new(2).unwrap());
lfu.insert('a', 1);
lfu.insert('b', 2);
lfu.get(&'a');         // freq(a)=1
lfu.insert('c', 3);    // evicts 'b'

let mut sieve = Sieve::new(NonZeroUsize::new(2).unwrap());
sieve.insert(1, "x");
sieve.insert(2, "y");
sieve.get(&1);         // mark visited
sieve.insert(3, "z");  // evicts 2 (unvisited)

Building from iterators

FromIterator collects all pairs setting capacity to the number of unique items in the iterator (minimum 1).

use evictor::{Lru, Mru, Lfu, Fifo, Lifo, Sieve};
#[cfg(feature = "rand")]
use evictor::Random;

let data = [(1, "one".to_string()), (2, "two".to_string()), (3, "three".to_string())];
let lru: Lru<_, _> = data.into_iter().collect();
assert_eq!(lru.len(), 3);

Iteration order

iter() and into_iter() yield entries in eviction order (tail first) except Random (arbitrary / randomized).

Performance

Average insert, get, peek, remove, pop: O(1). Worst cases inherit IndexMap behavior. LFU adjustments are O(1) amortized (bucket promotion); SIEVE’s tail() may scan O(n) in degenerate patterns.

Mutation‑aware access (peek_mut)

peek_mut only reorders if the value is mutated (tracked by Drop). Plain get_mut always touches.

Capacity management

• set_capacity(new) adjusts capacity, evicting as needed.
• evict_to_size(n) trims down to a target size.
• evict_n_entries(k) evicts up to k victims.

Feature flags

Feature	Default	Purpose
ahash	Yes	Faster hashing (ahash::RandomState)
rand	Yes	Enables Random policy
statistics	No	Enables cache statistics tracking (hits, misses, etc.)
internal-debugging	No	Potentially expensive invariant checking (debug builds only)

Safety & Guarantees

• No unsafe code in library (although e.g. hashbrown may use some).

License

MIT OR Apache‑2.0. See LICENSE-MIT and LICENSE-APACHE.

Structs

Cache

A generic cache implementation with configurable eviction policies.

Entry

A smart reference to a cached value that tracks modifications.

Statisticsstatistics

Cache performance and usage statistics.

Type Aliases

Fifo

A first-in-first-out (Fifo) cache.

Lfu

A least-frequently-used (Lfu) cache.

Lifo

A last-in-first-out (Lifo) cache.

Lru

A least-recently-used (Lru) cache.

Mru

A most-recently-used (Mru) cache.

Randomrand

A random eviction cache.

Sieve

A Sieve cache implementing the algorithm outlined in the paper Sieve is Simpler than Lru.