segment_array/

lib.rs

//
// Copyright (c) 2025 Nathan Fiedler
//

//! An implmentation of the segment array as described in the [blog
//! post](https://danielchasehooper.com/posts/segment_array/) by Daniel Hooper.
//!
//! From the blog post:
//!
//! > A data structure with constant time indexing, stable pointers, and works
//! > well with arena allocators. ... The idea is straight forward: the
//! > structure contains a fixed sized array of pointers to segments. Each
//! > segment is twice the size of its predecessor. New segments are allocated
//! > as needed. ... Unlike standard arrays, pointers to a segment array’s items
//! > are always valid because items are never moved. Leaving items in place
//! > also means it never leaves "holes" of abandoned memory in arena
//! > allocators. The layout also allows us to access any index in constant
//! > time.
//!
//! The behavior, memory layout, and performance of this implementation should
//! be very similar to that of the C implementation. To summarize:
//!
//! * Fixed number of segments (26)
//! * First segment has a capacity of 64
//! * Each segment is double the size of its predecessor
//! * Total capacity of 4,294,967,232 items
//!
//! # Memory Usage
//!
//! An empty segment array is approximately 224 bytes in size and it will have a
//! space overhead on the order of O(N) due to its geometric growth function
//! (like `std::vec::Vec`). As elements are added the array will grow by
//! allocating additional segments. Likewise, as elements are removed from the
//! end of the array, segments will be deallocated as they become empty.
//!
//! # Safety
//!
//! Because this data structure is allocating memory, copying bytes using
//! pointers, and de-allocating memory as needed, there are many `unsafe` blocks
//! throughout the code.

use std::alloc::{Layout, alloc, dealloc, handle_alloc_error};
use std::fmt;
use std::iter::{FromIterator, Iterator};
use std::ops::{Index, IndexMut};

//
// An individual segment can never be larger than 9,223,372,036,854,775,807
// bytes due to the mechanics of the Rust memory allocator.
//
// 26 segments with 6 skipped segments with each segment doubling in size
// results in the last segment having 2,147,483,648 items
//
// 9,223,372,036,854,775,807 bytes divided by 2,147,483,648 items yields a
// maximum item size of 4,294,967,296 bytes
//
const MAX_SEGMENT_COUNT: usize = 26;

// Segments of size 1, 2, 4, 8, 16, and 32 are not used at all (that is, the
// smallest (first) segment is 64 elements in size) to avoid the overhead of
// such tiny arrays.
const SMALL_SEGMENTS_TO_SKIP: usize = 6;
const SMALL_SEGMENTS_CAPACITY: usize = 1 << SMALL_SEGMENTS_TO_SKIP;

// Calculates the number of elements that will fit into the given segment.
#[inline]
fn slots_in_segment(segment: usize) -> usize {
    SMALL_SEGMENTS_CAPACITY << segment
}

// Calculates the overall capacity for all segments up to the given segment.
#[inline]
fn capacity_for_segment_count(segment: usize) -> usize {
    (SMALL_SEGMENTS_CAPACITY << segment) - SMALL_SEGMENTS_CAPACITY
}

///
/// Append-only growable array that uses a list of progressivly larger segments
/// to avoid the allocate-and-copy that many growable data structures typically
/// employ.
///
pub struct SegmentArray<T> {
    // number of elements stored in the array
    count: usize,
    // number of allocated segments
    used_segments: usize,
    // pointers to allocated segments (0 to used_segments-1)
    segments: [*mut T; MAX_SEGMENT_COUNT],
}

