sokoban/
deque.rs

1use crate::{
2    node_allocator::{NodeAllocator, ZeroCopy, SENTINEL},
3    FromSlice,
4};
5use bytemuck::{Pod, Zeroable};
6
7// Register aliases
8pub const PREV: u32 = 0;
9pub const NEXT: u32 = 1;
10
11#[repr(C)]
12#[derive(Copy, Clone)]
13pub struct Deque<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> {
14    pub sequence_number: u64,
15    pub head: u32,
16    pub tail: u32,
17    allocator: NodeAllocator<T, MAX_SIZE, 2>,
18}
19
20unsafe impl<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> Zeroable
21    for Deque<T, MAX_SIZE>
22{
23}
24unsafe impl<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> Pod
25    for Deque<T, MAX_SIZE>
26{
27}
28
29impl<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> ZeroCopy
30    for Deque<T, MAX_SIZE>
31{
32}
33
34impl<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> FromSlice
35    for Deque<T, MAX_SIZE>
36{
37    fn new_from_slice(slice: &mut [u8]) -> &mut Self {
38        let deque = Self::load_mut_bytes(slice).unwrap();
39        deque.initialize();
40        deque
41    }
42}
43
44impl<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> Default
45    for Deque<T, MAX_SIZE>
46{
47    fn default() -> Self {
48        Deque {
49            sequence_number: 0,
50            head: SENTINEL,
51            tail: SENTINEL,
52            allocator: NodeAllocator::<T, MAX_SIZE, 2>::default(),
53        }
54    }
55}
56
57impl<T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> Deque<T, MAX_SIZE> {
58    pub fn new() -> Self {
59        Self::default()
60    }
61
62    pub fn initialize(&mut self) {
63        self.allocator.initialize();
64    }
65
66    pub fn front(&self) -> Option<&T> {
67        if self.head == SENTINEL {
68            return None;
69        }
70        Some(self.get_node(self.head))
71    }
72
73    pub fn back(&self) -> Option<&T> {
74        if self.tail == SENTINEL {
75            return None;
76        }
77        Some(self.allocator.get(self.tail).get_value())
78    }
79
80    pub fn get_next(&self, index: u32) -> u32 {
81        self.allocator.get_register(index, NEXT)
82    }
83
84    pub fn get_prev(&self, index: u32) -> u32 {
85        self.allocator.get_register(index, PREV)
86    }
87
88    #[inline(always)]
89    fn get_node(&self, i: u32) -> &T {
90        self.allocator.get(i).get_value()
91    }
92
93    pub fn push_back(&mut self, node: T) {
94        let index = self.allocator.add_node(node);
95        if self.head == SENTINEL {
96            self.head = index;
97        }
98        if self.tail != SENTINEL {
99            self.allocator.connect(index, self.tail, PREV, NEXT);
100        }
101        self.tail = index;
102        self.sequence_number += 1;
103    }
104
105    pub fn push_front(&mut self, node: T) {
106        let index = self.allocator.add_node(node);
107        if self.tail == SENTINEL {
108            self.tail = index;
109        }
110        if self.head != SENTINEL {
111            self.allocator.connect(index, self.head, NEXT, PREV);
112        }
113        self.head = index;
114        self.sequence_number += 1;
115    }
116
117    pub fn pop_front(&mut self) -> Option<T> {
118        if self.head == SENTINEL {
119            return None;
120        }
121        let head = self.head;
122        self._remove(head)
123    }
124
125    pub fn pop_back(&mut self) -> Option<T> {
126        if self.tail == SENTINEL {
127            return None;
128        }
129        let tail = self.tail;
130        self._remove(tail)
131    }
132
133    fn _remove(&mut self, i: u32) -> Option<T> {
134        let (left, right, value) = {
135            let value = *self.get_node(i);
136            let left = self.get_prev(i);
137            let right = self.get_next(i);
138            (left, right, value)
139        };
140        self.allocator.clear_register(i as u32, PREV);
141        self.allocator.clear_register(i as u32, NEXT);
142        if left != SENTINEL && right != SENTINEL {
143            self.allocator.connect(left, right, NEXT, PREV);
144        }
145        if i == self.head {
146            self.head = right;
147            self.allocator.clear_register(right, PREV);
148        }
149        if i == self.tail {
150            self.tail = left;
151            self.allocator.clear_register(left, NEXT);
152        }
153        self.allocator.remove_node(i as u32);
154        self.sequence_number += 1;
155        Some(value)
156    }
157
158    pub fn len(&self) -> usize {
159        self.allocator.size as usize
160    }
161
162    pub fn is_empty(&self) -> bool {
163        self.len() == 0
164    }
165
166    pub fn iter(&self) -> DequeIterator<'_, T, MAX_SIZE> {
167        DequeIterator::<T, MAX_SIZE> {
168            deque: self,
169            fwd_ptr: self.head,
170            rev_ptr: self.tail,
171            terminated: false,
172        }
173    }
174
175    pub fn iter_mut(&mut self) -> DequeIteratorMut<'_, T, MAX_SIZE> {
176        let head = self.head;
177        let tail = self.tail;
178        DequeIteratorMut::<T, MAX_SIZE> {
179            deque: self,
180            fwd_ptr: head,
181            rev_ptr: tail,
182            terminated: false,
183        }
184    }
185}
186
187pub struct DequeIterator<'a, T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> {
188    deque: &'a Deque<T, MAX_SIZE>,
189    fwd_ptr: u32,
190    rev_ptr: u32,
191    terminated: bool,
192}
193
194impl<'a, T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> Iterator
195    for DequeIterator<'a, T, MAX_SIZE>
196{
197    type Item = (usize, &'a T);
198
199    fn next(&mut self) -> Option<Self::Item> {
200        if self.terminated {
201            return None;
202        }
203        match self.fwd_ptr {
204            SENTINEL => None,
205            _ => {
206                let ptr = self.fwd_ptr;
207                if ptr == self.rev_ptr {
208                    self.terminated = true;
209                }
210                self.fwd_ptr = self.deque.get_next(ptr);
211                Some((ptr as usize, self.deque.get_node(ptr)))
212            }
213        }
214    }
215}
216
217impl<'a, T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> DoubleEndedIterator
218    for DequeIterator<'a, T, MAX_SIZE>
219{
220    fn next_back(&mut self) -> Option<Self::Item> {
221        if self.terminated {
222            return None;
223        }
224        match self.rev_ptr {
225            SENTINEL => None,
226            _ => {
227                let ptr = self.rev_ptr;
228                if ptr == self.fwd_ptr {
229                    self.terminated = true;
230                }
231                self.rev_ptr = self.deque.get_prev(ptr);
232                Some((ptr as usize, self.deque.get_node(ptr)))
233            }
234        }
235    }
236}
237
238pub struct DequeIteratorMut<'a, T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> {
239    deque: &'a mut Deque<T, MAX_SIZE>,
240    fwd_ptr: u32,
241    rev_ptr: u32,
242    terminated: bool,
243}
244
245impl<'a, T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> Iterator
246    for DequeIteratorMut<'a, T, MAX_SIZE>
247{
248    type Item = (usize, &'a mut T);
249
250    fn next(&mut self) -> Option<Self::Item> {
251        if self.terminated {
252            return None;
253        }
254        match self.fwd_ptr {
255            SENTINEL => None,
256            _ => {
257                let ptr = self.fwd_ptr;
258                if ptr == self.rev_ptr {
259                    self.terminated = true;
260                }
261                self.fwd_ptr = self.deque.get_next(ptr);
262                Some((ptr as usize, unsafe {
263                    (*self
264                        .deque
265                        .allocator
266                        .nodes
267                        .as_mut_ptr()
268                        .add((ptr - 1) as usize))
269                    .get_value_mut()
270                }))
271            }
272        }
273    }
274}
275
276impl<'a, T: Default + Copy + Clone + Pod + Zeroable, const MAX_SIZE: usize> DoubleEndedIterator
277    for DequeIteratorMut<'a, T, MAX_SIZE>
278{
279    fn next_back(&mut self) -> Option<Self::Item> {
280        if self.terminated {
281            return None;
282        }
283        match self.rev_ptr {
284            SENTINEL => None,
285            _ => {
286                let ptr = self.rev_ptr;
287                if ptr == self.fwd_ptr {
288                    self.terminated = true;
289                }
290                self.rev_ptr = self.deque.get_prev(ptr);
291                Some((ptr as usize, unsafe {
292                    (*self
293                        .deque
294                        .allocator
295                        .nodes
296                        .as_mut_ptr()
297                        .add((ptr - 1) as usize))
298                    .get_value_mut()
299                }))
300            }
301        }
302    }
303}
304
305#[test]
306/// This test covers the primary use cases of the deque
307fn test_deque() {
308    use rand::thread_rng;
309    use rand::Rng;
310    use std::collections::VecDeque;
311    let mut rng = thread_rng();
312    type Q = Deque<u64, 1024>;
313    let mut buf = vec![0u8; std::mem::size_of::<Q>()];
314    let mut v = VecDeque::new();
315    let q = Q::new_from_slice(buf.as_mut_slice());
316    (0..128).for_each(|_| {
317        let t = rng.gen::<u64>();
318        q.push_back(t);
319        v.push_back(t);
320    });
321    (0..128).for_each(|_| {
322        let t = rng.gen::<u64>();
323        q.push_front(t);
324        v.push_front(t);
325    });
326    for ((_, i), j) in q.iter().zip(v.iter()) {
327        assert_eq!(i, j);
328    }
329    for ((_, i), j) in q.iter().rev().zip(v.iter().rev()) {
330        assert_eq!(i, j);
331    }
332
333    {
334        let mut q_iter = q.iter();
335        let mut v_iter = v.iter();
336        let breakpoint = rng.gen_range(1, 255);
337        for _ in 0..breakpoint {
338            assert_eq!(q_iter.next().map(|x| x.1), v_iter.next());
339        }
340        for _ in breakpoint..256 {
341            assert_eq!(q_iter.next_back().map(|x| x.1), v_iter.next_back());
342        }
343
344        assert!(q_iter.next().is_none());
345        assert!(q_iter.next_back().is_none());
346        assert!(v_iter.next().is_none());
347        assert!(v_iter.next_back().is_none());
348        // Do it again for good measure
349        assert!(q_iter.next().is_none());
350        assert!(q_iter.next_back().is_none());
351        assert!(v_iter.next().is_none());
352        assert!(v_iter.next_back().is_none());
353    }
354
355    {
356        let mut q_iter_mut = q.iter_mut();
357        let mut v_iter_mut = v.iter_mut();
358        let breakpoint = rng.gen_range(1, 255);
359        for _ in 0..breakpoint {
360            assert_eq!(q_iter_mut.next().map(|x| x.1), v_iter_mut.next());
361        }
362        for _ in breakpoint..256 {
363            assert_eq!(q_iter_mut.next_back().map(|x| x.1), v_iter_mut.next_back());
364        }
365
366        assert!(q_iter_mut.next().is_none());
367        assert!(q_iter_mut.next_back().is_none());
368        assert!(v_iter_mut.next().is_none());
369        assert!(v_iter_mut.next_back().is_none());
370        // Do it again for good measure
371        assert!(q_iter_mut.next().is_none());
372        assert!(q_iter_mut.next_back().is_none());
373        assert!(v_iter_mut.next().is_none());
374        assert!(v_iter_mut.next_back().is_none());
375    }
376
377    (0..256).for_each(|_| {
378        assert_eq!(q.pop_back(), v.pop_back());
379    });
380    assert!(q.is_empty() && v.is_empty());
381    (0..128).for_each(|_| {
382        let t = rng.gen::<u64>();
383        q.push_back(t);
384        v.push_back(t);
385    });
386    (0..128).for_each(|_| {
387        let t = rng.gen::<u64>();
388        q.push_front(t);
389        v.push_front(t);
390    });
391    for ((_, i), j) in q.iter().zip(v.iter()) {
392        assert_eq!(i, j);
393    }
394    for ((_, i), j) in q.iter().rev().zip(v.iter().rev()) {
395        assert_eq!(i, j);
396    }
397    (0..256).for_each(|_| {
398        assert_eq!(q.pop_front(), v.pop_front());
399    });
400    assert!(q.is_empty() && v.is_empty());
401}
sokoban/deque.rs

sokoban/
deque.rs
