1#![cfg_attr(not(feature = "full"), allow(dead_code))]
2
3//! An intrusive double linked list of data.
4//!
5//! The data structure supports tracking pinned nodes. Most of the data
6//! structure's APIs are `unsafe` as they require the caller to ensure the
7//! specified node is actually contained by the list.
8
9use core::cell::UnsafeCell;
10use core::fmt;
11use core::marker::{PhantomData, PhantomPinned};
12use core::mem::ManuallyDrop;
13use core::ptr::{self, NonNull};
14
15/// An intrusive linked list.
16///
17/// Currently, the list is not emptied on drop. It is the caller's
18/// responsibility to ensure the list is empty before dropping it.
19pub(crate) struct LinkedList<L, T> {
20 /// Linked list head
21 head: Option<NonNull<T>>,
22
23 /// Linked list tail
24 tail: Option<NonNull<T>>,
25
26 /// Node type marker.
27 _marker: PhantomData<*const L>,
28}
29
30unsafe impl<L: Link> Send for LinkedList<L, L::Target> where L::Target: Send {}
31unsafe impl<L: Link> Sync for LinkedList<L, L::Target> where L::Target: Sync {}
32
33/// Defines how a type is tracked within a linked list.
34///
35/// In order to support storing a single type within multiple lists, accessing
36/// the list pointers is decoupled from the entry type.
37///
38/// # Safety
39///
40/// Implementations must guarantee that `Target` types are pinned in memory. In
41/// other words, when a node is inserted, the value will not be moved as long as
42/// it is stored in the list.
43pub(crate) unsafe trait Link {
44 /// Handle to the list entry.
45 ///
46 /// This is usually a pointer-ish type.
47 type Handle;
48
49 /// Node type.
50 type Target;
51
52 /// Convert the handle to a raw pointer without consuming the handle.
53 #[allow(clippy::wrong_self_convention)]
54 fn as_raw(handle: &Self::Handle) -> NonNull<Self::Target>;
55
56 /// Convert the raw pointer to a handle
57 unsafe fn from_raw(ptr: NonNull<Self::Target>) -> Self::Handle;
58
59 /// Return the pointers for a node
60 ///
61 /// # Safety
62 ///
63 /// The resulting pointer should have the same tag in the stacked-borrows
64 /// stack as the argument. In particular, the method may not create an
65 /// intermediate reference in the process of creating the resulting raw
66 /// pointer.
67 unsafe fn pointers(target: NonNull<Self::Target>) -> NonNull<Pointers<Self::Target>>;
68}
69
70/// Previous / next pointers.
71pub(crate) struct Pointers<T> {
72 inner: UnsafeCell<PointersInner<T>>,
73}
74/// We do not want the compiler to put the `noalias` attribute on mutable
75/// references to this type, so the type has been made `!Unpin` with a
76/// `PhantomPinned` field.
77///
78/// Additionally, we never access the `prev` or `next` fields directly, as any
79/// such access would implicitly involve the creation of a reference to the
80/// field, which we want to avoid since the fields are not `!Unpin`, and would
81/// hence be given the `noalias` attribute if we were to do such an access.
82/// As an alternative to accessing the fields directly, the `Pointers` type
83/// provides getters and setters for the two fields, and those are implemented
84/// using raw pointer casts and offsets, which is valid since the struct is
85/// #[repr(C)].
86///
87/// See this link for more information:
88/// <https://github.com/rust-lang/rust/pull/82834>
89#[repr(C)]
90struct PointersInner<T> {
91 /// The previous node in the list. null if there is no previous node.
92 ///
93 /// This field is accessed through pointer manipulation, so it is not dead code.
94 #[allow(dead_code)]
95 prev: Option<NonNull<T>>,
96
97 /// The next node in the list. null if there is no previous node.
98 ///
99 /// This field is accessed through pointer manipulation, so it is not dead code.
100 #[allow(dead_code)]
101 next: Option<NonNull<T>>,
102
103 /// This type is !Unpin due to the heuristic from:
104 /// <https://github.com/rust-lang/rust/pull/82834>
105 _pin: PhantomPinned,
106}
107
108unsafe impl<T: Send> Send for Pointers<T> {}
109unsafe impl<T: Sync> Sync for Pointers<T> {}
110
111// ===== impl LinkedList =====
112
113impl<L, T> LinkedList<L, T> {
114 /// Creates an empty linked list.
115 pub(crate) const fn new() -> LinkedList<L, T> {
116 LinkedList {
117 head: None,
118 tail: None,
119 _marker: PhantomData,
120 }
121 }
122}
123
124impl<L: Link> LinkedList<L, L::Target> {
125 /// Adds an element first in the list.
126 pub(crate) fn push_front(&mut self, val: L::Handle) {
127 // The value should not be dropped, it is being inserted into the list
128 let val = ManuallyDrop::new(val);
129 let ptr = L::as_raw(&val);
130 assert_ne!(self.head, Some(ptr));
131 unsafe {
132 L::pointers(ptr).as_mut().set_next(self.head);
133 L::pointers(ptr).as_mut().set_prev(None);
134
135 if let Some(head) = self.head {
136 L::pointers(head).as_mut().set_prev(Some(ptr));
137 }
138
139 self.head = Some(ptr);
140
141 if self.tail.is_none() {
142 self.tail = Some(ptr);
143 }
144 }
145 }
146
147 /// Removes the last element from a list and returns it, or None if it is
148 /// empty.
149 pub(crate) fn pop_back(&mut self) -> Option<L::Handle> {
150 unsafe {
151 let last = self.tail?;
152 self.tail = L::pointers(last).as_ref().get_prev();
153
154 if let Some(prev) = L::pointers(last).as_ref().get_prev() {
155 L::pointers(prev).as_mut().set_next(None);
156 } else {
157 self.head = None;
158 }
159
160 L::pointers(last).as_mut().set_prev(None);
161 L::pointers(last).as_mut().set_next(None);
162
163 Some(L::from_raw(last))
164 }
165 }
166
167 /// Returns whether the linked list does not contain any node
168 pub(crate) fn is_empty(&self) -> bool {
169 if self.head.is_some() {
170 return false;
171 }
172
173 assert!(self.tail.is_none());
174 true
175 }
176
177 /// Removes the specified node from the list
178 ///
179 /// # Safety
180 ///
181 /// The caller **must** ensure that exactly one of the following is true:
182 /// - `node` is currently contained by `self`,
183 /// - `node` is not contained by any list,
184 /// - `node` is currently contained by some other `GuardedLinkedList` **and**
185 /// the caller has an exclusive access to that list. This condition is
186 /// used by the linked list in `sync::Notify`.
187 pub(crate) unsafe fn remove(&mut self, node: NonNull<L::Target>) -> Option<L::Handle> {
188 if let Some(prev) = L::pointers(node).as_ref().get_prev() {
189 debug_assert_eq!(L::pointers(prev).as_ref().get_next(), Some(node));
190 L::pointers(prev)
191 .as_mut()
192 .set_next(L::pointers(node).as_ref().get_next());
193 } else {
194 if self.head != Some(node) {
195 return None;
196 }
197
198 self.head = L::pointers(node).as_ref().get_next();
199 }
200
201 if let Some(next) = L::pointers(node).as_ref().get_next() {
202 debug_assert_eq!(L::pointers(next).as_ref().get_prev(), Some(node));
203 L::pointers(next)
204 .as_mut()
205 .set_prev(L::pointers(node).as_ref().get_prev());
206 } else {
207 // This might be the last item in the list
208 if self.tail != Some(node) {
209 return None;
210 }
211
212 self.tail = L::pointers(node).as_ref().get_prev();
213 }
214
215 L::pointers(node).as_mut().set_next(None);
216 L::pointers(node).as_mut().set_prev(None);
217
218 Some(L::from_raw(node))
219 }
220}
221
222impl<L: Link> fmt::Debug for LinkedList<L, L::Target> {
223 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
224 f&mut DebugStruct<'_, '_>.debug_struct("LinkedList")
225 .field("head", &self.head)
226 .field(name:"tail", &self.tail)
227 .finish()
228 }
229}
230
231#[cfg(any(
232 feature = "fs",
233 feature = "rt",
234 all(unix, feature = "process"),
235 feature = "signal",
236 feature = "sync",
237))]
238impl<L: Link> LinkedList<L, L::Target> {
239 pub(crate) fn last(&self) -> Option<&L::Target> {
240 let tail: &NonNull<::Target> = self.tail.as_ref()?;
241 unsafe { Some(&*tail.as_ptr()) }
242 }
243}
244
245impl<L: Link> Default for LinkedList<L, L::Target> {
246 fn default() -> Self {
247 Self::new()
248 }
249}
250
251// ===== impl DrainFilter =====
252
253cfg_io_driver_impl! {
254 pub(crate) struct DrainFilter<'a, T: Link, F> {
255 list: &'a mut LinkedList<T, T::Target>,
256 filter: F,
257 curr: Option<NonNull<T::Target>>,
258 }
259
260 impl<T: Link> LinkedList<T, T::Target> {
261 pub(crate) fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
262 where
263 F: FnMut(&T::Target) -> bool,
264 {
265 let curr = self.head;
266 DrainFilter {
267 curr,
268 filter,
269 list: self,
270 }
271 }
272 }
273
274 impl<'a, T, F> Iterator for DrainFilter<'a, T, F>
275 where
276 T: Link,
277 F: FnMut(&T::Target) -> bool,
278 {
279 type Item = T::Handle;
280
281 fn next(&mut self) -> Option<Self::Item> {
282 while let Some(curr) = self.curr {
283 // safety: the pointer references data contained by the list
284 self.curr = unsafe { T::pointers(curr).as_ref() }.get_next();
285
286 // safety: the value is still owned by the linked list.
287 if (self.filter)(unsafe { &mut *curr.as_ptr() }) {
288 return unsafe { self.list.remove(curr) };
289 }
290 }
291
292 None
293 }
294 }
295}
296
297cfg_taskdump! {
298 impl<T: Link> LinkedList<T, T::Target> {
299 pub(crate) fn for_each<F>(&mut self, mut f: F)
300 where
301 F: FnMut(&T::Handle),
302 {
303 let mut next = self.head;
304
305 while let Some(curr) = next {
306 unsafe {
307 let handle = ManuallyDrop::new(T::from_raw(curr));
308 f(&handle);
309 next = T::pointers(curr).as_ref().get_next();
310 }
311 }
312 }
313 }
314}
315
316// ===== impl GuardedLinkedList =====
317
318feature! {
319 #![any(
320 feature = "process",
321 feature = "sync",
322 feature = "rt",
323 feature = "signal",
324 )]
325
326 /// An intrusive linked list, but instead of keeping pointers to the head
327 /// and tail nodes, it uses a special guard node linked with those nodes.
328 /// It means that the list is circular and every pointer of a node from
329 /// the list is not `None`, including pointers from the guard node.
330 ///
331 /// If a list is empty, then both pointers of the guard node are pointing
332 /// at the guard node itself.
333 pub(crate) struct GuardedLinkedList<L, T> {
334 /// Pointer to the guard node.
335 guard: NonNull<T>,
336
337 /// Node type marker.
338 _marker: PhantomData<*const L>,
339 }
340
341 impl<U, L: Link<Handle = NonNull<U>>> LinkedList<L, L::Target> {
342 /// Turns a linked list into the guarded version by linking the guard node
343 /// with the head and tail nodes. Like with other nodes, you should guarantee
344 /// that the guard node is pinned in memory.
345 pub(crate) fn into_guarded(self, guard_handle: L::Handle) -> GuardedLinkedList<L, L::Target> {
346 // `guard_handle` is a NonNull pointer, we don't have to care about dropping it.
347 let guard = L::as_raw(&guard_handle);
348
349 unsafe {
350 if let Some(head) = self.head {
351 debug_assert!(L::pointers(head).as_ref().get_prev().is_none());
352 L::pointers(head).as_mut().set_prev(Some(guard));
353 L::pointers(guard).as_mut().set_next(Some(head));
354
355 // The list is not empty, so the tail cannot be `None`.
356 let tail = self.tail.unwrap();
357 debug_assert!(L::pointers(tail).as_ref().get_next().is_none());
358 L::pointers(tail).as_mut().set_next(Some(guard));
359 L::pointers(guard).as_mut().set_prev(Some(tail));
360 } else {
361 // The list is empty.
362 L::pointers(guard).as_mut().set_prev(Some(guard));
363 L::pointers(guard).as_mut().set_next(Some(guard));
364 }
365 }
366
367 GuardedLinkedList { guard, _marker: PhantomData }
368 }
369 }
370
371 impl<L: Link> GuardedLinkedList<L, L::Target> {
372 fn tail(&self) -> Option<NonNull<L::Target>> {
373 let tail_ptr = unsafe {
374 L::pointers(self.guard).as_ref().get_prev().unwrap()
375 };
376
377 // Compare the tail pointer with the address of the guard node itself.
378 // If the guard points at itself, then there are no other nodes and
379 // the list is considered empty.
380 if tail_ptr != self.guard {
381 Some(tail_ptr)
382 } else {
383 None
384 }
385 }
386
387 /// Removes the last element from a list and returns it, or None if it is
388 /// empty.
389 pub(crate) fn pop_back(&mut self) -> Option<L::Handle> {
390 unsafe {
391 let last = self.tail()?;
392 let before_last = L::pointers(last).as_ref().get_prev().unwrap();
393
394 L::pointers(self.guard).as_mut().set_prev(Some(before_last));
395 L::pointers(before_last).as_mut().set_next(Some(self.guard));
396
397 L::pointers(last).as_mut().set_prev(None);
398 L::pointers(last).as_mut().set_next(None);
399
400 Some(L::from_raw(last))
401 }
402 }
403 }
404}
405
406// ===== impl Pointers =====
407
408impl<T> Pointers<T> {
409 /// Create a new set of empty pointers
410 pub(crate) fn new() -> Pointers<T> {
411 Pointers {
412 inner: UnsafeCell::new(PointersInner {
413 prev: None,
414 next: None,
415 _pin: PhantomPinned,
416 }),
417 }
418 }
419
420 pub(crate) fn get_prev(&self) -> Option<NonNull<T>> {
421 // SAFETY: prev is the first field in PointersInner, which is #[repr(C)].
422 unsafe {
423 let inner = self.inner.get();
424 let prev = inner as *const Option<NonNull<T>>;
425 ptr::read(prev)
426 }
427 }
428 pub(crate) fn get_next(&self) -> Option<NonNull<T>> {
429 // SAFETY: next is the second field in PointersInner, which is #[repr(C)].
430 unsafe {
431 let inner = self.inner.get();
432 let prev = inner as *const Option<NonNull<T>>;
433 let next = prev.add(1);
434 ptr::read(next)
435 }
436 }
437
438 fn set_prev(&mut self, value: Option<NonNull<T>>) {
439 // SAFETY: prev is the first field in PointersInner, which is #[repr(C)].
440 unsafe {
441 let inner = self.inner.get();
442 let prev = inner as *mut Option<NonNull<T>>;
443 ptr::write(prev, value);
444 }
445 }
446 fn set_next(&mut self, value: Option<NonNull<T>>) {
447 // SAFETY: next is the second field in PointersInner, which is #[repr(C)].
448 unsafe {
449 let inner = self.inner.get();
450 let prev = inner as *mut Option<NonNull<T>>;
451 let next = prev.add(1);
452 ptr::write(next, value);
453 }
454 }
455}
456
457impl<T> fmt::Debug for Pointers<T> {
458 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
459 let prev: Option> = self.get_prev();
460 let next: Option> = self.get_next();
461 f&mut DebugStruct<'_, '_>.debug_struct("Pointers")
462 .field("prev", &prev)
463 .field(name:"next", &next)
464 .finish()
465 }
466}
467
468#[cfg(any(test, fuzzing))]
469#[cfg(not(loom))]
470pub(crate) mod tests {
471 use super::*;
472
473 use std::pin::Pin;
474
475 #[derive(Debug)]
476 #[repr(C)]
477 struct Entry {
478 pointers: Pointers<Entry>,
479 val: i32,
480 }
481
482 unsafe impl<'a> Link for &'a Entry {
483 type Handle = Pin<&'a Entry>;
484 type Target = Entry;
485
486 fn as_raw(handle: &Pin<&'_ Entry>) -> NonNull<Entry> {
487 NonNull::from(handle.get_ref())
488 }
489
490 unsafe fn from_raw(ptr: NonNull<Entry>) -> Pin<&'a Entry> {
491 Pin::new_unchecked(&*ptr.as_ptr())
492 }
493
494 unsafe fn pointers(target: NonNull<Entry>) -> NonNull<Pointers<Entry>> {
495 target.cast()
496 }
497 }
498
499 fn entry(val: i32) -> Pin<Box<Entry>> {
500 Box::pin(Entry {
501 pointers: Pointers::new(),
502 val,
503 })
504 }
505
506 fn ptr(r: &Pin<Box<Entry>>) -> NonNull<Entry> {
507 r.as_ref().get_ref().into()
508 }
509
510 fn collect_list(list: &mut LinkedList<&'_ Entry, <&'_ Entry as Link>::Target>) -> Vec<i32> {
511 let mut ret = vec![];
512
513 while let Some(entry) = list.pop_back() {
514 ret.push(entry.val);
515 }
516
517 ret
518 }
519
520 fn push_all<'a>(
521 list: &mut LinkedList<&'a Entry, <&'_ Entry as Link>::Target>,
522 entries: &[Pin<&'a Entry>],
523 ) {
524 for entry in entries.iter() {
525 list.push_front(*entry);
526 }
527 }
528
529 #[cfg(test)]
530 macro_rules! assert_clean {
531 ($e:ident) => {{
532 assert!($e.pointers.get_next().is_none());
533 assert!($e.pointers.get_prev().is_none());
534 }};
535 }
536
537 #[cfg(test)]
538 macro_rules! assert_ptr_eq {
539 ($a:expr, $b:expr) => {{
540 // Deal with mapping a Pin<&mut T> -> Option<NonNull<T>>
541 assert_eq!(Some($a.as_ref().get_ref().into()), $b)
542 }};
543 }
544
545 #[test]
546 fn const_new() {
547 const _: LinkedList<&Entry, <&Entry as Link>::Target> = LinkedList::new();
548 }
549
550 #[test]
551 fn push_and_drain() {
552 let a = entry(5);
553 let b = entry(7);
554 let c = entry(31);
555
556 let mut list = LinkedList::new();
557 assert!(list.is_empty());
558
559 list.push_front(a.as_ref());
560 assert!(!list.is_empty());
561 list.push_front(b.as_ref());
562 list.push_front(c.as_ref());
563
564 let items: Vec<i32> = collect_list(&mut list);
565 assert_eq!([5, 7, 31].to_vec(), items);
566
567 assert!(list.is_empty());
568 }
569
570 #[test]
571 fn push_pop_push_pop() {
572 let a = entry(5);
573 let b = entry(7);
574
575 let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new();
576
577 list.push_front(a.as_ref());
578
579 let entry = list.pop_back().unwrap();
580 assert_eq!(5, entry.val);
581 assert!(list.is_empty());
582
583 list.push_front(b.as_ref());
584
585 let entry = list.pop_back().unwrap();
586 assert_eq!(7, entry.val);
587
588 assert!(list.is_empty());
589 assert!(list.pop_back().is_none());
590 }
591
592 #[test]
593 fn remove_by_address() {
594 let a = entry(5);
595 let b = entry(7);
596 let c = entry(31);
597
598 unsafe {
599 // Remove first
600 let mut list = LinkedList::new();
601
602 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
603 assert!(list.remove(ptr(&a)).is_some());
604 assert_clean!(a);
605 // `a` should be no longer there and can't be removed twice
606 assert!(list.remove(ptr(&a)).is_none());
607 assert!(!list.is_empty());
608
609 assert!(list.remove(ptr(&b)).is_some());
610 assert_clean!(b);
611 // `b` should be no longer there and can't be removed twice
612 assert!(list.remove(ptr(&b)).is_none());
613 assert!(!list.is_empty());
614
615 assert!(list.remove(ptr(&c)).is_some());
616 assert_clean!(c);
617 // `b` should be no longer there and can't be removed twice
618 assert!(list.remove(ptr(&c)).is_none());
619 assert!(list.is_empty());
620 }
621
622 unsafe {
623 // Remove middle
624 let mut list = LinkedList::new();
625
626 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
627
628 assert!(list.remove(ptr(&a)).is_some());
629 assert_clean!(a);
630
631 assert_ptr_eq!(b, list.head);
632 assert_ptr_eq!(c, b.pointers.get_next());
633 assert_ptr_eq!(b, c.pointers.get_prev());
634
635 let items = collect_list(&mut list);
636 assert_eq!([31, 7].to_vec(), items);
637 }
638
639 unsafe {
640 // Remove middle
641 let mut list = LinkedList::new();
642
643 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
644
645 assert!(list.remove(ptr(&b)).is_some());
646 assert_clean!(b);
647
648 assert_ptr_eq!(c, a.pointers.get_next());
649 assert_ptr_eq!(a, c.pointers.get_prev());
650
651 let items = collect_list(&mut list);
652 assert_eq!([31, 5].to_vec(), items);
653 }
654
655 unsafe {
656 // Remove last
657 // Remove middle
658 let mut list = LinkedList::new();
659
660 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
661
662 assert!(list.remove(ptr(&c)).is_some());
663 assert_clean!(c);
664
665 assert!(b.pointers.get_next().is_none());
666 assert_ptr_eq!(b, list.tail);
667
668 let items = collect_list(&mut list);
669 assert_eq!([7, 5].to_vec(), items);
670 }
671
672 unsafe {
673 // Remove first of two
674 let mut list = LinkedList::new();
675
676 push_all(&mut list, &[b.as_ref(), a.as_ref()]);
677
678 assert!(list.remove(ptr(&a)).is_some());
679
680 assert_clean!(a);
681
682 // a should be no longer there and can't be removed twice
683 assert!(list.remove(ptr(&a)).is_none());
684
685 assert_ptr_eq!(b, list.head);
686 assert_ptr_eq!(b, list.tail);
687
688 assert!(b.pointers.get_next().is_none());
689 assert!(b.pointers.get_prev().is_none());
690
691 let items = collect_list(&mut list);
692 assert_eq!([7].to_vec(), items);
693 }
694
695 unsafe {
696 // Remove last of two
697 let mut list = LinkedList::new();
698
699 push_all(&mut list, &[b.as_ref(), a.as_ref()]);
700
701 assert!(list.remove(ptr(&b)).is_some());
702
703 assert_clean!(b);
704
705 assert_ptr_eq!(a, list.head);
706 assert_ptr_eq!(a, list.tail);
707
708 assert!(a.pointers.get_next().is_none());
709 assert!(a.pointers.get_prev().is_none());
710
711 let items = collect_list(&mut list);
712 assert_eq!([5].to_vec(), items);
713 }
714
715 unsafe {
716 // Remove last item
717 let mut list = LinkedList::new();
718
719 push_all(&mut list, &[a.as_ref()]);
720
721 assert!(list.remove(ptr(&a)).is_some());
722 assert_clean!(a);
723
724 assert!(list.head.is_none());
725 assert!(list.tail.is_none());
726 let items = collect_list(&mut list);
727 assert!(items.is_empty());
728 }
729
730 unsafe {
731 // Remove missing
732 let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new();
733
734 list.push_front(b.as_ref());
735 list.push_front(a.as_ref());
736
737 assert!(list.remove(ptr(&c)).is_none());
738 }
739 }
740
741 /// This is a fuzz test. You run it by entering `cargo fuzz run fuzz_linked_list` in CLI in `/tokio/` module.
742 #[cfg(fuzzing)]
743 pub fn fuzz_linked_list(ops: &[u8]) {
744 enum Op {
745 Push,
746 Pop,
747 Remove(usize),
748 }
749 use std::collections::VecDeque;
750
751 let ops = ops
752 .iter()
753 .map(|i| match i % 3u8 {
754 0 => Op::Push,
755 1 => Op::Pop,
756 2 => Op::Remove((i / 3u8) as usize),
757 _ => unreachable!(),
758 })
759 .collect::<Vec<_>>();
760
761 let mut ll = LinkedList::<&Entry, <&Entry as Link>::Target>::new();
762 let mut reference = VecDeque::new();
763
764 let entries: Vec<_> = (0..ops.len()).map(|i| entry(i as i32)).collect();
765
766 for (i, op) in ops.iter().enumerate() {
767 match op {
768 Op::Push => {
769 reference.push_front(i as i32);
770 assert_eq!(entries[i].val, i as i32);
771
772 ll.push_front(entries[i].as_ref());
773 }
774 Op::Pop => {
775 if reference.is_empty() {
776 assert!(ll.is_empty());
777 continue;
778 }
779
780 let v = reference.pop_back();
781 assert_eq!(v, ll.pop_back().map(|v| v.val));
782 }
783 Op::Remove(n) => {
784 if reference.is_empty() {
785 assert!(ll.is_empty());
786 continue;
787 }
788
789 let idx = n % reference.len();
790 let expect = reference.remove(idx).unwrap();
791
792 unsafe {
793 let entry = ll.remove(ptr(&entries[expect as usize])).unwrap();
794 assert_eq!(expect, entry.val);
795 }
796 }
797 }
798 }
799 }
800}
801