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

embed_collections/
dlist.rs
