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