zerovec/flexzerovec/
vec.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
5use super::FlexZeroSlice;
6use super::FlexZeroVecOwned;
7use crate::ZeroVecError;
8use core::cmp::Ordering;
9use core::iter::FromIterator;
10use core::ops::Deref;
11
12/// A zero-copy data structure that efficiently stores integer values.
13///
14/// `FlexZeroVec` automatically increases or decreases its storage capacity based on the largest
15/// integer stored in the vector. It therefore results in lower memory usage when smaller numbers
16/// are usually stored, but larger values must sometimes also be stored.
17///
18/// The maximum value that can be stored in `FlexZeroVec` is `usize::MAX` on the current platform.
19///
20/// `FlexZeroVec` is the data structure for storing `usize` in a `ZeroMap`.
21///
22/// `FlexZeroVec` derefs to [`FlexZeroSlice`], which contains most of the methods.
23///
24/// # Examples
25///
26/// Storing a vec of `usize`s in a zero-copy way:
27///
28/// ```
29/// use zerovec::vecs::FlexZeroVec;
30///
31/// // Create a FlexZeroVec and add a few numbers to it
32/// let mut zv1 = FlexZeroVec::new();
33/// zv1.to_mut().push(55);
34/// zv1.to_mut().push(33);
35/// zv1.to_mut().push(999);
36/// assert_eq!(zv1.to_vec(), vec![55, 33, 999]);
37///
38/// // Convert it to bytes and back
39/// let bytes = zv1.as_bytes();
40/// let zv2 =
41///     FlexZeroVec::parse_byte_slice(bytes).expect("bytes should round-trip");
42/// assert_eq!(zv2.to_vec(), vec![55, 33, 999]);
43///
44/// // Verify the compact storage
45/// assert_eq!(7, bytes.len());
46/// assert!(matches!(zv2, FlexZeroVec::Borrowed(_)));
47/// ```
48///
49/// Storing a map of `usize` to `usize` in a zero-copy way:
50///
51/// ```
52/// use zerovec::ZeroMap;
53///
54/// // Append some values to the ZeroMap
55/// let mut zm = ZeroMap::<usize, usize>::new();
56/// assert!(zm.try_append(&29, &92).is_none());
57/// assert!(zm.try_append(&38, &83).is_none());
58/// assert!(zm.try_append(&56, &65).is_none());
59/// assert_eq!(zm.len(), 3);
60///
61/// // Insert another value into the middle
62/// assert!(zm.try_append(&47, &74).is_some());
63/// assert!(zm.insert(&47, &74).is_none());
64/// assert_eq!(zm.len(), 4);
65///
66/// // Verify that the values are correct
67/// assert_eq!(zm.get_copied(&0), None);
68/// assert_eq!(zm.get_copied(&29), Some(92));
69/// assert_eq!(zm.get_copied(&38), Some(83));
70/// assert_eq!(zm.get_copied(&47), Some(74));
71/// assert_eq!(zm.get_copied(&56), Some(65));
72/// assert_eq!(zm.get_copied(&usize::MAX), None);
73/// ```
74#[derive(Debug)]
75#[non_exhaustive]
76pub enum FlexZeroVec<'a> {
77    Owned(FlexZeroVecOwned),
78    Borrowed(&'a FlexZeroSlice),
79}
80
81impl<'a> Deref for FlexZeroVec<'a> {
82    type Target = FlexZeroSlice;
83    fn deref(&self) -> &Self::Target {
84        match self {
85            FlexZeroVec::Owned(v) => v.deref(),
86            FlexZeroVec::Borrowed(v) => v,
87        }
88    }
89}
90
91impl<'a> AsRef<FlexZeroSlice> for FlexZeroVec<'a> {
92    fn as_ref(&self) -> &FlexZeroSlice {
93        self.deref()
94    }
95}
96
97impl Eq for FlexZeroVec<'_> {}
98
99impl<'a, 'b> PartialEq<FlexZeroVec<'b>> for FlexZeroVec<'a> {
100    #[inline]
101    fn eq(&self, other: &FlexZeroVec<'b>) -> bool {
102        self.iter().eq(other.iter())
103    }
104}
105
106impl<'a> Default for FlexZeroVec<'a> {
107    #[inline]
108    fn default() -> Self {
109        Self::new()
110    }
111}
112
113impl<'a> PartialOrd for FlexZeroVec<'a> {
114    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
115        Some(self.cmp(other))
116    }
117}
118
119impl<'a> Ord for FlexZeroVec<'a> {
120    fn cmp(&self, other: &Self) -> Ordering {
121        self.iter().cmp(other.iter())
122    }
123}
124
125impl<'a> FlexZeroVec<'a> {
126    #[inline]
127    /// Creates a new, borrowed, empty `FlexZeroVec`.
128    ///
129    /// # Examples
130    ///
131    /// ```
132    /// use zerovec::vecs::FlexZeroVec;
133    ///
134    /// let zv: FlexZeroVec = FlexZeroVec::new();
135    /// assert!(zv.is_empty());
136    /// ```
137    pub const fn new() -> Self {
138        Self::Borrowed(FlexZeroSlice::new_empty())
139    }
140
141    /// Parses a `&[u8]` buffer into a `FlexZeroVec`.
142    ///
143    /// The bytes within the byte buffer must remain constant for the life of the FlexZeroVec.
144    ///
145    /// # Endianness
146    ///
147    /// The byte buffer must be encoded in little-endian, even if running in a big-endian
148    /// environment. This ensures a consistent representation of data across platforms.
149    ///
150    /// # Max Value
151    ///
152    /// The bytes will fail to parse if the high value is greater than the capacity of `usize`
153    /// on this platform. For example, a `FlexZeroVec` created on a 64-bit platform might fail
154    /// to deserialize on a 32-bit platform.
155    ///
156    /// # Example
157    ///
158    /// ```
159    /// use zerovec::vecs::FlexZeroVec;
160    ///
161    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
162    /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid slice");
163    ///
164    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
165    /// assert_eq!(zv.get(2), Some(421));
166    /// ```
167    pub fn parse_byte_slice(bytes: &'a [u8]) -> Result<Self, ZeroVecError> {
168        let slice: &'a FlexZeroSlice = FlexZeroSlice::parse_byte_slice(bytes)?;
169        Ok(Self::Borrowed(slice))
170    }
171
172    /// Converts a borrowed FlexZeroVec to an owned FlexZeroVec. No-op if already owned.
173    ///
174    /// # Example
175    ///
176    /// ```
177    /// use zerovec::vecs::FlexZeroVec;
178    ///
179    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
180    /// let zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
181    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
182    ///
183    /// let owned = zv.into_owned();
184    /// assert!(matches!(owned, FlexZeroVec::Owned(_)));
185    /// ```
186    pub fn into_owned(self) -> FlexZeroVec<'static> {
187        match self {
188            Self::Owned(owned) => FlexZeroVec::Owned(owned),
189            Self::Borrowed(slice) => FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice)),
190        }
191    }
192
193    /// Allows the FlexZeroVec to be mutated by converting it to an owned variant, and producing
194    /// a mutable [`FlexZeroVecOwned`].
195    ///
196    /// # Example
197    ///
198    /// ```
199    /// use zerovec::vecs::FlexZeroVec;
200    ///
201    /// let bytes: &[u8] = &[2, 0xD3, 0x00, 0x19, 0x01, 0xA5, 0x01, 0xCD, 0x01];
202    /// let mut zv = FlexZeroVec::parse_byte_slice(bytes).expect("valid bytes");
203    /// assert!(matches!(zv, FlexZeroVec::Borrowed(_)));
204    ///
205    /// zv.to_mut().push(12);
206    /// assert!(matches!(zv, FlexZeroVec::Owned(_)));
207    /// assert_eq!(zv.get(4), Some(12));
208    /// ```
209    pub fn to_mut(&mut self) -> &mut FlexZeroVecOwned {
210        match self {
211            Self::Owned(ref mut owned) => owned,
212            Self::Borrowed(slice) => {
213                *self = FlexZeroVec::Owned(FlexZeroVecOwned::from_slice(slice));
214                // recursion is limited since we are guaranteed to hit the Owned branch
215                self.to_mut()
216            }
217        }
218    }
219
220    /// Remove all elements from this FlexZeroVec and reset it to an empty borrowed state.
221    ///
222    /// # Examples
223    ///
224    /// ```
225    /// use zerovec::vecs::FlexZeroVec;
226    ///
227    /// let mut zv: FlexZeroVec = [1, 2, 3].iter().copied().collect();
228    /// assert!(!zv.is_empty());
229    /// zv.clear();
230    /// assert!(zv.is_empty());
231    /// ```
232    pub fn clear(&mut self) {
233        *self = Self::Borrowed(FlexZeroSlice::new_empty())
234    }
235}
236
237impl FromIterator<usize> for FlexZeroVec<'_> {
238    /// Creates a [`FlexZeroVec::Owned`] from an iterator of `usize`.
239    fn from_iter<I>(iter: I) -> Self
240    where
241        I: IntoIterator<Item = usize>,
242    {
243        FlexZeroVecOwned::from_iter(iter).into_flexzerovec()
244    }
245}
246
247#[test]
248fn test_zeromap_usize() {
249    use crate::ZeroMap;
250
251    let mut zm = ZeroMap::<usize, usize>::new();
252    assert!(zm.try_append(&29, &92).is_none());
253    assert!(zm.try_append(&38, &83).is_none());
254    assert!(zm.try_append(&47, &74).is_none());
255    assert!(zm.try_append(&56, &65).is_none());
256
257    assert_eq!(zm.keys.get_width(), 1);
258    assert_eq!(zm.values.get_width(), 1);
259
260    assert_eq!(zm.insert(&47, &744), Some(74));
261    assert_eq!(zm.values.get_width(), 2);
262    assert_eq!(zm.insert(&47, &774), Some(744));
263    assert_eq!(zm.values.get_width(), 2);
264    assert!(zm.try_append(&1100, &1).is_none());
265    assert_eq!(zm.keys.get_width(), 2);
266    assert_eq!(zm.remove(&1100), Some(1));
267    assert_eq!(zm.keys.get_width(), 1);
268
269    assert_eq!(zm.get_copied(&0), None);
270    assert_eq!(zm.get_copied(&29), Some(92));
271    assert_eq!(zm.get_copied(&38), Some(83));
272    assert_eq!(zm.get_copied(&47), Some(774));
273    assert_eq!(zm.get_copied(&56), Some(65));
274    assert_eq!(zm.get_copied(&usize::MAX), None);
275}
zerovec/flexzerovec/vec.rs

zerovec/flexzerovec/
vec.rs
