use crate::host::clock::Clock;
use std::cell::Cell;
use std::collections::{HashMap, HashSet};
use std::rc::Rc;
use std::time::{Duration, SystemTime};
pub struct InMemoryCache<V: Clone + Copy> {
lock_version_map: HashMap<String, Entry<V>>,
clock: Rc<dyn Clock>,
expiration_period: Duration,
start_time: Cell<SystemTime>,
}
impl<V: Clone + Copy> InMemoryCache<V> {
pub fn new(clock: Rc<dyn Clock>, expiration_period: Duration) -> Self {
let now = clock.get_current_time();
Self {
lock_version_map: HashMap::new(),
clock,
expiration_period,
start_time: Cell::new(now),
}
}
pub fn save(&mut self, key: String, value: V) {
let now = self.clock.get_current_time();
let entry = Entry::new(value, now);
self.lock_version_map.insert(key, entry);
if let Ok(duration) = now.duration_since(self.start_time.get()) {
if duration > self.expiration_period {
self.expire_entries(now);
let offset = duration.as_millis() % self.expiration_period.as_millis();
let temp = self.start_time.get() + duration;
let new_time = temp - Duration::from_millis(offset as u64);
self.start_time.replace(new_time);
}
};
}
pub fn get(&self, key: &str) -> Option<V> {
let result = self.lock_version_map.get(key);
result.map(|entry| entry.value)
}
pub fn remove(&mut self, key: &str) {
self.lock_version_map.remove(key);
}
#[allow(dead_code)]
pub fn is_empty(&self) -> bool {
self.lock_version_map.is_empty()
}
#[allow(dead_code)]
pub fn expire_by_time(&mut self) -> HashSet<String> {
let now = self.clock.get_current_time();
self.expire_entries(now)
}
#[allow(dead_code)]
pub fn length(&self) -> usize {
self.lock_version_map.len()
}
fn expire_entries(&mut self, now: SystemTime) -> HashSet<String> {
let mut expired_keys = HashSet::new();
let expiration_period = self.get_expiration_period();
self.lock_version_map.retain(|key, value| {
let time_difference = now.duration_since(value.time).unwrap_or_default();
if time_difference > expiration_period {
expired_keys.insert(key.clone());
false
} else {
true
}
});
expired_keys
}
fn get_expiration_period(&self) -> Duration {
self.expiration_period
}
}
struct Entry<V: Clone + Copy> {
value: V,
time: SystemTime,
}
impl<V: Clone + Copy> Entry<V> {
pub fn new(value: V, time: SystemTime) -> Self {
Self { value, time }
}
}
#[cfg(test)]
mod test {
use super::InMemoryCache;
use crate::host::clock::TimeUnit;
use mockall::{mock, Sequence};
use oorandom::Rand64;
use std::cell::Cell;
use std::collections::{HashMap, HashSet};
use std::ops::{Add, Range};
use std::rc::Rc;
use std::time::{Duration, SystemTime, UNIX_EPOCH};
mock! {
pub Clock {}
impl crate::host::clock::Clock for Clock {
fn get_current_time(&self) -> SystemTime;
fn get_current_time_unit(&self, unit:TimeUnit) ->u128;
}
}
#[test]
fn save_without_reach_expiration_time() {
let mut mock_clock = MockClock::new();
let max_values: usize = 50;
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(SystemTime::now());
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
fill_cache(&mut cache, max_values);
assert!(!cache.is_empty());
assert_eq!(50, cache.length());
}
#[test]
fn save_reaching_expiration_time() {
let now = SystemTime::now();
let now_plus_five_seconds = now.add(Duration::new(5, 0));
let now_plus_thirty_seconds = now.add(Duration::new(30, 0));
let now_plus_fifty_seconds = now.add(Duration::new(50, 0));
let now_plus_five_plus_sixty = now_plus_five_seconds.add(Duration::new(61, 0));
let now_plus_thirty_plus_sixty = now_plus_thirty_seconds.add(Duration::new(61, 0));
let now_plus_five_minutes = now.add(Duration::new(300, 0));
let mut mock_clock = MockClock::new();
let max_values: usize = 50;
let mut seq = Sequence::new();
mock_clock
.expect_get_current_time()
.times(10)
.return_const(now_plus_five_seconds)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(30)
.return_const(now_plus_thirty_seconds)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(10)
.return_const(now_plus_fifty_seconds)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_five_plus_sixty)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_thirty_plus_sixty)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_five_minutes)
.in_sequence(&mut seq);
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(now),
};
fill_cache(&mut cache, max_values);
cache.save(String::from("extra"), 10);
assert!(!cache.is_empty());
assert_eq!(41, cache.length());
cache.save(String::from("extra2"), 10);
assert!(!cache.is_empty());
assert_eq!(42, cache.length());
cache.save(String::from("extra3"), 10);
assert!(!cache.is_empty());
assert_eq!(1, cache.length());
}
#[test]
fn save_without_reach_any_expiration() {
let mut mock_clock = MockClock::new();
let max_values: usize = 50;
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(SystemTime::now());
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
fill_cache(&mut cache, max_values);
assert!(!cache.is_empty());
assert_eq!(50, cache.length());
}
#[test]
fn save_starting_with_empty_and_finishing_with_empty() {
let mut mock_clock = MockClock::new();
let now = SystemTime::now();
let now_plus_thirty_one = now.add(Duration::new(31, 0));
let max_values: usize = 50;
let mut seq = Sequence::new();
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(now)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_thirty_one)
.in_sequence(&mut seq);
let expiration_period = Duration::new(30, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(now),
};
assert!(cache.is_empty());
fill_cache(&mut cache, max_values);
assert!(!cache.is_empty());
assert_eq!(50, cache.length());
cache.save(String::from("extra1"), 10);
assert!(!cache.is_empty());
assert_eq!(1, cache.length());
cache.remove("extra1");
assert!(cache.is_empty())
}
#[test]
fn update_entry_without_reach_expiration_time() {
let mut mock_clock = MockClock::new();
let now = SystemTime::now();
let now_plus_thirty = now.add(Duration::new(30, 0));
let now_plus_thirty_five = now.add(Duration::new(35, 0));
let max_values: usize = 10;
let mut seq = Sequence::new();
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(now)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_thirty)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_thirty_five)
.in_sequence(&mut seq);
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
fill_cache(&mut cache, max_values);
cache.save(String::from("extra1"), 10);
assert_eq!(11, cache.length());
cache.save(String::from("extra1"), 15);
assert_eq!(11, cache.length());
}
#[test]
fn update_entry_reaching_expiration_time() {
let mut mock_clock = MockClock::new();
let now = SystemTime::now();
let now_plus_thirty = now.add(Duration::new(30, 0));
let now_plus_sixty_five = now.add(Duration::new(65, 0));
let max_values: usize = 10;
let mut seq = Sequence::new();
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(now)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_thirty)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(now_plus_sixty_five)
.in_sequence(&mut seq);
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
fill_cache(&mut cache, max_values);
cache.save(String::from("extra1"), 10);
assert_eq!(11, cache.length());
cache.save(String::from("extra1"), 15);
assert_eq!(1, cache.length());
}
#[test]
fn remove_values() {
let mut mock_clock = MockClock::new();
let max_values: usize = 50;
let values_to_remove: usize = 15;
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(SystemTime::now());
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
let keys = fill_cache(&mut cache, max_values);
remove_from_cache(&mut cache, values_to_remove, &keys);
assert!(!cache.is_empty());
assert_eq!(max_values - values_to_remove, cache.length());
}
#[test]
fn get_values() {
let mut mock_clock = MockClock::new();
let max_values: usize = 50;
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(SystemTime::now());
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
let keys = fill_cache(&mut cache, max_values);
assert!(!cache.is_empty());
assert_values_existence(&cache, max_values, &keys);
}
#[test]
fn expire_entries() {
let mut mock_clock = MockClock::new();
let max_values: usize = 50;
let now = SystemTime::now();
let expiration_time = now.add(Duration::new(61, 0));
let mut seq = Sequence::new();
mock_clock
.expect_get_current_time()
.times(max_values)
.return_const(now)
.in_sequence(&mut seq);
mock_clock
.expect_get_current_time()
.times(1)
.return_const(expiration_time)
.in_sequence(&mut seq);
let expiration_period = Duration::new(60, 0);
let mut cache = InMemoryCache {
lock_version_map: HashMap::new(),
clock: Rc::new(mock_clock),
expiration_period,
start_time: Cell::new(SystemTime::now()),
};
let keys = fill_cache(&mut cache, max_values);
let deleted_keys = cache.expire_by_time();
assert!(cache.is_empty());
assert_eq!(keys, deleted_keys);
}
fn fill_cache(cache: &mut InMemoryCache<u64>, max_values: usize) -> HashSet<String> {
let mut set: HashSet<String> = HashSet::new();
let seed = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap()
.as_nanos();
let mut rand = Rand64::new(seed);
for _n in 1..=max_values {
let value = rand.rand_range(Range {
start: 1,
end: 1001,
});
let key = (value as u128)
+ SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap()
.as_nanos();
cache.save(key.to_string(), value);
set.insert(key.to_string());
}
set
}
fn remove_from_cache(
cache: &mut InMemoryCache<u64>,
max_removed: usize,
keys: &HashSet<String>,
) {
let mut iterator = keys.iter();
for _n in 1..=max_removed {
let key = iterator.next().unwrap();
cache.remove(key);
}
}
fn assert_values_existence(
cache: &InMemoryCache<u64>,
max_values: usize,
keys: &HashSet<String>,
) {
let mut iterator = keys.iter();
for _n in 1..=max_values {
assert!(cache.get(iterator.next().unwrap()).is_some())
}
}
}