orx_split_vec/fragment/
fragment_struct.rs

1use alloc::vec::Vec;
2use core::cmp::Ordering;
3use core::ops::{
4    Index, IndexMut, Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive,
5};
6
7const ZST_VEC_CAPACITY: usize = 4;
8
9/// A contiguous fragment of the split vector.
10///
11/// Suppose a split vector contains 10 integers from 0 to 9.
12/// Depending on the growth strategy of the split vector,
13/// this data might be stored in 3 contiguous fragments,
14/// say [0, 1, 2, 3], [4, 5, 6, 7] and [8, 9].
15#[derive(Default)]
16pub struct Fragment<T> {
17    data: Vec<T>,
18    capacity: usize,
19}
20
21impl<T> Fragment<T> {
22    /// Returns the effective capacity of a vector, normalizing zero-sized types.
23    pub(crate) fn capacity_of_vec(vec: &Vec<T>) -> usize {
24        match core::mem::size_of::<T>() == 0 {
25            true => ZST_VEC_CAPACITY,
26            false => vec.capacity(),
27        }
28    }
29
30    /// Creates a fragment from `data` with the target logical `capacity`.
31    pub fn new(capacity: usize, mut data: Vec<T>) -> Self {
32        match core::mem::size_of::<T>() == 0 {
33            true => Self { data, capacity },
34            false => {
35                if data.capacity() < capacity {
36                    data.reserve(capacity - data.capacity());
37                }
38                Self { data, capacity }
39            }
40        }
41    }
42
43    /// Creates a new fragment with the given `capacity`.
44    pub fn new_empty(capacity: usize) -> Self {
45        Self {
46            data: Vec::with_capacity(capacity),
47            capacity,
48        }
49    }
50
51    /// Consumes the fragment and returns the inner vector.
52    pub fn into_inner(self) -> Vec<T> {
53        self.data
54    }
55
56    /// Returns whether the fragment has room to push a new item or not.
57    pub fn has_capacity_for_one(&self) -> bool {
58        self.data.len() < self.capacity
59    }
60
61    /// Returns the available capacity in the fragment.
62    pub fn room(&self) -> usize {
63        self.capacity - self.data.len()
64    }
65
66    // helpers
67    pub(crate) fn fragments_with_default_capacity() -> Vec<Fragment<T>> {
68        Vec::new()
69    }
70
71    pub(crate) fn into_fragments(self) -> Vec<Fragment<T>> {
72        let mut fragments = Self::fragments_with_default_capacity();
73        fragments.push(self);
74        fragments
75    }
76
77    pub(crate) fn fragments_with_capacity(fragments_capacity: usize) -> Vec<Fragment<T>> {
78        Vec::with_capacity(fragments_capacity)
79    }
80
81    pub(crate) fn into_fragments_with_capacity(
82        self,
83        fragments_capacity: usize,
84    ) -> Vec<Fragment<T>> {
85        let mut fragments = Self::fragments_with_capacity(fragments_capacity);
86        fragments.push(self);
87        fragments
88    }
89
90    /// Zeroes out all memory; i.e., positions in `0..fragment.capacity()`, of the fragment.
91    #[inline(always)]
92    pub(crate) unsafe fn zero(&mut self) {
93        let slice =
94            unsafe { core::slice::from_raw_parts_mut(self.data.as_mut_ptr(), self.capacity()) };
95        slice
96            .iter_mut()
97            .for_each(|m| *m = unsafe { core::mem::zeroed() });
98    }
99
100    // exposed vec methods
101
102    /// Returns the number of initialized elements in the fragment.
103    #[inline(always)]
104    pub fn len(&self) -> usize {
105        self.data.len()
106    }
107
108    /// Returns `true` if the fragment contains no elements.
109    #[inline(always)]
110    pub fn is_empty(&self) -> bool {
111        self.data.is_empty()
112    }
113
114    /// Returns the logical capacity of the fragment.
115    #[inline(always)]
116    pub fn capacity(&self) -> usize {
117        self.capacity
118    }
119
120    /// Returns a shared slice view of initialized elements.
121    pub fn as_slice(&self) -> &[T] {
122        &self.data
123    }
124
125    /// Returns a raw pointer to the fragment's initialized elements.
126    #[inline(always)]
127    pub fn as_ptr(&self) -> *const T {
128        self.data.as_ptr()
129    }
130
131    /// Binary-searches initialized elements with a comparator.
132    pub fn binary_search_by<F>(&self, f: F) -> Result<usize, usize>
133    where
134        F: FnMut(&T) -> Ordering,
135    {
136        self.data.binary_search_by(f)
137    }
138
139    /// Returns an iterator over initialized elements.
140    pub fn iter(&self) -> core::slice::Iter<'_, T> {
141        self.data.iter()
142    }
143
144    /// Returns the last initialized element, if any.
145    #[inline(always)]
146    pub fn last(&self) -> Option<&T> {
147        self.data.last()
148    }
149
150    /// Returns the first initialized element, if any.
151    #[inline(always)]
152    pub fn first(&self) -> Option<&T> {
153        self.data.first()
154    }
155
156    /// Returns a shared reference to the element at `index`, if present.
157    #[inline(always)]
158    pub fn get(&self, index: usize) -> Option<&T> {
159        self.data.get(index)
160    }
161
162    /// Returns a shared reference to the element at `index` without bounds checks.
163    ///
164    /// # Safety
165    ///
166    /// Caller must ensure `index < self.len()`.
167    #[inline(always)]
168    pub unsafe fn get_unchecked(&self, index: usize) -> &T {
169        unsafe { self.data.get_unchecked(index) }
170    }
171
172    // exposed vec mut methods
173
174    /// Appends an element to the end of initialized region.
175    #[inline(always)]
176    pub fn push(&mut self, value: T) {
177        self.data.push(value);
178    }
179
180    /// Sets the initialized length of the fragment.
181    ///
182    /// # Safety
183    ///
184    /// Caller must uphold `Vec::set_len` invariants.
185    pub unsafe fn set_len(&mut self, new_len: usize) {
186        unsafe { self.data.set_len(new_len) };
187    }
188
189    /// # SAFETY
190    ///
191    /// Obtained reference to the vector can be used to change the length of the vector
192    /// by adding or removing elements; however, it must not change the capacity and
193    /// underlying allocation of the vector.
194    pub unsafe fn as_mut_vec(&mut self) -> &mut Vec<T> {
195        &mut self.data
196    }
197
198    /// Returns a mutable raw pointer to initialized elements.
199    #[inline(always)]
200    pub fn as_mut_ptr(&mut self) -> *mut T {
201        self.data.as_mut_ptr()
202    }
203
204    /// Clones and appends all elements from `slice`.
205    pub fn extend_from_slice(&mut self, slice: &[T])
206    where
207        T: Clone,
208    {
209        self.data.extend_from_slice(slice);
210    }
211
212    /// Returns a mutable reference to the element at `index` without bounds checks.
213    ///
214    /// # Safety
215    ///
216    /// Caller must ensure `index < self.len()` and aliasing rules are respected.
217    #[inline(always)]
218    pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
219        unsafe { self.data.get_unchecked_mut(index) }
220    }
221
222    /// Removes and returns the last element, if any.
223    #[inline(always)]
224    pub fn pop(&mut self) -> Option<T> {
225        self.data.pop()
226    }
227
228    /// Inserts `element` at `index`, shifting later elements to the right.
229    #[inline(always)]
230    pub fn insert(&mut self, index: usize, element: T) {
231        self.data.insert(index, element);
232    }
233
234    /// Removes and returns the element at `index`, shifting later elements left.
235    #[inline(always)]
236    pub fn remove(&mut self, index: usize) -> T {
237        self.data.remove(index)
238    }
239
240    /// Removes all initialized elements from the fragment.
241    pub fn clear(&mut self) {
242        self.data.clear();
243    }
244
245    /// Truncates the initialized length to at most `len`.
246    pub fn truncate(&mut self, len: usize) {
247        self.data.truncate(len);
248    }
249
250    /// Swaps two initialized elements.
251    #[inline(always)]
252    pub fn swap(&mut self, a: usize, b: usize) {
253        self.data.swap(a, b);
254    }
255
256    /// Returns a mutable iterator over initialized elements.
257    pub fn iter_mut(&mut self) -> core::slice::IterMut<'_, T> {
258        self.data.iter_mut()
259    }
260
261    /// Sorts initialized elements with the given comparator.
262    pub fn sort_by<F>(&mut self, compare: F)
263    where
264        F: FnMut(&T, &T) -> Ordering,
265    {
266        self.data.sort_by(compare);
267    }
268}
269
270pub(crate) unsafe fn set_fragments_len<T>(fragments: &mut [Fragment<T>], len: usize) {
271    let mut remaining = len;
272
273    for fragment in fragments {
274        let capacity = fragment.capacity();
275
276        match remaining <= capacity {
277            true => {
278                unsafe { fragment.set_len(remaining) };
279                remaining = 0;
280            }
281            false => {
282                unsafe { fragment.set_len(capacity) };
283                remaining -= capacity;
284            }
285        }
286    }
287}
288
289impl<T> IntoIterator for Fragment<T> {
290    type Item = T;
291
292    type IntoIter = alloc::vec::IntoIter<T>;
293
294    fn into_iter(self) -> Self::IntoIter {
295        self.data.into_iter()
296    }
297}
298
299impl<T> Index<usize> for Fragment<T> {
300    type Output = T;
301
302    #[inline(always)]
303    fn index(&self, index: usize) -> &Self::Output {
304        &self.data[index]
305    }
306}
307
308impl<T> IndexMut<usize> for Fragment<T> {
309    #[inline(always)]
310    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
311        &mut self.data[index]
312    }
313}
314
315impl<T> Index<Range<usize>> for Fragment<T> {
316    type Output = [T];
317
318    #[inline(always)]
319    fn index(&self, index: Range<usize>) -> &Self::Output {
320        &self.data[index]
321    }
322}
323
324impl<T> IndexMut<Range<usize>> for Fragment<T> {
325    #[inline(always)]
326    fn index_mut(&mut self, index: Range<usize>) -> &mut Self::Output {
327        &mut self.data[index]
328    }
329}
330
331impl<T> Index<RangeFrom<usize>> for Fragment<T> {
332    type Output = [T];
333
334    #[inline(always)]
335    fn index(&self, index: RangeFrom<usize>) -> &Self::Output {
336        &self.data[index]
337    }
338}
339
340impl<T> IndexMut<RangeFrom<usize>> for Fragment<T> {
341    #[inline(always)]
342    fn index_mut(&mut self, index: RangeFrom<usize>) -> &mut Self::Output {
343        &mut self.data[index]
344    }
345}
346
347impl<T> Index<RangeTo<usize>> for Fragment<T> {
348    type Output = [T];
349
350    #[inline(always)]
351    fn index(&self, index: RangeTo<usize>) -> &Self::Output {
352        &self.data[index]
353    }
354}
355
356impl<T> IndexMut<RangeTo<usize>> for Fragment<T> {
357    #[inline(always)]
358    fn index_mut(&mut self, index: RangeTo<usize>) -> &mut Self::Output {
359        &mut self.data[index]
360    }
361}
362
363impl<T> Index<RangeInclusive<usize>> for Fragment<T> {
364    type Output = [T];
365
366    #[inline(always)]
367    fn index(&self, index: RangeInclusive<usize>) -> &Self::Output {
368        &self.data[index]
369    }
370}
371
372impl<T> IndexMut<RangeInclusive<usize>> for Fragment<T> {
373    #[inline(always)]
374    fn index_mut(&mut self, index: RangeInclusive<usize>) -> &mut Self::Output {
375        &mut self.data[index]
376    }
377}
378
379impl<T> Index<RangeToInclusive<usize>> for Fragment<T> {
380    type Output = [T];
381
382    #[inline(always)]
383    fn index(&self, index: RangeToInclusive<usize>) -> &Self::Output {
384        &self.data[index]
385    }
386}
387
388impl<T> IndexMut<RangeToInclusive<usize>> for Fragment<T> {
389    #[inline(always)]
390    fn index_mut(&mut self, index: RangeToInclusive<usize>) -> &mut Self::Output {
391        &mut self.data[index]
392    }
393}
394
395impl<T> Index<RangeFull> for Fragment<T> {
396    type Output = [T];
397
398    #[inline(always)]
399    fn index(&self, index: RangeFull) -> &Self::Output {
400        &self.data[index]
401    }
402}
403
404impl<T> IndexMut<RangeFull> for Fragment<T> {
405    #[inline(always)]
406    fn index_mut(&mut self, index: RangeFull) -> &mut Self::Output {
407        &mut self.data[index]
408    }
409}
410
411#[cfg(test)]
412mod tests {
413    use super::*;
414
415    #[test]
416    fn zeroed() {
417        let mut fragment: Fragment<i32> = Fragment::new_empty(4);
418        unsafe { fragment.zero() };
419        unsafe { fragment.set_len(4) };
420        let zero: i32 = unsafe { core::mem::zeroed() };
421        for i in 0..4 {
422            assert_eq!(fragment.get(i), Some(&zero));
423        }
424    }
425}
orx_split_vec/fragment/fragment_struct.rs

orx_split_vec/fragment/
fragment_struct.rs
