1#![doc = include_str!("../README.md")]
2
3use std::hash::Hash;
6use std::num::NonZeroU64;
7use std::sync::atomic::{
8 AtomicU64,
9 Ordering,
10};
11use std::sync::{
12 Arc,
13 Mutex,
14};
15
16#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
18pub struct CacheStats {
19 pub hits: u64,
21 pub misses: u64,
23 pub evictions: u64,
25}
26
27pub struct ByteLruCache<K, V> {
38 inner: Mutex<Inner<K, V>>,
39 hits: AtomicU64,
40 misses: AtomicU64,
41 evictions: AtomicU64,
42 label: String,
43}
44
45struct Inner<K, V> {
46 entries: lru::LruCache<K, Weighted<V>>,
47 current_bytes: u64,
48 max_bytes: u64,
49}
50
51struct Weighted<V> {
52 value: Arc<V>,
53 weight_bytes: NonZeroU64,
54}
55
56impl<K, V> ByteLruCache<K, V>
57where
58 K: Eq + Hash + Send + Sync,
59 V: Send + Sync,
60{
61 #[must_use]
67 pub fn new(max_bytes: u64, label: impl Into<String>) -> Self {
68 Self {
69 inner: Mutex::new(Inner {
70 entries: lru::LruCache::unbounded(),
71 current_bytes: 0,
72 max_bytes,
73 }),
74 hits: AtomicU64::new(0),
75 misses: AtomicU64::new(0),
76 evictions: AtomicU64::new(0),
77 label: label.into(),
78 }
79 }
80
81 #[must_use]
83 pub fn label(&self) -> &str {
84 &self.label
85 }
86
87 #[must_use]
93 pub fn get(&self, key: &K) -> Option<Arc<V>> {
94 let mut guard = self.inner.lock().expect("cache lock poisoned");
95 if let Some(entry) = guard.entries.get(key) {
96 self.hits.fetch_add(1, Ordering::Relaxed);
97 Some(Arc::clone(&entry.value))
98 } else {
99 self.misses.fetch_add(1, Ordering::Relaxed);
100 None
101 }
102 }
103
104 pub fn insert(&self, key: K, value: Arc<V>, weight_bytes: NonZeroU64) {
115 let mut guard = self.inner.lock().expect("cache lock poisoned");
116 if let Some(previous) = guard.entries.peek(&key) {
117 guard.current_bytes = guard
118 .current_bytes
119 .saturating_sub(previous.weight_bytes.get());
120 }
121 guard.current_bytes = guard.current_bytes.saturating_add(weight_bytes.get());
122 guard.entries.put(
123 key,
124 Weighted {
125 value,
126 weight_bytes,
127 },
128 );
129 self.evict_until_under_cap(&mut guard);
130 }
131
132 pub fn evict(&self, key: &K) {
138 let mut guard = self.inner.lock().expect("cache lock poisoned");
139 if let Some(entry) = guard.entries.pop(key) {
140 guard.current_bytes = guard.current_bytes.saturating_sub(entry.weight_bytes.get());
141 }
142 }
143
144 #[must_use]
150 pub fn current_bytes(&self) -> u64 {
151 self.inner
152 .lock()
153 .expect("cache lock poisoned")
154 .current_bytes
155 }
156
157 #[must_use]
163 pub fn max_bytes(&self) -> u64 {
164 self.inner.lock().expect("cache lock poisoned").max_bytes
165 }
166
167 pub fn set_max_bytes(&self, max_bytes: u64) {
173 let mut guard = self.inner.lock().expect("cache lock poisoned");
174 guard.max_bytes = max_bytes;
175 self.evict_until_under_cap(&mut guard);
176 }
177
178 #[must_use]
180 pub fn stats(&self) -> CacheStats {
181 CacheStats {
182 hits: self.hits.load(Ordering::Relaxed),
183 misses: self.misses.load(Ordering::Relaxed),
184 evictions: self.evictions.load(Ordering::Relaxed),
185 }
186 }
187
188 #[must_use]
194 pub fn len(&self) -> usize {
195 self.inner
196 .lock()
197 .expect("cache lock poisoned")
198 .entries
199 .len()
200 }
201
202 #[must_use]
204 pub fn is_empty(&self) -> bool {
205 self.len() == 0
206 }
207
208 fn evict_until_under_cap(&self, guard: &mut Inner<K, V>) {
209 while guard.current_bytes > guard.max_bytes {
210 let Some((_, entry)) = guard.entries.pop_lru() else {
211 break;
212 };
213 guard.current_bytes = guard.current_bytes.saturating_sub(entry.weight_bytes.get());
214 self.evictions.fetch_add(1, Ordering::Relaxed);
215 }
216 }
217}
218
219#[cfg(test)]
220mod tests {
221 use std::num::NonZeroU64;
222 use std::sync::Arc;
223
224 use super::{
225 ByteLruCache,
226 CacheStats,
227 };
228
229 fn weight(bytes: u64) -> NonZeroU64 {
230 NonZeroU64::new(bytes).expect("test weights are positive")
231 }
232
233 #[test]
234 fn stores_and_retrieves_generic_values() {
235 let cache = ByteLruCache::new(64, "values");
236 cache.insert("answer", Arc::new(42_u32), weight(4));
237
238 assert_eq!(cache.get(&"answer").as_deref(), Some(&42));
239 assert_eq!(cache.current_bytes(), 4);
240 assert_eq!(cache.stats().hits, 1);
241 }
242
243 #[test]
244 fn misses_are_counted() {
245 let cache: ByteLruCache<u32, String> = ByteLruCache::new(64, "values");
246
247 assert!(cache.get(&7).is_none());
248 assert_eq!(cache.stats().misses, 1);
249 }
250
251 #[test]
252 fn least_recently_used_entry_is_evicted() {
253 let cache = ByteLruCache::new(20, "values");
254 cache.insert(1, Arc::new("one"), weight(8));
255 cache.insert(2, Arc::new("two"), weight(8));
256 let _ = cache.get(&1);
257 cache.insert(3, Arc::new("three"), weight(8));
258
259 assert!(cache.get(&1).is_some());
260 assert!(cache.get(&2).is_none());
261 assert!(cache.get(&3).is_some());
262 assert!(cache.current_bytes() <= 20);
263 assert_eq!(cache.stats().evictions, 1);
264 }
265
266 #[test]
267 fn replacement_updates_weight_without_double_counting() {
268 let cache = ByteLruCache::new(64, "values");
269 cache.insert(1, Arc::new(1_u32), weight(10));
270 cache.insert(1, Arc::new(2_u32), weight(30));
271
272 assert_eq!(cache.current_bytes(), 30);
273 assert_eq!(cache.get(&1).as_deref(), Some(&2));
274 }
275
276 #[test]
277 fn reducing_the_ceiling_evicts_immediately() {
278 let cache = ByteLruCache::new(1_000, "values");
279 for key in 0..10_u32 {
280 cache.insert(key, Arc::new(key), weight(100));
281 }
282
283 cache.set_max_bytes(250);
284
285 assert!(cache.current_bytes() <= 250);
286 assert_eq!(cache.len(), 2);
287 }
288
289 #[test]
290 fn zero_ceiling_retains_nothing() {
291 let cache = ByteLruCache::new(0, "disabled");
292 cache.insert(1_u32, Arc::new(1_u32), weight(1));
293
294 assert!(cache.is_empty());
295 assert_eq!(cache.current_bytes(), 0);
296 assert_eq!(cache.stats().evictions, 1);
297 }
298
299 #[test]
300 fn labels_and_empty_stats_are_stable() {
301 let cache: ByteLruCache<u32, u32> = ByteLruCache::new(64, "test-cache");
302
303 assert_eq!(cache.label(), "test-cache");
304 assert!(cache.is_empty());
305 assert_eq!(cache.stats(), CacheStats::default());
306 }
307}
308
309#[cfg(feature = "memory-budget")]
310impl<K, V> memory_budget::Resizable for ByteLruCache<K, V>
311where
312 K: Eq + std::hash::Hash + Send + Sync,
313 V: Send + Sync,
314{
315 fn name(&self) -> &str {
316 self.label()
317 }
318
319 fn current_bytes(&self) -> u64 {
320 self.current_bytes()
321 }
322
323 fn max_bytes(&self) -> u64 {
324 self.max_bytes()
325 }
326
327 fn set_max_bytes(&self, new: u64) {
328 self.set_max_bytes(new);
329 }
330
331 fn stats(&self) -> memory_budget::ResizableStats {
332 let stats = self.stats();
333 memory_budget::ResizableStats {
334 hits: stats.hits,
335 misses: stats.misses,
336 evictions: stats.evictions,
337 }
338 }
339}
340
341#[cfg(all(test, feature = "memory-budget"))]
342mod resizable_tests {
343 use std::num::NonZeroU64;
344 use std::sync::Arc;
345
346 use memory_budget::Resizable;
347
348 use super::ByteLruCache;
349
350 #[test]
351 fn the_cache_is_governable_through_the_resizable_seam() {
352 let cache = ByteLruCache::new(1024, "governed");
353 cache.insert(
354 "answer",
355 Arc::new(42_u32),
356 NonZeroU64::new(64).expect("positive weight"),
357 );
358 let governed: &dyn Resizable = &cache;
359 assert_eq!(governed.name(), "governed");
360 assert_eq!(governed.current_bytes(), 64);
361 assert_eq!(governed.max_bytes(), 1024);
362 governed.set_max_bytes(32);
363 assert_eq!(governed.current_bytes(), 0, "lowering the cap evicts");
364 let _ = cache.get(&"answer");
365 assert_eq!(governed.stats().misses, 1);
366 assert_eq!(governed.stats().evictions, 1);
367 }
368}