const-lru 1.0.0

A simple no_std, non-hashing, constant-capacity, constant-memory-usage LRU cache.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

use num_traits::{PrimInt, Unsigned};

use crate::ConstLru;

use super::double_ended_iter_cursors::DoubleEndedIterCursors;

/// Iterates through the keys and values of the `ConstLru` from most-recently-used to least-recently-used, consuming the `ConstLru`
///
/// Does not change the LRU order of the elements.
pub struct IntoIter<K, V, const CAP: usize, I: PrimInt + Unsigned> {
    cursors: DoubleEndedIterCursors<I, CAP>,
    const_lru: ConstLru<K, V, CAP, I>,
}

impl<K, V, const CAP: usize, I: PrimInt + Unsigned> IntoIter<K, V, CAP, I> {
    pub fn new(const_lru: ConstLru<K, V, CAP, I>) -> Self {
        let cursors = DoubleEndedIterCursors::new(&const_lru);
        Self { cursors, const_lru }
    }

    fn get_entry(&mut self, i: usize) -> (K, V) {
        let key = unsafe { self.const_lru.keys[i].assume_init_read() };
        let val = unsafe { self.const_lru.values[i].assume_init_read() };
        (key, val)
    }
}

impl<K, V, const CAP: usize, I: PrimInt + Unsigned> Iterator for IntoIter<K, V, CAP, I> {
    type Item = (K, V);

    fn next(&mut self) -> Option<Self::Item> {
        if self.cursors.has_ended() {
            return None;
        }
        // consume then increment
        let i = self.cursors.get_from_head_idx();
        self.cursors.advance_from_head(&self.const_lru);
        // get_entry copies out (k, v),
        // we need to truncate the const_lru so that they dont get dropped again
        // when const_lru drops
        self.const_lru.head = self.cursors.get_from_head();
        self.const_lru.len = self.const_lru.len - I::one();
        Some(self.get_entry(i))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let l = self.const_lru.len.to_usize().unwrap();
        (l, Some(l))
    }
}

// TODO: look into https://doc.rust-lang.org/std/iter/trait.TrustedLen.html when it lands in stable
impl<K, V, const CAP: usize, I: PrimInt + Unsigned> ExactSizeIterator for IntoIter<K, V, CAP, I> {}

impl<K, V, const CAP: usize, I: PrimInt + Unsigned> DoubleEndedIterator for IntoIter<K, V, CAP, I> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.cursors.has_ended() {
            return None;
        }
        // decrement then consume
        self.cursors.retreat_from_tail(&self.const_lru);
        let i = self.cursors.get_from_tail_idx();
        // get_entry copies out (k, v),
        // we need to truncate the const_lru so that they dont get dropped again
        // when const_lru drops

        // index safety: from_tail is < CAP so prevs[i] wont panic
        // but might = CAP, but in that case len = 0 so mustve ended
        self.const_lru.tail = self.const_lru.prevs[i];
        self.const_lru.len = self.const_lru.len - I::one();
        Some(self.get_entry(i))
    }
}