opentelemetry_sdk/
growable_array.rs

1/// The default max capacity for the stack portion of `GrowableArray`.
2const DEFAULT_MAX_INLINE_CAPACITY: usize = 10;
3/// The default initial capacity for the vector portion of `GrowableArray`.
4const DEFAULT_INITIAL_OVERFLOW_CAPACITY: usize = 5;
5
6#[derive(Debug, Clone, PartialEq)]
7/// A hybrid vector that starts with a fixed-size array and grows dynamically with a vector.
8///
9/// `GrowableArray` uses an internal fixed-size array (`inline`) for storing elements until it reaches
10/// `MAX_INLINE_CAPACITY`. When this capacity is exceeded, additional elements are stored in a heap-allocated
11/// vector (`overflow`). This structure allows for efficient use of stack memory for small numbers of elements,
12/// while still supporting dynamic growth.
13///
14pub(crate) struct GrowableArray<
15    T: Default + Clone + PartialEq,
16    const MAX_INLINE_CAPACITY: usize = DEFAULT_MAX_INLINE_CAPACITY,
17    const INITIAL_OVERFLOW_CAPACITY: usize = DEFAULT_INITIAL_OVERFLOW_CAPACITY,
18> {
19    inline: [T; MAX_INLINE_CAPACITY],
20    overflow: Option<Vec<T>>,
21    count: usize,
22}
23
24impl<
25        T: Default + Clone + PartialEq,
26        const MAX_INLINE_CAPACITY: usize,
27        const INITIAL_OVERFLOW_CAPACITY: usize,
28    > Default for GrowableArray<T, MAX_INLINE_CAPACITY, INITIAL_OVERFLOW_CAPACITY>
29{
30    fn default() -> Self {
31        Self {
32            inline: [(); MAX_INLINE_CAPACITY].map(|_| T::default()),
33            overflow: None,
34            count: 0,
35        }
36    }
37}
38
39impl<
40        T: Default + Clone + PartialEq,
41        const MAX_INLINE_CAPACITY: usize,
42        const INITIAL_OVERFLOW_CAPACITY: usize,
43    > GrowableArray<T, MAX_INLINE_CAPACITY, INITIAL_OVERFLOW_CAPACITY>
44{
45    /// Creates a new `GrowableArray` with the default initial capacity.
46    #[allow(dead_code)]
47    pub(crate) fn new() -> Self {
48        Self::default()
49    }
50
51    /// Pushes a value into the `GrowableArray`.
52    ///
53    /// If the internal array (`inline`) has reached its capacity (`MAX_INLINE_CAPACITY`), the value is pushed
54    /// into the heap-allocated vector (`overflow`). Otherwise, it is stored in the array.
55    #[allow(dead_code)]
56    #[inline]
57    pub(crate) fn push(&mut self, value: T) {
58        if self.count < MAX_INLINE_CAPACITY {
59            self.inline[self.count] = value;
60            self.count += 1;
61        } else {
62            self.overflow
63                .get_or_insert_with(|| Vec::with_capacity(INITIAL_OVERFLOW_CAPACITY))
64                .push(value);
65        }
66    }
67
68    /// Gets a reference to the value at the specified index.
69    ///
70    /// Returns `None` if the index is out of bounds.
71    #[allow(dead_code)]
72    #[inline]
73    pub(crate) fn get(&self, index: usize) -> Option<&T> {
74        if index < self.count {
75            Some(&self.inline[index])
76        } else if let Some(ref overflow) = self.overflow {
77            overflow.get(index - MAX_INLINE_CAPACITY)
78        } else {
79            None
80        }
81    }
82
83    /// Returns the number of elements in the `GrowableArray`.
84    #[allow(dead_code)]
85    #[inline]
86    pub(crate) fn len(&self) -> usize {
87        self.count + self.overflow.as_ref().map_or(0, Vec::len)
88    }
89
90    /// Returns an iterator over the elements in the `GrowableArray`.
91    ///
92    /// The iterator yields elements from the internal array (`initial`) first, followed by elements
93    /// from the vector (`overflow`) if present. This allows for efficient iteration over both
94    /// stack-allocated and heap-allocated portions.
95    ///
96    #[allow(dead_code)]
97    #[inline]
98    pub(crate) fn iter(&self) -> impl Iterator<Item = &T> {
99        if self.overflow.is_none() || self.overflow.as_ref().unwrap().is_empty() {
100            self.inline.iter().take(self.count).chain([].iter()) // Chaining with an empty array
101                                                                 // so that both `if` and `else` branch return the same type
102        } else {
103            self.inline
104                .iter()
105                .take(self.count)
106                .chain(self.overflow.as_ref().unwrap().iter())
107        }
108    }
109}
110
111// Implement `IntoIterator` for `GrowableArray`
112impl<T: Default + Clone + PartialEq, const INLINE_CAPACITY: usize> IntoIterator
113    for GrowableArray<T, INLINE_CAPACITY>
114{
115    type Item = T;
116    type IntoIter = GrowableArrayIntoIter<T, INLINE_CAPACITY>;
117
118    fn into_iter(self) -> Self::IntoIter {
119        GrowableArrayIntoIter::<T, INLINE_CAPACITY>::new(self)
120    }
121}
122
123/// Iterator for consuming a `GrowableArray`.
124///
125#[derive(Debug)]
126pub(crate) struct GrowableArrayIntoIter<
127    T: Default + Clone + PartialEq,
128    const INLINE_CAPACITY: usize,
129> {
130    iter: std::iter::Chain<
131        std::iter::Take<std::array::IntoIter<T, INLINE_CAPACITY>>,
132        std::vec::IntoIter<T>,
133    >,
134}
135
136impl<T: Default + Clone + PartialEq, const INLINE_CAPACITY: usize>
137    GrowableArrayIntoIter<T, INLINE_CAPACITY>
138{
139    fn new(source: GrowableArray<T, INLINE_CAPACITY>) -> Self {
140        Self {
141            iter: Self::get_iterator(source),
142        }
143    }
144
145    fn get_iterator(
146        source: GrowableArray<T, INLINE_CAPACITY>,
147    ) -> std::iter::Chain<
148        std::iter::Take<std::array::IntoIter<T, INLINE_CAPACITY>>,
149        std::vec::IntoIter<T>,
150    > {
151        if source.overflow.is_none() || source.overflow.as_ref().unwrap().is_empty() {
152            source
153                .inline
154                .into_iter()
155                .take(source.count)
156                .chain(Vec::<T>::new())
157        } else {
158            source
159                .inline
160                .into_iter()
161                .take(source.count)
162                .chain(source.overflow.unwrap())
163        }
164    }
165}
166
167impl<T: Default + Clone + PartialEq, const INITIAL_CAPACITY: usize> Iterator
168    for GrowableArrayIntoIter<T, INITIAL_CAPACITY>
169{
170    type Item = T;
171
172    fn next(&mut self) -> Option<Self::Item> {
173        self.iter.next()
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use crate::growable_array::{
180        GrowableArray, DEFAULT_INITIAL_OVERFLOW_CAPACITY, DEFAULT_MAX_INLINE_CAPACITY,
181    };
182    use opentelemetry::logs::AnyValue;
183    use opentelemetry::Key;
184
185    type KeyValuePair = Option<(Key, AnyValue)>;
186
187    #[test]
188    fn test_push_and_get() {
189        let mut collection = GrowableArray::<i32>::new();
190        for i in 0..15 {
191            collection.push(i);
192        }
193        for i in 0..15 {
194            assert_eq!(collection.get(i), Some(&(i as i32)));
195        }
196    }
197
198    #[test]
199    fn test_len() {
200        let mut collection = GrowableArray::<i32>::new();
201        for i in 0..15 {
202            collection.push(i);
203        }
204        assert_eq!(collection.len(), 15);
205    }
206
207    #[test]
208    fn test_into_iter() {
209        let mut collection = GrowableArray::<i32>::new();
210        for i in 0..15 {
211            collection.push(i);
212        }
213        let mut iter = collection.into_iter();
214        for i in 0..15 {
215            assert_eq!(iter.next(), Some(i));
216        }
217        assert_eq!(iter.next(), None);
218    }
219
220    #[test]
221    fn test_ref_iter() {
222        let mut collection = GrowableArray::<i32>::new();
223        for i in 0..15 {
224            collection.push(i);
225        }
226        let iter = collection.iter();
227        let mut count = 0;
228        for value in iter {
229            assert_eq!(*value, count);
230            count += 1;
231        }
232        assert_eq!(count, 15);
233    }
234
235    #[test]
236    fn test_key_value_pair_storage_growable_array() {
237        let mut collection = GrowableArray::<KeyValuePair>::new();
238
239        let key1 = Key::from("key1");
240        let value1 = AnyValue::String("value1".into());
241        let key2 = Key::from("key2");
242        let value2 = AnyValue::Int(42);
243
244        collection.push(Some((key1.clone(), value1.clone())));
245        collection.push(Some((key2.clone(), value2.clone())));
246
247        assert_eq!(
248            collection
249                .get(0)
250                .and_then(|kv| kv.as_ref().map(|kv| (&kv.0, &kv.1))),
251            Some((&key1, &value1))
252        );
253        assert_eq!(
254            collection
255                .get(1)
256                .and_then(|kv| kv.as_ref().map(|kv| (&kv.0, &kv.1))),
257            Some((&key2, &value2))
258        );
259        assert_eq!(collection.len(), 2);
260
261        // Test iterating over the key-value pairs
262        let mut iter = collection.into_iter();
263        assert_eq!(iter.next(), Some(Some((key1, value1))));
264        assert_eq!(iter.next(), Some(Some((key2, value2))));
265        assert_eq!(iter.next(), None);
266    }
267
268    #[test]
269    fn test_empty_attributes() {
270        let collection = GrowableArray::<KeyValuePair>::new();
271        assert_eq!(collection.len(), 0);
272        assert_eq!(collection.get(0), None);
273
274        let mut iter = collection.into_iter();
275        assert_eq!(iter.next(), None);
276    }
277
278    #[test]
279    fn test_less_than_max_stack_capacity() {
280        let mut collection = GrowableArray::<i32>::new();
281        for i in 0..DEFAULT_MAX_INLINE_CAPACITY - 1 {
282            collection.push(i as i32);
283        }
284        assert_eq!(collection.len(), DEFAULT_MAX_INLINE_CAPACITY - 1);
285
286        for i in 0..DEFAULT_MAX_INLINE_CAPACITY - 1 {
287            assert_eq!(collection.get(i), Some(&(i as i32)));
288        }
289        assert_eq!(collection.get(DEFAULT_MAX_INLINE_CAPACITY - 1), None);
290        assert_eq!(collection.get(DEFAULT_MAX_INLINE_CAPACITY), None);
291
292        let mut iter = collection.into_iter();
293        for i in 0..DEFAULT_MAX_INLINE_CAPACITY - 1 {
294            assert_eq!(iter.next(), Some(i as i32));
295        }
296        assert_eq!(iter.next(), None);
297    }
298
299    #[test]
300    fn test_exactly_max_stack_capacity() {
301        let mut collection = GrowableArray::<i32>::new();
302        for i in 0..DEFAULT_MAX_INLINE_CAPACITY {
303            collection.push(i as i32);
304        }
305        assert_eq!(collection.len(), DEFAULT_MAX_INLINE_CAPACITY);
306
307        for i in 0..DEFAULT_MAX_INLINE_CAPACITY {
308            assert_eq!(collection.get(i), Some(&(i as i32)));
309        }
310        assert_eq!(collection.get(DEFAULT_MAX_INLINE_CAPACITY), None);
311
312        let mut iter = collection.into_iter();
313        for i in 0..DEFAULT_MAX_INLINE_CAPACITY {
314            assert_eq!(iter.next(), Some(i as i32));
315        }
316        assert_eq!(iter.next(), None);
317    }
318
319    #[test]
320    fn test_exceeds_stack_but_not_initial_vec_capacity() {
321        let mut collection = GrowableArray::<i32>::new();
322        for i in 0..(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY - 1) {
323            collection.push(i as i32);
324        }
325        assert_eq!(
326            collection.len(),
327            DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY - 1
328        );
329
330        for i in 0..(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY - 1) {
331            assert_eq!(collection.get(i), Some(&(i as i32)));
332        }
333        assert_eq!(
334            collection.get(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY - 1),
335            None
336        );
337        assert_eq!(
338            collection.get(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY),
339            None
340        );
341
342        let mut iter = collection.into_iter();
343        for i in 0..(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY - 1) {
344            assert_eq!(iter.next(), Some(i as i32));
345        }
346        assert_eq!(iter.next(), None);
347    }
348
349    #[test]
350    fn test_exceeds_both_stack_and_initial_vec_capacities() {
351        let mut collection = GrowableArray::<i32>::new();
352        for i in 0..(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY + 5) {
353            collection.push(i as i32);
354        }
355        assert_eq!(
356            collection.len(),
357            DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY + 5
358        );
359
360        for i in 0..(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY + 5) {
361            assert_eq!(collection.get(i), Some(&(i as i32)));
362        }
363        assert_eq!(
364            collection.get(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY + 5),
365            None
366        );
367
368        let mut iter = collection.into_iter();
369        for i in 0..(DEFAULT_MAX_INLINE_CAPACITY + DEFAULT_INITIAL_OVERFLOW_CAPACITY + 5) {
370            assert_eq!(iter.next(), Some(i as i32));
371        }
372        assert_eq!(iter.next(), None);
373    }
374}
opentelemetry_sdk/growable_array.rs

opentelemetry_sdk/
growable_array.rs
