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

phf/
ordered_map.rs
