icydb-core 0.185.15

IcyDB — A schema-first typed query engine and persistence runtime for Internet Computer canisters
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

//! Module: db::session::bounded_cache
//! Responsibility: small bounded in-heap cache container for canister-lifetime session caches.
//! Does not own: cache key semantics, artifact compilation, or cache attribution.
//! Boundary: keeps global session caches from growing without limit.

use std::{
    collections::{HashMap, VecDeque, hash_map::Entry},
    hash::Hash,
};

///
/// BoundedCache
///
/// FIFO-bounded map used by process-global session caches. It preserves O(1)
/// key lookup while evicting the oldest inserted key when a new key would
/// exceed the configured entry budget.
///

pub(in crate::db::session) struct BoundedCache<K, V> {
    entries: HashMap<K, V>,
    insertion_order: VecDeque<K>,
    max_entries: usize,
}

impl<K, V> BoundedCache<K, V>
where
    K: Clone + Eq + Hash,
{
    pub(in crate::db::session) fn new(max_entries: usize) -> Self {
        Self {
            entries: HashMap::new(),
            insertion_order: VecDeque::new(),
            max_entries,
        }
    }

    pub(in crate::db::session) fn get(&self, key: &K) -> Option<&V> {
        self.entries.get(key)
    }

    pub(in crate::db::session) fn insert(&mut self, key: K, value: V) -> Option<V> {
        if let Entry::Occupied(mut entry) = self.entries.entry(key.clone()) {
            return Some(entry.insert(value));
        }

        self.evict_until_new_key_fits();
        self.insertion_order.push_back(key.clone());
        self.entries.insert(key, value)
    }

    #[cfg(test)]
    pub(in crate::db::session) fn clear(&mut self) {
        self.entries.clear();
        self.insertion_order.clear();
    }

    pub(in crate::db::session) fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    pub(in crate::db::session) fn len(&self) -> usize {
        self.entries.len()
    }

    pub(in crate::db::session) fn keys(&self) -> impl Iterator<Item = &K> {
        self.entries.keys()
    }

    fn evict_until_new_key_fits(&mut self) {
        if self.max_entries == 0 {
            self.entries.clear();
            self.insertion_order.clear();
            return;
        }

        while self.entries.len() >= self.max_entries {
            let Some(oldest) = self.insertion_order.pop_front() else {
                self.entries.clear();
                return;
            };
            self.entries.remove(&oldest);
        }
    }
}

impl<K, V> Default for BoundedCache<K, V>
where
    K: Clone + Eq + Hash,
{
    fn default() -> Self {
        Self::new(1024)
    }
}

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

    #[test]
    fn bounded_cache_evicts_oldest_inserted_key() {
        let mut cache = BoundedCache::new(2);

        cache.insert("a", 1);
        cache.insert("b", 2);
        cache.insert("c", 3);

        assert!(cache.get(&"a").is_none());
        assert_eq!(cache.get(&"b"), Some(&2));
        assert_eq!(cache.get(&"c"), Some(&3));
        assert_eq!(cache.len(), 2);
    }
}