associative_cache/
replacement.rs

1//! Implementations of various replacement algorithms used when inserting into a
2//! full cache.
3
4pub use super::{Capacity, Replacement};
5
6pub mod lru;
7pub use lru::*;
8
9/// Choose cache entries to replace in a round-robin order.
10///
11/// When considering `n` items to potentially replace, first it will replace the
12/// `0`th item, and then next time it will replace the `1`st item, ..., then the
13/// `n-1`th item, then the `0`th item, etc...
14///
15/// This replacement policy is simple and fast, but can suffer from harmonics.
16#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub struct RoundRobinReplacement {
18    n: usize,
19}
20
21impl<V, C> Replacement<V, C> for RoundRobinReplacement
22where
23    C: Capacity,
24{
25    #[inline]
26    fn choose_for_replacement<'a>(
27        &mut self,
28        mut candidates: impl ExactSizeIterator<Item = (usize, &'a V)>,
29    ) -> usize
30    where
31        V: 'a,
32    {
33        let len = candidates.len();
34        assert!(len > 0);
35        self.n %= len;
36        let index = candidates.nth(self.n).unwrap().0;
37        self.n += 1;
38        index
39    }
40}
41
42/// Choose a random cache entry to replace.
43///
44/// When considering `n` items to potentially replace, choose one at random.
45///
46/// **Requires the `"rand"` feature to be enabled.**
47#[cfg(feature = "rand")]
48#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
49pub struct RandomReplacement<R = rand::rngs::StdRng> {
50    rng: R,
51}
52
53#[cfg(feature = "rand")]
54impl Default for RandomReplacement<rand::rngs::StdRng> {
55    #[inline]
56    fn default() -> Self {
57        RandomReplacement { rng: rand::make_rng() }
58    }
59}
60
61#[cfg(feature = "rand")]
62impl<R> RandomReplacement<R> {
63    /// Construct a `RandomReplacement` with the given random number generator.
64    ///
65    /// ## Example
66    ///
67    /// ```
68    /// use associative_cache::*;
69    /// use rand::{rngs::StdRng, SeedableRng};
70    ///
71    /// let rng = StdRng::seed_from_u64(42);
72    /// let policy = RandomReplacement::with_rng(rng);
73    /// ```
74    #[inline]
75    pub fn with_rng(rng: R) -> Self {
76        RandomReplacement { rng }
77    }
78}
79
80#[cfg(feature = "rand")]
81impl<V, C, R> Replacement<V, C> for RandomReplacement<R>
82where
83    C: Capacity,
84    R: rand::Rng,
85{
86    #[inline]
87    fn choose_for_replacement<'a>(
88        &mut self,
89        candidates: impl Iterator<Item = (usize, &'a V)>,
90    ) -> usize
91    where
92        V: 'a,
93    {
94        use rand::seq::IteratorRandom;
95        candidates.choose(&mut self.rng).unwrap().0
96    }
97}
associative_cache/replacement.rs

associative_cache/
replacement.rs
