1use std::borrow::Borrow;
34use std::cmp::Reverse;
35use std::collections::{BinaryHeap, HashMap};
36use std::hash::Hash;
37use std::sync::atomic::{AtomicU64, Ordering};
38use std::time::{Duration, Instant};
39
40use parking_lot::Mutex;
41
42#[derive(Debug, Clone, Copy, Eq, PartialEq)]
48pub enum InsertIfAbsentNoEvictResult {
49 Inserted,
51 Duplicate,
53 Full,
55}
56
57#[derive(Debug, Clone)]
59struct Entry<V> {
60 value: V,
61 expires_at: Instant,
62 version: u64,
66}
67
68#[derive(Debug, Clone, Eq, PartialEq)]
72struct HeapEntry<K> {
73 expires_at: Instant,
74 key: K,
75 version: u64,
76}
77
78impl<K: Ord> Ord for HeapEntry<K> {
79 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
80 self.expires_at
81 .cmp(&other.expires_at)
82 .then_with(|| self.key.cmp(&other.key))
83 }
84}
85impl<K: Ord> PartialOrd for HeapEntry<K> {
86 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
87 Some(self.cmp(other))
88 }
89}
90
91struct Inner<K, V> {
92 entries: HashMap<K, Entry<V>>,
93 heap: BinaryHeap<Reverse<HeapEntry<K>>>,
94}
95
96pub struct TtlCache<K, V> {
132 inner: Mutex<Inner<K, V>>,
133 max_entries: usize,
136 reap_budget: usize,
139 next_version: AtomicU64,
140}
141
142impl<K, V> TtlCache<K, V>
143where
144 K: Clone + Eq + Hash + Ord,
145{
146 #[must_use]
149 pub fn new(max_entries: usize, reap_budget: usize) -> Self {
150 Self {
151 inner: Mutex::new(Inner {
152 entries: HashMap::new(),
153 heap: BinaryHeap::new(),
154 }),
155 max_entries,
156 reap_budget,
157 next_version: AtomicU64::new(1),
158 }
159 }
160
161 pub fn insert(&self, key: K, value: V, ttl: Duration) {
168 let now = Instant::now();
169 let expires_at = now + ttl;
170 let version = self.next_version.fetch_add(1, Ordering::Relaxed);
171
172 let mut inner = self.inner.lock();
173 Self::reap(&mut inner, now, self.reap_budget);
174
175 if inner.entries.len() >= self.max_entries && !inner.entries.contains_key(&key) {
176 Self::evict_one(&mut inner);
177 }
178
179 inner.entries.insert(
180 key.clone(),
181 Entry {
182 value,
183 expires_at,
184 version,
185 },
186 );
187 inner.heap.push(Reverse(HeapEntry {
188 expires_at,
189 key,
190 version,
191 }));
192 }
193
194 pub fn insert_if_absent(&self, key: K, value: V, ttl: Duration) -> bool {
208 let now = Instant::now();
209 let expires_at = now + ttl;
210 let version = self.next_version.fetch_add(1, Ordering::Relaxed);
211
212 let mut inner = self.inner.lock();
213 Self::reap(&mut inner, now, self.reap_budget);
214
215 if inner.entries.contains_key(&key) {
216 return false;
217 }
218 if inner.entries.len() >= self.max_entries {
219 Self::evict_one(&mut inner);
220 }
221 inner.entries.insert(
222 key.clone(),
223 Entry {
224 value,
225 expires_at,
226 version,
227 },
228 );
229 inner.heap.push(Reverse(HeapEntry {
230 expires_at,
231 key,
232 version,
233 }));
234 true
235 }
236
237 pub fn insert_if_absent_no_evict(
245 &self,
246 key: K,
247 value: V,
248 ttl: Duration,
249 ) -> InsertIfAbsentNoEvictResult {
250 let now = Instant::now();
251 let expires_at = now + ttl;
252 let version = self.next_version.fetch_add(1, Ordering::Relaxed);
253
254 let mut inner = self.inner.lock();
255 Self::reap(&mut inner, now, self.reap_budget);
256
257 if inner.entries.contains_key(&key) {
258 return InsertIfAbsentNoEvictResult::Duplicate;
259 }
260 if inner.entries.len() >= self.max_entries {
261 return InsertIfAbsentNoEvictResult::Full;
262 }
263 inner.entries.insert(
264 key.clone(),
265 Entry {
266 value,
267 expires_at,
268 version,
269 },
270 );
271 inner.heap.push(Reverse(HeapEntry {
272 expires_at,
273 key,
274 version,
275 }));
276 InsertIfAbsentNoEvictResult::Inserted
277 }
278
279 pub fn get<Q>(&self, key: &Q) -> Option<V>
285 where
286 K: Borrow<Q>,
287 Q: Hash + Eq + ?Sized,
288 V: Clone,
289 {
290 let now = Instant::now();
291 let mut inner = self.inner.lock();
292 Self::reap(&mut inner, now, self.reap_budget);
293 let entry = inner.entries.get(key)?;
294 if now >= entry.expires_at {
295 None
296 } else {
297 Some(entry.value.clone())
298 }
299 }
300
301 #[must_use]
303 pub fn len(&self) -> usize {
304 self.inner.lock().entries.len()
305 }
306
307 #[must_use]
309 pub fn is_empty(&self) -> bool {
310 self.inner.lock().entries.is_empty()
311 }
312
313 fn reap(inner: &mut Inner<K, V>, now: Instant, budget: usize) {
317 for _ in 0..budget {
318 let expired = match inner.heap.peek() {
319 Some(Reverse(top)) => top.expires_at <= now,
320 None => break,
321 };
322 if !expired {
323 break;
324 }
325 let Some(Reverse(popped)) = inner.heap.pop() else {
326 break;
327 };
328 if let Some(entry) = inner.entries.get(&popped.key) {
329 if entry.version == popped.version && entry.expires_at <= now {
330 inner.entries.remove(&popped.key);
331 }
332 }
334 }
335 }
336
337 fn evict_one(inner: &mut Inner<K, V>) {
341 while let Some(Reverse(top)) = inner.heap.pop() {
342 if let Some(entry) = inner.entries.get(&top.key) {
343 if entry.version == top.version {
344 inner.entries.remove(&top.key);
345 return;
346 }
347 }
349 }
350 }
351}
352
353#[cfg(test)]
354#[allow(clippy::unwrap_used, clippy::expect_used)]
355mod tests {
356 use super::*;
357
358 #[test]
359 fn insert_and_get_roundtrip() {
360 let cache: TtlCache<String, u32> = TtlCache::new(10_000, 16);
361 cache.insert("a".to_owned(), 1, Duration::from_secs(60));
362 assert_eq!(cache.get("a"), Some(1));
363 assert_eq!(cache.len(), 1);
364 assert!(!cache.is_empty());
365 }
366
367 #[test]
368 fn borrowed_key_lookup_avoids_allocation() {
369 let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
371 cache.insert("https://a.test/c".to_owned(), 7, Duration::from_secs(60));
372 let key: &str = "https://a.test/c";
373 assert_eq!(cache.get(key), Some(7));
374 }
375
376 #[test]
377 fn expired_entry_returns_none() {
378 let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
379 cache.insert("a".to_owned(), 1, Duration::from_millis(5));
380 std::thread::sleep(Duration::from_millis(20));
381 assert_eq!(cache.get("a"), None);
382 }
383
384 #[test]
385 fn reinsert_refreshes_and_does_not_leak_heap() {
386 let cache: TtlCache<String, u32> = TtlCache::new(10_000, 32);
387 for v in 0..5 {
389 cache.insert("a".to_owned(), v, Duration::from_millis(5));
390 }
391 std::thread::sleep(Duration::from_millis(20));
392 cache.insert("a".to_owned(), 99, Duration::from_secs(60));
394 assert_eq!(cache.len(), 1);
395 assert_eq!(cache.get("a"), Some(99));
396 }
397
398 #[test]
399 fn refresh_extends_expiry() {
400 let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
401 cache.insert("a".to_owned(), 1, Duration::from_millis(30));
402 std::thread::sleep(Duration::from_millis(15));
403 cache.insert("a".to_owned(), 2, Duration::from_secs(60));
405 std::thread::sleep(Duration::from_millis(30));
406 assert_eq!(cache.get("a"), Some(2));
408 }
409
410 #[test]
411 fn capacity_bound_evicts_next_to_expire() {
412 let cache: TtlCache<String, u32> = TtlCache::new(2, 16);
413 cache.insert("a".to_owned(), 1, Duration::from_secs(10));
414 cache.insert("b".to_owned(), 2, Duration::from_secs(60));
415 cache.insert("c".to_owned(), 3, Duration::from_secs(30));
417 assert_eq!(cache.len(), 2);
418 assert_eq!(cache.get("a"), None);
419 assert_eq!(cache.get("b"), Some(2));
420 assert_eq!(cache.get("c"), Some(3));
421 }
422
423 #[test]
424 fn evict_one_terminates_under_stale_heap_pressure() {
425 let cache: TtlCache<String, u32> = TtlCache::new(2, 4);
428 for v in 0..50 {
429 cache.insert("a".to_owned(), v, Duration::from_secs(120));
430 }
431 cache.insert("b".to_owned(), 1, Duration::from_secs(60));
432 assert_eq!(cache.len(), 2, "A + B at capacity");
433
434 cache.insert("c".to_owned(), 2, Duration::from_secs(180));
436 assert_eq!(cache.len(), 2, "still 2 after eviction");
437 assert_eq!(cache.get("b"), None, "B (shortest TTL) is the victim");
438 assert!(cache.get("a").is_some(), "A still present");
439 assert_eq!(cache.get("c"), Some(2), "C just inserted");
440 }
441
442 #[test]
443 fn lazy_delete_keeps_live_entry_after_stale_node_reaped() {
444 let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
448 cache.insert("a".to_owned(), 0, Duration::from_millis(5));
449 cache.insert("a".to_owned(), 1, Duration::from_secs(60));
450 std::thread::sleep(Duration::from_millis(20));
451 assert_eq!(cache.get("a"), Some(1));
453 assert_eq!(cache.len(), 1);
454 }
455
456 #[test]
457 fn insert_if_absent_rejects_duplicate_within_window() {
458 let cache: TtlCache<String, ()> = TtlCache::new(10, 16);
459 assert!(cache.insert_if_absent("jti-1".to_owned(), (), Duration::from_secs(60)));
460 assert!(!cache.insert_if_absent("jti-1".to_owned(), (), Duration::from_secs(60)));
461 assert!(cache.insert_if_absent("jti-2".to_owned(), (), Duration::from_secs(60)));
462 assert_eq!(cache.len(), 2);
463 }
464
465 #[test]
466 fn insert_if_absent_accepts_after_expiry() {
467 let cache: TtlCache<String, ()> = TtlCache::new(10, 16);
468 assert!(cache.insert_if_absent("jti".to_owned(), (), Duration::from_millis(5)));
469 std::thread::sleep(Duration::from_millis(20));
470 assert!(cache.insert_if_absent("jti".to_owned(), (), Duration::from_secs(60)));
471 }
472
473 #[test]
474 fn insert_if_absent_no_evict_fails_closed_at_capacity() {
475 let cache: TtlCache<String, ()> = TtlCache::new(2, 16);
476 assert_eq!(
477 cache.insert_if_absent_no_evict("jti-1".to_owned(), (), Duration::from_secs(60)),
478 InsertIfAbsentNoEvictResult::Inserted
479 );
480 assert_eq!(
481 cache.insert_if_absent_no_evict("jti-2".to_owned(), (), Duration::from_secs(60)),
482 InsertIfAbsentNoEvictResult::Inserted
483 );
484
485 assert_eq!(
486 cache.insert_if_absent_no_evict("jti-1".to_owned(), (), Duration::from_secs(60)),
487 InsertIfAbsentNoEvictResult::Duplicate,
488 "a replay and capacity exhaustion must be distinguishable"
489 );
490 assert_eq!(
491 cache.insert_if_absent_no_evict("jti-3".to_owned(), (), Duration::from_secs(60)),
492 InsertIfAbsentNoEvictResult::Full,
493 "a full barrier must not evict the earlier jti"
494 );
495 assert_eq!(cache.len(), 2);
496 assert_eq!(cache.get("jti-1"), Some(()));
497 assert_eq!(cache.get("jti-2"), Some(()));
498 }
499}