r_tool/cache/
fifo_cache.rs

1use std::collections::{HashMap, LinkedList};
2
3pub struct LRUCache<K, V> {
4    capacity: usize,
5    cache: HashMap<K, (V, usize)>,
6    order: LinkedList<K>,
7}
8
9impl<K, V> LRUCache<K, V>
10    where
11        K: Eq + std::hash::Hash + Clone,
12{
13    /// 创建一个新的LRU缓存实例。
14    ///
15    /// # 参数
16    ///
17    /// * `capacity`: usize - 缓存的容量
18    ///
19    /// 返回值：LRUCache<K, V> - 新创建的LRU缓存实例
20    pub fn new(capacity: usize) -> Self {
21        LRUCache {
22            capacity,
23            cache: HashMap::with_capacity(capacity),
24            order: LinkedList::new(),
25        }
26    }
27
28    /// 获取缓存中指定键的值，并将该键标记为最近使用。
29    ///
30    /// # 参数
31    ///
32    /// * `key`: &K - 要获取的键的引用
33    ///
34    /// 返回值：Option<&V> - 如果存在则返回对应值的引用，否则返回None
35    pub fn get(&mut self, key: &K) -> Option<&V> {
36        if let Some((value, timestamp)) = self.cache.get_mut(key) {
37            // 更新时间戳
38            *timestamp = self.order.len();
39            // 将键移动到顺序列表的末尾（最近使用）
40            let popped_key = self.order.pop_front().unwrap();
41            self.order.push_back(popped_key);
42            Some(value)
43        } else {
44            None
45        }
46    }
47
48    /// 将键值对插入缓存中，如果缓存已满则淘汰最久未使用的项。
49    ///
50    /// # 参数
51    ///
52    /// * `key`: K - 要插入的键
53    /// * `value`: V - 要插入的值
54    pub fn put(&mut self, key: K, value: V) {
55        if self.cache.len() >= self.capacity {
56            // 淘汰最久未使用的项
57            if let Some(oldest_key) = self.order.pop_front() {
58                self.cache.remove(&oldest_key);
59            }
60        }
61
62        // 插入新项
63        let timestamp = self.order.len();
64        self.cache.insert(key.clone(), (value, timestamp));
65        // 将键移动到顺序列表的末尾（最近使用）
66        self.order.push_back(key);
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_lru_cache() {
76        let mut lru_cache = LRUCache::new(3);
77
78        // 插入项
79        lru_cache.put("one", 1);
80        lru_cache.put("two", 2);
81        lru_cache.put("three", 3);
82
83        // 访问一项以使其成为最近使用的项
84        assert_eq!(lru_cache.get(&"one"), Some(&1));
85
86        // 插入新项，淘汰最久未使用的项（"two"）
87        lru_cache.put("four", 4);
88
89        // 检查缓存的状态
90        assert_eq!(lru_cache.cache.len(), 3);
91        assert_eq!(lru_cache.get(&"one"), Some(&1));
92        assert_eq!(lru_cache.get(&"two"), None); // "two" 应该被淘汰
93        assert_eq!(lru_cache.get(&"three"), Some(&3));
94        assert_eq!(lru_cache.get(&"four"), Some(&4));
95    }
96}
r_tool/cache/fifo_cache.rs

r_tool/cache/
fifo_cache.rs
