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

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

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.