tlru_cache/
queue.rs

1use std::fmt::Debug;
2use std::marker::PhantomData;
3use std::{fmt, ptr};
4
5pub type NodePtr<T> = *mut Node<T>;
6
7pub struct Node<T> {
8    pub value: T,
9    prev: NodePtr<T>,
10    next: NodePtr<T>,
11}
12
13pub struct Queue<T> {
14    head: NodePtr<T>,
15    tail: NodePtr<T>,
16    _pd: PhantomData<T>,
17}
18
19impl<T> Queue<T> {
20    pub fn new() -> Self {
21        Self {
22            head: ptr::null_mut(),
23            tail: ptr::null_mut(),
24            _pd: PhantomData,
25        }
26    }
27
28    pub fn push(&mut self, value: T) -> NodePtr<T> {
29        let new_tail = Box::into_raw(Box::new(Node {
30            value,
31            prev: ptr::null_mut(),
32            next: ptr::null_mut(),
33        }));
34        self.push_node(new_tail);
35        new_tail
36    }
37
38    pub fn push_node(&mut self, new_tail: NodePtr<T>) {
39        unsafe {
40            if !self.tail.is_null() {
41                (*self.tail).next = new_tail;
42                (*new_tail).prev = self.tail;
43            } else {
44                self.head = new_tail;
45            }
46            self.tail = new_tail;
47        }
48    }
49
50    pub fn peek(&self) -> Option<&T> {
51        unsafe { self.head.as_ref().map(|node| &node.value) }
52    }
53
54    pub fn pop_node(&mut self) -> Option<Box<Node<T>>> {
55        unsafe {
56            if self.head.is_null() {
57                None
58            } else {
59                let head = Box::from_raw(self.head);
60                self.head = head.next;
61
62                if self.head.is_null() {
63                    self.tail = ptr::null_mut();
64                }
65
66                Some(head)
67            }
68        }
69    }
70
71    pub fn remove(&mut self, elem: NodePtr<T>) {
72        unsafe {
73            if !(*elem).prev.is_null() {
74                (*(*elem).prev).next = (*elem).next;
75            }
76            if !(*elem).next.is_null() {
77                (*(*elem).next).prev = (*elem).prev;
78            }
79            if self.tail == elem {
80                self.tail = (*elem).prev;
81            }
82            if self.head == elem {
83                self.head = (*elem).next;
84            }
85            (*elem).prev = ptr::null_mut();
86            (*elem).next = ptr::null_mut();
87        }
88    }
89
90    pub fn iter(&self) -> Iter<'_, T> {
91        unsafe {
92            Iter {
93                next: self.head.as_ref(),
94            }
95        }
96    }
97}
98
99impl<T> Drop for Queue<T> {
100    fn drop(&mut self) {
101        while let Some(_) = self.pop_node() {}
102    }
103}
104
105pub struct Iter<'a, T> {
106    next: Option<&'a Node<T>>,
107}
108
109impl<'a, T> Iterator for Iter<'a, T> {
110    type Item = &'a T;
111
112    fn next(&mut self) -> Option<Self::Item> {
113        unsafe {
114            self.next.map(|node| {
115                self.next = node.next.as_ref();
116                &node.value
117            })
118        }
119    }
120}
121
122impl<T: Debug> Debug for Queue<T> {
123    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
124        f.debug_list().entries(self.iter()).finish()
125    }
126}
127
128unsafe impl<T: Send> Send for Queue<T> {}
129unsafe impl<T: Sync> Sync for Queue<T> {}
130
131#[cfg(test)]
132mod test {
133    use super::Queue;
134
135    #[test]
136    fn test_send_sync() {
137        fn is_send<T: Send>() {}
138        fn is_sync<T: Sync>() {}
139
140        is_send::<Queue<i32>>();
141        is_sync::<Queue<i32>>();
142    }
143
144    #[test]
145    fn test_push() {
146        let mut list = Queue::new();
147        list.push(1);
148        list.push(2);
149        list.push(3);
150
151        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![1, 2, 3]);
152    }
153
154    #[test]
155    fn test_move_to_end() {
156        let mut list = Queue::new();
157        let el1 = list.push(1);
158        let el2 = list.push(2);
159
160        list.remove(el1);
161        list.push_node(el1);
162
163        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![2, 1]);
164
165        list.remove(el2);
166        list.push_node(el2);
167
168        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![1, 2]);
169    }
170
171    #[test]
172    fn test_remove_front() {
173        let mut list = Queue::new();
174        let el = list.push(1);
175        list.push(2);
176        list.push(3);
177        list.push(4);
178
179        list.remove(el);
180
181        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![2, 3, 4]);
182    }
183
184    #[test]
185    fn test_remove_mid() {
186        let mut list = Queue::new();
187        list.push(1);
188        let el1 = list.push(2);
189        let el2 = list.push(3);
190        list.push(4);
191
192        list.remove(el2);
193        list.remove(el1);
194
195        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![1, 4]);
196    }
197
198    #[test]
199    fn test_remove_back() {
200        let mut list = Queue::new();
201        list.push(1);
202        list.push(2);
203        list.push(3);
204        let el = list.push(4);
205
206        list.remove(el);
207
208        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![1, 2, 3]);
209    }
210
211    #[test]
212    fn test_pop() {
213        let mut list = Queue::new();
214        list.push(1);
215        list.push(2);
216        list.push(3);
217
218        assert!(list.pop_node().is_some());
219        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![2, 3]);
220
221        assert!(list.pop_node().is_some());
222        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), vec![3]);
223
224        assert!(list.pop_node().is_some());
225        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), Vec::new());
226
227        assert!(list.pop_node().is_none());
228        assert_eq!(list.iter().map(|x| *x).collect::<Vec<_>>(), Vec::new());
229    }
230}
tlru_cache/queue.rs

tlru_cache/
queue.rs
