Struct GrowableArray

pub struct GrowableArray<T> {
    root: Atomic<Segment<T>>,
}

Growable array of Atomic<T>.

This is more complete version of the dynamic sized array from the paper. In the paper, the segment table is an array of arrays (segments) of pointers to the elements. In this implementation, a segment contains the pointers to the elements or other child segments. In other words, it is a tree that has segments as internal nodes.

Example run

Suppose SEGMENT_LOGSIZE = 3 (segment size 8).

When a new GrowableArray is created, root is initialized with Atomic::null().

                         +----+
                         |root|
                         +----+

When you store element cat at the index 0b001, it first initializes a segment.

                         +----+
                         |root|
                         +----+
                           | height: 1
                           v
                +---+---+---+---+---+---+---+---+
                |111|110|101|100|011|010|001|000|
                +---+---+---+---+---+---+---+---+
                                          |
                                          v
                                        +---+
                                        |cat|
                                        +---+

When you store fox at 0b111011, it is clear that there is no room for indices larger than 0b111. So it first allocates another segment for upper 3 bits and moves the previous root segment (0b000XXX segment) under the 0b000XXX branch of the the newly allocated segment.

                         +----+
                         |root|
                         +----+
                           | height: 2
                           v
                +---+---+---+---+---+---+---+---+
                |111|110|101|100|011|010|001|000|
                +---+---+---+---+---+---+---+---+
                                              |
                                              v
                                     +---+---+---+---+---+---+---+---+
                                     |111|110|101|100|011|010|001|000|
                                     +---+---+---+---+---+---+---+---+
                                                               |
                                                               v
                                                             +---+
                                                             |cat|
                                                             +---+

And then, it allocates another segment for 0b111XXX indices.

                         +----+
                         |root|
                         +----+
                           | height: 2
                           v
                +---+---+---+---+---+---+---+---+
                |111|110|101|100|011|010|001|000|
                +---+---+---+---+---+---+---+---+
                  |                           |
                  v                           v
+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
|111|110|101|100|011|010|001|000|    |111|110|101|100|011|010|001|000|
+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
                  |                                            |
                  v                                            v
                +---+                                        +---+
                |fox|                                        |cat|
                +---+                                        +---+

Finally, when you store owl at 0b000110, it traverses through the 0b000XXX branch of the height 2 segment and arrives at its 0b110 leaf.

                         +----+
                         |root|
                         +----+
                           | height: 2
                           v
                +---+---+---+---+---+---+---+---+
                |111|110|101|100|011|010|001|000|
                +---+---+---+---+---+---+---+---+
                  |                           |
                  v                           v
+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
|111|110|101|100|011|010|001|000|    |111|110|101|100|011|010|001|000|
+---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
                  |                        |                   |
                  v                        v                   v
                +---+                    +---+               +---+
                |fox|                    |owl|               |cat|
                +---+                    +---+               +---+

When the array is dropped, only the segments are dropped and the elements must not be dropped/deallocated.

                +---+                    +---+               +---+
                |fox|                    |owl|               |cat|
                +---+                    +---+               +---+

Instead, it should be handled by the container that the elements actually belong to. For example, in SplitOrderedList the destruction of elements are handled by the inner List.

Fields

root: Atomic<Segment<T>>

Implementations

impl<T> GrowableArray<T>

pub fn new() -> Self

Create a new growable array.

pub fn get<'g>(&self, index: usize, guard: &'g Guard) -> &'g Atomic<T>

Returns the reference to the Atomic pointer at index. Allocates new segments if necessary.

Trait Implementations

impl<T: Debug> Debug for GrowableArray<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for GrowableArray<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Drop for GrowableArray<T>

fn drop(&mut self)

Deallocate segments, but not the individual elements.