Crate segment_array

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 SegmentArray::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
• Total capacity of 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

SegArrayIntoIter

An iterator that moves out of a segment array.

SegArrayIter

Immutable segment array iterator.

SegmentArray

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.