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

embed_collections/
dlist.rs
