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
113
114
115

mod cache;

use cache::*;
use std::collections::HashMap;
use std::hash::Hash;

pub use cache::Iter;

#[cfg(test)]
mod tests;

/// LRU map
#[derive(Debug, Default)]
pub struct LRUMap<K, T, const N: usize> {
    /// LRU Cache array
    cache: Cache<(K, T), N>,
    /// map to relate key and index in cache
    indices: HashMap<K, u16>,
}

impl<K, T, const N: usize> LRUMap<K, T, N>
where
    K:  Hash + Eq + Clone
{
    /// Put a key-value pair
    /// Returns the old value if the key exists, otherwise returns None
    pub fn put(&mut self, key: K, value: T) -> Option<T> {
        match self.indices.get(&key) {
            None => {
                // insert into cache and update the indices map
                self.cache.insert((key.clone(), value));
                self.indices.insert(key, self.cache.head);
                None
            },
            Some(idx) => {
                // just replace the value
                Some(self.cache.replace(*idx, (key, value)).1)
            }
        }
    }

    /// get the key-value pair and touch it
    pub fn get(&mut self, key: &K) -> Option<&T> {
        match self.indices.get(key) {
            None => None,
            Some(idx) => Some(&self.cache.get(*idx).1)
        }
    }

    /// get the key-value pair and touch it
    pub fn get_mut(&mut self, key: &K) -> Option<&mut T> {
        match self.indices.get(key) {
            None => None,
            Some(idx) => Some(&mut self.cache.get_mut(*idx).1)
        }
    }

    /// Remove a key
    pub fn remove_one(&mut self, key: &K) {
        if let Some(idx) = self.indices.remove(key) {
            self.cache.remove(idx);
        }
    }

    /// Remove keys which match the predicate.
    pub fn remove<F>(&mut self, mut pred: F)
    where
        F: FnMut(&K) -> bool
    {
        // make a new hashmap and replace the old one to make the borrow checker happy
        let old_indices = std::mem::replace(&mut self.indices, HashMap::new());
        for (key, idx) in old_indices.into_iter() {
            if pred(&key) {
                self.cache.remove(idx);
            } else {
                self.indices.insert(key, idx);
            }
        }
    }

    /// Clear the LRU Cache
    #[inline]
    pub fn clear(&mut self) {
        self.indices.clear();
        self.cache.clear();
    }

    /// Number of items
    #[inline]
    pub fn len(&self) -> usize {
        self.cache.len()
    }

    /// Touch the keys which match the predicate.
    pub fn touch<F>(&mut self, mut pred: F)
    where
        F: FnMut(&K) -> bool
    {
       for (key, idx) in self.indices.iter() {
            if pred(key) {
                self.cache.touch_index(*idx);
            }
        }
    }

    /// Iterator for keys and values
    pub fn iter(&self) -> Iter<(K, T), N> {
        self.cache.iter()
    }

    /// Iterator for keys
    pub fn keys(&self) -> impl Iterator<Item=&K> {
        self.indices.keys()
    }
}