1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
use crate::{PinnedVec, PinnedVecGrowthError};
use core::ops::{Range, RangeBounds};
/// A wrapper for a pinned vector which provides additional guarantees for concurrent programs.
///
/// Note that a concurrent pinned vec inherits pinned memory location guarantees.
///
/// The struct encapsulates many methods of the pinned vector which are not suitable for concurrent programs.
/// Further, it exposes new and mostly unsafe methods for allowing performant concurrent collections.
/// It is designed to be a core structure for concurrent collections with a safe api.
pub trait ConcurrentPinnedVec<T> {
/// Type of the wrapped pinned vector.
type P: PinnedVec<T>;
/// Iterator yielding slices corresponding to a range of indices, returned by the `slice` method.
type SliceIter<'a>: IntoIterator<Item = &'a [T]> + Default
where
T: 'a,
Self: 'a;
/// Iterator yielding mutable slices corresponding to a range of indices, returned by the `slice_mut` and `slice_mut_unchecked` methods.
type SliceMutIter<'a>: IntoIterator<Item = &'a mut [T]> + Default
where
T: 'a,
Self: 'a;
/// Iterator yielding pointers to elements of the vector.
type PtrIter<'a>: ExactSizeIterator<Item = *mut T>
where
Self: 'a;
/// Iterator that the pinned vector is converted into, which moves out elements.
type IntoIter: ExactSizeIterator<Item = T>;
/// Converts back to the underlying pinned vector with the given length.
///
/// # Safety
///
/// This method is unsafe due to the following.
/// The concurrent pinned vector is the core data structure for different concurrent collections
/// which allow writing to the vector in different ways.
/// The wrapper is responsible to deal with the gaps.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn into_inner(self, len: usize) -> Self::P;
/// Clones the concurrent pinned vector with for the first `len` elements.
/// The created concurrent vector will have the same capacity and maximum capacity as this collection;
/// however, only the values within 0..len will be cloned to the target.
///
/// # Safety
///
/// This method is unsafe due to the following.
/// The concurrent pinned vector is the core data structure for different concurrent collections
/// which allow writing to the vector in different ways.
/// The wrapper is responsible to deal with the gaps.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn clone_with_len(&self, len: usize) -> Self
where
T: Clone;
// &self get
/// Returns an iterator over positions `0..len` of the vector.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn iter<'a>(&'a self, len: usize) -> impl Iterator<Item = &'a T> + 'a
where
T: 'a;
/// Returns an iterator over positions `range` of the vector.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if entries in all positions `range` are written.
unsafe fn iter_over_range<'a, R: RangeBounds<usize>>(
&'a self,
range: R,
) -> impl Iterator<Item = &'a T> + 'a
where
T: 'a;
/// Returns a reference to the element at the `index`-th position.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if the entry at position `index` is written.
unsafe fn get(&self, index: usize) -> Option<&T>;
/// Returns a mutable reference to the element at the `index`-th position.
///
/// # Safety
///
/// This method is used to write to the vector.
/// Therefore, its position will initially be uninitialized; hence, reading the pointer might result in UB.
unsafe fn get_ptr_mut(&self, index: usize) -> *mut T;
/// Returns an iterator of mutable slices to the elements extending over positions `range` of the vector.
///
/// # Safety
///
/// This method is used to write to the vector.
/// Therefore, the positions will initially be uninitialized; hence, reading from the slices might result in UB.
unsafe fn slices_mut<R: RangeBounds<usize>>(&self, range: R) -> Self::SliceMutIter<'_>;
/// Returns an iterator of slices to the elements extending over positions `range` of the vector.
fn slices<R: RangeBounds<usize>>(&self, range: R) -> Self::SliceIter<'_>;
// capacity
/// Returns the maximum possible capacity that the vector can concurrently grow to without requiring a `&mut self` reference.
///
/// In order to grow beyond this capacity, `reserve_maximum_concurrent_capacity` method can be used.
fn max_capacity(&self) -> usize;
/// Returns the current capacity of the vector, which is actually allocated.
fn capacity(&self) -> usize;
/// Tries to concurrently grow the capacity of the vector to at least `new_capacity`. Returns:
/// * Ok of the new capacity if succeeds
/// * Err otherwise.
///
/// Behavior of this method is deterministic.
/// The method always succeeds (fails) if `new_capacity <= self.max_capacity()` (otherwise).
///
/// If the method returns an error, `reserve_maximum_concurrent_capacity` method can be used; however, with a `&mut self` reference.
/// Then, `grow_to` will succeed.
fn grow_to(&self, new_capacity: usize) -> Result<usize, PinnedVecGrowthError>;
/// Tries to concurrently grow the capacity of the vector to at least `new_capacity`. Returns:
/// * Ok of the new capacity if succeeds
/// * Err otherwise.
///
/// Behavior of this method is deterministic.
/// The method always succeeds (fails) if `new_capacity <= self.max_capacity()` (otherwise).
///
/// If the method returns an error, `reserve_maximum_concurrent_capacity` method can be used;
/// however, with a `&mut self` reference.
/// Then, `grow_to` will succeed.
///
/// During growth:
///
/// * length of the vector is increased to its new capacity;
/// * the elements in the range `len..capacity` are filled with the values
/// obtained by repeatedly calling the function `fill_with`.
fn grow_to_and_fill_with<F>(
&self,
new_capacity: usize,
fill_with: F,
) -> Result<usize, PinnedVecGrowthError>
where
F: Fn() -> T;
/// Fills the provided `range` with elements created by successively calling the `fill_with` function.
fn fill_with<F>(&self, range: Range<usize>, fill_with: F)
where
F: Fn() -> T;
/// Increases the `maximum_capacity` to the `new_maximum_capacity`.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
/// The vector must be gap-free while increasing the maximum capacity.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn reserve_maximum_concurrent_capacity(
&mut self,
len: usize,
new_maximum_capacity: usize,
) -> usize;
/// Increases the `maximum_capacity` to the `new_maximum_capacity`.
/// If capacity extension leads to allocation, allocated memory is filled with the given function.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
/// The vector must be gap-free while increasing the maximum capacity.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn reserve_maximum_concurrent_capacity_fill_with<F>(
&mut self,
len: usize,
new_maximum_capacity: usize,
fill_with: F,
) -> usize
where
F: Fn() -> T;
// &mut self
/// Sets the length of the underlying pinned vector to the given `len`.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn set_pinned_vec_len(&mut self, len: usize);
/// Returns a mutable iterator over positions `0..len` of the vector.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn iter_mut<'a>(&'a mut self, len: usize) -> impl Iterator<Item = &'a mut T> + 'a
where
T: 'a;
/// Returns a reference to the element at the `index`-th position.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if the entry at position `index` is written.
unsafe fn get_mut(&mut self, index: usize) -> Option<&mut T>;
/// Clears the concurrent pinned vector.
///
/// # Safety
///
/// This method is unsafe since the concurrent pinned vector might contain gaps.
///
/// This method can safely be called if entries in all positions `0..len` are written.
unsafe fn clear(&mut self, len: usize);
/// Returns an iterator yielding pointers to elements within the given `range`.
///
/// # SAFETY
///
/// The method is marked unsafe due to the possibility of `range` being out of bounds.
/// This method does not perform a bounds check and it leads to UB if the range is
/// out of bounds.
///
/// Returned iterator is created from a shared reference to the vec.
/// Therefore, the vec, cannot be mutated while using the iterator.
///
/// Further, since the iterator is created using a shared reference to the vec,
/// it cannot outlive the vec.
///
/// These guarantee that all pointers that the iterator yields will be valid.
///
/// In brief, it is safe to use this method provided that the caller guarantees
/// that the range is in bounds.
unsafe fn ptr_iter_unchecked(&self, range: Range<usize>) -> Self::PtrIter<'_>;
/// Converts the concurrent pinned vector into an exact sized iterator.
///
/// # SAFETY
///
/// This method is to be called when only `range` contains valid elements of the vector
/// while elements in other positions are already dropped, if they need to be dropped.
///
/// The iterator is then responsible for yielding the valid elements within this `range`,
/// or dropping them if the iterator is not fully consumed. Furthermore, once the iterator
/// is dropped, all the allocations of the concurrent pinned vector will also be dropped.
unsafe fn into_iter(self, range: Range<usize>) -> Self::IntoIter;
}