impl<T> SegmentArray<T> {
    /// Return an empty segment array with zero capacity.
    ///
    /// Note that pre-allocating capacity has no benefit with this data
    /// structure since append operations are always constant time and
    /// no reallocation and copy is ever performed.
    pub fn new() -> Self {
        Self {
            count: 0,
            used_segments: 0,
            segments: [std::ptr::null_mut::<T>(); MAX_SEGMENT_COUNT],
        }
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Panics
    ///
    /// Panics if a new segment is allocated that would exceed `isize::MAX` _bytes_.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn push(&mut self, value: T) {
        if self.count >= capacity_for_segment_count(self.used_segments) {
            assert!(
                self.used_segments < MAX_SEGMENT_COUNT,
                "maximum number of segments exceeded"
            );
            let segment_len = slots_in_segment(self.used_segments);
            // overflowing the allocator is very unlikely as the item size would
            // have to be very large
            let layout = Layout::array::<T>(segment_len).expect("unexpected overflow");
            unsafe {
                let ptr = alloc(layout).cast::<T>();
                if ptr.is_null() {
                    handle_alloc_error(layout);
                }
                self.segments[self.used_segments] = ptr;
            }
            self.used_segments += 1;
        }

        let segment = ((self.count >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
        let slot = self.count - capacity_for_segment_count(segment);
        unsafe {
            std::ptr::write(self.segments[segment].add(slot), value);
        }
        self.count += 1;
    }

    /// Deallocate segments as they become empty.
    fn shrink(&mut self) {
        if self.used_segments > 0
            && self.count <= capacity_for_segment_count(self.used_segments - 1)
        {
            let segment = self.used_segments - 1;
            let segment_len = slots_in_segment(segment);
            let layout = Layout::array::<T>(segment_len).expect("unexpected overflow");
            unsafe {
                dealloc(self.segments[segment] as *mut u8, layout);
            }
            self.segments[segment] = std::ptr::null_mut();
            self.used_segments -= 1;
        }
    }

    /// Appends an element if there is sufficient spare capacity, otherwise an
    /// error is returned with the element.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> {
        if self.count >= capacity_for_segment_count(self.used_segments) {
            Err(value)
        } else {
            self.push(value);
            Ok(())
        }
    }

    /// Removes the last element from a vector and returns it, or `None` if it
    /// is empty.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn pop(&mut self) -> Option<T> {
        if self.count > 0 {
            self.count -= 1;
            let segment = ((self.count >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let slot = self.count - capacity_for_segment_count(segment);
            let value = unsafe { Some((self.segments[segment].add(slot)).read()) };
            self.shrink();
            value
        } else {
            None
        }
    }

    /// Removes and returns the last element from a vector if the predicate
    /// returns true, or None if the predicate returns false or the vector is
    /// empty (the predicate will not be called in that case).
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
        if self.count == 0 {
            None
        } else if let Some(last) = self.get_mut(self.count - 1) {
            if predicate(last) { self.pop() } else { None }
        } else {
            None
        }
    }

    /// Return the number of elements in the array.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn len(&self) -> usize {
        self.count
    }

