linera_cache/
unique_value_cache.rs

1// Copyright (c) Zefchain Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4//! A mutex-guarded LRU cache for move-in/move-out value patterns where `V` is not `Clone`.
5
6use std::{hash::Hash, num::NonZeroUsize, sync::Mutex};
7
8use lru::LruCache;
9
10/// A bounded cache for values that are inserted and then taken out (moved), not cloned.
11///
12/// Uses `Mutex<LruCache>` internally. Suitable for caching values that don't implement
13/// `Clone`, where the access pattern is insert → remove rather than insert → get.
14pub struct UniqueValueCache<K, V>
15where
16    K: Hash + Eq,
17{
18    cache: Mutex<LruCache<K, V>>,
19}
20
21impl<K, V> UniqueValueCache<K, V>
22where
23    K: Hash + Eq + Copy,
24{
25    /// Creates a new `UniqueValueCache` with the given capacity.
26    pub fn new(size: usize) -> Self {
27        let size = NonZeroUsize::try_from(size).expect("Cache size must be greater than zero");
28        UniqueValueCache {
29            cache: Mutex::new(LruCache::new(size)),
30        }
31    }
32
33    /// Inserts a value into the cache if the key is not already present.
34    ///
35    /// Returns `true` if the value was newly inserted.
36    pub fn insert(&self, key: &K, value: V) -> bool {
37        let mut cache = self.cache.lock().unwrap();
38        if cache.contains(key) {
39            cache.promote(key);
40            false
41        } else {
42            cache.push(*key, value);
43            true
44        }
45    }
46
47    /// Removes a value from the cache and returns it, if present.
48    pub fn remove(&self, key: &K) -> Option<V> {
49        self.cache.lock().unwrap().pop(key)
50    }
51}
52
53#[cfg(test)]
54mod tests {
55    use super::UniqueValueCache;
56
57    const TEST_CACHE_SIZE: usize = 10;
58
59    #[test]
60    fn test_retrieve_missing_value() {
61        let cache = UniqueValueCache::<u64, String>::new(TEST_CACHE_SIZE);
62        assert!(cache.remove(&42).is_none());
63    }
64
65    #[test]
66    fn test_insert_and_remove() {
67        let cache = UniqueValueCache::<u64, String>::new(TEST_CACHE_SIZE);
68
69        assert!(cache.insert(&1, "hello".to_string()));
70        assert_eq!(cache.remove(&1), Some("hello".to_string()));
71        // Value is gone after removal.
72        assert!(cache.remove(&1).is_none());
73    }
74
75    #[test]
76    fn test_insert_duplicate_returns_false() {
77        let cache = UniqueValueCache::<u64, String>::new(TEST_CACHE_SIZE);
78
79        assert!(cache.insert(&1, "first".to_string()));
80        assert!(!cache.insert(&1, "second".to_string()));
81
82        // Original value is preserved.
83        assert_eq!(cache.remove(&1), Some("first".to_string()));
84    }
85
86    #[test]
87    fn test_insert_many_values() {
88        let cache = UniqueValueCache::<u64, String>::new(TEST_CACHE_SIZE);
89
90        for i in 0..TEST_CACHE_SIZE as u64 {
91            assert!(cache.insert(&i, format!("value-{i}")));
92        }
93
94        for i in 0..TEST_CACHE_SIZE as u64 {
95            assert_eq!(cache.remove(&i), Some(format!("value-{i}")));
96        }
97    }
98
99    #[test]
100    fn test_lru_eviction() {
101        let cache = UniqueValueCache::<u64, String>::new(TEST_CACHE_SIZE);
102
103        // Fill cache to capacity.
104        for i in 0..TEST_CACHE_SIZE as u64 {
105            cache.insert(&i, format!("value-{i}"));
106        }
107
108        // Insert one more — should evict the LRU entry (key 0).
109        cache.insert(&(TEST_CACHE_SIZE as u64), "extra".to_string());
110
111        assert!(cache.remove(&0).is_none(), "LRU entry should be evicted");
112        assert_eq!(
113            cache.remove(&(TEST_CACHE_SIZE as u64)),
114            Some("extra".to_string()),
115            "newest entry should be present"
116        );
117    }
118
119    #[test]
120    fn test_reinsertion_promotes_entry() {
121        let cache = UniqueValueCache::<u64, String>::new(TEST_CACHE_SIZE);
122
123        // Fill cache.
124        for i in 0..TEST_CACHE_SIZE as u64 {
125            cache.insert(&i, format!("value-{i}"));
126        }
127
128        // Re-insert key 0 to promote it (move to most-recently-used).
129        assert!(!cache.insert(&0, "should-be-ignored".to_string()));
130
131        // Insert one more — should evict key 1 (now the LRU), not key 0.
132        cache.insert(&(TEST_CACHE_SIZE as u64), "extra".to_string());
133
134        assert!(
135            cache.remove(&0).is_some(),
136            "re-inserted entry should survive eviction"
137        );
138        assert!(
139            cache.remove(&1).is_none(),
140            "entry after promoted one should be evicted"
141        );
142    }
143}
linera_cache/unique_value_cache.rs

linera_cache/
unique_value_cache.rs
