1#![doc = include_str!("../README.md")]
2
3use std::hash::Hash;
6use std::num::NonZeroU64;
7use std::sync::atomic::{AtomicU64, Ordering};
8use std::sync::{Arc, Mutex};
9
10#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
12pub struct CacheStats {
13 pub hits: u64,
15 pub misses: u64,
17 pub evictions: u64,
19}
20
21pub struct ByteLruCache<K, V> {
32 inner: Mutex<Inner<K, V>>,
33 hits: AtomicU64,
34 misses: AtomicU64,
35 evictions: AtomicU64,
36 label: String,
37}
38
39struct Inner<K, V> {
40 entries: lru::LruCache<K, Weighted<V>>,
41 current_bytes: u64,
42 max_bytes: u64,
43}
44
45struct Weighted<V> {
46 value: Arc<V>,
47 weight_bytes: NonZeroU64,
48}
49
50impl<K, V> ByteLruCache<K, V>
51where
52 K: Eq + Hash + Send + Sync,
53 V: Send + Sync,
54{
55 #[must_use]
61 pub fn new(max_bytes: u64, label: impl Into<String>) -> Self {
62 Self {
63 inner: Mutex::new(Inner {
64 entries: lru::LruCache::unbounded(),
65 current_bytes: 0,
66 max_bytes,
67 }),
68 hits: AtomicU64::new(0),
69 misses: AtomicU64::new(0),
70 evictions: AtomicU64::new(0),
71 label: label.into(),
72 }
73 }
74
75 #[must_use]
77 pub fn label(&self) -> &str {
78 &self.label
79 }
80
81 #[must_use]
87 pub fn get(&self, key: &K) -> Option<Arc<V>> {
88 let mut guard = self.inner.lock().expect("cache lock poisoned");
89 if let Some(entry) = guard.entries.get(key) {
90 self.hits.fetch_add(1, Ordering::Relaxed);
91 Some(Arc::clone(&entry.value))
92 } else {
93 self.misses.fetch_add(1, Ordering::Relaxed);
94 None
95 }
96 }
97
98 pub fn insert(&self, key: K, value: Arc<V>, weight_bytes: NonZeroU64) {
109 let mut guard = self.inner.lock().expect("cache lock poisoned");
110 if let Some(previous) = guard.entries.peek(&key) {
111 guard.current_bytes = guard
112 .current_bytes
113 .saturating_sub(previous.weight_bytes.get());
114 }
115 guard.current_bytes = guard.current_bytes.saturating_add(weight_bytes.get());
116 guard.entries.put(
117 key,
118 Weighted {
119 value,
120 weight_bytes,
121 },
122 );
123 self.evict_until_under_cap(&mut guard);
124 }
125
126 pub fn evict(&self, key: &K) {
132 let mut guard = self.inner.lock().expect("cache lock poisoned");
133 if let Some(entry) = guard.entries.pop(key) {
134 guard.current_bytes = guard.current_bytes.saturating_sub(entry.weight_bytes.get());
135 }
136 }
137
138 #[must_use]
144 pub fn current_bytes(&self) -> u64 {
145 self.inner
146 .lock()
147 .expect("cache lock poisoned")
148 .current_bytes
149 }
150
151 #[must_use]
157 pub fn max_bytes(&self) -> u64 {
158 self.inner.lock().expect("cache lock poisoned").max_bytes
159 }
160
161 pub fn set_max_bytes(&self, max_bytes: u64) {
167 let mut guard = self.inner.lock().expect("cache lock poisoned");
168 guard.max_bytes = max_bytes;
169 self.evict_until_under_cap(&mut guard);
170 }
171
172 #[must_use]
174 pub fn stats(&self) -> CacheStats {
175 CacheStats {
176 hits: self.hits.load(Ordering::Relaxed),
177 misses: self.misses.load(Ordering::Relaxed),
178 evictions: self.evictions.load(Ordering::Relaxed),
179 }
180 }
181
182 #[must_use]
188 pub fn len(&self) -> usize {
189 self.inner
190 .lock()
191 .expect("cache lock poisoned")
192 .entries
193 .len()
194 }
195
196 #[must_use]
198 pub fn is_empty(&self) -> bool {
199 self.len() == 0
200 }
201
202 fn evict_until_under_cap(&self, guard: &mut Inner<K, V>) {
203 while guard.current_bytes > guard.max_bytes {
204 let Some((_, entry)) = guard.entries.pop_lru() else {
205 break;
206 };
207 guard.current_bytes = guard.current_bytes.saturating_sub(entry.weight_bytes.get());
208 self.evictions.fetch_add(1, Ordering::Relaxed);
209 }
210 }
211}
212
213#[cfg(test)]
214mod tests {
215 use std::num::NonZeroU64;
216 use std::sync::Arc;
217
218 use super::{ByteLruCache, CacheStats};
219
220 fn weight(bytes: u64) -> NonZeroU64 {
221 NonZeroU64::new(bytes).expect("test weights are positive")
222 }
223
224 #[test]
225 fn stores_and_retrieves_generic_values() {
226 let cache = ByteLruCache::new(64, "values");
227 cache.insert("answer", Arc::new(42_u32), weight(4));
228
229 assert_eq!(cache.get(&"answer").as_deref(), Some(&42));
230 assert_eq!(cache.current_bytes(), 4);
231 assert_eq!(cache.stats().hits, 1);
232 }
233
234 #[test]
235 fn misses_are_counted() {
236 let cache: ByteLruCache<u32, String> = ByteLruCache::new(64, "values");
237
238 assert!(cache.get(&7).is_none());
239 assert_eq!(cache.stats().misses, 1);
240 }
241
242 #[test]
243 fn least_recently_used_entry_is_evicted() {
244 let cache = ByteLruCache::new(20, "values");
245 cache.insert(1, Arc::new("one"), weight(8));
246 cache.insert(2, Arc::new("two"), weight(8));
247 let _ = cache.get(&1);
248 cache.insert(3, Arc::new("three"), weight(8));
249
250 assert!(cache.get(&1).is_some());
251 assert!(cache.get(&2).is_none());
252 assert!(cache.get(&3).is_some());
253 assert!(cache.current_bytes() <= 20);
254 assert_eq!(cache.stats().evictions, 1);
255 }
256
257 #[test]
258 fn replacement_updates_weight_without_double_counting() {
259 let cache = ByteLruCache::new(64, "values");
260 cache.insert(1, Arc::new(1_u32), weight(10));
261 cache.insert(1, Arc::new(2_u32), weight(30));
262
263 assert_eq!(cache.current_bytes(), 30);
264 assert_eq!(cache.get(&1).as_deref(), Some(&2));
265 }
266
267 #[test]
268 fn reducing_the_ceiling_evicts_immediately() {
269 let cache = ByteLruCache::new(1_000, "values");
270 for key in 0..10_u32 {
271 cache.insert(key, Arc::new(key), weight(100));
272 }
273
274 cache.set_max_bytes(250);
275
276 assert!(cache.current_bytes() <= 250);
277 assert_eq!(cache.len(), 2);
278 }
279
280 #[test]
281 fn zero_ceiling_retains_nothing() {
282 let cache = ByteLruCache::new(0, "disabled");
283 cache.insert(1_u32, Arc::new(1_u32), weight(1));
284
285 assert!(cache.is_empty());
286 assert_eq!(cache.current_bytes(), 0);
287 assert_eq!(cache.stats().evictions, 1);
288 }
289
290 #[test]
291 fn labels_and_empty_stats_are_stable() {
292 let cache: ByteLruCache<u32, u32> = ByteLruCache::new(64, "test-cache");
293
294 assert_eq!(cache.label(), "test-cache");
295 assert!(cache.is_empty());
296 assert_eq!(cache.stats(), CacheStats::default());
297 }
298}