1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

//! Implementations of various replacement algorithms used when inserting into a
//! full cache.

pub use super::{Capacity, Replacement};

pub mod lru;
pub use lru::*;

/// Choose cache entries to replace in a round-robin order.
///
/// When considering `n` items to potentially replace, first it will replace the
/// `0`th item, and then next time it will replace the `1`st item, ..., then the
/// `n-1`th item, then the `0`th item, etc...
///
/// This replacement policy is simple and fast, but can suffer from harmonics.
#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RoundRobinReplacement {
    n: usize,
}

impl<V, C> Replacement<V, C> for RoundRobinReplacement
where
    C: Capacity,
{
    #[inline]
    fn choose_for_replacement<'a>(
        &mut self,
        mut candidates: impl ExactSizeIterator<Item = (usize, &'a V)>,
    ) -> usize
    where
        V: 'a,
    {
        let len = candidates.len();
        assert!(len > 0);
        self.n %= len;
        let index = candidates.nth(self.n).unwrap().0;
        self.n += 1;
        index
    }
}

/// Choose a random cache entry to replace.
///
/// When considering `n` items to potentially replace, choose one at random.
///
/// **Requires the `"rand"` feature to be enabled.**
#[cfg(feature = "rand")]
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RandomReplacement<R = rand::rngs::StdRng> {
    rng: R,
}

#[cfg(feature = "rand")]
impl Default for RandomReplacement<rand::rngs::StdRng> {
    #[inline]
    fn default() -> Self {
        use rand::{Rng, SeedableRng};
        let rng = rand::rngs::StdRng::seed_from_u64(rand::rngs::OsRng.gen());
        RandomReplacement { rng }
    }
}

#[cfg(feature = "rand")]
impl<R> RandomReplacement<R> {
    /// Construct a `RandomReplacement` with the given random number generator.
    ///
    /// ## Example
    ///
    /// ```
    /// use associative_cache::*;
    /// use rand::{rngs::StdRng, SeedableRng};
    ///
    /// let rng = StdRng::seed_from_u64(42);
    /// let policy = RandomReplacement::with_rng(rng);
    /// ```
    #[inline]
    pub fn with_rng(rng: R) -> Self {
        RandomReplacement { rng }
    }
}

#[cfg(feature = "rand")]
impl<V, C, R> Replacement<V, C> for RandomReplacement<R>
where
    C: Capacity,
    R: rand::Rng,
{
    #[inline]
    fn choose_for_replacement<'a>(
        &mut self,
        candidates: impl Iterator<Item = (usize, &'a V)>,
    ) -> usize
    where
        V: 'a,
    {
        use rand::seq::IteratorRandom;
        candidates.choose(&mut self.rng).unwrap().0
    }
}