tlspuffin/tls/rustls/
limited_cache.rs1use std::borrow::Borrow;
2use std::collections::hash_map::Entry;
3use std::collections::{HashMap, VecDeque};
4use std::hash::Hash;
5
6pub struct LimitedCache<K: Clone + Hash + Eq, V> {
15 map: HashMap<K, V>,
16
17 oldest: VecDeque<K>,
19}
20
21impl<K, V> LimitedCache<K, V>
22where
23 K: Eq + Hash + Clone + std::fmt::Debug,
24{
25 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 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 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 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}