embed_collections/
various.rs

1//! Various - A small-list optimization container for efficient parameter passing.
2//!
3//! `Various<T>` optimizing for the common case of a single element (use Option initially).
4//! It's storage can be seamless grow when more elements pushed, using [SegList](crate::seg_list),
5//! more efficient for CPU cache-line (compared to LinkedList), and produce less memory fragment (compared to `Vec`).
6//!
7//! # NOTE:
8//!
9//! It does not support random access, only sequential read and write.
10//!
11//! # Example
12//!
13//! ```rust
14//! use embed_collections::various::Various;
15//!
16//! // Create an empty Various
17//! let mut values = Various::new();
18//!
19//! // Push a single element (no allocation)
20//! values.push(42);
21//! assert_eq!(values.len(), 1);
22//! assert_eq!(values.first(), Some(&42));
23//!
24//! // Push more elements (transitions to SegList internally)
25//! values.push(100);
26//! values.push(200);
27//! assert_eq!(values.len(), 3);
28//!
29//! // Iterate over elements
30//! let sum: i32 = values.iter().sum();
31//! assert_eq!(sum, 342);
32//!
33//! // Pop elements from the back
34//! assert_eq!(values.pop(), Some(200));
35//! assert_eq!(values.pop(), Some(100));
36//! assert_eq!(values.pop(), Some(42));
37//! assert_eq!(values.pop(), None);
38//!
39//! // Create from a single value
40//! let single = Various::from("hello");
41//! assert_eq!(single.first(), Some(&"hello"));
42//!
43//! // Efficient for function parameter passing
44//! fn process_items(items: &Various<i32>) -> i32 {
45//!     items.iter().sum()
46//! }
47//!
48//! let items = Various::from(10);
49//! assert_eq!(process_items(&items), 10);
50//! ```
51
52use crate::seg_list::SegList;
53use core::fmt;
54
55pub struct Various<T> {
56    inner: VariousInner<T>,
57}
58
59enum VariousInner<T> {
60    One(Option<T>),
61    More(SegList<T>),
62}
63
64macro_rules! match_iter {
65    ($self: expr, $iter_type: tt, $f: tt $($m: tt)*) =>{
66        match $self.inner {
67            VariousInner::One($($m)* s)=>$iter_type::One(s.$f()),
68            VariousInner::More($($m)* s)=>$iter_type::More(s.$f()),
69        }
70    }
71}
72
73macro_rules! match_call {
74    ($self: expr, $cls: tt, $call: tt) => {
75        match $self {
76            $cls::One(i) => i.$call(),
77            $cls::More(i) => i.$call(),
78        }
79    };
80}
81
82impl<T> Default for Various<T> {
83    fn default() -> Self {
84        Self::new()
85    }
86}
87
88impl<T> Various<T> {
89    #[inline]
90    pub fn new() -> Self {
91        Self { inner: VariousInner::One(None) }
92    }
93
94    #[inline]
95    pub fn from(item: T) -> Self {
96        Self { inner: VariousInner::One(Some(item)) }
97    }
98
99    #[inline]
100    pub fn is_empty(&self) -> bool {
101        match &self.inner {
102            VariousInner::One(i) => i.is_none(),
103            VariousInner::More(i) => i.is_empty(),
104        }
105    }
106
107    #[inline]
108    pub fn len(&self) -> usize {
109        match &self.inner {
110            VariousInner::One(i) => {
111                if i.is_none() {
112                    0
113                } else {
114                    1
115                }
116            }
117            VariousInner::More(i) => i.len(),
118        }
119    }
120
121    /// push element to the tail
122    #[inline]
123    pub fn push(&mut self, new_item: T) {
124        match self.inner {
125            VariousInner::More(ref mut s) => {
126                s.push(new_item);
127            }
128            VariousInner::One(ref mut s) => {
129                if s.is_none() {
130                    s.replace(new_item);
131                } else {
132                    let mut l = SegList::new();
133                    l.push(s.take().unwrap());
134                    l.push(new_item);
135                    self.inner = VariousInner::More(l);
136                }
137            }
138        }
139    }
140
141    /// pop element from the tail
142    #[inline]
143    pub fn pop(&mut self) -> Option<T> {
144        match self.inner {
145            VariousInner::More(ref mut s) => s.pop(),
146            VariousInner::One(ref mut s) => s.take(),
147        }
148    }
149
150    #[inline]
151    pub fn iter<'a>(&'a self) -> VariousIter<'a, T> {
152        match_iter!(self, VariousIter, iter ref)
153    }
154
155    pub fn iter_mut<'a>(&'a mut self) -> VariousIterMut<'a, T> {
156        match_iter!(self, VariousIterMut, iter_mut ref mut)
157    }
158
159    #[inline]
160    pub fn first(&self) -> Option<&T> {
161        match self.inner {
162            VariousInner::One(ref s) => s.as_ref(),
163            VariousInner::More(ref s) => s.iter().next(),
164        }
165    }
166
167    #[inline]
168    pub fn last(&self) -> Option<&T> {
169        match self.inner {
170            VariousInner::More(ref s) => s.last(),
171            VariousInner::One(ref s) => s.as_ref(),
172        }
173    }
174
175    pub fn last_mut(&mut self) -> Option<&mut T> {
176        match self.inner {
177            VariousInner::More(ref mut s) => s.last_mut(),
178            VariousInner::One(ref mut s) => s.as_mut(),
179        }
180    }
181
182    /// Take the content out and leave and empty option inside, freeing inner memory
183    #[inline]
184    pub fn take(&mut self) -> Self {
185        use core::mem;
186        Various { inner: mem::replace(&mut self.inner, VariousInner::One(None)) }
187    }
188
189    /// Clear the content without freeing inner memory
190    #[inline]
191    pub fn clear(&mut self) {
192        match &mut self.inner {
193            VariousInner::One(inner) => {
194                let _ = inner.take();
195            }
196            VariousInner::More(inner) => inner.clear(),
197        }
198    }
199}
200
201impl<T> IntoIterator for Various<T> {
202    type Item = T;
203
204    type IntoIter = VariousIntoIter<T>;
205
206    fn into_iter(self) -> VariousIntoIter<T> {
207        match_iter!(self, VariousIntoIter, into_iter)
208    }
209}
210
211impl<'a, T> IntoIterator for &'a Various<T> {
212    type Item = &'a T;
213
214    type IntoIter = VariousIter<'a, T>;
215
216    fn into_iter(self) -> VariousIter<'a, T> {
217        match_iter!(self, VariousIter, iter ref)
218    }
219}
220
221pub enum VariousIter<'a, T> {
222    One(core::option::Iter<'a, T>),
223    More(crate::seg_list::SegListIter<'a, T>),
224}
225
226impl<'a, T> core::iter::Iterator for VariousIter<'a, T> {
227    type Item = &'a T;
228
229    fn next(&mut self) -> Option<Self::Item> {
230        match_call!(self, VariousIter, next)
231    }
232}
233
234pub enum VariousIterMut<'a, T> {
235    One(core::option::IterMut<'a, T>),
236    More(crate::seg_list::SegListIterMut<'a, T>),
237}
238
239impl<'a, T> core::iter::Iterator for VariousIterMut<'a, T> {
240    type Item = &'a mut T;
241
242    fn next(&mut self) -> Option<Self::Item> {
243        match_call!(self, VariousIterMut, next)
244    }
245}
246
247pub enum VariousIntoIter<T> {
248    One(core::option::IntoIter<T>),
249    More(crate::seg_list::SegListDrain<T>),
250}
251
252impl<T> core::iter::Iterator for VariousIntoIter<T> {
253    type Item = T;
254
255    fn next(&mut self) -> Option<Self::Item> {
256        match_call!(self, VariousIntoIter, next)
257    }
258}
259
260impl<T: fmt::Debug> fmt::Debug for Various<T> {
261    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
262        match &self.inner {
263            VariousInner::One(s) => s.fmt(f),
264            VariousInner::More(s) => s.fmt(f),
265        }
266    }
267}
268
269#[cfg(test)]
270mod tests {
271
272    use super::*;
273
274    #[test]
275    fn test_one() {
276        let mut s = Various::new();
277        s.push(1);
278        assert_eq!(s.len(), 1);
279        for i in &s {
280            assert_eq!(*i, 1);
281        }
282        assert_eq!(Some(1), s.pop());
283        assert_eq!(s.len(), 0);
284        if (&s).into_iter().next().is_some() {
285            unreachable!();
286        }
287    }
288
289    #[test]
290    fn test_cap_0() {
291        let mut s = Various::new();
292        s.push(1);
293        assert_eq!(s.len(), 1);
294        for i in &s {
295            assert_eq!(*i, 1);
296        }
297        s.push(2);
298        s.push(3);
299        assert_eq!(s.len(), 3);
300        let mut total = 0;
301        for i in &s {
302            total += *i;
303        }
304        assert_eq!(total, 6);
305        for i in s.iter_mut() {
306            *i += 1;
307        }
308        let mut total = 0;
309        for i in &s {
310            total += *i;
311        }
312        assert_eq!(total, 9);
313        assert_eq!(s.pop(), Some(4));
314        let mut total = 0;
315        for i in s {
316            total += i;
317        }
318        assert_eq!(total, 5);
319    }
320
321    #[test]
322    fn test_more() {
323        let mut s = Various::new();
324        s.push(1);
325        s.push(2);
326        s.push(3);
327        assert_eq!(s.len(), 3);
328        let mut total = 0;
329        for i in &s {
330            total += *i;
331        }
332        assert_eq!(total, 6);
333        for i in s.iter_mut() {
334            *i += 1;
335        }
336        let mut total = 0;
337        for i in &s {
338            total += *i;
339        }
340        assert_eq!(total, 9);
341        assert_eq!(s.pop(), Some(4));
342        let mut total = 0;
343        for i in s {
344            total += i;
345        }
346        assert_eq!(total, 5);
347    }
348}
embed_collections/various.rs

embed_collections/
various.rs
