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

wasmparser/collections/
index_map.rs
