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

use crate::{PinnedVec, PinnedVecGrowthError};
use std::ops::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>;

    /// 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;

    // &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 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::P as PinnedVec<T>>::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::P as PinnedVec<T>>::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;

    /// 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;

    // &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);
}