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 crate::ule::AsULE;
6use crate::ZeroSlice;
7
8use core::cmp::Ordering;
9use core::fmt;
10
11pub use super::kv::ZeroMapKV;
12pub 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)
39pub struct ZeroMapBorrowed<'a, K, V>
40where
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
50impl<'a, K, V> Copy for ZeroMapBorrowed<'a, K, V>
51where
52 K: ZeroMapKV<'a>,
53 V: ZeroMapKV<'a>,
54 K: ?Sized,
55 V: ?Sized,
56{
57}
58impl<'a, K, V> Clone for ZeroMapBorrowed<'a, K, V>
59where
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
70impl<'a, K, V> Default for ZeroMapBorrowed<'a, K, V>
71where
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
84impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
85where
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
114impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
115where
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
140impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
141where
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
209impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
210where
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
241impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
242where
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
274impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
275where
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
300impl<'a, 'b, K, V> PartialEq<ZeroMapBorrowed<'b, K, V>> for ZeroMapBorrowed<'a, K, V>
301where
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
312impl<'a, K, V> fmt::Debug for ZeroMapBorrowed<'a, K, V>
313where
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