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

embed_collections/
seg_list.rs
