embed_dlist/
lib.rs

1#![allow(rustdoc::redundant_explicit_links)]
2#![cfg_attr(docsrs, feature(doc_cfg))]
3#![cfg_attr(docsrs, allow(unused_attributes))]
4#![cfg_attr(not(feature = "std"), no_std)]
5
6//! An intrusive doubly linked list implementation.
7//!
8//! This module provides `DLinkedList`, a doubly linked list where elements
9//! embed the list nodes themselves. This design offers memory efficiency
10//! and explicit control over allocation, suitable for scenarios like
11//! building LRU caches directly within data structures.
12//!
13//! # Features
14//! - O(1) push and pop from both front and back.
15//! - Generic over pointer types (`Box`, `Arc`, `NonNull`, raw pointers).
16//! - Supports multiple lists for the same item via `Tag`.
17//!
18//! # Example
19//!
20//! ```rust
21//! use embed_dlist::{DLinkedList, DListItem, DListNode};
22//! use core::cell::UnsafeCell;
23//! use std::sync::Arc;
24//! use core::ptr::NonNull;
25//!
26//! struct MyItem {
27//!     id: u32,
28//!     data: String,
29//!     node: UnsafeCell<DListNode<MyItem, ()>>,
30//! }
31//!
32//! impl MyItem {
33//!     fn new(id: u32, data: &str) -> Self {
34//!         MyItem {
35//!             id,
36//!             data: data.to_string(),
37//!             node: UnsafeCell::new(DListNode::default()),
38//!         }
39//!     }
40//! }
41//!
42//! unsafe impl DListItem<()> for MyItem {
43//!     fn get_node(&self) -> &mut DListNode<Self, ()> {
44//!         unsafe { &mut *self.node.get() }
45//!     }
46//! }
47//!
48//! // Using Box<T> (owned pointers)
49//! {
50//!     let mut list = DLinkedList::<Box<MyItem>, ()>::new();
51//!     list.push_back(Box::new(MyItem::new(1, "First")));
52//!     list.push_front(Box::new(MyItem::new(2, "Second")));
53//!     list.push_back(Box::new(MyItem::new(3, "Third")));
54//!     assert_eq!(list.len(), 3);
55//!     assert_eq!(list.pop_front().unwrap().id, 2);
56//!     assert_eq!(list.pop_back().unwrap().id, 3);
57//!     assert_eq!(list.pop_front().unwrap().id, 1);
58//!     assert!(list.is_empty());
59//! }
60//!
61//! // Using Arc<T> (shared ownership)
62//! {
63//!     let mut list = DLinkedList::<Arc<MyItem>, ()>::new();
64//!     list.push_back(Arc::new(MyItem::new(1, "First")));
65//!     list.push_front(Arc::new(MyItem::new(2, "Second")));
66//!     list.push_back(Arc::new(MyItem::new(3, "Third")));
67//!     assert_eq!(list.len(), 3);
68//!     assert_eq!(list.pop_front().unwrap().id, 2);
69//!     assert_eq!(list.pop_back().unwrap().id, 3);
70//!     assert_eq!(list.pop_front().unwrap().id, 1);
71//!     assert!(list.is_empty());
72//! }
73//!
74//! // Using NonNull<T> (raw pointers without ownership)
75//! {
76//!     let mut list = DLinkedList::<NonNull<MyItem>, ()>::new();
77//!     let item1 = Box::into_raw(Box::new(MyItem::new(1, "First")));
78//!     let item2 = Box::into_raw(Box::new(MyItem::new(2, "Second")));
79//!     let item3 = Box::into_raw(Box::new(MyItem::new(3, "Third")));
80//!     list.push_back(unsafe{NonNull::new_unchecked(item1)});
81//!     list.push_front(unsafe{NonNull::new_unchecked(item2)});
82//!     list.push_back(unsafe{NonNull::new_unchecked(item3)});
83//!     assert_eq!(list.len(), 3);
84//!     assert_eq!(unsafe { list.pop_front().unwrap().as_ref().id }, 2);
85//!     assert_eq!(unsafe { list.pop_back().unwrap().as_ref().id }, 3);
86//!     assert_eq!(unsafe { list.pop_front().unwrap().as_ref().id }, 1);
87//!     assert!(list.is_empty());
88//!     unsafe{
89//!         let _ = Box::from_raw(item1);
90//!         let _ = Box::from_raw(item2);
91//!         let _ = Box::from_raw(item3);
92//!     }
93//! }
94//! ```
95
96extern crate alloc;
97#[cfg(any(feature = "std", test))]
98extern crate std;
99
100use core::marker::PhantomData;
101use core::{
102    fmt, mem,
103    ptr::{self, null},
104};
105use pointers::Pointer;
106
107/// A trait to return internal mutable DListNode for specified list.
108///
109/// The tag is used to distinguish different DListNodes within the same item,
110/// allowing an item to belong to multiple lists simultaneously.
111/// For only one ownership, you can use `()`.
112///
113/// # Safety
114///
115/// Implementors must ensure `get_node` returns a valid reference to the `DListNode`
116/// embedded within `Self`. Users must use `UnsafeCell` to hold `DListNode` to support
117/// interior mutability required by list operations.
118pub unsafe trait DListItem<Tag>: Sized {
119    fn get_node(&self) -> &mut DListNode<Self, Tag>;
120}
121
122/// The node structure that must be embedded in items to be stored in a `DLinkedList`.
123#[repr(C)]
124pub struct DListNode<T: Sized, Tag> {
125    prev: *const T,
126    next: *const T,
127    _phan: PhantomData<fn(&Tag)>,
128}
129
130unsafe impl<T, Tag> Send for DListNode<T, Tag> {}
131
132impl<T: DListItem<Tag>, Tag> DListNode<T, Tag> {
133    #[inline]
134    fn get_prev<'a>(&self) -> Option<&'a mut DListNode<T, Tag>> {
135        unsafe { if !self.prev.is_null() { Some((*self.prev).get_node()) } else { None } }
136    }
137
138    #[inline]
139    fn get_next<'a>(&self) -> Option<&'a mut DListNode<T, Tag>> {
140        unsafe { if !self.next.is_null() { Some((*self.next).get_node()) } else { None } }
141    }
142}
143
144impl<T, Tag> Default for DListNode<T, Tag> {
145    #[inline(always)]
146    fn default() -> Self {
147        Self { prev: null(), next: null(), _phan: Default::default() }
148    }
149}
150
151impl<T: DListItem<Tag> + fmt::Debug, Tag> fmt::Debug for DListNode<T, Tag> {
152    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
153        write!(f, "(")?;
154        if !self.prev.is_null() {
155            write!(f, "prev: {:p} ", self.prev)?;
156        } else {
157            write!(f, "prev: none ")?;
158        }
159        if !self.next.is_null() {
160            write!(f, "next: {:p} ", self.next)?;
161        } else {
162            write!(f, "next: none ")?;
163        }
164        write!(f, ")")
165    }
166}
167
168/// An intrusive doubly linked list.
169///
170/// Supports O(1) insertion and removal at both ends.
171#[repr(C)]
172pub struct DLinkedList<P, Tag>
173where
174    P: Pointer,
175    P::Target: DListItem<Tag>,
176{
177    length: usize,
178    head: *const P::Target,
179    tail: *const P::Target,
180    _phan: PhantomData<fn(&Tag)>,
181}
182
183unsafe impl<P, Tag> Send for DLinkedList<P, Tag>
184where
185    P: Pointer,
186    P::Target: DListItem<Tag>,
187{
188}
189
190impl<P: fmt::Debug, Tag> fmt::Debug for DLinkedList<P, Tag>
191where
192    P: Pointer,
193    P::Target: DListItem<Tag>,
194{
195    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
196        write!(f, "{{ length: {} ", self.length)?;
197        if !self.head.is_null() {
198            write!(f, "head: {:?} ", self.head)?;
199        } else {
200            write!(f, "head: none ")?;
201        }
202        if !self.tail.is_null() {
203            write!(f, "tail: {:?} ", self.tail)?;
204        } else {
205            write!(f, "tail: none ")?;
206        }
207        write!(f, "}}")
208    }
209}
210
211impl<P, Tag> DLinkedList<P, Tag>
212where
213    P: Pointer,
214    P::Target: DListItem<Tag>,
215{
216    /// Creates a new, empty doubly linked list.
217    #[inline(always)]
218    pub fn new() -> Self {
219        DLinkedList { length: 0, head: null(), tail: null(), _phan: Default::default() }
220    }
221
222    /// Clears the list, dropping all of its elements if the pointer type `P` owns them.
223    #[inline]
224    pub fn clear(&mut self) {
225        // By repeatedly popping from the front, we drop each element.
226        // If P is an owned pointer (like Box), the element is dropped.
227        // If P is a raw pointer, it's a no-op, but the list is still emptied.
228        while self.pop_front().is_some() {}
229    }
230
231    /// Returns the length of the list as `usize`.
232    #[inline(always)]
233    pub fn len(&self) -> usize {
234        self.length
235    }
236
237    /// Returns `true` if the list contains no elements.
238    #[inline(always)]
239    pub fn is_empty(&self) -> bool {
240        self.length == 0
241    }
242
243    #[inline(always)]
244    fn _remove_node(&mut self, item: *const P::Target) -> bool {
245        let mut removed = false;
246        unsafe {
247            let node = (*item).get_node();
248            if let Some(prev) = node.get_prev() {
249                prev.next = node.next;
250                removed = true;
251            } else if self.head == item {
252                self.head = node.next;
253                removed = true;
254            }
255            if let Some(next) = node.get_next() {
256                next.prev = node.prev;
257                removed = true;
258            } else if self.tail == item {
259                self.tail = node.prev;
260                removed = true;
261            }
262            if removed {
263                node.next = null();
264                node.prev = null();
265                self.length -= 1;
266            }
267            removed
268        }
269    }
270
271    /// Remove a node by raw pointer from the middle of the list, and recover P from `item`
272    ///
273    /// - Return Some if the item is in the list.
274    /// - Return None if the item is not in any list.
275    ///
276    /// NOTE： Due to avoid miri stack borrow rule error, `item` is a raw pointer.
277    ///
278    /// # Safety
279    ///
280    /// `item` should point the a valid item. Do not remove item from other list, otherwise will lead to UB.
281    ///
282    /// # Example
283    ///
284    /// ```
285    ///
286    /// use embed_dlist::{DLinkedList, DListItem, DListNode};
287    /// use core::cell::UnsafeCell;
288    /// extern crate alloc;
289    /// use alloc::boxed::Box;
290    ///
291    /// #[derive(Debug)]
292    /// pub struct TestNode {
293    ///     pub value: i64,
294    ///     pub node: UnsafeCell<DListNode<Self, ()>>,
295    /// }
296    ///
297    /// unsafe impl Send for TestNode {}
298    ///
299    /// unsafe impl DListItem<()> for TestNode {
300    ///     fn get_node(&self) -> &mut DListNode<Self, ()> {
301    ///         unsafe { &mut *self.node.get() }
302    ///     }
303    /// }
304    ///
305    /// fn new_node(v: i64) -> TestNode {
306    ///     TestNode { value: v, node: UnsafeCell::new(DListNode::default()) }
307    /// }
308    ///
309    /// let mut l = DLinkedList::<Box<TestNode>, ()>::new();
310    ///
311    /// let node1 = Box::new(new_node(1));
312    /// l.push_back(node1);
313    /// let node2 = Box::new(new_node(2));
314    ///
315    /// // NOTE: use `node_p = node2.as_ptr()`  will trigger miri stack borrow rule.
316    /// // we use into_raw and then from_raw
317    /// let node2_p = Box::into_raw(node2);
318    /// l.push_back(unsafe{Box::from_raw(node2_p)});
319    ///
320    /// let node3 = Box::new(new_node(3));
321    /// l.push_back(node3);
322    /// assert_eq!(l.len(), 3);
323    ///
324    /// let node2 = unsafe { l.remove_node(node2_p).unwrap() };
325    /// assert_eq!(l.len(), 2);
326    /// assert_eq!(node2.value, 2);
327    /// ```
328    #[inline(always)]
329    pub unsafe fn remove_node(&mut self, item: *const P::Target) -> Option<P> {
330        if self._remove_node(item) { Some(unsafe { P::from_raw(item) }) } else { None }
331    }
332
333    /// Moves a node to the front of the list (e.g., for LRU updates).
334    ///
335    /// NOTE： Due to avoid miri stack borrow rule error, `item` is a raw pointer.
336    ///
337    /// # Safety
338    ///
339    /// The item must be in the list, otherwise will lead to UB.
340    #[inline(always)]
341    pub unsafe fn peak(&mut self, item: *const P::Target) {
342        assert!(!self.head.is_null());
343        unsafe {
344            if !self.head.is_null() {
345                let head_node = (*self.head).get_node() as *const DListNode<P::Target, Tag>;
346                if ptr::eq(head_node, (*item).get_node()) {
347                    return;
348                }
349            }
350            self._remove_node(item);
351            self.push_front_ptr(item);
352        }
353    }
354
355    /// Pushes an element to the front of the list.
356    #[inline]
357    pub fn push_front(&mut self, item: P) {
358        let ptr = item.into_raw();
359        self.push_front_ptr(ptr);
360    }
361
362    #[inline]
363    fn push_front_ptr(&mut self, ptr: *const P::Target) {
364        let node = unsafe { (*ptr).get_node() };
365        let head = self.head;
366        node.next = head;
367        node.prev = null();
368
369        if head.is_null() {
370            self.tail = ptr;
371        } else {
372            unsafe {
373                (*head).get_node().prev = ptr;
374            }
375        }
376        self.head = ptr;
377        self.length += 1;
378    }
379
380    /// Pushes an element to the back of the list.
381    #[inline]
382    pub fn push_back(&mut self, item: P) {
383        let node = item.as_ref().get_node();
384        let tail = self.tail;
385        node.prev = tail;
386        node.next = null();
387
388        let ptr = item.into_raw();
389        if tail.is_null() {
390            self.head = ptr;
391        } else {
392            unsafe {
393                (*tail).get_node().next = ptr;
394            }
395        }
396        self.tail = ptr;
397        self.length += 1;
398    }
399
400    /// Removes and returns the element at the front of the list.
401    pub fn pop_front(&mut self) -> Option<P> {
402        if !self.head.is_null() {
403            let head_ptr = self.head;
404            self._remove_node(head_ptr);
405            unsafe { Some(P::from_raw(head_ptr)) }
406        } else {
407            None
408        }
409    }
410
411    /// Removes and returns the element at the back of the list.
412    #[inline]
413    pub fn pop_back(&mut self) -> Option<P> {
414        if !self.tail.is_null() {
415            let tail_ptr = self.tail;
416            self._remove_node(tail_ptr);
417            unsafe { Some(P::from_raw(tail_ptr)) }
418        } else {
419            None
420        }
421    }
422
423    /// Returns a reference to the front element.
424    #[inline]
425    pub fn get_front(&self) -> Option<&P::Target> {
426        unsafe { if !self.head.is_null() { Some(&(*self.head)) } else { None } }
427    }
428
429    /// Returns a reference to the back element.
430    #[inline]
431    pub fn get_back(&self) -> Option<&P::Target> {
432        unsafe { if !self.tail.is_null() { Some(&(*self.tail)) } else { None } }
433    }
434
435    /// Checks if the given node is the head of the list.
436    #[inline(always)]
437    pub fn is_front(&self, node: &P::Target) -> bool {
438        if self.head.is_null() {
439            false
440        } else {
441            // This comparison is tricky because self.head is *mut HrcWrapper<T>
442            // and node is &mut DListNode<T>.
443            // We need to compare the node address or the wrapper address.
444            // Converting head -> node and comparing addresses of DListNode is safer.
445            ptr::eq(self.head, node)
446        }
447    }
448
449    #[cfg(feature = "std")]
450    pub fn print<U: std::fmt::Debug>(&self) {
451        println!("print list begin! length={}", self.length);
452        let mut ptr = self.head;
453        while !ptr.is_null() {
454            unsafe {
455                // Assuming T can be cast to U for printing, or T implements Debug.
456                // The original code had print<T>, here print<U>.
457                // We'll just print the address for now if T is not Debug?
458                // Or assume T is Debug.
459                // println!("node={:?}", item); // Requires T: Debug
460                ptr = (*ptr).get_node().next;
461            }
462        }
463        println!("print list end:");
464    }
465
466    /// Returns an iterator over the list (borrowed).
467    ///
468    /// # NOTE
469    ///
470    /// If you plan on turn the raw pointer to owned, use drain instead
471    ///
472    /// # Safety
473    ///
474    /// The caller must ensure that the list is not modified in a way that can
475    /// invalidate internal pointers (such as removing elements or dropping
476    /// items) for the duration of the iterator's use.
477    #[inline(always)]
478    pub fn iter<'a>(&'a self) -> DLinkedListIterator<'a, P, Tag> {
479        DLinkedListIterator { list: self, cur: null() }
480    }
481
482    /// Returns a draining iterator that removes items from the list.
483    /// Crucial for cleaning up lists containing owned pointers (like `Box`).
484    ///
485    /// # Note
486    ///
487    /// The iterator removes elements from the **front** of the list (FIFO order),
488    #[inline(always)]
489    pub fn drain<'a>(&'a mut self) -> DLinkedListDrainer<'a, P, Tag> {
490        DLinkedListDrainer { list: self }
491    }
492}
493
494impl<P, Tag> Drop for DLinkedList<P, Tag>
495where
496    P: Pointer,
497    P::Target: DListItem<Tag>,
498{
499    fn drop(&mut self) {
500        // Calling drain will remove all elements from the list and drop them.
501        // The DLinkedListDrainer iterator returns P, which will be dropped
502        // when the iterator is consumed.
503        if mem::needs_drop::<P>() {
504            self.drain().for_each(drop);
505        }
506    }
507}
508
509pub struct DLinkedListIterator<'a, P, Tag>
510where
511    P: Pointer,
512    P::Target: DListItem<Tag>,
513{
514    list: &'a DLinkedList<P, Tag>,
515    cur: *const P::Target,
516}
517
518unsafe impl<'a, P, Tag> Send for DLinkedListIterator<'a, P, Tag>
519where
520    P: Pointer,
521    P::Target: DListItem<Tag>,
522{
523}
524
525impl<'a, P, Tag> Iterator for DLinkedListIterator<'a, P, Tag>
526where
527    P: Pointer,
528    P::Target: DListItem<Tag>,
529{
530    type Item = &'a P::Target;
531
532    fn next(&mut self) -> Option<Self::Item> {
533        if self.cur.is_null() {
534            if self.list.head.is_null() {
535                return None;
536            } else {
537                self.cur = self.list.head;
538            }
539        } else {
540            let next = unsafe { (*self.cur).get_node().next };
541            if next.is_null() {
542                return None;
543            } else {
544                self.cur = next;
545            }
546        }
547        unsafe { Some(&(*self.cur)) }
548    }
549}
550
551pub struct DLinkedListDrainer<'a, P, Tag>
552where
553    P: Pointer,
554    P::Target: DListItem<Tag>,
555{
556    list: &'a mut DLinkedList<P, Tag>,
557}
558
559unsafe impl<'a, P, Tag> Send for DLinkedListDrainer<'a, P, Tag>
560where
561    P: Pointer,
562    P::Target: DListItem<Tag>,
563{
564}
565
566impl<'a, P, Tag> Iterator for DLinkedListDrainer<'a, P, Tag>
567where
568    P: Pointer,
569    P::Target: DListItem<Tag>,
570{
571    type Item = P;
572
573    #[inline]
574    fn next(&mut self) -> Option<P> {
575        self.list.pop_front()
576    }
577}
578
579#[cfg(test)]
580mod tests {
581    use super::*;
582    use std::boxed::Box;
583    use std::cell::UnsafeCell;
584    use std::println;
585    use std::ptr::NonNull;
586    use std::sync::Arc;
587    use std::sync::atomic::{AtomicUsize, Ordering};
588
589    pub struct TestTag;
590
591    #[derive(Debug)]
592    pub struct TestNode {
593        pub value: i64,
594        pub node: UnsafeCell<DListNode<Self, TestTag>>,
595    }
596
597    static ACTIVE_NODE_COUNT: AtomicUsize = AtomicUsize::new(0);
598
599    impl Drop for TestNode {
600        fn drop(&mut self) {
601            ACTIVE_NODE_COUNT.fetch_sub(1, Ordering::SeqCst);
602        }
603    }
604
605    unsafe impl Send for TestNode {}
606
607    unsafe impl DListItem<TestTag> for TestNode {
608        fn get_node(&self) -> &mut DListNode<Self, TestTag> {
609            unsafe { &mut *self.node.get() }
610        }
611    }
612
613    fn new_node(v: i64) -> TestNode {
614        ACTIVE_NODE_COUNT.fetch_add(1, Ordering::SeqCst);
615        TestNode { value: v, node: UnsafeCell::new(DListNode::default()) }
616    }
617
618    #[test]
619    fn test_push_back_box() {
620        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
621
622        let node1 = Box::new(new_node(1));
623        l.push_back(node1);
624
625        let node2 = Box::new(new_node(2));
626        l.push_back(node2);
627
628        let node3 = Box::new(new_node(3));
629        l.push_back(node3);
630
631        assert_eq!(3, l.len());
632
633        let mut iter = l.iter();
634        assert_eq!(iter.next().unwrap().value, 1);
635        assert_eq!(iter.next().unwrap().value, 2);
636        assert_eq!(iter.next().unwrap().value, 3);
637        assert!(iter.next().is_none());
638
639        {
640            let mut drain = l.drain();
641            assert_eq!(drain.next().unwrap().value, 1);
642            assert_eq!(drain.next().unwrap().value, 2);
643            assert_eq!(drain.next().unwrap().value, 3);
644            assert!(drain.next().is_none());
645        }
646        assert_eq!(l.len(), 0);
647    }
648
649    #[test]
650    fn test_push_back_arc() {
651        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
652
653        let node1 = Arc::new(new_node(1));
654        l.push_back(node1);
655
656        let node2 = Arc::new(new_node(2));
657        l.push_back(node2);
658
659        let node3 = Arc::new(new_node(3));
660        l.push_back(node3);
661
662        assert_eq!(3, l.len());
663
664        let mut iter = l.iter();
665        assert_eq!(iter.next().unwrap().value, 1);
666        assert_eq!(iter.next().unwrap().value, 2);
667        assert_eq!(iter.next().unwrap().value, 3);
668        assert!(iter.next().is_none());
669
670        {
671            let mut drain = l.drain();
672            assert_eq!(drain.next().unwrap().value, 1);
673            assert_eq!(drain.next().unwrap().value, 2);
674            assert_eq!(drain.next().unwrap().value, 3);
675            assert!(drain.next().is_none());
676        }
677        assert_eq!(l.len(), 0);
678    }
679
680    #[test]
681    fn test_push_front_box() {
682        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
683
684        let node3 = Box::new(new_node(3));
685        l.push_front(node3);
686
687        let node2 = Box::new(new_node(2));
688        l.push_front(node2);
689
690        let node1 = Box::new(new_node(1));
691        l.push_front(node1);
692
693        assert_eq!(3, l.len());
694
695        let mut iter = l.iter();
696        assert_eq!(iter.next().unwrap().value, 1);
697        assert_eq!(iter.next().unwrap().value, 2);
698        assert_eq!(iter.next().unwrap().value, 3);
699        assert!(iter.next().is_none());
700
701        {
702            let mut drain = l.drain();
703            assert_eq!(drain.next().unwrap().value, 1);
704            assert_eq!(drain.next().unwrap().value, 2);
705            assert_eq!(drain.next().unwrap().value, 3);
706            assert!(drain.next().is_none());
707        }
708        assert_eq!(l.len(), 0);
709    }
710
711    #[test]
712    fn test_push_front_arc() {
713        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
714
715        let node3 = Arc::new(new_node(3));
716        l.push_front(node3);
717
718        let node2 = Arc::new(new_node(2));
719        l.push_front(node2);
720
721        let node1 = Arc::new(new_node(1));
722        l.push_front(node1);
723
724        assert_eq!(3, l.len());
725
726        let mut iter = l.iter();
727        assert_eq!(iter.next().unwrap().value, 1);
728        assert_eq!(iter.next().unwrap().value, 2);
729        assert_eq!(iter.next().unwrap().value, 3);
730        assert!(iter.next().is_none());
731
732        {
733            let mut drain = l.drain();
734            assert_eq!(drain.next().unwrap().value, 1);
735            assert_eq!(drain.next().unwrap().value, 2);
736            assert_eq!(drain.next().unwrap().value, 3);
737            assert!(drain.next().is_none());
738        }
739        assert_eq!(l.len(), 0);
740    }
741
742    #[test]
743    fn test_pop_back_box() {
744        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
745
746        let node1 = Box::new(new_node(1));
747        l.push_back(node1);
748
749        let node2 = Box::new(new_node(2));
750        l.push_back(node2);
751
752        let node3 = Box::new(new_node(3));
753        l.push_back(node3);
754
755        let mut iter = l.iter();
756        assert_eq!(iter.next().unwrap().value, 1);
757        assert_eq!(iter.next().unwrap().value, 2);
758        assert_eq!(iter.next().unwrap().value, 3);
759        assert!(iter.next().is_none());
760
761        let del_node = l.pop_back();
762        assert_eq!(2, l.len());
763        assert!(del_node.is_some());
764        assert_eq!(del_node.unwrap().value, 3);
765
766        let mut iter_remaining = l.iter();
767        assert_eq!(iter_remaining.next().unwrap().value, 1);
768        assert_eq!(iter_remaining.next().unwrap().value, 2);
769        assert!(iter_remaining.next().is_none());
770
771        {
772            let mut drain = l.drain();
773            assert_eq!(drain.next().unwrap().value, 1);
774            assert_eq!(drain.next().unwrap().value, 2);
775            assert!(drain.next().is_none());
776        }
777        assert_eq!(l.len(), 0);
778    }
779
780    #[test]
781    fn test_pop_back_arc() {
782        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
783
784        let node1 = Arc::new(new_node(1));
785        l.push_back(node1);
786
787        let node2 = Arc::new(new_node(2));
788        l.push_back(node2);
789
790        let node3 = Arc::new(new_node(3));
791        l.push_back(node3);
792
793        let mut iter = l.iter();
794        assert_eq!(iter.next().unwrap().value, 1);
795        assert_eq!(iter.next().unwrap().value, 2);
796        assert_eq!(iter.next().unwrap().value, 3);
797        assert!(iter.next().is_none());
798
799        let del_node = l.pop_back();
800        assert_eq!(2, l.len());
801        assert!(del_node.is_some());
802        // Note: The value returned by Arc::from_raw must still be used.
803        assert!(del_node.is_some());
804
805        // Check the order of remaining elements
806        let mut iter = l.iter();
807        assert_eq!(iter.next().unwrap().value, 1);
808        assert_eq!(iter.next().unwrap().value, 2);
809        assert!(iter.next().is_none());
810
811        {
812            let mut drain = l.drain();
813            assert_eq!(drain.next().unwrap().value, 1);
814            assert_eq!(drain.next().unwrap().value, 2);
815            assert!(drain.next().is_none());
816        }
817        assert_eq!(l.len(), 0);
818    }
819
820    #[test]
821    fn test_pop_front_arc() {
822        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
823
824        let node1 = Arc::new(new_node(1));
825        l.push_front(node1);
826
827        let node2 = Arc::new(new_node(2));
828        l.push_front(node2);
829
830        let node3 = Arc::new(new_node(3));
831        l.push_front(node3);
832
833        let mut iter = l.iter();
834        assert_eq!(iter.next().unwrap().value, 3);
835        assert_eq!(iter.next().unwrap().value, 2);
836        assert_eq!(iter.next().unwrap().value, 1);
837        assert!(iter.next().is_none());
838
839        let del_node = l.pop_front();
840        assert_eq!(2, l.len());
841        assert!(del_node.is_some());
842        // Note: The value returned by Arc::from_raw must still be used.
843        assert!(del_node.is_some());
844
845        // Check the order of remaining elements
846        let mut iter = l.iter();
847        assert_eq!(iter.next().unwrap().value, 2);
848        assert_eq!(iter.next().unwrap().value, 1);
849        assert!(iter.next().is_none());
850
851        {
852            assert_eq!(l.pop_front().unwrap().value, 2);
853            assert_eq!(l.pop_front().unwrap().value, 1);
854            assert!(l.pop_front().is_none());
855            assert!(l.pop_back().is_none());
856        }
857        assert_eq!(l.len(), 0);
858    }
859
860    #[test]
861    fn test_iter_box() {
862        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
863
864        let mut count = 0;
865        for _item in l.iter() {
866            count += 1;
867        }
868        assert_eq!(count, 0);
869
870        let node1 = Box::new(new_node(1));
871        l.push_back(node1);
872
873        let node2 = Box::new(new_node(2));
874        l.push_back(node2);
875
876        let node3 = Box::new(new_node(3));
877        l.push_back(node3);
878
879        count = 0;
880        for item in l.iter() {
881            count += 1;
882            println!("{}", item.value);
883        }
884        assert_eq!(count, 3);
885
886        {
887            let mut drain = l.drain();
888            assert_eq!(drain.next().unwrap().value, 1);
889            assert_eq!(drain.next().unwrap().value, 2);
890            assert_eq!(drain.next().unwrap().value, 3);
891            assert!(drain.next().is_none());
892        }
893        assert_eq!(l.len(), 0);
894    }
895
896    #[test]
897    fn test_iter_arc() {
898        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
899
900        let mut count = 0;
901        for _item in l.iter() {
902            count += 1;
903        }
904        assert_eq!(count, 0);
905
906        let node1 = Arc::new(new_node(1));
907        l.push_back(node1);
908
909        let node2 = Arc::new(new_node(2));
910        l.push_back(node2);
911
912        let node3 = Arc::new(new_node(3));
913        l.push_back(node3);
914
915        // Check order
916        let mut iter = l.iter();
917        assert_eq!(iter.next().unwrap().value, 1);
918        assert_eq!(iter.next().unwrap().value, 2);
919        assert_eq!(iter.next().unwrap().value, 3);
920        assert!(iter.next().is_none());
921
922        {
923            let mut drain = l.drain();
924            assert_eq!(drain.next().unwrap().value, 1);
925            assert_eq!(drain.next().unwrap().value, 2);
926            assert_eq!(drain.next().unwrap().value, 3);
927            assert!(drain.next().is_none());
928        }
929        assert_eq!(l.len(), 0);
930    }
931
932    #[test]
933    fn test_single_element_box() {
934        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
935        let node1 = Box::new(new_node(1));
936        l.push_front(node1);
937        let del_node = l.pop_back();
938        assert!(del_node.is_some());
939        assert_eq!(del_node.unwrap().value, 1);
940        assert_eq!(0, l.len());
941        assert!(l.pop_back().is_none());
942
943        let mut l2 = DLinkedList::<Box<TestNode>, TestTag>::new();
944        let node2 = Box::new(new_node(2));
945        l2.push_back(node2);
946        let del_node2 = l2.pop_back();
947        assert!(del_node2.is_some());
948        assert_eq!(del_node2.unwrap().value, 2);
949        assert_eq!(0, l2.len());
950        assert!(l2.pop_back().is_none());
951
952        {
953            let mut drain = l.drain();
954            assert!(drain.next().is_none());
955        }
956        assert_eq!(l.len(), 0);
957
958        {
959            let mut drain = l2.drain();
960            assert!(drain.next().is_none());
961        }
962        assert_eq!(l2.len(), 0);
963    }
964
965    #[test]
966    fn test_single_element_arc() {
967        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
968        let node1 = Arc::new(new_node(1));
969        l.push_front(node1);
970        let del_node = l.pop_back();
971        assert!(del_node.is_some());
972        assert_eq!(0, l.len());
973        assert!(l.pop_back().is_none());
974
975        let mut l2 = DLinkedList::<Arc<TestNode>, TestTag>::new();
976        let node2 = Arc::new(new_node(2));
977        l2.push_back(node2);
978        let del_node2 = l2.pop_back();
979        assert!(del_node2.is_some());
980        assert_eq!(0, l2.len());
981        assert!(l2.pop_back().is_none());
982
983        {
984            let mut drain = l.drain();
985            assert!(drain.next().is_none());
986        }
987        assert_eq!(l.len(), 0);
988
989        {
990            let mut drain = l2.drain();
991            assert!(drain.next().is_none());
992        }
993        assert_eq!(l2.len(), 0);
994    }
995
996    #[test]
997    fn test_drop_box_implementation() {
998        // Reset the counter before the test
999        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1000
1001        {
1002            let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
1003
1004            let node1 = Box::new(new_node(1));
1005            l.push_back(node1);
1006
1007            let node2 = Box::new(new_node(2));
1008            l.push_back(node2);
1009
1010            let node3 = Box::new(new_node(3));
1011            l.push_back(node3);
1012
1013            assert_eq!(l.len(), 3);
1014            assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
1015        } // `l` goes out of scope here, triggering DLinkedList's Drop, which drains and drops nodes.
1016
1017        // All nodes should have been dropped
1018        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1019    }
1020
1021    #[test]
1022    fn test_raw_pointer_list() {
1023        // Reset the counter before the test
1024        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1025
1026        // Manually create nodes as raw pointers
1027        let node1 = Box::into_raw(Box::new(new_node(10)));
1028        let node2 = Box::into_raw(Box::new(new_node(20)));
1029
1030        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1031
1032        {
1033            let mut l = DLinkedList::<*const TestNode, TestTag>::new();
1034            l.push_back(node1);
1035            l.push_back(node2);
1036
1037            let mut iter = l.iter();
1038            assert_eq!(iter.next().unwrap().value, 10);
1039            assert_eq!(iter.next().unwrap().value, 20);
1040            assert!(iter.next().is_none());
1041        } // l dropped here. Because P is *const TestNode, needs_drop is false, so drain is NOT called.
1042
1043        // Nodes should still exist
1044        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1045
1046        unsafe {
1047            // Check values
1048            assert_eq!((*node1).value, 10);
1049            assert_eq!((*node2).value, 20);
1050
1051            // Clean up
1052            drop(Box::from_raw(node1));
1053            drop(Box::from_raw(node2));
1054        }
1055        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1056    }
1057
1058    #[test]
1059    fn test_non_null_list() {
1060        // Reset the counter before the test
1061        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1062
1063        // Manually create nodes
1064        // Box::leak returns &mut T, which helps creating NonNull
1065        let node1 = Box::leak(Box::new(new_node(100)));
1066        let node2 = Box::leak(Box::new(new_node(200)));
1067
1068        let ptr1 = NonNull::from(node1);
1069        let ptr2 = NonNull::from(node2);
1070
1071        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1072
1073        {
1074            let mut l = DLinkedList::<NonNull<TestNode>, TestTag>::new();
1075            l.push_back(ptr1);
1076            l.push_back(ptr2);
1077
1078            let mut iter = l.iter();
1079            assert_eq!(iter.next().unwrap().value, 100);
1080            assert_eq!(iter.next().unwrap().value, 200);
1081            assert!(iter.next().is_none());
1082        } // l dropped here. NonNull doesn't need drop, so no drain.
1083
1084        // Nodes should still exist
1085        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1086
1087        unsafe {
1088            // Clean up
1089            drop(Box::from_raw(ptr1.as_ptr()));
1090            drop(Box::from_raw(ptr2.as_ptr()));
1091        }
1092
1093        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1094    }
1095
1096    #[test]
1097    fn test_clear() {
1098        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1099        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
1100
1101        l.push_back(Box::new(new_node(1)));
1102        l.push_back(Box::new(new_node(2)));
1103        assert_eq!(l.len(), 2);
1104        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1105
1106        l.clear();
1107
1108        assert!(l.is_empty());
1109        assert_eq!(l.len(), 0);
1110        assert!(l.get_front().is_none());
1111        assert!(l.get_back().is_none());
1112        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1113
1114        // Can still push to the list
1115        l.push_back(Box::new(new_node(3)));
1116        assert_eq!(l.len(), 1);
1117        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 1);
1118    }
1119
1120    #[test]
1121    fn test_remove_middle() {
1122        // Reset the counter before the test
1123        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1124        {
1125            let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
1126
1127            let node1 = Box::new(new_node(1));
1128            l.push_back(node1);
1129
1130            let node2 = Box::new(new_node(2));
1131
1132            // NOTE: use `node_p = node2.as_ptr()`  will trigger miri stack borrow rule.
1133            // we use into_raw and then from_raw
1134            let node2_p = Box::into_raw(node2);
1135            l.push_back(unsafe { Box::from_raw(node2_p) });
1136
1137            let node3 = Box::new(new_node(3));
1138            l.push_back(node3);
1139
1140            assert_eq!(l.len(), 3);
1141            assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
1142
1143            let node2 = unsafe { l.remove_node(node2_p).unwrap() };
1144            assert_eq!(l.len(), 2);
1145            assert_eq!(node2.value, 2);
1146
1147            let node4 = Box::new(new_node(4));
1148
1149            let node4_p = Box::into_raw(node4);
1150            assert!(unsafe { l.remove_node(node4_p) }.is_none());
1151            unsafe {
1152                let _ = Box::from_raw(node4_p);
1153            }
1154        } // `l` goes out of scope here, triggering DLinkedList's Drop, which drains and drops nodes.
1155
1156        // All nodes should have been dropped
1157        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1158    }
1159
1160    #[test]
1161    fn test_peak_arc() {
1162        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
1163
1164        let node1 = Arc::new(new_node(1));
1165        l.push_back(node1);
1166
1167        let node2 = Arc::new(new_node(2));
1168        l.push_back(node2);
1169
1170        let node3 = Arc::new(new_node(3));
1171        l.push_back(node3.clone());
1172
1173        let mut iter = l.iter();
1174        assert_eq!(iter.next().unwrap().value, 1);
1175        assert_eq!(iter.next().unwrap().value, 2);
1176        assert_eq!(iter.next().unwrap().value, 3);
1177        assert!(iter.next().is_none());
1178
1179        let node3_p = Arc::as_ptr(&node3);
1180
1181        unsafe { l.peak(node3_p) };
1182
1183        // Check the order of remaining elements
1184        let mut iter = l.iter();
1185        assert_eq!(iter.next().unwrap().value, 3);
1186        assert_eq!(iter.next().unwrap().value, 1);
1187        assert_eq!(iter.next().unwrap().value, 2);
1188        assert!(iter.next().is_none());
1189
1190        {
1191            let mut drain = l.drain();
1192            assert_eq!(drain.next().unwrap().value, 3);
1193            assert_eq!(drain.next().unwrap().value, 1);
1194            assert_eq!(drain.next().unwrap().value, 2);
1195            assert!(drain.next().is_none());
1196        }
1197        assert_eq!(l.len(), 0);
1198    }
1199}
embed_dlist/lib.rs

embed_dlist/
lib.rs
