associative_cache/replacement/
lru.rs

1//! Least recently used (LRU) replacement policy implementation and traits for
2//! working with LRU timestamps.
3
4use super::*;
5use std::cell::Cell;
6use std::ops::{Deref, DerefMut};
7use std::time::Instant;
8
9/// A trait for anything that has a timestamp that we can use with an LRU cache
10/// replacement policy.
11///
12/// Don't already have a timestamp in your cache value? Consider using the
13/// `WithLruTimestamp<T>` wrapper type around your cache value. That is likely a
14/// little easier than implementing this trait yourself.
15pub trait LruTimestamp {
16    /// The timestamp type that will be compared.
17    ///
18    /// The entry with smallest timestamp value (according to its `PartialOrd`
19    /// implementation) is the one that will be replaced.
20    type Timestamp<'a>: PartialOrd
21    where
22        Self: 'a;
23
24    /// Get this cache value's timestamp.
25    fn get_timestamp(&self) -> Self::Timestamp<'_>;
26
27    /// Update this cache value's timestamp.
28    ///
29    /// Note that this takes `&self`, not `&mut self`, because this is called on
30    /// all cache hits, where we don't necessarily have `&mut` access to the
31    /// cache. It is up to implementors to use internal mutability to update the
32    /// timestamp.
33    fn update_timestamp(&self);
34}
35
36/// A wrapper around a `T` cache value that maintains a timestamp for use with
37/// LRU cache replacement policies.
38///
39/// Provides `Deref[Mut]` and `As{Ref,Mut}` implementations, so it is easy to
40/// drop in with minimal source changes.
41///
42/// You can recover ownership of the inner `T` value via
43/// `WithLruTimestamp::into_inner(x)` once a value has been removed from the
44/// cache.
45///
46/// # Example
47///
48/// ```
49/// use associative_cache::*;
50///
51/// let cache = AssociativeCache::<
52///     String,
53///     // Wrap your cache value in `WithLruTimestamp`...
54///     WithLruTimestamp<usize>,
55///     Capacity128,
56///     HashEightWay,
57///     // ... and take advantage of LRU cache replacement!
58///     LruReplacement,
59/// >::default();
60/// ```
61#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
62pub struct WithLruTimestamp<T> {
63    timestamp: Cell<Instant>,
64    inner: T,
65}
66
67impl<T> Default for WithLruTimestamp<T>
68where
69    T: Default,
70{
71    #[inline]
72    fn default() -> Self {
73        WithLruTimestamp {
74            timestamp: Cell::new(Instant::now()),
75            inner: Default::default(),
76        }
77    }
78}
79
80impl<T> AsRef<T> for WithLruTimestamp<T> {
81    #[inline]
82    fn as_ref(&self) -> &T {
83        &self.inner
84    }
85}
86
87impl<T> AsMut<T> for WithLruTimestamp<T> {
88    #[inline]
89    fn as_mut(&mut self) -> &mut T {
90        &mut self.inner
91    }
92}
93
94impl<T> Deref for WithLruTimestamp<T> {
95    type Target = T;
96
97    #[inline]
98    fn deref(&self) -> &T {
99        &self.inner
100    }
101}
102
103impl<T> DerefMut for WithLruTimestamp<T> {
104    #[inline]
105    fn deref_mut(&mut self) -> &mut T {
106        &mut self.inner
107    }
108}
109
110impl<T> From<T> for WithLruTimestamp<T> {
111    #[inline]
112    fn from(inner: T) -> WithLruTimestamp<T> {
113        WithLruTimestamp::new(inner)
114    }
115}
116
117impl<T> WithLruTimestamp<T> {
118    /// Construct a new `WithLruTimestamp` wrapper around an inner value.
119    ///
120    /// ## Example
121    ///
122    /// ```
123    /// use associative_cache::*;
124    ///
125    /// let inner = "hello!".to_string();
126    /// let outer = WithLruTimestamp::new(inner);
127    /// ```
128    #[inline]
129    pub fn new(inner: T) -> WithLruTimestamp<T> {
130        WithLruTimestamp {
131            timestamp: Cell::new(Instant::now()),
132            inner,
133        }
134    }
135
136    /// Recover the inner `T` value by consuming a `WithLruTimestamp<T>`.
137    ///
138    /// ## Example
139    ///
140    /// ```
141    /// use associative_cache::*;
142    ///
143    /// let outer = WithLruTimestamp::new("hello!".to_string());
144    /// let inner = WithLruTimestamp::into_inner(outer);
145    /// assert_eq!(inner, "hello!");
146    /// ```
147    #[inline]
148    pub fn into_inner(outer: WithLruTimestamp<T>) -> T {
149        outer.inner
150    }
151}
152
153impl<T> LruTimestamp for WithLruTimestamp<T> {
154    type Timestamp<'a> = &'a Cell<Instant> where T: 'a;
155
156    #[inline]
157    fn get_timestamp(&self) -> Self::Timestamp<'_> {
158        &self.timestamp
159    }
160
161    #[inline]
162    fn update_timestamp(&self) {
163        self.timestamp.set(Instant::now());
164    }
165}
166
167/// Least recently used (LRU) cache replacement.
168///
169/// When considering which one of N cache values to replace, choose the one that
170/// was least recently used.
171///
172/// Requires that the cache value type implement `LruTimestamp`.
173#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
174pub struct LruReplacement {
175    _private: (),
176}
177
178impl<V, C> Replacement<V, C> for LruReplacement
179where
180    C: Capacity,
181    V: LruTimestamp,
182{
183    #[inline]
184    fn choose_for_replacement<'a>(
185        &mut self,
186        candidates: impl ExactSizeIterator<Item = (usize, &'a V)>,
187    ) -> usize
188    where
189        V: 'a,
190    {
191        let mut lru = None;
192        for (index, value) in candidates {
193            let timestamp = value.get_timestamp();
194            lru = match lru {
195                Some((t, i)) if t < timestamp => Some((t, i)),
196                _ => Some((timestamp, index)),
197            };
198        }
199        lru.unwrap().1
200    }
201
202    #[inline]
203    fn on_hit(&self, value: &V) {
204        value.update_timestamp();
205    }
206
207    #[inline]
208    fn on_insert(&self, value: &V) {
209        value.update_timestamp();
210    }
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216    use crate::Capacity4;
217    use std::time::Duration;
218
219    #[test]
220    fn lru_replacement() {
221        let now = Instant::now();
222        let candidates = vec![
223            now,
224            now - Duration::from_secs(1),
225            now - Duration::from_secs(2),
226            now - Duration::from_secs(3),
227        ]
228        .into_iter()
229        .map(|t| WithLruTimestamp {
230            timestamp: Cell::new(t),
231            inner: (),
232        })
233        .collect::<Vec<_>>();
234
235        let replacement = &mut LruReplacement::default();
236
237        let index = <LruReplacement as Replacement<_, Capacity4>>::choose_for_replacement(
238            replacement,
239            candidates.iter().enumerate(),
240        );
241
242        assert_eq!(index, 3);
243    }
244
245    #[test]
246    fn lru_timestamp_ref() {
247        struct Wrap {
248            timestamp: Instant,
249        }
250        impl LruTimestamp for Wrap {
251            type Timestamp<'a> = &'a Instant;
252            fn get_timestamp(&self) -> Self::Timestamp<'_> {
253                &self.timestamp
254            }
255            fn update_timestamp(&self) {}
256        }
257        let now = Instant::now();
258        let candidates = vec![
259            now,
260            now - Duration::from_secs(1),
261            now - Duration::from_secs(2),
262            now - Duration::from_secs(3),
263        ]
264        .into_iter()
265        .map(|t| Wrap { timestamp: t })
266        .collect::<Vec<_>>();
267
268        let replacement = &mut LruReplacement::default();
269
270        let index = <LruReplacement as Replacement<_, Capacity4>>::choose_for_replacement(
271            replacement,
272            candidates.iter().enumerate(),
273        );
274
275        assert_eq!(index, 3);
276    }
277
278    #[test]
279    fn lru_timestamp_owned() {
280        #[repr(packed)]
281        struct Wrap {
282            timestamp: Instant,
283        }
284        impl LruTimestamp for Wrap {
285            type Timestamp<'a> = Instant;
286            fn get_timestamp(&self) -> Self::Timestamp<'_> {
287                self.timestamp
288            }
289            fn update_timestamp(&self) {}
290        }
291        let now = Instant::now();
292        let candidates = vec![
293            now,
294            now - Duration::from_secs(1),
295            now - Duration::from_secs(2),
296            now - Duration::from_secs(3),
297        ]
298        .into_iter()
299        .map(|t| Wrap { timestamp: t })
300        .collect::<Vec<_>>();
301
302        let replacement = &mut LruReplacement::default();
303
304        let index = <LruReplacement as Replacement<_, Capacity4>>::choose_for_replacement(
305            replacement,
306            candidates.iter().enumerate(),
307        );
308
309        assert_eq!(index, 3);
310    }
311}
associative_cache/replacement/lru.rs

associative_cache/replacement/
lru.rs
