Expand description
An append-only (no insert or remove) growable array as described in the blog post 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.
In terms of this Rust implementation, rather than stable “pointers”, the
references returned from SegmentedArray::get() will be stable. The
behavior, memory layout, and performance of this implementation should be
identical 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 the previous one
- The total capacity if 4,294,967,232 items
This data structure is meant to hold an unknown, though likely large, number
of elements, otherwise Vec would be more appropriate. An empty array will
have a hefty size of around 224 bytes.
Structs§
- SegArray
Into Iter - An iterator that moves out of a segmented array.
- SegArray
Iter - Immutable segmented array iterator.
- Segmented
Array - Append-only growable array that uses a list of progressivly larger segments to avoid the allocate-and-copy that typical growable data structures employ.