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, PhfBorrow, 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.
19pub struct OrderedMap<K: 'static, V: 'static> {
20    #[doc(hidden)]
21    pub key: HashKey,
22    #[doc(hidden)]
23    pub disps: &'static [(u32, u32)],
24    #[doc(hidden)]
25    pub idxs: &'static [usize],
26    #[doc(hidden)]
27    pub entries: &'static [(K, V)],
28}
29
30impl<K, V> fmt::Debug for OrderedMap<K, V>
31where
32    K: fmt::Debug,
33    V: fmt::Debug,
34{
35    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
36        fmt.debug_map().entries(self.entries()).finish()
37    }
38}
39
40impl<'a, K, V, T: ?Sized> Index<&'a T> for OrderedMap<K, V>
41where
42    T: Eq + PhfHash,
43    K: PhfBorrow<T>,
44{
45    type Output = V;
46
47    fn index(&self, k: &'a T) -> &V {
48        self.get(k).expect("invalid key")
49    }
50}
51
52impl<K, V> PartialEq for OrderedMap<K, V>
53where
54    K: PartialEq,
55    V: PartialEq,
56{
57    fn eq(&self, other: &Self) -> bool {
58        self.key == other.key
59            && self.disps == other.disps
60            && self.idxs == other.idxs
61            && self.entries == other.entries
62    }
63}
64
65impl<K, V> Eq for OrderedMap<K, V>
66where
67    K: Eq,
68    V: Eq,
69{
70}
71
72impl<K, V> OrderedMap<K, V> {
73    /// Returns the number of entries in the `OrderedMap`.
74    #[inline]
75    pub const fn len(&self) -> usize {
76        self.entries.len()
77    }
78
79    /// Returns true if the `OrderedMap` is empty.
80    #[inline]
81    pub const fn is_empty(&self) -> bool {
82        self.len() == 0
83    }
84
85    /// Returns a reference to the value that `key` maps to.
86    pub fn get<T: ?Sized>(&self, key: &T) -> Option<&V>
87    where
88        T: Eq + PhfHash,
89        K: PhfBorrow<T>,
90    {
91        self.get_entry(key).map(|e| e.1)
92    }
93
94    /// Returns a reference to the map's internal static instance of the given
95    /// key.
96    ///
97    /// This can be useful for interning schemes.
98    pub fn get_key<T: ?Sized>(&self, key: &T) -> Option<&K>
99    where
100        T: Eq + PhfHash,
101        K: PhfBorrow<T>,
102    {
103        self.get_entry(key).map(|e| e.0)
104    }
105
106    /// Determines if `key` is in the `OrderedMap`.
107    pub fn contains_key<T: ?Sized>(&self, key: &T) -> bool
108    where
109        T: Eq + PhfHash,
110        K: PhfBorrow<T>,
111    {
112        self.get(key).is_some()
113    }
114
115    /// Returns the index of the key within the list used to initialize
116    /// the ordered map.
117    pub fn get_index<T: ?Sized>(&self, key: &T) -> Option<usize>
118    where
119        T: Eq + PhfHash,
120        K: PhfBorrow<T>,
121    {
122        self.get_internal(key).map(|(i, _)| i)
123    }
124
125    /// Returns references to both the key and values at an index
126    /// within the list used to initialize the ordered map. See `.get_index(key)`.
127    pub fn index(&self, index: usize) -> Option<(&K, &V)> {
128        self.entries.get(index).map(|&(ref k, ref v)| (k, v))
129    }
130
131    /// Like `get`, but returns both the key and the value.
132    pub fn get_entry<T: ?Sized>(&self, key: &T) -> Option<(&K, &V)>
133    where
134        T: Eq + PhfHash,
135        K: PhfBorrow<T>,
136    {
137        self.get_internal(key).map(|(_, e)| e)
138    }
139
140    fn get_internal<T: ?Sized>(&self, key: &T) -> Option<(usize, (&K, &V))>
141    where
142        T: Eq + PhfHash,
143        K: PhfBorrow<T>,
144    {
145        if self.disps.is_empty() {
146            return None;
147        } //Prevent panic on empty map
148        let hashes = phf_shared::hash(key, &self.key);
149        let idx_index = phf_shared::get_index(&hashes, self.disps, self.idxs.len());
150        let idx = self.idxs[idx_index as usize];
151        let entry = &self.entries[idx];
152
153        let b: &T = entry.0.borrow();
154        if b == key {
155            Some((idx, (&entry.0, &entry.1)))
156        } else {
157            None
158        }
159    }
160
161    /// Returns an iterator over the key/value pairs in the map.
162    ///
163    /// Entries are returned in the same order in which they were defined.
164    pub fn entries(&self) -> Entries<'_, K, V> {
165        Entries {
166            iter: self.entries.iter(),
167        }
168    }
169
170    /// Returns an iterator over the keys in the map.
171    ///
172    /// Keys are returned in the same order in which they were defined.
173    pub fn keys(&self) -> Keys<'_, K, V> {
174        Keys {
175            iter: self.entries(),
176        }
177    }
178
179    /// Returns an iterator over the values in the map.
180    ///
181    /// Values are returned in the same order in which they were defined.
182    pub fn values(&self) -> Values<'_, K, V> {
183        Values {
184            iter: self.entries(),
185        }
186    }
187}
188
189impl<'a, K, V> IntoIterator for &'a OrderedMap<K, V> {
190    type Item = (&'a K, &'a V);
191    type IntoIter = Entries<'a, K, V>;
192
193    fn into_iter(self) -> Entries<'a, K, V> {
194        self.entries()
195    }
196}
197
198/// An iterator over the entries in a `OrderedMap`.
199pub struct Entries<'a, K, V> {
200    iter: slice::Iter<'a, (K, V)>,
201}
202
203impl<'a, K, V> Clone for Entries<'a, K, V> {
204    #[inline]
205    fn clone(&self) -> Self {
206        Self {
207            iter: self.iter.clone(),
208        }
209    }
210}
211
212impl<'a, K, V> fmt::Debug for Entries<'a, K, V>
213where
214    K: fmt::Debug,
215    V: fmt::Debug,
216{
217    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
218        f.debug_list().entries(self.clone()).finish()
219    }
220}
221
222impl<'a, K, V> Iterator for Entries<'a, K, V> {
223    type Item = (&'a K, &'a V);
224
225    fn next(&mut self) -> Option<(&'a K, &'a V)> {
226        self.iter.next().map(|e| (&e.0, &e.1))
227    }
228
229    fn size_hint(&self) -> (usize, Option<usize>) {
230        self.iter.size_hint()
231    }
232}
233
234impl<'a, K, V> DoubleEndedIterator for Entries<'a, K, V> {
235    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
236        self.iter.next_back().map(|e| (&e.0, &e.1))
237    }
238}
239
240impl<'a, K, V> ExactSizeIterator for Entries<'a, K, V> {}
241
242impl<'a, K, V> FusedIterator for Entries<'a, K, V> {}
243
244/// An iterator over the keys in a `OrderedMap`.
245pub struct Keys<'a, K, V> {
246    iter: Entries<'a, K, V>,
247}
248
249impl<'a, K, V> Clone for Keys<'a, K, V> {
250    #[inline]
251    fn clone(&self) -> Self {
252        Self {
253            iter: self.iter.clone(),
254        }
255    }
256}
257
258impl<'a, K, V> fmt::Debug for Keys<'a, K, V>
259where
260    K: fmt::Debug,
261{
262    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
263        f.debug_list().entries(self.clone()).finish()
264    }
265}
266
267impl<'a, K, V> Iterator for Keys<'a, K, V> {
268    type Item = &'a K;
269
270    fn next(&mut self) -> Option<&'a K> {
271        self.iter.next().map(|e| e.0)
272    }
273
274    fn size_hint(&self) -> (usize, Option<usize>) {
275        self.iter.size_hint()
276    }
277}
278
279impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
280    fn next_back(&mut self) -> Option<&'a K> {
281        self.iter.next_back().map(|e| e.0)
282    }
283}
284
285impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
286
287impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
288
289/// An iterator over the values in a `OrderedMap`.
290pub struct Values<'a, K, V> {
291    iter: Entries<'a, K, V>,
292}
293
294impl<'a, K, V> Clone for Values<'a, K, V> {
295    #[inline]
296    fn clone(&self) -> Self {
297        Self {
298            iter: self.iter.clone(),
299        }
300    }
301}
302
303impl<'a, K, V> fmt::Debug for Values<'a, K, V>
304where
305    V: fmt::Debug,
306{
307    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
308        f.debug_list().entries(self.clone()).finish()
309    }
310}
311
312impl<'a, K, V> Iterator for Values<'a, K, V> {
313    type Item = &'a V;
314
315    fn next(&mut self) -> Option<&'a V> {
316        self.iter.next().map(|e| e.1)
317    }
318
319    fn size_hint(&self) -> (usize, Option<usize>) {
320        self.iter.size_hint()
321    }
322}
323
324impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
325    fn next_back(&mut self) -> Option<&'a V> {
326        self.iter.next_back().map(|e| e.1)
327    }
328}
329
330impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
331
332impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
phf/ordered_map.rs

phf/
ordered_map.rs
