Skip to main content

lru_slab/
lib.rs

1//! Pre-allocated storage with constant-time LRU tracking
2
3#![warn(missing_docs)]
4#![no_std]
5
6extern crate alloc;
7
8use alloc::boxed::Box;
9use core::{fmt, iter::FusedIterator, marker::PhantomData, ptr::addr_of_mut};
10
11/// A random-access table that maintains an LRU list in constant time
12#[derive(Clone)]
13pub struct LruSlab<T> {
14    slots: Box<[Slot<T>]>,
15    /// Most recently used
16    head: u32,
17    /// Least recently used
18    tail: u32,
19    /// First unused
20    free: u32,
21    /// Number of occupied slots
22    len: u32,
23}
24
25impl<T> LruSlab<T> {
26    /// Create an empty [`LruSlab`]
27    pub fn new() -> Self {
28        Self::with_capacity(0)
29    }
30
31    /// Create an [`LruSlab`] that can store at least `capacity` elements without reallocating
32    pub fn with_capacity(capacity: u32) -> Self {
33        assert!(capacity != u32::MAX, "capacity too large");
34        Self {
35            slots: (0..capacity)
36                .map(|n| Slot {
37                    value: None,
38                    prev: NONE,
39                    next: if n + 1 == capacity { NONE } else { n + 1 },
40                })
41                .collect(),
42            head: NONE,
43            tail: NONE,
44            free: if capacity == 0 { NONE } else { 0 },
45            len: 0,
46        }
47    }
48
49    /// Whether no elements are stored
50    pub fn is_empty(&self) -> bool {
51        self.len == 0
52    }
53
54    /// Number of elements stored
55    pub fn len(&self) -> u32 {
56        self.len
57    }
58
59    /// Number of elements that can be stored without reallocating
60    pub fn capacity(&self) -> u32 {
61        self.slots.len() as u32
62    }
63
64    /// The slot that will be returned by the next call to `insert`, unless `remove` is called first
65    pub fn vacant_key(&self) -> u32 {
66        match self.free {
67            NONE => self.capacity(),
68            _ => self.free,
69        }
70    }
71
72    /// Insert a value, returning the slot it was stored in
73    ///
74    /// The returned slot is marked as the most recently used.
75    pub fn insert(&mut self, value: T) -> u32 {
76        let id = match self.alloc() {
77            Some(id) => id,
78            None => {
79                let len = self.capacity();
80                // Ensure `NONE` never becomes a real slot index
81                let cap = 2u32.saturating_mul(len.max(2)).min(u32::MAX - 1);
82                if cap == len {
83                    panic!("cannot store more than 2^32-2 elements");
84                }
85                self.slots = self
86                    .slots
87                    .iter_mut()
88                    .map(|x| Slot {
89                        value: x.value.take(),
90                        next: x.next,
91                        prev: x.prev,
92                    })
93                    .chain((len..cap).map(|n| Slot {
94                        value: None,
95                        prev: NONE,
96                        next: if n + 1 == cap { NONE } else { n + 1 },
97                    }))
98                    .collect();
99                self.free = len + 1;
100                len
101            }
102        };
103        let idx = id as usize;
104
105        debug_assert!(self.slots[idx].value.is_none(), "corrupt free list");
106        self.slots[idx].value = Some(value);
107        self.link_at_head(id);
108        self.len += 1;
109
110        id
111    }
112
113    /// Get the least recently used slot, if any
114    pub fn lru(&self) -> Option<u32> {
115        if self.tail == NONE {
116            debug_assert_eq!(self.head, NONE);
117            None
118        } else {
119            Some(self.tail)
120        }
121    }
122
123    /// Remove the element stored in `slot`, returning it
124    pub fn remove(&mut self, slot: u32) -> T {
125        let value = self.slots[slot as usize]
126            .value
127            .take()
128            .expect("removing empty slot");
129        self.unlink(slot);
130        self.slots[slot as usize].next = self.free;
131        self.slots[slot as usize].prev = NONE;
132        self.free = slot;
133        self.len -= 1;
134        value
135    }
136
137    /// Mark `slot` as the most recently used and access it uniquely
138    pub fn get_mut(&mut self, slot: u32) -> &mut T {
139        self.freshen(slot);
140        self.peek_mut(slot)
141    }
142
143    /// Access `slot` without marking it as most recently used
144    pub fn peek(&self, slot: u32) -> &T {
145        self.slots[slot as usize].value.as_ref().unwrap()
146    }
147
148    /// Access `slot` uniquely without marking it as most recently used
149    pub fn peek_mut(&mut self, slot: u32) -> &mut T {
150        self.slots[slot as usize].value.as_mut().unwrap()
151    }
152
153    /// Walk the container from most to least recently used
154    pub fn iter(&self) -> Iter<'_, T> {
155        let state = IterState::new(self);
156        Iter {
157            slots: &self.slots[..],
158            state,
159        }
160    }
161
162    /// Walk the container from most to least recently used
163    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
164        let state = IterState::new(self);
165        IterMut {
166            slots: self.slots[..].as_mut_ptr().cast(),
167            state,
168            _marker: PhantomData,
169        }
170    }
171
172    /// Remove a slot from the freelist
173    fn alloc(&mut self) -> Option<u32> {
174        if self.free == NONE {
175            return None;
176        }
177        let slot = self.free;
178        self.free = self.slots[slot as usize].next;
179        Some(slot)
180    }
181
182    /// Mark `slot` as the most recently used
183    fn freshen(&mut self, slot: u32) {
184        if self.slots[slot as usize].prev == NONE {
185            // This is already the freshest slot, so we don't need to do anything
186            debug_assert_eq!(self.head, slot, "corrupt LRU list");
187            return;
188        }
189
190        self.unlink(slot);
191        self.link_at_head(slot);
192    }
193
194    /// Add a link to the head of the list
195    fn link_at_head(&mut self, slot: u32) {
196        let idx = slot as usize;
197        if self.head == NONE {
198            // List was empty
199            self.slots[idx].next = NONE;
200            self.tail = slot;
201        } else {
202            self.slots[idx].next = self.head;
203            self.slots[self.head as usize].prev = slot;
204        }
205        self.slots[idx].prev = NONE;
206        self.head = slot;
207    }
208
209    /// Remove a link from anywhere in the list
210    fn unlink(&mut self, slot: u32) {
211        let idx = slot as usize;
212        if self.slots[idx].prev != NONE {
213            self.slots[self.slots[idx].prev as usize].next = self.slots[idx].next;
214        } else {
215            self.head = self.slots[idx].next;
216        }
217        if self.slots[idx].next != NONE {
218            self.slots[self.slots[idx].next as usize].prev = self.slots[idx].prev;
219        } else {
220            // This was the tail
221            self.tail = self.slots[idx].prev;
222        }
223    }
224}
225
226impl<T> Default for LruSlab<T> {
227    fn default() -> Self {
228        Self::new()
229    }
230}
231
232impl<T> FromIterator<T> for LruSlab<T> {
233    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
234        let iter = iter.into_iter();
235        let mut slab = LruSlab::with_capacity(u32::try_from(iter.size_hint().0).unwrap());
236        for x in iter {
237            slab.insert(x);
238        }
239        slab
240    }
241}
242
243impl<'a, T> IntoIterator for &'a LruSlab<T> {
244    type Item = (u32, &'a T);
245
246    type IntoIter = Iter<'a, T>;
247
248    fn into_iter(self) -> Self::IntoIter {
249        self.iter()
250    }
251}
252
253impl<'a, T> IntoIterator for &'a mut LruSlab<T> {
254    type Item = (u32, &'a mut T);
255
256    type IntoIter = IterMut<'a, T>;
257
258    fn into_iter(self) -> Self::IntoIter {
259        self.iter_mut()
260    }
261}
262
263impl<T: fmt::Debug> fmt::Debug for LruSlab<T> {
264    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
265        f.debug_map().entries(self).finish()
266    }
267}
268
269#[derive(Clone)]
270struct Slot<T> {
271    value: Option<T>,
272    /// Next slot in the LRU or free list
273    next: u32,
274    /// Previous slot in the LRU list; NONE when free
275    prev: u32,
276}
277
278const NONE: u32 = u32::MAX;
279
280/// Iterator over elements of an [`LruSlab`], from most to least recently used
281pub struct Iter<'a, T> {
282    slots: &'a [Slot<T>],
283    state: IterState,
284}
285
286impl<'a, T> Iterator for Iter<'a, T> {
287    type Item = (u32, &'a T);
288    fn next(&mut self) -> Option<(u32, &'a T)> {
289        let idx = self.state.next(|i| self.slots[i as usize].next)?;
290        let result = self.slots[idx as usize]
291            .value
292            .as_ref()
293            .expect("corrupt LRU list");
294        Some((idx, result))
295    }
296
297    fn size_hint(&self) -> (usize, Option<usize>) {
298        (self.state.len as usize, Some(self.state.len as usize))
299    }
300}
301
302impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
303    fn next_back(&mut self) -> Option<(u32, &'a T)> {
304        let idx = self.state.next_back(|i| self.slots[i as usize].prev)?;
305        let result = self.slots[idx as usize]
306            .value
307            .as_ref()
308            .expect("corrupt LRU list");
309        Some((idx, result))
310    }
311}
312
313impl<T> ExactSizeIterator for Iter<'_, T> {
314    fn len(&self) -> usize {
315        self.state.len as usize
316    }
317}
318
319impl<T> FusedIterator for Iter<'_, T> {}
320
321/// Iterator over mutable elements of an [`LruSlab`], from most to least recently used
322pub struct IterMut<'a, T> {
323    slots: *mut Slot<T>,
324    state: IterState,
325    _marker: PhantomData<&'a mut [Slot<T>]>,
326}
327
328impl<'a, T> Iterator for IterMut<'a, T> {
329    type Item = (u32, &'a mut T);
330    fn next(&mut self) -> Option<(u32, &'a mut T)> {
331        // Safety: `next` returns unique in-bounds indices, and no live references overlap with any
332        // `next` field
333        unsafe {
334            let idx = self
335                .state
336                .next(|i| *addr_of_mut!((*self.slots.add(i as usize)).next))?;
337            let result = (*addr_of_mut!((*self.slots.add(idx as usize)).value))
338                .as_mut()
339                .expect("corrupt LRU list");
340            Some((idx, result))
341        }
342    }
343
344    fn size_hint(&self) -> (usize, Option<usize>) {
345        (self.state.len as usize, Some(self.state.len as usize))
346    }
347}
348
349impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
350    fn next_back(&mut self) -> Option<(u32, &'a mut T)> {
351        // Safety: `next_back` returns unique in-bounds indices, and no live references overlap with
352        // any `prev` field
353        unsafe {
354            let idx = self
355                .state
356                .next_back(|i| *addr_of_mut!((*self.slots.add(i as usize)).prev))?;
357            let result = (*addr_of_mut!((*self.slots.add(idx as usize)).value))
358                .as_mut()
359                .expect("corrupt LRU list");
360            Some((idx, result))
361        }
362    }
363}
364
365impl<T> ExactSizeIterator for IterMut<'_, T> {
366    fn len(&self) -> usize {
367        self.state.len as usize
368    }
369}
370
371impl<T> FusedIterator for IterMut<'_, T> {}
372
373struct IterState {
374    head: u32,
375    tail: u32,
376    len: u32,
377}
378
379impl IterState {
380    fn new<T>(slab: &LruSlab<T>) -> Self {
381        Self {
382            head: slab.head,
383            tail: slab.tail,
384            len: slab.len,
385        }
386    }
387
388    fn next(&mut self, get_next: impl Fn(u32) -> u32) -> Option<u32> {
389        if self.len == 0 {
390            return None;
391        }
392        let idx = self.head;
393        self.head = get_next(idx);
394        self.len -= 1;
395        Some(idx)
396    }
397
398    fn next_back(&mut self, get_prev: impl Fn(u32) -> u32) -> Option<u32> {
399        if self.len == 0 {
400            return None;
401        }
402        let idx = self.tail;
403        self.tail = get_prev(idx);
404        self.len -= 1;
405        Some(idx)
406    }
407}
408
409#[cfg(test)]
410mod tests {
411    extern crate std;
412
413    use alloc::{format, string::String, vec::Vec};
414    use self::std::panic::{catch_unwind, AssertUnwindSafe};
415
416    use super::*;
417
418    #[test]
419    fn removing_vacant_slot_preserves_state() {
420        let mut slab = [42].into_iter().collect::<LruSlab<_>>();
421        let vacant = slab.insert(0);
422        slab.remove(vacant);
423        let before = (slab.len, slab.head, slab.tail, slab.free);
424        assert!(catch_unwind(AssertUnwindSafe(|| slab.remove(vacant))).is_err());
425        assert_eq!((slab.len, slab.head, slab.tail, slab.free), before);
426    }
427
428    #[test]
429    fn lru_order() {
430        let mut cache = LruSlab::new();
431        let b = cache.insert('b');
432        assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "b");
433        let _a = cache.insert('a');
434        assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "ab");
435        let d = cache.insert('d');
436        assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "dab");
437        let c = cache.insert('c');
438        assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "cdab");
439        let e = cache.insert('e');
440        assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "ecdab");
441
442        cache.get_mut(b);
443        cache.get_mut(c);
444        cache.get_mut(d);
445        cache.get_mut(e);
446
447        assert_eq!(cache.remove(cache.lru().unwrap()), 'a');
448        assert_eq!(cache.remove(cache.lru().unwrap()), 'b');
449        assert_eq!(cache.remove(cache.lru().unwrap()), 'c');
450        assert_eq!(cache.remove(cache.lru().unwrap()), 'd');
451        assert_eq!(cache.remove(cache.lru().unwrap()), 'e');
452        assert!(cache.lru().is_none());
453    }
454
455    #[test]
456    fn slot_reuse() {
457        let mut cache = LruSlab::new();
458        let a = cache.insert('a');
459        cache.remove(a);
460        let a_prime = cache.insert('a');
461        assert_eq!(a, a_prime);
462        assert_eq!(cache.len(), 1);
463    }
464
465    #[test]
466    fn debug() {
467        let slab = ['a', 'b'].into_iter().collect::<LruSlab<_>>();
468        assert_eq!(format!("{:?}", slab), "{1: 'b', 0: 'a'}");
469    }
470
471    #[test]
472    fn iter_reverse() {
473        let slab = ['a', 'b'].into_iter().collect::<LruSlab<_>>();
474        let mut double_reversed = slab.iter().rev().collect::<Vec<_>>();
475        double_reversed.reverse();
476        assert_eq!(slab.iter().collect::<Vec<_>>(), double_reversed);
477    }
478
479    #[test]
480    fn vacant_key() {
481        let mut slab = LruSlab::new();
482        assert_eq!(slab.vacant_key(), 0);
483        slab.insert(());
484        assert_eq!(slab.vacant_key(), 1);
485        slab.remove(0);
486        assert_eq!(slab.vacant_key(), 0);
487    }
488}