zerovec/map/
borrowed.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 crate::ule::AsULE;
6use crate::ZeroSlice;
7
8use core::cmp::Ordering;
9use core::fmt;
10
11use super::kv::ZeroMapKV;
12use super::vecs::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; 25] = &[
27///     4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 1, 0, 111,
28///     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::ZeroMap;
155    ///
156    /// let mut map = ZeroMap::new();
157    /// map.insert(&1, "one");
158    /// map.insert(&2, "two");
159    /// let borrowed = map.as_borrowed();
160    /// assert_eq!(borrowed.get(&1), Some("one"));
161    /// assert_eq!(borrowed.get(&3), None);
162    /// ```
163    pub fn get(self, key: &K) -> Option<&'a V::GetType> {
164        let index = self.keys.zvl_binary_search(key).ok()?;
165        self.values.zvl_get(index)
166    }
167
168    /// Binary search the map with `predicate` to find a key, returning the value.
169    ///
170    /// This is able to return values that live longer than the map itself
171    /// since they borrow directly from the backing buffer. This is the
172    /// primary advantage of using [`ZeroMapBorrowed`](super::ZeroMapBorrowed) over [`ZeroMap`](super::ZeroMap).
173    ///
174    /// ```rust
175    /// use zerovec::ZeroMap;
176    ///
177    /// let mut map = ZeroMap::new();
178    /// map.insert(&1, "one");
179    /// map.insert(&2, "two");
180    /// let borrowed = map.as_borrowed();
181    /// assert_eq!(borrowed.get_by(|probe| probe.cmp(&1)), Some("one"));
182    /// assert_eq!(borrowed.get_by(|probe| probe.cmp(&3)), None);
183    /// ```
184    pub fn get_by(self, predicate: impl FnMut(&K) -> Ordering) -> Option<&'a V::GetType> {
185        let index = self.keys.zvl_binary_search_by(predicate).ok()?;
186        self.values.zvl_get(index)
187    }
188
189    /// Returns whether `key` is contained in this map
190    ///
191    /// ```rust
192    /// use zerovec::ZeroMap;
193    ///
194    /// let mut map = ZeroMap::new();
195    /// map.insert(&1, "one");
196    /// map.insert(&2, "two");
197    /// let borrowed = map.as_borrowed();
198    /// assert!(borrowed.contains_key(&1));
199    /// assert!(!borrowed.contains_key(&3));
200    /// ```
201    pub fn contains_key(self, key: &K) -> bool {
202        self.keys.zvl_binary_search(key).is_ok()
203    }
204}
205
206impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
207where
208    K: ZeroMapKV<'a> + ?Sized,
209    V: ZeroMapKV<'a> + ?Sized,
210{
211    /// Produce an ordered iterator over key-value pairs
212    pub fn iter(
213        self,
214    ) -> impl Iterator<
215        Item = (
216            &'a <K as ZeroMapKV<'a>>::GetType,
217            &'a <V as ZeroMapKV<'a>>::GetType,
218        ),
219    > {
220        self.iter_keys().zip(self.iter_values())
221    }
222
223    /// Produce an ordered iterator over keys
224    pub fn iter_keys(self) -> impl Iterator<Item = &'a <K as ZeroMapKV<'a>>::GetType> {
225        #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
226        (0..self.keys.zvl_len()).map(move |idx| self.keys.zvl_get(idx).unwrap())
227    }
228
229    /// Produce an iterator over values, ordered by keys
230    pub fn iter_values(self) -> impl Iterator<Item = &'a <V as ZeroMapKV<'a>>::GetType> {
231        #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() == values.zvl_len()
232        (0..self.values.zvl_len()).map(move |idx| self.values.zvl_get(idx).unwrap())
233    }
234}
235
236impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
237where
238    K: ZeroMapKV<'a> + Ord + ?Sized,
239    V: ZeroMapKV<'a, Slice = ZeroSlice<V>> + AsULE + Copy + 'static,
240{
241    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
242    pub fn get_copied(self, key: &K) -> Option<V> {
243        let index = self.keys.zvl_binary_search(key).ok()?;
244        self.values.get(index)
245    }
246
247    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
248    pub fn get_copied_by(self, predicate: impl FnMut(&K) -> Ordering) -> Option<V> {
249        let index = self.keys.zvl_binary_search_by(predicate).ok()?;
250        self.values.get(index)
251    }
252
253    /// Similar to [`Self::iter()`] except it returns a direct copy of the values instead of references
254    /// to `V::ULE`, in cases when `V` is fixed-size
255    pub fn iter_copied_values(
256        self,
257    ) -> impl Iterator<Item = (&'a <K as ZeroMapKV<'a>>::GetType, V)> {
258        (0..self.keys.zvl_len()).map(move |idx| {
259            (
260                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
261                self.keys.zvl_get(idx).unwrap(),
262                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
263                self.values.get(idx).unwrap(),
264            )
265        })
266    }
267}
268
269impl<'a, K, V> ZeroMapBorrowed<'a, K, V>
270where
271    K: ZeroMapKV<'a, Slice = ZeroSlice<K>> + AsULE + Copy + Ord + 'static,
272    V: ZeroMapKV<'a, Slice = ZeroSlice<V>> + AsULE + Copy + 'static,
273{
274    /// Similar to [`Self::iter()`] except it returns a direct copy of the keys values instead of references
275    /// to `K::ULE` and `V::ULE`, in cases when `K` and `V` are fixed-size
276    #[allow(clippy::needless_lifetimes)] // Lifetime is necessary in impl Trait
277    pub fn iter_copied(self) -> impl Iterator<Item = (K, V)> + 'a {
278        let len = self.keys.zvl_len();
279        (0..len).map(move |idx| {
280            (
281                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
282                ZeroSlice::get(self.keys, idx).unwrap(),
283                #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
284                ZeroSlice::get(self.values, idx).unwrap(),
285            )
286        })
287    }
288}
289
290// We can't use the default PartialEq because ZeroMap is invariant
291// so otherwise rustc will not automatically allow you to compare ZeroMaps
292// with different lifetimes
293impl<'a, 'b, K, V> PartialEq<ZeroMapBorrowed<'b, K, V>> for ZeroMapBorrowed<'a, K, V>
294where
295    K: for<'c> ZeroMapKV<'c> + ?Sized,
296    V: for<'c> ZeroMapKV<'c> + ?Sized,
297    <K as ZeroMapKV<'a>>::Slice: PartialEq<<K as ZeroMapKV<'b>>::Slice>,
298    <V as ZeroMapKV<'a>>::Slice: PartialEq<<V as ZeroMapKV<'b>>::Slice>,
299{
300    fn eq(&self, other: &ZeroMapBorrowed<'b, K, V>) -> bool {
301        self.keys.eq(other.keys) && self.values.eq(other.values)
302    }
303}
304
305impl<'a, K, V> fmt::Debug for ZeroMapBorrowed<'a, K, V>
306where
307    K: ZeroMapKV<'a> + ?Sized,
308    V: ZeroMapKV<'a> + ?Sized,
309    K::Slice: fmt::Debug,
310    V::Slice: fmt::Debug,
311{
312    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
313        f.debug_struct("ZeroMapBorrowed")
314            .field("keys", &self.keys)
315            .field("values", &self.values)
316            .finish()
317    }
318}
zerovec/map/borrowed.rs

zerovec/map/
borrowed.rs
