blob: 8e4c7371938d336f645b9fc1fae4f930d9eaf001 (
plain) (
blame)
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
|
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
//! A simple LRU cache.
#![deny(missing_docs)]
extern crate arraydeque;
use self::arraydeque::Array;
use self::arraydeque::ArrayDeque;
/// A LRU cache used to store a set of at most `n` elements at the same time.
///
/// The most-recently-used entry is at index zero.
pub struct LRUCache <K: Array>{
entries: ArrayDeque<K>,
}
/// A iterator over the items of the LRU cache.
pub type LRUCacheIterator<'a, K> = arraydeque::Iter<'a, K>;
/// A iterator over the mutable items of the LRU cache.
pub type LRUCacheMutIterator<'a, K> = arraydeque::IterMut<'a, K>;
impl<K: Array> LRUCache<K> {
/// Create a new LRU cache with `size` elements at most.
pub fn new() -> Self {
LRUCache {
entries: ArrayDeque::new(),
}
}
/// Returns the number of elements in the cache.
pub fn num_entries(&self) -> usize {
self.entries.len()
}
#[inline]
/// Touch a given entry, putting it first in the list.
pub fn touch(&mut self, pos: usize) {
let last_index = self.entries.len() - 1;
if pos != last_index {
let entry = self.entries.remove(pos).unwrap();
self.entries.push_front(entry);
}
}
/// Iterate over the contents of this cache, from more to less recently
/// used.
pub fn iter(&self) -> arraydeque::Iter<K::Item> {
self.entries.iter()
}
/// Iterate mutably over the contents of this cache.
pub fn iter_mut(&mut self) -> arraydeque::IterMut<K::Item> {
self.entries.iter_mut()
}
/// Insert a given key in the cache.
pub fn insert(&mut self, key: K::Item) {
if self.entries.len() == self.entries.capacity() {
self.entries.pop_back();
}
self.entries.push_front(key);
debug_assert!(self.entries.len() <= self.entries.capacity());
}
/// Evict all elements from the cache.
pub fn evict_all(&mut self) {
self.entries.clear();
}
}
|
