moka/common/
deque.rs

Help
1// License and Copyright Notice:
2//
3// Some of the code and doc comments in this module were copied from
4// `std::collections::LinkedList` in the Rust standard library.
5// https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/linked_list.rs
6//
7// The original code/comments from LinkedList are dual-licensed under
8// the Apache License, Version 2.0 <https://github.com/rust-lang/rust/blob/master/LICENSE-APACHE>
9// or the MIT license <https://github.com/rust-lang/rust/blob/master/LICENSE-MIT>
10//
11// Copyrights of the original code/comments are retained by their contributors.
12// For full authorship information, see the version control history of
13// https://github.com/rust-lang/rust/ or https://thanks.rust-lang.org
14
15use std::{marker::PhantomData, ptr::NonNull};
16
17use super::CacheRegion;
18
19#[cfg(feature = "unstable-debug-counters")]
20use crate::common::concurrent::debug_counters;
21
22// `crate::{sync,unsync}::DeqNodes` uses a `tagptr::TagNonNull<DeqNode<T>, 2>`
23// pointer. To reserve the space for the 2-bit tag, use 4 bytes as the *minimum*
24// alignment.
25// https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers
26#[repr(align(4))]
27#[derive(PartialEq, Eq)]
28pub(crate) struct DeqNode<T> {
29    next: Option<NonNull<DeqNode<T>>>,
30    prev: Option<NonNull<DeqNode<T>>>,
31    pub(crate) element: T,
32}
33
34impl<T> std::fmt::Debug for DeqNode<T> {
35    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36        f.debug_struct("DeqNode")
37            .field("next", &self.next)
38            .field("prev", &self.prev)
39            .finish()
40    }
41}
42
43impl<T> DeqNode<T> {
44    pub(crate) fn new(element: T) -> Self {
45        #[cfg(feature = "unstable-debug-counters")]
46        debug_counters::InternalGlobalDebugCounters::deq_node_created();
47
48        Self {
49            next: None,
50            prev: None,
51            element,
52        }
53    }
54
55    pub(crate) fn next_node_ptr(this: NonNull<Self>) -> Option<NonNull<DeqNode<T>>> {
56        unsafe { this.as_ref() }.next
57    }
58}
59
60#[cfg(feature = "unstable-debug-counters")]
61impl<T> Drop for DeqNode<T> {
62    fn drop(&mut self) {
63        debug_counters::InternalGlobalDebugCounters::deq_node_dropped();
64    }
65}
66
67/// Cursor is used to remember the current iterating position.
68enum DeqCursor<T> {
69    Node(NonNull<DeqNode<T>>),
70    Done,
71}
72
73pub(crate) struct Deque<T> {
74    region: CacheRegion,
75    len: usize,
76    head: Option<NonNull<DeqNode<T>>>,
77    tail: Option<NonNull<DeqNode<T>>>,
78    cursor: Option<DeqCursor<T>>,
79    marker: PhantomData<Box<DeqNode<T>>>,
80}
81
82impl<T> Drop for Deque<T> {
83    fn drop(&mut self) {
84        struct DropGuard<'a, T>(&'a mut Deque<T>);
85
86        impl<T> Drop for DropGuard<'_, T> {
87            fn drop(&mut self) {
88                // Continue the same loop we do below. This only runs when a destructor has
89                // panicked. If another one panics this will abort.
90                while self.0.pop_front().is_some() {}
91            }
92        }
93
94        while let Some(node) = self.pop_front() {
95            let guard = DropGuard(self);
96            drop(node);
97            std::mem::forget(guard);
98        }
99    }
100}
101
102// Inner crate public function/methods
103impl<T> Deque<T> {
104    pub(crate) fn new(region: CacheRegion) -> Self {
105        Self {
106            region,
107            len: 0,
108            head: None,
109            tail: None,
110            cursor: None,
111            marker: PhantomData,
112        }
113    }
114
115    pub(crate) fn region(&self) -> CacheRegion {
116        self.region
117    }
118
119    pub(crate) fn len(&self) -> usize {
120        self.len
121    }
122
123    pub(crate) fn contains(&self, node: &DeqNode<T>) -> bool {
124        node.prev.is_some() || self.is_head(node)
125    }
126
127    pub(crate) fn peek_front(&self) -> Option<&DeqNode<T>> {
128        self.head.as_ref().map(|node| unsafe { node.as_ref() })
129    }
130
131    pub(crate) fn peek_front_ptr(&self) -> Option<NonNull<DeqNode<T>>> {
132        self.head.as_ref().copied()
133    }
134
135    /// Removes and returns the node at the front of the list.
136    pub(crate) fn pop_front(&mut self) -> Option<Box<DeqNode<T>>> {
137        // This method takes care not to create mutable references to whole nodes,
138        // to maintain validity of aliasing pointers into `element`.
139        self.head.map(|node| unsafe {
140            if self.is_at_cursor(node.as_ref()) {
141                self.advance_cursor();
142            }
143
144            let mut node = Box::from_raw(node.as_ptr());
145            self.head = node.next;
146
147            match self.head {
148                None => self.tail = None,
149                // Not creating new mutable (unique!) references overlapping `element`.
150                Some(head) => (*head.as_ptr()).prev = None,
151            }
152
153            self.len -= 1;
154
155            node.prev = None;
156            node.next = None;
157            node
158        })
159    }
160
161    pub(crate) fn peek_back(&self) -> Option<&DeqNode<T>> {
162        self.tail.as_ref().map(|node| unsafe { node.as_ref() })
163    }
164
165    /// Adds the given node to the back of the list.
166    pub(crate) fn push_back(&mut self, mut node: Box<DeqNode<T>>) -> NonNull<DeqNode<T>> {
167        // This method takes care not to create mutable references to whole nodes,
168        // to maintain validity of aliasing pointers into `element`.
169        unsafe {
170            node.next = None;
171            node.prev = self.tail;
172            let node = NonNull::new(Box::into_raw(node)).expect("Got a null ptr");
173
174            match self.tail {
175                None => self.head = Some(node),
176                // Not creating new mutable (unique!) references overlapping `element`.
177                Some(tail) => (*tail.as_ptr()).next = Some(node),
178            }
179
180            self.tail = Some(node);
181            self.len += 1;
182            node
183        }
184    }
185
186    pub(crate) unsafe fn move_to_back(&mut self, mut node: NonNull<DeqNode<T>>) {
187        if self.is_tail(node.as_ref()) {
188            // Already at the tail. Nothing to do.
189            return;
190        }
191
192        if self.is_at_cursor(node.as_ref()) {
193            self.advance_cursor();
194        }
195
196        let node = node.as_mut(); // this one is ours now, we can create an &mut.
197
198        // Not creating new mutable (unique!) references overlapping `element`.
199        match node.prev {
200            Some(prev) if node.next.is_some() => (*prev.as_ptr()).next = node.next,
201            Some(..) => (),
202            // This node is the head node.
203            None => self.head = node.next,
204        };
205
206        // This node is not the tail node.
207        if let Some(next) = node.next.take() {
208            (*next.as_ptr()).prev = node.prev;
209
210            let mut node = NonNull::from(node);
211            match self.tail {
212                // Not creating new mutable (unique!) references overlapping `element`.
213                Some(tail) => {
214                    node.as_mut().prev = Some(tail);
215                    (*tail.as_ptr()).next = Some(node);
216                }
217                None => unreachable!(),
218            }
219            self.tail = Some(node);
220        }
221    }
222
223    pub(crate) fn move_front_to_back(&mut self) {
224        if let Some(node) = self.head {
225            unsafe { self.move_to_back(node) };
226        }
227    }
228
229    /// Unlinks the specified node from the current list.
230    ///
231    /// This method takes care not to create mutable references to `element`, to
232    /// maintain validity of aliasing pointers.
233    ///
234    /// IMPORTANT: This method does not drop the node. If the node is no longer
235    /// needed, use `unlink_and_drop` instead, or drop it at the caller side.
236    /// Otherwise, the node will leak.
237    pub(crate) unsafe fn unlink(&mut self, mut node: NonNull<DeqNode<T>>) {
238        if self.is_at_cursor(node.as_ref()) {
239            self.advance_cursor();
240        }
241
242        let node = node.as_mut(); // this one is ours now, we can create an &mut.
243
244        // Not creating new mutable (unique!) references overlapping `element`.
245        match node.prev {
246            Some(prev) => (*prev.as_ptr()).next = node.next,
247            // this node is the head node
248            None => self.head = node.next,
249        };
250
251        match node.next {
252            Some(next) => (*next.as_ptr()).prev = node.prev,
253            // this node is the tail node
254            None => self.tail = node.prev,
255        };
256
257        node.prev = None;
258        node.next = None;
259
260        self.len -= 1;
261    }
262
263    /// Unlinks the specified node from the current list, and then drop the node.
264    ///
265    /// This method takes care not to create mutable references to `element`, to
266    /// maintain validity of aliasing pointers.
267    ///
268    /// Panics:
269    pub(crate) unsafe fn unlink_and_drop(&mut self, node: NonNull<DeqNode<T>>) {
270        self.unlink(node);
271        std::mem::drop(Box::from_raw(node.as_ptr()));
272    }
273
274    pub(crate) fn reset_cursor(&mut self) {
275        self.cursor = None;
276    }
277}
278
279impl<'a, T> Iterator for &'a mut Deque<T> {
280    type Item = &'a T;
281
282    fn next(&mut self) -> Option<Self::Item> {
283        if self.cursor.is_none() {
284            if let Some(head) = self.head {
285                self.cursor = Some(DeqCursor::Node(head));
286            }
287        }
288        let elem = if let Some(DeqCursor::Node(node)) = self.cursor {
289            unsafe { Some(&(*node.as_ptr()).element) }
290        } else {
291            None
292        };
293        self.advance_cursor();
294        elem
295    }
296}
297
298// Private function/methods
299impl<T> Deque<T> {
300    fn is_head(&self, node: &DeqNode<T>) -> bool {
301        if let Some(head) = self.head {
302            std::ptr::eq(unsafe { head.as_ref() }, node)
303        } else {
304            false
305        }
306    }
307
308    fn is_tail(&self, node: &DeqNode<T>) -> bool {
309        if let Some(tail) = self.tail {
310            std::ptr::eq(unsafe { tail.as_ref() }, node)
311        } else {
312            false
313        }
314    }
315
316    fn is_at_cursor(&self, node: &DeqNode<T>) -> bool {
317        if let Some(DeqCursor::Node(cur_node)) = self.cursor {
318            std::ptr::eq(unsafe { cur_node.as_ref() }, node)
319        } else {
320            false
321        }
322    }
323
324    fn advance_cursor(&mut self) {
325        match self.cursor.take() {
326            None => (),
327            Some(DeqCursor::Node(node)) => unsafe {
328                if let Some(next) = (*node.as_ptr()).next {
329                    self.cursor = Some(DeqCursor::Node(next));
330                } else {
331                    self.cursor = Some(DeqCursor::Done);
332                }
333            },
334            Some(DeqCursor::Done) => {
335                self.cursor = None;
336            }
337        }
338    }
339}
340
341#[cfg(test)]
342mod tests {
343    use super::{CacheRegion::MainProbation, DeqNode, Deque};
344
345    #[test]
346    #[allow(clippy::cognitive_complexity)]
347    fn basics() {
348        let mut deque: Deque<String> = Deque::new(MainProbation);
349        assert_eq!(deque.len(), 0);
350        assert!(deque.peek_front().is_none());
351        assert!(deque.peek_back().is_none());
352
353        // push_back(node1)
354        let node1 = DeqNode::new("a".to_string());
355        assert!(!deque.contains(&node1));
356        let node1 = Box::new(node1);
357        let node1_ptr = deque.push_back(node1);
358        assert_eq!(deque.len(), 1);
359
360        // peek_front() -> node1
361        let head_a = deque.peek_front().unwrap();
362        assert!(deque.contains(head_a));
363        assert!(deque.is_head(head_a));
364        assert!(deque.is_tail(head_a));
365        assert_eq!(head_a.element, "a".to_string());
366
367        // move_to_back(node1)
368        unsafe { deque.move_to_back(node1_ptr) };
369        assert_eq!(deque.len(), 1);
370
371        // peek_front() -> node1
372        let head_b = deque.peek_front().unwrap();
373        assert!(deque.contains(head_b));
374        assert!(deque.is_head(head_b));
375        assert!(deque.is_tail(head_b));
376        assert!(std::ptr::eq(head_b, node1_ptr.as_ptr()));
377        assert!(head_b.prev.is_none());
378        assert!(head_b.next.is_none());
379
380        // peek_back() -> node1
381        let tail_a = deque.peek_back().unwrap();
382        assert!(deque.contains(tail_a));
383        assert!(deque.is_head(tail_a));
384        assert!(deque.is_tail(tail_a));
385        assert!(std::ptr::eq(tail_a, node1_ptr.as_ptr()));
386        assert!(tail_a.prev.is_none());
387        assert!(tail_a.next.is_none());
388
389        // push_back(node2)
390        let node2 = DeqNode::new("b".to_string());
391        assert!(!deque.contains(&node2));
392        let node2_ptr = deque.push_back(Box::new(node2));
393        assert_eq!(deque.len(), 2);
394
395        // peek_front() -> node1
396        let head_c = deque.peek_front().unwrap();
397        assert!(deque.contains(head_c));
398        assert!(deque.is_head(head_c));
399        assert!(!deque.is_tail(head_c));
400        assert!(std::ptr::eq(head_c, node1_ptr.as_ptr()));
401        assert!(head_c.prev.is_none());
402        assert!(std::ptr::eq(
403            head_c.next.unwrap().as_ptr(),
404            node2_ptr.as_ptr()
405        ));
406
407        // move_to_back(node2)
408        unsafe { deque.move_to_back(node2_ptr) };
409        assert_eq!(deque.len(), 2);
410
411        // peek_front() -> node1
412        let head_d = deque.peek_front().unwrap();
413        assert!(deque.contains(head_d));
414        assert!(deque.is_head(head_d));
415        assert!(!deque.is_tail(head_d));
416        assert!(std::ptr::eq(head_d, node1_ptr.as_ptr()));
417        assert!(head_d.prev.is_none());
418        assert!(std::ptr::eq(
419            head_d.next.unwrap().as_ptr(),
420            node2_ptr.as_ptr()
421        ));
422
423        // peek_back() -> node2
424        let tail_b = deque.peek_back().unwrap();
425        assert!(deque.contains(tail_b));
426        assert!(!deque.is_head(tail_b));
427        assert!(deque.is_tail(tail_b));
428        assert!(std::ptr::eq(tail_b, node2_ptr.as_ptr()));
429        assert!(std::ptr::eq(
430            tail_b.prev.unwrap().as_ptr(),
431            node1_ptr.as_ptr()
432        ));
433        assert_eq!(tail_b.element, "b".to_string());
434        assert!(tail_b.next.is_none());
435
436        // move_to_back(node1)
437        unsafe { deque.move_to_back(node1_ptr) };
438        assert_eq!(deque.len(), 2);
439
440        // peek_front() -> node2
441        let head_e = deque.peek_front().unwrap();
442        assert!(deque.contains(head_e));
443        assert!(deque.is_head(head_e));
444        assert!(!deque.is_tail(head_e));
445        assert!(std::ptr::eq(head_e, node2_ptr.as_ptr()));
446        assert!(head_e.prev.is_none());
447        assert!(std::ptr::eq(
448            head_e.next.unwrap().as_ptr(),
449            node1_ptr.as_ptr()
450        ));
451
452        // peek_back() -> node1
453        let tail_c = deque.peek_back().unwrap();
454        assert!(deque.contains(tail_c));
455        assert!(!deque.is_head(tail_c));
456        assert!(deque.is_tail(tail_c));
457        assert!(std::ptr::eq(tail_c, node1_ptr.as_ptr()));
458        assert!(std::ptr::eq(
459            tail_c.prev.unwrap().as_ptr(),
460            node2_ptr.as_ptr()
461        ));
462        assert!(tail_c.next.is_none());
463
464        // push_back(node3)
465        let node3 = DeqNode::new("c".to_string());
466        assert!(!deque.contains(&node3));
467        let node3_ptr = deque.push_back(Box::new(node3));
468        assert_eq!(deque.len(), 3);
469
470        // peek_front() -> node2
471        let head_f = deque.peek_front().unwrap();
472        assert!(deque.contains(head_f));
473        assert!(deque.is_head(head_f));
474        assert!(!deque.is_tail(head_f));
475        assert!(std::ptr::eq(head_f, node2_ptr.as_ptr()));
476        assert!(head_f.prev.is_none());
477        assert!(std::ptr::eq(
478            head_f.next.unwrap().as_ptr(),
479            node1_ptr.as_ptr()
480        ));
481
482        // peek_back() -> node3
483        let tail_d = deque.peek_back().unwrap();
484        assert!(std::ptr::eq(tail_d, node3_ptr.as_ptr()));
485        assert_eq!(tail_d.element, "c".to_string());
486        assert!(deque.contains(tail_d));
487        assert!(!deque.is_head(tail_d));
488        assert!(deque.is_tail(tail_d));
489        assert!(std::ptr::eq(tail_d, node3_ptr.as_ptr()));
490        assert!(std::ptr::eq(
491            tail_d.prev.unwrap().as_ptr(),
492            node1_ptr.as_ptr()
493        ));
494        assert!(tail_d.next.is_none());
495
496        // move_to_back(node1)
497        unsafe { deque.move_to_back(node1_ptr) };
498        assert_eq!(deque.len(), 3);
499
500        // peek_front() -> node2
501        let head_g = deque.peek_front().unwrap();
502        assert!(deque.contains(head_g));
503        assert!(deque.is_head(head_g));
504        assert!(!deque.is_tail(head_g));
505        assert!(std::ptr::eq(head_g, node2_ptr.as_ptr()));
506        assert!(head_g.prev.is_none());
507        assert!(std::ptr::eq(
508            head_g.next.unwrap().as_ptr(),
509            node3_ptr.as_ptr()
510        ));
511
512        // peek_back() -> node1
513        let tail_e = deque.peek_back().unwrap();
514        assert!(deque.contains(tail_e));
515        assert!(!deque.is_head(tail_e));
516        assert!(deque.is_tail(tail_e));
517        assert!(std::ptr::eq(tail_e, node1_ptr.as_ptr()));
518        assert!(std::ptr::eq(
519            tail_e.prev.unwrap().as_ptr(),
520            node3_ptr.as_ptr()
521        ));
522        assert!(tail_e.next.is_none());
523
524        // unlink(node3)
525        unsafe { deque.unlink(node3_ptr) };
526        assert_eq!(deque.len(), 2);
527        let node3_ref = unsafe { node3_ptr.as_ref() };
528        assert!(!deque.contains(node3_ref));
529        assert!(node3_ref.next.is_none());
530        assert!(node3_ref.next.is_none());
531        std::mem::drop(unsafe { Box::from_raw(node3_ptr.as_ptr()) });
532
533        // peek_front() -> node2
534        let head_h = deque.peek_front().unwrap();
535        assert!(deque.contains(head_h));
536        assert!(deque.is_head(head_h));
537        assert!(!deque.is_tail(head_h));
538        assert!(std::ptr::eq(head_h, node2_ptr.as_ptr()));
539        assert!(head_h.prev.is_none());
540        assert!(std::ptr::eq(
541            head_h.next.unwrap().as_ptr(),
542            node1_ptr.as_ptr()
543        ));
544
545        // peek_back() -> node1
546        let tail_f = deque.peek_back().unwrap();
547        assert!(deque.contains(tail_f));
548        assert!(!deque.is_head(tail_f));
549        assert!(deque.is_tail(tail_f));
550        assert!(std::ptr::eq(tail_f, node1_ptr.as_ptr()));
551        assert!(std::ptr::eq(
552            tail_f.prev.unwrap().as_ptr(),
553            node2_ptr.as_ptr()
554        ));
555        assert!(tail_f.next.is_none());
556
557        // unlink(node2)
558        unsafe { deque.unlink(node2_ptr) };
559        assert_eq!(deque.len(), 1);
560        let node2_ref = unsafe { node2_ptr.as_ref() };
561        assert!(!deque.contains(node2_ref));
562        assert!(node2_ref.next.is_none());
563        assert!(node2_ref.next.is_none());
564        std::mem::drop(unsafe { Box::from_raw(node2_ptr.as_ptr()) });
565
566        // peek_front() -> node1
567        let head_g = deque.peek_front().unwrap();
568        assert!(deque.contains(head_g));
569        assert!(deque.is_head(head_g));
570        assert!(deque.is_tail(head_g));
571        assert!(std::ptr::eq(head_g, node1_ptr.as_ptr()));
572        assert!(head_g.prev.is_none());
573        assert!(head_g.next.is_none());
574
575        // peek_back() -> node1
576        let tail_g = deque.peek_back().unwrap();
577        assert!(deque.contains(tail_g));
578        assert!(deque.is_head(tail_g));
579        assert!(deque.is_tail(tail_g));
580        assert!(std::ptr::eq(tail_g, node1_ptr.as_ptr()));
581        assert!(tail_g.next.is_none());
582        assert!(tail_g.next.is_none());
583
584        // unlink(node1)
585        unsafe { deque.unlink(node1_ptr) };
586        assert_eq!(deque.len(), 0);
587        let node1_ref = unsafe { node1_ptr.as_ref() };
588        assert!(!deque.contains(node1_ref));
589        assert!(node1_ref.next.is_none());
590        assert!(node1_ref.next.is_none());
591        std::mem::drop(unsafe { Box::from_raw(node1_ptr.as_ptr()) });
592
593        // peek_front() -> node1
594        let head_h = deque.peek_front();
595        assert!(head_h.is_none());
596
597        // peek_back() -> node1
598        let tail_e = deque.peek_back();
599        assert!(tail_e.is_none());
600    }
601
602    #[test]
603    fn iter() {
604        let mut deque: Deque<String> = Deque::new(MainProbation);
605        assert!((&mut deque).next().is_none());
606
607        let node1 = DeqNode::new("a".into());
608        deque.push_back(Box::new(node1));
609        let node2 = DeqNode::new("b".into());
610        let node2_ptr = deque.push_back(Box::new(node2));
611        let node3 = DeqNode::new("c".into());
612        let node3_ptr = deque.push_back(Box::new(node3));
613
614        // -------------------------------------------------------
615        // First iteration.
616        assert_eq!((&mut deque).next(), Some(&"a".into()));
617        assert_eq!((&mut deque).next(), Some(&"b".into()));
618        assert_eq!((&mut deque).next(), Some(&"c".into()));
619        assert!((&mut deque).next().is_none());
620
621        // -------------------------------------------------------
622        // Ensure the iterator restarts.
623        assert_eq!((&mut deque).next(), Some(&"a".into()));
624        assert_eq!((&mut deque).next(), Some(&"b".into()));
625        assert_eq!((&mut deque).next(), Some(&"c".into()));
626        assert!((&mut deque).next().is_none());
627
628        // -------------------------------------------------------
629        // Ensure reset_cursor works.
630        assert_eq!((&mut deque).next(), Some(&"a".into()));
631        assert_eq!((&mut deque).next(), Some(&"b".into()));
632        deque.reset_cursor();
633        assert_eq!((&mut deque).next(), Some(&"a".into()));
634        assert_eq!((&mut deque).next(), Some(&"b".into()));
635        assert_eq!((&mut deque).next(), Some(&"c".into()));
636        assert!((&mut deque).next().is_none());
637
638        // -------------------------------------------------------
639        // Try to move_to_back during iteration.
640        assert_eq!((&mut deque).next(), Some(&"a".into()));
641        // Next will be "b", but we move it to the back.
642        unsafe { deque.move_to_back(node2_ptr) };
643        // Now, next should be "c", and then "b".
644        assert_eq!((&mut deque).next(), Some(&"c".into()));
645        assert_eq!((&mut deque).next(), Some(&"b".into()));
646        assert!((&mut deque).next().is_none());
647
648        // -------------------------------------------------------
649        // Try to unlink during iteration.
650        assert_eq!((&mut deque).next(), Some(&"a".into()));
651        // Next will be "c", but we unlink it.
652        unsafe { deque.unlink_and_drop(node3_ptr) };
653        // Now, next should be "b".
654        assert_eq!((&mut deque).next(), Some(&"b".into()));
655        assert!((&mut deque).next().is_none());
656
657        // -------------------------------------------------------
658        // Try pop_front during iteration.
659        let node3 = DeqNode::new("c".into());
660        deque.push_back(Box::new(node3));
661
662        assert_eq!((&mut deque).next(), Some(&"a".into()));
663        // Next will be "b", but we call pop_front twice to remove "a" and "b".
664        deque.pop_front(); // "a"
665        deque.pop_front(); // "b"
666                           // Now, next should be "c".
667        assert_eq!((&mut deque).next(), Some(&"c".into()));
668        assert!((&mut deque).next().is_none());
669
670        // -------------------------------------------------------
671        // Check iterating on an empty deque.
672        deque.pop_front(); // "c"
673        assert!((&mut deque).next().is_none());
674        assert!((&mut deque).next().is_none());
675    }
676
677    #[test]
678    fn next_node() {
679        let mut deque: Deque<String> = Deque::new(MainProbation);
680
681        let node1 = DeqNode::new("a".into());
682        deque.push_back(Box::new(node1));
683        let node2 = DeqNode::new("b".into());
684        let node2_ptr = deque.push_back(Box::new(node2));
685        let node3 = DeqNode::new("c".into());
686        let node3_ptr = deque.push_back(Box::new(node3));
687
688        // -------------------------------------------------------
689        // First iteration.
690        // peek_front() -> node1
691        let node1a = deque.peek_front_ptr().unwrap();
692        assert_eq!(unsafe { node1a.as_ref() }.element, "a".to_string());
693        let node2a = DeqNode::next_node_ptr(node1a).unwrap();
694        assert_eq!(unsafe { node2a.as_ref() }.element, "b".to_string());
695        let node3a = DeqNode::next_node_ptr(node2a).unwrap();
696        assert_eq!(unsafe { node3a.as_ref() }.element, "c".to_string());
697        assert!(DeqNode::next_node_ptr(node3a).is_none());
698
699        // -------------------------------------------------------
700        // Iterate after a move_to_back.
701        // Move "b" to the back. So now "a" -> "c" -> "b".
702        unsafe { deque.move_to_back(node2_ptr) };
703        let node1a = deque.peek_front_ptr().unwrap();
704        assert_eq!(unsafe { node1a.as_ref() }.element, "a".to_string());
705        let node3a = DeqNode::next_node_ptr(node1a).unwrap();
706        assert_eq!(unsafe { node3a.as_ref() }.element, "c".to_string());
707        let node2a = DeqNode::next_node_ptr(node3a).unwrap();
708        assert_eq!(unsafe { node2a.as_ref() }.element, "b".to_string());
709        assert!(DeqNode::next_node_ptr(node2a).is_none());
710
711        // -------------------------------------------------------
712        // Iterate after an unlink.
713        // Unlink the second node "c". Now "a" -> "c".
714        unsafe { deque.unlink_and_drop(node3_ptr) };
715        let node1a = deque.peek_front_ptr().unwrap();
716        assert_eq!(unsafe { node1a.as_ref() }.element, "a".to_string());
717        let node2a = DeqNode::next_node_ptr(node1a).unwrap();
718        assert_eq!(unsafe { node2a.as_ref() }.element, "b".to_string());
719        assert!(DeqNode::next_node_ptr(node2a).is_none());
720    }
721
722    #[test]
723    fn peek_and_move_to_back() {
724        let mut deque: Deque<String> = Deque::new(MainProbation);
725
726        let node1 = DeqNode::new("a".into());
727        deque.push_back(Box::new(node1));
728        let node2 = DeqNode::new("b".into());
729        let _ = deque.push_back(Box::new(node2));
730        let node3 = DeqNode::new("c".into());
731        let _ = deque.push_back(Box::new(node3));
732        // "a" -> "b" -> "c"
733
734        let node1a = deque.peek_front_ptr().unwrap();
735        assert_eq!(unsafe { node1a.as_ref() }.element, "a".to_string());
736        unsafe { deque.move_to_back(node1a) };
737        // "b" -> "c" -> "a"
738
739        let node2a = deque.peek_front_ptr().unwrap();
740        assert_eq!(unsafe { node2a.as_ref() }.element, "b".to_string());
741
742        let node3a = DeqNode::next_node_ptr(node2a).unwrap();
743        assert_eq!(unsafe { node3a.as_ref() }.element, "c".to_string());
744        unsafe { deque.move_to_back(node3a) };
745        // "b" -> "a" -> "c"
746
747        deque.move_front_to_back();
748        // "a" -> "c" -> "b"
749
750        let node1b = deque.peek_front().unwrap();
751        assert_eq!(node1b.element, "a".to_string());
752    }
753
754    #[test]
755    fn drop() {
756        use std::{cell::RefCell, rc::Rc};
757
758        struct X(u32, Rc<RefCell<Vec<u32>>>);
759
760        impl Drop for X {
761            fn drop(&mut self) {
762                self.1.borrow_mut().push(self.0)
763            }
764        }
765
766        let mut deque: Deque<X> = Deque::new(MainProbation);
767        let dropped = Rc::new(RefCell::new(Vec::default()));
768
769        let node1 = DeqNode::new(X(1, Rc::clone(&dropped)));
770        let node2 = DeqNode::new(X(2, Rc::clone(&dropped)));
771        let node3 = DeqNode::new(X(3, Rc::clone(&dropped)));
772        let node4 = DeqNode::new(X(4, Rc::clone(&dropped)));
773        deque.push_back(Box::new(node1));
774        deque.push_back(Box::new(node2));
775        deque.push_back(Box::new(node3));
776        deque.push_back(Box::new(node4));
777        assert_eq!(deque.len(), 4);
778
779        std::mem::drop(deque);
780
781        assert_eq!(*dropped.borrow(), &[1, 2, 3, 4]);
782    }
783}
moka/common/deque.rs

moka/common/
deque.rs
