evobench_tools/utillib/
micro_vec.rs

1//! A vector type that is optimized for storing 0 or 1 elements
2//!
3//! Currently `size_of::<MicroVec<T>>()` is at least 2 machine
4//! words. Could optimize via tagged-pointer-as-enum, tagged-pointer,
5//! enum-ptr, tagged-box crates.
6
7/// A vector that is optimized for storing 0 or 1 elements. >1
8/// elements are stored in a normal Vec, slowly.
9#[derive(Debug, PartialEq, Eq)]
10pub enum MicroVec<T> {
11    None,
12    One(T),
13    More(Box<Vec<T>>),
14}
15
16impl<T> Default for MicroVec<T> {
17    #[inline]
18    fn default() -> Self {
19        MicroVec::new()
20    }
21}
22
23impl<T, const N: usize> From<[T; N]> for MicroVec<T> {
24    fn from(values: [T; N]) -> Self {
25        let mut vec = MicroVec::new();
26        for v in values {
27            vec.push(v);
28        }
29        vec
30    }
31}
32
33impl<T: Clone> From<&[T]> for MicroVec<T> {
34    fn from(values: &[T]) -> Self {
35        let mut vec = MicroVec::new();
36        for v in values {
37            vec.push(v.clone());
38        }
39        vec
40    }
41}
42
43impl<T> MicroVec<T> {
44    #[inline]
45    pub fn new() -> Self {
46        Self::None
47    }
48
49    pub fn len(&self) -> usize {
50        match self {
51            MicroVec::None => 0,
52            MicroVec::One(_) => 1,
53            MicroVec::More(items) => items.len(),
54        }
55    }
56
57    pub fn push(&mut self, val: T) {
58        match self {
59            MicroVec::None => {
60                *self = MicroVec::One(val);
61            }
62            MicroVec::One(_) => {
63                let mut removed = MicroVec::None;
64                std::mem::swap(self, &mut removed);
65                match removed {
66                    MicroVec::One(v0) => {
67                        *self = MicroVec::More(vec![v0, val].into());
68                    }
69                    _ => unreachable!(),
70                }
71            }
72            MicroVec::More(items) => {
73                items.push(val);
74            }
75        }
76    }
77}
78
79/// Construct a `MicroVec` from a list of expressions (no support for
80/// `[val; N]`)
81#[macro_export]
82macro_rules! microvec {
83    [] => {
84        $crate::utillib::micro_vec::MicroVec::None
85    };
86    [ $v:expr ] => {
87        $crate::utillib::micro_vec::MicroVec::One($v)
88    };
89    [ $($e:tt)* ] => {
90        {
91            let mut vec = $crate::utillib::micro_vec::MicroVec::None;
92            for v in [$($e)*] {
93                vec.push(v);
94            }
95            vec
96        }
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn t_1() {
106        let mut vec: MicroVec<u32> = Default::default();
107
108        // A little disappointing but not caring about this now
109        assert_eq!(size_of_val(&vec), 16);
110
111        assert_eq!(vec.len(), 0);
112        assert_eq!(&microvec![], &vec);
113
114        vec.push(123);
115        assert_eq!(vec.len(), 1);
116        assert_eq!(&microvec![123], &vec);
117
118        vec.push(124);
119        assert_eq!(vec.len(), 2);
120
121        assert_eq!(&microvec![123, 124], &vec);
122    }
123}
evobench_tools/utillib/micro_vec.rs

evobench_tools/utillib/
micro_vec.rs
