embed_collections/
dlist.rs

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

embed_collections/
dlist.rs
