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();
    }
}