spec_stream_cache/
eviction.rs1use std::collections::{HashMap, VecDeque};
7use std::time::Instant;
8
9pub trait EvictionPolicy: Send + Sync {
11 fn record_access(&mut self, seq_id: u64);
13
14 fn remove_sequence(&mut self, seq_id: u64);
16
17 fn select_eviction_candidate(&self) -> Option<u64>;
19
20 fn len(&self) -> usize;
22
23 fn is_empty(&self) -> bool {
25 self.len() == 0
26 }
27}
28
29#[derive(Debug, Default)]
31pub struct LruEvictionPolicy {
32 queue: VecDeque<u64>,
33 timestamps: HashMap<u64, Instant>,
34}
35
36impl LruEvictionPolicy {
37 pub fn new() -> Self {
38 Self {
39 queue: VecDeque::new(),
40 timestamps: HashMap::new(),
41 }
42 }
43}
44
45impl EvictionPolicy for LruEvictionPolicy {
46 fn record_access(&mut self, seq_id: u64) {
47 self.timestamps.insert(seq_id, Instant::now());
48 self.queue.retain(|&id| id != seq_id);
49 self.queue.push_back(seq_id);
50 }
51
52 fn remove_sequence(&mut self, seq_id: u64) {
53 self.timestamps.remove(&seq_id);
54 self.queue.retain(|&id| id != seq_id);
55 }
56
57 fn select_eviction_candidate(&self) -> Option<u64> {
58 self.queue.front().copied()
59 }
60
61 fn len(&self) -> usize {
62 self.queue.len()
63 }
64}
65
66#[cfg(test)]
67mod tests {
68 use super::*;
69
70 #[test]
71 fn test_lru_eviction_policy() {
72 let mut policy = LruEvictionPolicy::new();
73 policy.record_access(101);
74 policy.record_access(102);
75 policy.record_access(103);
76
77 assert_eq!(policy.select_eviction_candidate(), Some(101));
79
80 policy.record_access(101);
82 assert_eq!(policy.select_eviction_candidate(), Some(102));
83
84 policy.remove_sequence(102);
86 assert_eq!(policy.select_eviction_candidate(), Some(103));
87 }
88}