backtrace/symbolize/gimli/
lru.rs

1use core::mem::{self, MaybeUninit};
2use core::ptr;
3
4/// least-recently-used cache with static size
5pub(crate) struct Lru<T, const N: usize> {
6    // SAFETY: len <= initialized values
7    len: usize,
8    arr: [MaybeUninit<T>; N],
9}
10
11impl<T, const N: usize> Default for Lru<T, N> {
12    fn default() -> Self {
13        Lru {
14            len: 0,
15            arr: [const { MaybeUninit::uninit() }; N],
16        }
17    }
18}
19
20impl<T, const N: usize> Lru<T, N> {
21    #[inline]
22    pub fn clear(&mut self) {
23        let len = self.len;
24        self.len = 0;
25        // SAFETY: we can't touch these values again due to setting self.len = 0
26        unsafe { ptr::drop_in_place(ptr::addr_of_mut!(self.arr[0..len]) as *mut [T]) }
27    }
28
29    #[inline]
30    pub fn iter(&self) -> impl Iterator<Item = &T> {
31        self.arr[0..self.len]
32            .iter()
33            // SAFETY: we only iterate initialized values due to our len invariant
34            .map(|init| unsafe { init.assume_init_ref() })
35    }
36
37    #[inline]
38    pub fn push_front(&mut self, value: T) -> Option<&mut T> {
39        if N == 0 {
40            return None;
41        } else if self.len == N {
42            self.len = N - 1;
43            // SAFETY: we maintain len invariant and bail on N == 0
44            unsafe { ptr::drop_in_place(self.arr.as_mut_ptr().cast::<T>().add(N - 1)) };
45        };
46        let len_to_init = self.len + 1;
47        let mut last = MaybeUninit::new(value);
48        for elem in self.arr[0..len_to_init].iter_mut() {
49            // OPT(size): using `mem::swap` allows surprising size regressions
50            last = mem::replace(elem, last);
51        }
52        self.len = len_to_init;
53
54        self.arr
55            .first_mut()
56            // SAFETY: we just pushed it
57            .map(|elem| unsafe { elem.assume_init_mut() })
58    }
59
60    #[inline]
61    pub fn move_to_front(&mut self, idx: usize) -> Option<&mut T> {
62        let elem = self.arr[0..self.len].get_mut(idx)?;
63        // SAFETY: we already bailed if the index is bad, so our slicing will be infallible,
64        // so it is permissible to allow the len invariant to decay, as we always restore it
65        let mut last = mem::replace(elem, MaybeUninit::uninit());
66        for elem in self.arr[0..=idx].iter_mut() {
67            // OPT(size): using `mem::swap` allows surprising size regressions
68            last = mem::replace(elem, last);
69        }
70        self.arr
71            .first_mut()
72            // SAFETY: we have restored the len invariant
73            .map(|elem| unsafe { elem.assume_init_mut() })
74    }
75}
backtrace/symbolize/gimli/lru.rs

backtrace/symbolize/gimli/
lru.rs
