Struct GrowableArray

Source
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>>

Implementations§

Source§

impl<T> GrowableArray<T>

Source

pub fn new() -> Self

Create a new growable array.

Source

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§

Source§

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

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T> Default for GrowableArray<T>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T> Drop for GrowableArray<T>

Source§

fn drop(&mut self)

Deallocate segments, but not the individual elements.

Auto Trait Implementations§

§

impl<T> !Freeze for GrowableArray<T>

§

impl<T> RefUnwindSafe for GrowableArray<T>
where T: RefUnwindSafe,

§

impl<T> Send for GrowableArray<T>
where T: Send + Sync,

§

impl<T> Sync for GrowableArray<T>
where T: Send + Sync,

§

impl<T> Unpin for GrowableArray<T>

§

impl<T> UnwindSafe for GrowableArray<T>
where T: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> Pointable for T

Source§

const ALIGN: usize

The alignment of pointer.
Source§

type Init = T

The type for initializers.
Source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
Source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
Source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
Source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

Source§

fn vzip(self) -> V