spnr_lib/
log.rs

1//! Append-only log keeping log entries in stable memory.
2//!
3//! Log entries are given an index, allowing for random read access.
4//!
5//! Internally, logs are organized in buckets so that the random read access can be made more efficiently.
6//! We can first seek to the right bucket, then seek to an index within the bucket.
7//! During writes, if the current bucket is full, a new bucket will be created to store the next entry.
8use crate::storage::*;
9use candid::CandidType;
10use serde::{Deserialize, Serialize};
11
12/// The state and configuration of the log.
13#[derive(CandidType, Serialize, Deserialize, Clone, Debug, Default)]
14pub struct LogState {
15    /// Stores the offset (starting position) to each buckets.
16    buckets: Vec<Offset>,
17    /// Number of entries in the log.
18    pub size: u64,
19    /// Number of entries in each bucket (must not be changed once initialized).
20    pub bucket_size: usize,
21    /// Max number of buckets, once reached the log is full and any writes will be rejected.
22    pub max_buckets: usize,
23    /// Next writing position in the storage.
24    pub offset: Offset,
25}
26
27/// A generic log parameterized by its storage type `S` and log entry type `T`.
28pub struct Log<'a, S, T> {
29    pub state: &'a mut LogState,
30    storage: &'a mut S,
31    element: std::marker::PhantomData<T>,
32}
33
34impl LogState {
35    /// Return an empty `LogState` with initial memory `offset`, `bucket_size` and `max_buckets` settings.
36    pub fn new(offset: Offset, bucket_size: usize, max_buckets: usize) -> Self {
37        LogState {
38            buckets: Vec::new(),
39            size: 0,
40            bucket_size,
41            max_buckets,
42            offset,
43        }
44    }
45}
46
47impl<'a, S: StorageStack, T> Log<'a, S, T> {
48    /// Return `Log` by initializing it with a [LogState] and a [StorageStack].
49    pub fn new(state: &'a mut LogState, storage: &'a mut S) -> Self {
50        Self {
51            state,
52            storage,
53            element: std::marker::PhantomData,
54        }
55    }
56
57    /// Add a new entry to the log.
58    /// Return `None` if the log is full, or storage is full.
59    pub fn push(&mut self, entry: T) -> Option<()>
60    where
61        T: candid::utils::ArgumentEncoder,
62    {
63        let state = &mut self.state;
64        let mut storage = self.storage.new_with(state.offset);
65        storage.push(entry).ok()?;
66        if state.size >= state.bucket_size as u64 * state.buckets.len() as u64 {
67            if state.buckets.len() >= state.max_buckets {
68                return None;
69            }
70            state.buckets.push(state.offset);
71        }
72        state.size += 1;
73        state.offset = storage.offset();
74        Some(())
75    }
76
77    /// Return number of entries in the log.
78    pub fn size(&self) -> u64 {
79        self.state.size
80    }
81
82    /// Look up a log entry by index.
83    /// Return `None` if the index is out of range, or it fails to read the entry.
84    pub fn get(&self, index: u64) -> Option<T>
85    where
86        T: for<'de> candid::utils::ArgumentDecoder<'de>,
87    {
88        let state = &self.state;
89        if index >= state.size {
90            return None;
91        }
92        let i = (index / state.bucket_size as u64) as usize;
93        assert!(i < state.buckets.len());
94        let mut n;
95        let offset;
96        if i == state.buckets.len() - 1 {
97            n = state.size;
98            offset = self.state.offset;
99        } else {
100            n = ((i + 1) * state.bucket_size) as u64;
101            offset = state.buckets[i + 1];
102        }
103        let mut storage = self.storage.new_with(offset);
104        while n > index + 1 {
105            storage.seek_prev().ok()?;
106            n -= 1;
107        }
108        storage.pop().ok()
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use super::*;
115    use crate::storage::test::Stack;
116
117    #[test]
118    fn test_log_int() {
119        let mut state: LogState = LogState::new(0, 3, 0);
120        let mut stack = Stack::default();
121        let mut log: Log<Stack, (u8,)> = Log::new(&mut state, &mut stack);
122        assert_eq!(log.size(), 0);
123        assert!(log.push((0,)).is_none());
124        assert!(log.get(0).is_none());
125
126        let mut state: LogState = LogState::new(0, 4, 2);
127        let mut stack = Stack::default();
128        let mut log: Log<Stack, (u8,)> = Log::new(&mut state, &mut stack);
129        for i in 0..8 {
130            assert!(log.push((i,)).is_some());
131            assert_eq!(log.get(i as u64), Some((i,)));
132        }
133        assert_eq!(log.size(), 8);
134        for i in 0..8 {
135            assert_eq!(log.get(i as u64), Some((i,)));
136        }
137        assert_eq!(log.size(), 8);
138        assert!(log.push((0,)).is_none());
139    }
140
141    #[test]
142    fn test_log_str() {
143        let mut state: LogState = LogState::new(0, 4, 100);
144        let mut stack = Stack::default();
145        let mut log: Log<Stack, (String,)> = Log::new(&mut state, &mut stack);
146        for i in 0..108 {
147            assert!(log.push((format!("{}", i),)).is_some());
148        }
149        assert_eq!(log.size(), 108);
150        for i in 0..108 {
151            assert_eq!(log.get(i as u64), Some((format!("{}", i),)));
152        }
153        assert_eq!(log.size(), 108);
154    }
155}
spnr_lib/log.rs

spnr_lib/
log.rs
