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

embed_collections/
dlist.rs
