Segmented Array

This crate is deprecated, please use segment-array instead.

lib.rs:

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.