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
100
101
102
103
104
105
106
107
108
109
110
111
112

use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::Hash;

use super::{
    policy::{EvictionPolicy, InsertionPolicy},
    Cache,
};

#[derive(Default)]
pub struct ModularCache<K, V, IP, EP>
where
    K: Hash + Eq,
    IP: Default + InsertionPolicy<K>,
    EP: Default + EvictionPolicy<K>,
{
    data: HashMap<K, V>,

    insertion_policy: IP,
    eviction_policy: EP,

    maximum_size: usize,
}

impl<K, V, IP, EP> ModularCache<K, V, IP, EP>
where
    K: Hash + Eq + std::fmt::Debug,
    IP: Default + InsertionPolicy<K>,
    EP: Default + EvictionPolicy<K>,
{
    pub fn new(maximum_size: usize) -> Self {
        Self {
            data: HashMap::new(),
            insertion_policy: IP::default(),
            eviction_policy: EP::default(),
            maximum_size,
        }
    }
}

impl<K, V, IP, EP> Cache for ModularCache<K, V, IP, EP>
where
    K: Hash + Eq + std::fmt::Debug,
    IP: Default + InsertionPolicy<K>,
    EP: Default + EvictionPolicy<K>,
{
    type Key = K;
    type Value = V;

    fn insert(&mut self, key: K, value: V) -> (bool, Option<V>) {
        let is_in_cache = self.data.contains_key(&key);

        if is_in_cache {
            // Update.
            self.eviction_policy.on_update(&key);
            self.data.insert(key, value);
            return (true, None);
        } else if self.data.len() < self.maximum_size {
            if self.insertion_policy.should_add(&key) {
                // Straight insert.
                self.eviction_policy.on_insert(&key);
                self.data.insert(key, value);
                return (true, None);
            }
        } else {
            // Get a cache victim.
            let victim_key = self.eviction_policy.get_victim().unwrap(); // If this panics, there is most likely a bug in the cache.
            if self.insertion_policy.should_replace(&key, &victim_key) {
                // Evict the key
                self.eviction_policy.on_eviction(&victim_key);
                let evicted = self.data.remove(&victim_key).unwrap();

                self.eviction_policy.on_insert(&key);
                self.data.insert(key, value);
                return (true, Some(evicted));
            }
        }
        (false, None)
    }

    fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        match self.data.get(key) {
            Some(d) => {
                self.eviction_policy.on_cache_hit(key);
                self.insertion_policy.on_cache_hit(key);
                Some(d)
            }
            None => {
                self.insertion_policy.on_cache_miss(key);
                None
            }
        }
    }

    fn invalidate<Q: ?Sized>(&mut self, key: &Q)
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.data.remove(key);
        self.insertion_policy.invalidate(key);
        self.eviction_policy.invalidate(key);
    }

    fn clear(&mut self) {
        self.data.clear();
    }
}