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}