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// Opt-in feature modules. Each is independent of the base cache and
18// gated by its own Cargo feature; `cargo add subms-block-cache` alone
19// keeps the base zero-dep + std-only shape.
20//
21// The `clock-sweep` policy from the original feature menu IS the base
22// in this recipe, so it has no separate feature gate.
23#[cfg(any(
24    feature = "arc",
25    feature = "tinylfu",
26    feature = "weighted",
27    feature = "concurrent-shards",
28    feature = "metrics",
29))]
30pub mod features;
31
32#[cfg(feature = "arc")]
33pub use features::arc::ArcCache;
34#[cfg(feature = "concurrent-shards")]
35pub use features::concurrent_shards::ShardedCache;
36#[cfg(feature = "metrics")]
37pub use features::metrics::{CacheMetrics, MetricsCache};
38#[cfg(feature = "tinylfu")]
39pub use features::tinylfu::TinyLfuCache;
40#[cfg(feature = "weighted")]
41pub use features::weighted::WeightedCache;
42
43use std::collections::HashMap;
44
45pub struct BlockCache<K, V> {
46    capacity: usize,
47    /// Slot storage. None = empty slot.
48    slots: Vec<Option<Slot<K, V>>>,
49    /// Map key -> slot index.
50    index: HashMap<K, usize>,
51    /// Clock hand position.
52    hand: usize,
53}
54
55struct Slot<K, V> {
56    key: K,
57    value: V,
58    referenced: bool,
59}
60
61impl<K: std::hash::Hash + Eq + Clone, V> BlockCache<K, V> {
62    pub fn with_capacity(capacity: usize) -> Self {
63        let cap = capacity.max(1);
64        let mut slots = Vec::with_capacity(cap);
65        for _ in 0..cap {
66            slots.push(None);
67        }
68        Self {
69            capacity: cap,
70            slots,
71            index: HashMap::with_capacity(cap),
72            hand: 0,
73        }
74    }
75
76    pub fn capacity(&self) -> usize {
77        self.capacity
78    }
79    pub fn len(&self) -> usize {
80        self.index.len()
81    }
82    pub fn is_empty(&self) -> bool {
83        self.index.is_empty()
84    }
85
86    /// Get a reference to the value for `key`, marking the slot referenced
87    /// for the clock sweep.
88    pub fn get(&mut self, key: &K) -> Option<&V> {
89        let idx = *self.index.get(key)?;
90        let slot = self.slots[idx].as_mut().expect("indexed slot is populated");
91        slot.referenced = true;
92        Some(&self.slots[idx].as_ref().unwrap().value)
93    }
94
95    /// Insert or update. Returns the evicted (key, value) pair if eviction
96    /// happened to make room.
97    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
98        if let Some(&idx) = self.index.get(&key) {
99            // Update in place.
100            let slot = self.slots[idx].as_mut().unwrap();
101            slot.value = value;
102            slot.referenced = true;
103            return None;
104        }
105
106        if self.index.len() < self.capacity {
107            // Find an empty slot.
108            for i in 0..self.capacity {
109                if self.slots[i].is_none() {
110                    self.slots[i] = Some(Slot {
111                        key: key.clone(),
112                        value,
113                        referenced: true,
114                    });
115                    self.index.insert(key, i);
116                    return None;
117                }
118            }
119            unreachable!("under capacity but no empty slot");
120        }
121
122        // Evict via clock sweep.
123        loop {
124            let idx = self.hand;
125            self.hand = (self.hand + 1) % self.capacity;
126            let slot = self.slots[idx].as_mut().expect("populated");
127            if slot.referenced {
128                slot.referenced = false;
129                continue;
130            }
131            // Evict this slot.
132            let old = self.slots[idx].take().unwrap();
133            self.index.remove(&old.key);
134            self.slots[idx] = Some(Slot {
135                key: key.clone(),
136                value,
137                referenced: true,
138            });
139            self.index.insert(key, idx);
140            return Some((old.key, old.value));
141        }
142    }
143}
144
145#[cfg(feature = "harness")]
146pub mod recipe;
subms_block_cache/lib.rs

subms_block_cache/
lib.rs
