cached/
lru_list.rs

1/// Limited functionality doubly linked list using Vec as storage.
2#[derive(Clone, Debug)]
3
4pub struct LRUList<T> {
5    values: Vec<ListEntry<T>>,
6}
7
8#[derive(Clone, Debug)]
9struct ListEntry<T> {
10    value: Option<T>,
11    next: usize,
12    prev: usize,
13}
14
15/// Free and occupied cells are each linked into a cyclic list with one auxiliary cell.
16/// Cell #0 is on the list of free cells, element #1 is on the list of occupied cells.
17///
18impl<T> LRUList<T> {
19    const FREE: usize = 0;
20    const OCCUPIED: usize = 1;
21
22    pub(crate) fn with_capacity(capacity: usize) -> LRUList<T> {
23        let mut values = Vec::with_capacity(capacity + 2);
24        values.push(ListEntry::<T> {
25            value: None,
26            next: 0,
27            prev: 0,
28        });
29        values.push(ListEntry::<T> {
30            value: None,
31            next: 1,
32            prev: 1,
33        });
34        LRUList { values }
35    }
36
37    pub(crate) fn unlink(&mut self, index: usize) {
38        let prev = self.values[index].prev;
39        let next = self.values[index].next;
40        self.values[prev].next = next;
41        self.values[next].prev = prev;
42    }
43
44    pub(crate) fn link_after(&mut self, index: usize, prev: usize) {
45        let next = self.values[prev].next;
46        self.values[index].prev = prev;
47        self.values[index].next = next;
48        self.values[prev].next = index;
49        self.values[next].prev = index;
50    }
51
52    pub(crate) fn move_to_front(&mut self, index: usize) {
53        self.unlink(index);
54        self.link_after(index, Self::OCCUPIED);
55    }
56
57    pub(crate) fn push_front(&mut self, value: T) -> usize {
58        if self.values[Self::FREE].next == Self::FREE {
59            self.values.push(ListEntry::<T> {
60                value: None,
61                next: Self::FREE,
62                prev: Self::FREE,
63            });
64            self.values[Self::FREE].next = self.values.len() - 1;
65        }
66        let index = self.values[Self::FREE].next;
67        self.values[index].value = Some(value);
68        self.unlink(index);
69        self.link_after(index, Self::OCCUPIED);
70        index
71    }
72
73    pub(crate) fn remove(&mut self, index: usize) -> T {
74        self.unlink(index);
75        self.link_after(index, Self::FREE);
76        self.values[index].value.take().expect("invalid index")
77    }
78
79    pub(crate) fn back(&self) -> usize {
80        self.values[Self::OCCUPIED].prev
81    }
82
83    pub(crate) fn get(&self, index: usize) -> &T {
84        self.values[index].value.as_ref().expect("invalid index")
85    }
86
87    pub(crate) fn get_mut(&mut self, index: usize) -> &mut T {
88        self.values[index].value.as_mut().expect("invalid index")
89    }
90
91    pub(crate) fn set(&mut self, index: usize, value: T) -> Option<T> {
92        self.values[index].value.replace(value)
93    }
94
95    pub(crate) fn clear(&mut self) {
96        self.values.clear();
97        self.values.push(ListEntry::<T> {
98            value: None,
99            next: 0,
100            prev: 0,
101        });
102        self.values.push(ListEntry::<T> {
103            value: None,
104            next: 1,
105            prev: 1,
106        });
107    }
108
109    pub fn iter(&self) -> LRUListIterator<T> {
110        LRUListIterator::<T> {
111            list: self,
112            index: Self::OCCUPIED,
113        }
114    }
115}
116
117#[derive(Debug)]
118pub struct LRUListIterator<'a, T> {
119    list: &'a LRUList<T>,
120    index: usize,
121}
122
123impl<'a, T> Iterator for LRUListIterator<'a, T> {
124    type Item = &'a T;
125
126    fn next(&mut self) -> Option<Self::Item> {
127        let next = self.list.values[self.index].next;
128        if next == LRUList::<T>::OCCUPIED {
129            None
130        } else {
131            let value = self.list.values[next].value.as_ref();
132            self.index = next;
133            value
134        }
135    }
136}
cached/lru_list.rs

cached/
lru_list.rs
