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// ===== impl CountedLinkedList ====
232
233// Delegates operations to the base LinkedList implementation, and adds a counter to the elements
234// in the list.
235pub(crate) struct CountedLinkedList<L: Link, T> {
236 list: LinkedList<L, T>,
237 count: usize,
238}
239
240impl<L: Link> CountedLinkedList<L, L::Target> {
241 pub(crate) fn new() -> CountedLinkedList<L, L::Target> {
242 CountedLinkedList {
243 list: LinkedList::new(),
244 count: 0,
245 }
246 }
247
248 pub(crate) fn push_front(&mut self, val: L::Handle) {
249 self.list.push_front(val);
250 self.count += 1;
251 }
252
253 pub(crate) fn pop_back(&mut self) -> Option<L::Handle> {
254 let val = self.list.pop_back();
255 if val.is_some() {
256 self.count -= 1;
257 }
258 val
259 }
260
261 pub(crate) fn is_empty(&self) -> bool {
262 self.list.is_empty()
263 }
264
265 pub(crate) unsafe fn remove(&mut self, node: NonNull<L::Target>) -> Option<L::Handle> {
266 let val = self.list.remove(node);
267 if val.is_some() {
268 self.count -= 1;
269 }
270 val
271 }
272
273 pub(crate) fn count(&self) -> usize {
274 self.count
275 }
276}
277
278#[cfg(any(
279 feature = "fs",
280 feature = "rt",
281 all(unix, feature = "process"),
282 feature = "signal",
283 feature = "sync",
284))]
285impl<L: Link> LinkedList<L, L::Target> {
286 pub(crate) fn last(&self) -> Option<&L::Target> {
287 let tail: &NonNull<::Target> = self.tail.as_ref()?;
288 unsafe { Some(&*tail.as_ptr()) }
289 }
290}
291
292impl<L: Link> Default for LinkedList<L, L::Target> {
293 fn default() -> Self {
294 Self::new()
295 }
296}
297
298// ===== impl DrainFilter =====
299
300cfg_io_readiness! {
301 pub(crate) struct DrainFilter<'a, T: Link, F> {
302 list: &'a mut LinkedList<T, T::Target>,
303 filter: F,
304 curr: Option<NonNull<T::Target>>,
305 }
306
307 impl<T: Link> LinkedList<T, T::Target> {
308 pub(crate) fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F>
309 where
310 F: FnMut(&mut T::Target) -> bool,
311 {
312 let curr = self.head;
313 DrainFilter {
314 curr,
315 filter,
316 list: self,
317 }
318 }
319 }
320
321 impl<'a, T, F> Iterator for DrainFilter<'a, T, F>
322 where
323 T: Link,
324 F: FnMut(&mut T::Target) -> bool,
325 {
326 type Item = T::Handle;
327
328 fn next(&mut self) -> Option<Self::Item> {
329 while let Some(curr) = self.curr {
330 // safety: the pointer references data contained by the list
331 self.curr = unsafe { T::pointers(curr).as_ref() }.get_next();
332
333 // safety: the value is still owned by the linked list.
334 if (self.filter)(unsafe { &mut *curr.as_ptr() }) {
335 return unsafe { self.list.remove(curr) };
336 }
337 }
338
339 None
340 }
341 }
342}
343
344cfg_taskdump! {
345 impl<T: Link> CountedLinkedList<T, T::Target> {
346 pub(crate) fn for_each<F>(&mut self, f: F)
347 where
348 F: FnMut(&T::Handle),
349 {
350 self.list.for_each(f)
351 }
352 }
353
354 impl<T: Link> LinkedList<T, T::Target> {
355 pub(crate) fn for_each<F>(&mut self, mut f: F)
356 where
357 F: FnMut(&T::Handle),
358 {
359 use std::mem::ManuallyDrop;
360
361 let mut next = self.head;
362
363 while let Some(curr) = next {
364 unsafe {
365 let handle = ManuallyDrop::new(T::from_raw(curr));
366 f(&handle);
367 next = T::pointers(curr).as_ref().get_next();
368 }
369 }
370 }
371 }
372}
373
374// ===== impl GuardedLinkedList =====
375
376feature! {
377 #![any(
378 feature = "process",
379 feature = "sync",
380 feature = "rt",
381 feature = "signal",
382 )]
383
384 /// An intrusive linked list, but instead of keeping pointers to the head
385 /// and tail nodes, it uses a special guard node linked with those nodes.
386 /// It means that the list is circular and every pointer of a node from
387 /// the list is not `None`, including pointers from the guard node.
388 ///
389 /// If a list is empty, then both pointers of the guard node are pointing
390 /// at the guard node itself.
391 pub(crate) struct GuardedLinkedList<L, T> {
392 /// Pointer to the guard node.
393 guard: NonNull<T>,
394
395 /// Node type marker.
396 _marker: PhantomData<*const L>,
397 }
398
399 impl<U, L: Link<Handle = NonNull<U>>> LinkedList<L, L::Target> {
400 /// Turns a linked list into the guarded version by linking the guard node
401 /// with the head and tail nodes. Like with other nodes, you should guarantee
402 /// that the guard node is pinned in memory.
403 pub(crate) fn into_guarded(self, guard_handle: L::Handle) -> GuardedLinkedList<L, L::Target> {
404 // `guard_handle` is a NonNull pointer, we don't have to care about dropping it.
405 let guard = L::as_raw(&guard_handle);
406
407 unsafe {
408 if let Some(head) = self.head {
409 debug_assert!(L::pointers(head).as_ref().get_prev().is_none());
410 L::pointers(head).as_mut().set_prev(Some(guard));
411 L::pointers(guard).as_mut().set_next(Some(head));
412
413 // The list is not empty, so the tail cannot be `None`.
414 let tail = self.tail.unwrap();
415 debug_assert!(L::pointers(tail).as_ref().get_next().is_none());
416 L::pointers(tail).as_mut().set_next(Some(guard));
417 L::pointers(guard).as_mut().set_prev(Some(tail));
418 } else {
419 // The list is empty.
420 L::pointers(guard).as_mut().set_prev(Some(guard));
421 L::pointers(guard).as_mut().set_next(Some(guard));
422 }
423 }
424
425 GuardedLinkedList { guard, _marker: PhantomData }
426 }
427 }
428
429 impl<L: Link> GuardedLinkedList<L, L::Target> {
430 fn tail(&self) -> Option<NonNull<L::Target>> {
431 let tail_ptr = unsafe {
432 L::pointers(self.guard).as_ref().get_prev().unwrap()
433 };
434
435 // Compare the tail pointer with the address of the guard node itself.
436 // If the guard points at itself, then there are no other nodes and
437 // the list is considered empty.
438 if tail_ptr != self.guard {
439 Some(tail_ptr)
440 } else {
441 None
442 }
443 }
444
445 /// Removes the last element from a list and returns it, or None if it is
446 /// empty.
447 pub(crate) fn pop_back(&mut self) -> Option<L::Handle> {
448 unsafe {
449 let last = self.tail()?;
450 let before_last = L::pointers(last).as_ref().get_prev().unwrap();
451
452 L::pointers(self.guard).as_mut().set_prev(Some(before_last));
453 L::pointers(before_last).as_mut().set_next(Some(self.guard));
454
455 L::pointers(last).as_mut().set_prev(None);
456 L::pointers(last).as_mut().set_next(None);
457
458 Some(L::from_raw(last))
459 }
460 }
461 }
462}
463
464// ===== impl Pointers =====
465
466impl<T> Pointers<T> {
467 /// Create a new set of empty pointers
468 pub(crate) fn new() -> Pointers<T> {
469 Pointers {
470 inner: UnsafeCell::new(PointersInner {
471 prev: None,
472 next: None,
473 _pin: PhantomPinned,
474 }),
475 }
476 }
477
478 pub(crate) fn get_prev(&self) -> Option<NonNull<T>> {
479 // SAFETY: prev is the first field in PointersInner, which is #[repr(C)].
480 unsafe {
481 let inner = self.inner.get();
482 let prev = inner as *const Option<NonNull<T>>;
483 ptr::read(prev)
484 }
485 }
486 pub(crate) fn get_next(&self) -> Option<NonNull<T>> {
487 // SAFETY: next is the second field in PointersInner, which is #[repr(C)].
488 unsafe {
489 let inner = self.inner.get();
490 let prev = inner as *const Option<NonNull<T>>;
491 let next = prev.add(1);
492 ptr::read(next)
493 }
494 }
495
496 fn set_prev(&mut self, value: Option<NonNull<T>>) {
497 // SAFETY: prev is the first field in PointersInner, which is #[repr(C)].
498 unsafe {
499 let inner = self.inner.get();
500 let prev = inner as *mut Option<NonNull<T>>;
501 ptr::write(prev, value);
502 }
503 }
504 fn set_next(&mut self, value: Option<NonNull<T>>) {
505 // SAFETY: next is the second field in PointersInner, which is #[repr(C)].
506 unsafe {
507 let inner = self.inner.get();
508 let prev = inner as *mut Option<NonNull<T>>;
509 let next = prev.add(1);
510 ptr::write(next, value);
511 }
512 }
513}
514
515impl<T> fmt::Debug for Pointers<T> {
516 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
517 let prev: Option> = self.get_prev();
518 let next: Option> = self.get_next();
519 f&mut DebugStruct<'_, '_>.debug_struct("Pointers")
520 .field("prev", &prev)
521 .field(name:"next", &next)
522 .finish()
523 }
524}
525
526#[cfg(any(test, fuzzing))]
527#[cfg(not(loom))]
528pub(crate) mod tests {
529 use super::*;
530
531 use std::pin::Pin;
532
533 #[derive(Debug)]
534 #[repr(C)]
535 struct Entry {
536 pointers: Pointers<Entry>,
537 val: i32,
538 }
539
540 unsafe impl<'a> Link for &'a Entry {
541 type Handle = Pin<&'a Entry>;
542 type Target = Entry;
543
544 fn as_raw(handle: &Pin<&'_ Entry>) -> NonNull<Entry> {
545 NonNull::from(handle.get_ref())
546 }
547
548 unsafe fn from_raw(ptr: NonNull<Entry>) -> Pin<&'a Entry> {
549 Pin::new_unchecked(&*ptr.as_ptr())
550 }
551
552 unsafe fn pointers(target: NonNull<Entry>) -> NonNull<Pointers<Entry>> {
553 target.cast()
554 }
555 }
556
557 fn entry(val: i32) -> Pin<Box<Entry>> {
558 Box::pin(Entry {
559 pointers: Pointers::new(),
560 val,
561 })
562 }
563
564 fn ptr(r: &Pin<Box<Entry>>) -> NonNull<Entry> {
565 r.as_ref().get_ref().into()
566 }
567
568 fn collect_list(list: &mut LinkedList<&'_ Entry, <&'_ Entry as Link>::Target>) -> Vec<i32> {
569 let mut ret = vec![];
570
571 while let Some(entry) = list.pop_back() {
572 ret.push(entry.val);
573 }
574
575 ret
576 }
577
578 fn push_all<'a>(
579 list: &mut LinkedList<&'a Entry, <&'_ Entry as Link>::Target>,
580 entries: &[Pin<&'a Entry>],
581 ) {
582 for entry in entries.iter() {
583 list.push_front(*entry);
584 }
585 }
586
587 #[cfg(test)]
588 macro_rules! assert_clean {
589 ($e:ident) => {{
590 assert!($e.pointers.get_next().is_none());
591 assert!($e.pointers.get_prev().is_none());
592 }};
593 }
594
595 #[cfg(test)]
596 macro_rules! assert_ptr_eq {
597 ($a:expr, $b:expr) => {{
598 // Deal with mapping a Pin<&mut T> -> Option<NonNull<T>>
599 assert_eq!(Some($a.as_ref().get_ref().into()), $b)
600 }};
601 }
602
603 #[test]
604 fn const_new() {
605 const _: LinkedList<&Entry, <&Entry as Link>::Target> = LinkedList::new();
606 }
607
608 #[test]
609 fn push_and_drain() {
610 let a = entry(5);
611 let b = entry(7);
612 let c = entry(31);
613
614 let mut list = LinkedList::new();
615 assert!(list.is_empty());
616
617 list.push_front(a.as_ref());
618 assert!(!list.is_empty());
619 list.push_front(b.as_ref());
620 list.push_front(c.as_ref());
621
622 let items: Vec<i32> = collect_list(&mut list);
623 assert_eq!([5, 7, 31].to_vec(), items);
624
625 assert!(list.is_empty());
626 }
627
628 #[test]
629 fn push_pop_push_pop() {
630 let a = entry(5);
631 let b = entry(7);
632
633 let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new();
634
635 list.push_front(a.as_ref());
636
637 let entry = list.pop_back().unwrap();
638 assert_eq!(5, entry.val);
639 assert!(list.is_empty());
640
641 list.push_front(b.as_ref());
642
643 let entry = list.pop_back().unwrap();
644 assert_eq!(7, entry.val);
645
646 assert!(list.is_empty());
647 assert!(list.pop_back().is_none());
648 }
649
650 #[test]
651 fn remove_by_address() {
652 let a = entry(5);
653 let b = entry(7);
654 let c = entry(31);
655
656 unsafe {
657 // Remove first
658 let mut list = LinkedList::new();
659
660 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
661 assert!(list.remove(ptr(&a)).is_some());
662 assert_clean!(a);
663 // `a` should be no longer there and can't be removed twice
664 assert!(list.remove(ptr(&a)).is_none());
665 assert!(!list.is_empty());
666
667 assert!(list.remove(ptr(&b)).is_some());
668 assert_clean!(b);
669 // `b` should be no longer there and can't be removed twice
670 assert!(list.remove(ptr(&b)).is_none());
671 assert!(!list.is_empty());
672
673 assert!(list.remove(ptr(&c)).is_some());
674 assert_clean!(c);
675 // `b` should be no longer there and can't be removed twice
676 assert!(list.remove(ptr(&c)).is_none());
677 assert!(list.is_empty());
678 }
679
680 unsafe {
681 // Remove middle
682 let mut list = LinkedList::new();
683
684 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
685
686 assert!(list.remove(ptr(&a)).is_some());
687 assert_clean!(a);
688
689 assert_ptr_eq!(b, list.head);
690 assert_ptr_eq!(c, b.pointers.get_next());
691 assert_ptr_eq!(b, c.pointers.get_prev());
692
693 let items = collect_list(&mut list);
694 assert_eq!([31, 7].to_vec(), items);
695 }
696
697 unsafe {
698 // Remove middle
699 let mut list = LinkedList::new();
700
701 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
702
703 assert!(list.remove(ptr(&b)).is_some());
704 assert_clean!(b);
705
706 assert_ptr_eq!(c, a.pointers.get_next());
707 assert_ptr_eq!(a, c.pointers.get_prev());
708
709 let items = collect_list(&mut list);
710 assert_eq!([31, 5].to_vec(), items);
711 }
712
713 unsafe {
714 // Remove last
715 // Remove middle
716 let mut list = LinkedList::new();
717
718 push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
719
720 assert!(list.remove(ptr(&c)).is_some());
721 assert_clean!(c);
722
723 assert!(b.pointers.get_next().is_none());
724 assert_ptr_eq!(b, list.tail);
725
726 let items = collect_list(&mut list);
727 assert_eq!([7, 5].to_vec(), items);
728 }
729
730 unsafe {
731 // Remove first of two
732 let mut list = LinkedList::new();
733
734 push_all(&mut list, &[b.as_ref(), a.as_ref()]);
735
736 assert!(list.remove(ptr(&a)).is_some());
737
738 assert_clean!(a);
739
740 // a should be no longer there and can't be removed twice
741 assert!(list.remove(ptr(&a)).is_none());
742
743 assert_ptr_eq!(b, list.head);
744 assert_ptr_eq!(b, list.tail);
745
746 assert!(b.pointers.get_next().is_none());
747 assert!(b.pointers.get_prev().is_none());
748
749 let items = collect_list(&mut list);
750 assert_eq!([7].to_vec(), items);
751 }
752
753 unsafe {
754 // Remove last of two
755 let mut list = LinkedList::new();
756
757 push_all(&mut list, &[b.as_ref(), a.as_ref()]);
758
759 assert!(list.remove(ptr(&b)).is_some());
760
761 assert_clean!(b);
762
763 assert_ptr_eq!(a, list.head);
764 assert_ptr_eq!(a, list.tail);
765
766 assert!(a.pointers.get_next().is_none());
767 assert!(a.pointers.get_prev().is_none());
768
769 let items = collect_list(&mut list);
770 assert_eq!([5].to_vec(), items);
771 }
772
773 unsafe {
774 // Remove last item
775 let mut list = LinkedList::new();
776
777 push_all(&mut list, &[a.as_ref()]);
778
779 assert!(list.remove(ptr(&a)).is_some());
780 assert_clean!(a);
781
782 assert!(list.head.is_none());
783 assert!(list.tail.is_none());
784 let items = collect_list(&mut list);
785 assert!(items.is_empty());
786 }
787
788 unsafe {
789 // Remove missing
790 let mut list = LinkedList::<&Entry, <&Entry as Link>::Target>::new();
791
792 list.push_front(b.as_ref());
793 list.push_front(a.as_ref());
794
795 assert!(list.remove(ptr(&c)).is_none());
796 }
797 }
798
799 #[test]
800 fn count() {
801 let mut list = CountedLinkedList::<&Entry, <&Entry as Link>::Target>::new();
802 assert_eq!(0, list.count());
803
804 let a = entry(5);
805 let b = entry(7);
806 list.push_front(a.as_ref());
807 list.push_front(b.as_ref());
808 assert_eq!(2, list.count());
809
810 list.pop_back();
811 assert_eq!(1, list.count());
812
813 unsafe {
814 list.remove(ptr(&b));
815 }
816 assert_eq!(0, list.count());
817 }
818
819 /// This is a fuzz test. You run it by entering `cargo fuzz run fuzz_linked_list` in CLI in `/tokio/` module.
820 #[cfg(fuzzing)]
821 pub fn fuzz_linked_list(ops: &[u8]) {
822 enum Op {
823 Push,
824 Pop,
825 Remove(usize),
826 }
827 use std::collections::VecDeque;
828
829 let ops = ops
830 .iter()
831 .map(|i| match i % 3u8 {
832 0 => Op::Push,
833 1 => Op::Pop,
834 2 => Op::Remove((i / 3u8) as usize),
835 _ => unreachable!(),
836 })
837 .collect::<Vec<_>>();
838
839 let mut ll = LinkedList::<&Entry, <&Entry as Link>::Target>::new();
840 let mut reference = VecDeque::new();
841
842 let entries: Vec<_> = (0..ops.len()).map(|i| entry(i as i32)).collect();
843
844 for (i, op) in ops.iter().enumerate() {
845 match op {
846 Op::Push => {
847 reference.push_front(i as i32);
848 assert_eq!(entries[i].val, i as i32);
849
850 ll.push_front(entries[i].as_ref());
851 }
852 Op::Pop => {
853 if reference.is_empty() {
854 assert!(ll.is_empty());
855 continue;
856 }
857
858 let v = reference.pop_back();
859 assert_eq!(v, ll.pop_back().map(|v| v.val));
860 }
861 Op::Remove(n) => {
862 if reference.is_empty() {
863 assert!(ll.is_empty());
864 continue;
865 }
866
867 let idx = n % reference.len();
868 let expect = reference.remove(idx).unwrap();
869
870 unsafe {
871 let entry = ll.remove(ptr(&entries[expect as usize])).unwrap();
872 assert_eq!(expect, entry.val);
873 }
874 }
875 }
876 }
877 }
878}
879