Source code
Revision control
Copy as Markdown
Other Tools
//! An ordered map based on a B-Tree that keeps insertion order of elements.
#[cfg(not(feature = "no-hash-maps"))]
mod impls {
use crate::collections::hash;
use indexmap::IndexMap;
pub type IndexMapImpl<K, V> = IndexMap<K, V, hash::RandomState>;
pub type EntryImpl<'a, K, V> = indexmap::map::Entry<'a, K, V>;
pub type OccupiedEntryImpl<'a, K, V> = indexmap::map::OccupiedEntry<'a, K, V>;
pub type VacantEntryImpl<'a, K, V> = indexmap::map::VacantEntry<'a, K, V>;
pub type IterImpl<'a, K, V> = indexmap::map::Iter<'a, K, V>;
pub type IterMutImpl<'a, K, V> = indexmap::map::IterMut<'a, K, V>;
pub type IntoIterImpl<K, V> = indexmap::map::IntoIter<K, V>;
pub type KeysImpl<'a, K, V> = indexmap::map::Keys<'a, K, V>;
pub type ValuesImpl<'a, K, V> = indexmap::map::Values<'a, K, V>;
pub type ValuesMutImpl<'a, K, V> = indexmap::map::ValuesMut<'a, K, V>;
}
#[cfg(feature = "no-hash-maps")]
mod impls {
pub type IndexMapImpl<K, V> = super::IndexMap<K, V>;
pub type EntryImpl<'a, K, V> = super::Entry<'a, K, V>;
pub type OccupiedEntryImpl<'a, K, V> = super::OccupiedEntry<'a, K, V>;
pub type VacantEntryImpl<'a, K, V> = super::VacantEntry<'a, K, V>;
pub type IterImpl<'a, K, V> = super::Iter<'a, K, V>;
pub type IterMutImpl<'a, K, V> = super::IterMut<'a, K, V>;
pub type IntoIterImpl<K, V> = super::IntoIter<K, V>;
pub type KeysImpl<'a, K, V> = super::Keys<'a, K, V>;
pub type ValuesImpl<'a, K, V> = super::Values<'a, K, V>;
pub type ValuesMutImpl<'a, K, V> = super::ValuesMut<'a, K, V>;
}
pub use self::impls::*;
use alloc::collections::{btree_map, BTreeMap};
use alloc::vec::IntoIter as VecIntoIter;
use alloc::vec::Vec;
use core::borrow::Borrow;
use core::fmt;
use core::iter::FusedIterator;
use core::mem::replace;
use core::ops::{Index, IndexMut};
use core::slice::Iter as SliceIter;
use core::slice::IterMut as SliceIterMut;
/// A slot index referencing a slot in an [`IndexMap`].
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct SlotIndex(usize);
impl SlotIndex {
/// Returns the raw `usize` index of the [`SlotIndex`].
pub fn index(self) -> usize {
self.0
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Slot<K, V> {
/// The key of the [`Slot`].
key: K,
/// The value of the [`Slot`].
value: V,
}
impl<K, V> Slot<K, V> {
/// Creates a new [`Slot`] from the given `key` and `value`.
pub fn new(key: K, value: V) -> Self {
Self { key, value }
}
/// Returns the [`Slot`] as a pair of references to its `key` and `value`.
pub fn as_pair(&self) -> (&K, &V) {
(&self.key, &self.value)
}
/// Returns the [`Slot`] as a pair of references to its `key` and `value`.
pub fn as_pair_mut(&mut self) -> (&K, &mut V) {
(&self.key, &mut self.value)
}
/// Converts the [`Slot`] into a pair of its `key` and `value`.
pub fn into_pair(self) -> (K, V) {
(self.key, self.value)
}
/// Returns a shared reference to the key of the [`Slot`].
pub fn key(&self) -> &K {
&self.key
}
/// Returns a shared reference to the value of the [`Slot`].
pub fn value(&self) -> &V {
&self.value
}
/// Returns an exclusive reference to the value of the [`Slot`].
pub fn value_mut(&mut self) -> &mut V {
&mut self.value
}
}
/// A b-tree map where the iteration order of the key-value
/// pairs is independent of the ordering of the keys.
///
/// The interface is closely compatible with the [`indexmap` crate]
/// and a subset of the features that is relevant for the
/// [`wasmparser-nostd` crate].
///
/// # Differences to original `IndexMap`
///
/// Since the goal of this crate was to maintain a simple
/// `no_std` compatible fork of the [`indexmap` crate] there are some
/// downsides and differences.
///
/// - Some operations such as `IndexMap::insert` now require `K: Clone`.
/// - It is to be expected that this fork performs worse than the original
/// [`indexmap` crate] implementation.
/// - The implementation is based on `BTreeMap` internally instead of
/// `HashMap` which has the effect that methods no longer require `K: Hash`
/// but `K: Ord` instead.
///
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct IndexMap<K, V> {
/// A mapping from keys to slot indices.
key2slot: BTreeMap<K, SlotIndex>,
/// A vector holding all slots of key value pairs.
slots: Vec<Slot<K, V>>,
}
impl<K, V> Default for IndexMap<K, V> {
fn default() -> Self {
Self::new()
}
}
impl<K, V> IndexMap<K, V> {
/// Makes a new, empty [`IndexMap`].
///
/// Does not allocate anything on its own.
pub fn new() -> Self {
Self {
key2slot: BTreeMap::new(),
slots: Vec::new(),
}
}
/// Constructs a new, empty [`IndexMap`] with at least the specified capacity.
///
/// Does not allocate if `capacity` is zero.
pub fn with_capacity(capacity: usize) -> Self {
Self {
key2slot: BTreeMap::new(),
slots: Vec::with_capacity(capacity),
}
}
/// Reserve capacity for at least `additional` more key-value pairs.
pub fn reserve(&mut self, additional: usize) {
self.slots.reserve(additional);
}
/// Returns the number of elements in the map.
pub fn len(&self) -> usize {
self.slots.len()
}
/// Returns `true` if the map contains no elements.
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Returns true if the map contains a value for the specified key.
///
/// The key may be any borrowed form of the map’s key type,
/// but the ordering on the borrowed form must match the ordering on the key type.
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
where
K: Borrow<Q> + Ord,
Q: Ord,
{
self.key2slot.contains_key(key)
}
/// Inserts a key-value pair into the map.
///
/// If the map did not have this key present, `None` is returned.
///
/// If the map did have this key present, the value is updated, and the old
/// value is returned. The key is not updated, though; this matters for
/// types that can be `==` without being identical.
pub fn insert(&mut self, key: K, value: V) -> Option<V>
where
K: Ord + Clone,
{
self.insert_full(key, value).1
}
/// Inserts a key-value pair into the map.
///
/// Returns the unique index to the key-value pair alongside the previous value.
///
/// If the map did not have this key present, `None` is returned.
///
/// If the map did have this key present, the value is updated, and the old
/// value is returned. The key is not updated, though; this matters for
/// types that can be `==` without being identical.
pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>)
where
K: Ord + Clone,
{
match self.key2slot.entry(key.clone()) {
btree_map::Entry::Vacant(entry) => {
let index = self.slots.len();
entry.insert(SlotIndex(index));
self.slots.push(Slot::new(key, value));
(index, None)
}
btree_map::Entry::Occupied(entry) => {
let index = entry.get().index();
let new_slot = Slot::new(key, value);
let old_slot = replace(&mut self.slots[index], new_slot);
(index, Some(old_slot.value))
}
}
}
/// Remove the key-value pair equivalent to `key` and return it and
/// the index it had.
///
/// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
/// last element of the map and popping it off. **This perturbs
/// the position of what used to be the last element!**
///
/// Return `None` if `key` is not in map.
pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q> + Ord,
Q: ?Sized + Ord,
{
self.swap_remove_full(key)
.map(|(_index, _key, value)| value)
}
/// Remove and return the key-value pair equivalent to `key`.
///
/// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
/// last element of the map and popping it off. **This perturbs
/// the position of what used to be the last element!**
///
/// Return `None` if `key` is not in map.
///
/// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Ord,
Q: ?Sized + Ord,
{
self.swap_remove_full(key)
.map(|(_index, key, value)| (key, value))
}
/// Remove the key-value pair equivalent to `key` and return it and
/// the index it had.
///
/// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
/// last element of the map and popping it off. **This perturbs
/// the position of what used to be the last element!**
///
/// Return `None` if `key` is not in map.
pub fn swap_remove_full<Q>(&mut self, key: &Q) -> Option<(usize, K, V)>
where
K: Borrow<Q> + Ord,
Q: ?Sized + Ord,
{
let index = self.key2slot.remove(key)?.0;
let removed = self.slots.swap_remove(index);
if index != self.len() {
// If the index was referring the last element
// `swap_remove` would not swap any other element
// thus adjustments are only needed if this was not the case.
let swapped = self.slots[index].key.borrow();
let swapped_index = self
.key2slot
.get_mut(swapped)
.expect("the swapped entry's key must be present");
*swapped_index = SlotIndex(index);
}
Some((index, removed.key, removed.value))
}
/// Gets the given key’s corresponding entry in the map for in-place manipulation.
pub fn entry(&mut self, key: K) -> Entry<K, V>
where
K: Ord + Clone,
{
match self.key2slot.entry(key) {
btree_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
vacant: entry,
slots: &mut self.slots,
}),
btree_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry {
occupied: entry,
slots: &mut self.slots,
}),
}
}
/// Returns a reference to the value corresponding to the key.
///
/// The key may be any borrowed form of the map’s key type,
/// but the ordering on the borrowed form must match the ordering on the key type.
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q> + Ord,
Q: ?Sized + Ord,
{
self.key2slot
.get(key)
.map(|slot| &self.slots[slot.index()].value)
}
/// Returns a mutable reference to the value corresponding to the key.
///
/// The key may be any borrowed form of the map’s key type,
/// but the ordering on the borrowed form must match the ordering on the key type.
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q> + Ord,
Q: Ord,
{
self.key2slot
.get(key)
.map(|slot| &mut self.slots[slot.index()].value)
}
/// Returns the key-value pair corresponding to the supplied key.
///
/// The supplied key may be any borrowed form of the map's key type,
/// but the ordering on the borrowed form *must* match the ordering
/// on the key type.
pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q> + Ord,
Q: Ord,
{
self.key2slot
.get_key_value(key)
.map(|(key, slot)| (key, &self.slots[slot.index()].value))
}
/// Returns the key-value pair corresponding to the supplied key
/// as well as the unique index of the returned key-value pair.
///
/// The supplied key may be any borrowed form of the map's key type,
/// but the ordering on the borrowed form *must* match the ordering
/// on the key type.
pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
where
K: Borrow<Q> + Ord,
Q: Ord,
{
self.key2slot.get_key_value(key).map(|(key, slot)| {
let index = slot.index();
let value = &self.slots[index].value;
(index, key, value)
})
}
/// Returns the unique index corresponding to the supplied key.
///
/// The supplied key may be any borrowed form of the map's key type,
/// but the ordering on the borrowed form *must* match the ordering
/// on the key type.
pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
where
K: Borrow<Q> + Ord,
Q: Ord,
{
self.key2slot.get(key).copied().map(SlotIndex::index)
}
/// Returns a shared reference to the key-value pair at the given index.
pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
self.slots.get(index).map(Slot::as_pair)
}
/// Returns an exclusive reference to the key-value pair at the given index.
pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
self.slots.get_mut(index).map(Slot::as_pair_mut)
}
/// Gets an iterator over the entries of the map, sorted by key.
pub fn iter(&self) -> Iter<K, V> {
Iter {
iter: self.slots.iter(),
}
}
/// Gets a mutable iterator over the entries of the map, sorted by key.
pub fn iter_mut(&mut self) -> IterMut<K, V> {
IterMut {
iter: self.slots.iter_mut(),
}
}
/// Gets an iterator over the values of the map, in order by key.
pub fn keys(&self) -> Keys<K, V> {
Keys {
iter: self.slots.iter(),
}
}
/// Gets an iterator over the values of the map, in order by key.
pub fn values(&self) -> Values<K, V> {
Values {
iter: self.slots.iter(),
}
}
/// Gets a mutable iterator over the values of the map, in order by key.
pub fn values_mut(&mut self) -> ValuesMut<K, V> {
ValuesMut {
iter: self.slots.iter_mut(),
}
}
/// Clears the map, removing all elements.
pub fn clear(&mut self) {
self.key2slot.clear();
self.slots.clear();
}
}
impl<'a, K, Q, V> Index<&'a Q> for IndexMap<K, V>
where
K: Borrow<Q> + Ord,
Q: ?Sized + Ord,
{
type Output = V;
fn index(&self, key: &'a Q) -> &Self::Output {
self.get(key).expect("no entry found for key")
}
}
impl<K, V> Index<usize> for IndexMap<K, V> {
type Output = V;
fn index(&self, index: usize) -> &Self::Output {
let (_key, value) = self
.get_index(index)
.expect("IndexMap: index out of bounds");
value
}
}
impl<K, V> IndexMut<usize> for IndexMap<K, V> {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
let (_key, value) = self
.get_index_mut(index)
.expect("IndexMap: index out of bounds");
value
}
}
impl<'a, K, V> Extend<(&'a K, &'a V)> for IndexMap<K, V>
where
K: Ord + Copy,
V: Copy,
{
fn extend<T>(&mut self, iter: T)
where
T: IntoIterator<Item = (&'a K, &'a V)>,
{
self.extend(iter.into_iter().map(|(key, value)| (*key, *value)))
}
}
impl<K, V> Extend<(K, V)> for IndexMap<K, V>
where
K: Ord + Clone,
{
fn extend<T>(&mut self, iter: T)
where
T: IntoIterator<Item = (K, V)>,
{
iter.into_iter().for_each(move |(k, v)| {
self.insert(k, v);
});
}
}
impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
where
K: Ord + Clone,
{
fn from_iter<T>(iter: T) -> Self
where
T: IntoIterator<Item = (K, V)>,
{
let mut map = IndexMap::new();
map.extend(iter);
map
}
}
impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V>
where
K: Ord + Clone,
{
fn from(items: [(K, V); N]) -> Self {
items.into_iter().collect()
}
}
impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<K, V> IntoIterator for IndexMap<K, V> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
fn into_iter(self) -> Self::IntoIter {
IntoIter {
iter: self.slots.into_iter(),
}
}
}
/// An iterator over the entries of an [`IndexMap`].
///
/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
/// documentation for more.
///
/// [`iter`]: IndexMap::iter
#[derive(Debug, Clone)]
pub struct Iter<'a, K, V> {
iter: SliceIter<'a, Slot<K, V>>,
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn count(self) -> usize {
self.iter.count()
}
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(Slot::as_pair)
}
}
impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(Slot::as_pair)
}
}
impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
/// A mutable iterator over the entries of an [`IndexMap`].
///
/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
/// documentation for more.
///
/// [`iter_mut`]: IndexMap::iter_mut
#[derive(Debug)]
pub struct IterMut<'a, K, V> {
iter: SliceIterMut<'a, Slot<K, V>>,
}
impl<'a, K, V> Iterator for IterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn count(self) -> usize {
self.iter.count()
}
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(Slot::as_pair_mut)
}
}
impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(Slot::as_pair_mut)
}
}
impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
/// An owning iterator over the entries of a [`IndexMap`].
///
/// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
/// (provided by the [`IntoIterator`] trait). See its documentation for more.
///
/// [`into_iter`]: IntoIterator::into_iter
/// [`IntoIterator`]: core::iter::IntoIterator
#[derive(Debug)]
pub struct IntoIter<K, V> {
iter: VecIntoIter<Slot<K, V>>,
}
impl<K, V> Iterator for IntoIter<K, V> {
type Item = (K, V);
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn count(self) -> usize {
self.iter.count()
}
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(Slot::into_pair)
}
}
impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(Slot::into_pair)
}
}
impl<K, V> ExactSizeIterator for IntoIter<K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<K, V> FusedIterator for IntoIter<K, V> {}
/// An iterator over the keys of an [`IndexMap`].
///
/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
/// documentation for more.
///
/// [`keys`]: IndexMap::keys
#[derive(Debug, Clone)]
pub struct Keys<'a, K, V> {
iter: SliceIter<'a, Slot<K, V>>,
}
impl<'a, K, V> Iterator for Keys<'a, K, V> {
type Item = &'a K;
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn count(self) -> usize {
self.iter.count()
}
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(Slot::key)
}
}
impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(Slot::key)
}
}
impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
/// An iterator over the values of an [`IndexMap`].
///
/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
/// documentation for more.
///
/// [`values`]: IndexMap::values
#[derive(Debug, Clone)]
pub struct Values<'a, K, V> {
iter: SliceIter<'a, Slot<K, V>>,
}
impl<'a, K, V> Iterator for Values<'a, K, V> {
type Item = &'a V;
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn count(self) -> usize {
self.iter.count()
}
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(Slot::value)
}
}
impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(Slot::value)
}
}
impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
/// An iterator over the values of an [`IndexMap`].
///
/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
/// documentation for more.
///
/// [`values`]: IndexMap::values
#[derive(Debug)]
pub struct ValuesMut<'a, K, V> {
iter: SliceIterMut<'a, Slot<K, V>>,
}
impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
type Item = &'a mut V;
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
fn count(self) -> usize {
self.iter.count()
}
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(Slot::value_mut)
}
}
impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back().map(Slot::value_mut)
}
}
impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
/// A view into a single entry in a map, which may either be vacant or occupied.
///
/// This `enum` is constructed from the [`entry`] method on [`IndexMap`].
///
/// [`entry`]: IndexMap::entry
pub enum Entry<'a, K, V> {
/// A vacant entry.
Vacant(VacantEntry<'a, K, V>),
/// An occupied entry.
Occupied(OccupiedEntry<'a, K, V>),
}
impl<'a, K: Ord, V> Entry<'a, K, V> {
/// Ensures a value is in the entry by inserting the default if empty,
/// and returns a mutable reference to the value in the entry.
pub fn or_insert(self, default: V) -> &'a mut V
where
K: Clone,
{
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => entry.insert(default),
}
}
/// Ensures a value is in the entry by inserting the result
/// of the default function if empty,
/// and returns a mutable reference to the value in the entry.
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
where
K: Clone,
{
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => entry.insert(default()),
}
}
/// Ensures a value is in the entry by inserting,
/// if empty, the result of the default function.
///
/// This method allows for generating key-derived values for
/// insertion by providing the default function a reference
/// to the key that was moved during the `.entry(key)` method call.
///
/// The reference to the moved key is provided
/// so that cloning or copying the key is
/// unnecessary, unlike with `.or_insert_with(|| ... )`.
pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V
where
K: Clone,
{
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => {
let value = default(entry.key());
entry.insert(value)
}
}
}
/// Returns a reference to this entry’s key.
pub fn key(&self) -> &K {
match *self {
Self::Occupied(ref entry) => entry.key(),
Self::Vacant(ref entry) => entry.key(),
}
}
/// Provides in-place mutable access to an occupied entry
/// before any potential inserts into the map.
pub fn and_modify<F>(self, f: F) -> Self
where
F: FnOnce(&mut V),
{
match self {
Self::Occupied(mut entry) => {
f(entry.get_mut());
Self::Occupied(entry)
}
Self::Vacant(entry) => Self::Vacant(entry),
}
}
}
impl<'a, K, V> Entry<'a, K, V>
where
K: Ord + Clone,
V: Default,
{
/// Ensures a value is in the entry by inserting the default value if empty,
/// and returns a mutable reference to the value in the entry.
pub fn or_default(self) -> &'a mut V {
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => entry.insert(Default::default()),
}
}
}
impl<'a, K, V> fmt::Debug for Entry<'a, K, V>
where
K: fmt::Debug + Ord,
V: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Entry::Vacant(entry) => entry.fmt(f),
Entry::Occupied(entry) => entry.fmt(f),
}
}
}
/// A view into a vacant entry in an [`IndexMap`]. It is part of the [`Entry`] `enum`.
pub struct VacantEntry<'a, K, V> {
/// The underlying vacant entry.
vacant: btree_map::VacantEntry<'a, K, SlotIndex>,
/// The vector that stores all slots.
slots: &'a mut Vec<Slot<K, V>>,
}
impl<'a, K, V> VacantEntry<'a, K, V>
where
K: Ord,
{
/// Gets a reference to the key that would be used when inserting a value through the VacantEntry.
pub fn key(&self) -> &K {
self.vacant.key()
}
/// Take ownership of the key.
pub fn into_key(self) -> K {
self.vacant.into_key()
}
/// Sets the value of the entry with the `VacantEntry`’s key,
/// and returns a mutable reference to it.
pub fn insert(self, value: V) -> &'a mut V
where
K: Clone,
{
let index = self.slots.len();
let key = self.vacant.key().clone();
self.vacant.insert(SlotIndex(index));
self.slots.push(Slot::new(key, value));
&mut self.slots[index].value
}
}
impl<'a, K, V> fmt::Debug for VacantEntry<'a, K, V>
where
K: fmt::Debug + Ord,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("VacantEntry")
.field("key", self.key())
.finish()
}
}
/// A view into an occupied entry in a [`IndexMap`]. It is part of the [`Entry`] `enum`.
pub struct OccupiedEntry<'a, K, V> {
/// The underlying occupied entry.
occupied: btree_map::OccupiedEntry<'a, K, SlotIndex>,
/// The vector that stores all slots.
slots: &'a mut Vec<Slot<K, V>>,
}
impl<'a, K, V> OccupiedEntry<'a, K, V>
where
K: Ord,
{
/// Gets a reference to the key in the entry.
pub fn key(&self) -> &K {
self.occupied.key()
}
/// Gets a reference to the value in the entry.
pub fn get(&self) -> &V {
let index = self.occupied.get().index();
&self.slots[index].value
}
/// Gets a mutable reference to the value in the entry.
///
/// If you need a reference to the `OccupiedEntry` that may outlive the
/// destruction of the `Entry` value, see [`into_mut`].
///
/// [`into_mut`]: OccupiedEntry::into_mut
pub fn get_mut(&mut self) -> &mut V {
let index = self.occupied.get().index();
&mut self.slots[index].value
}
/// Converts the entry into a mutable reference to its value.
///
/// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
///
/// [`get_mut`]: OccupiedEntry::get_mut
pub fn into_mut(self) -> &'a mut V {
let index = self.occupied.get().index();
&mut self.slots[index].value
}
/// Sets the value of the entry with the `OccupiedEntry`’s key,
/// and returns the entry’s old value.
pub fn insert(&mut self, value: V) -> V
where
K: Clone,
{
let index = self.occupied.get().index();
let key = self.key().clone();
let new_slot = Slot::new(key, value);
let old_slot = replace(&mut self.slots[index], new_slot);
old_slot.value
}
}
impl<'a, K, V> fmt::Debug for OccupiedEntry<'a, K, V>
where
K: fmt::Debug + Ord,
V: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("OccupiedEntry")
.field("key", self.key())
.field("value", self.get())
.finish()
}
}
#[cfg(feature = "serde")]
mod serde_impls {
use super::IndexMap;
use core::fmt;
use core::marker::PhantomData;
use serde::de::{Deserialize, MapAccess, Visitor};
use serde::ser::{Serialize, SerializeMap, Serializer};
impl<K, V> Serialize for IndexMap<K, V>
where
K: Serialize + Ord,
V: Serialize,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
let mut map = serializer.serialize_map(Some(self.len()))?;
for (k, v) in self.iter() {
map.serialize_entry(k, v)?;
}
map.end()
}
}
impl<'a, K, V> Deserialize<'a> for IndexMap<K, V>
where
K: Deserialize<'a> + Clone + Ord,
V: Deserialize<'a>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::de::Deserializer<'a>,
{
deserializer.deserialize_map(IndexMapVisitor {
_marker: PhantomData,
})
}
}
struct IndexMapVisitor<K, V> {
_marker: PhantomData<fn() -> IndexMap<K, V>>,
}
impl<'de, K, V> Visitor<'de> for IndexMapVisitor<K, V>
where
K: Deserialize<'de> + Clone + Ord,
V: Deserialize<'de>,
{
type Value = IndexMap<K, V>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("a map")
}
fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
where
M: MapAccess<'de>,
{
let mut map = IndexMap::with_capacity(access.size_hint().unwrap_or(0));
while let Some((key, value)) = access.next_entry()? {
map.insert(key, value);
}
Ok(map)
}
}
}