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

use crate::Fragment;

/// Growth strategy of a split vector.
pub trait Growth: Clone {
    /// Given that the split vector contains the given `fragments`,
    /// returns the capacity of the next fragment.
    fn new_fragment_capacity<T>(&self, fragments: &[Fragment<T>]) -> 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> {
        let mut prev_cumulative_capacity = 0;
        let mut cumulative_capacity = 0;
        for fragment in fragments {
            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));
            }
            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.
    ///
    /// 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,
    ) -> usize {
        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 fragment = Vec::with_capacity(new_capacity).into();
            cloned.push(fragment);

            current_capacity += new_capacity;
            num_fragments += 1;
        }

        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))
    }
}