wasmparser/collections/index_map/
detail.rs

1//! An ordered map based on a B-Tree that keeps insertion order of elements.
2
3#[cfg(all(
4    feature = "hash-collections",
5    not(feature = "prefer-btree-collections")
6))]
7mod impls {
8    use crate::collections::hash;
9    use indexmap::IndexMap;
10
11    pub type IndexMapImpl<K, V> = IndexMap<K, V, hash::RandomState>;
12    pub type EntryImpl<'a, K, V> = indexmap::map::Entry<'a, K, V>;
13    pub type OccupiedEntryImpl<'a, K, V> = indexmap::map::OccupiedEntry<'a, K, V>;
14    pub type VacantEntryImpl<'a, K, V> = indexmap::map::VacantEntry<'a, K, V>;
15    pub type IterImpl<'a, K, V> = indexmap::map::Iter<'a, K, V>;
16    pub type IterMutImpl<'a, K, V> = indexmap::map::IterMut<'a, K, V>;
17    pub type IntoIterImpl<K, V> = indexmap::map::IntoIter<K, V>;
18    pub type KeysImpl<'a, K, V> = indexmap::map::Keys<'a, K, V>;
19    pub type ValuesImpl<'a, K, V> = indexmap::map::Values<'a, K, V>;
20    pub type ValuesMutImpl<'a, K, V> = indexmap::map::ValuesMut<'a, K, V>;
21}
22
23#[cfg(any(
24    not(feature = "hash-collections"),
25    feature = "prefer-btree-collections"
26))]
27mod impls {
28    pub type IndexMapImpl<K, V> = super::IndexMap<K, V>;
29    pub type EntryImpl<'a, K, V> = super::Entry<'a, K, V>;
30    pub type OccupiedEntryImpl<'a, K, V> = super::OccupiedEntry<'a, K, V>;
31    pub type VacantEntryImpl<'a, K, V> = super::VacantEntry<'a, K, V>;
32    pub type IterImpl<'a, K, V> = super::Iter<'a, K, V>;
33    pub type IterMutImpl<'a, K, V> = super::IterMut<'a, K, V>;
34    pub type IntoIterImpl<K, V> = super::IntoIter<K, V>;
35    pub type KeysImpl<'a, K, V> = super::Keys<'a, K, V>;
36    pub type ValuesImpl<'a, K, V> = super::Values<'a, K, V>;
37    pub type ValuesMutImpl<'a, K, V> = super::ValuesMut<'a, K, V>;
38}
39
40pub use self::impls::*;
41
42use alloc::collections::{BTreeMap, btree_map};
43use alloc::vec::IntoIter as VecIntoIter;
44use alloc::vec::Vec;
45use core::borrow::Borrow;
46use core::fmt;
47use core::iter::FusedIterator;
48use core::mem::replace;
49use core::ops::{Index, IndexMut};
50use core::slice::Iter as SliceIter;
51use core::slice::IterMut as SliceIterMut;
52
53/// A slot index referencing a slot in an [`IndexMap`].
54#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
55struct SlotIndex(usize);
56
57impl SlotIndex {
58    /// Returns the raw `usize` index of the [`SlotIndex`].
59    pub fn index(self) -> usize {
60        self.0
61    }
62}
63
64#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
65struct Slot<K, V> {
66    /// The key of the [`Slot`].
67    key: K,
68    /// The value of the [`Slot`].
69    value: V,
70}
71
72impl<K, V> Slot<K, V> {
73    /// Creates a new [`Slot`] from the given `key` and `value`.
74    pub fn new(key: K, value: V) -> Self {
75        Self { key, value }
76    }
77
78    /// Returns the [`Slot`] as a pair of references to its `key` and `value`.
79    pub fn as_pair(&self) -> (&K, &V) {
80        (&self.key, &self.value)
81    }
82
83    /// Returns the [`Slot`] as a pair of references to its `key` and `value`.
84    pub fn as_pair_mut(&mut self) -> (&K, &mut V) {
85        (&self.key, &mut self.value)
86    }
87
88    /// Converts the [`Slot`] into a pair of its `key` and `value`.
89    pub fn into_pair(self) -> (K, V) {
90        (self.key, self.value)
91    }
92
93    /// Returns a shared reference to the key of the [`Slot`].
94    pub fn key(&self) -> &K {
95        &self.key
96    }
97
98    /// Returns a shared reference to the value of the [`Slot`].
99    pub fn value(&self) -> &V {
100        &self.value
101    }
102
103    /// Returns an exclusive reference to the value of the [`Slot`].
104    pub fn value_mut(&mut self) -> &mut V {
105        &mut self.value
106    }
107}
108
109/// A b-tree map where the iteration order of the key-value
110/// pairs is independent of the ordering of the keys.
111///
112/// The interface is closely compatible with the [`indexmap` crate]
113/// and a subset of the features that is relevant for the
114/// [`wasmparser-nostd` crate].
115///
116/// # Differences to original `IndexMap`
117///
118/// Since the goal of this crate was to maintain a simple
119/// `no_std` compatible fork of the [`indexmap` crate] there are some
120/// downsides and differences.
121///
122/// - Some operations such as `IndexMap::insert` now require `K: Clone`.
123/// - It is to be expected that this fork performs worse than the original
124/// [`indexmap` crate] implementation.
125/// - The implementation is based on `BTreeMap` internally instead of
126/// `HashMap` which has the effect that methods no longer require `K: Hash`
127/// but `K: Ord` instead.
128///
129/// [`indexmap` crate]: https://crates.io/crates/indexmap
130/// [`wasmparser-nostd` crate]: https://crates.io/crates/wasmparser-nostd
131#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
132pub struct IndexMap<K, V> {
133    /// A mapping from keys to slot indices.
134    key2slot: BTreeMap<K, SlotIndex>,
135    /// A vector holding all slots of key value pairs.
136    slots: Vec<Slot<K, V>>,
137}
138
139impl<K, V> Default for IndexMap<K, V> {
140    fn default() -> Self {
141        Self::new()
142    }
143}
144
145impl<K, V> IndexMap<K, V> {
146    /// Makes a new, empty [`IndexMap`].
147    ///
148    /// Does not allocate anything on its own.
149    pub fn new() -> Self {
150        Self {
151            key2slot: BTreeMap::new(),
152            slots: Vec::new(),
153        }
154    }
155
156    /// Constructs a new, empty [`IndexMap`] with at least the specified capacity.
157    ///
158    /// Does not allocate if `capacity` is zero.
159    pub fn with_capacity(capacity: usize) -> Self {
160        Self {
161            key2slot: BTreeMap::new(),
162            slots: Vec::with_capacity(capacity),
163        }
164    }
165
166    /// Reserve capacity for at least `additional` more key-value pairs.
167    pub fn reserve(&mut self, additional: usize) {
168        self.slots.reserve(additional);
169    }
170
171    /// Returns the number of elements in the map.
172    pub fn len(&self) -> usize {
173        self.slots.len()
174    }
175
176    /// Returns `true` if the map contains no elements.
177    pub fn is_empty(&self) -> bool {
178        self.len() == 0
179    }
180
181    /// Returns true if the map contains a value for the specified key.
182    ///
183    /// The key may be any borrowed form of the map’s key type,
184    /// but the ordering on the borrowed form must match the ordering on the key type.
185    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
186    where
187        K: Borrow<Q> + Ord,
188        Q: Ord,
189    {
190        self.key2slot.contains_key(key)
191    }
192
193    /// Inserts a key-value pair into the map.
194    ///
195    /// If the map did not have this key present, `None` is returned.
196    ///
197    /// If the map did have this key present, the value is updated, and the old
198    /// value is returned. The key is not updated, though; this matters for
199    /// types that can be `==` without being identical.
200    pub fn insert(&mut self, key: K, value: V) -> Option<V>
201    where
202        K: Ord + Clone,
203    {
204        self.insert_full(key, value).1
205    }
206
207    /// Inserts a key-value pair into the map.
208    ///
209    /// Returns the unique index to the key-value pair alongside the previous value.
210    ///
211    /// If the map did not have this key present, `None` is returned.
212    ///
213    /// If the map did have this key present, the value is updated, and the old
214    /// value is returned. The key is not updated, though; this matters for
215    /// types that can be `==` without being identical.
216    pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>)
217    where
218        K: Ord + Clone,
219    {
220        match self.key2slot.entry(key.clone()) {
221            btree_map::Entry::Vacant(entry) => {
222                let index = self.slots.len();
223                entry.insert(SlotIndex(index));
224                self.slots.push(Slot::new(key, value));
225                (index, None)
226            }
227            btree_map::Entry::Occupied(entry) => {
228                let index = entry.get().index();
229                let new_slot = Slot::new(key, value);
230                let old_slot = replace(&mut self.slots[index], new_slot);
231                (index, Some(old_slot.value))
232            }
233        }
234    }
235
236    /// Remove the key-value pair equivalent to `key` and return it and
237    /// the index it had.
238    ///
239    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
240    /// last element of the map and popping it off. **This perturbs
241    /// the position of what used to be the last element!**
242    ///
243    /// Return `None` if `key` is not in map.
244    pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
245    where
246        K: Borrow<Q> + Ord,
247        Q: ?Sized + Ord,
248    {
249        self.swap_remove_full(key)
250            .map(|(_index, _key, value)| value)
251    }
252
253    /// Remove and return the key-value pair equivalent to `key`.
254    ///
255    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
256    /// last element of the map and popping it off. **This perturbs
257    /// the position of what used to be the last element!**
258    ///
259    /// Return `None` if `key` is not in map.
260    ///
261    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
262    pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
263    where
264        K: Borrow<Q> + Ord,
265        Q: ?Sized + Ord,
266    {
267        self.swap_remove_full(key)
268            .map(|(_index, key, value)| (key, value))
269    }
270
271    /// Remove the key-value pair equivalent to `key` and return it and
272    /// the index it had.
273    ///
274    /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
275    /// last element of the map and popping it off. **This perturbs
276    /// the position of what used to be the last element!**
277    ///
278    /// Return `None` if `key` is not in map.
279    pub fn swap_remove_full<Q>(&mut self, key: &Q) -> Option<(usize, K, V)>
280    where
281        K: Borrow<Q> + Ord,
282        Q: ?Sized + Ord,
283    {
284        let index = self.key2slot.remove(key)?.0;
285        let removed = self.slots.swap_remove(index);
286        if index != self.len() {
287            // If the index was referring the last element
288            // `swap_remove` would not swap any other element
289            // thus adjustments are only needed if this was not the case.
290            let swapped = self.slots[index].key.borrow();
291            let swapped_index = self
292                .key2slot
293                .get_mut(swapped)
294                .expect("the swapped entry's key must be present");
295            *swapped_index = SlotIndex(index);
296        }
297        Some((index, removed.key, removed.value))
298    }
299
300    /// Gets the given key’s corresponding entry in the map for in-place manipulation.
301    pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
302    where
303        K: Ord + Clone,
304    {
305        match self.key2slot.entry(key) {
306            btree_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
307                vacant: entry,
308                slots: &mut self.slots,
309            }),
310            btree_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry {
311                occupied: entry,
312                slots: &mut self.slots,
313            }),
314        }
315    }
316
317    /// Returns a reference to the value corresponding to the key.
318    ///
319    /// The key may be any borrowed form of the map’s key type,
320    /// but the ordering on the borrowed form must match the ordering on the key type.
321    pub fn get<Q>(&self, key: &Q) -> Option<&V>
322    where
323        K: Borrow<Q> + Ord,
324        Q: ?Sized + Ord,
325    {
326        self.key2slot
327            .get(key)
328            .map(|slot| &self.slots[slot.index()].value)
329    }
330
331    /// Returns a mutable reference to the value corresponding to the key.
332    ///
333    /// The key may be any borrowed form of the map’s key type,
334    /// but the ordering on the borrowed form must match the ordering on the key type.
335    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
336    where
337        K: Borrow<Q> + Ord,
338        Q: Ord,
339    {
340        self.key2slot
341            .get(key)
342            .map(|slot| &mut self.slots[slot.index()].value)
343    }
344
345    /// Returns the key-value pair corresponding to the supplied key.
346    ///
347    /// The supplied key may be any borrowed form of the map's key type,
348    /// but the ordering on the borrowed form *must* match the ordering
349    /// on the key type.
350    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
351    where
352        K: Borrow<Q> + Ord,
353        Q: Ord,
354    {
355        self.key2slot
356            .get_key_value(key)
357            .map(|(key, slot)| (key, &self.slots[slot.index()].value))
358    }
359
360    /// Returns the key-value pair corresponding to the supplied key
361    /// as well as the unique index of the returned key-value pair.
362    ///
363    /// The supplied key may be any borrowed form of the map's key type,
364    /// but the ordering on the borrowed form *must* match the ordering
365    /// on the key type.
366    pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
367    where
368        K: Borrow<Q> + Ord,
369        Q: Ord,
370    {
371        self.key2slot.get_key_value(key).map(|(key, slot)| {
372            let index = slot.index();
373            let value = &self.slots[index].value;
374            (index, key, value)
375        })
376    }
377
378    /// Returns the unique index corresponding to the supplied key.
379    ///
380    /// The supplied key may be any borrowed form of the map's key type,
381    /// but the ordering on the borrowed form *must* match the ordering
382    /// on the key type.
383    pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
384    where
385        K: Borrow<Q> + Ord,
386        Q: Ord,
387    {
388        self.key2slot.get(key).copied().map(SlotIndex::index)
389    }
390
391    /// Returns a shared reference to the key-value pair at the given index.
392    pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
393        self.slots.get(index).map(Slot::as_pair)
394    }
395
396    /// Returns an exclusive reference to the key-value pair at the given index.
397    pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
398        self.slots.get_mut(index).map(Slot::as_pair_mut)
399    }
400
401    /// Gets an iterator over the entries of the map, sorted by key.
402    pub fn iter(&self) -> Iter<'_, K, V> {
403        Iter {
404            iter: self.slots.iter(),
405        }
406    }
407
408    /// Gets a mutable iterator over the entries of the map, sorted by key.
409    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
410        IterMut {
411            iter: self.slots.iter_mut(),
412        }
413    }
414
415    /// Gets an iterator over the values of the map, in order by key.
416    pub fn keys(&self) -> Keys<'_, K, V> {
417        Keys {
418            iter: self.slots.iter(),
419        }
420    }
421
422    /// Gets an iterator over the values of the map, in order by key.
423    pub fn values(&self) -> Values<'_, K, V> {
424        Values {
425            iter: self.slots.iter(),
426        }
427    }
428
429    /// Gets a mutable iterator over the values of the map, in order by key.
430    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
431        ValuesMut {
432            iter: self.slots.iter_mut(),
433        }
434    }
435
436    /// Clears the map, removing all elements.
437    pub fn clear(&mut self) {
438        self.key2slot.clear();
439        self.slots.clear();
440    }
441}
442
443impl<'a, K, Q, V> Index<&'a Q> for IndexMap<K, V>
444where
445    K: Borrow<Q> + Ord,
446    Q: ?Sized + Ord,
447{
448    type Output = V;
449
450    fn index(&self, key: &'a Q) -> &Self::Output {
451        self.get(key).expect("no entry found for key")
452    }
453}
454
455impl<K, V> Index<usize> for IndexMap<K, V> {
456    type Output = V;
457
458    fn index(&self, index: usize) -> &Self::Output {
459        let (_key, value) = self
460            .get_index(index)
461            .expect("IndexMap: index out of bounds");
462        value
463    }
464}
465
466impl<K, V> IndexMut<usize> for IndexMap<K, V> {
467    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
468        let (_key, value) = self
469            .get_index_mut(index)
470            .expect("IndexMap: index out of bounds");
471        value
472    }
473}
474
475impl<'a, K, V> Extend<(&'a K, &'a V)> for IndexMap<K, V>
476where
477    K: Ord + Copy,
478    V: Copy,
479{
480    fn extend<T>(&mut self, iter: T)
481    where
482        T: IntoIterator<Item = (&'a K, &'a V)>,
483    {
484        self.extend(iter.into_iter().map(|(key, value)| (*key, *value)))
485    }
486}
487
488impl<K, V> Extend<(K, V)> for IndexMap<K, V>
489where
490    K: Ord + Clone,
491{
492    fn extend<T>(&mut self, iter: T)
493    where
494        T: IntoIterator<Item = (K, V)>,
495    {
496        iter.into_iter().for_each(move |(k, v)| {
497            self.insert(k, v);
498        });
499    }
500}
501
502impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
503where
504    K: Ord + Clone,
505{
506    fn from_iter<T>(iter: T) -> Self
507    where
508        T: IntoIterator<Item = (K, V)>,
509    {
510        let mut map = IndexMap::new();
511        map.extend(iter);
512        map
513    }
514}
515
516impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V>
517where
518    K: Ord + Clone,
519{
520    fn from(items: [(K, V); N]) -> Self {
521        items.into_iter().collect()
522    }
523}
524
525impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
526    type Item = (&'a K, &'a V);
527    type IntoIter = Iter<'a, K, V>;
528
529    fn into_iter(self) -> Self::IntoIter {
530        self.iter()
531    }
532}
533
534impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
535    type Item = (&'a K, &'a mut V);
536    type IntoIter = IterMut<'a, K, V>;
537
538    fn into_iter(self) -> Self::IntoIter {
539        self.iter_mut()
540    }
541}
542
543impl<K, V> IntoIterator for IndexMap<K, V> {
544    type Item = (K, V);
545    type IntoIter = IntoIter<K, V>;
546
547    fn into_iter(self) -> Self::IntoIter {
548        IntoIter {
549            iter: self.slots.into_iter(),
550        }
551    }
552}
553
554/// An iterator over the entries of an [`IndexMap`].
555///
556/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
557/// documentation for more.
558///
559/// [`iter`]: IndexMap::iter
560#[derive(Debug, Clone)]
561pub struct Iter<'a, K, V> {
562    iter: SliceIter<'a, Slot<K, V>>,
563}
564
565impl<'a, K, V> Iterator for Iter<'a, K, V> {
566    type Item = (&'a K, &'a V);
567
568    fn size_hint(&self) -> (usize, Option<usize>) {
569        self.iter.size_hint()
570    }
571
572    fn count(self) -> usize {
573        self.iter.count()
574    }
575
576    fn next(&mut self) -> Option<Self::Item> {
577        self.iter.next().map(Slot::as_pair)
578    }
579}
580
581impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
582    fn next_back(&mut self) -> Option<Self::Item> {
583        self.iter.next_back().map(Slot::as_pair)
584    }
585}
586
587impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
588    fn len(&self) -> usize {
589        self.iter.len()
590    }
591}
592
593impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
594
595/// A mutable iterator over the entries of an [`IndexMap`].
596///
597/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
598/// documentation for more.
599///
600/// [`iter_mut`]: IndexMap::iter_mut
601#[derive(Debug)]
602pub struct IterMut<'a, K, V> {
603    iter: SliceIterMut<'a, Slot<K, V>>,
604}
605
606impl<'a, K, V> Iterator for IterMut<'a, K, V> {
607    type Item = (&'a K, &'a mut V);
608
609    fn size_hint(&self) -> (usize, Option<usize>) {
610        self.iter.size_hint()
611    }
612
613    fn count(self) -> usize {
614        self.iter.count()
615    }
616
617    fn next(&mut self) -> Option<Self::Item> {
618        self.iter.next().map(Slot::as_pair_mut)
619    }
620}
621
622impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
623    fn next_back(&mut self) -> Option<Self::Item> {
624        self.iter.next_back().map(Slot::as_pair_mut)
625    }
626}
627
628impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
629    fn len(&self) -> usize {
630        self.iter.len()
631    }
632}
633
634impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
635
636/// An owning iterator over the entries of a [`IndexMap`].
637///
638/// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
639/// (provided by the [`IntoIterator`] trait). See its documentation for more.
640///
641/// [`into_iter`]: IntoIterator::into_iter
642/// [`IntoIterator`]: core::iter::IntoIterator
643#[derive(Debug)]
644pub struct IntoIter<K, V> {
645    iter: VecIntoIter<Slot<K, V>>,
646}
647
648impl<K, V> Iterator for IntoIter<K, V> {
649    type Item = (K, V);
650
651    fn size_hint(&self) -> (usize, Option<usize>) {
652        self.iter.size_hint()
653    }
654
655    fn count(self) -> usize {
656        self.iter.count()
657    }
658
659    fn next(&mut self) -> Option<Self::Item> {
660        self.iter.next().map(Slot::into_pair)
661    }
662}
663
664impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
665    fn next_back(&mut self) -> Option<Self::Item> {
666        self.iter.next_back().map(Slot::into_pair)
667    }
668}
669
670impl<K, V> ExactSizeIterator for IntoIter<K, V> {
671    fn len(&self) -> usize {
672        self.iter.len()
673    }
674}
675
676impl<K, V> FusedIterator for IntoIter<K, V> {}
677
678/// An iterator over the keys of an [`IndexMap`].
679///
680/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
681/// documentation for more.
682///
683/// [`keys`]: IndexMap::keys
684#[derive(Debug, Clone)]
685pub struct Keys<'a, K, V> {
686    iter: SliceIter<'a, Slot<K, V>>,
687}
688
689impl<'a, K, V> Iterator for Keys<'a, K, V> {
690    type Item = &'a K;
691
692    fn size_hint(&self) -> (usize, Option<usize>) {
693        self.iter.size_hint()
694    }
695
696    fn count(self) -> usize {
697        self.iter.count()
698    }
699
700    fn next(&mut self) -> Option<Self::Item> {
701        self.iter.next().map(Slot::key)
702    }
703}
704
705impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
706    fn next_back(&mut self) -> Option<Self::Item> {
707        self.iter.next_back().map(Slot::key)
708    }
709}
710
711impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
712    fn len(&self) -> usize {
713        self.iter.len()
714    }
715}
716
717impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
718
719/// An iterator over the values of an [`IndexMap`].
720///
721/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
722/// documentation for more.
723///
724/// [`values`]: IndexMap::values
725#[derive(Debug, Clone)]
726pub struct Values<'a, K, V> {
727    iter: SliceIter<'a, Slot<K, V>>,
728}
729
730impl<'a, K, V> Iterator for Values<'a, K, V> {
731    type Item = &'a V;
732
733    fn size_hint(&self) -> (usize, Option<usize>) {
734        self.iter.size_hint()
735    }
736
737    fn count(self) -> usize {
738        self.iter.count()
739    }
740
741    fn next(&mut self) -> Option<Self::Item> {
742        self.iter.next().map(Slot::value)
743    }
744}
745
746impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
747    fn next_back(&mut self) -> Option<Self::Item> {
748        self.iter.next_back().map(Slot::value)
749    }
750}
751
752impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
753    fn len(&self) -> usize {
754        self.iter.len()
755    }
756}
757
758impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
759
760/// An iterator over the values of an [`IndexMap`].
761///
762/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
763/// documentation for more.
764///
765/// [`values`]: IndexMap::values
766#[derive(Debug)]
767pub struct ValuesMut<'a, K, V> {
768    iter: SliceIterMut<'a, Slot<K, V>>,
769}
770
771impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
772    type Item = &'a mut V;
773
774    fn size_hint(&self) -> (usize, Option<usize>) {
775        self.iter.size_hint()
776    }
777
778    fn count(self) -> usize {
779        self.iter.count()
780    }
781
782    fn next(&mut self) -> Option<Self::Item> {
783        self.iter.next().map(Slot::value_mut)
784    }
785}
786
787impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
788    fn next_back(&mut self) -> Option<Self::Item> {
789        self.iter.next_back().map(Slot::value_mut)
790    }
791}
792
793impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
794    fn len(&self) -> usize {
795        self.iter.len()
796    }
797}
798
799impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
800
801/// A view into a single entry in a map, which may either be vacant or occupied.
802///
803/// This `enum` is constructed from the [`entry`] method on [`IndexMap`].
804///
805/// [`entry`]: IndexMap::entry
806pub enum Entry<'a, K, V> {
807    /// A vacant entry.
808    Vacant(VacantEntry<'a, K, V>),
809    /// An occupied entry.
810    Occupied(OccupiedEntry<'a, K, V>),
811}
812
813impl<'a, K: Ord, V> Entry<'a, K, V> {
814    /// Ensures a value is in the entry by inserting the default if empty,
815    /// and returns a mutable reference to the value in the entry.
816    pub fn or_insert(self, default: V) -> &'a mut V
817    where
818        K: Clone,
819    {
820        match self {
821            Self::Occupied(entry) => entry.into_mut(),
822            Self::Vacant(entry) => entry.insert(default),
823        }
824    }
825
826    /// Ensures a value is in the entry by inserting the result
827    /// of the default function if empty,
828    /// and returns a mutable reference to the value in the entry.
829    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
830    where
831        K: Clone,
832    {
833        match self {
834            Self::Occupied(entry) => entry.into_mut(),
835            Self::Vacant(entry) => entry.insert(default()),
836        }
837    }
838
839    /// Ensures a value is in the entry by inserting,
840    /// if empty, the result of the default function.
841    ///
842    /// This method allows for generating key-derived values for
843    /// insertion by providing the default function a reference
844    /// to the key that was moved during the `.entry(key)` method call.
845    ///
846    /// The reference to the moved key is provided
847    /// so that cloning or copying the key is
848    /// unnecessary, unlike with `.or_insert_with(|| ... )`.
849    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V
850    where
851        K: Clone,
852    {
853        match self {
854            Self::Occupied(entry) => entry.into_mut(),
855            Self::Vacant(entry) => {
856                let value = default(entry.key());
857                entry.insert(value)
858            }
859        }
860    }
861
862    /// Returns a reference to this entry’s key.
863    pub fn key(&self) -> &K {
864        match *self {
865            Self::Occupied(ref entry) => entry.key(),
866            Self::Vacant(ref entry) => entry.key(),
867        }
868    }
869
870    /// Provides in-place mutable access to an occupied entry
871    /// before any potential inserts into the map.
872    pub fn and_modify<F>(self, f: F) -> Self
873    where
874        F: FnOnce(&mut V),
875    {
876        match self {
877            Self::Occupied(mut entry) => {
878                f(entry.get_mut());
879                Self::Occupied(entry)
880            }
881            Self::Vacant(entry) => Self::Vacant(entry),
882        }
883    }
884}
885
886impl<'a, K, V> Entry<'a, K, V>
887where
888    K: Ord + Clone,
889    V: Default,
890{
891    /// Ensures a value is in the entry by inserting the default value if empty,
892    /// and returns a mutable reference to the value in the entry.
893    pub fn or_default(self) -> &'a mut V {
894        match self {
895            Self::Occupied(entry) => entry.into_mut(),
896            Self::Vacant(entry) => entry.insert(Default::default()),
897        }
898    }
899}
900
901impl<'a, K, V> fmt::Debug for Entry<'a, K, V>
902where
903    K: fmt::Debug + Ord,
904    V: fmt::Debug,
905{
906    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
907        match self {
908            Entry::Vacant(entry) => entry.fmt(f),
909            Entry::Occupied(entry) => entry.fmt(f),
910        }
911    }
912}
913
914/// A view into a vacant entry in an [`IndexMap`]. It is part of the [`Entry`] `enum`.
915pub struct VacantEntry<'a, K, V> {
916    /// The underlying vacant entry.
917    vacant: btree_map::VacantEntry<'a, K, SlotIndex>,
918    /// The vector that stores all slots.
919    slots: &'a mut Vec<Slot<K, V>>,
920}
921
922impl<'a, K, V> VacantEntry<'a, K, V>
923where
924    K: Ord,
925{
926    /// Gets a reference to the key that would be used when inserting a value through the VacantEntry.
927    pub fn key(&self) -> &K {
928        self.vacant.key()
929    }
930
931    /// Take ownership of the key.
932    pub fn into_key(self) -> K {
933        self.vacant.into_key()
934    }
935
936    /// Sets the value of the entry with the `VacantEntry`’s key,
937    /// and returns a mutable reference to it.
938    pub fn insert(self, value: V) -> &'a mut V
939    where
940        K: Clone,
941    {
942        let index = self.slots.len();
943        let key = self.vacant.key().clone();
944        self.vacant.insert(SlotIndex(index));
945        self.slots.push(Slot::new(key, value));
946        &mut self.slots[index].value
947    }
948}
949
950impl<'a, K, V> fmt::Debug for VacantEntry<'a, K, V>
951where
952    K: fmt::Debug + Ord,
953{
954    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
955        f.debug_struct("VacantEntry")
956            .field("key", self.key())
957            .finish()
958    }
959}
960
961/// A view into an occupied entry in a [`IndexMap`]. It is part of the [`Entry`] `enum`.
962pub struct OccupiedEntry<'a, K, V> {
963    /// The underlying occupied entry.
964    occupied: btree_map::OccupiedEntry<'a, K, SlotIndex>,
965    /// The vector that stores all slots.
966    slots: &'a mut Vec<Slot<K, V>>,
967}
968
969impl<'a, K, V> OccupiedEntry<'a, K, V>
970where
971    K: Ord,
972{
973    /// Gets a reference to the key in the entry.
974    pub fn key(&self) -> &K {
975        self.occupied.key()
976    }
977
978    /// Gets a reference to the value in the entry.
979    pub fn get(&self) -> &V {
980        let index = self.occupied.get().index();
981        &self.slots[index].value
982    }
983
984    /// Gets a mutable reference to the value in the entry.
985    ///
986    /// If you need a reference to the `OccupiedEntry` that may outlive the
987    /// destruction of the `Entry` value, see [`into_mut`].
988    ///
989    /// [`into_mut`]: OccupiedEntry::into_mut
990    pub fn get_mut(&mut self) -> &mut V {
991        let index = self.occupied.get().index();
992        &mut self.slots[index].value
993    }
994
995    /// Converts the entry into a mutable reference to its value.
996    ///
997    /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
998    ///
999    /// [`get_mut`]: OccupiedEntry::get_mut
1000    pub fn into_mut(self) -> &'a mut V {
1001        let index = self.occupied.get().index();
1002        &mut self.slots[index].value
1003    }
1004
1005    /// Sets the value of the entry with the `OccupiedEntry`’s key,
1006    /// and returns the entry’s old value.
1007    pub fn insert(&mut self, value: V) -> V
1008    where
1009        K: Clone,
1010    {
1011        let index = self.occupied.get().index();
1012        let key = self.key().clone();
1013        let new_slot = Slot::new(key, value);
1014        let old_slot = replace(&mut self.slots[index], new_slot);
1015        old_slot.value
1016    }
1017}
1018
1019impl<'a, K, V> fmt::Debug for OccupiedEntry<'a, K, V>
1020where
1021    K: fmt::Debug + Ord,
1022    V: fmt::Debug,
1023{
1024    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1025        f.debug_struct("OccupiedEntry")
1026            .field("key", self.key())
1027            .field("value", self.get())
1028            .finish()
1029    }
1030}
1031
1032#[cfg(feature = "serde")]
1033mod serde_impls {
1034    use super::IndexMap;
1035    use core::fmt;
1036    use core::marker::PhantomData;
1037    use serde::de::{Deserialize, MapAccess, Visitor};
1038    use serde::ser::{Serialize, SerializeMap, Serializer};
1039
1040    impl<K, V> Serialize for IndexMap<K, V>
1041    where
1042        K: Serialize + Ord,
1043        V: Serialize,
1044    {
1045        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1046        where
1047            S: Serializer,
1048        {
1049            let mut map = serializer.serialize_map(Some(self.len()))?;
1050            for (k, v) in self.iter() {
1051                map.serialize_entry(k, v)?;
1052            }
1053            map.end()
1054        }
1055    }
1056
1057    impl<'a, K, V> Deserialize<'a> for IndexMap<K, V>
1058    where
1059        K: Deserialize<'a> + Clone + Ord,
1060        V: Deserialize<'a>,
1061    {
1062        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1063        where
1064            D: serde::de::Deserializer<'a>,
1065        {
1066            deserializer.deserialize_map(IndexMapVisitor {
1067                _marker: PhantomData,
1068            })
1069        }
1070    }
1071
1072    struct IndexMapVisitor<K, V> {
1073        _marker: PhantomData<fn() -> IndexMap<K, V>>,
1074    }
1075
1076    impl<'de, K, V> Visitor<'de> for IndexMapVisitor<K, V>
1077    where
1078        K: Deserialize<'de> + Clone + Ord,
1079        V: Deserialize<'de>,
1080    {
1081        type Value = IndexMap<K, V>;
1082
1083        fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1084            formatter.write_str("a map")
1085        }
1086
1087        fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
1088        where
1089            M: MapAccess<'de>,
1090        {
1091            let mut map = IndexMap::with_capacity(access.size_hint().unwrap_or(0));
1092
1093            while let Some((key, value)) = access.next_entry()? {
1094                map.insert(key, value);
1095            }
1096
1097            Ok(map)
1098        }
1099    }
1100}
wasmparser/collections/index_map/detail.rs

wasmparser/collections/index_map/
detail.rs
