use std::collections::{HashMap, VecDeque};
use std::time::Instant;
pub trait EvictionPolicy: Send + Sync {
fn record_access(&mut self, seq_id: u64);
fn remove_sequence(&mut self, seq_id: u64);
fn select_eviction_candidate(&self) -> Option<u64>;
fn len(&self) -> usize;
fn is_empty(&self) -> bool {
self.len() == 0
}
}
#[derive(Debug, Default)]
pub struct LruEvictionPolicy {
queue: VecDeque<u64>,
timestamps: HashMap<u64, Instant>,
}
impl LruEvictionPolicy {
pub fn new() -> Self {
Self {
queue: VecDeque::new(),
timestamps: HashMap::new(),
}
}
}
impl EvictionPolicy for LruEvictionPolicy {
fn record_access(&mut self, seq_id: u64) {
self.timestamps.insert(seq_id, Instant::now());
self.queue.retain(|&id| id != seq_id);
self.queue.push_back(seq_id);
}
fn remove_sequence(&mut self, seq_id: u64) {
self.timestamps.remove(&seq_id);
self.queue.retain(|&id| id != seq_id);
}
fn select_eviction_candidate(&self) -> Option<u64> {
self.queue.front().copied()
}
fn len(&self) -> usize {
self.queue.len()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_lru_eviction_policy() {
let mut policy = LruEvictionPolicy::new();
policy.record_access(101);
policy.record_access(102);
policy.record_access(103);
assert_eq!(policy.select_eviction_candidate(), Some(101));
policy.record_access(101);
assert_eq!(policy.select_eviction_candidate(), Some(102));
policy.remove_sequence(102);
assert_eq!(policy.select_eviction_candidate(), Some(103));
}
}