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 crate::ule::AsULE; |
6 | use crate::ZeroSlice; |
7 | |
8 | use core::cmp::Ordering; |
9 | use core::fmt; |
10 | |
11 | pub use super::kv::ZeroMapKV; |
12 | pub use super::vecs::{MutableZeroVecLike, ZeroVecLike}; |
13 | |
14 | /// A borrowed-only version of [`ZeroMap`](super::ZeroMap) |
15 | /// |
16 | /// This is useful for fully-zero-copy deserialization from non-human-readable |
17 | /// serialization formats. It also has the advantage that it can return references that live for |
18 | /// the lifetime of the backing buffer as opposed to that of the [`ZeroMapBorrowed`] instance. |
19 | /// |
20 | /// # Examples |
21 | /// |
22 | /// ``` |
23 | /// use zerovec::maps::ZeroMapBorrowed; |
24 | /// |
25 | /// // Example byte buffer representing the map { 1: "one" } |
26 | /// let BINCODE_BYTES: &[u8; 29] = &[ |
27 | /// 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, |
28 | /// 0, 0, 111, 110, 101, |
29 | /// ]; |
30 | /// |
31 | /// // Deserializing to ZeroMap requires no heap allocations. |
32 | /// let zero_map: ZeroMapBorrowed<u32, str> = |
33 | /// bincode::deserialize(BINCODE_BYTES) |
34 | /// .expect("Should deserialize successfully" ); |
35 | /// assert_eq!(zero_map.get(&1), Some("one" )); |
36 | /// ``` |
37 | /// |
38 | /// This can be obtained from a [`ZeroMap`](super::ZeroMap) via [`ZeroMap::as_borrowed`](super::ZeroMap::as_borrowed) |
39 | pub struct ZeroMapBorrowed<'a, K, V> |
40 | where |
41 | K: ZeroMapKV<'a>, |
42 | V: ZeroMapKV<'a>, |
43 | K: ?Sized, |
44 | V: ?Sized, |
45 | { |
46 | pub(crate) keys: &'a <K as ZeroMapKV<'a>>::Slice, |
47 | pub(crate) values: &'a <V as ZeroMapKV<'a>>::Slice, |
48 | } |
49 | |
50 | impl<'a, K, V> Copy for ZeroMapBorrowed<'a, K, V> |
51 | where |
52 | K: ZeroMapKV<'a>, |
53 | V: ZeroMapKV<'a>, |
54 | K: ?Sized, |
55 | V: ?Sized, |
56 | { |
57 | } |
58 | impl<'a, K, V> Clone for ZeroMapBorrowed<'a, K, V> |
59 | where |
60 | K: ZeroMapKV<'a>, |
61 | V: ZeroMapKV<'a>, |
62 | K: ?Sized, |
63 | V: ?Sized, |
64 | { |
65 | fn clone(&self) -> Self { |
66 | *self |
67 | } |
68 | } |
69 | |
70 | impl<'a, K, V> Default for ZeroMapBorrowed<'a, K, V> |
71 | where |
72 | K: ZeroMapKV<'a>, |
73 | V: ZeroMapKV<'a>, |
74 | K::Slice: 'static, |
75 | V::Slice: 'static, |
76 | K: ?Sized, |
77 | V: ?Sized, |
78 | { |
79 | fn default() -> Self { |
80 | Self::new() |
81 | } |
82 | } |
83 | |
84 | impl<'a, K, V> ZeroMapBorrowed<'a, K, V> |
85 | where |
86 | K: ZeroMapKV<'a>, |
87 | V: ZeroMapKV<'a>, |
88 | K::Slice: 'static, |
89 | V::Slice: 'static, |
90 | K: ?Sized, |
91 | V: ?Sized, |
92 | { |
93 | /// Creates a new, empty `ZeroMapBorrowed<K, V>`. |
94 | /// |
95 | /// Note: Since [`ZeroMapBorrowed`] is not mutable, the return value will be a stub unless |
96 | /// converted into a [`ZeroMap`](super::ZeroMap). |
97 | /// |
98 | /// # Examples |
99 | /// |
100 | /// ``` |
101 | /// use zerovec::maps::ZeroMapBorrowed; |
102 | /// |
103 | /// let zm: ZeroMapBorrowed<u16, str> = ZeroMapBorrowed::new(); |
104 | /// assert!(zm.is_empty()); |
105 | /// ``` |
106 | pub fn new() -> Self { |
107 | Self { |
108 | keys: K::Container::zvl_new_borrowed(), |
109 | values: V::Container::zvl_new_borrowed(), |
110 | } |
111 | } |
112 | } |
113 | |
114 | impl<'a, K, V> ZeroMapBorrowed<'a, K, V> |
115 | where |
116 | K: ZeroMapKV<'a>, |
117 | V: ZeroMapKV<'a>, |
118 | K: ?Sized, |
119 | V: ?Sized, |
120 | { |
121 | #[doc (hidden)] // databake internal |
122 | pub const unsafe fn from_parts_unchecked( |
123 | keys: &'a <K as ZeroMapKV<'a>>::Slice, |
124 | values: &'a <V as ZeroMapKV<'a>>::Slice, |
125 | ) -> Self { |
126 | Self { keys, values } |
127 | } |
128 | |
129 | /// The number of elements in the [`ZeroMapBorrowed`] |
130 | pub fn len(&self) -> usize { |
131 | self.values.zvl_len() |
132 | } |
133 | |
134 | /// Whether the [`ZeroMapBorrowed`] is empty |
135 | pub fn is_empty(&self) -> bool { |
136 | self.values.zvl_len() == 0 |
137 | } |
138 | } |
139 | |
140 | impl<'a, K, V> ZeroMapBorrowed<'a, K, V> |
141 | where |
142 | K: ZeroMapKV<'a> + Ord, |
143 | V: ZeroMapKV<'a>, |
144 | K: ?Sized, |
145 | V: ?Sized, |
146 | { |
147 | /// Get the value associated with `key`, if it exists. |
148 | /// |
149 | /// This is able to return values that live longer than the map itself |
150 | /// since they borrow directly from the backing buffer. This is the |
151 | /// primary advantage of using [`ZeroMapBorrowed`](super::ZeroMapBorrowed) over [`ZeroMap`](super::ZeroMap). |
152 | /// |
153 | /// ```rust |
154 | /// use zerovec::maps::ZeroMapBorrowed; |
155 | /// use zerovec::ZeroMap; |
156 | /// |
157 | /// let mut map = ZeroMap::new(); |
158 | /// map.insert(&1, "one" ); |
159 | /// map.insert(&2, "two" ); |
160 | /// let borrowed = map.as_borrowed(); |
161 | /// assert_eq!(borrowed.get(&1), Some("one" )); |
162 | /// assert_eq!(borrowed.get(&3), None); |
163 | /// ``` |
164 | pub fn get(&self, key: &K) -> Option<&'a V::GetType> { |
165 | let index = self.keys.zvl_binary_search(key).ok()?; |
166 | self.values.zvl_get(index) |
167 | } |
168 | |
169 | /// Binary search the map with `predicate` to find a key, returning the value. |
170 | /// |
171 | /// This is able to return values that live longer than the map itself |
172 | /// since they borrow directly from the backing buffer. This is the |
173 | /// primary advantage of using [`ZeroMapBorrowed`](super::ZeroMapBorrowed) over [`ZeroMap`](super::ZeroMap). |
174 | /// |
175 | /// ```rust |
176 | /// use zerovec::maps::ZeroMapBorrowed; |
177 | /// use zerovec::ZeroMap; |
178 | /// |
179 | /// let mut map = ZeroMap::new(); |
180 | /// map.insert(&1, "one" ); |
181 | /// map.insert(&2, "two" ); |
182 | /// let borrowed = map.as_borrowed(); |
183 | /// assert_eq!(borrowed.get_by(|probe| probe.cmp(&1)), Some("one" )); |
184 | /// assert_eq!(borrowed.get_by(|probe| probe.cmp(&3)), None); |
185 | /// ``` |
186 | pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&'a V::GetType> { |
187 | let index = self.keys.zvl_binary_search_by(predicate).ok()?; |
188 | self.values.zvl_get(index) |
189 | } |
190 | |
191 | /// Returns whether `key` is contained in this map |
192 | /// |
193 | /// ```rust |
194 | /// use zerovec::maps::ZeroMapBorrowed; |
195 | /// use zerovec::ZeroMap; |
196 | /// |
197 | /// let mut map = ZeroMap::new(); |
198 | /// map.insert(&1, "one" ); |
199 | /// map.insert(&2, "two" ); |
200 | /// let borrowed = map.as_borrowed(); |
201 | /// assert!(borrowed.contains_key(&1)); |
202 | /// assert!(!borrowed.contains_key(&3)); |
203 | /// ``` |
204 | pub fn contains_key(&self, key: &K) -> bool { |
205 | self.keys.zvl_binary_search(key).is_ok() |
206 | } |
207 | } |
208 | |
209 | impl<'a, K, V> ZeroMapBorrowed<'a, K, V> |
210 | where |
211 | K: ZeroMapKV<'a> + ?Sized, |
212 | V: ZeroMapKV<'a> + ?Sized, |
213 | { |
214 | /// Produce an ordered iterator over key-value pairs |
215 | pub fn iter<'b>( |
216 | &'b self, |
217 | ) -> impl Iterator< |
218 | Item = ( |
219 | &'a <K as ZeroMapKV<'a>>::GetType, |
220 | &'a <V as ZeroMapKV<'a>>::GetType, |
221 | ), |
222 | > + 'b { |
223 | self.iter_keys().zip(self.iter_values()) |
224 | } |
225 | |
226 | /// Produce an ordered iterator over keys |
227 | pub fn iter_keys<'b>(&'b self) -> impl Iterator<Item = &'a <K as ZeroMapKV<'a>>::GetType> + 'b { |
228 | #[allow (clippy::unwrap_used)] // idx in 0..keys.zvl_len() |
229 | (0..self.keys.zvl_len()).map(move |idx| self.keys.zvl_get(idx).unwrap()) |
230 | } |
231 | |
232 | /// Produce an iterator over values, ordered by keys |
233 | pub fn iter_values<'b>( |
234 | &'b self, |
235 | ) -> impl Iterator<Item = &'a <V as ZeroMapKV<'a>>::GetType> + 'b { |
236 | #[allow (clippy::unwrap_used)] // idx in 0..keys.zvl_len() == values.zvl_len() |
237 | (0..self.values.zvl_len()).map(move |idx| self.values.zvl_get(idx).unwrap()) |
238 | } |
239 | } |
240 | |
241 | impl<'a, K, V> ZeroMapBorrowed<'a, K, V> |
242 | where |
243 | K: ZeroMapKV<'a> + Ord + ?Sized, |
244 | V: ZeroMapKV<'a, Slice = ZeroSlice<V>> + AsULE + Copy + 'static, |
245 | { |
246 | /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE` |
247 | pub fn get_copied(&self, key: &K) -> Option<V> { |
248 | let index = self.keys.zvl_binary_search(key).ok()?; |
249 | self.values.get(index) |
250 | } |
251 | |
252 | /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE` |
253 | pub fn get_copied_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<V> { |
254 | let index = self.keys.zvl_binary_search_by(predicate).ok()?; |
255 | self.values.get(index) |
256 | } |
257 | |
258 | /// Similar to [`Self::iter()`] except it returns a direct copy of the values instead of references |
259 | /// to `V::ULE`, in cases when `V` is fixed-size |
260 | pub fn iter_copied_values<'b>( |
261 | &'b self, |
262 | ) -> impl Iterator<Item = (&'b <K as ZeroMapKV<'a>>::GetType, V)> { |
263 | (0..self.keys.zvl_len()).map(move |idx| { |
264 | ( |
265 | #[allow (clippy::unwrap_used)] // idx in 0..keys.zvl_len() |
266 | self.keys.zvl_get(idx).unwrap(), |
267 | #[allow (clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len() |
268 | self.values.get(idx).unwrap(), |
269 | ) |
270 | }) |
271 | } |
272 | } |
273 | |
274 | impl<'a, K, V> ZeroMapBorrowed<'a, K, V> |
275 | where |
276 | K: ZeroMapKV<'a, Slice = ZeroSlice<K>> + AsULE + Copy + Ord + 'static, |
277 | V: ZeroMapKV<'a, Slice = ZeroSlice<V>> + AsULE + Copy + 'static, |
278 | { |
279 | /// Similar to [`Self::iter()`] except it returns a direct copy of the keys values instead of references |
280 | /// to `K::ULE` and `V::ULE`, in cases when `K` and `V` are fixed-size |
281 | #[allow (clippy::needless_lifetimes)] // Lifetime is necessary in impl Trait |
282 | pub fn iter_copied<'b: 'a>(&'b self) -> impl Iterator<Item = (K, V)> + 'b { |
283 | let keys: &&ZeroSlice = &self.keys; |
284 | let values: &&ZeroSlice = &self.values; |
285 | let len: usize = self.keys.zvl_len(); |
286 | (0..len).map(move |idx: usize| { |
287 | ( |
288 | #[allow (clippy::unwrap_used)] // idx in 0..keys.zvl_len() |
289 | ZeroSlice::get(self:keys, index:idx).unwrap(), |
290 | #[allow (clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len() |
291 | ZeroSlice::get(self:values, index:idx).unwrap(), |
292 | ) |
293 | }) |
294 | } |
295 | } |
296 | |
297 | // We can't use the default PartialEq because ZeroMap is invariant |
298 | // so otherwise rustc will not automatically allow you to compare ZeroMaps |
299 | // with different lifetimes |
300 | impl<'a, 'b, K, V> PartialEq<ZeroMapBorrowed<'b, K, V>> for ZeroMapBorrowed<'a, K, V> |
301 | where |
302 | K: for<'c> ZeroMapKV<'c> + ?Sized, |
303 | V: for<'c> ZeroMapKV<'c> + ?Sized, |
304 | <K as ZeroMapKV<'a>>::Slice: PartialEq<<K as ZeroMapKV<'b>>::Slice>, |
305 | <V as ZeroMapKV<'a>>::Slice: PartialEq<<V as ZeroMapKV<'b>>::Slice>, |
306 | { |
307 | fn eq(&self, other: &ZeroMapBorrowed<'b, K, V>) -> bool { |
308 | self.keys.eq(other.keys) && self.values.eq(other.values) |
309 | } |
310 | } |
311 | |
312 | impl<'a, K, V> fmt::Debug for ZeroMapBorrowed<'a, K, V> |
313 | where |
314 | K: ZeroMapKV<'a> + ?Sized, |
315 | V: ZeroMapKV<'a> + ?Sized, |
316 | K::Slice: fmt::Debug, |
317 | V::Slice: fmt::Debug, |
318 | { |
319 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> { |
320 | f&mut DebugStruct<'_, '_>.debug_struct("ZeroMapBorrowed" ) |
321 | .field("keys" , &self.keys) |
322 | .field(name:"values" , &self.values) |
323 | .finish() |
324 | } |
325 | } |
326 | |