    /// Returns the total number of elements the segment array can hold
    /// without reallocating.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn capacity(&self) -> usize {
        capacity_for_segment_count(self.used_segments)
    }

    /// Returns true if the array has a length of 0.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }

    /// Retrieve a reference to the element at the given offset.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn get(&self, index: usize) -> Option<&T> {
        if index >= self.count {
            None
        } else {
            let segment = ((index >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let slot = index - capacity_for_segment_count(segment);
            unsafe { (self.segments[segment].add(slot)).as_ref() }
        }
    }

    /// Returns a mutable reference to an element.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index >= self.count {
            None
        } else {
            let segment = ((index >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let slot = index - capacity_for_segment_count(segment);
            unsafe { (self.segments[segment].add(slot)).as_mut() }
        }
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// This does not preserve ordering of the remaining elements.
    ///
    /// # Time complexity
    ///
    /// Constant time.
    pub fn swap_remove(&mut self, index: usize) -> T {
        if index >= self.count {
            panic!(
                "swap_remove index (is {index}) should be < len (is {})",
                self.count
            );
        }
        // retreive the value at index before overwriting
        let segment = ((index >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
        let slot = index - capacity_for_segment_count(segment);
        unsafe {
            let index_ptr = self.segments[segment].add(slot);
            let value = index_ptr.read();
            // find the pointer of the last element and copy to index pointer
            self.count -= 1;
            let segment = ((self.count >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let slot = self.count - capacity_for_segment_count(segment);
            let last_ptr = self.segments[segment].add(slot);
            std::ptr::copy(last_ptr, index_ptr, 1);
            self.shrink();
            value
        }
    }

    /// Returns an iterator over the segment array.
    ///
    /// The iterator yields all items from start to end.
    pub fn iter(&self) -> SegArrayIter<'_, T> {
        SegArrayIter {
            array: self,
            index: 0,
        }
    }

    /// Clears the segment array, removing and dropping all values.
    ///
    /// Note that this method has no effect on the allocated capacity of the
    /// segment array.
    pub fn clear(&mut self) {
        if self.count > 0 && std::mem::needs_drop::<T>() {
            // find the last segment that contains values
            let last_segment = ((self.count >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let last_slot = self.count - capacity_for_segment_count(last_segment);
            unsafe {
                std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(
                    self.segments[last_segment],
                    last_slot,
                ));
            }
            // now drop the values in all of the preceding segments
            for segment in 0..last_segment {
                let segment_len = slots_in_segment(segment);
                unsafe {
                    std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(
                        self.segments[segment],
                        segment_len,
                    ));
                }
            }
        }
        self.count = 0;

        // deallocate the segments themselves and clear everything
        for segment in 0..self.used_segments {
            if !self.segments[segment].is_null() {
                let segment_len = slots_in_segment(segment);
                let layout = Layout::array::<T>(segment_len).expect("unexpected overflow");
                unsafe {
                    dealloc(self.segments[segment] as *mut u8, layout);
                }
                self.segments[segment] = std::ptr::null_mut();
            }
        }
        self.used_segments = 0;
    }
}

impl<T> Default for SegmentArray<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> fmt::Display for SegmentArray<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let longest_segment = if self.used_segments > 0 {
            slots_in_segment(self.used_segments - 1)
        } else {
            0
        };
        write!(
            f,
            "SegmentArray(count: {}, used_segments: {}, longest segment: {})",
            self.count, self.used_segments, longest_segment
        )
    }
}

impl<T> Drop for SegmentArray<T> {
    fn drop(&mut self) {
        self.clear();
    }
}

impl<T> Index<usize> for SegmentArray<T> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        let Some(item) = self.get(index) else {
            panic!("index out of bounds: {}", index);
        };
        item
    }
}

impl<T> IndexMut<usize> for SegmentArray<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        let Some(item) = self.get_mut(index) else {
            panic!("index out of bounds: {}", index);
        };
        item
    }
}

impl<A> FromIterator<A> for SegmentArray<A> {
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
        let mut arr: SegmentArray<A> = SegmentArray::new();
        for value in iter {
            arr.push(value)
        }
        arr
    }
}

/// Immutable segment array iterator.
pub struct SegArrayIter<'a, T> {
    array: &'a SegmentArray<T>,
    index: usize,
}

impl<'a, T> Iterator for SegArrayIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        let value = self.array.get(self.index);
        self.index += 1;
        value
    }
}

/// An iterator that moves out of a segment array.
pub struct SegArrayIntoIter<T> {
    index: usize,
    count: usize,
    used_segments: usize,
    segments: [*mut T; MAX_SEGMENT_COUNT],
}

impl<T> Iterator for SegArrayIntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.count {
            let segment = ((self.index >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let slot = self.index - capacity_for_segment_count(segment);
            self.index += 1;
            unsafe { Some((self.segments[segment].add(slot)).read()) }
        } else {
            None
        }
    }
}

