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        use rand::{Rng, SeedableRng};
58        let rng = rand::rngs::StdRng::seed_from_u64(rand::rngs::OsRng.gen());
59        RandomReplacement { rng }
60    }
61}
62
63#[cfg(feature = "rand")]
64impl<R> RandomReplacement<R> {
65    /// Construct a `RandomReplacement` with the given random number generator.
66    ///
67    /// ## Example
68    ///
69    /// ```
70    /// use associative_cache::*;
71    /// use rand::{rngs::StdRng, SeedableRng};
72    ///
73    /// let rng = StdRng::seed_from_u64(42);
74    /// let policy = RandomReplacement::with_rng(rng);
75    /// ```
76    #[inline]
77    pub fn with_rng(rng: R) -> Self {
78        RandomReplacement { rng }
79    }
80}
81
82#[cfg(feature = "rand")]
83impl<V, C, R> Replacement<V, C> for RandomReplacement<R>
84where
85    C: Capacity,
86    R: rand::Rng,
87{
88    #[inline]
89    fn choose_for_replacement<'a>(
90        &mut self,
91        candidates: impl Iterator<Item = (usize, &'a V)>,
92    ) -> usize
93    where
94        V: 'a,
95    {
96        use rand::seq::IteratorRandom;
97        candidates.choose(&mut self.rng).unwrap().0
98    }
99}
associative_cache/replacement.rs

associative_cache/
replacement.rs
