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///
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    #[cfg(feature = "std")]
336    pub fn print<U: std::fmt::Debug>(&self) {
337        println!("print list begin! length={}", self.length);
338        let mut ptr = self.head;
339        while !ptr.is_null() {
340            unsafe {
341                // Assuming T can be cast to U for printing, or T implements Debug.
342                // The original code had print<T>, here print<U>.
343                // We'll just print the address for now if T is not Debug?
344                // Or assume T is Debug.
345                // println!("node={:?}", item); // Requires T: Debug
346                ptr = (*ptr).get_node().next;
347            }
348        }
349        println!("print list end:");
350    }
351
352    /// Returns an iterator over the list (borrowed).
353    ///
354    /// # NOTE
355    ///
356    /// If you plan on turn the raw pointer to owned, use drain instead
357    ///
358    /// # Safety
359    ///
360    /// The caller must ensure that the list is not modified in a way that can
361    /// invalidate internal pointers (such as removing elements or dropping
362    /// items) for the duration of the iterator's use.
363    #[inline(always)]
364    pub fn iter<'a>(&'a self) -> DLinkedListIterator<'a, P, Tag> {
365        DLinkedListIterator { list: self, cur: null() }
366    }
367
368    /// Returns a draining iterator that removes items from the list.
369    /// Crucial for cleaning up lists containing owned pointers (like `Box`).
370    #[inline(always)]
371    pub fn drain<'a>(&'a mut self) -> DLinkedListDrainer<'a, P, Tag> {
372        DLinkedListDrainer { list: self }
373    }
374}
375
376impl<P, Tag> Drop for DLinkedList<P, Tag>
377where
378    P: Pointer,
379    P::Target: DListItem<Tag>,
380{
381    fn drop(&mut self) {
382        // Calling drain will remove all elements from the list and drop them.
383        // The DLinkedListDrainer iterator returns P, which will be dropped
384        // when the iterator is consumed.
385        if mem::needs_drop::<P>() {
386            self.drain().for_each(drop);
387        }
388    }
389}
390
391pub struct DLinkedListIterator<'a, P, Tag>
392where
393    P: Pointer,
394    P::Target: DListItem<Tag>,
395{
396    list: &'a DLinkedList<P, Tag>,
397    cur: *const P::Target,
398}
399
400unsafe impl<'a, P, Tag> Send for DLinkedListIterator<'a, P, Tag>
401where
402    P: Pointer,
403    P::Target: DListItem<Tag>,
404{
405}
406
407impl<'a, P, Tag> Iterator for DLinkedListIterator<'a, P, Tag>
408where
409    P: Pointer,
410    P::Target: DListItem<Tag>,
411{
412    type Item = &'a P::Target;
413
414    fn next(&mut self) -> Option<Self::Item> {
415        if self.cur.is_null() {
416            if self.list.head.is_null() {
417                return None;
418            } else {
419                self.cur = self.list.head;
420            }
421        } else {
422            let next = unsafe { (*self.cur).get_node().next };
423            if next.is_null() {
424                return None;
425            } else {
426                self.cur = next;
427            }
428        }
429        unsafe { Some(&(*self.cur)) }
430    }
431}
432
433pub struct DLinkedListDrainer<'a, P, Tag>
434where
435    P: Pointer,
436    P::Target: DListItem<Tag>,
437{
438    list: &'a mut DLinkedList<P, Tag>,
439}
440
441unsafe impl<'a, P, Tag> Send for DLinkedListDrainer<'a, P, Tag>
442where
443    P: Pointer,
444    P::Target: DListItem<Tag>,
445{
446}
447
448impl<'a, P, Tag> Iterator for DLinkedListDrainer<'a, P, Tag>
449where
450    P: Pointer,
451    P::Target: DListItem<Tag>,
452{
453    type Item = P;
454
455    #[inline]
456    fn next(&mut self) -> Option<P> {
457        self.list.pop_back()
458    }
459}
460
461#[cfg(test)]
462mod tests {
463    use super::*;
464    use std::cell::UnsafeCell;
465    use std::ptr::NonNull;
466    use std::sync::Arc;
467    use std::sync::atomic::{AtomicUsize, Ordering};
468
469    pub struct TestTag;
470
471    #[derive(Debug)]
472    pub struct TestNode {
473        pub value: i64,
474        pub node: UnsafeCell<DListNode<Self, TestTag>>,
475    }
476
477    static ACTIVE_NODE_COUNT: AtomicUsize = AtomicUsize::new(0);
478
479    impl Drop for TestNode {
480        fn drop(&mut self) {
481            ACTIVE_NODE_COUNT.fetch_sub(1, Ordering::SeqCst);
482        }
483    }
484
485    unsafe impl Send for TestNode {}
486
487    unsafe impl DListItem<TestTag> for TestNode {
488        fn get_node(&self) -> &mut DListNode<Self, TestTag> {
489            unsafe { &mut *self.node.get() }
490        }
491    }
492
493    fn new_node(v: i64) -> TestNode {
494        ACTIVE_NODE_COUNT.fetch_add(1, Ordering::SeqCst);
495        TestNode { value: v, node: UnsafeCell::new(DListNode::default()) }
496    }
497
498    #[test]
499    fn test_push_back_box() {
500        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
501
502        let node1 = Box::new(new_node(1));
503        l.push_back(node1);
504
505        let node2 = Box::new(new_node(2));
506        l.push_back(node2);
507
508        let node3 = Box::new(new_node(3));
509        l.push_back(node3);
510
511        assert_eq!(3, l.get_length());
512
513        let mut iter = l.iter();
514        assert_eq!(iter.next().unwrap().value, 1);
515        assert_eq!(iter.next().unwrap().value, 2);
516        assert_eq!(iter.next().unwrap().value, 3);
517        assert!(iter.next().is_none());
518
519        {
520            let mut drain = l.drain();
521            assert_eq!(drain.next().unwrap().value, 3);
522            assert_eq!(drain.next().unwrap().value, 2);
523            assert_eq!(drain.next().unwrap().value, 1);
524            assert!(drain.next().is_none());
525        }
526        assert_eq!(l.get_length(), 0);
527    }
528
529    #[test]
530    fn test_push_back_arc() {
531        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
532
533        let node1 = Arc::new(new_node(1));
534        l.push_back(node1);
535
536        let node2 = Arc::new(new_node(2));
537        l.push_back(node2);
538
539        let node3 = Arc::new(new_node(3));
540        l.push_back(node3);
541
542        assert_eq!(3, l.get_length());
543
544        let mut iter = l.iter();
545        assert_eq!(iter.next().unwrap().value, 1);
546        assert_eq!(iter.next().unwrap().value, 2);
547        assert_eq!(iter.next().unwrap().value, 3);
548        assert!(iter.next().is_none());
549
550        {
551            let mut drain = l.drain();
552            assert_eq!(drain.next().unwrap().value, 3);
553            assert_eq!(drain.next().unwrap().value, 2);
554            assert_eq!(drain.next().unwrap().value, 1);
555            assert!(drain.next().is_none());
556        }
557        assert_eq!(l.get_length(), 0);
558    }
559
560    #[test]
561    fn test_push_front_box() {
562        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
563
564        let node3 = Box::new(new_node(3));
565        l.push_front(node3);
566
567        let node2 = Box::new(new_node(2));
568        l.push_front(node2);
569
570        let node1 = Box::new(new_node(1));
571        l.push_front(node1);
572
573        assert_eq!(3, l.get_length());
574
575        let mut iter = l.iter();
576        assert_eq!(iter.next().unwrap().value, 1);
577        assert_eq!(iter.next().unwrap().value, 2);
578        assert_eq!(iter.next().unwrap().value, 3);
579        assert!(iter.next().is_none());
580
581        {
582            let mut drain = l.drain();
583            assert_eq!(drain.next().unwrap().value, 3);
584            assert_eq!(drain.next().unwrap().value, 2);
585            assert_eq!(drain.next().unwrap().value, 1);
586            assert!(drain.next().is_none());
587        }
588        assert_eq!(l.get_length(), 0);
589    }
590
591    #[test]
592    fn test_push_front_arc() {
593        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
594
595        let node3 = Arc::new(new_node(3));
596        l.push_front(node3);
597
598        let node2 = Arc::new(new_node(2));
599        l.push_front(node2);
600
601        let node1 = Arc::new(new_node(1));
602        l.push_front(node1);
603
604        assert_eq!(3, l.get_length());
605
606        let mut iter = l.iter();
607        assert_eq!(iter.next().unwrap().value, 1);
608        assert_eq!(iter.next().unwrap().value, 2);
609        assert_eq!(iter.next().unwrap().value, 3);
610        assert!(iter.next().is_none());
611
612        {
613            let mut drain = l.drain();
614            assert_eq!(drain.next().unwrap().value, 3);
615            assert_eq!(drain.next().unwrap().value, 2);
616            assert_eq!(drain.next().unwrap().value, 1);
617            assert!(drain.next().is_none());
618        }
619        assert_eq!(l.get_length(), 0);
620    }
621
622    #[test]
623    fn test_pop_back_box() {
624        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
625
626        let node1 = Box::new(new_node(1));
627        l.push_back(node1);
628
629        let node2 = Box::new(new_node(2));
630        l.push_back(node2);
631
632        let node3 = Box::new(new_node(3));
633        l.push_back(node3);
634
635        let mut iter = l.iter();
636        assert_eq!(iter.next().unwrap().value, 1);
637        assert_eq!(iter.next().unwrap().value, 2);
638        assert_eq!(iter.next().unwrap().value, 3);
639        assert!(iter.next().is_none());
640
641        let del_node = l.pop_back();
642        assert_eq!(2, l.get_length());
643        assert!(del_node.is_some());
644        assert_eq!(del_node.unwrap().value, 3);
645
646        let mut iter_remaining = l.iter();
647        assert_eq!(iter_remaining.next().unwrap().value, 1);
648        assert_eq!(iter_remaining.next().unwrap().value, 2);
649        assert!(iter_remaining.next().is_none());
650
651        {
652            let mut drain = l.drain();
653            assert_eq!(drain.next().unwrap().value, 2);
654            assert_eq!(drain.next().unwrap().value, 1);
655            assert!(drain.next().is_none());
656        }
657        assert_eq!(l.get_length(), 0);
658    }
659
660    #[test]
661    fn test_pop_back_arc() {
662        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
663
664        let node1 = Arc::new(new_node(1));
665        l.push_back(node1);
666
667        let node2 = Arc::new(new_node(2));
668        l.push_back(node2);
669
670        let node3 = Arc::new(new_node(3));
671        l.push_back(node3);
672
673        let mut iter = l.iter();
674        assert_eq!(iter.next().unwrap().value, 1);
675        assert_eq!(iter.next().unwrap().value, 2);
676        assert_eq!(iter.next().unwrap().value, 3);
677        assert!(iter.next().is_none());
678
679        let del_node = l.pop_back();
680        assert_eq!(2, l.get_length());
681        assert!(del_node.is_some());
682        // Note: The value returned by Arc::from_raw must still be used.
683        assert!(del_node.is_some());
684
685        // Check the order of remaining elements
686        let mut iter = l.iter();
687        assert_eq!(iter.next().unwrap().value, 1);
688        assert_eq!(iter.next().unwrap().value, 2);
689        assert!(iter.next().is_none());
690
691        {
692            let mut drain = l.drain();
693            assert_eq!(drain.next().unwrap().value, 2);
694            assert_eq!(drain.next().unwrap().value, 1);
695            assert!(drain.next().is_none());
696        }
697        assert_eq!(l.get_length(), 0);
698    }
699
700    #[test]
701    fn test_iter_box() {
702        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
703
704        let mut count = 0;
705        for _item in l.iter() {
706            count += 1;
707        }
708        assert_eq!(count, 0);
709
710        let node1 = Box::new(new_node(1));
711        l.push_back(node1);
712
713        let node2 = Box::new(new_node(2));
714        l.push_back(node2);
715
716        let node3 = Box::new(new_node(3));
717        l.push_back(node3);
718
719        count = 0;
720        for item in l.iter() {
721            count += 1;
722            println!("{}", item.value);
723        }
724        assert_eq!(count, 3);
725
726        {
727            let mut drain = l.drain();
728            assert_eq!(drain.next().unwrap().value, 3);
729            assert_eq!(drain.next().unwrap().value, 2);
730            assert_eq!(drain.next().unwrap().value, 1);
731            assert!(drain.next().is_none());
732        }
733        assert_eq!(l.get_length(), 0);
734    }
735
736    #[test]
737    fn test_iter_arc() {
738        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
739
740        let mut count = 0;
741        for _item in l.iter() {
742            count += 1;
743        }
744        assert_eq!(count, 0);
745
746        let node1 = Arc::new(new_node(1));
747        l.push_back(node1);
748
749        let node2 = Arc::new(new_node(2));
750        l.push_back(node2);
751
752        let node3 = Arc::new(new_node(3));
753        l.push_back(node3);
754
755        // Check order
756        let mut iter = l.iter();
757        assert_eq!(iter.next().unwrap().value, 1);
758        assert_eq!(iter.next().unwrap().value, 2);
759        assert_eq!(iter.next().unwrap().value, 3);
760        assert!(iter.next().is_none());
761
762        {
763            let mut drain = l.drain();
764            assert_eq!(drain.next().unwrap().value, 3);
765            assert_eq!(drain.next().unwrap().value, 2);
766            assert_eq!(drain.next().unwrap().value, 1);
767            assert!(drain.next().is_none());
768        }
769        assert_eq!(l.get_length(), 0);
770    }
771
772    #[test]
773    fn test_single_element_box() {
774        let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
775        let node1 = Box::new(new_node(1));
776        l.push_front(node1);
777        let del_node = l.pop_back();
778        assert!(del_node.is_some());
779        assert_eq!(del_node.unwrap().value, 1);
780        assert_eq!(0, l.get_length());
781        assert!(l.pop_back().is_none());
782
783        let mut l2 = DLinkedList::<Box<TestNode>, TestTag>::new();
784        let node2 = Box::new(new_node(2));
785        l2.push_back(node2);
786        let del_node2 = l2.pop_back();
787        assert!(del_node2.is_some());
788        assert_eq!(del_node2.unwrap().value, 2);
789        assert_eq!(0, l2.get_length());
790        assert!(l2.pop_back().is_none());
791
792        {
793            let mut drain = l.drain();
794            assert!(drain.next().is_none());
795        }
796        assert_eq!(l.get_length(), 0);
797
798        {
799            let mut drain = l2.drain();
800            assert!(drain.next().is_none());
801        }
802        assert_eq!(l2.get_length(), 0);
803    }
804
805    #[test]
806    fn test_single_element_arc() {
807        let mut l = DLinkedList::<Arc<TestNode>, TestTag>::new();
808        let node1 = Arc::new(new_node(1));
809        l.push_front(node1);
810        let del_node = l.pop_back();
811        assert!(del_node.is_some());
812        assert_eq!(0, l.get_length());
813        assert!(l.pop_back().is_none());
814
815        let mut l2 = DLinkedList::<Arc<TestNode>, TestTag>::new();
816        let node2 = Arc::new(new_node(2));
817        l2.push_back(node2);
818        let del_node2 = l2.pop_back();
819        assert!(del_node2.is_some());
820        assert_eq!(0, l2.get_length());
821        assert!(l2.pop_back().is_none());
822
823        {
824            let mut drain = l.drain();
825            assert!(drain.next().is_none());
826        }
827        assert_eq!(l.get_length(), 0);
828
829        {
830            let mut drain = l2.drain();
831            assert!(drain.next().is_none());
832        }
833        assert_eq!(l2.get_length(), 0);
834    }
835
836    #[test]
837    fn test_drop_box_implementation() {
838        // Reset the counter before the test
839        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
840
841        {
842            let mut l = DLinkedList::<Box<TestNode>, TestTag>::new();
843
844            let node1 = Box::new(new_node(1));
845            l.push_back(node1);
846
847            let node2 = Box::new(new_node(2));
848            l.push_back(node2);
849
850            let node3 = Box::new(new_node(3));
851            l.push_back(node3);
852
853            assert_eq!(l.get_length(), 3);
854            assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 3);
855        } // `l` goes out of scope here, triggering DLinkedList's Drop, which drains and drops nodes.
856
857        // All nodes should have been dropped
858        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
859    }
860
861    #[test]
862    fn test_raw_pointer_list() {
863        // Reset the counter before the test
864        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
865
866        // Manually create nodes as raw pointers
867        let node1 = Box::into_raw(Box::new(new_node(10)));
868        let node2 = Box::into_raw(Box::new(new_node(20)));
869
870        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
871
872        {
873            let mut l = DLinkedList::<*const TestNode, TestTag>::new();
874            l.push_back(node1);
875            l.push_back(node2);
876
877            let mut iter = l.iter();
878            assert_eq!(iter.next().unwrap().value, 10);
879            assert_eq!(iter.next().unwrap().value, 20);
880            assert!(iter.next().is_none());
881        } // l dropped here. Because P is *const TestNode, needs_drop is false, so drain is NOT called.
882
883        // Nodes should still exist
884        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
885
886        unsafe {
887            // Check values
888            assert_eq!((*node1).value, 10);
889            assert_eq!((*node2).value, 20);
890
891            // Clean up
892            drop(Box::from_raw(node1));
893            drop(Box::from_raw(node2));
894        }
895
896        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
897    }
898
899    #[test]
900    fn test_non_null_list() {
901        // Reset the counter before the test
902        ACTIVE_NODE_COUNT.store(0, Ordering::SeqCst);
903
904        // Manually create nodes
905        // Box::leak returns &mut T, which helps creating NonNull
906        let node1 = Box::leak(Box::new(new_node(100)));
907        let node2 = Box::leak(Box::new(new_node(200)));
908
909        let ptr1 = NonNull::from(node1);
910        let ptr2 = NonNull::from(node2);
911
912        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
913
914        {
915            let mut l = DLinkedList::<NonNull<TestNode>, TestTag>::new();
916            l.push_back(ptr1);
917            l.push_back(ptr2);
918
919            let mut iter = l.iter();
920            assert_eq!(iter.next().unwrap().value, 100);
921            assert_eq!(iter.next().unwrap().value, 200);
922            assert!(iter.next().is_none());
923        } // l dropped here. NonNull doesn't need drop, so no drain.
924
925        // Nodes should still exist
926        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 2);
927
928        unsafe {
929            // Clean up
930            drop(Box::from_raw(ptr1.as_ptr()));
931            drop(Box::from_raw(ptr2.as_ptr()));
932        }
933
934        assert_eq!(ACTIVE_NODE_COUNT.load(Ordering::SeqCst), 0);
935    }
936}
embed_collections/dlist.rs

embed_collections/
dlist.rs
