subms_block_cache/
lib.rs

1//! Clock-sweep block cache. Fixed capacity. Constant-time eviction.
2//!
3//! Slots form a ring. Each slot has a referenced bit. On insert, if the
4//! cache is full, the hand walks the ring: if the slot's referenced bit is
5//! set, clear it; if not, evict that slot. Reads set the referenced bit on
6//! the hit slot. This is the second-chance variant of LRU - fewer per-op
7//! pointer-chasing costs, near-LRU eviction quality.
8//!
9//! ```
10//! use subms_block_cache::BlockCache;
11//! let mut c: BlockCache<u32, &'static str> = BlockCache::with_capacity(4);
12//! c.put(1, "one");
13//! c.put(2, "two");
14//! assert_eq!(c.get(&1), Some(&"one"));
15//! ```
16//!
17//! Full writeup, design notes and measured benchmarks:
18//! <https://www.submillisecond.com/cookbook/recipes/subms-block-cache>
19
20// Opt-in feature modules. Each is independent of the base cache and
21// gated by its own Cargo feature; `cargo add subms-block-cache` alone
22// keeps the base zero-dep + std-only shape.
23//
24// The `clock-sweep` policy from the original feature menu IS the base
25// in this recipe, so it has no separate feature gate.
26#[cfg(any(
27    feature = "arc",
28    feature = "tinylfu",
29    feature = "weighted",
30    feature = "concurrent-shards",
31    feature = "metrics",
32))]
33pub mod features;
34
35#[cfg(feature = "arc")]
36pub use features::arc::ArcCache;
37#[cfg(feature = "concurrent-shards")]
38pub use features::concurrent_shards::ShardedCache;
39#[cfg(feature = "metrics")]
40pub use features::metrics::{CacheMetrics, MetricsCache};
41#[cfg(feature = "tinylfu")]
42pub use features::tinylfu::TinyLfuCache;
43#[cfg(feature = "weighted")]
44pub use features::weighted::WeightedCache;
45
46use std::collections::HashMap;
47
48pub struct BlockCache<K, V> {
49    capacity: usize,
50    /// Slot storage. None = empty slot.
51    slots: Vec<Option<Slot<K, V>>>,
52    /// Map key -> slot index.
53    index: HashMap<K, usize>,
54    /// Clock hand position.
55    hand: usize,
56}
57
58struct Slot<K, V> {
59    key: K,
60    value: V,
61    referenced: bool,
62}
63
64impl<K: std::hash::Hash + Eq + Clone, V> BlockCache<K, V> {
65    pub fn with_capacity(capacity: usize) -> Self {
66        let cap = capacity.max(1);
67        let mut slots = Vec::with_capacity(cap);
68        for _ in 0..cap {
69            slots.push(None);
70        }
71        Self {
72            capacity: cap,
73            slots,
74            index: HashMap::with_capacity(cap),
75            hand: 0,
76        }
77    }
78
79    pub fn capacity(&self) -> usize {
80        self.capacity
81    }
82    pub fn len(&self) -> usize {
83        self.index.len()
84    }
85    pub fn is_empty(&self) -> bool {
86        self.index.is_empty()
87    }
88
89    /// Get a reference to the value for `key`, marking the slot referenced
90    /// for the clock sweep.
91    pub fn get(&mut self, key: &K) -> Option<&V> {
92        let idx = *self.index.get(key)?;
93        let slot = self.slots[idx].as_mut().expect("indexed slot is populated");
94        slot.referenced = true;
95        Some(&self.slots[idx].as_ref().unwrap().value)
96    }
97
98    /// Insert or update. Returns the evicted (key, value) pair if eviction
99    /// happened to make room.
100    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
101        if let Some(&idx) = self.index.get(&key) {
102            // Update in place.
103            let slot = self.slots[idx].as_mut().unwrap();
104            slot.value = value;
105            slot.referenced = true;
106            return None;
107        }
108
109        if self.index.len() < self.capacity {
110            // Find an empty slot.
111            for i in 0..self.capacity {
112                if self.slots[i].is_none() {
113                    self.slots[i] = Some(Slot {
114                        key: key.clone(),
115                        value,
116                        referenced: true,
117                    });
118                    self.index.insert(key, i);
119                    return None;
120                }
121            }
122            unreachable!("under capacity but no empty slot");
123        }
124
125        // Evict via clock sweep.
126        loop {
127            let idx = self.hand;
128            self.hand = (self.hand + 1) % self.capacity;
129            let slot = self.slots[idx].as_mut().expect("populated");
130            if slot.referenced {
131                slot.referenced = false;
132                continue;
133            }
134            // Evict this slot.
135            let old = self.slots[idx].take().unwrap();
136            self.index.remove(&old.key);
137            self.slots[idx] = Some(Slot {
138                key: key.clone(),
139                value,
140                referenced: true,
141            });
142            self.index.insert(key, idx);
143            return Some((old.key, old.value));
144        }
145    }
146
147    /// Invalidate `key`, returning its value. The vacated slot is refilled by
148    /// the next insert; the hand does not move, so removal costs one map
149    /// lookup and one slot store.
150    pub fn remove(&mut self, key: &K) -> Option<V> {
151        let idx = self.index.remove(key)?;
152        let slot = self.slots[idx].take().expect("indexed slot is populated");
153        Some(slot.value)
154    }
155
156    /// Drop every entry and reset the hand. Capacity is unchanged.
157    pub fn clear(&mut self) {
158        for slot in &mut self.slots {
159            *slot = None;
160        }
161        self.index.clear();
162        self.hand = 0;
163    }
164}
165
166#[cfg(feature = "harness")]
167pub mod recipe;
168
169#[cfg(test)]
170#[path = "cache_tests.rs"]
171mod cache_tests;
172
173#[cfg(test)]
174#[path = "sample_app_tests.rs"]
175mod sample_app_tests;
subms_block_cache/lib.rs

subms_block_cache/
lib.rs
