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 | use super::FlexZeroSlice; |
6 | use super::FlexZeroVecOwned; |
7 | use crate::ZeroVecError; |
8 | use core::cmp::Ordering; |
9 | use core::iter::FromIterator; |
10 | use 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 ] |
76 | pub enum FlexZeroVec<'a> { |
77 | Owned(FlexZeroVecOwned), |
78 | Borrowed(&'a FlexZeroSlice), |
79 | } |
80 | |
81 | impl<'a> Deref for FlexZeroVec<'a> { |
82 | type Target = FlexZeroSlice; |
83 | fn deref(&self) -> &Self::Target { |
84 | match self { |
85 | FlexZeroVec::Owned(v: &FlexZeroVecOwned) => v.deref(), |
86 | FlexZeroVec::Borrowed(v: &&FlexZeroSlice) => v, |
87 | } |
88 | } |
89 | } |
90 | |
91 | impl<'a> AsRef<FlexZeroSlice> for FlexZeroVec<'a> { |
92 | fn as_ref(&self) -> &FlexZeroSlice { |
93 | self.deref() |
94 | } |
95 | } |
96 | |
97 | impl Eq for FlexZeroVec<'_> {} |
98 | |
99 | impl<'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 | |
106 | impl<'a> Default for FlexZeroVec<'a> { |
107 | #[inline ] |
108 | fn default() -> Self { |
109 | Self::new() |
110 | } |
111 | } |
112 | |
113 | impl<'a> PartialOrd for FlexZeroVec<'a> { |
114 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |
115 | self.iter().partial_cmp(other.iter()) |
116 | } |
117 | } |
118 | |
119 | impl<'a> Ord for FlexZeroVec<'a> { |
120 | fn cmp(&self, other: &Self) -> Ordering { |
121 | self.iter().cmp(other.iter()) |
122 | } |
123 | } |
124 | |
125 | impl<'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 | |
237 | impl 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 ] |
248 | fn 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 | } |
276 | |