lru_map/
cache.rs

1#![deny(unsafe_code)]
2
3//! A simple, fast, least-recently-used (LRU) cache.
4
5extern crate arrayvec;
6
7use arrayvec::ArrayVec;
8
9/// A LRU Cache based on array
10#[derive(Debug)]
11pub(crate) struct Cache<T, const N: usize> {
12    // staticaly-sized array on which linked list is built
13    pub(crate) entries: ArrayVec<Entry<T>, N>,
14    // Index of the most-recently-used entry
15    pub(crate) head: u16,
16    // Index of the least-recently-used entry
17    pub(crate) tail: u16
18}
19
20// An entry in the cache
21#[derive(Debug, Clone)]
22pub(crate) struct Entry<T> {
23    pub(crate) val: T,
24    /// Index of the previous entry
25    prev: u16,
26    /// Index of the next entry
27    next: u16,
28}
29
30impl<T, const N: usize> Default for Cache<T, N> {
31    fn default() -> Self {
32        let cache = Cache {
33            entries: ArrayVec::new(),
34            head: 0,
35            tail: 0,
36        };
37        assert!(
38            cache.entries.capacity() < u16::max_value() as usize,
39            "Capacity overflow"
40        );
41        cache
42    }
43}
44
45impl<T, const N: usize> Cache<T, N> {
46    /// Insert an item in the cache
47    /// 
48    /// This item becomes most-recently-used item.
49    /// If the cache is full, the least-recently-used item will be removed.
50    pub(crate) fn insert(&mut self, val: T) {
51        let entry = Entry {
52            val,
53            prev: 0,
54            next: 0,
55        };
56
57        let new_head = if self.entries.len() == self.entries.capacity() {
58            let i = self.pop_back();
59            self.entries[i as usize] = entry;
60            i
61        } else {
62            self.entries.push(entry);
63            self.entries.len() as u16 -1
64        };
65
66        self.push_front(new_head);
67    }
68
69    /// Touch a given entry, putting it first in the list
70    #[inline]
71    pub(crate) fn touch_index(&mut self, idx: u16) {
72        if idx != self.head {
73            self.remove(idx);
74            self.push_front(idx);
75        }
76    }
77
78    /// Returns the number of elements in the cache
79    #[inline]
80    pub(crate) fn len(&self) -> usize {
81        self.entries.len()
82    }
83
84    /// Evict all elements from the cache
85    #[inline]
86    pub(crate) fn clear(&mut self) {
87        self.entries.clear();
88    }
89
90    /// Remove an entry from the linked list
91    pub(crate) fn remove(&mut self, idx: u16) {
92        let prev = self.entries[idx as usize].prev;
93        let next = self.entries[idx as usize].next;
94
95        if idx == self.head {
96            self.head = next;
97        } else {
98            self.entries[prev as usize].next = next;
99        }
100
101        if idx == self.tail {
102            self.tail = prev;
103        } else {
104            self.entries[next as usize].prev = prev;
105        }
106    }
107
108    /// Insert a new entry at `idx` at the head of the list
109    pub(crate) fn push_front(&mut self, idx: u16) {
110        if self.entries.len() == 1 {
111            self.tail = idx;
112        } else {
113            self.entries[idx as usize].next = self.head;
114            self.entries[self.head as usize].prev = idx;
115        }
116        self.head = idx;
117    }
118
119    /// Remove the last entry from the linked list.
120    /// Returns the index of the removed entry
121    pub(crate) fn pop_back(&mut self) -> u16 {
122        let old_tail = self.tail;
123        let new_tail = self.entries[old_tail as usize].prev;
124        self.tail = new_tail;
125        old_tail
126    }
127
128    /// Replace the item in the linked list.
129    /// Returns the replaced item.
130    pub(crate) fn replace(&mut self, idx: u16, val: T) -> T {
131        self.touch_index(idx);
132        let entry = &mut self.entries[idx as usize];
133        std::mem::replace(&mut entry.val, val)
134    }
135
136    /// Touch the index and get the reference of the value
137    pub(crate) fn get(&mut self, idx: u16) -> &T {
138        self.touch_index(idx);
139        &self.entries[idx as usize].val
140    }
141
142    /// Touche the index and get the mutable reference of the value
143    pub(crate) fn get_mut(&mut self, idx: u16) -> &mut T {
144        self.touch_index(idx);
145        &mut self.entries[idx as usize].val
146    }
147
148    pub(crate) fn iter(&self) -> Iter<T, N> {
149        Iter {
150            cache: self,
151            pos: self.head,
152        }
153    }
154}
155
156impl<T, const N: usize> Clone for Cache<T, N>
157where
158    T: Clone,
159{
160    fn clone(&self) -> Self {
161        Self {
162            entries: self.entries.clone(),
163            head: self.head,
164            tail: self.tail,
165        }
166    }
167}
168
169/// Iterator over values in an LRUCache, from most-recently-used to least-recently-used.
170pub struct Iter<'a, T, const N: usize> {
171    cache: &'a Cache<T, N>,
172    pos: u16,
173}
174
175impl<'a, T, const N: usize> Iterator for Iter<'a, T, N> {
176    type Item = &'a T;
177
178    fn next(&mut self) -> Option<&'a T> {
179        let entry = self.cache.entries.get(self.pos as usize)?;
180
181        self.pos = if self.pos == self.cache.tail {
182            N as u16 // Point past the end of the array to signal we are done.
183        } else {
184            entry.next
185        };
186        Some(&entry.val)
187    }
188}
lru_map/cache.rs

lru_map/
cache.rs
