orx_split_vec/growth/growth_trait.rs
1use crate::Fragment;
2use alloc::{string::String, vec::Vec};
3use orx_pseudo_default::PseudoDefault;
4
5/// Growth strategy of a split vector.
6pub trait Growth: Clone + PseudoDefault + Send + Sync {
7 /// Given that the split vector has no fragments yet,
8 /// returns the capacity of the first fragment.
9 fn first_fragment_capacity(&self) -> usize {
10 self.new_fragment_capacity_from([].into_iter())
11 }
12
13 /// Given that the split vector contains the given `fragments`,
14 /// returns the capacity of the next fragment.
15 #[inline(always)]
16 fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> usize {
17 self.new_fragment_capacity_from(fragments.iter().map(|x| x.capacity()))
18 }
19
20 /// Given that the split vector contains fragments with the given `fragment_capacities`,
21 /// returns the capacity of the next fragment.
22 fn new_fragment_capacity_from(
23 &self,
24 fragment_capacities: impl ExactSizeIterator<Item = usize>,
25 ) -> usize;
26
27 /// ***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).
28 ///
29 /// Returns None if the element index is out of bounds.
30 fn get_fragment_and_inner_indices<T>(
31 &self,
32 _vec_len: usize,
33 fragments: &[Fragment<T>],
34 element_index: usize,
35 ) -> Option<(usize, usize)> {
36 let mut prev_end = 0;
37 let mut end = 0;
38 for (f, fragment) in fragments.iter().enumerate() {
39 end += fragment.len();
40 if element_index < end {
41 return Some((f, element_index - prev_end));
42 }
43 prev_end = end;
44 }
45 None
46 }
47
48 /// ***O(fragments.len())*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`.
49 ///
50 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
51 ///
52 /// # Safety
53 ///
54 /// This method allows to write to a memory which is greater than the vector's length.
55 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
56 fn get_ptr<T>(&self, fragments: &[Fragment<T>], index: usize) -> Option<*const T> {
57 self.get_ptr_and_indices(fragments, index).map(|x| x.0)
58 }
59
60 /// ***O(fragments.len())*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`.
61 ///
62 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
63 ///
64 /// # Safety
65 ///
66 /// This method allows to write to a memory which is greater than the vector's length.
67 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
68 fn get_ptr_mut<T>(&self, fragments: &mut [Fragment<T>], index: usize) -> Option<*mut T> {
69 self.get_ptr_mut_and_indices(fragments, index).map(|x| x.0)
70 }
71
72 /// ***O(fragments.len())*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`
73 /// together with the index of the fragment that the element belongs to
74 /// and index of the element withing the respective fragment.
75 ///
76 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
77 ///
78 /// # Safety
79 ///
80 /// This method allows to write to a memory which is greater than the vector's length.
81 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
82 fn get_ptr_and_indices<T>(
83 &self,
84 fragments: &[Fragment<T>],
85 index: usize,
86 ) -> Option<(*const T, usize, usize)> {
87 let mut prev_cumulative_capacity = 0;
88 let mut cumulative_capacity = 0;
89 for (f, fragment) in fragments.iter().enumerate() {
90 cumulative_capacity += fragment.capacity();
91 if index < cumulative_capacity {
92 let index_in_fragment = index - prev_cumulative_capacity;
93 return Some((
94 unsafe { fragment.as_ptr().add(index_in_fragment) },
95 f,
96 index_in_fragment,
97 ));
98 }
99 prev_cumulative_capacity = cumulative_capacity;
100 }
101 None
102 }
103
104 /// ***O(fragments.len())*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`
105 /// together with the index of the fragment that the element belongs to
106 /// and index of the element withing the respective fragment.
107 ///
108 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
109 ///
110 /// # Safety
111 ///
112 /// This method allows to write to a memory which is greater than the vector's length.
113 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
114 fn get_ptr_mut_and_indices<T>(
115 &self,
116 fragments: &mut [Fragment<T>],
117 index: usize,
118 ) -> Option<(*mut T, usize, usize)> {
119 let mut prev_cumulative_capacity = 0;
120 let mut cumulative_capacity = 0;
121 for (f, fragment) in fragments.iter_mut().enumerate() {
122 cumulative_capacity += fragment.capacity();
123 if index < cumulative_capacity {
124 let index_in_fragment = index - prev_cumulative_capacity;
125 return Some((
126 unsafe { fragment.as_mut_ptr().add(index_in_fragment) },
127 f,
128 index_in_fragment,
129 ));
130 }
131 prev_cumulative_capacity = cumulative_capacity;
132 }
133 None
134 }
135
136 /// Returns the maximum number of elements that can safely be stored in a concurrent program.
137 ///
138 /// Note that pinned vectors already keep the elements pinned to their memory locations.
139 /// Therefore, concurrently safe growth here corresponds to growth without requiring `fragments` collection to allocate.
140 /// Recall that `fragments` contains meta information about the splits of the `SplitVec`, such as the capacity of each split.
141 ///
142 /// This default implementation is not the most efficient as it allocates a small vector to compute the capacity.
143 /// However, it is almost always possible to provide a non-allocating implementation provided that the concurrency is relevant.
144 /// `Doubling`, `Recursive` and `Linear` growth strategies introduced in this crate all override this method.
145 ///
146 /// # Panics
147 ///
148 /// Panics if `fragments.len() < fragments_capacity`, which must not hold.
149 fn maximum_concurrent_capacity<T>(
150 &self,
151 fragments: &[Fragment<T>],
152 fragments_capacity: usize,
153 ) -> usize {
154 assert!(fragments_capacity >= fragments.len());
155
156 if fragments_capacity == fragments.len() {
157 fragments.iter().map(|x| x.capacity()).sum()
158 } else {
159 let mut cloned: Vec<Fragment<T>> = Vec::with_capacity(fragments_capacity);
160 for fragment in fragments {
161 let fragment = Fragment::new_empty(fragment.capacity());
162 cloned.push(fragment);
163 }
164 for _ in fragments.len()..fragments_capacity {
165 let new_capacity = self.new_fragment_capacity(&cloned);
166 let fragment = Fragment::new_empty(new_capacity);
167 cloned.push(fragment);
168 }
169 cloned.iter().map(|x| x.capacity()).sum()
170 }
171 }
172
173 /// Returns the number of fragments with this growth strategy in order to be able to reach a capacity of `maximum_capacity` of elements.
174 /// Returns the error if it the growth strategy does not allow the required number of fragments.
175 ///
176 /// This method is relevant and useful for concurrent programs, which helps in avoiding the fragments to allocate.
177 fn required_fragments_len<T>(
178 &self,
179 fragments: &[Fragment<T>],
180 maximum_capacity: usize,
181 ) -> Result<usize, String> {
182 fn overflown_err() -> String {
183 alloc::format!(
184 "Maximum cumulative capacity that can be reached is {}.",
185 usize::MAX
186 )
187 }
188
189 let mut cloned: Vec<Fragment<T>> = Vec::new();
190 for fragment in fragments {
191 let fragment = Fragment::new_empty(fragment.capacity());
192 cloned.push(fragment);
193 }
194
195 let mut num_fragments = cloned.len();
196 let mut current_capacity: usize = cloned.iter().map(|x| x.capacity()).sum();
197
198 while current_capacity < maximum_capacity {
199 let new_capacity = self.new_fragment_capacity(&cloned);
200 let (new_current_capacity, overflown) = current_capacity.overflowing_add(new_capacity);
201 if overflown {
202 return Err(overflown_err());
203 }
204
205 let fragment = Fragment::new_empty(new_capacity);
206 cloned.push(fragment);
207
208 current_capacity = new_current_capacity;
209 num_fragments += 1;
210 }
211
212 Ok(num_fragments)
213 }
214
215 /// Returns the maximum possible bound on concurrent capacity.
216 fn maximum_concurrent_capacity_bound<T>(&self, _: &[Fragment<T>], _: usize) -> usize {
217 usize::MAX
218 }
219}
220
221/// Growth strategy of a split vector which allows for constant time access to the elements.
222pub trait GrowthWithConstantTimeAccess: Growth {
223 /// ***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).
224 ///
225 /// Notice that unlike the [`Growth::get_fragment_and_inner_indices`]:
226 /// * this method does not receive the current state of the split vector,
227 /// * therefore, it does not perform bounds check,
228 /// * and hence, returns the expected fragment and within-fragment indices for any index computed by the constant access time function.
229 fn get_fragment_and_inner_indices_unchecked(&self, element_index: usize) -> (usize, usize);
230
231 /// ***O(1)*** Returns a pointer to the `index`-th element of the split vector of the `fragments`.
232 ///
233 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
234 ///
235 /// # Safety
236 ///
237 /// This method allows to write to a memory which is greater than the split vector's length.
238 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
239 fn get_ptr<T>(&self, fragments: &[Fragment<T>], index: usize) -> Option<*const T> {
240 let (f, i) = self.get_fragment_and_inner_indices_unchecked(index);
241 fragments
242 .get(f)
243 .map(|fragment| unsafe { fragment.as_ptr().add(i) })
244 }
245
246 /// ***O(1)*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`.
247 ///
248 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
249 ///
250 /// # Safety
251 ///
252 /// This method allows to write to a memory which is greater than the split vector's length.
253 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
254 fn get_ptr_mut<T>(&self, fragments: &mut [Fragment<T>], index: usize) -> Option<*mut T> {
255 let (f, i) = self.get_fragment_and_inner_indices_unchecked(index);
256 fragments
257 .get_mut(f)
258 .map(|fragment| unsafe { fragment.as_mut_ptr().add(i) })
259 }
260
261 /// ***O(1)*** Returns a mutable reference to the `index`-th element of the split vector of the `fragments`
262 /// together with the index of the fragment that the element belongs to
263 /// and index of the element withing the respective fragment.
264 ///
265 /// Returns `None` if `index`-th position does not belong to the split vector; i.e., if `index` is out of cumulative capacity of fragments.
266 ///
267 /// # Safety
268 ///
269 /// This method allows to write to a memory which is greater than the split vector's length.
270 /// On the other hand, it will never return a pointer to a memory location that the vector does not own.
271 fn get_ptr_mut_and_indices<T>(
272 &self,
273 fragments: &mut [Fragment<T>],
274 index: usize,
275 ) -> Option<(*mut T, usize, usize)> {
276 let (f, i) = self.get_fragment_and_inner_indices_unchecked(index);
277 fragments
278 .get_mut(f)
279 .map(|fragment| (unsafe { fragment.as_mut_ptr().add(i) }, f, i))
280 }
281
282 /// ***O(1)*** Returns the capacity of the fragment with the given `fragment_index`.
283 fn fragment_capacity_of(&self, fragment_index: usize) -> usize;
284}