cs431_homework/hash_table/
growable_array.rs

1//! Growable array.
2
3use core::fmt::Debug;
4use core::mem::{self, ManuallyDrop};
5use core::sync::atomic::Ordering::*;
6
7use crossbeam_epoch::{Atomic, Guard, Owned, Shared};
8
9/// Growable array of `Atomic<T>`.
10///
11/// This is more complete version of the dynamic sized array from the paper. In the paper, the
12/// segment table is an array of arrays (segments) of pointers to the elements. In this
13/// implementation, a segment contains the pointers to the elements **or other child segments**. In
14/// other words, it is a tree that has segments as internal nodes.
15///
16/// # Example run
17///
18/// Suppose `SEGMENT_LOGSIZE = 3` (segment size 8).
19///
20/// When a new `GrowableArray` is created, `root` is initialized with `Atomic::null()`.
21///
22/// ```text
23///                          +----+
24///                          |root|
25///                          +----+
26/// ```
27///
28/// When you store element `cat` at the index `0b001`, it first initializes a segment.
29///
30/// ```text
31///                          +----+
32///                          |root|
33///                          +----+
34///                            | height: 1
35///                            v
36///                 +---+---+---+---+---+---+---+---+
37///                 |111|110|101|100|011|010|001|000|
38///                 +---+---+---+---+---+---+---+---+
39///                                           |
40///                                           v
41///                                         +---+
42///                                         |cat|
43///                                         +---+
44/// ```
45///
46/// When you store `fox` at `0b111011`, it is clear that there is no room for indices larger than
47/// `0b111`. So it first allocates another segment for upper 3 bits and moves the previous root
48/// segment (`0b000XXX` segment) under the `0b000XXX` branch of the the newly allocated segment.
49///
50/// ```text
51///                          +----+
52///                          |root|
53///                          +----+
54///                            | height: 2
55///                            v
56///                 +---+---+---+---+---+---+---+---+
57///                 |111|110|101|100|011|010|001|000|
58///                 +---+---+---+---+---+---+---+---+
59///                                               |
60///                                               v
61///                                      +---+---+---+---+---+---+---+---+
62///                                      |111|110|101|100|011|010|001|000|
63///                                      +---+---+---+---+---+---+---+---+
64///                                                                |
65///                                                                v
66///                                                              +---+
67///                                                              |cat|
68///                                                              +---+
69/// ```
70///
71/// And then, it allocates another segment for `0b111XXX` indices.
72///
73/// ```text
74///                          +----+
75///                          |root|
76///                          +----+
77///                            | height: 2
78///                            v
79///                 +---+---+---+---+---+---+---+---+
80///                 |111|110|101|100|011|010|001|000|
81///                 +---+---+---+---+---+---+---+---+
82///                   |                           |
83///                   v                           v
84/// +---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
85/// |111|110|101|100|011|010|001|000|    |111|110|101|100|011|010|001|000|
86/// +---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
87///                   |                                            |
88///                   v                                            v
89///                 +---+                                        +---+
90///                 |fox|                                        |cat|
91///                 +---+                                        +---+
92/// ```
93///
94/// Finally, when you store `owl` at `0b000110`, it traverses through the `0b000XXX` branch of the
95/// height 2 segment and arrives at its `0b110` leaf.
96///
97/// ```text
98///                          +----+
99///                          |root|
100///                          +----+
101///                            | height: 2
102///                            v
103///                 +---+---+---+---+---+---+---+---+
104///                 |111|110|101|100|011|010|001|000|
105///                 +---+---+---+---+---+---+---+---+
106///                   |                           |
107///                   v                           v
108/// +---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
109/// |111|110|101|100|011|010|001|000|    |111|110|101|100|011|010|001|000|
110/// +---+---+---+---+---+---+---+---+    +---+---+---+---+---+---+---+---+
111///                   |                        |                   |
112///                   v                        v                   v
113///                 +---+                    +---+               +---+
114///                 |fox|                    |owl|               |cat|
115///                 +---+                    +---+               +---+
116/// ```
117///
118/// When the array is dropped, only the segments are dropped and the **elements must not be
119/// dropped/deallocated**.
120///
121/// ```text
122///                 +---+                    +---+               +---+
123///                 |fox|                    |owl|               |cat|
124///                 +---+                    +---+               +---+
125/// ```
126///
127/// Instead, it should be handled by the container that the elements actually belong to. For
128/// example, in `SplitOrderedList` the destruction of elements are handled by the inner `List`.
129#[derive(Debug)]
130pub struct GrowableArray<T> {
131    root: Atomic<Segment<T>>,
132}
133
134const SEGMENT_LOGSIZE: usize = 10;
135
136/// A fixed size array of atomic pointers to other `Segment<T>` or `T`.
137///
138/// Each segment is either an inner segment with pointers to other, children `Segment<T>` or an
139/// element segment with pointers to `T`. This is determined by the height of this segment in the
140/// main array, which one needs to track separately. For example, use the main array root's tag.
141///
142/// Since destructing segments requires its height information, it is not recommended to implement
143/// [`Drop`]. Rather, implement and use the custom [`Segment::deallocate`] method that accounts for
144/// the height of the segment.
145union Segment<T> {
146    children: ManuallyDrop<[Atomic<Segment<T>>; 1 << SEGMENT_LOGSIZE]>,
147    elements: ManuallyDrop<[Atomic<T>; 1 << SEGMENT_LOGSIZE]>,
148}
149
150impl<T> Segment<T> {
151    /// Create a new segment filled with null pointers. It is up to the callee to whether to use
152    /// this as an intermediate or an element segment.
153    fn new() -> Owned<Self> {
154        Owned::new(
155            // SAFETY: An array of null pointers can be interperted as either an intermediate
156            // segment or an element segment.
157            unsafe { mem::zeroed() },
158        )
159    }
160
161    /// Deallocates a segment of `height`.
162    ///
163    /// # Safety
164    ///
165    /// - `self` must actually have height `height`.
166    /// - There should be no other references to possible children segments.
167    unsafe fn deallocate(self, height: usize) {
168        todo!()
169    }
170}
171
172impl<T> Debug for Segment<T> {
173    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
174        write!(f, "Segment")
175    }
176}
177
178impl<T> Drop for GrowableArray<T> {
179    /// Deallocate segments, but not the individual elements.
180    fn drop(&mut self) {
181        todo!()
182    }
183}
184
185impl<T> Default for GrowableArray<T> {
186    fn default() -> Self {
187        Self::new()
188    }
189}
190
191impl<T> GrowableArray<T> {
192    /// Create a new growable array.
193    pub fn new() -> Self {
194        Self {
195            root: Atomic::null(),
196        }
197    }
198
199    /// Returns the reference to the `Atomic` pointer at `index`. Allocates new segments if
200    /// necessary.
201    pub fn get<'g>(&self, index: usize, guard: &'g Guard) -> &'g Atomic<T> {
202        todo!()
203    }
204}