phf/
ordered_map.rs

1//! An order-preserving immutable map constructed at compile time.
2use core::fmt;
3use core::iter::FusedIterator;
4use core::iter::IntoIterator;
5use core::ops::Index;
6use core::slice;
7use phf_shared::{self, HashKey, PhfEq, PhfHash};
8
9/// An order-preserving immutable map constructed at compile time.
10///
11/// Unlike a `Map`, iteration order is guaranteed to match the definition
12/// order.
13///
14/// ## Note
15///
16/// The fields of this struct are public so that they may be initialized by the
17/// `phf_ordered_map!` macro and code generation. They are subject to change at
18/// any time and should never be accessed directly.
19#[cfg(not(feature = "ptrhash"))]
20pub struct OrderedMap<K: 'static, V: 'static> {
21    #[doc(hidden)]
22    pub key: HashKey,
23    #[doc(hidden)]
24    pub disps: &'static [(u32, u32)],
25    #[doc(hidden)]
26    pub idxs: &'static [usize],
27    #[doc(hidden)]
28    pub entries: &'static [(K, V)],
29}
30
31/// An order-preserving immutable map constructed at compile time.
32///
33/// Unlike a `Map`, iteration order is guaranteed to match the definition
34/// order.
35///
36/// ## Note
37///
38/// The fields of this struct are public so that they may be initialized by the
39/// `phf_ordered_map!` macro and code generation. They are subject to change at
40/// any time and should never be accessed directly.
41#[cfg(feature = "ptrhash")]
42pub struct OrderedMap<K: 'static, V: 'static> {
43    #[doc(hidden)]
44    pub key: HashKey,
45    #[doc(hidden)]
46    pub pilots: &'static [u8],
47    #[doc(hidden)]
48    pub remap: &'static [u32],
49    #[doc(hidden)]
50    pub idxs: &'static [usize],
51    #[doc(hidden)]
52    pub entries: &'static [(K, V)],
53}
54
55impl<K, V> fmt::Debug for OrderedMap<K, V>
56where
57    K: fmt::Debug,
58    V: fmt::Debug,
59{
60    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
61        fmt.debug_map().entries(self.entries()).finish()
62    }
63}
64
65impl<'a, K, V, T: ?Sized> Index<&'a T> for OrderedMap<K, V>
66where
67    T: Eq + PhfHash,
68    K: PhfEq<T>,
69{
70    type Output = V;
71
72    fn index(&self, k: &'a T) -> &V {
73        self.get(k).expect("invalid key")
74    }
75}
76
77impl<K, V> PartialEq for OrderedMap<K, V>
78where
79    K: PartialEq,
80    V: PartialEq,
81{
82    #[cfg(not(feature = "ptrhash"))]
83    fn eq(&self, other: &Self) -> bool {
84        self.key == other.key
85            && self.disps == other.disps
86            && self.idxs == other.idxs
87            && self.entries == other.entries
88    }
89
90    #[cfg(feature = "ptrhash")]
91    fn eq(&self, other: &Self) -> bool {
92        self.key == other.key
93            && self.pilots == other.pilots
94            && self.remap == other.remap
95            && self.idxs == other.idxs
96            && self.entries == other.entries
97    }
98}
99
100impl<K, V> Eq for OrderedMap<K, V>
101where
102    K: Eq,
103    V: Eq,
104{
105}
106
107impl<K, V> OrderedMap<K, V> {
108    /// Returns the number of entries in the `OrderedMap`.
109    #[inline]
110    pub const fn len(&self) -> usize {
111        self.entries.len()
112    }
113
114    /// Returns true if the `OrderedMap` is empty.
115    #[inline]
116    pub const fn is_empty(&self) -> bool {
117        self.len() == 0
118    }
119
120    /// Returns a reference to the value that `key` maps to.
121    pub fn get<T>(&self, key: &T) -> Option<&V>
122    where
123        T: Eq + PhfHash + ?Sized,
124        K: PhfEq<T>,
125    {
126        self.get_entry(key).map(|e| e.1)
127    }
128
129    /// Returns a reference to the map's internal static instance of the given
130    /// key.
131    ///
132    /// This can be useful for interning schemes.
133    pub fn get_key<T>(&self, key: &T) -> Option<&K>
134    where
135        T: Eq + PhfHash + ?Sized,
136        K: PhfEq<T>,
137    {
138        self.get_entry(key).map(|e| e.0)
139    }
140
141    /// Determines if `key` is in the `OrderedMap`.
142    pub fn contains_key<T>(&self, key: &T) -> bool
143    where
144        T: Eq + PhfHash + ?Sized,
145        K: PhfEq<T>,
146    {
147        self.get(key).is_some()
148    }
149
150    /// Returns the index of the key within the list used to initialize
151    /// the ordered map.
152    pub fn get_index<T>(&self, key: &T) -> Option<usize>
153    where
154        T: Eq + PhfHash + ?Sized,
155        K: PhfEq<T>,
156    {
157        self.get_internal(key).map(|(i, _)| i)
158    }
159
160    /// Returns references to both the key and values at an index
161    /// within the list used to initialize the ordered map. See `.get_index(key)`.
162    pub fn index(&self, index: usize) -> Option<(&K, &V)> {
163        self.entries.get(index).map(|(k, v)| (k, v))
164    }
165
166    /// Like `get`, but returns both the key and the value.
167    pub fn get_entry<T>(&self, key: &T) -> Option<(&K, &V)>
168    where
169        T: Eq + PhfHash + ?Sized,
170        K: PhfEq<T>,
171    {
172        self.get_internal(key).map(|(_, e)| e)
173    }
174
175    fn get_internal<T>(&self, key: &T) -> Option<(usize, (&K, &V))>
176    where
177        T: Eq + PhfHash + ?Sized,
178        K: PhfEq<T>,
179    {
180        #[cfg(not(feature = "ptrhash"))]
181        {
182            if self.disps.is_empty() {
183                return None;
184            }
185
186            let hashes = phf_shared::hash(key, &self.key);
187            let idx_index = phf_shared::get_index(&hashes, self.disps, self.idxs.len());
188            let idx = self.idxs[idx_index as usize];
189            let entry = &self.entries[idx];
190
191            if entry.0.phf_eq(key) {
192                Some((idx, (&entry.0, &entry.1)))
193            } else {
194                None
195            }
196        }
197
198        #[cfg(feature = "ptrhash")]
199        {
200            if self.entries.is_empty() {
201                return None;
202            }
203
204            let hash = phf_shared::ptrhash::hash(key, &self.key);
205            let idx_index = phf_shared::ptrhash::get_index(
206                self.key,
207                hash,
208                self.pilots,
209                self.remap,
210                self.idxs.len(),
211            );
212            let idx = self.idxs[idx_index as usize];
213            let entry = &self.entries[idx];
214
215            if entry.0.phf_eq(key) {
216                Some((idx, (&entry.0, &entry.1)))
217            } else {
218                None
219            }
220        }
221    }
222
223    /// Returns an iterator over the key/value pairs in the map.
224    ///
225    /// Entries are returned in the same order in which they were defined.
226    pub fn entries(&self) -> Entries<'_, K, V> {
227        Entries {
228            iter: self.entries.iter(),
229        }
230    }
231
232    /// Returns an iterator over the keys in the map.
233    ///
234    /// Keys are returned in the same order in which they were defined.
235    pub fn keys(&self) -> Keys<'_, K, V> {
236        Keys {
237            iter: self.entries(),
238        }
239    }
240
241    /// Returns an iterator over the values in the map.
242    ///
243    /// Values are returned in the same order in which they were defined.
244    pub fn values(&self) -> Values<'_, K, V> {
245        Values {
246            iter: self.entries(),
247        }
248    }
249}
250
251impl<'a, K, V> IntoIterator for &'a OrderedMap<K, V> {
252    type Item = (&'a K, &'a V);
253    type IntoIter = Entries<'a, K, V>;
254
255    fn into_iter(self) -> Entries<'a, K, V> {
256        self.entries()
257    }
258}
259
260/// An iterator over the entries in a `OrderedMap`.
261pub struct Entries<'a, K, V> {
262    iter: slice::Iter<'a, (K, V)>,
263}
264
265impl<'a, K, V> Clone for Entries<'a, K, V> {
266    #[inline]
267    fn clone(&self) -> Self {
268        Self {
269            iter: self.iter.clone(),
270        }
271    }
272}
273
274impl<'a, K, V> fmt::Debug for Entries<'a, K, V>
275where
276    K: fmt::Debug,
277    V: fmt::Debug,
278{
279    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
280        f.debug_list().entries(self.clone()).finish()
281    }
282}
283
284impl<'a, K, V> Iterator for Entries<'a, K, V> {
285    type Item = (&'a K, &'a V);
286
287    fn next(&mut self) -> Option<(&'a K, &'a V)> {
288        self.iter.next().map(|e| (&e.0, &e.1))
289    }
290
291    fn size_hint(&self) -> (usize, Option<usize>) {
292        self.iter.size_hint()
293    }
294}
295
296impl<'a, K, V> DoubleEndedIterator for Entries<'a, K, V> {
297    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
298        self.iter.next_back().map(|e| (&e.0, &e.1))
299    }
300}
301
302impl<'a, K, V> ExactSizeIterator for Entries<'a, K, V> {}
303
304impl<'a, K, V> FusedIterator for Entries<'a, K, V> {}
305
306/// An iterator over the keys in a `OrderedMap`.
307pub struct Keys<'a, K, V> {
308    iter: Entries<'a, K, V>,
309}
310
311impl<'a, K, V> Clone for Keys<'a, K, V> {
312    #[inline]
313    fn clone(&self) -> Self {
314        Self {
315            iter: self.iter.clone(),
316        }
317    }
318}
319
320impl<'a, K, V> fmt::Debug for Keys<'a, K, V>
321where
322    K: fmt::Debug,
323{
324    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
325        f.debug_list().entries(self.clone()).finish()
326    }
327}
328
329impl<'a, K, V> Iterator for Keys<'a, K, V> {
330    type Item = &'a K;
331
332    fn next(&mut self) -> Option<&'a K> {
333        self.iter.next().map(|e| e.0)
334    }
335
336    fn size_hint(&self) -> (usize, Option<usize>) {
337        self.iter.size_hint()
338    }
339}
340
341impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
342    fn next_back(&mut self) -> Option<&'a K> {
343        self.iter.next_back().map(|e| e.0)
344    }
345}
346
347impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
348
349impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
350
351/// An iterator over the values in a `OrderedMap`.
352pub struct Values<'a, K, V> {
353    iter: Entries<'a, K, V>,
354}
355
356impl<'a, K, V> Clone for Values<'a, K, V> {
357    #[inline]
358    fn clone(&self) -> Self {
359        Self {
360            iter: self.iter.clone(),
361        }
362    }
363}
364
365impl<'a, K, V> fmt::Debug for Values<'a, K, V>
366where
367    V: fmt::Debug,
368{
369    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
370        f.debug_list().entries(self.clone()).finish()
371    }
372}
373
374impl<'a, K, V> Iterator for Values<'a, K, V> {
375    type Item = &'a V;
376
377    fn next(&mut self) -> Option<&'a V> {
378        self.iter.next().map(|e| e.1)
379    }
380
381    fn size_hint(&self) -> (usize, Option<usize>) {
382        self.iter.size_hint()
383    }
384}
385
386impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
387    fn next_back(&mut self) -> Option<&'a V> {
388        self.iter.next_back().map(|e| e.1)
389    }
390}
391
392impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
393
394impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
phf/ordered_map.rs

phf/
ordered_map.rs
