Crate segment_array Copy item path

An implmentation of the segment 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.

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.