sequential_storage/cache/
key_pointers.rs

1//! Implementation of key caching
2
3#[cfg(feature = "alloc")]
4extern crate alloc;
5
6use core::{fmt::Debug, num::NonZeroU32};
7
8use crate::map::Key;
9
10pub(crate) trait SealedKeyPointersCache<KEY> {
11    fn key_location(&self, key: &KEY) -> Option<u32>;
12
13    fn notice_key_location(&mut self, key: &KEY, item_address: u32);
14    fn notice_key_erased(&mut self, key: &KEY);
15
16    fn invalidate_cache_state(&mut self);
17}
18
19/// A cache that caches pointers to keys
20#[allow(private_bounds)]
21pub trait KeyPointersCache<KEY>: SealedKeyPointersCache<KEY> {}
22
23/// A cache that stores keys in an array.
24/// The array may be smaller than the amount of keys, but that will reduce performance.
25#[derive(Debug)]
26#[cfg_attr(feature = "defmt", derive(defmt::Format))]
27pub struct ArrayKeyPointers<KEY: Key, const KEYS: usize> {
28    key_pointers: [Option<(KEY, NonZeroU32)>; KEYS],
29}
30
31impl<const KEYS: usize, KEY: Key> ArrayKeyPointers<KEY, KEYS> {
32    /// Create a new empty cache
33    pub const fn new() -> Self {
34        Self {
35            key_pointers: [const { None }; _],
36        }
37    }
38
39    fn as_tracked(&mut self) -> TrackedKeyPointers<'_, KEY> {
40        TrackedKeyPointers {
41            key_pointers: &mut self.key_pointers,
42        }
43    }
44}
45
46impl<const KEYS: usize, KEY: Key> Default for ArrayKeyPointers<KEY, KEYS> {
47    fn default() -> Self {
48        Self::new()
49    }
50}
51
52impl<const KEYS: usize, KEY: Key> SealedKeyPointersCache<KEY> for ArrayKeyPointers<KEY, KEYS> {
53    fn key_location(&self, key: &KEY) -> Option<u32> {
54        self.key_pointers
55            .iter()
56            .flatten()
57            .find(|(iter_key, _)| key == iter_key)
58            .map(|(_, pointer)| pointer.get())
59    }
60
61    fn notice_key_location(&mut self, key: &KEY, item_address: u32) {
62        self.as_tracked().notice_key_location(key, item_address);
63    }
64
65    fn notice_key_erased(&mut self, key: &KEY) {
66        self.as_tracked().notice_key_erased(key);
67    }
68
69    fn invalidate_cache_state(&mut self) {
70        self.as_tracked().invalidate_cache_state();
71    }
72}
73impl<const KEYS: usize, KEY: Key> KeyPointersCache<KEY> for ArrayKeyPointers<KEY, KEYS> {}
74
75#[cfg(feature = "alloc")]
76/// A cache that stores keys in a vec.
77/// The vec may be smaller than the amount of keys, but that will reduce performance.
78#[derive(Debug)]
79#[cfg_attr(feature = "defmt", derive(defmt::Format))]
80pub struct HeapKeyPointers<KEY: Key> {
81    key_pointers: alloc::vec::Vec<Option<(KEY, NonZeroU32)>>,
82}
83
84#[cfg(feature = "alloc")]
85impl<KEY: Key> HeapKeyPointers<KEY> {
86    /// Create a new empty cache for the given amount of keys
87    pub fn new(keys: usize) -> Self {
88        Self {
89            key_pointers: alloc::vec![None; keys],
90        }
91    }
92
93    fn as_tracked(&mut self) -> TrackedKeyPointers<'_, KEY> {
94        TrackedKeyPointers {
95            key_pointers: &mut self.key_pointers,
96        }
97    }
98}
99
100#[cfg(feature = "alloc")]
101impl<KEY: Key> SealedKeyPointersCache<KEY> for HeapKeyPointers<KEY> {
102    fn key_location(&self, key: &KEY) -> Option<u32> {
103        self.key_pointers
104            .iter()
105            .flatten()
106            .find(|(iter_key, _)| key == iter_key)
107            .map(|(_, pointer)| pointer.get())
108    }
109
110    fn notice_key_location(&mut self, key: &KEY, item_address: u32) {
111        self.as_tracked().notice_key_location(key, item_address);
112    }
113
114    fn notice_key_erased(&mut self, key: &KEY) {
115        self.as_tracked().notice_key_erased(key);
116    }
117
118    fn invalidate_cache_state(&mut self) {
119        self.as_tracked().invalidate_cache_state();
120    }
121}
122#[cfg(feature = "alloc")]
123impl<KEY: Key> KeyPointersCache<KEY> for HeapKeyPointers<KEY> {}
124
125#[derive(Debug)]
126#[cfg_attr(feature = "defmt", derive(defmt::Format))]
127pub(crate) struct TrackedKeyPointers<'a, KEY: Eq> {
128    key_pointers: &'a mut [Option<(KEY, NonZeroU32)>],
129}
130
131impl<'a, KEY: Eq> TrackedKeyPointers<'a, KEY> {
132    fn insert_front(&mut self, value: (KEY, NonZeroU32)) {
133        let len = self.key_pointers.len();
134        self.key_pointers[len - 1] = Some(value);
135        move_to_front(self.key_pointers, len - 1);
136    }
137}
138
139impl<KEY: Key> SealedKeyPointersCache<KEY> for TrackedKeyPointers<'_, KEY> {
140    fn key_location(&self, key: &KEY) -> Option<u32> {
141        self.key_pointers
142            .iter()
143            .flatten()
144            .find(|(iter_key, _)| key == iter_key)
145            .map(|(_, pointer)| pointer.get())
146    }
147
148    fn notice_key_location(&mut self, key: &KEY, item_address: u32) {
149        let existing_pointer = self
150            .key_pointers
151            .iter_mut()
152            .enumerate()
153            .filter_map(|(index, val)| val.as_mut().map(|(key, pointer)| (index, key, pointer)))
154            .find(|(_, iter_key, _)| key == *iter_key)
155            .map(|(index, _, pointer)| (index, pointer));
156
157        match existing_pointer {
158            Some((existing_index, pointer)) => {
159                *pointer = NonZeroU32::new(item_address).unwrap();
160                move_to_front(self.key_pointers, existing_index);
161            }
162            None => self.insert_front((key.clone(), NonZeroU32::new(item_address).unwrap())),
163        }
164    }
165
166    fn notice_key_erased(&mut self, key: &KEY) {
167        let existing_pointer = self
168            .key_pointers
169            .iter_mut()
170            .enumerate()
171            .find(|(_, val)| val.as_ref().is_some_and(|(iter_key, _)| key == iter_key));
172
173        if let Some((existing_index, val)) = existing_pointer {
174            *val = None;
175            move_to_back(self.key_pointers, existing_index);
176        }
177    }
178
179    fn invalidate_cache_state(&mut self) {
180        for pointers in self.key_pointers.iter_mut() {
181            *pointers = None;
182        }
183    }
184}
185
186fn move_to_front<T>(data: &mut [Option<T>], index: usize) {
187    debug_assert!(index < data.len());
188
189    // In an if to get rid of panic. Assert above still panics in debug builds
190    if index < data.len() {
191        data[..=index].rotate_right(1);
192    }
193}
194
195fn move_to_back<T>(data: &mut [Option<T>], index: usize) {
196    debug_assert!(index < data.len());
197
198    // In an if to get rid of panic. Assert above still panics in debug builds
199    if index < data.len() {
200        data[index..].rotate_left(1);
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::*;
207
208    #[test]
209    fn test_move_to_front() {
210        let mut array = [
211            Some("0".into()),
212            Some("1".into()),
213            Some("2".into()),
214            Some("3".into()),
215        ];
216        move_to_front::<String>(&mut array, 0);
217        assert_eq!(
218            array,
219            [
220                Some("0".into()),
221                Some("1".into()),
222                Some("2".into()),
223                Some("3".into()),
224            ]
225        );
226
227        let mut array = [
228            Some("0".into()),
229            Some("1".into()),
230            Some("2".into()),
231            Some("3".into()),
232        ];
233        move_to_front::<String>(&mut array, 1);
234        assert_eq!(
235            array,
236            [
237                Some("1".into()),
238                Some("0".into()),
239                Some("2".into()),
240                Some("3".into()),
241            ]
242        );
243
244        let mut array = [
245            Some("0".into()),
246            Some("1".into()),
247            Some("2".into()),
248            Some("3".into()),
249        ];
250        move_to_front::<String>(&mut array, 2);
251        assert_eq!(
252            array,
253            [
254                Some("2".into()),
255                Some("0".into()),
256                Some("1".into()),
257                Some("3".into()),
258            ]
259        );
260
261        let mut array = [
262            Some("0".into()),
263            Some("1".into()),
264            Some("2".into()),
265            Some("3".into()),
266        ];
267        move_to_front::<String>(&mut array, 3);
268        assert_eq!(
269            array,
270            [
271                Some("3".into()),
272                Some("0".into()),
273                Some("1".into()),
274                Some("2".into()),
275            ]
276        );
277    }
278
279    #[test]
280    fn test_move_to_back() {
281        let mut array = [
282            Some("0".into()),
283            Some("1".into()),
284            Some("2".into()),
285            Some("3".into()),
286        ];
287        move_to_back::<String>(&mut array, 0);
288        assert_eq!(
289            array,
290            [
291                Some("1".into()),
292                Some("2".into()),
293                Some("3".into()),
294                Some("0".into()),
295            ]
296        );
297
298        let mut array = [
299            Some("0".into()),
300            Some("1".into()),
301            Some("2".into()),
302            Some("3".into()),
303        ];
304        move_to_back::<String>(&mut array, 1);
305        assert_eq!(
306            array,
307            [
308                Some("0".into()),
309                Some("2".into()),
310                Some("3".into()),
311                Some("1".into()),
312            ]
313        );
314
315        let mut array = [
316            Some("0".into()),
317            Some("1".into()),
318            Some("2".into()),
319            Some("3".into()),
320        ];
321        move_to_back::<String>(&mut array, 2);
322        assert_eq!(
323            array,
324            [
325                Some("0".into()),
326                Some("1".into()),
327                Some("3".into()),
328                Some("2".into()),
329            ]
330        );
331
332        let mut array = [
333            Some("0".into()),
334            Some("1".into()),
335            Some("2".into()),
336            Some("3".into()),
337        ];
338        move_to_back::<String>(&mut array, 3);
339        assert_eq!(
340            array,
341            [
342                Some("0".into()),
343                Some("1".into()),
344                Some("2".into()),
345                Some("3".into()),
346            ]
347        );
348    }
349}
sequential_storage/cache/key_pointers.rs

sequential_storage/cache/
key_pointers.rs
