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
use crate::Fragment;
use alloc::{string::String, vec::Vec};
use orx_pseudo_default::PseudoDefault;
/// Growth strategy of a split vector.
pub trait Growth: Clone + PseudoDefault {
/// Given that the split vector has no fragments yet,
/// returns the capacity of the first fragment.
fn first_fragment_capacity(&self) -> usize {
self.new_fragment_capacity_from([].into_iter())
}
/// Given that the split vector contains the given `fragments`,
/// returns the capacity of the next fragment.
#[inline(always)]
fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> usize {
self.new_fragment_capacity_from(fragments.iter().map(|x| x.capacity()))
}
/// Given that the split vector contains fragments with the given `fragment_capacities`,
/// returns the capacity of the next fragment.
fn new_fragment_capacity_from(
&self,
fragment_capacities: impl ExactSizeIterator<Item = usize>,
) -> usize;
/// ***O(fragments.len())*** Returns the location of the element with the given `element_index` on the split vector as a tuple of (fragment-index, index-within-fragment).
///
/// Returns None if the element index is out of bounds.
fn get_fragment_and_inner_indices<T>(
&self,
_vec_len: usize,
fragments: &[Fragment<T>],
element_index: usize,
) -> Option<(usize, usize)> {
let mut prev_end = 0;
let mut end = 0;
for (f, fragment) in fragments.iter().enumerate() {
end += fragment.len();
if element_index < end {
return Some((f, element_index - prev_end));
}
prev_end = end;
}
None
}
/// ***O(fragments.len())*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`.
///
/// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
///
/// # Safety
///
/// This method allows to write to a memory which is greater than the vector's length.
/// On the other hand, it will never return a pointer to a memory location that the vector does not own.
unsafe fn get_ptr_mut<T>(&self, fragments: &mut [Fragment<T>], index: usize) -> Option<*mut T> {
self.get_ptr_mut_and_indices(fragments, index).map(|x| x.0)
}
/// ***O(fragments.len())*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`
/// together with the index of the fragment that the element belongs to
/// and index of the element withing the respective fragment.
///
/// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
///
/// # Safety
///
/// This method allows to write to a memory which is greater than the vector's length.
/// On the other hand, it will never return a pointer to a memory location that the vector does not own.
unsafe fn get_ptr_mut_and_indices<T>(
&self,
fragments: &mut [Fragment<T>],
index: usize,
) -> Option<(*mut T, usize, usize)> {
let mut prev_cumulative_capacity = 0;
let mut cumulative_capacity = 0;
for (f, fragment) in fragments.iter_mut().enumerate() {
cumulative_capacity += fragment.capacity();
if index < cumulative_capacity {
let index_in_fragment = index - prev_cumulative_capacity;
return Some((
fragment.as_mut_ptr().add(index_in_fragment),
f,
index_in_fragment,
));
}
prev_cumulative_capacity = cumulative_capacity;
}
None
}
/// Returns the maximum number of elements that can safely be stored in a concurrent program.
///
/// Note that pinned vectors already keep the elements pinned to their memory locations.
/// Therefore, concurrently safe growth here corresponds to growth without requiring `fragments` collection to allocate.
/// Recall that `fragments` contains meta information about the splits of the `SplitVec`, such as the capacity of each split.
///
/// This default implementation is not the most efficient as it allocates a small vector to compute the capacity.
/// However, it is almost always possible to provide a non-allocating implementation provided that the concurrency is relevant.
/// `Doubling`, `Recursive` and `Linear` growth strategies introduced in this crate all override this method.
///
/// # Panics
///
/// Panics if `fragments.len() < fragments_capacity`, which must not hold.
fn maximum_concurrent_capacity<T>(
&self,
fragments: &[Fragment<T>],
fragments_capacity: usize,
) -> usize {
assert!(fragments_capacity >= fragments.len());
if fragments_capacity == fragments.len() {
fragments.iter().map(|x| x.capacity()).sum()
} else {
let mut cloned: Vec<Fragment<T>> = Vec::with_capacity(fragments_capacity);
for fragment in fragments {
cloned.push(Vec::with_capacity(fragment.capacity()).into());
}
for _ in fragments.len()..fragments_capacity {
let new_capacity = self.new_fragment_capacity(&cloned);
let fragment = Vec::with_capacity(new_capacity).into();
cloned.push(fragment);
}
cloned.iter().map(|x| x.capacity()).sum()
}
}
/// Returns the number of fragments with this growth strategy in order to be able to reach a capacity of `maximum_capacity` of elements.
/// Returns the error if it the growth strategy does not allow the required number of fragments.
///
/// This method is relevant and useful for concurrent programs, which helps in avoiding the fragments to allocate.
fn required_fragments_len<T>(
&self,
fragments: &[Fragment<T>],
maximum_capacity: usize,
) -> Result<usize, String> {
fn overflown_err() -> String {
alloc::format!(
"Maximum cumulative capacity that can be reached is {}.",
usize::MAX
)
}
let mut cloned: Vec<Fragment<T>> = Vec::new();
for fragment in fragments {
cloned.push(Vec::with_capacity(fragment.capacity()).into());
}
let mut num_fragments = cloned.len();
let mut current_capacity: usize = cloned.iter().map(|x| x.capacity()).sum();
while current_capacity < maximum_capacity {
let new_capacity = self.new_fragment_capacity(&cloned);
let (new_current_capacity, overflown) = current_capacity.overflowing_add(new_capacity);
if overflown {
return Err(overflown_err());
}
let fragment = Vec::with_capacity(new_capacity).into();
cloned.push(fragment);
current_capacity = new_current_capacity;
num_fragments += 1;
}
Ok(num_fragments)
}
}
/// Growth strategy of a split vector which allows for constant time access to the elements.
pub trait GrowthWithConstantTimeAccess: Growth {
/// ***O(1)*** Returns the location of the element with the given `element_index` on the split vector as a tuple of (fragment-index, index-within-fragment).
///
/// Notice that unlike the [`Growth::get_fragment_and_inner_indices`]:
/// * this method does not receive the current state of the split vector,
/// * therefore, it does not perform bounds check,
/// * and hence, returns the expected fragment and within-fragment indices for any index computed by the constant access time function.
fn get_fragment_and_inner_indices_unchecked(&self, element_index: usize) -> (usize, usize);
/// ***O(1)*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`.
///
/// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
///
/// # Safety
///
/// This method allows to write to a memory which is greater than the split vector's length.
/// On the other hand, it will never return a pointer to a memory location that the vector does not own.
unsafe fn get_ptr_mut<T>(&self, fragments: &mut [Fragment<T>], index: usize) -> Option<*mut T> {
let (f, i) = self.get_fragment_and_inner_indices_unchecked(index);
fragments
.get_mut(f)
.map(|fragment| fragment.as_mut_ptr().add(i))
}
/// ***O(1)*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`
/// together with the index of the fragment that the element belongs to
/// and index of the element withing the respective fragment.
///
/// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
///
/// # Safety
///
/// This method allows to write to a memory which is greater than the split vector's length.
/// On the other hand, it will never return a pointer to a memory location that the vector does not own.
unsafe fn get_ptr_mut_and_indices<T>(
&self,
fragments: &mut [Fragment<T>],
index: usize,
) -> Option<(*mut T, usize, usize)> {
let (f, i) = self.get_fragment_and_inner_indices_unchecked(index);
fragments
.get_mut(f)
.map(|fragment| (fragment.as_mut_ptr().add(i), f, i))
}
/// ***O(1)*** Returns the capacity of the fragment with the given `fragment_index`.
fn fragment_capacity_of(&self, fragment_index: usize) -> usize;
}