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

embed_dlist/
lib.rs
