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(msg:"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: &(K, V)| (&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: &(K, V)| (&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: (&K, &V)| 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: (&K, &V)| 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: (&K, &V)| 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: (&K, &V)| 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> {}
313