Skip to content

web search done right

4.2 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2023 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
use std::{
    collections::{HashMap, VecDeque},
    hash::Hash,
    time::{Duration, SystemTime},
};

pub struct TTLCache<K, V> {
    ttl: Duration,
    data: HashMap<K, V>,
    insertion_order: VecDeque<K>,
    insertion_times: HashMap<K, SystemTime>,
    max_size: Option<usize>,
}

impl<K: Hash + Eq + Clone, V> TTLCache<K, V> {
    pub fn with_ttl(ttl: Duration) -> Self {
        Self::with_ttl_and_max_size(ttl, None)
    }
    pub fn with_ttl_and_max_size(ttl: Duration, max_size: Option<usize>) -> Self {
        Self {
            ttl,
            data: HashMap::new(),
            insertion_order: VecDeque::new(),
            insertion_times: HashMap::new(),
            max_size,
        }
    }

    pub fn insert(&mut self, key: K, val: V) {
        self.prune_old_entries();
        let current_time = SystemTime::now();

        if self.data.insert(key.clone(), val).is_some() {
            let (idx, _) = self
                .insertion_order
                .iter()
                .enumerate()
                .find(|(_, k)| *k == &key)
                .unwrap();

            self.insertion_order.remove(idx);
        }

        self.insertion_times.insert(key.clone(), current_time);
        self.insertion_order.push_back(key);
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        let current_time = SystemTime::now();

        self.insertion_times.get(key).and_then(|insertion_time| {
            if current_time.duration_since(*insertion_time).unwrap() < self.ttl {
                self.data.get(key)
            } else {
                None
            }
        })
    }

    fn prune_old_entries(&mut self) {
        let current_time = SystemTime::now();

        if let Some(max_size) = self.max_size {
            while self.data.len() >= max_size {
                let front = self.insertion_order.pop_front().unwrap();
                self.insertion_times.remove(&front);
                self.data.remove(&front);
            }
        }

        while let Some(front) = self.insertion_order.front() {
            if current_time
                .duration_since(*self.insertion_times.get(front).unwrap())
                .unwrap()
                <= self.ttl
            {
                break;
            }

            let front = self.insertion_order.pop_front().unwrap();
            self.insertion_times.remove(&front);
            self.data.remove(&front);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn simple() {
        let mut cache = TTLCache::with_ttl_and_max_size(Duration::from_millis(500), None);

        cache.insert(0, 0);
        std::thread::sleep(Duration::from_millis(250));
        cache.insert(1, 1);

        assert_eq!(cache.get(&0), Some(&0));
        assert_eq!(cache.get(&1), Some(&1));

        std::thread::sleep(Duration::from_millis(300));

        assert_eq!(cache.get(&0), None);
        assert_eq!(cache.get(&1), Some(&1));

        std::thread::sleep(Duration::from_millis(300));

        assert_eq!(cache.get(&0), None);
        assert_eq!(cache.get(&1), None);

        cache.insert(2, 2);

        assert_eq!(cache.data.len(), 1);
        assert_eq!(cache.insertion_order.len(), 1);
        assert_eq!(cache.insertion_times.len(), 1);
    }

    #[test]
    fn max_size() {
        let mut cache = TTLCache::with_ttl_and_max_size(Duration::from_millis(50), Some(1));

        cache.insert(0, 0);
        cache.insert(1, 1);

        assert_eq!(cache.get(&0), None);
        assert_eq!(cache.get(&1), Some(&1));
    }
}