embed_collections/
seg_list.rs

1//! Segmented List - A segmented list with cache-friendly node sizes.
2//!
3//! Each segment is a singly linked list node containing dynamically calculated
4//! number of elements based on cache line size and element size.
5
6use alloc::alloc::{alloc, dealloc, handle_alloc_error};
7use core::alloc::Layout;
8use core::mem::{MaybeUninit, align_of, size_of};
9use core::ptr::{NonNull, null_mut};
10
11/// Cache line size in bytes
12#[cfg(any(
13    target_arch = "x86_64",
14    target_arch = "aarch64",
15    target_arch = "arm64ec",
16    target_arch = "powerpc64",
17))]
18pub const CACHE_LINE_SIZE: usize = 128;
19#[cfg(not(any(
20    target_arch = "x86_64",
21    target_arch = "aarch64",
22    target_arch = "arm64ec",
23    target_arch = "powerpc64",
24)))]
25pub const CACHE_LINE_SIZE: usize = 64;
26
27/// Segmented list with cache-friendly segment sizes
28///
29/// Each segment's capacity is calculated at runtime based on T's size
30/// to fit within a cache line.
31///
32/// NOTE: T is allow to larger than `CACHE_LINE_SIZE`, in this case SegList will ensure at least 2
33/// items in one segment. But when T larger than 128B, you should consider put T into Box.
34///
35pub struct SegList<T> {
36    /// Pointer to the last segment (tail.get_header().next points to first element), to reduce the main struct size
37    tail: NonNull<SegHeader<T>>,
38    /// Total number of elements in the list
39    count: usize,
40}
41
42unsafe impl<T: Send> Send for SegList<T> {}
43unsafe impl<T: Send> Sync for SegList<T> {}
44
45impl<T> SegList<T> {
46    /// Create a new empty SegList with one allocated segment
47    pub fn new() -> Self {
48        let mut seg = unsafe { Segment::<T>::alloc(null_mut(), null_mut()) };
49        let header_ptr = seg.header.as_ptr();
50        let header = seg.get_header_mut();
51        // Make it circular: tail.next points to head (itself for now)
52        header.next = header_ptr;
53        Self { tail: seg.header, count: 0 }
54    }
55
56    /// Returns true if the list is empty
57    #[inline(always)]
58    pub fn is_empty(&self) -> bool {
59        self.count == 0
60    }
61
62    /// Get the capacity of each segment
63    #[inline(always)]
64    pub const fn segment_cap() -> usize {
65        Segment::<T>::LAYOUT_INFO.0
66    }
67
68    /// Returns the total number of elements in the list
69    #[inline(always)]
70    pub fn len(&self) -> usize {
71        self.count
72    }
73
74    /// Push an element to the back of the list
75    pub fn push(&mut self, item: T) {
76        unsafe {
77            let mut tail_seg = Segment::from_raw(self.tail);
78            if tail_seg.is_full() {
79                let tail_ptr = tail_seg.header.as_ptr();
80                let cur = tail_seg.get_header_mut();
81                let new_seg = Segment::alloc(tail_ptr, cur.next);
82                cur.next = new_seg.header.as_ptr();
83                self.tail = new_seg.header;
84                tail_seg = new_seg;
85            }
86            tail_seg.push(item);
87        }
88        self.count += 1;
89    }
90
91    /// Pop an element from the back of the list
92    pub fn pop(&mut self) -> Option<T> {
93        if self.count == 0 {
94            return None;
95        }
96        unsafe {
97            let mut tail_seg = Segment::from_raw(self.tail);
98            let (item, is_empty) = tail_seg.pop();
99            if is_empty {
100                let cur = tail_seg.get_header_mut();
101                let first_ptr = cur.next;
102                let cur_prev = cur.prev;
103                if self.tail.as_ptr() != first_ptr && !cur_prev.is_null() {
104                    // More than one segment: remove tail segment
105                    self.tail = NonNull::new_unchecked(cur_prev);
106                    (*self.tail.as_ptr()).next = first_ptr;
107                    tail_seg.dealloc();
108                }
109                // If only one segment, keep it for future use
110            }
111            self.count -= 1;
112            Some(item)
113        }
114    }
115
116    // Break the cycle and free all segments
117    #[inline]
118    fn break_first_node(&mut self) -> Segment<T> {
119        let tail_header = unsafe { self.tail.as_mut() };
120        let first = tail_header.next;
121        tail_header.next = null_mut();
122        unsafe { Segment::from_raw(NonNull::new_unchecked(first)) }
123    }
124
125    /// Returns an iterator over the list
126    pub fn iter(&self) -> SegListIter<'_, T> {
127        let head = unsafe { self.tail.as_ref().next };
128        let first_seg = if head.is_null() {
129            None
130        } else {
131            Some(unsafe { Segment::from_raw(NonNull::new_unchecked(head)) })
132        };
133        SegListIter {
134            cur: first_seg,
135            cur_idx: 0,
136            remaining: self.count,
137            _marker: core::marker::PhantomData,
138        }
139    }
140
141    /// Returns a mutable iterator over the list
142    pub fn iter_mut(&mut self) -> SegListIterMut<'_, T> {
143        let head = unsafe { self.tail.as_ref().next };
144        let first_seg = if head.is_null() {
145            None
146        } else {
147            Some(unsafe { Segment::from_raw(NonNull::new_unchecked(head)) })
148        };
149        SegListIterMut {
150            cur: first_seg,
151            cur_idx: 0,
152            remaining: self.count,
153            _marker: core::marker::PhantomData,
154        }
155    }
156
157    /// Returns a draining iterator that consumes the list and yields elements from head to tail
158    pub fn drain(mut self) -> SegListDrain<T> {
159        // Break the cycle and get the first segment
160        let first = self.break_first_node();
161        // To prevent drop from being called
162        core::mem::forget(self);
163
164        SegListDrain { cur: Some(first), cur_idx: 0 }
165    }
166
167    /// Returns a reference to the first element in the list
168    #[inline]
169    pub fn first(&self) -> Option<&T> {
170        self.iter().next()
171    }
172
173    /// Returns a reference to the last element in the list
174    #[inline]
175    pub fn last(&self) -> Option<&T> {
176        if self.is_empty() {
177            return None;
178        }
179        // SAFETY: tail always points to a valid segment with at least one element
180        unsafe {
181            let header = self.tail.as_ref();
182            let count = header.count;
183            let items = (self.tail.as_ptr() as *mut u8).add(Segment::<T>::LAYOUT_INFO.1)
184                as *mut MaybeUninit<T>;
185            Some((*items.add(count - 1)).assume_init_ref())
186        }
187    }
188
189    /// Returns a mutable reference to the last element in the list
190    #[inline]
191    pub fn last_mut(&mut self) -> Option<&mut T> {
192        if self.is_empty() {
193            return None;
194        }
195        // SAFETY: tail always points to a valid segment with at least one element
196        unsafe {
197            let header = self.tail.as_mut();
198            let count = header.count;
199            let items = (self.tail.as_ptr() as *mut u8).add(Segment::<T>::LAYOUT_INFO.1)
200                as *mut MaybeUninit<T>;
201            Some((*items.add(count - 1)).assume_init_mut())
202        }
203    }
204
205    /// Clear all elements from the list
206    pub fn clear(&mut self) {
207        while self.pop().is_some() {}
208    }
209}
210
211impl<T> Default for SegList<T> {
212    fn default() -> Self {
213        Self::new()
214    }
215}
216
217impl<T> Drop for SegList<T> {
218    fn drop(&mut self) {
219        // Break the cycle and get the first segment
220        let mut cur = self.break_first_node();
221        loop {
222            // Save next pointer before dealloc
223            let next = cur.get_header().next;
224            unsafe { cur.dealloc() };
225            if next.is_null() {
226                break;
227            }
228            cur = unsafe { Segment::from_raw(NonNull::new_unchecked(next)) };
229        }
230    }
231}
232
233impl<T> IntoIterator for SegList<T> {
234    type Item = T;
235    type IntoIter = SegListDrain<T>;
236
237    fn into_iter(self) -> Self::IntoIter {
238        self.drain()
239    }
240}
241
242impl<T: core::fmt::Debug> core::fmt::Debug for SegList<T> {
243    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
244        f.debug_struct("SegList").field("len", &self.len()).finish()
245    }
246}
247
248/// Segment header containing metadata
249#[repr(C)]
250struct SegHeader<T> {
251    /// Count of valid elements in this segment
252    count: usize,
253    prev: *mut SegHeader<T>,
254    /// Next segment in the list
255    next: *mut SegHeader<T>,
256}
257
258/// A segment containing header and element storage
259struct Segment<T> {
260    /// Pointer to the header
261    header: NonNull<SegHeader<T>>,
262    /// Pointer to the element storage (right after header in memory)
263    items: *mut MaybeUninit<T>,
264}
265
266impl<T> Segment<T> {
267    // cap, data_offset, mem layout
268    const LAYOUT_INFO: (usize, usize, Layout) = {
269        let mut data_offset = size_of::<SegHeader<T>>();
270        let t_size = size_of::<T>();
271        let t_align = align_of::<MaybeUninit<T>>();
272        let (capacity, final_alloc_size, final_align);
273        if t_size == 0 {
274            // 0-size does not actually take place, but storing them does not make sense
275            (final_alloc_size, final_align) = (CACHE_LINE_SIZE, CACHE_LINE_SIZE);
276            capacity = 1024;
277        } else {
278            // Calculate first element's offset (considering T's alignment)
279            data_offset = (data_offset + t_align - 1) & !(t_align - 1);
280            let min_elements = 2;
281            let min_required_size = data_offset + (t_size * min_elements);
282            let alloc_size = (min_required_size + CACHE_LINE_SIZE - 1) & !(CACHE_LINE_SIZE - 1);
283            final_align = if CACHE_LINE_SIZE > t_align { CACHE_LINE_SIZE } else { t_align };
284            final_alloc_size = (alloc_size + final_align - 1) & !(final_align - 1);
285            capacity = (final_alloc_size - data_offset) / t_size;
286            // rust 1.57 support assert in const fn
287            assert!(capacity >= min_elements);
288        }
289        match Layout::from_size_align(final_alloc_size, final_align) {
290            Ok(l) => (capacity, data_offset, l),
291            Err(_) => panic!("Invalid layout"),
292        }
293    };
294
295    const fn get_layout() -> Layout {
296        Self::LAYOUT_INFO.2
297    }
298
299    /// Create a new empty segment with calculated capacity
300    unsafe fn alloc(prev: *mut SegHeader<T>, next: *mut SegHeader<T>) -> Self {
301        let layout = Self::get_layout();
302        let ptr: *mut u8 = unsafe { alloc(layout) };
303        if ptr.is_null() {
304            handle_alloc_error(layout);
305        }
306        unsafe {
307            let p = NonNull::new_unchecked(ptr as *mut SegHeader<T>);
308            let header = p.as_ptr();
309            // Initialize header
310            (*header).count = 0;
311            (*header).prev = prev;
312            (*header).next = next;
313            Self::from_raw(p)
314        }
315    }
316
317    unsafe fn dealloc(&mut self) {
318        if core::mem::needs_drop::<T>() {
319            for i in 0..self.len() {
320                unsafe {
321                    (*self.item_ptr(i)).assume_init_drop();
322                }
323            }
324        }
325        // Deallocate the entire segment (header + items)
326        unsafe {
327            dealloc(self.header.as_ptr() as *mut u8, Self::LAYOUT_INFO.2);
328        }
329    }
330
331    #[inline(always)]
332    unsafe fn from_raw(header: NonNull<SegHeader<T>>) -> Self {
333        let p = header.as_ptr() as *mut u8;
334        let items = unsafe { p.add(Self::LAYOUT_INFO.1) as *mut MaybeUninit<T> };
335        Self { header, items }
336    }
337
338    /// Get the count of valid elements in this segment
339    #[inline(always)]
340    fn len(&self) -> usize {
341        unsafe { (*self.header.as_ptr()).count }
342    }
343
344    #[inline(always)]
345    fn get_header(&self) -> &SegHeader<T> {
346        unsafe { self.header.as_ref() }
347    }
348
349    #[inline(always)]
350    fn get_header_mut(&mut self) -> &mut SegHeader<T> {
351        unsafe { self.header.as_mut() }
352    }
353
354    /// Check if segment has no valid elements
355    #[inline(always)]
356    fn is_empty(&self) -> bool {
357        self.len() == 0
358    }
359
360    /// Check if segment is full
361    #[inline(always)]
362    fn is_full(&self) -> bool {
363        self.len() >= Self::LAYOUT_INFO.0
364    }
365
366    /// Get pointer to item at index
367    #[inline]
368    fn item_ptr(&self, index: usize) -> *mut MaybeUninit<T> {
369        unsafe { self.items.add(index) }
370    }
371
372    /// Push an element to this segment (if not full)
373    #[inline]
374    fn push(&mut self, item: T) {
375        debug_assert!(!self.is_full());
376        let idx = self.get_header().count;
377        unsafe {
378            (*self.item_ptr(idx)).write(item);
379        }
380        self.get_header_mut().count = idx + 1;
381    }
382
383    /// return (item, is_empty_now)
384    #[inline]
385    fn pop(&mut self) -> (T, bool) {
386        debug_assert!(!self.is_empty());
387        let idx = self.get_header().count - 1;
388        let item = unsafe { self.item_ptr(idx).read().assume_init() };
389        self.get_header_mut().count = idx;
390        (item, idx == 0)
391    }
392}
393
394/// Immutable iterator over SegList
395pub struct SegListIter<'a, T> {
396    cur: Option<Segment<T>>,
397    cur_idx: usize,
398    remaining: usize,
399    _marker: core::marker::PhantomData<&'a T>,
400}
401
402impl<'a, T> Iterator for SegListIter<'a, T> {
403    type Item = &'a T;
404
405    fn next(&mut self) -> Option<Self::Item> {
406        if self.remaining == 0 {
407            return None;
408        }
409        let cur = self.cur.as_ref()?;
410        let cur_header = cur.get_header();
411        unsafe {
412            if self.cur_idx >= cur_header.count {
413                let next = cur_header.next;
414                // In circular list, next is never null, but we use remaining to limit iteration
415                self.cur = Some(Segment::from_raw(NonNull::new_unchecked(next)));
416                self.cur_idx = 0;
417                return self.next();
418            }
419            let item = (*cur.item_ptr(self.cur_idx)).assume_init_ref();
420            self.cur_idx += 1;
421            self.remaining -= 1;
422            Some(item)
423        }
424    }
425}
426
427/// Mutable iterator over SegList
428pub struct SegListIterMut<'a, T> {
429    cur: Option<Segment<T>>,
430    cur_idx: usize,
431    remaining: usize,
432    _marker: core::marker::PhantomData<&'a mut T>,
433}
434
435impl<'a, T> Iterator for SegListIterMut<'a, T> {
436    type Item = &'a mut T;
437
438    fn next(&mut self) -> Option<Self::Item> {
439        if self.remaining == 0 {
440            return None;
441        }
442        let cur = self.cur.as_mut()?;
443        let cur_header = cur.get_header();
444        unsafe {
445            if self.cur_idx >= cur_header.count {
446                let next = cur_header.next;
447                // In circular list, next is never null, but we use remaining to limit iteration
448                self.cur = Some(Segment::from_raw(NonNull::new_unchecked(next)));
449                self.cur_idx = 0;
450                return self.next();
451            }
452            let item = (*cur.item_ptr(self.cur_idx)).assume_init_mut();
453            self.cur_idx += 1;
454            self.remaining -= 1;
455            Some(item)
456        }
457    }
458}
459
460/// Draining iterator over SegList
461/// Consumes elements from head to tail (FIFO order)
462pub struct SegListDrain<T> {
463    cur: Option<Segment<T>>,
464    cur_idx: usize,
465}
466
467impl<T> Iterator for SegListDrain<T> {
468    type Item = T;
469
470    fn next(&mut self) -> Option<Self::Item> {
471        let cur = self.cur.as_mut()?;
472        unsafe {
473            let cur_header = cur.get_header();
474            // Skip empty segments
475            if self.cur_idx >= cur_header.count {
476                // Save next pointer before dealloc
477                let next = cur_header.next;
478                // Don't call Segment::dealloc because we have already yield item outside
479                dealloc(cur.header.as_ptr() as *mut u8, Segment::<T>::LAYOUT_INFO.2);
480                if next.is_null() {
481                    self.cur = None;
482                    return None;
483                } else {
484                    self.cur = Some(Segment::from_raw(NonNull::new_unchecked(next)));
485                    self.cur_idx = 0;
486                    return self.next();
487                }
488            }
489            let item = cur.item_ptr(self.cur_idx).read().assume_init();
490            self.cur_idx += 1;
491            if self.cur_idx >= cur_header.count {
492                // Save next pointer before dealloc
493                let next = cur_header.next;
494                // Don't call Segment::dealloc because we have already yield item outside
495                dealloc(cur.header.as_ptr() as *mut u8, Segment::<T>::LAYOUT_INFO.2);
496                if next.is_null() {
497                    self.cur = None;
498                } else {
499                    self.cur = Some(Segment::from_raw(NonNull::new_unchecked(next)));
500                    self.cur_idx = 0;
501                }
502            }
503            Some(item)
504        }
505    }
506}
507
508impl<T> Drop for SegListDrain<T> {
509    fn drop(&mut self) {
510        let mut next: *mut SegHeader<T>;
511        if let Some(mut cur) = self.cur.take() {
512            unsafe {
513                // Save next pointer before dealloc
514                let header = cur.get_header();
515                next = header.next;
516                // Drop remaining elements in this segment (from current index to end)
517                if core::mem::needs_drop::<T>() {
518                    for i in self.cur_idx..header.count {
519                        (*cur.item_ptr(i)).assume_init_drop();
520                    }
521                }
522                dealloc(cur.header.as_ptr() as *mut u8, Segment::<T>::LAYOUT_INFO.2);
523                while !next.is_null() {
524                    cur = Segment::from_raw(NonNull::new_unchecked(next));
525                    let header = cur.get_header();
526                    next = header.next;
527                    cur.dealloc();
528                }
529            }
530        }
531    }
532}
533
534#[cfg(test)]
535mod tests {
536    use super::*;
537    use core::sync::atomic::{AtomicUsize, Ordering};
538
539    static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
540
541    #[derive(Debug)]
542    struct DropTracker(i32);
543
544    impl Drop for DropTracker {
545        fn drop(&mut self) {
546            DROP_COUNT.fetch_add(1, Ordering::SeqCst);
547        }
548    }
549
550    fn reset_drop_count() {
551        DROP_COUNT.store(0, Ordering::SeqCst);
552    }
553
554    fn get_drop_count() -> usize {
555        DROP_COUNT.load(Ordering::SeqCst)
556    }
557
558    #[test]
559    fn test_multiple_segments() {
560        let mut list: SegList<i32> = SegList::new();
561        if CACHE_LINE_SIZE == 128 {
562            assert_eq!(Segment::<i32>::LAYOUT_INFO.0, 26);
563        }
564
565        for i in 0..100 {
566            list.push(i);
567        }
568
569        assert_eq!(list.len(), 100);
570
571        for i in (0..100).rev() {
572            assert_eq!(list.pop(), Some(i));
573        }
574
575        assert_eq!(list.pop(), None);
576    }
577
578    #[test]
579    fn test_iter_single_segment() {
580        // Test with small number of elements (single segment)
581        let mut list: SegList<i32> = SegList::new();
582
583        for i in 0..10 {
584            list.push(i);
585        }
586        assert_eq!(list.first(), Some(&0));
587        assert_eq!(list.last(), Some(&9));
588
589        // Test immutable iterator
590        let collected: Vec<i32> = list.iter().copied().collect();
591        assert_eq!(collected, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
592
593        // Test mutable iterator - modify elements
594        for item in list.iter_mut() {
595            *item *= 2;
596        }
597        assert_eq!(list.first(), Some(&0));
598        assert_eq!(list.last(), Some(&18));
599
600        // Verify modification
601        let collected: Vec<i32> = list.iter().copied().collect();
602        assert_eq!(collected, vec![0, 2, 4, 6, 8, 10, 12, 14, 16, 18]);
603
604        // Test pop() - should return elements in LIFO order
605        for i in (0..10).rev() {
606            assert_eq!(list.pop(), Some(i * 2));
607        }
608        assert_eq!(list.pop(), None);
609        assert!(list.is_empty());
610    }
611
612    #[test]
613    fn test_iter_multi_segment() {
614        // Test with many elements (multiple segments)
615        let mut list: SegList<i32> = SegList::new();
616
617        for i in 0..200 {
618            list.push(i * 10);
619        }
620        assert_eq!(list.first(), Some(&0));
621        assert_eq!(list.last(), Some(&1990));
622
623        // Test immutable iterator across multiple segments
624        let collected: Vec<i32> = list.iter().copied().collect();
625        let expected: Vec<i32> = (0..200).map(|i| i * 10).collect();
626        assert_eq!(collected, expected);
627
628        // Test mutable iterator - modify elements
629        for item in list.iter_mut() {
630            *item += 1;
631        }
632        assert_eq!(list.first(), Some(&1));
633        assert_eq!(list.last(), Some(&1991));
634
635        // Verify modification
636        let collected: Vec<i32> = list.iter().copied().collect();
637        let expected: Vec<i32> = (0..200).map(|i| i * 10 + 1).collect();
638        assert_eq!(collected, expected);
639
640        // Test pop() - should return elements in LIFO order across multiple segments
641        for i in (0..200).rev() {
642            assert_eq!(list.pop(), Some(i * 10 + 1));
643        }
644        assert_eq!(list.pop(), None);
645        assert!(list.is_empty());
646    }
647
648    #[test]
649    fn test_drain() {
650        // Get capacity per segment for DropTracker (i32)
651        let cap = Segment::<DropTracker>::LAYOUT_INFO.0;
652
653        // Scenario 1: Single segment, drain completely
654        {
655            reset_drop_count();
656            {
657                let mut list: SegList<DropTracker> = SegList::new();
658                // Push fewer elements than one segment capacity
659                for i in 0..5 {
660                    list.push(DropTracker(i));
661                }
662                assert!(list.len() < cap);
663
664                // Drain all elements
665                let drained: Vec<i32> = list.drain().map(|d| d.0).collect();
666                assert_eq!(drained, vec![0, 1, 2, 3, 4]);
667            }
668            // All 5 elements should be dropped by drain
669            assert_eq!(get_drop_count(), 5);
670        }
671
672        // Scenario 2: Three segments, drain first segment partially, then drop remaining
673        {
674            reset_drop_count();
675            {
676                let mut list: SegList<DropTracker> = SegList::new();
677                // Push elements to create 3 segments (cap * 2 + 5 = more than 2 segments)
678                let total = cap * 2 + 5;
679                for i in 0..total {
680                    list.push(DropTracker(i as i32));
681                }
682
683                // Drain only half of first segment
684                let drain_count = cap / 2;
685                let mut drain_iter = list.drain();
686                for i in 0..drain_count {
687                    assert_eq!(drain_iter.next().unwrap().0, i as i32);
688                }
689                // Drop the drain iterator early (remaining elements should be dropped)
690                drop(drain_iter);
691            }
692            // All elements should be dropped (drained + remaining in list)
693            assert_eq!(get_drop_count(), cap * 2 + 5);
694        }
695
696        // Scenario 3: Three segments, drain exactly first segment, then drop remaining
697        {
698            reset_drop_count();
699            {
700                let mut list: SegList<DropTracker> = SegList::new();
701                // Push elements to create 3 segments
702                let total = cap * 2 + 3;
703                for i in 0..total {
704                    list.push(DropTracker(i as i32));
705                }
706
707                // Drain exactly first segment
708                let mut drain_iter = list.drain();
709                for i in 0..cap {
710                    assert_eq!(drain_iter.next().unwrap().0, i as i32);
711                }
712                // Drop the drain iterator early
713                drop(drain_iter);
714            }
715            // All elements should be dropped
716            assert_eq!(get_drop_count(), cap * 2 + 3);
717        }
718    }
719
720    #[test]
721    fn test_drop_single_segment() {
722        reset_drop_count();
723        {
724            let mut list: SegList<DropTracker> = SegList::new();
725            let cap = Segment::<DropTracker>::LAYOUT_INFO.0;
726
727            // Push fewer elements than one segment capacity
728            for i in 0..5 {
729                list.push(DropTracker(i));
730            }
731            assert!(list.len() < cap);
732
733            // list drops here, should drop all elements
734        }
735
736        assert_eq!(get_drop_count(), 5);
737    }
738
739    #[test]
740    fn test_drop_multi_segment() {
741        let cap = Segment::<DropTracker>::LAYOUT_INFO.0;
742        reset_drop_count();
743        {
744            let mut list: SegList<DropTracker> = SegList::new();
745
746            // Push elements to create multiple segments (3 segments)
747            let total = cap * 2 + 10;
748            for i in 0..total {
749                list.push(DropTracker(i as i32));
750            }
751            // list drops here, should drop all elements across all segments
752        }
753        assert_eq!(get_drop_count(), cap * 2 + 10);
754    }
755
756    #[test]
757    fn test_clear() {
758        let mut list: SegList<i32> = SegList::new();
759
760        for i in 0..50 {
761            list.push(i);
762        }
763
764        list.clear();
765
766        assert!(list.is_empty());
767        assert_eq!(list.len(), 0);
768        assert_eq!(list.pop(), None);
769    }
770
771    /// Large struct that larger than cache line
772    #[derive(Debug, Clone, Copy, PartialEq)]
773    struct LargeStruct {
774        data: [u64; 16], // 128 bytes
775    }
776
777    impl LargeStruct {
778        fn new(val: u64) -> Self {
779            Self { data: [val; 16] }
780        }
781    }
782
783    #[test]
784    fn test_size() {
785        let layout = Segment::<LargeStruct>::LAYOUT_INFO;
786        println!(
787            "LargeStruct: cap {} offset {}, size {}, align {}",
788            layout.0,
789            layout.1,
790            layout.2.size(),
791            layout.2.align()
792        );
793        let layout = Segment::<u64>::LAYOUT_INFO;
794        println!(
795            "u64: cap {} offset {}, size {}, align {}",
796            layout.0,
797            layout.1,
798            layout.2.size(),
799            layout.2.align()
800        );
801        let layout = Segment::<u32>::LAYOUT_INFO;
802        println!(
803            "u32: cap {} offset {}, size {}, align {}",
804            layout.0,
805            layout.1,
806            layout.2.size(),
807            layout.2.align()
808        );
809        let layout = Segment::<u16>::LAYOUT_INFO;
810        println!(
811            "u16: cap {} offset {}, size {}, align {}",
812            layout.0,
813            layout.1,
814            layout.2.size(),
815            layout.2.align()
816        );
817    }
818
819    #[test]
820    fn test_large_type_push_pop() {
821        let mut list: SegList<LargeStruct> = SegList::new();
822        // Push elements - each segment can only hold a few due to large element size
823        for i in 0..50 {
824            list.push(LargeStruct::new(i));
825        }
826        assert_eq!(list.len(), 50);
827
828        // Pop all elements - should work correctly across multiple segments
829        for i in (0..50).rev() {
830            let val = list.pop().unwrap();
831            assert_eq!(val.data[0], i);
832            assert_eq!(val.data[7], i);
833        }
834        assert!(list.is_empty());
835        assert_eq!(list.pop(), None);
836    }
837
838    #[test]
839    fn test_large_type_iter() {
840        let mut list: SegList<LargeStruct> = SegList::new();
841
842        // Push elements
843        for i in 0..30 {
844            list.push(LargeStruct::new(i * 10));
845        }
846
847        // Test iterator
848        let collected: Vec<u64> = list.iter().map(|s| s.data[0]).collect();
849        let expected: Vec<u64> = (0..30).map(|i| i * 10).collect();
850        assert_eq!(collected, expected);
851    }
852
853    #[test]
854    fn test_large_type_iter_mut() {
855        let mut list: SegList<LargeStruct> = SegList::new();
856
857        // Push elements
858        for i in 0..20 {
859            list.push(LargeStruct::new(i));
860        }
861
862        // Modify through iterator
863        for item in list.iter_mut() {
864            item.data[0] *= 2;
865        }
866
867        // Verify modification
868        let collected: Vec<u64> = list.iter().map(|s| s.data[0]).collect();
869        let expected: Vec<u64> = (0..20).map(|i| i * 2).collect();
870        assert_eq!(collected, expected);
871    }
872
873    #[test]
874    fn test_large_type_drain() {
875        let mut list: SegList<LargeStruct> = SegList::new();
876
877        // Push elements
878        for i in 0..40 {
879            list.push(LargeStruct::new(i));
880        }
881
882        // Drain and verify FIFO order
883        let drained: Vec<u64> = list.drain().map(|s| s.data[0]).collect();
884        let expected: Vec<u64> = (0..40).collect();
885        assert_eq!(drained, expected);
886    }
887
888    #[test]
889    fn test_large_type_clear() {
890        let mut list: SegList<LargeStruct> = SegList::new();
891
892        // Push elements
893        for i in 0..60 {
894            list.push(LargeStruct::new(i));
895        }
896        assert_eq!(list.len(), 60);
897
898        // Clear
899        list.clear();
900        assert!(list.is_empty());
901        assert_eq!(list.len(), 0);
902        assert_eq!(list.pop(), None);
903    }
904}
embed_collections/seg_list.rs

embed_collections/
seg_list.rs