impl<T> Drop for SegArrayIntoIter<T> {
    fn drop(&mut self) {
        if std::mem::needs_drop::<T>() {
            let first_segment = ((self.index >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            let last_segment = (((self.count - 1) >> SMALL_SEGMENTS_TO_SKIP) + 1).ilog2() as usize;
            if first_segment == last_segment {
                // special-case, remaining values are in only one segment
                let first = self.index - capacity_for_segment_count(first_segment);
                let last = self.count - capacity_for_segment_count(first_segment);
                if first < last {
                    let len = last - first;
                    unsafe {
                        let first: *mut T = self.segments[first_segment].add(first);
                        std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(first, len));
                    }
                }
            } else {
                // drop values in the first segment that still has values to be
                // visited
                let first = self.index - capacity_for_segment_count(first_segment);
                let segment_len = slots_in_segment(first_segment);
                if segment_len < self.count {
                    unsafe {
                        let ptr: *mut T = self.segments[first_segment].add(first);
                        let len = segment_len - first;
                        std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(ptr, len));
                    }
                }

                // drop the values in the last segment
                let last_slot = self.count - capacity_for_segment_count(last_segment);
                unsafe {
                    std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(
                        self.segments[last_segment],
                        last_slot,
                    ));
                }

                // now drop the values in all of the other segments
                for segment in first_segment + 1..last_segment {
                    let segment_len = slots_in_segment(segment);
                    unsafe {
                        std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(
                            self.segments[segment],
                            segment_len,
                        ));
                    }
                }
            }
        }

        // deallocate the segments themselves and clear everything
        for segment in 0..self.used_segments {
            if !self.segments[segment].is_null() {
                let segment_len = slots_in_segment(segment);
                let layout = Layout::array::<T>(segment_len).expect("unexpected overflow");
                unsafe {
                    dealloc(self.segments[segment] as *mut u8, layout);
                }
                self.segments[segment] = std::ptr::null_mut();
            }
        }
        self.index = 0;
        self.count = 0;
        self.used_segments = 0;
    }
}

