pub struct GrowableArray<T> {
root: Atomic<Segment<T>>,
}
Expand description
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>>