miden_node_utils/
block_cache.rs

1use std::collections::VecDeque;
2use std::num::NonZeroUsize;
3use std::sync::{Arc, RwLock};
4
5use miden_protocol::block::BlockNumber;
6
7/// A cheaply cloneable block-ordered cache.
8#[derive(Clone)]
9pub struct BlockOrderedCache<T> {
10    inner: Arc<RwLock<Inner<T>>>,
11}
12
13struct Inner<T> {
14    fifo: VecDeque<T>,
15    youngest: Option<BlockNumber>,
16    capacity: usize,
17}
18
19impl<T> BlockOrderedCache<T> {
20    /// Creates a new cache with the given capacity.
21    pub fn new(capacity: NonZeroUsize) -> Self {
22        Self {
23            inner: Arc::new(RwLock::new(Inner {
24                fifo: VecDeque::new(),
25                youngest: None,
26                capacity: capacity.get(),
27            })),
28        }
29    }
30
31    /// Pushes a new value into the cache and evicts the oldest value if the cache is full.
32    ///
33    /// # Error
34    ///
35    /// Returns the value if the provided block number is not the next in sequence.
36    pub fn push(&self, number: BlockNumber, value: T) -> Result<(), T> {
37        let mut inner = self.inner.write().expect("block cache lock poisoned");
38
39        if let Some(youngest) = inner.youngest {
40            if youngest.child() != number {
41                return Err(value);
42            }
43        }
44
45        if inner.fifo.len() >= inner.capacity {
46            inner.fifo.pop_front();
47        }
48
49        inner.fifo.push_back(value);
50        inner.youngest = Some(number);
51
52        Ok(())
53    }
54}
55
56impl<T: Clone> BlockOrderedCache<T> {
57    /// Retrieves the value associated with the given block number from the cache.
58    pub fn get(&self, number: BlockNumber) -> Option<T> {
59        let inner = self.inner.read().expect("block cache lock poisoned");
60        let youngest = inner.youngest?;
61        let distance_to_oldest = u32::try_from(inner.fifo.len().checked_sub(1)?).ok()?;
62        let oldest = youngest.checked_sub(distance_to_oldest)?;
63
64        let offset = number.checked_sub(oldest.as_u32())?;
65        inner.fifo.get(offset.as_usize()).cloned()
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use std::num::NonZeroUsize;
72
73    use super::BlockOrderedCache;
74
75    fn cache(cap: usize) -> BlockOrderedCache<&'static str> {
76        BlockOrderedCache::new(NonZeroUsize::new(cap).unwrap())
77    }
78
79    #[test]
80    fn get_returns_none_on_empty_cache() {
81        let c = cache(4);
82        assert_eq!(c.get(1.into()), None);
83    }
84
85    #[test]
86    fn get_returns_inserted_value() {
87        let c = cache(4);
88        assert_eq!(c.push(1.into(), "a"), Ok(()));
89        assert_eq!(c.get(1.into()), Some("a"));
90    }
91
92    #[test]
93    fn evicts_oldest_entry_when_full() {
94        let c = cache(2);
95        assert_eq!(c.push(5.into(), "a"), Ok(()));
96        assert_eq!(c.push(6.into(), "b"), Ok(()));
97        assert_eq!(c.push(7.into(), "c"), Ok(())); // evicts 5
98        assert_eq!(c.get(5.into()), None);
99        assert_eq!(c.get(6.into()), Some("b"));
100        assert_eq!(c.get(7.into()), Some("c"));
101    }
102
103    #[test]
104    fn overwrite_key_returns_value() {
105        let c = cache(2);
106        assert_eq!(c.push(1.into(), "a"), Ok(()));
107        assert_eq!(c.push(1.into(), "b"), Err("b"));
108        assert_eq!(c.get(1.into()), Some("a"));
109    }
110
111    #[test]
112    fn parent_returns_value() {
113        let c = cache(2);
114        assert_eq!(c.push(3.into(), "a"), Ok(()));
115        assert_eq!(c.push(2.into(), "b"), Err("b"));
116        assert_eq!(c.get(3.into()), Some("a"));
117    }
118
119    #[test]
120    fn wrong_child_returns_value() {
121        let c = cache(2);
122        assert_eq!(c.push(1.into(), "a"), Ok(()));
123        assert_eq!(c.push(3.into(), "b"), Err("b"));
124        assert_eq!(c.get(1.into()), Some("a"));
125    }
126
127    #[test]
128    fn clone_shares_state() {
129        let c1 = cache(4);
130        let c2 = c1.clone();
131        assert_eq!(c1.push(1.into(), "a"), Ok(()));
132        assert_eq!(c2.get(1.into()), Some("a"));
133    }
134}
miden_node_utils/block_cache.rs

miden_node_utils/
block_cache.rs