impl<T> IntoIterator for SegmentArray<T> {
    type Item = T;
    type IntoIter = SegArrayIntoIter<Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        let me = std::mem::ManuallyDrop::new(self);
        SegArrayIntoIter {
            index: 0,
            count: me.count,
            used_segments: me.used_segments,
            segments: me.segments,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_slots_in_segment() {
        // values are simply capacity_for_segment_count() plus 64 but there
        // should be a test for this function regardless of its simplicity
        let expected_values = [
            64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,
            1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456,
            536870912, 1073741824, 2147483648,
        ];
        assert_eq!(expected_values.len(), MAX_SEGMENT_COUNT);
        for (segment, item) in expected_values.iter().enumerate() {
            assert_eq!(*item, slots_in_segment(segment));
        }
    }

    #[test]
    fn test_capacity_for_segment_count() {
        //
        // from https://danielchasehooper.com/posts/segment_array/segment_array.h:
        //
        // 26 segments with 6 skipped segments can hold 4,294,967,232 items, aka
        // capacity_for_segment_count(26)
        //
        let expected_values = [
            0, 64, 192, 448, 960, 1984, 4032, 8128, 16320, 32704, 65472, 131008, 262080, 524224,
            1048512, 2097088, 4194240, 8388544, 16777152, 33554368, 67108800, 134217664, 268435392,
            536870848, 1073741760, 2147483584, 4294967232,
        ];
        assert_eq!(expected_values.len(), MAX_SEGMENT_COUNT + 1);
        for (count, item) in expected_values.iter().enumerate() {
            assert_eq!(*item, capacity_for_segment_count(count));
        }
    }

    #[test]
    fn test_push_within_capacity() {
        // empty array has no allocated space
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        assert_eq!(sut.push_within_capacity(101), Err(101));
        sut.push(10);
        assert_eq!(sut.push_within_capacity(101), Ok(()));

        // edge case (first segment is 64 elements long)
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        for value in 1..64 {
            sut.push(value);
        }
        assert_eq!(sut.push_within_capacity(64), Ok(()));
        assert_eq!(sut.push_within_capacity(65), Err(65));
    }

    #[test]
    fn test_push_get_one_item() {
        let item = String::from("hello world");
        let mut sut: SegmentArray<String> = SegmentArray::new();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
        sut.push(item);
        assert_eq!(sut.len(), 1);
        assert!(!sut.is_empty());
        let maybe = sut.get(0);
        assert!(maybe.is_some());
        let actual = maybe.unwrap();
        assert_eq!("hello world", actual);
        let missing = sut.get(10);
        assert!(missing.is_none());
    }

    #[test]
    fn test_push_get_several_strings() {
        let inputs = [
            "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for item in inputs {
            sut.push(item.to_owned());
        }
        assert_eq!(sut.len(), 9);
        for (idx, item) in inputs.iter().enumerate() {
            let maybe = sut.get(idx);
            assert!(maybe.is_some(), "{idx} is none");
            let actual = maybe.unwrap();
            assert_eq!(item, actual);
        }
        let maybe = sut.get(10);
        assert!(maybe.is_none());
        assert_eq!(sut[3], "four");
    }

    #[test]
    fn test_get_mut_index_mut() {
        let mut sut: SegmentArray<String> = SegmentArray::new();
        sut.push(String::from("first"));
        sut.push(String::from("second"));
        sut.push(String::from("third"));
        if let Some(value) = sut.get_mut(1) {
            value.push_str(" place");
        } else {
            panic!("get_mut() returned None")
        }
        assert_eq!(sut[1], "second place");
        sut[2] = "third planet".into();
        assert_eq!(sut[2], "third planet");
    }

    #[test]
    #[should_panic(expected = "index out of bounds:")]
    fn test_index_out_of_bounds() {
        let mut sut: SegmentArray<i32> = SegmentArray::new();
        sut.push(10);
        sut.push(20);
        let _ = sut[2];
    }

    #[test]
    #[should_panic(expected = "index out of bounds:")]
    fn test_index_mut_out_of_bounds() {
        let mut sut: SegmentArray<i32> = SegmentArray::new();
        sut.push(10);
        sut.push(20);
        sut[2] = 30;
    }

    #[test]
    fn test_push_and_pop() {
        let inputs = [
            "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        let mut sut: SegmentArray<String> = SegmentArray::new();
        assert_eq!(sut.capacity(), 0);
        assert!(sut.pop().is_none());
        for item in inputs {
            sut.push(item.to_owned());
        }
        assert_eq!(sut.len(), 9);
        for (idx, elem) in sut.iter().enumerate() {
            assert_eq!(inputs[idx], elem);
        }
        let maybe = sut.pop();
        assert!(maybe.is_some());
        let value = maybe.unwrap();
        assert_eq!(value, "nine");
        assert_eq!(sut.len(), 8);
        sut.push(String::from("nine"));
        assert_eq!(sut.len(), 9);
        for (idx, elem) in sut.iter().enumerate() {
            assert_eq!(inputs[idx], elem);
        }

        // pop everything and add back again
        while !sut.is_empty() {
            sut.pop();
        }
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 0);
        for item in inputs {
            sut.push(item.to_owned());
        }
        assert_eq!(sut.len(), 9);
        for (idx, elem) in sut.iter().enumerate() {
            assert_eq!(inputs[idx], elem);
        }
    }

    #[test]
    fn test_push_many_pop_all_verify() {
        // push many values, then pop all off and verify
        let mut sut: SegmentArray<usize> = SegmentArray::new();
        for value in 0..16384 {
            sut.push(value);
        }
        for value in (0..16384).rev() {
            assert_eq!(sut.pop(), Some(value));
        }
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 0);
    }

    #[test]
    fn test_pop_if() {
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        assert!(sut.pop_if(|_| panic!("should not be called")).is_none());
        for value in 0..10 {
            sut.push(value);
        }
        assert!(sut.pop_if(|_| false).is_none());
        let maybe = sut.pop_if(|v| *v == 9);
        assert_eq!(maybe.unwrap(), 9);
        assert!(sut.pop_if(|v| *v == 9).is_none());
    }

