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

embed_collections/
dlist.rs
