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

embed_collections/
dlist.rs
