icu_locale_core/shortvec/
mod.rs

Help
1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5//! This module includes variable-length data types that are const-constructible for single
6//! values and overflow to the heap.
7//!
8//! # Why?
9//!
10//! This module is far from the first stack-or-heap vector in the Rust ecosystem. It was created
11//! with the following value proposition:
12//!
13//! 1. Enable safe const construction of stack collections.
14//! 2. Avoid stack size penalties common with stack-or-heap collections.
15//!
16//! As of this writing, `heapless` and `tinyvec` don't support const construction except
17//! for empty vectors, and `smallvec` supports it on unstable.
18//!
19//! Additionally, [`ShortBoxSlice`] has a smaller stack size than any of these:
20//!
21//! ```ignore
22//! use core::mem::size_of;
23//!
24//! // NonZeroU64 has a niche that this module utilizes
25//! use core::num::NonZeroU64;
26//!
27//! // ShortBoxSlice is the same size as `Box<[]>` for small or nichey values
28//! assert_eq!(16, size_of::<shortvec::ShortBoxSlice::<NonZeroU64>>());
29//!
30//! // Note: SmallVec supports pushing and therefore has a capacity field
31//! assert_eq!(24, size_of::<smallvec::SmallVec::<[NonZeroU64; 1]>>());
32//!
33//! // Note: heapless doesn't support spilling to the heap
34//! assert_eq!(16, size_of::<heapless::Vec::<NonZeroU64, 1>>());
35//!
36//! // Note: TinyVec only supports types that implement `Default`
37//! assert_eq!(24, size_of::<tinyvec::TinyVec::<[u64; 1]>>());
38//! ```
39//!
40//! The module is `no_std` with `alloc`.
41
42mod litemap;
43
44#[cfg(feature = "alloc")]
45use alloc::boxed::Box;
46#[cfg(feature = "alloc")]
47use alloc::vec;
48#[cfg(feature = "alloc")]
49use alloc::vec::Vec;
50use core::ops::Deref;
51use core::ops::DerefMut;
52
53/// A boxed slice that supports no-allocation, constant values if length 0 or 1.
54/// Using ZeroOne(Option<T>) saves 8 bytes in ShortBoxSlice via niche optimization.
55#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
56pub(crate) enum ShortBoxSliceInner<T> {
57    ZeroOne(Option<T>),
58    #[cfg(feature = "alloc")]
59    Multi(Box<[T]>),
60}
61
62impl<T> Default for ShortBoxSliceInner<T> {
63    fn default() -> Self {
64        use ShortBoxSliceInner::*;
65        ZeroOne(None)
66    }
67}
68
69/// A boxed slice that supports no-allocation, constant values if length 0 or 1.
70///
71/// Supports mutation but always reallocs when mutated.
72#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
73pub(crate) struct ShortBoxSlice<T>(ShortBoxSliceInner<T>);
74
75impl<T> Default for ShortBoxSlice<T> {
76    fn default() -> Self {
77        Self(Default::default())
78    }
79}
80
81impl<T> ShortBoxSlice<T> {
82    /// Creates a new, empty [`ShortBoxSlice`].
83    #[inline]
84    pub const fn new() -> Self {
85        use ShortBoxSliceInner::*;
86        Self(ZeroOne(None))
87    }
88
89    /// Creates a new [`ShortBoxSlice`] containing a single element.
90    #[inline]
91    pub const fn new_single(item: T) -> Self {
92        use ShortBoxSliceInner::*;
93        Self(ZeroOne(Some(item)))
94    }
95
96    /// Pushes an element onto this [`ShortBoxSlice`].
97    ///
98    /// Reallocs if more than 1 item is already in the collection.
99    #[cfg(feature = "alloc")]
100    pub fn push(&mut self, item: T) {
101        use ShortBoxSliceInner::*;
102        self.0 = match core::mem::replace(&mut self.0, ZeroOne(None)) {
103            ZeroOne(None) => ZeroOne(Some(item)),
104            ZeroOne(Some(prev_item)) => Multi(vec![prev_item, item].into_boxed_slice()),
105            Multi(items) => {
106                let mut items = items.into_vec();
107                items.push(item);
108                Multi(items.into_boxed_slice())
109            }
110        };
111    }
112
113    /// Gets a single element from the [`ShortBoxSlice`].
114    ///
115    /// Returns `None` if empty or more than one element.
116    #[inline]
117    pub const fn single(&self) -> Option<&T> {
118        use ShortBoxSliceInner::*;
119        match self.0 {
120            ZeroOne(Some(ref v)) => Some(v),
121            _ => None,
122        }
123    }
124
125    /// Destruct into a single element of the [`ShortBoxSlice`].
126    ///
127    /// Returns `None` if empty or more than one element.
128    pub fn into_single(self) -> Option<T> {
129        use ShortBoxSliceInner::*;
130        match self.0 {
131            ZeroOne(Some(v)) => Some(v),
132            _ => None,
133        }
134    }
135
136    /// Returns the number of elements in the collection.
137    #[inline]
138    pub fn len(&self) -> usize {
139        use ShortBoxSliceInner::*;
140        match self.0 {
141            ZeroOne(None) => 0,
142            ZeroOne(_) => 1,
143            #[cfg(feature = "alloc")]
144            Multi(ref v) => v.len(),
145        }
146    }
147
148    /// Returns whether the collection is empty.
149    #[inline]
150    pub const fn is_empty(&self) -> bool {
151        use ShortBoxSliceInner::*;
152        matches!(self.0, ZeroOne(None))
153    }
154
155    /// Inserts an element at the specified index into the collection.
156    ///
157    /// Reallocs if more than 1 item is already in the collection.
158    #[cfg(feature = "alloc")]
159    pub fn insert(&mut self, index: usize, elt: T) {
160        use ShortBoxSliceInner::*;
161        assert!(
162            index <= self.len(),
163            "insertion index (is {}) should be <= len (is {})",
164            index,
165            self.len()
166        );
167
168        self.0 = match core::mem::replace(&mut self.0, ZeroOne(None)) {
169            ZeroOne(None) => ZeroOne(Some(elt)),
170            ZeroOne(Some(item)) => {
171                let items = if index == 0 {
172                    vec![elt, item].into_boxed_slice()
173                } else {
174                    vec![item, elt].into_boxed_slice()
175                };
176                Multi(items)
177            }
178            Multi(items) => {
179                let mut items = items.into_vec();
180                items.insert(index, elt);
181                Multi(items.into_boxed_slice())
182            }
183        }
184    }
185
186    /// Removes the element at the specified index from the collection.
187    ///
188    /// Reallocs if more than 2 items are in the collection.
189    pub fn remove(&mut self, index: usize) -> T {
190        use ShortBoxSliceInner::*;
191        assert!(
192            index < self.len(),
193            "removal index (is {}) should be < len (is {})",
194            index,
195            self.len()
196        );
197
198        let (replaced, removed_item) = match core::mem::replace(&mut self.0, ZeroOne(None)) {
199            ZeroOne(None) => unreachable!(),
200            ZeroOne(Some(v)) => (ZeroOne(None), v),
201            #[cfg(feature = "alloc")]
202            Multi(v) => {
203                let mut v = v.into_vec();
204                let removed_item = v.remove(index);
205                match v.len() {
206                    #[allow(clippy::unwrap_used)]
207                    // we know that the vec has exactly one element left
208                    1 => (ZeroOne(Some(v.pop().unwrap())), removed_item),
209                    // v has at least 2 elements, create a Multi variant
210                    _ => (Multi(v.into_boxed_slice()), removed_item),
211                }
212            }
213        };
214        self.0 = replaced;
215        removed_item
216    }
217
218    /// Removes all elements from the collection.
219    #[inline]
220    pub fn clear(&mut self) {
221        use ShortBoxSliceInner::*;
222        let _ = core::mem::replace(&mut self.0, ZeroOne(None));
223    }
224
225    /// Retains only the elements specified by the predicate.
226    #[allow(dead_code)]
227    pub fn retain<F>(&mut self, mut f: F)
228    where
229        F: FnMut(&T) -> bool,
230    {
231        use ShortBoxSliceInner::*;
232        match core::mem::take(&mut self.0) {
233            ZeroOne(Some(one)) if f(&one) => self.0 = ZeroOne(Some(one)),
234            ZeroOne(_) => self.0 = ZeroOne(None),
235            #[cfg(feature = "alloc")]
236            Multi(slice) => {
237                let mut vec = slice.into_vec();
238                vec.retain(f);
239                *self = ShortBoxSlice::from(vec)
240            }
241        };
242    }
243}
244
245impl<T> Deref for ShortBoxSlice<T> {
246    type Target = [T];
247
248    fn deref(&self) -> &Self::Target {
249        use ShortBoxSliceInner::*;
250        match self.0 {
251            ZeroOne(None) => &[],
252            ZeroOne(Some(ref v)) => core::slice::from_ref(v),
253            #[cfg(feature = "alloc")]
254            Multi(ref v) => v,
255        }
256    }
257}
258
259impl<T> DerefMut for ShortBoxSlice<T> {
260    fn deref_mut(&mut self) -> &mut Self::Target {
261        use ShortBoxSliceInner::*;
262        match self.0 {
263            ZeroOne(None) => &mut [],
264            ZeroOne(Some(ref mut v)) => core::slice::from_mut(v),
265            #[cfg(feature = "alloc")]
266            Multi(ref mut v) => v,
267        }
268    }
269}
270
271#[cfg(feature = "alloc")]
272impl<T> From<Vec<T>> for ShortBoxSlice<T> {
273    fn from(v: Vec<T>) -> Self {
274        use ShortBoxSliceInner::*;
275        match v.len() {
276            0 => Self(ZeroOne(None)),
277            #[allow(clippy::unwrap_used)] // we know that the vec is not empty
278            1 => Self(ZeroOne(Some(v.into_iter().next().unwrap()))),
279            _ => Self(Multi(v.into_boxed_slice())),
280        }
281    }
282}
283
284#[cfg(feature = "alloc")]
285impl<T> FromIterator<T> for ShortBoxSlice<T> {
286    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
287        use ShortBoxSliceInner::*;
288        let mut iter = iter.into_iter();
289        match (iter.next(), iter.next()) {
290            (Some(first), Some(second)) => {
291                // Size hint behaviour same as `Vec::extend` + 2
292                let mut vec = Vec::with_capacity(iter.size_hint().0.saturating_add(3));
293                vec.push(first);
294                vec.push(second);
295                vec.extend(iter);
296                Self(Multi(vec.into_boxed_slice()))
297            }
298            (first, _) => Self(ZeroOne(first)),
299        }
300    }
301}
302
303/// An iterator that yields elements from a [`ShortBoxSlice`].
304#[derive(Debug)]
305pub struct ShortBoxSliceIntoIter<T>(ShortBoxSliceIntoIterInner<T>);
306
307#[derive(Debug)]
308pub(crate) enum ShortBoxSliceIntoIterInner<T> {
309    ZeroOne(Option<T>),
310    #[cfg(feature = "alloc")]
311    Multi(alloc::vec::IntoIter<T>),
312}
313
314impl<T> Iterator for ShortBoxSliceIntoIter<T> {
315    type Item = T;
316    fn next(&mut self) -> Option<T> {
317        use ShortBoxSliceIntoIterInner::*;
318        match &mut self.0 {
319            ZeroOne(option) => option.take(),
320            #[cfg(feature = "alloc")]
321            Multi(into_iter) => into_iter.next(),
322        }
323    }
324}
325
326impl<T> IntoIterator for ShortBoxSlice<T> {
327    type Item = T;
328    type IntoIter = ShortBoxSliceIntoIter<T>;
329
330    fn into_iter(self) -> Self::IntoIter {
331        match self.0 {
332            ShortBoxSliceInner::ZeroOne(option) => {
333                ShortBoxSliceIntoIter(ShortBoxSliceIntoIterInner::ZeroOne(option))
334            }
335            // TODO: Use a boxed slice IntoIter impl when available:
336            // <https://github.com/rust-lang/rust/issues/59878>
337            #[cfg(feature = "alloc")]
338            ShortBoxSliceInner::Multi(boxed_slice) => ShortBoxSliceIntoIter(
339                ShortBoxSliceIntoIterInner::Multi(boxed_slice.into_vec().into_iter()),
340            ),
341        }
342    }
343}
344
345#[cfg(test)]
346mod tests {
347    use super::*;
348
349    #[test]
350    #[allow(clippy::get_first)]
351    fn test_new_single_const() {
352        const MY_CONST_SLICE: ShortBoxSlice<i32> = ShortBoxSlice::new_single(42);
353
354        assert_eq!(MY_CONST_SLICE.len(), 1);
355        assert_eq!(MY_CONST_SLICE.get(0), Some(&42));
356    }
357
358    #[test]
359    #[allow(clippy::redundant_pattern_matching)]
360    fn test_get_single() {
361        let mut vec = ShortBoxSlice::new();
362        assert!(matches!(vec.single(), None));
363
364        vec.push(100);
365        assert!(matches!(vec.single(), Some(_)));
366
367        vec.push(200);
368        assert!(matches!(vec.single(), None));
369    }
370}
icu_locale_core/shortvec/mod.rs

icu_locale_core/shortvec/
mod.rs
