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> 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: &'a (K, V)| (&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: &'a (K, V)| (&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: (&'a K, &'a V)| 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: (&'a K, &'a V)| 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: (&'a K, &'a V)| 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: (&'a K, &'a V)| 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> {}
333