    #[test]
    fn test_swap_remove_single_segment() {
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        for value in 0..10 {
            sut.push(value);
        }
        assert_eq!(sut.len(), 10);
        let five = sut.swap_remove(5);
        assert_eq!(five, 5);
        assert_eq!(sut.pop(), Some(8));
        assert_eq!(sut[5], 9);
    }

    #[test]
    fn test_swap_remove_multiple_segments() {
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        for value in 0..512 {
            sut.push(value);
        }
        assert_eq!(sut.len(), 512);
        let eighty = sut.swap_remove(80);
        assert_eq!(eighty, 80);
        assert_eq!(sut.pop(), Some(510));
        assert_eq!(sut[80], 511);
    }

    #[test]
    #[should_panic(expected = "swap_remove index (is 0) should be < len (is 0)")]
    fn test_swap_remove_panic_empty() {
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        sut.swap_remove(0);
    }

    #[test]
    #[should_panic(expected = "swap_remove index (is 1) should be < len (is 1)")]
    fn test_swap_remove_panic_range_edge() {
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        sut.push(1);
        sut.swap_remove(1);
    }

    #[test]
    #[should_panic(expected = "swap_remove index (is 2) should be < len (is 1)")]
    fn test_swap_remove_panic_range_exceed() {
        let mut sut: SegmentArray<u32> = SegmentArray::new();
        sut.push(1);
        sut.swap_remove(2);
    }

    #[test]
    fn test_push_get_thousands_structs() {
        struct MyData {
            a: u64,
            b: i32,
        }
        let mut sut: SegmentArray<MyData> = SegmentArray::new();
        for value in 0..88_888i32 {
            sut.push(MyData {
                a: value as u64,
                b: value,
            });
        }
        assert_eq!(sut.len(), 88_888);
        for idx in 0..88_888i32 {
            let maybe = sut.get(idx as usize);
            assert!(maybe.is_some(), "{idx} is none");
            let actual = maybe.unwrap();
            assert_eq!(idx as u64, actual.a);
            assert_eq!(idx, actual.b);
        }
    }

    #[test]
    fn test_push_get_hundred_ints() {
        let mut sut: SegmentArray<i32> = SegmentArray::new();
        for value in 0..100 {
            sut.push(value);
        }
        assert_eq!(sut.len(), 100);
        for idx in 0..100 {
            let maybe = sut.get(idx);
            assert!(maybe.is_some(), "{idx} is none");
            let actual = maybe.unwrap();
            assert_eq!(idx, *actual as usize);
        }
        assert_eq!(sut[99], 99);
    }

