wasmparser/collections/
index_map.rs

1//! Type definitions for an ordered map.
2
3use core::borrow::Borrow;
4use core::hash::Hash;
5use core::iter::FusedIterator;
6use core::ops::Index;
7
8mod detail;
9
10#[cfg(test)]
11mod tests;
12
13/// A hash table where the iteration order of the key-value pairs is independent of the hash values of the keys.
14///
15/// Provides an API compatible with both [`IndexMap`] and a custom implementation based on [`BTreeMap`].
16///
17/// [`IndexMap`]: indexmap::IndexMap
18/// [`BTreeMap`]: alloc::collections::BTreeMap
19#[derive(Debug, Clone)]
20pub struct IndexMap<K, V> {
21    inner: detail::IndexMapImpl<K, V>,
22}
23
24impl<K, V> Default for IndexMap<K, V> {
25    #[inline]
26    fn default() -> Self {
27        Self {
28            inner: detail::IndexMapImpl::default(),
29        }
30    }
31}
32
33impl<K, V> IndexMap<K, V> {
34    /// Clears the [`IndexMap`], removing all elements.
35    #[inline]
36    pub fn clear(&mut self) {
37        self.inner.clear()
38    }
39
40    /// Returns the number of elements in the [`IndexMap`].
41    #[inline]
42    pub fn len(&self) -> usize {
43        self.inner.len()
44    }
45
46    /// Returns `true` if the [`IndexMap`] contains no elements.
47    #[inline]
48    pub fn is_empty(&self) -> bool {
49        self.inner.is_empty()
50    }
51
52    /// Returns an iterator that yields the items in the [`IndexMap`].
53    #[inline]
54    pub fn iter(&self) -> Iter<'_, K, V> {
55        Iter {
56            inner: self.inner.iter(),
57        }
58    }
59
60    /// Returns an iterator that yields the mutable items in the [`IndexMap`].
61    #[inline]
62    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
63        IterMut {
64            inner: self.inner.iter_mut(),
65        }
66    }
67
68    /// Returns an iterator that yields the keys in the [`IndexMap`].
69    #[inline]
70    pub fn keys(&self) -> Keys<'_, K, V> {
71        Keys {
72            inner: self.inner.keys(),
73        }
74    }
75
76    /// Returns an iterator that yields the values in the [`IndexMap`].
77    #[inline]
78    pub fn values(&self) -> Values<'_, K, V> {
79        Values {
80            inner: self.inner.values(),
81        }
82    }
83
84    /// Returns a mutable iterator that yields the values in the [`IndexMap`].
85    #[inline]
86    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
87        ValuesMut {
88            inner: self.inner.values_mut(),
89        }
90    }
91
92    /// Returns the key-value entry at the given `index` if any.
93    #[inline]
94    pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
95        self.inner.get_index(index)
96    }
97
98    /// Returns the mutable key-value entry at the given `index` if any.
99    #[inline]
100    pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
101        self.inner.get_index_mut(index)
102    }
103}
104
105impl<K, V> IndexMap<K, V>
106where
107    K: Hash + Eq + Ord + Clone,
108{
109    /// Reserves capacity for at least `additional` more elements to be inserted in the [`IndexMap`].
110    #[inline]
111    pub fn reserve(&mut self, additional: usize) {
112        self.inner.reserve(additional);
113    }
114
115    /// Returns true if `key` is contains in the [`IndexMap`].
116    #[inline]
117    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
118    where
119        K: Borrow<Q>,
120        Q: Hash + Eq + Ord,
121    {
122        self.inner.contains_key(key)
123    }
124
125    /// Returns a reference to the value corresponding to the `key`.
126    #[inline]
127    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
128    where
129        K: Borrow<Q>,
130        Q: Hash + Eq + Ord,
131    {
132        self.inner.get(key)
133    }
134
135    /// Return references to the key-value pair stored for `key`,
136    /// if it is present, else `None`.
137    #[inline]
138    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
139    where
140        K: Borrow<Q>,
141        Q: Hash + Eq + Ord,
142    {
143        self.inner.get_key_value(key)
144    }
145
146    /// Returns the key-value pair corresponding to the supplied key
147    /// as well as the unique index of the returned key-value pair.
148    ///
149    /// The supplied key may be any borrowed form of the map's key type,
150    /// but the ordering on the borrowed form *must* match the ordering
151    /// on the key type.
152    #[inline]
153    pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
154    where
155        K: Borrow<Q> + Ord,
156        Q: Hash + Eq + Ord,
157    {
158        self.inner.get_full(key)
159    }
160
161    /// Returns a mutable reference to the value corresponding to the key.
162    #[inline]
163    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
164    where
165        K: Borrow<Q>,
166        Q: Hash + Eq + Ord,
167    {
168        self.inner.get_mut(key)
169    }
170
171    /// Inserts a key-value pair into the [`IndexMap`].
172    ///
173    /// If the map did not have this key present, `None` is returned.
174    ///
175    /// If the map did have this key present, the value is updated, and the old
176    /// value is returned. The key is not updated, though; this matters for
177    /// types that can be `==` without being identical.
178    #[inline]
179    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
180        self.inner.insert(key, value)
181    }
182
183    /// Remove the key-value pair equivalent to `key` and return its value.
184    ///
185    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
186    /// last element of the map and popping it off. **This perturbs
187    /// the position of what used to be the last element!**
188    ///
189    /// Return `None` if `key` is not in map.
190    ///
191    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
192    #[inline]
193    pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
194    where
195        K: Borrow<Q>,
196        Q: ?Sized + Hash + Eq + Ord,
197    {
198        self.inner.swap_remove(key)
199    }
200
201    /// Remove and return the key-value pair equivalent to `key`.
202    ///
203    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
204    /// last element of the map and popping it off. **This perturbs
205    /// the position of what used to be the last element!**
206    ///
207    /// Return `None` if `key` is not in map.
208    ///
209    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
210    #[inline]
211    pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
212    where
213        K: Borrow<Q>,
214        Q: ?Sized + Hash + Eq + Ord,
215    {
216        self.inner.swap_remove_entry(key)
217    }
218
219    /// Gets the given key's corresponding entry in the [`IndexMap`] for in-place manipulation.
220    #[inline]
221    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
222        match self.inner.entry(key) {
223            detail::EntryImpl::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
224            detail::EntryImpl::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
225        }
226    }
227}
228
229impl<K, Q, V> Index<&Q> for IndexMap<K, V>
230where
231    K: Borrow<Q> + Hash + Eq + Ord,
232    Q: ?Sized + Hash + Eq + Ord,
233{
234    type Output = V;
235
236    #[inline]
237    fn index(&self, key: &Q) -> &V {
238        &self.inner[key]
239    }
240}
241
242impl<K, V> Index<usize> for IndexMap<K, V>
243where
244    K: Hash + Eq + Ord,
245{
246    type Output = V;
247
248    #[inline]
249    fn index(&self, key: usize) -> &V {
250        &self.inner[key]
251    }
252}
253
254impl<K, V> Extend<(K, V)> for IndexMap<K, V>
255where
256    K: Eq + Hash + Ord + Clone,
257{
258    #[inline]
259    fn extend<Iter: IntoIterator<Item = (K, V)>>(&mut self, iter: Iter) {
260        self.inner.extend(iter)
261    }
262}
263
264/// A view into a single entry in a [`IndexMap`], which may either be vacant or occupied.
265///
266/// This enum is constructed from the entry method on [`IndexMap`].
267#[derive(Debug)]
268pub enum Entry<'a, K: Ord, V> {
269    /// An occupied entry.
270    Occupied(OccupiedEntry<'a, K, V>),
271    /// A vacant entry.
272    Vacant(VacantEntry<'a, K, V>),
273}
274
275impl<'a, K, V> Entry<'a, K, V>
276where
277    K: Hash + Eq + Ord + Clone,
278{
279    /// Returns a reference to this entry's key.
280    #[inline]
281    pub fn key(&self) -> &K {
282        match *self {
283            Self::Occupied(ref entry) => entry.key(),
284            Self::Vacant(ref entry) => entry.key(),
285        }
286    }
287}
288
289impl<'a, K, V> Entry<'a, K, V>
290where
291    K: Hash + Eq + Ord + Clone,
292    V: Default,
293{
294    /// Ensures a value is in the entry by inserting the default value if empty,
295    /// and returns a mutable reference to the value in the entry.
296    #[inline]
297    pub fn or_default(self) -> &'a mut V {
298        match self {
299            Self::Occupied(entry) => entry.into_mut(),
300            Self::Vacant(entry) => entry.insert(Default::default()),
301        }
302    }
303}
304
305/// A view into an occupied entry in a [`IndexMap`].
306///
307/// It is part of the [`Entry`] enum.
308#[derive(Debug)]
309pub struct OccupiedEntry<'a, K: Ord, V> {
310    inner: detail::OccupiedEntryImpl<'a, K, V>,
311}
312
313impl<'a, K: 'a, V: 'a> OccupiedEntry<'a, K, V>
314where
315    K: Ord + Clone,
316{
317    /// Gets a reference to the key in the entry.
318    #[inline]
319    pub fn key(&self) -> &K {
320        self.inner.key()
321    }
322
323    /// Gets a reference to the value in the entry.
324    #[inline]
325    pub fn get(&self) -> &V {
326        self.inner.get()
327    }
328
329    /// Gets a mutable reference to the value in the entry.
330    #[inline]
331    pub fn get_mut(&mut self) -> &mut V {
332        self.inner.get_mut()
333    }
334
335    /// Sets the value of the entry with the [`OccupiedEntry`]'s key, and returns the entry's old value.
336    #[inline]
337    pub fn insert(&mut self, value: V) -> V {
338        self.inner.insert(value)
339    }
340
341    /// Converts the [`OccupiedEntry`] into a mutable reference to the value in the entry
342    /// with a lifetime bound to the map itself.
343    #[inline]
344    pub fn into_mut(self) -> &'a mut V {
345        self.inner.into_mut()
346    }
347}
348
349/// A view into a vacant entry in a [`IndexMap`].
350///
351/// It is part of the [`Entry`] enum.
352#[derive(Debug)]
353pub struct VacantEntry<'a, K: Ord, V> {
354    inner: detail::VacantEntryImpl<'a, K, V>,
355}
356
357impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V>
358where
359    K: Ord + Clone,
360{
361    /// Gets a reference to the key in the entry.
362    #[inline]
363    pub fn key(&self) -> &K {
364        self.inner.key()
365    }
366
367    /// Take ownership of the key.
368    #[inline]
369    pub fn into_key(self) -> K {
370        self.inner.into_key()
371    }
372
373    /// Sets the value of the entry with the [`VacantEntry`]'s key, and returns a mutable reference to it.
374    #[inline]
375    pub fn insert(self, value: V) -> &'a mut V
376    where
377        K: Hash,
378    {
379        self.inner.insert(value)
380    }
381}
382
383impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
384where
385    K: Hash + Ord + Eq + Clone,
386{
387    #[inline]
388    fn from_iter<I>(iter: I) -> Self
389    where
390        I: IntoIterator<Item = (K, V)>,
391    {
392        Self {
393            inner: <detail::IndexMapImpl<K, V>>::from_iter(iter),
394        }
395    }
396}
397
398impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
399    type Item = (&'a K, &'a V);
400    type IntoIter = Iter<'a, K, V>;
401
402    #[inline]
403    fn into_iter(self) -> Self::IntoIter {
404        self.iter()
405    }
406}
407
408/// An iterator over the items of a [`IndexMap`].
409#[derive(Debug, Clone)]
410pub struct Iter<'a, K, V> {
411    inner: detail::IterImpl<'a, K, V>,
412}
413
414impl<'a, K, V> Iterator for Iter<'a, K, V> {
415    type Item = (&'a K, &'a V);
416
417    #[inline]
418    fn size_hint(&self) -> (usize, Option<usize>) {
419        self.inner.size_hint()
420    }
421
422    #[inline]
423    fn next(&mut self) -> Option<Self::Item> {
424        self.inner.next()
425    }
426}
427
428impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
429    #[inline]
430    fn len(&self) -> usize {
431        self.inner.len()
432    }
433}
434
435impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
436
437impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
438    type Item = (&'a K, &'a mut V);
439    type IntoIter = IterMut<'a, K, V>;
440
441    #[inline]
442    fn into_iter(self) -> Self::IntoIter {
443        self.iter_mut()
444    }
445}
446
447/// An iterator over the mutable items of a [`IndexMap`].
448#[derive(Debug)]
449pub struct IterMut<'a, K, V> {
450    inner: detail::IterMutImpl<'a, K, V>,
451}
452
453impl<'a, K, V> Iterator for IterMut<'a, K, V> {
454    type Item = (&'a K, &'a mut V);
455
456    #[inline]
457    fn size_hint(&self) -> (usize, Option<usize>) {
458        self.inner.size_hint()
459    }
460
461    #[inline]
462    fn next(&mut self) -> Option<Self::Item> {
463        self.inner.next()
464    }
465}
466
467impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
468    #[inline]
469    fn len(&self) -> usize {
470        self.inner.len()
471    }
472}
473
474impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
475
476impl<K, V> IntoIterator for IndexMap<K, V> {
477    type Item = (K, V);
478    type IntoIter = IntoIter<K, V>;
479
480    #[inline]
481    fn into_iter(self) -> Self::IntoIter {
482        IntoIter {
483            inner: self.inner.into_iter(),
484        }
485    }
486}
487
488/// An iterator over the owned items of an [`IndexMap`].
489#[derive(Debug)]
490pub struct IntoIter<K, V> {
491    inner: detail::IntoIterImpl<K, V>,
492}
493
494impl<K, V> Iterator for IntoIter<K, V> {
495    type Item = (K, V);
496
497    #[inline]
498    fn size_hint(&self) -> (usize, Option<usize>) {
499        self.inner.size_hint()
500    }
501
502    #[inline]
503    fn next(&mut self) -> Option<Self::Item> {
504        self.inner.next()
505    }
506}
507
508impl<K, V> ExactSizeIterator for IntoIter<K, V> {
509    #[inline]
510    fn len(&self) -> usize {
511        self.inner.len()
512    }
513}
514
515impl<K, V> FusedIterator for IntoIter<K, V> {}
516
517/// An iterator over the keys of a [`IndexMap`].
518#[derive(Debug, Clone)]
519pub struct Keys<'a, K, V> {
520    inner: detail::KeysImpl<'a, K, V>,
521}
522
523impl<'a, K, V> Iterator for Keys<'a, K, V> {
524    type Item = &'a K;
525
526    #[inline]
527    fn size_hint(&self) -> (usize, Option<usize>) {
528        self.inner.size_hint()
529    }
530
531    #[inline]
532    fn next(&mut self) -> Option<Self::Item> {
533        self.inner.next()
534    }
535}
536
537impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
538    #[inline]
539    fn len(&self) -> usize {
540        self.inner.len()
541    }
542}
543
544impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
545
546/// An iterator over the values of a [`IndexMap`].
547#[derive(Debug, Clone)]
548pub struct Values<'a, K, V> {
549    inner: detail::ValuesImpl<'a, K, V>,
550}
551
552impl<'a, K, V> Iterator for Values<'a, K, V> {
553    type Item = &'a V;
554
555    #[inline]
556    fn size_hint(&self) -> (usize, Option<usize>) {
557        self.inner.size_hint()
558    }
559
560    #[inline]
561    fn next(&mut self) -> Option<Self::Item> {
562        self.inner.next()
563    }
564}
565
566impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
567    #[inline]
568    fn len(&self) -> usize {
569        self.inner.len()
570    }
571}
572
573impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
574
575/// An mutable iterator over the values of a [`IndexMap`].
576#[derive(Debug)]
577pub struct ValuesMut<'a, K, V> {
578    inner: detail::ValuesMutImpl<'a, K, V>,
579}
580
581impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
582    type Item = &'a mut V;
583
584    #[inline]
585    fn size_hint(&self) -> (usize, Option<usize>) {
586        self.inner.size_hint()
587    }
588
589    #[inline]
590    fn next(&mut self) -> Option<Self::Item> {
591        self.inner.next()
592    }
593}
594
595impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
596    #[inline]
597    fn len(&self) -> usize {
598        self.inner.len()
599    }
600}
601
602impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
603
604#[cfg(feature = "serde")]
605impl<K, V> serde::Serialize for IndexMap<K, V>
606where
607    K: serde::Serialize + Eq + Hash + Ord,
608    V: serde::Serialize,
609{
610    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
611    where
612        S: serde::ser::Serializer,
613    {
614        serde::Serialize::serialize(&self.inner, serializer)
615    }
616}
617
618#[cfg(feature = "serde")]
619impl<'a, K, V> serde::Deserialize<'a> for IndexMap<K, V>
620where
621    K: serde::Deserialize<'a> + Eq + Hash + Ord + Clone,
622    V: serde::Deserialize<'a>,
623{
624    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
625    where
626        D: serde::de::Deserializer<'a>,
627    {
628        Ok(IndexMap {
629            inner: serde::Deserialize::deserialize(deserializer)?,
630        })
631    }
632}
633
634impl<K, V> PartialEq for IndexMap<K, V>
635where
636    K: PartialEq + Hash + Ord,
637    V: PartialEq,
638{
639    fn eq(&self, other: &Self) -> bool {
640        self.inner == other.inner
641    }
642
643    fn ne(&self, other: &Self) -> bool {
644        self.inner != other.inner
645    }
646}
647
648impl<K, V> Eq for IndexMap<K, V>
649where
650    K: Eq + Hash + Ord,
651    V: Eq,
652{
653}
wasmparser/collections/index_map.rs

wasmparser/collections/
index_map.rs
