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
17use std::collections::HashMap;
18
19pub struct BlockCache<K, V> {
20    capacity: usize,
21    /// Slot storage. None = empty slot.
22    slots: Vec<Option<Slot<K, V>>>,
23    /// Map key -> slot index.
24    index: HashMap<K, usize>,
25    /// Clock hand position.
26    hand: usize,
27}
28
29struct Slot<K, V> {
30    key: K,
31    value: V,
32    referenced: bool,
33}
34
35impl<K: std::hash::Hash + Eq + Clone, V> BlockCache<K, V> {
36    pub fn with_capacity(capacity: usize) -> Self {
37        let cap = capacity.max(1);
38        let mut slots = Vec::with_capacity(cap);
39        for _ in 0..cap {
40            slots.push(None);
41        }
42        Self {
43            capacity: cap,
44            slots,
45            index: HashMap::with_capacity(cap),
46            hand: 0,
47        }
48    }
49
50    pub fn capacity(&self) -> usize {
51        self.capacity
52    }
53    pub fn len(&self) -> usize {
54        self.index.len()
55    }
56    pub fn is_empty(&self) -> bool {
57        self.index.is_empty()
58    }
59
60    /// Get a reference to the value for `key`, marking the slot referenced
61    /// for the clock sweep.
62    pub fn get(&mut self, key: &K) -> Option<&V> {
63        let idx = *self.index.get(key)?;
64        let slot = self.slots[idx].as_mut().expect("indexed slot is populated");
65        slot.referenced = true;
66        Some(&self.slots[idx].as_ref().unwrap().value)
67    }
68
69    /// Insert or update. Returns the evicted (key, value) pair if eviction
70    /// happened to make room.
71    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
72        if let Some(&idx) = self.index.get(&key) {
73            // Update in place.
74            let slot = self.slots[idx].as_mut().unwrap();
75            slot.value = value;
76            slot.referenced = true;
77            return None;
78        }
79
80        if self.index.len() < self.capacity {
81            // Find an empty slot.
82            for i in 0..self.capacity {
83                if self.slots[i].is_none() {
84                    self.slots[i] = Some(Slot {
85                        key: key.clone(),
86                        value,
87                        referenced: true,
88                    });
89                    self.index.insert(key, i);
90                    return None;
91                }
92            }
93            unreachable!("under capacity but no empty slot");
94        }
95
96        // Evict via clock sweep.
97        loop {
98            let idx = self.hand;
99            self.hand = (self.hand + 1) % self.capacity;
100            let slot = self.slots[idx].as_mut().expect("populated");
101            if slot.referenced {
102                slot.referenced = false;
103                continue;
104            }
105            // Evict this slot.
106            let old = self.slots[idx].take().unwrap();
107            self.index.remove(&old.key);
108            self.slots[idx] = Some(Slot {
109                key: key.clone(),
110                value,
111                referenced: true,
112            });
113            self.index.insert(key, idx);
114            return Some((old.key, old.value));
115        }
116    }
117}
118
119#[cfg(feature = "harness")]
120pub mod recipe;
subms_block_cache/lib.rs

subms_block_cache/
lib.rs
