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