    #[test]
    fn test_len_and_capacity() {
        let mut sut: SegmentArray<i32> = SegmentArray::new();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 0);
        for value in 0..100 {
            sut.push(value);
        }
        assert_eq!(sut.len(), 100);
        assert_eq!(sut.capacity(), 192);
    }

    #[test]
    fn test_clear_and_reuse_tiny() {
        // clear an array that allocated only one segment
        let inputs = [
            "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for item in inputs {
            sut.push(item.to_owned());
        }
        assert_eq!(sut.len(), 9);
        sut.clear();
        assert_eq!(sut.len(), 0);
        for item in inputs {
            sut.push(item.to_owned());
        }
        assert_eq!(sut.len(), 9);
        // implicitly drop()
    }

    #[test]
    fn test_clear_and_reuse_ints() {
        let mut sut: SegmentArray<i32> = SegmentArray::new();
        for value in 0..512 {
            sut.push(value);
        }
        assert_eq!(sut.len(), 512);
        sut.clear();
        assert_eq!(sut.len(), 0);
        for value in 0..512 {
            sut.push(value);
        }
        for idx in 0..512 {
            let maybe = sut.get(idx);
            assert!(maybe.is_some(), "{idx} is none");
            let actual = maybe.unwrap();
            assert_eq!(idx, *actual as usize);
        }
    }

    #[test]
    fn test_clear_and_reuse_strings() {
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for _ in 0..512 {
            let value = ulid::Ulid::new().to_string();
            sut.push(value);
        }
        assert_eq!(sut.len(), 512);
        sut.clear();
        assert_eq!(sut.len(), 0);
        for _ in 0..512 {
            let value = ulid::Ulid::new().to_string();
            sut.push(value);
        }
        assert_eq!(sut.len(), 512);
        // implicitly drop()
    }

    #[test]
    fn test_push_get_many_ints() {
        let mut sut: SegmentArray<i32> = SegmentArray::new();
        for value in 0..1_000_000 {
            sut.push(value);
        }
        assert_eq!(sut.len(), 1_000_000);
        for idx in 0..1_000_000 {
            let maybe = sut.get(idx);
            assert!(maybe.is_some(), "{idx} is none");
            let actual = maybe.unwrap();
            assert_eq!(idx, *actual as usize);
        }
        assert_eq!(sut[99_999], 99_999);
    }

    #[test]
    fn test_array_iterator() {
        let inputs = [
            "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for item in inputs {
            sut.push(item.to_owned());
        }
        for (idx, elem) in sut.iter().enumerate() {
            assert_eq!(inputs[idx], elem);
        }
    }

    #[test]
    fn test_array_intoiterator() {
        // an array that only requires a single segment
        let inputs = [
            "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for item in inputs {
            sut.push(item.to_owned());
        }
        for (idx, elem) in sut.into_iter().enumerate() {
            assert_eq!(inputs[idx], elem);
        }
        // sut.len(); // error: ownership of sut was moved
    }

    #[test]
    fn test_array_intoiterator_drop_tiny() {
        // an array that only requires a single segment and only some need to be
        // dropped after partially iterating the values
        let inputs = [
            "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        ];
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for item in inputs {
            sut.push(item.to_owned());
        }
        for (idx, _) in sut.into_iter().enumerate() {
            if idx > 2 {
                break;
            }
        }
        // implicitly drop()
    }

    #[test]
    fn test_array_intoiterator_drop_large() {
        // by adding 512 values and iterating less than 64 times, there will be
        // values in the first segment and some in the last segment, and two
        // segments inbetween that all need to be dropped
        let mut sut: SegmentArray<String> = SegmentArray::new();
        for _ in 0..512 {
            let value = ulid::Ulid::new().to_string();
            sut.push(value);
        }
        for (idx, _) in sut.into_iter().enumerate() {
            if idx >= 30 {
                break;
            }
        }
        // implicitly drop()
    }

    #[test]
    fn test_array_fromiterator() {
        let mut inputs: Vec<i32> = Vec::new();
        for value in 0..10_000 {
            inputs.push(value);
        }
        let sut: SegmentArray<i32> = inputs.into_iter().collect();
        assert_eq!(sut.len(), 10_000);
        for idx in 0..10_000i32 {
            let maybe = sut.get(idx as usize);
            assert!(maybe.is_some(), "{idx} is none");
            let actual = maybe.unwrap();
            assert_eq!(idx, *actual);
        }
    }

    #[test]
    fn test_push_get_many_instances_ints() {
        // test allocating, filling, and then dropping many instances
        for _ in 0..1_000 {
            let mut sut: SegmentArray<usize> = SegmentArray::new();
            for value in 0..10_000 {
                sut.push(value);
            }
            assert_eq!(sut.len(), 10_000);
        }
    }

    #[test]
    fn test_push_get_many_instances_strings() {
        // test allocating, filling, and then dropping many instances
        for _ in 0..1_000 {
            let mut sut: SegmentArray<String> = SegmentArray::new();
            for _ in 0..1_000 {
                let value = ulid::Ulid::new().to_string();
                sut.push(value);
            }
            assert_eq!(sut.len(), 1_000);
        }
    }
}