television_utils/
cache.rs

1use rustc_hash::{FxBuildHasher, FxHashSet};
2use std::collections::{HashSet, VecDeque};
3use tracing::debug;
4
5/// A ring buffer that also keeps track of the keys it contains to avoid duplicates.
6///
7/// This serves as a backend for the preview cache.
8/// Basic idea:
9/// - When a new key is pushed, if it's already in the buffer, do nothing.
10/// - If the buffer is full, remove the oldest key and push the new key.
11///
12/// # Example
13/// ```rust
14/// use television_utils::cache::RingSet;
15///
16/// let mut ring_set = RingSet::with_capacity(3);
17/// // push 3 values into the ringset
18/// assert_eq!(ring_set.push(1), None);
19/// assert_eq!(ring_set.push(2), None);
20/// assert_eq!(ring_set.push(3), None);
21///
22/// // check that the values are in the buffer
23/// assert!(ring_set.contains(&1));
24/// assert!(ring_set.contains(&2));
25/// assert!(ring_set.contains(&3));
26///
27/// // push an existing value (should do nothing)
28/// assert_eq!(ring_set.push(1), None);
29///
30/// // entries should still be there
31/// assert!(ring_set.contains(&1));
32/// assert!(ring_set.contains(&2));
33/// assert!(ring_set.contains(&3));
34///
35/// // push a new value, should remove the oldest value (1)
36/// assert_eq!(ring_set.push(4), Some(1));
37///
38/// // 1 is no longer there but 2 and 3 remain
39/// assert!(!ring_set.contains(&1));
40/// assert!(ring_set.contains(&2));
41/// assert!(ring_set.contains(&3));
42/// assert!(ring_set.contains(&4));
43/// ```
44#[derive(Debug)]
45pub struct RingSet<T> {
46    ring_buffer: VecDeque<T>,
47    known_keys: FxHashSet<T>,
48    capacity: usize,
49}
50
51const DEFAULT_CAPACITY: usize = 20;
52
53impl<T> Default for RingSet<T>
54where
55    T: Eq + std::hash::Hash + Clone + std::fmt::Debug,
56{
57    fn default() -> Self {
58        RingSet::with_capacity(DEFAULT_CAPACITY)
59    }
60}
61
62impl<T> RingSet<T>
63where
64    T: Eq + std::hash::Hash + Clone + std::fmt::Debug,
65{
66    /// Create a new `RingSet` with the given capacity.
67    pub fn with_capacity(capacity: usize) -> Self {
68        RingSet {
69            ring_buffer: VecDeque::with_capacity(capacity),
70            known_keys: HashSet::with_capacity_and_hasher(
71                capacity,
72                FxBuildHasher,
73            ),
74            capacity,
75        }
76    }
77
78    /// Push a new item to the back of the buffer, removing the oldest item if the buffer is full.
79    /// Returns the item that was removed, if any.
80    /// If the item is already in the buffer, do nothing and return None.
81    pub fn push(&mut self, item: T) -> Option<T> {
82        // If the key is already in the buffer, do nothing
83        if self.contains(&item) {
84            debug!("Key already in ring buffer: {:?}", item);
85            return None;
86        }
87        let mut popped_key = None;
88        // If the buffer is full, remove the oldest key (e.g. pop from the front of the buffer)
89        if self.ring_buffer.len() >= self.capacity {
90            popped_key = self.pop();
91        }
92        // finally, push the new key to the back of the buffer
93        self.ring_buffer.push_back(item.clone());
94        self.known_keys.insert(item);
95        popped_key
96    }
97
98    fn pop(&mut self) -> Option<T> {
99        if let Some(item) = self.ring_buffer.pop_front() {
100            debug!("Removing key from ring buffer: {:?}", item);
101            self.known_keys.remove(&item);
102            Some(item)
103        } else {
104            None
105        }
106    }
107
108    pub fn contains(&self, key: &T) -> bool {
109        self.known_keys.contains(key)
110    }
111
112    /// Returns an iterator that goes from the back to the front of the buffer.
113    pub fn back_to_front(&self) -> impl Iterator<Item = T> {
114        self.ring_buffer.clone().into_iter().rev()
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121
122    #[test]
123    fn test_ring_set() {
124        let mut ring_set = RingSet::with_capacity(3);
125        // push 3 values into the ringset
126        assert_eq!(ring_set.push(1), None);
127        assert_eq!(ring_set.push(2), None);
128        assert_eq!(ring_set.push(3), None);
129
130        // check that the values are in the buffer
131        assert!(ring_set.contains(&1));
132        assert!(ring_set.contains(&2));
133        assert!(ring_set.contains(&3));
134
135        // push an existing value (should do nothing)
136        assert_eq!(ring_set.push(1), None);
137
138        // entries should still be there
139        assert!(ring_set.contains(&1));
140        assert!(ring_set.contains(&2));
141        assert!(ring_set.contains(&3));
142
143        // push a new value, should remove the oldest value (1)
144        assert_eq!(ring_set.push(4), Some(1));
145
146        // 1 is no longer there but 2 and 3 remain
147        assert!(!ring_set.contains(&1));
148        assert!(ring_set.contains(&2));
149        assert!(ring_set.contains(&3));
150        assert!(ring_set.contains(&4));
151
152        // push two new values, should remove 2 and 3
153        assert_eq!(ring_set.push(5), Some(2));
154        assert_eq!(ring_set.push(6), Some(3));
155
156        // 2 and 3 are no longer there but 4, 5 and 6 remain
157        assert!(!ring_set.contains(&2));
158        assert!(!ring_set.contains(&3));
159        assert!(ring_set.contains(&4));
160        assert!(ring_set.contains(&5));
161        assert!(ring_set.contains(&6));
162    }
163}
television_utils/cache.rs

television_utils/
cache.rs
