1 // Copyright © 2022 Collabora, Ltd. 2 // SPDX-License-Identifier: MIT 3 4 /// `SmallVec` is an optimized data structure that handles collections of items. 5 /// It is designed to avoid allocating a `Vec` unless multiple items are present. 6 /// 7 /// # Variants 8 /// 9 /// * `None` - Represents an empty collection, no items are stored. 10 /// * `One(T)` - Stores a single item without allocating a `Vec`. 11 /// * `Many(Vec<T>)` - Stores multiple items in a heap-allocated `Vec`. 12 /// 13 /// This helps to reduce the amount of Vec's allocated in the optimization passes. 14 pub enum SmallVec<T> { 15 None, 16 One(T), 17 Many(Vec<T>), 18 } 19 20 impl<T> SmallVec<T> { 21 /// Adds an item to the `SmallVec`. 22 /// 23 /// If the collection is empty (`None`), the item is stored as `One`. 24 /// If the collection has one item (`One`), it transitions to `Many` and both items are stored in a `Vec`. 25 /// If the collection is already in the `Many` variant, the new item is pushed into the existing `Vec`. 26 /// 27 /// # Arguments 28 /// 29 /// * `item` - The item to be added. 30 /// 31 /// # Example 32 /// 33 /// ``` 34 /// let mut vec: SmallVec<String> = SmallVec::None; 35 /// vec.push("Hello".to_string()); 36 /// vec.push("World".to_string()); 37 /// ``` push(&mut self, i: T)38 pub fn push(&mut self, i: T) { 39 match self { 40 SmallVec::None => { 41 *self = SmallVec::One(i); 42 } 43 SmallVec::One(_) => { 44 *self = match std::mem::replace(self, SmallVec::None) { 45 SmallVec::One(o) => SmallVec::Many(vec![o, i]), 46 _ => panic!("Not a One"), 47 }; 48 } 49 SmallVec::Many(v) => { 50 v.push(i); 51 } 52 } 53 } 54 55 /// Returns a mutable reference to the last item in the `SmallVec`, if it exists. 56 /// 57 /// * If the collection is empty (`None`), it returns `None`. 58 /// * If the collection has one item (`One`), it returns a mutable reference to that item. 59 /// * If the collection has multiple items (`Many`), it returns a mutable reference to the last item in the `Vec`. 60 /// 61 /// # Returns 62 /// 63 /// * `Option<&mut T>` - A mutable reference to the last item, or `None` if the collection is empty. 64 /// 65 /// # Example 66 /// 67 /// ``` 68 /// let mut vec: SmallVec<i32> = SmallVec::None; 69 /// vec.push(1); 70 /// vec.push(2); 71 /// 72 /// if let Some(last) = vec.last_mut() { 73 /// *last = 10; // Modify the last element. 74 /// } 75 /// ``` last_mut(&mut self) -> Option<&mut T>76 pub fn last_mut(&mut self) -> Option<&mut T> { 77 match self { 78 SmallVec::None => None, 79 SmallVec::One(item) => Some(item), 80 SmallVec::Many(v) => v.last_mut(), 81 } 82 } 83 } 84