1 // Copyright 2016 Amanieu d'Antras
2 // Copyright 2020 Amari Robinson
3 //
4 // Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
5 // http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
6 // http://opensource.org/licenses/MIT>, at your option. This file may not be
7 // copied, modified, or distributed except according to those terms.
8 
9 //! Intrusive doubly-linked list.
10 
11 use core::cell::Cell;
12 use core::fmt;
13 use core::ptr::{null_mut, NonNull};
14 use core::sync::atomic::{AtomicPtr, Ordering};
15 
16 use crate::link_ops::{self, DefaultLinkOps};
17 use crate::pointer_ops::PointerOps;
18 use crate::singly_linked_list::SinglyLinkedListOps;
19 use crate::xor_linked_list::XorLinkedListOps;
20 use crate::Adapter;
21 // Necessary for Rust 1.56 compatability
22 #[allow(unused_imports)]
23 use crate::unchecked_option::UncheckedOptionExt;
24 
25 // =============================================================================
26 // LinkedListOps
27 // =============================================================================
28 
29 /// Link operations for `LinkedList`.
30 pub unsafe trait LinkedListOps: link_ops::LinkOps {
31     /// Returns the "next" link pointer of `ptr`.
32     ///
33     /// # Safety
34     /// An implementation of `next` must not panic.
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>35     unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
36 
37     /// Returns the "prev" link pointer of `ptr`.
38     ///
39     /// # Safety
40     /// An implementation of `prev` must not panic.
prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>41     unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>;
42 
43     /// Sets the "next" link pointer of `ptr`.
44     ///
45     /// # Safety
46     /// An implementation of `set_next` must not panic.
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)47     unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>);
48 
49     /// Sets the "prev" link pointer of `ptr`.
50     ///
51     /// # Safety
52     /// An implementation of `set_prev` must not panic.
set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>)53     unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>);
54 }
55 
56 // =============================================================================
57 // Link
58 // =============================================================================
59 
60 /// Intrusive link that allows an object to be inserted into a
61 /// `LinkedList`.
62 #[repr(align(2))]
63 pub struct Link {
64     next: Cell<Option<NonNull<Link>>>,
65     prev: Cell<Option<NonNull<Link>>>,
66 }
67 
68 // Use a special value to indicate an unlinked node
69 const UNLINKED_MARKER: Option<NonNull<Link>> =
70     unsafe { Some(NonNull::new_unchecked(1 as *mut Link)) };
71 
72 impl Link {
73     /// Creates a new `Link`.
74     #[inline]
new() -> Link75     pub const fn new() -> Link {
76         Link {
77             next: Cell::new(UNLINKED_MARKER),
78             prev: Cell::new(UNLINKED_MARKER),
79         }
80     }
81 
82     /// Checks whether the `Link` is linked into a `LinkedList`.
83     #[inline]
is_linked(&self) -> bool84     pub fn is_linked(&self) -> bool {
85         self.next.get() != UNLINKED_MARKER
86     }
87 
88     /// Forcibly unlinks an object from a `LinkedList`.
89     ///
90     /// # Safety
91     ///
92     /// It is undefined behavior to call this function while still linked into a
93     /// `LinkedList`. The only situation where this function is useful is
94     /// after calling `fast_clear` on a `LinkedList`, since this clears
95     /// the collection without marking the nodes as unlinked.
96     #[inline]
force_unlink(&self)97     pub unsafe fn force_unlink(&self) {
98         self.next.set(UNLINKED_MARKER);
99     }
100 }
101 
102 impl DefaultLinkOps for Link {
103     type Ops = LinkOps;
104 
105     const NEW: Self::Ops = LinkOps;
106 }
107 
108 // An object containing a link can be sent to another thread if it is unlinked.
109 unsafe impl Send for Link {}
110 
111 // Provide an implementation of Clone which simply initializes the new link as
112 // unlinked. This allows structs containing a link to derive Clone.
113 impl Clone for Link {
114     #[inline]
clone(&self) -> Link115     fn clone(&self) -> Link {
116         Link::new()
117     }
118 }
119 
120 // Same as above
121 impl Default for Link {
122     #[inline]
default() -> Link123     fn default() -> Link {
124         Link::new()
125     }
126 }
127 
128 // Provide an implementation of Debug so that structs containing a link can
129 // still derive Debug.
130 impl fmt::Debug for Link {
131     #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result132     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
133         // There isn't anything sensible to print here except whether the link
134         // is currently in a list.
135         if self.is_linked() {
136             write!(f, "linked")
137         } else {
138             write!(f, "unlinked")
139         }
140     }
141 }
142 
143 // =============================================================================
144 // LinkOps
145 // =============================================================================
146 
147 /// Default `LinkOps` implementation for `LinkedList`.
148 #[derive(Clone, Copy, Default)]
149 pub struct LinkOps;
150 
151 unsafe impl link_ops::LinkOps for LinkOps {
152     type LinkPtr = NonNull<Link>;
153 
154     #[inline]
acquire_link(&mut self, ptr: Self::LinkPtr) -> bool155     unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
156         if ptr.as_ref().is_linked() {
157             false
158         } else {
159             ptr.as_ref().next.set(None);
160             true
161         }
162     }
163 
164     #[inline]
release_link(&mut self, ptr: Self::LinkPtr)165     unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
166         ptr.as_ref().next.set(UNLINKED_MARKER);
167     }
168 }
169 
170 unsafe impl LinkedListOps for LinkOps {
171     #[inline]
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>172     unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
173         ptr.as_ref().next.get()
174     }
175 
176     #[inline]
prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>177     unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
178         ptr.as_ref().prev.get()
179     }
180 
181     #[inline]
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)182     unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
183         ptr.as_ref().next.set(next);
184     }
185 
186     #[inline]
set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>)187     unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>) {
188         ptr.as_ref().prev.set(prev);
189     }
190 }
191 
192 unsafe impl SinglyLinkedListOps for LinkOps {
193     #[inline]
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>194     unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
195         ptr.as_ref().next.get()
196     }
197 
198     #[inline]
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)199     unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
200         ptr.as_ref().next.set(next);
201     }
202 }
203 
204 unsafe impl XorLinkedListOps for LinkOps {
205     #[inline]
next( &self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>, ) -> Option<Self::LinkPtr>206     unsafe fn next(
207         &self,
208         ptr: Self::LinkPtr,
209         prev: Option<Self::LinkPtr>,
210     ) -> Option<Self::LinkPtr> {
211         let packed = ptr
212             .as_ref()
213             .next
214             .get()
215             .map(|x| x.as_ptr() as usize)
216             .unwrap_or(0);
217         let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
218         NonNull::new(raw as *mut _)
219     }
220 
221     #[inline]
prev( &self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>, ) -> Option<Self::LinkPtr>222     unsafe fn prev(
223         &self,
224         ptr: Self::LinkPtr,
225         next: Option<Self::LinkPtr>,
226     ) -> Option<Self::LinkPtr> {
227         let packed = ptr
228             .as_ref()
229             .next
230             .get()
231             .map(|x| x.as_ptr() as usize)
232             .unwrap_or(0);
233         let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
234         NonNull::new(raw as *mut _)
235     }
236 
237     #[inline]
set( &mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>, next: Option<Self::LinkPtr>, )238     unsafe fn set(
239         &mut self,
240         ptr: Self::LinkPtr,
241         prev: Option<Self::LinkPtr>,
242         next: Option<Self::LinkPtr>,
243     ) {
244         let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
245             ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
246 
247         let new_next = NonNull::new(new_packed as *mut _);
248         ptr.as_ref().next.set(new_next);
249     }
250 
251     #[inline]
replace_next_or_prev( &mut self, ptr: Self::LinkPtr, old: Option<Self::LinkPtr>, new: Option<Self::LinkPtr>, )252     unsafe fn replace_next_or_prev(
253         &mut self,
254         ptr: Self::LinkPtr,
255         old: Option<Self::LinkPtr>,
256         new: Option<Self::LinkPtr>,
257     ) {
258         let packed = ptr
259             .as_ref()
260             .next
261             .get()
262             .map(|x| x.as_ptr() as usize)
263             .unwrap_or(0);
264         let new_packed = packed
265             ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
266             ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
267 
268         let new_next = NonNull::new(new_packed as *mut _);
269         ptr.as_ref().next.set(new_next);
270     }
271 }
272 
273 // =============================================================================
274 // AtomicLink
275 // =============================================================================
276 
277 /// Intrusive atomic link that allows an object to be inserted into a
278 /// `LinkedList`. This link allows the structure to be shared between threads.
279 #[repr(align(2))]
280 pub struct AtomicLink {
281     next: AtomicPtr<AtomicLink>,
282     prev: Cell<Option<NonNull<AtomicLink>>>,
283 }
284 
285 // Use a special value to indicate an unlinked node
286 const ATOMIC_UNLINKED_MARKER_PTR: *mut AtomicLink = 1 as *mut AtomicLink;
287 
288 // Use a special value to indicate an unlinked node
289 const ATOMIC_UNLINKED_MARKER: Option<NonNull<AtomicLink>> =
290     unsafe { Some(NonNull::new_unchecked(ATOMIC_UNLINKED_MARKER_PTR)) };
291 
292 impl AtomicLink {
293     /// Creates a new `AtomicLink`.
294     #[inline]
new() -> AtomicLink295     pub const fn new() -> AtomicLink {
296         Self {
297             next: AtomicPtr::new(ATOMIC_UNLINKED_MARKER_PTR),
298             prev: Cell::new(ATOMIC_UNLINKED_MARKER),
299         }
300     }
301 
302     /// Checks whether the `AtomicLink` is linked into a `LinkedList`.
303     #[inline]
is_linked(&self) -> bool304     pub fn is_linked(&self) -> bool {
305         self.next.load(Ordering::Relaxed) != ATOMIC_UNLINKED_MARKER_PTR
306     }
307 
308     /// Forcibly unlinks an object from a `LinkedList`.
309     ///
310     /// # Safety
311     ///
312     /// It is undefined behavior to call this function while still linked into a
313     /// `LinkedList`. The only situation where this function is useful is
314     /// after calling `fast_clear` on a `LinkedList`, since this clears
315     /// the collection without marking the nodes as unlinked.
316     #[inline]
force_unlink(&self)317     pub unsafe fn force_unlink(&self) {
318         self.next
319             .store(ATOMIC_UNLINKED_MARKER_PTR, Ordering::Release)
320     }
321 
322     /// Access the `next` pointer in an exclusive context.
323     ///
324     /// # Safety
325     ///
326     /// This can only be called after `acquire_link` has been succesfully called.
327     #[inline]
next_exclusive(&self) -> &Cell<Option<NonNull<AtomicLink>>>328     unsafe fn next_exclusive(&self) -> &Cell<Option<NonNull<AtomicLink>>> {
329         // This is safe because currently AtomicPtr<AtomicLink> has the same representation Cell<Option<NonNull<AtomicLink>>>.
330         core::mem::transmute(&self.next)
331     }
332 }
333 
334 impl DefaultLinkOps for AtomicLink {
335     type Ops = AtomicLinkOps;
336 
337     const NEW: Self::Ops = AtomicLinkOps;
338 }
339 
340 // An object containing a link can be sent to another thread since `acquire_link` is atomic.
341 unsafe impl Send for AtomicLink {}
342 
343 // An object containing a link can be shared between threads since `acquire_link` is atomic.
344 unsafe impl Sync for AtomicLink {}
345 
346 impl Clone for AtomicLink {
347     #[inline]
clone(&self) -> AtomicLink348     fn clone(&self) -> AtomicLink {
349         AtomicLink::new()
350     }
351 }
352 
353 impl Default for AtomicLink {
354     #[inline]
default() -> AtomicLink355     fn default() -> AtomicLink {
356         AtomicLink::new()
357     }
358 }
359 
360 // Provide an implementation of Debug so that structs containing a link can
361 // still derive Debug.
362 impl fmt::Debug for AtomicLink {
363     #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result364     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
365         // There isn't anything sensible to print here except whether the link
366         // is currently in a list.
367         if self.is_linked() {
368             write!(f, "linked")
369         } else {
370             write!(f, "unlinked")
371         }
372     }
373 }
374 
375 // =============================================================================
376 // AtomicLinkOps
377 // =============================================================================
378 
379 /// Default `AtomicLinkOps` implementation for `LinkedList`.
380 #[derive(Clone, Copy, Default)]
381 pub struct AtomicLinkOps;
382 
383 unsafe impl link_ops::LinkOps for AtomicLinkOps {
384     type LinkPtr = NonNull<AtomicLink>;
385 
386     #[inline]
acquire_link(&mut self, ptr: Self::LinkPtr) -> bool387     unsafe fn acquire_link(&mut self, ptr: Self::LinkPtr) -> bool {
388         ptr.as_ref()
389             .next
390             .compare_exchange(
391                 ATOMIC_UNLINKED_MARKER_PTR,
392                 null_mut(),
393                 Ordering::Acquire,
394                 Ordering::Relaxed,
395             )
396             .is_ok()
397     }
398 
399     #[inline]
release_link(&mut self, ptr: Self::LinkPtr)400     unsafe fn release_link(&mut self, ptr: Self::LinkPtr) {
401         ptr.as_ref()
402             .next
403             .store(ATOMIC_UNLINKED_MARKER_PTR, Ordering::Release)
404     }
405 }
406 
407 unsafe impl LinkedListOps for AtomicLinkOps {
408     #[inline]
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>409     unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
410         ptr.as_ref().next_exclusive().get()
411     }
412 
413     #[inline]
prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>414     unsafe fn prev(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
415         ptr.as_ref().prev.get()
416     }
417 
418     #[inline]
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)419     unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
420         ptr.as_ref().next_exclusive().set(next);
421     }
422 
423     #[inline]
set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>)424     unsafe fn set_prev(&mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>) {
425         ptr.as_ref().prev.set(prev);
426     }
427 }
428 
429 unsafe impl SinglyLinkedListOps for AtomicLinkOps {
430     #[inline]
next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr>431     unsafe fn next(&self, ptr: Self::LinkPtr) -> Option<Self::LinkPtr> {
432         ptr.as_ref().next_exclusive().get()
433     }
434 
435     #[inline]
set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>)436     unsafe fn set_next(&mut self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>) {
437         ptr.as_ref().next_exclusive().set(next);
438     }
439 }
440 
441 unsafe impl XorLinkedListOps for AtomicLinkOps {
442     #[inline]
next( &self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>, ) -> Option<Self::LinkPtr>443     unsafe fn next(
444         &self,
445         ptr: Self::LinkPtr,
446         prev: Option<Self::LinkPtr>,
447     ) -> Option<Self::LinkPtr> {
448         let packed = ptr
449             .as_ref()
450             .next_exclusive()
451             .get()
452             .map(|x| x.as_ptr() as usize)
453             .unwrap_or(0);
454         let raw = packed ^ prev.map(|x| x.as_ptr() as usize).unwrap_or(0);
455         NonNull::new(raw as *mut _)
456     }
457 
458     #[inline]
prev( &self, ptr: Self::LinkPtr, next: Option<Self::LinkPtr>, ) -> Option<Self::LinkPtr>459     unsafe fn prev(
460         &self,
461         ptr: Self::LinkPtr,
462         next: Option<Self::LinkPtr>,
463     ) -> Option<Self::LinkPtr> {
464         let packed = ptr
465             .as_ref()
466             .next_exclusive()
467             .get()
468             .map(|x| x.as_ptr() as usize)
469             .unwrap_or(0);
470         let raw = packed ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
471         NonNull::new(raw as *mut _)
472     }
473 
474     #[inline]
set( &mut self, ptr: Self::LinkPtr, prev: Option<Self::LinkPtr>, next: Option<Self::LinkPtr>, )475     unsafe fn set(
476         &mut self,
477         ptr: Self::LinkPtr,
478         prev: Option<Self::LinkPtr>,
479         next: Option<Self::LinkPtr>,
480     ) {
481         let new_packed = prev.map(|x| x.as_ptr() as usize).unwrap_or(0)
482             ^ next.map(|x| x.as_ptr() as usize).unwrap_or(0);
483 
484         let new_next = NonNull::new(new_packed as *mut _);
485         ptr.as_ref().next_exclusive().set(new_next);
486     }
487 
488     #[inline]
replace_next_or_prev( &mut self, ptr: Self::LinkPtr, old: Option<Self::LinkPtr>, new: Option<Self::LinkPtr>, )489     unsafe fn replace_next_or_prev(
490         &mut self,
491         ptr: Self::LinkPtr,
492         old: Option<Self::LinkPtr>,
493         new: Option<Self::LinkPtr>,
494     ) {
495         let packed = ptr
496             .as_ref()
497             .next_exclusive()
498             .get()
499             .map(|x| x.as_ptr() as usize)
500             .unwrap_or(0);
501         let new_packed = packed
502             ^ old.map(|x| x.as_ptr() as usize).unwrap_or(0)
503             ^ new.map(|x| x.as_ptr() as usize).unwrap_or(0);
504 
505         let new_next = NonNull::new(new_packed as *mut _);
506         ptr.as_ref().next_exclusive().set(new_next);
507     }
508 }
509 
510 #[inline]
link_between<T: LinkedListOps>( link_ops: &mut T, ptr: T::LinkPtr, prev: Option<T::LinkPtr>, next: Option<T::LinkPtr>, )511 unsafe fn link_between<T: LinkedListOps>(
512     link_ops: &mut T,
513     ptr: T::LinkPtr,
514     prev: Option<T::LinkPtr>,
515     next: Option<T::LinkPtr>,
516 ) {
517     if let Some(prev) = prev {
518         link_ops.set_next(prev, Some(ptr));
519     }
520     if let Some(next) = next {
521         link_ops.set_prev(next, Some(ptr));
522     }
523     link_ops.set_next(ptr, next);
524     link_ops.set_prev(ptr, prev);
525 }
526 
527 #[inline]
link_after<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr, prev: T::LinkPtr)528 unsafe fn link_after<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr, prev: T::LinkPtr) {
529     link_between(link_ops, ptr, Some(prev), link_ops.next(prev));
530 }
531 
532 #[inline]
link_before<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr, next: T::LinkPtr)533 unsafe fn link_before<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr, next: T::LinkPtr) {
534     link_between(link_ops, ptr, link_ops.prev(next), Some(next));
535 }
536 
537 #[inline]
replace_with<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr, new: T::LinkPtr)538 unsafe fn replace_with<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr, new: T::LinkPtr) {
539     let prev = link_ops.prev(ptr);
540     let next = link_ops.next(ptr);
541 
542     if let Some(prev) = prev {
543         link_ops.set_next(prev, Some(new));
544     }
545     if let Some(next) = next {
546         link_ops.set_prev(next, Some(new));
547     }
548     link_ops.set_next(new, next);
549     link_ops.set_prev(new, prev);
550     link_ops.release_link(ptr);
551 }
552 
553 #[inline]
remove<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr)554 unsafe fn remove<T: LinkedListOps>(link_ops: &mut T, ptr: T::LinkPtr) {
555     let prev = link_ops.prev(ptr);
556     let next = link_ops.next(ptr);
557 
558     if let Some(next) = next {
559         link_ops.set_prev(next, prev);
560     }
561     if let Some(prev) = prev {
562         link_ops.set_next(prev, next);
563     }
564     link_ops.release_link(ptr);
565 }
566 
567 #[inline]
splice<T: LinkedListOps>( link_ops: &mut T, start: T::LinkPtr, end: T::LinkPtr, prev: Option<T::LinkPtr>, next: Option<T::LinkPtr>, )568 unsafe fn splice<T: LinkedListOps>(
569     link_ops: &mut T,
570     start: T::LinkPtr,
571     end: T::LinkPtr,
572     prev: Option<T::LinkPtr>,
573     next: Option<T::LinkPtr>,
574 ) {
575     link_ops.set_prev(start, prev);
576     link_ops.set_next(end, next);
577     if let Some(prev) = prev {
578         link_ops.set_next(prev, Some(start));
579     }
580     if let Some(next) = next {
581         link_ops.set_prev(next, Some(end));
582     }
583 }
584 
585 // =============================================================================
586 // Cursor, CursorMut, CursorOwning
587 // =============================================================================
588 
589 /// A cursor which provides read-only access to a `LinkedList`.
590 pub struct Cursor<'a, A: Adapter>
591 where
592     A::LinkOps: LinkedListOps,
593 {
594     current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
595     list: &'a LinkedList<A>,
596 }
597 
598 impl<'a, A: Adapter> Clone for Cursor<'a, A>
599 where
600     A::LinkOps: LinkedListOps,
601 {
602     #[inline]
603     fn clone(&self) -> Cursor<'a, A> {
604         Cursor {
605             current: self.current,
606             list: self.list,
607         }
608     }
609 }
610 
611 impl<'a, A: Adapter> Cursor<'a, A>
612 where
613     A::LinkOps: LinkedListOps,
614 {
615     /// Checks if the cursor is currently pointing to the null object.
616     #[inline]
617     pub fn is_null(&self) -> bool {
618         self.current.is_none()
619     }
620 
621     /// Returns a reference to the object that the cursor is currently
622     /// pointing to.
623     ///
624     /// This returns `None` if the cursor is currently pointing to the null
625     /// object.
626     #[inline]
627     pub fn get(&self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
628         Some(unsafe { &*self.list.adapter.get_value(self.current?) })
629     }
630 
631     /// Clones and returns the pointer that points to the element that the
632     /// cursor is referencing.
633     ///
634     /// This returns `None` if the cursor is currently pointing to the null
635     /// object.
636     #[inline]
637     pub fn clone_pointer(&self) -> Option<<A::PointerOps as PointerOps>::Pointer>
638     where
639         <A::PointerOps as PointerOps>::Pointer: Clone,
640     {
641         let raw_pointer = unsafe { self.list.adapter.get_value(self.current?) };
642         Some(unsafe {
643             crate::pointer_ops::clone_pointer_from_raw(self.list.adapter.pointer_ops(), raw_pointer)
644         })
645     }
646 
647     /// Moves the cursor to the next element of the `LinkedList`.
648     ///
649     /// If the cursor is pointer to the null object then this will move it to
650     /// the first element of the `LinkedList`. If it is pointing to the
651     /// last element of the `LinkedList` then this will move it to the
652     /// null object.
653     #[inline]
654     pub fn move_next(&mut self) {
655         if let Some(current) = self.current {
656             self.current = unsafe { self.list.adapter.link_ops().next(current) };
657         } else {
658             self.current = self.list.head;
659         }
660     }
661 
662     /// Moves the cursor to the previous element of the `LinkedList`.
663     ///
664     /// If the cursor is pointer to the null object then this will move it to
665     /// the last element of the `LinkedList`. If it is pointing to the first
666     /// element of the `LinkedList` then this will move it to the null object.
667     #[inline]
668     pub fn move_prev(&mut self) {
669         if let Some(current) = self.current {
670             self.current = unsafe { self.list.adapter.link_ops().prev(current) };
671         } else {
672             self.current = self.list.tail;
673         }
674     }
675 
676     /// Returns a cursor pointing to the next element of the `LinkedList`.
677     ///
678     /// If the cursor is pointer to the null object then this will return the
679     /// first element of the `LinkedList`. If it is pointing to the last
680     /// element of the `LinkedList` then this will return a null cursor.
681     #[inline]
682     pub fn peek_next(&self) -> Cursor<'_, A> {
683         let mut next = self.clone();
684         next.move_next();
685         next
686     }
687 
688     /// Returns a cursor pointing to the previous element of the `LinkedList`.
689     ///
690     /// If the cursor is pointer to the null object then this will return the
691     /// last element of the `LinkedList`. If it is pointing to the first
692     /// element of the `LinkedList` then this will return a null cursor.
693     #[inline]
694     pub fn peek_prev(&self) -> Cursor<'_, A> {
695         let mut prev = self.clone();
696         prev.move_prev();
697         prev
698     }
699 }
700 
701 /// A cursor which provides mutable access to a `LinkedList`.
702 pub struct CursorMut<'a, A: Adapter>
703 where
704     A::LinkOps: LinkedListOps,
705 {
706     current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
707     list: &'a mut LinkedList<A>,
708 }
709 
710 impl<'a, A: Adapter> CursorMut<'a, A>
711 where
712     A::LinkOps: LinkedListOps,
713 {
714     /// Checks if the cursor is currently pointing to the null object.
715     #[inline]
716     pub fn is_null(&self) -> bool {
717         self.current.is_none()
718     }
719 
720     /// Returns a reference to the object that the cursor is currently
721     /// pointing to.
722     ///
723     /// This returns None if the cursor is currently pointing to the null
724     /// object.
725     #[inline]
726     pub fn get(&self) -> Option<&<A::PointerOps as PointerOps>::Value> {
727         Some(unsafe { &*self.list.adapter.get_value(self.current?) })
728     }
729 
730     /// Returns a read-only cursor pointing to the current element.
731     ///
732     /// The lifetime of the returned `Cursor` is bound to that of the
733     /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
734     /// `CursorMut` is frozen for the lifetime of the `Cursor`.
735     #[inline]
736     pub fn as_cursor(&self) -> Cursor<'_, A> {
737         Cursor {
738             current: self.current,
739             list: self.list,
740         }
741     }
742 
743     /// Moves the cursor to the next element of the `LinkedList`.
744     ///
745     /// If the cursor is pointer to the null object then this will move it to
746     /// the first element of the `LinkedList`. If it is pointing to the
747     /// last element of the `LinkedList` then this will move it to the
748     /// null object.
749     #[inline]
750     pub fn move_next(&mut self) {
751         if let Some(current) = self.current {
752             self.current = unsafe { self.list.adapter.link_ops().next(current) };
753         } else {
754             self.current = self.list.head;
755         }
756     }
757 
758     /// Moves the cursor to the previous element of the `LinkedList`.
759     ///
760     /// If the cursor is pointer to the null object then this will move it to
761     /// the last element of the `LinkedList`. If it is pointing to the first
762     /// element of the `LinkedList` then this will move it to the null object.
763     #[inline]
764     pub fn move_prev(&mut self) {
765         if let Some(current) = self.current {
766             self.current = unsafe { self.list.adapter.link_ops().prev(current) };
767         } else {
768             self.current = self.list.tail;
769         }
770     }
771 
772     ///Returns a cursor pointing to the next element of the `LinkedList`.
773     ///
774     /// If the cursor is pointer to the null object then this will return the
775     /// first element of the `LinkedList`. If it is pointing to the last
776     /// element of the `LinkedList` then this will return a null cursor.
777     #[inline]
778     pub fn peek_next(&self) -> Cursor<'_, A> {
779         let mut next = self.as_cursor();
780         next.move_next();
781         next
782     }
783 
784     /// Returns a cursor pointing to the previous element of the `LinkedList`.
785     ///
786     /// If the cursor is pointer to the null object then this will return the
787     /// last element of the `LinkedList`. If it is pointing to the first
788     /// element of the `LinkedList` then this will return a null cursor.
789     #[inline]
790     pub fn peek_prev(&self) -> Cursor<'_, A> {
791         let mut prev = self.as_cursor();
792         prev.move_prev();
793         prev
794     }
795 
796     /// Removes the current element from the `LinkedList`.
797     ///
798     /// A pointer to the element that was removed is returned, and the cursor is
799     /// moved to point to the next element in the `LinkedList`.
800     ///
801     /// If the cursor is currently pointing to the null object then no element
802     /// is removed and `None` is returned.
803     #[inline]
804     pub fn remove(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
805         unsafe {
806             if let Some(current) = self.current {
807                 if self.list.head == self.current {
808                     self.list.head = self.list.adapter.link_ops().next(current);
809                 }
810                 if self.list.tail == self.current {
811                     self.list.tail = self.list.adapter.link_ops().prev(current);
812                 }
813                 let next = self.list.adapter.link_ops().next(current);
814                 let result = current;
815                 remove(self.list.adapter.link_ops_mut(), current);
816                 self.current = next;
817                 Some(
818                     self.list
819                         .adapter
820                         .pointer_ops()
821                         .from_raw(self.list.adapter.get_value(result)),
822                 )
823             } else {
824                 None
825             }
826         }
827     }
828 
829     /// Removes the current element from the `LinkedList` and inserts another
830     /// object in its place.
831     ///
832     /// A pointer to the element that was removed is returned, and the cursor is
833     /// modified to point to the newly added element.
834     ///
835     /// If the cursor is currently pointing to the null object then an error is
836     /// returned containing the given `val` parameter.
837     ///
838     /// # Panics
839     ///
840     /// Panics if the new element is already linked to a different intrusive
841     /// collection.
842     #[inline]
843     pub fn replace_with(
844         &mut self,
845         val: <A::PointerOps as PointerOps>::Pointer,
846     ) -> Result<<A::PointerOps as PointerOps>::Pointer, <A::PointerOps as PointerOps>::Pointer>
847     {
848         unsafe {
849             if let Some(current) = self.current {
850                 let new = self.list.node_from_value(val);
851                 if self.list.head == self.current {
852                     self.list.head = Some(new);
853                 }
854                 if self.list.tail == self.current {
855                     self.list.tail = Some(new);
856                 }
857                 let result = current;
858                 replace_with(self.list.adapter.link_ops_mut(), current, new);
859                 self.current = Some(new);
860                 Ok(self
861                     .list
862                     .adapter
863                     .pointer_ops()
864                     .from_raw(self.list.adapter.get_value(result)))
865             } else {
866                 Err(val)
867             }
868         }
869     }
870 
871     /// Inserts a new element into the `LinkedList` after the current one.
872     ///
873     /// If the cursor is pointing at the null object then the new element is
874     /// inserted at the front of the `LinkedList`.
875     ///
876     /// # Panics
877     ///
878     /// Panics if the new element is already linked to a different intrusive
879     /// collection.
880     #[inline]
881     pub fn insert_after(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
882         unsafe {
883             let new = self.list.node_from_value(val);
884             if let Some(current) = self.current {
885                 link_after(self.list.adapter.link_ops_mut(), new, current);
886             } else {
887                 link_between(self.list.adapter.link_ops_mut(), new, None, self.list.head);
888                 self.list.head = Some(new);
889             }
890             if self.list.tail == self.current {
891                 self.list.tail = Some(new);
892             }
893         }
894     }
895 
896     /// Inserts a new element into the `LinkedList` before the current one.
897     ///
898     /// If the cursor is pointing at the null object then the new element is
899     /// inserted at the end of the `LinkedList`.
900     ///
901     /// # Panics
902     ///
903     /// Panics if the new element is already linked to a different intrusive
904     /// collection.
905     #[inline]
906     pub fn insert_before(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
907         unsafe {
908             let new = self.list.node_from_value(val);
909 
910             let link_ops = self.list.adapter.link_ops_mut();
911 
912             if let Some(current) = self.current {
913                 link_before(link_ops, new, current);
914             } else {
915                 link_between(link_ops, new, self.list.tail, None);
916                 self.list.tail = Some(new);
917             }
918             if self.list.head == self.current {
919                 self.list.head = Some(new);
920             }
921         }
922     }
923 
924     /// Inserts the elements from the given `LinkedList` after the current one.
925     ///
926     /// If the cursor is pointing at the null object then the new elements are
927     /// inserted at the start of the `LinkedList`.
928     #[inline]
929     pub fn splice_after(&mut self, mut list: LinkedList<A>) {
930         if !list.is_empty() {
931             unsafe {
932                 let head = list.head.unwrap_unchecked();
933                 let tail = list.tail.unwrap_unchecked();
934 
935                 let link_ops = self.list.adapter.link_ops_mut();
936 
937                 if let Some(current) = self.current {
938                     splice(link_ops, head, tail, Some(current), link_ops.next(current));
939                 } else {
940                     splice(link_ops, head, tail, None, self.list.head);
941                     self.list.head = list.head;
942                 }
943                 if self.list.tail == self.current {
944                     self.list.tail = list.tail;
945                 }
946                 list.head = None;
947                 list.tail = None;
948             }
949         }
950     }
951 
952     /// Moves all element from the given `LinkedList` before the current one.
953     ///
954     /// If the cursor is pointing at the null object then the new elements are
955     /// inserted at the end of the `LinkedList`.
956     #[inline]
957     pub fn splice_before(&mut self, mut list: LinkedList<A>) {
958         if !list.is_empty() {
959             unsafe {
960                 let head = list.head.unwrap_unchecked();
961                 let tail = list.tail.unwrap_unchecked();
962 
963                 let link_ops = self.list.adapter.link_ops_mut();
964 
965                 if let Some(current) = self.current {
966                     splice(link_ops, head, tail, link_ops.prev(current), Some(current));
967                 } else {
968                     splice(link_ops, head, tail, self.list.tail, None);
969                     self.list.tail = list.tail;
970                 }
971                 if self.list.head == self.current {
972                     self.list.head = list.head;
973                 }
974                 list.head = None;
975                 list.tail = None;
976             }
977         }
978     }
979 
980     /// Splits the list into two after the current element. This will return a
981     /// new list consisting of everything after the cursor, with the original
982     /// list retaining everything before.
983     ///
984     /// If the cursor is pointing at the null object then the entire contents
985     /// of the `LinkedList` are moved.
986     #[inline]
987     pub fn split_after(&mut self) -> LinkedList<A>
988     where
989         A: Clone,
990     {
991         if let Some(current) = self.current {
992             unsafe {
993                 let mut list = LinkedList {
994                     head: self.list.adapter.link_ops().next(current),
995                     tail: self.list.tail,
996                     adapter: self.list.adapter.clone(),
997                 };
998                 if let Some(head) = list.head {
999                     self.list.adapter.link_ops_mut().set_prev(head, None);
1000                 } else {
1001                     list.tail = None;
1002                 }
1003                 self.list.adapter.link_ops_mut().set_next(current, None);
1004                 self.list.tail = self.current;
1005                 list
1006             }
1007         } else {
1008             let list = LinkedList {
1009                 head: self.list.head,
1010                 tail: self.list.tail,
1011                 adapter: self.list.adapter.clone(),
1012             };
1013             self.list.head = None;
1014             self.list.tail = None;
1015             list
1016         }
1017     }
1018 
1019     /// Splits the list into two before the current element. This will return a
1020     /// new list consisting of everything before the cursor, with the original
1021     /// list retaining everything after.
1022     ///
1023     /// If the cursor is pointing at the null object then the entire contents
1024     /// of the `LinkedList` are moved.
1025     #[inline]
1026     pub fn split_before(&mut self) -> LinkedList<A>
1027     where
1028         A: Clone,
1029     {
1030         if let Some(current) = self.current {
1031             unsafe {
1032                 let mut list = LinkedList {
1033                     head: self.list.head,
1034                     tail: self.list.adapter.link_ops().prev(current),
1035                     adapter: self.list.adapter.clone(),
1036                 };
1037                 if let Some(tail) = list.tail {
1038                     self.list.adapter.link_ops_mut().set_prev(tail, None);
1039                 } else {
1040                     list.head = None;
1041                 }
1042                 self.list.adapter.link_ops_mut().set_prev(current, None);
1043                 self.list.head = self.current;
1044                 list
1045             }
1046         } else {
1047             let list = LinkedList {
1048                 head: self.list.head,
1049                 tail: self.list.tail,
1050                 adapter: self.list.adapter.clone(),
1051             };
1052             self.list.head = None;
1053             self.list.tail = None;
1054             list
1055         }
1056     }
1057 
1058     /// Consumes `CursorMut` and returns a reference to the object that
1059     /// the cursor is currently pointing to. Unlike [get](Self::get),
1060     /// the returned reference's lifetime is tied to `LinkedList`'s lifetime.
1061     ///
1062     /// This returns None if the cursor is currently pointing to the null object.
1063     #[inline]
1064     pub fn into_ref(self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
1065         Some(unsafe { &*self.list.adapter.get_value(self.current?) })
1066     }
1067 }
1068 
1069 /// A cursor with ownership over the `LinkedList` it points into.
1070 pub struct CursorOwning<A: Adapter>
1071 where
1072     A::LinkOps: LinkedListOps,
1073 {
1074     current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1075     list: LinkedList<A>,
1076 }
1077 
1078 impl<A: Adapter> CursorOwning<A>
1079 where
1080     A::LinkOps: LinkedListOps,
1081 {
1082     /// Consumes self and returns the inner `LinkedList`.
1083     #[inline]
1084     pub fn into_inner(self) -> LinkedList<A> {
1085         self.list
1086     }
1087 
1088     /// Returns a read-only cursor pointing to the current element.
1089     ///
1090     /// The lifetime of the returned `Cursor` is bound to that of the
1091     /// `CursorOwning`, which means it cannot outlive the `CursorOwning` and that the
1092     /// `CursorOwning` is frozen for the lifetime of the `Cursor`.
1093     ///
1094     /// Mutations of the returned cursor are _not_ reflected in the original.
1095     #[inline]
1096     pub fn as_cursor(&self) -> Cursor<'_, A> {
1097         Cursor {
1098             current: self.current,
1099             list: &self.list,
1100         }
1101     }
1102 
1103     /// Perform action with mutable reference to the cursor.
1104     ///
1105     /// All mutations of the cursor are reflected in the original.
1106     #[inline]
1107     pub fn with_cursor_mut<T>(&mut self, f: impl FnOnce(&mut CursorMut<'_, A>) -> T) -> T {
1108         let mut cursor = CursorMut {
1109             current: self.current,
1110             list: &mut self.list,
1111         };
1112         let ret = f(&mut cursor);
1113         self.current = cursor.current;
1114         ret
1115     }
1116 }
1117 unsafe impl<A: Adapter> Send for CursorOwning<A>
1118 where
1119     LinkedList<A>: Send,
1120     A::LinkOps: LinkedListOps,
1121 {
1122 }
1123 
1124 // =============================================================================
1125 // LinkedList
1126 // =============================================================================
1127 
1128 /// An intrusive doubly-linked list.
1129 ///
1130 /// When this collection is dropped, all elements linked into it will be
1131 /// converted back to owned pointers and dropped.
1132 pub struct LinkedList<A: Adapter>
1133 where
1134     A::LinkOps: LinkedListOps,
1135 {
1136     head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1137     tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1138     adapter: A,
1139 }
1140 
1141 impl<A: Adapter> LinkedList<A>
1142 where
1143     A::LinkOps: LinkedListOps,
1144 {
1145     #[inline]
1146     fn node_from_value(
1147         &mut self,
1148         val: <A::PointerOps as PointerOps>::Pointer,
1149     ) -> <A::LinkOps as link_ops::LinkOps>::LinkPtr {
1150         use link_ops::LinkOps;
1151 
1152         unsafe {
1153             let raw = self.adapter.pointer_ops().into_raw(val);
1154             let link = self.adapter.get_link(raw);
1155 
1156             if !self.adapter.link_ops_mut().acquire_link(link) {
1157                 // convert the node back into a pointer
1158                 self.adapter.pointer_ops().from_raw(raw);
1159 
1160                 panic!("attempted to insert an object that is already linked");
1161             }
1162 
1163             link
1164         }
1165     }
1166 
1167     /// Creates an empty `LinkedList`.
1168     #[cfg(not(feature = "nightly"))]
1169     #[inline]
1170     pub fn new(adapter: A) -> LinkedList<A> {
1171         LinkedList {
1172             head: None,
1173             tail: None,
1174             adapter,
1175         }
1176     }
1177 
1178     /// Creates an empty `LinkedList`.
1179     #[cfg(feature = "nightly")]
1180     #[inline]
1181     pub const fn new(adapter: A) -> LinkedList<A> {
1182         LinkedList {
1183             head: None,
1184             tail: None,
1185             adapter,
1186         }
1187     }
1188 
1189     /// Returns `true` if the `LinkedList` is empty.
1190     #[inline]
1191     pub fn is_empty(&self) -> bool {
1192         self.head.is_none()
1193     }
1194 
1195     /// Returns a null `Cursor` for this list.
1196     #[inline]
1197     pub fn cursor(&self) -> Cursor<'_, A> {
1198         Cursor {
1199             current: None,
1200             list: self,
1201         }
1202     }
1203 
1204     /// Returns a null `CursorMut` for this list.
1205     #[inline]
1206     pub fn cursor_mut(&mut self) -> CursorMut<'_, A> {
1207         CursorMut {
1208             current: None,
1209             list: self,
1210         }
1211     }
1212 
1213     /// Returns a null `CursorOwning` for this list.
1214     #[inline]
1215     pub fn cursor_owning(self) -> CursorOwning<A> {
1216         CursorOwning {
1217             current: None,
1218             list: self,
1219         }
1220     }
1221 
1222     /// Creates a `Cursor` from a pointer to an element.
1223     ///
1224     /// # Safety
1225     ///
1226     /// `ptr` must be a pointer to an object that is part of this list.
1227     #[inline]
1228     pub unsafe fn cursor_from_ptr(
1229         &self,
1230         ptr: *const <A::PointerOps as PointerOps>::Value,
1231     ) -> Cursor<'_, A> {
1232         Cursor {
1233             current: Some(self.adapter.get_link(ptr)),
1234             list: self,
1235         }
1236     }
1237 
1238     /// Creates a `CursorMut` from a pointer to an element.
1239     ///
1240     /// # Safety
1241     ///
1242     /// `ptr` must be a pointer to an object that is part of this list.
1243     #[inline]
1244     pub unsafe fn cursor_mut_from_ptr(
1245         &mut self,
1246         ptr: *const <A::PointerOps as PointerOps>::Value,
1247     ) -> CursorMut<'_, A> {
1248         CursorMut {
1249             current: Some(self.adapter.get_link(ptr)),
1250             list: self,
1251         }
1252     }
1253 
1254     /// Creates a `CursorOwning` from a pointer to an element.
1255     ///
1256     /// # Safety
1257     ///
1258     /// `ptr` must be a pointer to an object that is part of this list.
1259     #[inline]
1260     pub unsafe fn cursor_owning_from_ptr(
1261         self,
1262         ptr: *const <A::PointerOps as PointerOps>::Value,
1263     ) -> CursorOwning<A> {
1264         CursorOwning {
1265             current: Some(self.adapter.get_link(ptr)),
1266             list: self,
1267         }
1268     }
1269 
1270     /// Returns a `Cursor` pointing to the first element of the list. If the
1271     /// list is empty then a null cursor is returned.
1272     #[inline]
1273     pub fn front(&self) -> Cursor<'_, A> {
1274         let mut cursor = self.cursor();
1275         cursor.move_next();
1276         cursor
1277     }
1278 
1279     /// Returns a `CursorMut` pointing to the first element of the list. If the
1280     /// the list is empty then a null cursor is returned.
1281     #[inline]
1282     pub fn front_mut(&mut self) -> CursorMut<'_, A> {
1283         let mut cursor = self.cursor_mut();
1284         cursor.move_next();
1285         cursor
1286     }
1287 
1288     /// Returns a `CursorOwning` pointing to the first element of the list. If the
1289     /// the list is empty then a null cursor is returned.
1290     #[inline]
1291     pub fn front_owning(self) -> CursorOwning<A> {
1292         let mut cursor = self.cursor_owning();
1293         cursor.with_cursor_mut(|c| c.move_next());
1294         cursor
1295     }
1296 
1297     /// Returns a `Cursor` pointing to the last element of the list. If the list
1298     /// is empty then a null cursor is returned.
1299     #[inline]
1300     pub fn back(&self) -> Cursor<'_, A> {
1301         let mut cursor = self.cursor();
1302         cursor.move_prev();
1303         cursor
1304     }
1305 
1306     /// Returns a `CursorMut` pointing to the last element of the list. If the
1307     /// list is empty then a null cursor is returned.
1308     #[inline]
1309     pub fn back_mut(&mut self) -> CursorMut<'_, A> {
1310         let mut cursor = self.cursor_mut();
1311         cursor.move_prev();
1312         cursor
1313     }
1314 
1315     /// Returns a `CursorOwning` pointing to the last element of the list. If the
1316     /// list is empty then a null cursor is returned.
1317     #[inline]
1318     pub fn back_owning(self) -> CursorOwning<A> {
1319         let mut cursor = self.cursor_owning();
1320         cursor.with_cursor_mut(|c| c.move_prev());
1321         cursor
1322     }
1323 
1324     /// Gets an iterator over the objects in the `LinkedList`.
1325     #[inline]
1326     pub fn iter(&self) -> Iter<'_, A> {
1327         Iter {
1328             head: self.head,
1329             tail: self.tail,
1330             list: self,
1331         }
1332     }
1333 
1334     /// Removes all elements from the `LinkedList`.
1335     ///
1336     /// This will unlink all object currently in the list, which requires
1337     /// iterating through all elements in the `LinkedList`. Each element is
1338     /// converted back to an owned pointer and then dropped.
1339     #[inline]
1340     pub fn clear(&mut self) {
1341         use link_ops::LinkOps;
1342 
1343         let mut current = self.head;
1344         self.head = None;
1345         self.tail = None;
1346         while let Some(x) = current {
1347             unsafe {
1348                 let next = self.adapter.link_ops().next(x);
1349                 self.adapter.link_ops_mut().release_link(x);
1350                 self.adapter
1351                     .pointer_ops()
1352                     .from_raw(self.adapter.get_value(x));
1353                 current = next;
1354             }
1355         }
1356     }
1357 
1358     /// Empties the `LinkedList` without unlinking or freeing objects in it.
1359     ///
1360     /// Since this does not unlink any objects, any attempts to link these
1361     /// objects into another `LinkedList` will fail but will not cause any
1362     /// memory unsafety. To unlink those objects manually, you must call the
1363     /// `force_unlink` function on them.
1364     #[inline]
1365     pub fn fast_clear(&mut self) {
1366         self.head = None;
1367         self.tail = None;
1368     }
1369 
1370     /// Takes all the elements out of the `LinkedList`, leaving it empty.
1371     /// The taken elements are returned as a new `LinkedList`.
1372     #[inline]
1373     pub fn take(&mut self) -> LinkedList<A>
1374     where
1375         A: Clone,
1376     {
1377         let list = LinkedList {
1378             head: self.head,
1379             tail: self.tail,
1380             adapter: self.adapter.clone(),
1381         };
1382         self.head = None;
1383         self.tail = None;
1384         list
1385     }
1386 
1387     /// Inserts a new element at the start of the `LinkedList`.
1388     #[inline]
1389     pub fn push_front(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
1390         self.cursor_mut().insert_after(val);
1391     }
1392 
1393     /// Inserts a new element at the end of the `LinkedList`.
1394     #[inline]
1395     pub fn push_back(&mut self, val: <A::PointerOps as PointerOps>::Pointer) {
1396         self.cursor_mut().insert_before(val);
1397     }
1398 
1399     /// Removes the first element of the `LinkedList`.
1400     ///
1401     /// This returns `None` if the `LinkedList` is empty.
1402     #[inline]
1403     pub fn pop_front(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
1404         self.front_mut().remove()
1405     }
1406 
1407     /// Removes the last element of the `LinkedList`.
1408     ///
1409     /// This returns `None` if the `LinkedList` is empty.
1410     #[inline]
1411     pub fn pop_back(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
1412         self.back_mut().remove()
1413     }
1414 }
1415 
1416 // Allow read-only access to values from multiple threads
1417 unsafe impl<A: Adapter + Sync> Sync for LinkedList<A>
1418 where
1419     <A::PointerOps as PointerOps>::Value: Sync,
1420     A::LinkOps: LinkedListOps,
1421 {
1422 }
1423 
1424 // Allow sending to another thread if the ownership (represented by the <A::PointerOps as PointerOps>::Pointer owned
1425 // pointer type) can be transferred to another thread.
1426 unsafe impl<A: Adapter + Send> Send for LinkedList<A>
1427 where
1428     <A::PointerOps as PointerOps>::Pointer: Send,
1429     A::LinkOps: LinkedListOps,
1430 {
1431 }
1432 
1433 // Drop all owned pointers if the collection is dropped
1434 impl<A: Adapter> Drop for LinkedList<A>
1435 where
1436     A::LinkOps: LinkedListOps,
1437 {
1438     #[inline]
1439     fn drop(&mut self) {
1440         self.clear();
1441     }
1442 }
1443 
1444 impl<A: Adapter> IntoIterator for LinkedList<A>
1445 where
1446     A::LinkOps: LinkedListOps,
1447 {
1448     type Item = <A::PointerOps as PointerOps>::Pointer;
1449     type IntoIter = IntoIter<A>;
1450 
1451     #[inline]
1452     fn into_iter(self) -> IntoIter<A> {
1453         IntoIter { list: self }
1454     }
1455 }
1456 
1457 impl<'a, A: Adapter + 'a> IntoIterator for &'a LinkedList<A>
1458 where
1459     A::LinkOps: LinkedListOps,
1460 {
1461     type Item = &'a <A::PointerOps as PointerOps>::Value;
1462     type IntoIter = Iter<'a, A>;
1463 
1464     #[inline]
1465     fn into_iter(self) -> Iter<'a, A> {
1466         self.iter()
1467     }
1468 }
1469 
1470 impl<A: Adapter + Default> Default for LinkedList<A>
1471 where
1472     A::LinkOps: LinkedListOps,
1473 {
1474     fn default() -> LinkedList<A> {
1475         LinkedList::new(A::default())
1476     }
1477 }
1478 
1479 impl<A: Adapter> fmt::Debug for LinkedList<A>
1480 where
1481     A::LinkOps: LinkedListOps,
1482     <A::PointerOps as PointerOps>::Value: fmt::Debug,
1483 {
1484     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1485         f.debug_list().entries(self.iter()).finish()
1486     }
1487 }
1488 
1489 // =============================================================================
1490 // Iter
1491 // =============================================================================
1492 
1493 /// An iterator over references to the items of a `LinkedList`.
1494 pub struct Iter<'a, A: Adapter>
1495 where
1496     A::LinkOps: LinkedListOps,
1497 {
1498     head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1499     tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1500     list: &'a LinkedList<A>,
1501 }
1502 impl<'a, A: Adapter + 'a> Iterator for Iter<'a, A>
1503 where
1504     A::LinkOps: LinkedListOps,
1505 {
1506     type Item = &'a <A::PointerOps as PointerOps>::Value;
1507 
1508     #[inline]
1509     fn next(&mut self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
1510         let head = self.head?;
1511 
1512         if Some(head) == self.tail {
1513             self.head = None;
1514             self.tail = None;
1515         } else {
1516             self.head = unsafe { self.list.adapter.link_ops().next(head) };
1517         }
1518         Some(unsafe { &*self.list.adapter.get_value(head) })
1519     }
1520 }
1521 impl<'a, A: Adapter + 'a> DoubleEndedIterator for Iter<'a, A>
1522 where
1523     A::LinkOps: LinkedListOps,
1524 {
1525     #[inline]
1526     fn next_back(&mut self) -> Option<&'a <A::PointerOps as PointerOps>::Value> {
1527         let tail = self.tail?;
1528 
1529         if Some(tail) == self.head {
1530             self.head = None;
1531             self.tail = None;
1532         } else {
1533             self.tail = unsafe { self.list.adapter.link_ops().prev(tail) };
1534         }
1535         Some(unsafe { &*self.list.adapter.get_value(tail) })
1536     }
1537 }
1538 impl<'a, A: Adapter + 'a> Clone for Iter<'a, A>
1539 where
1540     A::LinkOps: LinkedListOps,
1541 {
1542     #[inline]
1543     fn clone(&self) -> Iter<'a, A> {
1544         Iter {
1545             head: self.head,
1546             tail: self.tail,
1547             list: self.list,
1548         }
1549     }
1550 }
1551 
1552 // =============================================================================
1553 // IntoIter
1554 // =============================================================================
1555 
1556 /// An iterator which consumes a `LinkedList`.
1557 pub struct IntoIter<A: Adapter>
1558 where
1559     A::LinkOps: LinkedListOps,
1560 {
1561     list: LinkedList<A>,
1562 }
1563 impl<A: Adapter> Iterator for IntoIter<A>
1564 where
1565     A::LinkOps: LinkedListOps,
1566 {
1567     type Item = <A::PointerOps as PointerOps>::Pointer;
1568 
1569     #[inline]
1570     fn next(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
1571         self.list.pop_front()
1572     }
1573 }
1574 impl<A: Adapter> DoubleEndedIterator for IntoIter<A>
1575 where
1576     A::LinkOps: LinkedListOps,
1577 {
1578     #[inline]
1579     fn next_back(&mut self) -> Option<<A::PointerOps as PointerOps>::Pointer> {
1580         self.list.pop_back()
1581     }
1582 }
1583 
1584 // =============================================================================
1585 // Tests
1586 // =============================================================================
1587 
1588 #[cfg(test)]
1589 mod tests {
1590     use alloc::boxed::Box;
1591 
1592     use crate::UnsafeRef;
1593 
1594     use super::{CursorOwning, Link, LinkedList};
1595     use std::fmt;
1596     use std::format;
1597     use std::rc::Rc;
1598     use std::vec::Vec;
1599 
1600     struct Obj {
1601         link1: Link,
1602         link2: Link,
1603         value: u32,
1604     }
1605     impl fmt::Debug for Obj {
1606         fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1607             write!(f, "{}", self.value)
1608         }
1609     }
1610     intrusive_adapter!(ObjAdapter1 = Rc<Obj>: Obj { link1: Link });
1611     intrusive_adapter!(ObjAdapter2 = Rc<Obj>: Obj { link2: Link });
1612     intrusive_adapter!(UnsafeRefObjAdapter1 = UnsafeRef<Obj>: Obj { link1: Link });
1613 
1614     fn make_rc_obj(value: u32) -> Rc<Obj> {
1615         Rc::new(make_obj(value))
1616     }
1617 
1618     fn make_obj(value: u32) -> Obj {
1619         Obj {
1620             link1: Link::new(),
1621             link2: Link::default(),
1622             value,
1623         }
1624     }
1625 
1626     #[test]
1627     fn test_link() {
1628         let a = make_rc_obj(1);
1629         assert!(!a.link1.is_linked());
1630         assert!(!a.link2.is_linked());
1631 
1632         let mut b = LinkedList::<ObjAdapter1>::default();
1633         assert!(b.is_empty());
1634 
1635         b.cursor_mut().insert_after(a.clone());
1636         assert!(!b.is_empty());
1637         assert!(a.link1.is_linked());
1638         assert!(!a.link2.is_linked());
1639         assert_eq!(format!("{:?}", a.link1), "linked");
1640         assert_eq!(format!("{:?}", a.link2), "unlinked");
1641 
1642         assert_eq!(
1643             b.front_mut().remove().unwrap().as_ref() as *const _,
1644             a.as_ref() as *const _
1645         );
1646         assert!(b.is_empty());
1647         assert!(!a.link1.is_linked());
1648         assert!(!a.link2.is_linked());
1649     }
1650 
1651     #[test]
1652     fn test_cursor() {
1653         let a = make_rc_obj(1);
1654         let b = make_rc_obj(2);
1655         let c = make_rc_obj(3);
1656 
1657         let mut l = LinkedList::new(ObjAdapter1::new());
1658         let mut cur = l.cursor_mut();
1659         assert!(cur.is_null());
1660         assert!(cur.get().is_none());
1661         assert!(cur.remove().is_none());
1662         assert_eq!(
1663             cur.replace_with(a.clone()).unwrap_err().as_ref() as *const _,
1664             a.as_ref() as *const _
1665         );
1666 
1667         cur.insert_before(a.clone());
1668         cur.insert_before(c.clone());
1669         cur.move_prev();
1670         cur.insert_before(b.clone());
1671         assert!(cur.peek_next().is_null());
1672         cur.move_next();
1673         assert!(cur.is_null());
1674 
1675         cur.move_next();
1676         assert!(cur.peek_prev().is_null());
1677         assert!(!cur.is_null());
1678         assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
1679 
1680         {
1681             let mut cur2 = cur.as_cursor();
1682             assert_eq!(cur2.get().unwrap() as *const _, a.as_ref() as *const _);
1683             assert_eq!(cur2.peek_next().get().unwrap().value, 2);
1684             cur2.move_next();
1685             assert_eq!(cur2.get().unwrap().value, 2);
1686             cur2.move_next();
1687             assert_eq!(cur2.peek_prev().get().unwrap().value, 2);
1688             assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
1689             cur2.move_prev();
1690             assert_eq!(cur2.get().unwrap() as *const _, b.as_ref() as *const _);
1691             cur2.move_next();
1692             assert_eq!(cur2.get().unwrap() as *const _, c.as_ref() as *const _);
1693             cur2.move_next();
1694             assert!(cur2.is_null());
1695             assert!(cur2.clone().get().is_none());
1696         }
1697         assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
1698 
1699         cur.move_next();
1700         assert_eq!(
1701             cur.remove().unwrap().as_ref() as *const _,
1702             b.as_ref() as *const _
1703         );
1704         assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
1705         cur.insert_after(b.clone());
1706         assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
1707         cur.move_prev();
1708         assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
1709         assert_eq!(
1710             cur.remove().unwrap().as_ref() as *const _,
1711             a.as_ref() as *const _
1712         );
1713         assert!(!a.link1.is_linked());
1714         assert!(c.link1.is_linked());
1715         assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
1716         assert_eq!(
1717             cur.replace_with(a.clone()).unwrap().as_ref() as *const _,
1718             c.as_ref() as *const _
1719         );
1720         assert!(a.link1.is_linked());
1721         assert!(!c.link1.is_linked());
1722         assert_eq!(cur.get().unwrap() as *const _, a.as_ref() as *const _);
1723         cur.move_next();
1724         assert_eq!(
1725             cur.replace_with(c.clone()).unwrap().as_ref() as *const _,
1726             b.as_ref() as *const _
1727         );
1728         assert!(a.link1.is_linked());
1729         assert!(!b.link1.is_linked());
1730         assert!(c.link1.is_linked());
1731         assert_eq!(cur.get().unwrap() as *const _, c.as_ref() as *const _);
1732     }
1733 
1734     #[test]
1735     fn test_cursor_owning() {
1736         struct Container {
1737             cur: CursorOwning<ObjAdapter1>,
1738         }
1739 
1740         let mut l = LinkedList::new(ObjAdapter1::new());
1741         l.push_back(make_rc_obj(1));
1742         l.push_back(make_rc_obj(2));
1743         l.push_back(make_rc_obj(3));
1744         l.push_back(make_rc_obj(4));
1745         let mut con = Container {
1746             cur: l.cursor_owning(),
1747         };
1748         assert!(con.cur.as_cursor().is_null());
1749 
1750         con.cur = con.cur.into_inner().front_owning();
1751         assert_eq!(con.cur.as_cursor().get().unwrap().value, 1);
1752 
1753         con.cur.with_cursor_mut(|c| c.move_next());
1754         assert_eq!(con.cur.as_cursor().get().unwrap().value, 2);
1755 
1756         con.cur = con.cur.into_inner().back_owning();
1757         assert_eq!(con.cur.as_cursor().get().unwrap().value, 4);
1758     }
1759 
1760     #[test]
1761     fn test_push_pop() {
1762         let a = make_rc_obj(1);
1763         let b = make_rc_obj(2);
1764         let c = make_rc_obj(3);
1765 
1766         let mut l = LinkedList::new(ObjAdapter1::new());
1767         l.push_front(a);
1768         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1]);
1769         l.push_front(b);
1770         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [2, 1]);
1771         l.push_back(c);
1772         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [2, 1, 3]);
1773         assert_eq!(l.pop_front().unwrap().value, 2);
1774         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3]);
1775         assert_eq!(l.pop_back().unwrap().value, 3);
1776         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1]);
1777         assert_eq!(l.pop_front().unwrap().value, 1);
1778         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1779         assert!(l.pop_front().is_none());
1780         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1781         assert!(l.pop_back().is_none());
1782         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1783     }
1784 
1785     #[test]
1786     fn test_split_splice() {
1787         let mut l1 = LinkedList::new(ObjAdapter1::new());
1788         let mut l2 = LinkedList::new(ObjAdapter1::new());
1789         let mut l3 = LinkedList::new(ObjAdapter1::new());
1790 
1791         let a = make_rc_obj(1);
1792         let b = make_rc_obj(2);
1793         let c = make_rc_obj(3);
1794         let d = make_rc_obj(4);
1795         l1.cursor_mut().insert_before(a);
1796         l1.cursor_mut().insert_before(b);
1797         l1.cursor_mut().insert_before(c);
1798         l1.cursor_mut().insert_before(d);
1799         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]);
1800         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1801         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1802         {
1803             let mut cur = l1.front_mut();
1804             cur.move_next();
1805             l2 = cur.split_after();
1806         }
1807         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2]);
1808         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [3, 4]);
1809         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1810         {
1811             let mut cur = l2.back_mut();
1812             l3 = cur.split_before();
1813         }
1814         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2]);
1815         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4]);
1816         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), [3]);
1817         {
1818             let mut cur = l1.front_mut();
1819             cur.splice_after(l2.take());
1820         }
1821         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 4, 2]);
1822         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1823         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), [3]);
1824         {
1825             let mut cur = l1.front_mut();
1826             cur.move_next();
1827             cur.splice_before(l3.take());
1828         }
1829         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1830         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1831         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1832         {
1833             let mut cur = l2.cursor_mut();
1834             cur.splice_after(l1.take());
1835         }
1836         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1837         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1838         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1839         {
1840             let mut cur = l1.cursor_mut();
1841             cur.splice_before(l2.take());
1842         }
1843         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1844         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1845         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1846         {
1847             let mut cur = l1.cursor_mut();
1848             l2 = cur.split_after();
1849         }
1850         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1851         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1852         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1853         {
1854             let mut cur = l2.cursor_mut();
1855             l1 = cur.split_before();
1856         }
1857         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1858         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1859         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1860         {
1861             let mut cur = l1.front_mut();
1862             l2 = cur.split_before();
1863         }
1864         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1865         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1866         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1867         {
1868             let mut cur = l1.back_mut();
1869             l2 = cur.split_after();
1870         }
1871         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 3, 4, 2]);
1872         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1873         assert_eq!(l3.iter().map(|x| x.value).collect::<Vec<_>>(), []);
1874     }
1875 
1876     #[test]
1877     fn test_iter() {
1878         let mut l = LinkedList::new(ObjAdapter1::new());
1879         let a = make_rc_obj(1);
1880         let b = make_rc_obj(2);
1881         let c = make_rc_obj(3);
1882         let d = make_rc_obj(4);
1883         l.cursor_mut().insert_before(a.clone());
1884         l.cursor_mut().insert_before(b.clone());
1885         l.cursor_mut().insert_before(c.clone());
1886         l.cursor_mut().insert_before(d.clone());
1887 
1888         assert_eq!(l.front().get().unwrap().value, 1);
1889         assert_eq!(l.back().get().unwrap().value, 4);
1890         unsafe {
1891             assert_eq!(l.cursor_from_ptr(b.as_ref()).get().unwrap().value, 2);
1892             assert_eq!(l.cursor_mut_from_ptr(c.as_ref()).get().unwrap().value, 3);
1893         }
1894 
1895         let mut v = Vec::new();
1896         for x in &l {
1897             v.push(x.value);
1898         }
1899         assert_eq!(v, [1, 2, 3, 4]);
1900         assert_eq!(
1901             l.iter().clone().map(|x| x.value).collect::<Vec<_>>(),
1902             [1, 2, 3, 4]
1903         );
1904         assert_eq!(
1905             l.iter().rev().map(|x| x.value).collect::<Vec<_>>(),
1906             [4, 3, 2, 1]
1907         );
1908         assert_eq!(l.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]);
1909 
1910         assert_eq!(format!("{:?}", l), "[1, 2, 3, 4]");
1911 
1912         let mut v = Vec::new();
1913         for x in l.take() {
1914             v.push(x.value);
1915         }
1916         assert_eq!(v, [1, 2, 3, 4]);
1917         assert!(l.is_empty());
1918         assert!(!a.link1.is_linked());
1919         assert!(!b.link1.is_linked());
1920         assert!(!c.link1.is_linked());
1921         assert!(!d.link1.is_linked());
1922 
1923         l.cursor_mut().insert_before(a.clone());
1924         l.cursor_mut().insert_before(b.clone());
1925         l.cursor_mut().insert_before(c.clone());
1926         l.cursor_mut().insert_before(d.clone());
1927         l.clear();
1928         assert!(l.is_empty());
1929         assert!(!a.link1.is_linked());
1930         assert!(!b.link1.is_linked());
1931         assert!(!c.link1.is_linked());
1932         assert!(!d.link1.is_linked());
1933 
1934         v.clear();
1935         l.cursor_mut().insert_before(a.clone());
1936         l.cursor_mut().insert_before(b.clone());
1937         l.cursor_mut().insert_before(c.clone());
1938         l.cursor_mut().insert_before(d.clone());
1939         for x in l.into_iter().rev() {
1940             v.push(x.value);
1941         }
1942         assert_eq!(v, [4, 3, 2, 1]);
1943         assert!(!a.link1.is_linked());
1944         assert!(!b.link1.is_linked());
1945         assert!(!c.link1.is_linked());
1946         assert!(!d.link1.is_linked());
1947     }
1948 
1949     #[test]
1950     fn test_multi_list() {
1951         let mut l1 = LinkedList::new(ObjAdapter1::new());
1952         let mut l2 = LinkedList::new(ObjAdapter2::new());
1953         let a = make_rc_obj(1);
1954         let b = make_rc_obj(2);
1955         let c = make_rc_obj(3);
1956         let d = make_rc_obj(4);
1957         l1.cursor_mut().insert_before(a.clone());
1958         l1.cursor_mut().insert_before(b.clone());
1959         l1.cursor_mut().insert_before(c.clone());
1960         l1.cursor_mut().insert_before(d.clone());
1961         l2.cursor_mut().insert_after(a);
1962         l2.cursor_mut().insert_after(b);
1963         l2.cursor_mut().insert_after(c);
1964         l2.cursor_mut().insert_after(d);
1965         assert_eq!(l1.iter().map(|x| x.value).collect::<Vec<_>>(), [1, 2, 3, 4]);
1966         assert_eq!(l2.iter().map(|x| x.value).collect::<Vec<_>>(), [4, 3, 2, 1]);
1967     }
1968 
1969     #[test]
1970     fn test_fast_clear_force_unlink() {
1971         let mut l = LinkedList::new(UnsafeRefObjAdapter1::new());
1972         let a = UnsafeRef::from_box(Box::new(make_obj(1)));
1973         let b = UnsafeRef::from_box(Box::new(make_obj(2)));
1974         let c = UnsafeRef::from_box(Box::new(make_obj(3)));
1975         l.cursor_mut().insert_before(a.clone());
1976         l.cursor_mut().insert_before(b.clone());
1977         l.cursor_mut().insert_before(c.clone());
1978 
1979         l.fast_clear();
1980         assert!(l.is_empty());
1981 
1982         unsafe {
1983             assert!(a.link1.is_linked());
1984             assert!(b.link1.is_linked());
1985             assert!(c.link1.is_linked());
1986 
1987             a.link1.force_unlink();
1988             b.link1.force_unlink();
1989             c.link1.force_unlink();
1990 
1991             assert!(l.is_empty());
1992 
1993             assert!(!a.link1.is_linked());
1994             assert!(!b.link1.is_linked());
1995             assert!(!c.link1.is_linked());
1996         }
1997 
1998         unsafe {
1999             UnsafeRef::into_box(a);
2000             UnsafeRef::into_box(b);
2001             UnsafeRef::into_box(c);
2002         }
2003     }
2004 
2005     #[test]
2006     fn test_non_static() {
2007         #[derive(Clone)]
2008         struct Obj<'a, T> {
2009             link: Link,
2010             value: &'a T,
2011         }
2012         intrusive_adapter!(ObjAdapter<'a, T> = &'a Obj<'a, T>: Obj<'a, T> {link: Link} where T: 'a);
2013 
2014         let v = 5;
2015         let a = Obj {
2016             link: Link::new(),
2017             value: &v,
2018         };
2019         let b = a.clone();
2020         let mut l = LinkedList::new(ObjAdapter::new());
2021         l.cursor_mut().insert_before(&a);
2022         l.cursor_mut().insert_before(&b);
2023         assert_eq!(*l.front().get().unwrap().value, 5);
2024         assert_eq!(*l.back().get().unwrap().value, 5);
2025     }
2026 
2027     macro_rules! test_clone_pointer {
2028         ($ptr: ident, $ptr_import: path) => {
2029             use $ptr_import;
2030 
2031             #[derive(Clone)]
2032             struct Obj {
2033                 link: Link,
2034                 value: usize,
2035             }
2036             intrusive_adapter!(ObjAdapter = $ptr<Obj>: Obj { link: Link });
2037 
2038             let a = $ptr::new(Obj {
2039                 link: Link::new(),
2040                 value: 5,
2041             });
2042             let mut l = LinkedList::new(ObjAdapter::new());
2043             l.cursor_mut().insert_before(a.clone());
2044             assert_eq!(2, $ptr::strong_count(&a));
2045 
2046             let pointer = l.front().clone_pointer().unwrap();
2047             assert_eq!(pointer.value, 5);
2048             assert_eq!(3, $ptr::strong_count(&a));
2049 
2050             l.front_mut().remove();
2051             assert!(l.front().clone_pointer().is_none());
2052         };
2053     }
2054 
2055     #[test]
2056     fn test_clone_pointer_rc() {
2057         test_clone_pointer!(Rc, std::rc::Rc);
2058     }
2059 
2060     #[test]
2061     fn test_clone_pointer_arc() {
2062         test_clone_pointer!(Arc, std::sync::Arc);
2063     }
2064 }
2065