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        if self.prev.is_null() { None } else { unsafe { Some((*self.prev).get_node()) } }
131    }
132
133    #[inline]
134    fn get_next<'a>(&self) -> Option<&'a mut DListNode<T, Tag>> {
135        if self.next.is_null() { None } else { unsafe { Some((*self.next).get_node()) } }
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) {
240        unsafe {
241            let node = (*item).get_node();
242            if let Some(prev) = node.get_prev() {
243                prev.next = node.next;
244            } else {
245                self.head = node.next;
246            }
247            if let Some(next) = node.get_next() {
248                next.prev = node.prev;
249            } else {
250                self.tail = node.prev;
251            }
252            node.next = null();
253            node.prev = null();
254        }
255        self.length -= 1;
256    }
257
258    /// Remove a node by raw pointer from the middle of the list, and recover P from `item`
259    ///
260    /// NOTE： Due to we need to support Arc, item should be immutable reference.
261    ///
262    /// # Safety
263    ///
264    /// `item` should point the a valid item, which must be already in the list, otherwise will lead to UB.
265    ///
266    /// # Example
267    ///
268    /// ```
269    ///
270    /// use embed_dlist::{DLinkedList, DListItem, DListNode};
271    /// use core::cell::UnsafeCell;
272    /// extern crate alloc;
273    /// use alloc::boxed::Box;
274    ///
275    /// #[derive(Debug)]
276    /// pub struct TestNode {
277    ///     pub value: i64,
278    ///     pub node: UnsafeCell<DListNode<Self, ()>>,
279    /// }
280    ///
281    /// unsafe impl Send for TestNode {}
282    ///
283    /// unsafe impl DListItem<()> for TestNode {
284    ///     fn get_node(&self) -> &mut DListNode<Self, ()> {
285    ///         unsafe { &mut *self.node.get() }
286    ///     }
287    /// }
288    ///
289    /// fn new_node(v: i64) -> TestNode {
290    ///     TestNode { value: v, node: UnsafeCell::new(DListNode::default()) }
291    /// }
292    ///
293    /// let mut l = DLinkedList::<Box<TestNode>, ()>::new();
294    ///
295    /// let node1 = Box::new(new_node(1));
296    /// l.push_back(node1);
297    /// let node2 = Box::new(new_node(2));
298    ///
299    /// // NOTE: use `node_p = node2.as_ptr()`  will trigger miri stack borrow rule.
300    /// // we use into_raw and then from_raw
301    /// let node2_p = Box::into_raw(node2);
302    /// l.push_back(unsafe{Box::from_raw(node2_p)});
303    ///
304    /// let node3 = Box::new(new_node(3));
305    /// l.push_back(node3);
306    /// assert_eq!(l.len(), 3);
307    ///
308    /// let node2 = unsafe { l.remove_node(node2_p) };
309    /// assert_eq!(l.len(), 2);
310    /// assert_eq!(node2.value, 2);
311    /// ```
312    #[inline(always)]
313    pub unsafe fn remove_node(&mut self, item: *const P::Target) -> P {
314        self._remove_node(item);
315        unsafe { P::from_raw(item) }
316    }
317
318    /// Moves a node to the front of the list (e.g., for LRU updates).
319    ///
320    /// NOTE： Due to we need to support Arc, item should be immutable reference.
321    ///
322    /// # Safety
323    ///
324    /// The item must be in the list, otherwise will lead to UB.
325    #[inline(always)]
326    pub unsafe fn peak(&mut self, item: &P::Target) {
327        assert!(!self.head.is_null());
328        if !self.head.is_null() {
329            let head_node = unsafe { (*self.head).get_node() } as *const DListNode<P::Target, Tag>;
330            if ptr::eq(head_node, item.get_node()) {
331                return;
332            }
333        }
334        let p = item as *const P::Target;
335        self._remove_node(p);
336        self.push_front_ptr(p);
337    }
338
339    /// Pushes an element to the front of the list.
340    #[inline]
341    pub fn push_front(&mut self, item: P) {
342        let ptr = item.into_raw();
343        self.push_front_ptr(ptr);
344    }
345
346    #[inline]
347    fn push_front_ptr(&mut self, ptr: *const P::Target) {
348        let node = unsafe { (*ptr).get_node() };
349        let head = self.head;
350        node.next = head;
351        node.prev = null();
352
353        if head.is_null() {
354            self.tail = ptr;
355        } else {
356            unsafe {
357                (*head).get_node().prev = ptr;
358            }
359        }
360        self.head = ptr;
361        self.length += 1;
362    }
363
364    /// Pushes an element to the back of the list.
365    #[inline]
366    pub fn push_back(&mut self, item: P) {
367        let node = item.as_ref().get_node();
368        let tail = self.tail;
369        node.prev = tail;
370        node.next = null();
371
372        let ptr = item.into_raw();
373        if tail.is_null() {
374            self.head = ptr;
375        } else {
376            unsafe {
377                (*tail).get_node().next = ptr;
378            }
379        }
380        self.tail = ptr;
381        self.length += 1;
382    }
383
384    /// Removes and returns the element at the front of the list.
385    pub fn pop_front(&mut self) -> Option<P> {
386        if self.head.is_null() {
387            None
388        } else {
389            let head_ptr = self.head;
390            self._remove_node(head_ptr);
391            unsafe { Some(P::from_raw(head_ptr)) }
392        }
393    }
394
395    /// Removes and returns the element at the back of the list.
396    #[inline]
397    pub fn pop_back(&mut self) -> Option<P> {
398        if self.tail.is_null() {
399            None
400        } else {
401            let tail_ptr = self.tail;
402            self._remove_node(tail_ptr);
403            unsafe { Some(P::from_raw(tail_ptr)) }
404        }
405    }
406
407    /// Returns a reference to the front element.
408    #[inline]
409    pub fn get_front(&self) -> Option<&P::Target> {
410        if self.head.is_null() { None } else { unsafe { Some(&(*self.head)) } }
411    }
412
413    /// Returns a reference to the back element.
414    #[inline]
415    pub fn get_back(&self) -> Option<&P::Target> {
416        if self.tail.is_null() { None } else { unsafe { Some(&(*self.tail)) } }
417    }
418
419    /// Checks if the given node is the head of the list.
420    #[inline(always)]
421    pub fn is_front(&self, node: &P::Target) -> bool {
422        if self.head.is_null() {
423            false
424        } else {
425            // This comparison is tricky because self.head is *mut HrcWrapper<T>
426            // and node is &mut DListNode<T>.
427            // We need to compare the node address or the wrapper address.
428            // Converting head -> node and comparing addresses of DListNode is safer.
429            ptr::eq(self.head, node)
430        }
431    }
432
433    #[cfg(feature = "std")]
434    pub fn print<U: std::fmt::Debug>(&self) {
435        println!("print list begin! length={}", self.length);
436        let mut ptr = self.head;
437        while !ptr.is_null() {
438            unsafe {
439                // Assuming T can be cast to U for printing, or T implements Debug.
440                // The original code had print<T>, here print<U>.
441                // We'll just print the address for now if T is not Debug?
442                // Or assume T is Debug.
443                // println!("node={:?}", item); // Requires T: Debug
444                ptr = (*ptr).get_node().next;
445            }
446        }
447        println!("print list end:");
448    }
449
450    /// Returns an iterator over the list (borrowed).
451    ///
452    /// # NOTE
453    ///
454    /// If you plan on turn the raw pointer to owned, use drain instead
455    ///
456    /// # Safety
457    ///
458    /// The caller must ensure that the list is not modified in a way that can
459    /// invalidate internal pointers (such as removing elements or dropping
460    /// items) for the duration of the iterator's use.
461    #[inline(always)]
462    pub fn iter<'a>(&'a self) -> DLinkedListIterator<'a, P, Tag> {
463        DLinkedListIterator { list: self, cur: null() }
464    }
465
466    /// Returns a draining iterator that removes items from the list.
467    /// Crucial for cleaning up lists containing owned pointers (like `Box`).
468    ///
469    /// # Note
470    ///
471    /// The iterator removes elements from the **front** of the list (FIFO order),
472    #[inline(always)]
473    pub fn drain<'a>(&'a mut self) -> DLinkedListDrainer<'a, P, Tag> {
474        DLinkedListDrainer { list: self }
475    }
476}
477
478impl<P, Tag> Drop for DLinkedList<P, Tag>
479where
480    P: Pointer,
481    P::Target: DListItem<Tag>,
482{
483    fn drop(&mut self) {
484        // Calling drain will remove all elements from the list and drop them.
485        // The DLinkedListDrainer iterator returns P, which will be dropped
486        // when the iterator is consumed.
487        if mem::needs_drop::<P>() {
488            self.drain().for_each(drop);
489        }
490    }
491}
492
493pub struct DLinkedListIterator<'a, P, Tag>
494where
495    P: Pointer,
496    P::Target: DListItem<Tag>,
497{
498    list: &'a DLinkedList<P, Tag>,
499    cur: *const P::Target,
500}
501
502unsafe impl<'a, P, Tag> Send for DLinkedListIterator<'a, P, Tag>
503where
504    P: Pointer,
505    P::Target: DListItem<Tag>,
506{
507}
508
509impl<'a, P, Tag> Iterator for DLinkedListIterator<'a, P, Tag>
510where
511    P: Pointer,
512    P::Target: DListItem<Tag>,
513{
514    type Item = &'a P::Target;
515
516    fn next(&mut self) -> Option<Self::Item> {
517        if self.cur.is_null() {
518            if self.list.head.is_null() {
519                return None;
520            } else {
521                self.cur = self.list.head;
522            }
523        } else {
524            let next = unsafe { (*self.cur).get_node().next };
525            if next.is_null() {
526                return None;
527            } else {
528                self.cur = next;
529            }
530        }
531        unsafe { Some(&(*self.cur)) }
532    }
533}
534
535pub struct DLinkedListDrainer<'a, P, Tag>
536where
537    P: Pointer,
538    P::Target: DListItem<Tag>,
539{
540    list: &'a mut DLinkedList<P, Tag>,
541}
542
543unsafe impl<'a, P, Tag> Send for DLinkedListDrainer<'a, P, Tag>
544where
545    P: Pointer,
546    P::Target: DListItem<Tag>,
547{
548}
549
550impl<'a, P, Tag> Iterator for DLinkedListDrainer<'a, P, Tag>
551where
552    P: Pointer,
553    P::Target: DListItem<Tag>,
554{
555    type Item = P;
556
557    #[inline]
558    fn next(&mut self) -> Option<P> {
559        self.list.pop_front()
560    }
561}
562
563#[cfg(test)]
564mod tests {
565    use super::*;
566    use std::boxed::Box;
567    use std::cell::UnsafeCell;
568    use std::println;
569    use std::ptr::NonNull;
570    use std::sync::Arc;
571    use std::sync::atomic::{AtomicUsize, Ordering};
572
573    pub struct TestTag;
574
575    #[derive(Debug)]
576    pub struct TestNode {
577        pub value: i64,
578        pub node: UnsafeCell<DListNode<Self, TestTag>>,
579    }
580
581    static ACTIVE_NODE_COUNT: AtomicUsize = AtomicUsize::new(0);
582
583    impl Drop for TestNode {
584        fn drop(&mut self) {
585            ACTIVE_NODE_COUNT.fetch_sub(1, Ordering::SeqCst);
586        }
587    }
588
589    unsafe impl Send for TestNode {}
590
591    unsafe impl DListItem<TestTag> for TestNode {
592        fn get_node(&self) -> &mut DListNode<Self, TestTag> {
593            unsafe { &mut *self.node.get() }
594        }
595    }
596
597    fn new_node(v: i64) -> TestNode {
598        ACTIVE_NODE_COUNT.fetch_add(1, Ordering::SeqCst);
599        TestNode { value: v, node: UnsafeCell::new(DListNode::default()) }
600    }
601
602    #[test]
603    fn test_push_back_box() {
604        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
605
606        let node1 = Box::new(new_node(1));
607        l.push_back(node1);
608
609        let node2 = Box::new(new_node(2));
610        l.push_back(node2);
611
612        let node3 = Box::new(new_node(3));
613        l.push_back(node3);
614
615        assert_eq!(3, l.len());
616
617        let mut iter = l.iter();
618        assert_eq!(iter.next().unwrap().value, 1);
619        assert_eq!(iter.next().unwrap().value, 2);
620        assert_eq!(iter.next().unwrap().value, 3);
621        assert!(iter.next().is_none());
622
623        {
624            let mut drain = l.drain();
625            assert_eq!(drain.next().unwrap().value, 1);
626            assert_eq!(drain.next().unwrap().value, 2);
627            assert_eq!(drain.next().unwrap().value, 3);
628            assert!(drain.next().is_none());
629        }
630        assert_eq!(l.len(), 0);
631    }
632
633    #[test]
634    fn test_push_back_arc() {
635        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
636
637        let node1 = Arc::new(new_node(1));
638        l.push_back(node1);
639
640        let node2 = Arc::new(new_node(2));
641        l.push_back(node2);
642
643        let node3 = Arc::new(new_node(3));
644        l.push_back(node3);
645
646        assert_eq!(3, l.len());
647
648        let mut iter = l.iter();
649        assert_eq!(iter.next().unwrap().value, 1);
650        assert_eq!(iter.next().unwrap().value, 2);
651        assert_eq!(iter.next().unwrap().value, 3);
652        assert!(iter.next().is_none());
653
654        {
655            let mut drain = l.drain();
656            assert_eq!(drain.next().unwrap().value, 1);
657            assert_eq!(drain.next().unwrap().value, 2);
658            assert_eq!(drain.next().unwrap().value, 3);
659            assert!(drain.next().is_none());
660        }
661        assert_eq!(l.len(), 0);
662    }
663
664    #[test]
665    fn test_push_front_box() {
666        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
667
668        let node3 = Box::new(new_node(3));
669        l.push_front(node3);
670
671        let node2 = Box::new(new_node(2));
672        l.push_front(node2);
673
674        let node1 = Box::new(new_node(1));
675        l.push_front(node1);
676
677        assert_eq!(3, l.len());
678
679        let mut iter = l.iter();
680        assert_eq!(iter.next().unwrap().value, 1);
681        assert_eq!(iter.next().unwrap().value, 2);
682        assert_eq!(iter.next().unwrap().value, 3);
683        assert!(iter.next().is_none());
684
685        {
686            let mut drain = l.drain();
687            assert_eq!(drain.next().unwrap().value, 1);
688            assert_eq!(drain.next().unwrap().value, 2);
689            assert_eq!(drain.next().unwrap().value, 3);
690            assert!(drain.next().is_none());
691        }
692        assert_eq!(l.len(), 0);
693    }
694
695    #[test]
696    fn test_push_front_arc() {
697        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
698
699        let node3 = Arc::new(new_node(3));
700        l.push_front(node3);
701
702        let node2 = Arc::new(new_node(2));
703        l.push_front(node2);
704
705        let node1 = Arc::new(new_node(1));
706        l.push_front(node1);
707
708        assert_eq!(3, l.len());
709
710        let mut iter = l.iter();
711        assert_eq!(iter.next().unwrap().value, 1);
712        assert_eq!(iter.next().unwrap().value, 2);
713        assert_eq!(iter.next().unwrap().value, 3);
714        assert!(iter.next().is_none());
715
716        {
717            let mut drain = l.drain();
718            assert_eq!(drain.next().unwrap().value, 1);
719            assert_eq!(drain.next().unwrap().value, 2);
720            assert_eq!(drain.next().unwrap().value, 3);
721            assert!(drain.next().is_none());
722        }
723        assert_eq!(l.len(), 0);
724    }
725
726    #[test]
727    fn test_pop_back_box() {
728        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
729
730        let node1 = Box::new(new_node(1));
731        l.push_back(node1);
732
733        let node2 = Box::new(new_node(2));
734        l.push_back(node2);
735
736        let node3 = Box::new(new_node(3));
737        l.push_back(node3);
738
739        let mut iter = l.iter();
740        assert_eq!(iter.next().unwrap().value, 1);
741        assert_eq!(iter.next().unwrap().value, 2);
742        assert_eq!(iter.next().unwrap().value, 3);
743        assert!(iter.next().is_none());
744
745        let del_node = l.pop_back();
746        assert_eq!(2, l.len());
747        assert!(del_node.is_some());
748        assert_eq!(del_node.unwrap().value, 3);
749
750        let mut iter_remaining = l.iter();
751        assert_eq!(iter_remaining.next().unwrap().value, 1);
752        assert_eq!(iter_remaining.next().unwrap().value, 2);
753        assert!(iter_remaining.next().is_none());
754
755        {
756            let mut drain = l.drain();
757            assert_eq!(drain.next().unwrap().value, 1);
758            assert_eq!(drain.next().unwrap().value, 2);
759            assert!(drain.next().is_none());
760        }
761        assert_eq!(l.len(), 0);
762    }
763
764    #[test]
765    fn test_pop_back_arc() {
766        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
767
768        let node1 = Arc::new(new_node(1));
769        l.push_back(node1);
770
771        let node2 = Arc::new(new_node(2));
772        l.push_back(node2);
773
774        let node3 = Arc::new(new_node(3));
775        l.push_back(node3);
776
777        let mut iter = l.iter();
778        assert_eq!(iter.next().unwrap().value, 1);
779        assert_eq!(iter.next().unwrap().value, 2);
780        assert_eq!(iter.next().unwrap().value, 3);
781        assert!(iter.next().is_none());
782
783        let del_node = l.pop_back();
784        assert_eq!(2, l.len());
785        assert!(del_node.is_some());
786        // Note: The value returned by Arc::from_raw must still be used.
787        assert!(del_node.is_some());
788
789        // Check the order of remaining elements
790        let mut iter = l.iter();
791        assert_eq!(iter.next().unwrap().value, 1);
792        assert_eq!(iter.next().unwrap().value, 2);
793        assert!(iter.next().is_none());
794
795        {
796            let mut drain = l.drain();
797            assert_eq!(drain.next().unwrap().value, 1);
798            assert_eq!(drain.next().unwrap().value, 2);
799            assert!(drain.next().is_none());
800        }
801        assert_eq!(l.len(), 0);
802    }
803
804    #[test]
805    fn test_iter_box() {
806        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
807
808        let mut count = 0;
809        for _item in l.iter() {
810            count += 1;
811        }
812        assert_eq!(count, 0);
813
814        let node1 = Box::new(new_node(1));
815        l.push_back(node1);
816
817        let node2 = Box::new(new_node(2));
818        l.push_back(node2);
819
820        let node3 = Box::new(new_node(3));
821        l.push_back(node3);
822
823        count = 0;
824        for item in l.iter() {
825            count += 1;
826            println!("{}", item.value);
827        }
828        assert_eq!(count, 3);
829
830        {
831            let mut drain = l.drain();
832            assert_eq!(drain.next().unwrap().value, 1);
833            assert_eq!(drain.next().unwrap().value, 2);
834            assert_eq!(drain.next().unwrap().value, 3);
835            assert!(drain.next().is_none());
836        }
837        assert_eq!(l.len(), 0);
838    }
839
840    #[test]
841    fn test_iter_arc() {
842        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
843
844        let mut count = 0;
845        for _item in l.iter() {
846            count += 1;
847        }
848        assert_eq!(count, 0);
849
850        let node1 = Arc::new(new_node(1));
851        l.push_back(node1);
852
853        let node2 = Arc::new(new_node(2));
854        l.push_back(node2);
855
856        let node3 = Arc::new(new_node(3));
857        l.push_back(node3);
858
859        // Check order
860        let mut iter = l.iter();
861        assert_eq!(iter.next().unwrap().value, 1);
862        assert_eq!(iter.next().unwrap().value, 2);
863        assert_eq!(iter.next().unwrap().value, 3);
864        assert!(iter.next().is_none());
865
866        {
867            let mut drain = l.drain();
868            assert_eq!(drain.next().unwrap().value, 1);
869            assert_eq!(drain.next().unwrap().value, 2);
870            assert_eq!(drain.next().unwrap().value, 3);
871            assert!(drain.next().is_none());
872        }
873        assert_eq!(l.len(), 0);
874    }
875
876    #[test]
877    fn test_single_element_box() {
878        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
879        let node1 = Box::new(new_node(1));
880        l.push_front(node1);
881        let del_node = l.pop_back();
882        assert!(del_node.is_some());
883        assert_eq!(del_node.unwrap().value, 1);
884        assert_eq!(0, l.len());
885        assert!(l.pop_back().is_none());
886
887        let mut l2 = DLinkedList::<Box<TestNode>, TestTag>::new();
888        let node2 = Box::new(new_node(2));
889        l2.push_back(node2);
890        let del_node2 = l2.pop_back();
891        assert!(del_node2.is_some());
892        assert_eq!(del_node2.unwrap().value, 2);
893        assert_eq!(0, l2.len());
894        assert!(l2.pop_back().is_none());
895
896        {
897            let mut drain = l.drain();
898            assert!(drain.next().is_none());
899        }
900        assert_eq!(l.len(), 0);
901
902        {
903            let mut drain = l2.drain();
904            assert!(drain.next().is_none());
905        }
906        assert_eq!(l2.len(), 0);
907    }
908
909    #[test]
910    fn test_single_element_arc() {
911        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
912        let node1 = Arc::new(new_node(1));
913        l.push_front(node1);
914        let del_node = l.pop_back();
915        assert!(del_node.is_some());
916        assert_eq!(0, l.len());
917        assert!(l.pop_back().is_none());
918
919        let mut l2 = DLinkedList::<Arc<TestNode>, TestTag>::new();
920        let node2 = Arc::new(new_node(2));
921        l2.push_back(node2);
922        let del_node2 = l2.pop_back();
923        assert!(del_node2.is_some());
924        assert_eq!(0, l2.len());
925        assert!(l2.pop_back().is_none());
926
927        {
928            let mut drain = l.drain();
929            assert!(drain.next().is_none());
930        }
931        assert_eq!(l.len(), 0);
932
933        {
934            let mut drain = l2.drain();
935            assert!(drain.next().is_none());
936        }
937        assert_eq!(l2.len(), 0);
938    }
939
940    #[test]
941    fn test_drop_box_implementation() {
942        // Reset the counter before the test
943        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
944
945        {
946            let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
947
948            let node1 = Box::new(new_node(1));
949            l.push_back(node1);
950
951            let node2 = Box::new(new_node(2));
952            l.push_back(node2);
953
954            let node3 = Box::new(new_node(3));
955            l.push_back(node3);
956
957            assert_eq!(l.len(), 3);
958            assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
959        } // `l` goes out of scope here, triggering DLinkedList's Drop, which drains and drops nodes.
960
961        // All nodes should have been dropped
962        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
963    }
964
965    #[test]
966    fn test_raw_pointer_list() {
967        // Reset the counter before the test
968        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
969
970        // Manually create nodes as raw pointers
971        let node1 = Box::into_raw(Box::new(new_node(10)));
972        let node2 = Box::into_raw(Box::new(new_node(20)));
973
974        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
975
976        {
977            let mut l = DLinkedList::<*const TestNode, TestTag>::new();
978            l.push_back(node1);
979            l.push_back(node2);
980
981            let mut iter = l.iter();
982            assert_eq!(iter.next().unwrap().value, 10);
983            assert_eq!(iter.next().unwrap().value, 20);
984            assert!(iter.next().is_none());
985        } // l dropped here. Because P is *const TestNode, needs_drop is false, so drain is NOT called.
986
987        // Nodes should still exist
988        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
989
990        unsafe {
991            // Check values
992            assert_eq!((*node1).value, 10);
993            assert_eq!((*node2).value, 20);
994
995            // Clean up
996            drop(Box::from_raw(node1));
997            drop(Box::from_raw(node2));
998        }
999        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1000    }
1001
1002    #[test]
1003    fn test_non_null_list() {
1004        // Reset the counter before the test
1005        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1006
1007        // Manually create nodes
1008        // Box::leak returns &mut T, which helps creating NonNull
1009        let node1 = Box::leak(Box::new(new_node(100)));
1010        let node2 = Box::leak(Box::new(new_node(200)));
1011
1012        let ptr1 = NonNull::from(node1);
1013        let ptr2 = NonNull::from(node2);
1014
1015        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1016
1017        {
1018            let mut l = DLinkedList::<NonNull<TestNode>, TestTag>::new();
1019            l.push_back(ptr1);
1020            l.push_back(ptr2);
1021
1022            let mut iter = l.iter();
1023            assert_eq!(iter.next().unwrap().value, 100);
1024            assert_eq!(iter.next().unwrap().value, 200);
1025            assert!(iter.next().is_none());
1026        } // l dropped here. NonNull doesn't need drop, so no drain.
1027
1028        // Nodes should still exist
1029        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1030
1031        unsafe {
1032            // Clean up
1033            drop(Box::from_raw(ptr1.as_ptr()));
1034            drop(Box::from_raw(ptr2.as_ptr()));
1035        }
1036
1037        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1038    }
1039
1040    #[test]
1041    fn test_clear() {
1042        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1043        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
1044
1045        l.push_back(Box::new(new_node(1)));
1046        l.push_back(Box::new(new_node(2)));
1047        assert_eq!(l.len(), 2);
1048        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
1049
1050        l.clear();
1051
1052        assert!(l.is_empty());
1053        assert_eq!(l.len(), 0);
1054        assert!(l.get_front().is_none());
1055        assert!(l.get_back().is_none());
1056        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1057
1058        // Can still push to the list
1059        l.push_back(Box::new(new_node(3)));
1060        assert_eq!(l.len(), 1);
1061        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 1);
1062    }
1063
1064    #[test]
1065    fn test_remove_middle() {
1066        // Reset the counter before the test
1067        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
1068        {
1069            let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
1070
1071            let node1 = Box::new(new_node(1));
1072            l.push_back(node1);
1073
1074            let node2 = Box::new(new_node(2));
1075
1076            // NOTE: use `node_p = node2.as_ptr()`  will trigger miri stack borrow rule.
1077            // we use into_raw and then from_raw
1078            let node2_p = Box::into_raw(node2);
1079            l.push_back(unsafe { Box::from_raw(node2_p) });
1080
1081            let node3 = Box::new(new_node(3));
1082            l.push_back(node3);
1083
1084            assert_eq!(l.len(), 3);
1085            assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
1086
1087            let node2 = unsafe { l.remove_node(node2_p) };
1088            assert_eq!(l.len(), 2);
1089            assert_eq!(node2.value, 2);
1090        } // `l` goes out of scope here, triggering DLinkedList's Drop, which drains and drops nodes.
1091
1092        // All nodes should have been dropped
1093        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
1094    }
1095}
embed_dlist/lib.rs

embed_dlist/
lib.rs
