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