tlspuffin/tls/rustls/
limited_cache.rs

1use std::borrow::Borrow;
2use std::collections::hash_map::Entry;
3use std::collections::{HashMap, VecDeque};
4use std::hash::Hash;
5
6/// A HashMap-alike, which never gets larger than a specified
7/// capacity, and evicts the oldest insertion to maintain this.
8///
9/// The requested capacity may be rounded up by the underlying
10/// collections.  This implementation uses all the allocated
11/// storage.
12///
13/// This is inefficient: it stores keys twice.
14pub struct LimitedCache<K: Clone + Hash + Eq, V> {
15    map: HashMap<K, V>,
16
17    // first item is the oldest key
18    oldest: VecDeque<K>,
19}
20
21impl<K, V> LimitedCache<K, V>
22where
23    K: Eq + Hash + Clone + std::fmt::Debug,
24{
25    /// Create a new LimitedCache with the given rough capacity.
26    pub fn new(capacity_order_of_magnitude: usize) -> Self {
27        Self {
28            map: HashMap::with_capacity(capacity_order_of_magnitude),
29            oldest: VecDeque::with_capacity(capacity_order_of_magnitude),
30        }
31    }
32
33    pub fn insert(&mut self, k: K, v: V) {
34        let inserted_new_item = match self.map.entry(k) {
35            Entry::Occupied(mut old) => {
36                // nb. does not freshen entry in `oldest`
37                old.insert(v);
38                false
39            }
40
41            entry @ Entry::Vacant(_) => {
42                self.oldest.push_back(entry.key().clone());
43                entry.or_insert(v);
44                true
45            }
46        };
47
48        // ensure next insert() does not require a realloc
49        if inserted_new_item && self.oldest.capacity() == self.oldest.len() {
50            if let Some(oldest_key) = self.oldest.pop_front() {
51                self.map.remove(&oldest_key);
52            }
53        }
54    }
55
56    pub fn get<Q>(&self, k: &Q) -> Option<&V>
57    where
58        K: Borrow<Q>,
59        Q: ?Sized + Hash + Eq,
60    {
61        self.map.get(k)
62    }
63
64    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
65    where
66        K: Borrow<Q>,
67        Q: ?Sized + Hash + Eq,
68    {
69        if let Some(value) = self.map.remove(k) {
70            // O(N) search, followed by O(N) removal
71            if let Some(index) = self.oldest.iter().position(|item| item.borrow() == k) {
72                self.oldest.remove(index);
73            }
74            Some(value)
75        } else {
76            None
77        }
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    type Test = super::LimitedCache<String, usize>;
84
85    #[test_log::test]
86    fn test_updates_existing_item() {
87        let mut t = Test::new(3);
88        t.insert("abc".into(), 1);
89        t.insert("abc".into(), 2);
90        assert_eq!(t.get("abc"), Some(&2));
91    }
92
93    #[test_log::test]
94    fn test_evicts_oldest_item() {
95        let mut t = Test::new(3);
96        t.insert("abc".into(), 1);
97        t.insert("def".into(), 2);
98        t.insert("ghi".into(), 3);
99
100        assert_eq!(t.get("abc"), None);
101        assert_eq!(t.get("def"), Some(&2));
102        assert_eq!(t.get("ghi"), Some(&3));
103    }
104
105    #[test_log::test]
106    fn test_evicts_second_oldest_item_if_first_removed() {
107        let mut t = Test::new(3);
108        t.insert("abc".into(), 1);
109        t.insert("def".into(), 2);
110
111        assert_eq!(t.remove("abc"), Some(1));
112
113        t.insert("ghi".into(), 3);
114        t.insert("jkl".into(), 4);
115
116        assert_eq!(t.get("abc"), None);
117        assert_eq!(t.get("def"), None);
118        assert_eq!(t.get("ghi"), Some(&3));
119        assert_eq!(t.get("jkl"), Some(&4));
120    }
121
122    #[test_log::test]
123    fn test_evicts_after_second_oldest_item_removed() {
124        let mut t = Test::new(3);
125        t.insert("abc".into(), 1);
126        t.insert("def".into(), 2);
127
128        assert_eq!(t.remove("def"), Some(2));
129        assert_eq!(t.get("abc"), Some(&1));
130
131        t.insert("ghi".into(), 3);
132        t.insert("jkl".into(), 4);
133
134        assert_eq!(t.get("abc"), None);
135        assert_eq!(t.get("def"), None);
136        assert_eq!(t.get("ghi"), Some(&3));
137        assert_eq!(t.get("jkl"), Some(&4));
138    }
139
140    #[test_log::test]
141    fn test_removes_all_items() {
142        let mut t = Test::new(3);
143        t.insert("abc".into(), 1);
144        t.insert("def".into(), 2);
145
146        assert_eq!(t.remove("def"), Some(2));
147        assert_eq!(t.remove("abc"), Some(1));
148
149        t.insert("ghi".into(), 3);
150        t.insert("jkl".into(), 4);
151        t.insert("mno".into(), 5);
152
153        assert_eq!(t.get("abc"), None);
154        assert_eq!(t.get("def"), None);
155        assert_eq!(t.get("ghi"), None);
156        assert_eq!(t.get("jkl"), Some(&4));
157        assert_eq!(t.get("mno"), Some(&5));
158    }
159
160    #[test_log::test]
161    fn test_inserts_many_items() {
162        let mut t = Test::new(3);
163
164        for _ in 0..10000 {
165            t.insert("abc".into(), 1);
166            t.insert("def".into(), 2);
167            t.insert("ghi".into(), 3);
168        }
169    }
170}