/rust/registry/src/index.crates.io-1949cf8c6b5b557f/indexmap-2.13.0/src/inner/entry.rs

Source
use super::{equivalent, get_hash, Bucket, Core};
use crate::map::{Entry, IndexedEntry};
use crate::HashValue;
use core::cmp::Ordering;
use core::mem;

impl<'a, K, V> Entry<'a, K, V> {
    pub(crate) fn new(map: &'a mut Core<K, V>, hash: HashValue, key: K) -> Self
    where
        K: Eq,
    {
        let eq = equivalent(&key, &map.entries);
        match map.indices.find_entry(hash.get(), eq) {
            Ok(entry) => Entry::Occupied(OccupiedEntry {
                bucket: entry.bucket_index(),
                index: *entry.get(),
                map,
            }),
            Err(_) => Entry::Vacant(VacantEntry { map, hash, key }),
        }
    }
}

/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap].
/// It is part of the [`Entry`] enum.
pub struct OccupiedEntry<'a, K, V> {
    map: &'a mut Core<K, V>,
    // We have a mutable reference to the map, which keeps these two
    // indices valid and pointing to the correct entry.
    index: usize,
    bucket: usize,
}

impl<'a, K, V> OccupiedEntry<'a, K, V> {
    /// Constructor for `RawEntryMut::from_hash`
    pub(crate) fn from_hash<F>(
        map: &'a mut Core<K, V>,
        hash: HashValue,
        mut is_match: F,
    ) -> Result<Self, &'a mut Core<K, V>>
    where
        F: FnMut(&K) -> bool,
    {
        let entries = &*map.entries;
        let eq = move |&i: &usize| is_match(&entries[i].key);
        match map.indices.find_entry(hash.get(), eq) {
            Ok(entry) => Ok(OccupiedEntry {
                bucket: entry.bucket_index(),
                index: *entry.get(),
                map,
            }),
            Err(_) => Err(map),
        }
    }

    pub(crate) fn into_core(self) -> &'a mut Core<K, V> {
        self.map
    }

    pub(crate) fn get_bucket(&self) -> &Bucket<K, V> {
        &self.map.entries[self.index]
    }

    pub(crate) fn get_bucket_mut(&mut self) -> &mut Bucket<K, V> {
        &mut self.map.entries[self.index]
    }

    pub(crate) fn into_bucket(self) -> &'a mut Bucket<K, V> {
        &mut self.map.entries[self.index]
    }

    /// Return the index of the key-value pair
    #[inline]
    pub fn index(&self) -> usize {
        self.index
    }

    /// Gets a reference to the entry's key in the map.
    ///
    /// Note that this is not the key that was used to find the entry. There may be an observable
    /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
    /// extra fields or the memory address of an allocation.
    pub fn key(&self) -> &K {
        &self.get_bucket().key
    }

    /// Gets a reference to the entry's value in the map.
    pub fn get(&self) -> &V {
        &self.get_bucket().value
    }

    /// Gets a mutable reference to the entry's value in the map.
    ///
    /// If you need a reference which may outlive the destruction of the
    /// [`Entry`] value, see [`into_mut`][Self::into_mut].
    pub fn get_mut(&mut self) -> &mut V {
        &mut self.get_bucket_mut().value
    }

    /// Converts into a mutable reference to the entry's value in the map,
    /// with a lifetime bound to the map itself.
    pub fn into_mut(self) -> &'a mut V {
        &mut self.into_bucket().value
    }

    /// Sets the value of the entry to `value`, and returns the entry's old value.
    pub fn insert(&mut self, value: V) -> V {
        mem::replace(self.get_mut(), value)
    }

    /// Remove the key, value pair stored in the map for this entry, and return the value.
    ///
    /// **NOTE:** This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this
    /// entry's position with the last element, and it is deprecated in favor of calling that
    /// explicitly. If you need to preserve the relative order of the keys in the map, use
    /// [`.shift_remove()`][Self::shift_remove] instead.
    #[deprecated(note = "`remove` disrupts the map order -- \
        use `swap_remove` or `shift_remove` for explicit behavior.")]
    pub fn remove(self) -> V {
        self.swap_remove()
    }

    /// Remove the key, value pair stored in the map for this entry, and return the value.
    ///
    /// Like [`Vec::swap_remove`][alloc::vec::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!**
    ///
    /// Computes in **O(1)** time (average).
    pub fn swap_remove(self) -> V {
        self.swap_remove_entry().1
    }

    /// Remove the key, value pair stored in the map for this entry, and return the value.
    ///
    /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
    /// elements that follow it, preserving their relative order.
    /// **This perturbs the index of all of those elements!**
    ///
    /// Computes in **O(n)** time (average).
    pub fn shift_remove(self) -> V {
        self.shift_remove_entry().1
    }

    /// Remove and return the key, value pair stored in the map for this entry
    ///
    /// **NOTE:** This is equivalent to [`.swap_remove_entry()`][Self::swap_remove_entry],
    /// replacing this entry's position with the last element, and it is deprecated in favor of
    /// calling that explicitly. If you need to preserve the relative order of the keys in the map,
    /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead.
    #[deprecated(note = "`remove_entry` disrupts the map order -- \
        use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")]
    pub fn remove_entry(self) -> (K, V) {
        self.swap_remove_entry()
    }

    /// Remove and return the key, value pair stored in the map for this entry
    ///
    /// Like [`Vec::swap_remove`][alloc::vec::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!**
    ///
    /// Computes in **O(1)** time (average).
    pub fn swap_remove_entry(mut self) -> (K, V) {
        self.remove_index();
        self.map.swap_remove_finish(self.index)
    }

    /// Remove and return the key, value pair stored in the map for this entry
    ///
    /// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
    /// elements that follow it, preserving their relative order.
    /// **This perturbs the index of all of those elements!**
    ///
    /// Computes in **O(n)** time (average).
    pub fn shift_remove_entry(mut self) -> (K, V) {
        self.remove_index();
        self.map.shift_remove_finish(self.index)
    }

    fn remove_index(&mut self) {
        let entry = self.map.indices.get_bucket_entry(self.bucket).unwrap();
        debug_assert_eq!(*entry.get(), self.index);
        entry.remove();
    }

    /// Moves the position of the entry to a new index
    /// by shifting all other entries in-between.
    ///
    /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
    /// coming `from` the current [`.index()`][Self::index].
    ///
    /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
    /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
    ///
    /// ***Panics*** if `to` is out of bounds.
    ///
    /// Computes in **O(n)** time (average).
    #[track_caller]
    pub fn move_index(self, to: usize) {
        if self.index != to {
            let _ = self.map.entries[to]; // explicit bounds check
            self.map.move_index_inner(self.index, to);
            self.update_index(to);
        }
    }

    /// Swaps the position of entry with another.
    ///
    /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
    /// with the current [`.index()`][Self::index] as one of the two being swapped.
    ///
    /// ***Panics*** if the `other` index is out of bounds.
    ///
    /// Computes in **O(1)** time (average).
    #[track_caller]
    pub fn swap_indices(self, other: usize) {
        if self.index != other {
            // Since we already know where our bucket is, we only need to find the other.
            let hash = self.map.entries[other].hash;
            let other_mut = self.map.indices.find_mut(hash.get(), move |&i| i == other);
            *other_mut.expect("index not found") = self.index;

            self.map.entries.swap(self.index, other);
            self.update_index(other);
        }
    }

    fn update_index(self, to: usize) {
        let index = self.map.indices.get_bucket_mut(self.bucket).unwrap();
        debug_assert_eq!(*index, self.index);
        *index = to;
    }
}

impl<'a, K, V> From<IndexedEntry<'a, K, V>> for OccupiedEntry<'a, K, V> {
    fn from(other: IndexedEntry<'a, K, V>) -> Self {
        let index = other.index();
        let map = other.into_core();
        let hash = map.entries[index].hash;
        let bucket = map
            .indices
            .find_bucket_index(hash.get(), move |&i| i == index)
            .expect("index not found");
        Self { map, index, bucket }
    }
}

/// A view into a vacant entry in an [`IndexMap`][crate::IndexMap].
/// It is part of the [`Entry`] enum.
pub struct VacantEntry<'a, K, V> {
    map: &'a mut Core<K, V>,
    hash: HashValue,
    key: K,
}

impl<'a, K, V> VacantEntry<'a, K, V> {
    /// Return the index where a key-value pair may be inserted.
    pub fn index(&self) -> usize {
        self.map.indices.len()
    }

    /// Gets a reference to the key that was used to find the entry.
    pub fn key(&self) -> &K {
        &self.key
    }

    pub(crate) fn key_mut(&mut self) -> &mut K {
        &mut self.key
    }

    /// Takes ownership of the key, leaving the entry vacant.
    pub fn into_key(self) -> K {
        self.key
    }

    /// Inserts the entry's key and the given value into the map, and returns a mutable reference
    /// to the value.
    ///
    /// Computes in **O(1)** time (amortized average).
    pub fn insert(self, value: V) -> &'a mut V {
        let Self { map, hash, key } = self;
        map.insert_unique(hash, key, value).value_mut()
    }

    /// Inserts the entry's key and the given value into the map, and returns an `OccupiedEntry`.
    ///
    /// Computes in **O(1)** time (amortized average).
    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
        let Self { map, hash, key } = self;
        let index = map.indices.len();
        debug_assert_eq!(index, map.entries.len());
        let bucket = map
            .indices
            .insert_unique(hash.get(), index, get_hash(&map.entries))
            .bucket_index();
        map.push_entry(hash, key, value);
        OccupiedEntry { map, index, bucket }
    }

    /// Inserts the entry's key and the given value into the map at its ordered
    /// position among sorted keys, and returns the new index and a mutable
    /// reference to the value.
    ///
    /// If the existing keys are **not** already sorted, then the insertion
    /// index is unspecified (like [`slice::binary_search`]), but the key-value
    /// pair is inserted at that position regardless.
    ///
    /// Computes in **O(n)** time (average).
    pub fn insert_sorted(self, value: V) -> (usize, &'a mut V)
    where
        K: Ord,
    {
        let slice = crate::map::Slice::from_slice(&self.map.entries);
        let i = slice.binary_search_keys(&self.key).unwrap_err();
        (i, self.shift_insert(i, value))
    }

    /// Inserts the entry's key and the given value into the map at its ordered
    /// position among keys sorted by `cmp`, and returns the new index and a
    /// mutable reference to the value.
    ///
    /// If the existing keys are **not** already sorted, then the insertion
    /// index is unspecified (like [`slice::binary_search`]), but the key-value
    /// pair is inserted at that position regardless.
    ///
    /// Computes in **O(n)** time (average).
    pub fn insert_sorted_by<F>(self, value: V, mut cmp: F) -> (usize, &'a mut V)
    where
        F: FnMut(&K, &V, &K, &V) -> Ordering,
    {
        let slice = crate::map::Slice::from_slice(&self.map.entries);
        let (Ok(i) | Err(i)) = slice.binary_search_by(|k, v| cmp(k, v, &self.key, &value));
        (i, self.shift_insert(i, value))
    }

    /// Inserts the entry's key and the given value into the map at its ordered
    /// position using a sort-key extraction function, and returns the new index
    /// and a mutable reference to the value.
    ///
    /// If the existing keys are **not** already sorted, then the insertion
    /// index is unspecified (like [`slice::binary_search`]), but the key-value
    /// pair is inserted at that position regardless.
    ///
    /// Computes in **O(n)** time (average).
    pub fn insert_sorted_by_key<B, F>(self, value: V, mut sort_key: F) -> (usize, &'a mut V)
    where
        B: Ord,
        F: FnMut(&K, &V) -> B,
    {
        let search_key = sort_key(&self.key, &value);
        let slice = crate::map::Slice::from_slice(&self.map.entries);
        let (Ok(i) | Err(i)) = slice.binary_search_by_key(&search_key, sort_key);
        (i, self.shift_insert(i, value))
    }

    /// Inserts the entry's key and the given value into the map at the given index,
    /// shifting others to the right, and returns a mutable reference to the value.
    ///
    /// ***Panics*** if `index` is out of bounds.
    ///
    /// Computes in **O(n)** time (average).
    #[track_caller]
    pub fn shift_insert(self, index: usize, value: V) -> &'a mut V {
        self.map
            .shift_insert_unique(index, self.hash, self.key, value)
            .value_mut()
    }

    /// Replaces the key at the given index with this entry's key, returning the
    /// old key and an `OccupiedEntry` for that index.
    ///
    /// ***Panics*** if `index` is out of bounds.
    ///
    /// Computes in **O(1)** time (average).
    #[track_caller]
    pub fn replace_index(self, index: usize) -> (K, OccupiedEntry<'a, K, V>) {
        let Self { map, hash, key } = self;

        // NB: This removal and insertion isn't "no grow" (with unreachable hasher)
        // because hashbrown's tombstones might force a resize anyway.
        let old_hash = map.entries[index].hash;
        map.indices
            .find_entry(old_hash.get(), move |&i| i == index)
            .expect("index not found")
            .remove();
        let bucket = map
            .indices
            .insert_unique(hash.get(), index, get_hash(&map.entries))
            .bucket_index();

        let entry = &mut map.entries[index];
        entry.hash = hash;
        let old_key = mem::replace(&mut entry.key, key);

        (old_key, OccupiedEntry { map, index, bucket })
    }
}

Coverage Report

Created: 2026-02-26 06:30

Line	Count	Source
1		use super::{equivalent, get_hash, Bucket, Core};
2		use crate::map::{Entry, IndexedEntry};
3		use crate::HashValue;
4		use core::cmp::Ordering;
5		use core::mem;
6
7		impl<'a, K, V> Entry<'a, K, V> {
8	0	pub(crate) fn new(map: &'a mut Core<K, V>, hash: HashValue, key: K) -> Self
9	0	where
10	0	K: Eq,
11		{
12	0	let eq = equivalent(&key, &map.entries);
13	0	match map.indices.find_entry(hash.get(), eq) {
14	0	Ok(entry) => Entry::Occupied(OccupiedEntry {
15	0	bucket: entry.bucket_index(),
16	0	index: *entry.get(),
17	0	map,
18	0	}),
19	0	Err(_) => Entry::Vacant(VacantEntry { map, hash, key }),
20		}
21	0	}
22		}
23
24		/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap].
25		/// It is part of the [`Entry`] enum.
26		pub struct OccupiedEntry<'a, K, V> {
27		map: &'a mut Core<K, V>,
28		// We have a mutable reference to the map, which keeps these two
29		// indices valid and pointing to the correct entry.
30		index: usize,
31		bucket: usize,
32		}
33
34		impl<'a, K, V> OccupiedEntry<'a, K, V> {
35		/// Constructor for `RawEntryMut::from_hash`
36	0	pub(crate) fn from_hash<F>(
37	0	map: &'a mut Core<K, V>,
38	0	hash: HashValue,
39	0	mut is_match: F,
40	0	) -> Result<Self, &'a mut Core<K, V>>
41	0	where
42	0	F: FnMut(&K) -> bool,
43		{
44	0	let entries = &*map.entries;
45	0	let eq = move \|&i: &usize\| is_match(&entries[i].key);
46	0	match map.indices.find_entry(hash.get(), eq) {
47	0	Ok(entry) => Ok(OccupiedEntry {
48	0	bucket: entry.bucket_index(),
49	0	index: *entry.get(),
50	0	map,
51	0	}),
52	0	Err(_) => Err(map),
53		}
54	0	}
55
56	0	pub(crate) fn into_core(self) -> &'a mut Core<K, V> {
57	0	self.map
58	0	}
59
60	0	pub(crate) fn get_bucket(&self) -> &Bucket<K, V> {
61	0	&self.map.entries[self.index]
62	0	} Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<alloc::string::String, bson::bson::Bson>>::get_bucket Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<_, _>>::get_bucket
63
64	0	pub(crate) fn get_bucket_mut(&mut self) -> &mut Bucket<K, V> {
65	0	&mut self.map.entries[self.index]
66	0	}
67
68	0	pub(crate) fn into_bucket(self) -> &'a mut Bucket<K, V> {
69	0	&mut self.map.entries[self.index]
70	0	} Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<alloc::string::String, bson::bson::Bson>>::into_bucket Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<_, _>>::into_bucket
71
72		/// Return the index of the key-value pair
73		#[inline]
74	0	pub fn index(&self) -> usize {
75	0	self.index
76	0	}
77
78		/// Gets a reference to the entry's key in the map.
79		///
80		/// Note that this is not the key that was used to find the entry. There may be an observable
81		/// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
82		/// extra fields or the memory address of an allocation.
83	0	pub fn key(&self) -> &K {
84	0	&self.get_bucket().key
85	0	} Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<alloc::string::String, bson::bson::Bson>>::key Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<_, _>>::key
86
87		/// Gets a reference to the entry's value in the map.
88	0	pub fn get(&self) -> &V {
89	0	&self.get_bucket().value
90	0	}
91
92		/// Gets a mutable reference to the entry's value in the map.
93		///
94		/// If you need a reference which may outlive the destruction of the
95		/// [`Entry`] value, see [`into_mut`][Self::into_mut].
96	0	pub fn get_mut(&mut self) -> &mut V {
97	0	&mut self.get_bucket_mut().value
98	0	}
99
100		/// Converts into a mutable reference to the entry's value in the map,
101		/// with a lifetime bound to the map itself.
102	0	pub fn into_mut(self) -> &'a mut V {
103	0	&mut self.into_bucket().value
104	0	} Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<alloc::string::String, bson::bson::Bson>>::into_mut Unexecuted instantiation: <indexmap::inner::entry::OccupiedEntry<_, _>>::into_mut
105
106		/// Sets the value of the entry to `value`, and returns the entry's old value.
107	0	pub fn insert(&mut self, value: V) -> V {
108	0	mem::replace(self.get_mut(), value)
109	0	}
110
111		/// Remove the key, value pair stored in the map for this entry, and return the value.
112		///
113		/// NOTE: This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this
114		/// entry's position with the last element, and it is deprecated in favor of calling that
115		/// explicitly. If you need to preserve the relative order of the keys in the map, use
116		/// [`.shift_remove()`][Self::shift_remove] instead.
117		#[deprecated(note = "`remove` disrupts the map order -- \
118		use `swap_remove` or `shift_remove` for explicit behavior.")]
119	0	pub fn remove(self) -> V {
120	0	self.swap_remove()
121	0	}
122
123		/// Remove the key, value pair stored in the map for this entry, and return the value.
124		///
125		/// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
126		/// with the last element of the map and popping it off.
127		/// This perturbs the position of what used to be the last element!
128		///
129		/// Computes in O(1) time (average).
130	0	pub fn swap_remove(self) -> V {
131	0	self.swap_remove_entry().1
132	0	}
133
134		/// Remove the key, value pair stored in the map for this entry, and return the value.
135		///
136		/// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
137		/// elements that follow it, preserving their relative order.
138		/// This perturbs the index of all of those elements!
139		///
140		/// Computes in O(n) time (average).
141	0	pub fn shift_remove(self) -> V {
142	0	self.shift_remove_entry().1
143	0	}
144
145		/// Remove and return the key, value pair stored in the map for this entry
146		///
147		/// NOTE: This is equivalent to [`.swap_remove_entry()`][Self::swap_remove_entry],
148		/// replacing this entry's position with the last element, and it is deprecated in favor of
149		/// calling that explicitly. If you need to preserve the relative order of the keys in the map,
150		/// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead.
151		#[deprecated(note = "`remove_entry` disrupts the map order -- \
152		use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")]
153	0	pub fn remove_entry(self) -> (K, V) {
154	0	self.swap_remove_entry()
155	0	}
156
157		/// Remove and return the key, value pair stored in the map for this entry
158		///
159		/// Like [`Vec::swap_remove`][alloc::vec::Vec::swap_remove], the pair is removed by swapping it
160		/// with the last element of the map and popping it off.
161		/// This perturbs the position of what used to be the last element!
162		///
163		/// Computes in O(1) time (average).
164	0	pub fn swap_remove_entry(mut self) -> (K, V) {
165	0	self.remove_index();
166	0	self.map.swap_remove_finish(self.index)
167	0	}
168
169		/// Remove and return the key, value pair stored in the map for this entry
170		///
171		/// Like [`Vec::remove`][alloc::vec::Vec::remove], the pair is removed by shifting all of the
172		/// elements that follow it, preserving their relative order.
173		/// This perturbs the index of all of those elements!
174		///
175		/// Computes in O(n) time (average).
176	0	pub fn shift_remove_entry(mut self) -> (K, V) {
177	0	self.remove_index();
178	0	self.map.shift_remove_finish(self.index)
179	0	}
180
181	0	fn remove_index(&mut self) {
182	0	let entry = self.map.indices.get_bucket_entry(self.bucket).unwrap();
183	0	debug_assert_eq!(*entry.get(), self.index);
184	0	entry.remove();
185	0	}
186
187		/// Moves the position of the entry to a new index
188		/// by shifting all other entries in-between.
189		///
190		/// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
191		/// coming `from` the current [`.index()`][Self::index].
192		///
193		/// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
194		/// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
195		///
196		/// *Panics* if `to` is out of bounds.
197		///
198		/// Computes in O(n) time (average).
199		#[track_caller]
200	0	pub fn move_index(self, to: usize) {
201	0	if self.index != to {
202	0	let _ = self.map.entries[to]; // explicit bounds check
203	0	self.map.move_index_inner(self.index, to);
204	0	self.update_index(to);
205	0	}
206	0	}
207
208		/// Swaps the position of entry with another.
209		///
210		/// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
211		/// with the current [`.index()`][Self::index] as one of the two being swapped.
212		///
213		/// *Panics* if the `other` index is out of bounds.
214		///
215		/// Computes in O(1) time (average).
216		#[track_caller]
217	0	pub fn swap_indices(self, other: usize) {
218	0	if self.index != other {
219		// Since we already know where our bucket is, we only need to find the other.
220	0	let hash = self.map.entries[other].hash;
221	0	let other_mut = self.map.indices.find_mut(hash.get(), move \|&i\| i == other);
222	0	*other_mut.expect("index not found") = self.index;
223
224	0	self.map.entries.swap(self.index, other);
225	0	self.update_index(other);
226	0	}
227	0	}
228
229	0	fn update_index(self, to: usize) {
230	0	let index = self.map.indices.get_bucket_mut(self.bucket).unwrap();
231	0	debug_assert_eq!(*index, self.index);
232	0	*index = to;
233	0	}
234		}
235
236		impl<'a, K, V> From<IndexedEntry<'a, K, V>> for OccupiedEntry<'a, K, V> {
237	0	fn from(other: IndexedEntry<'a, K, V>) -> Self {
238	0	let index = other.index();
239	0	let map = other.into_core();
240	0	let hash = map.entries[index].hash;
241	0	let bucket = map
242	0	.indices
243	0	.find_bucket_index(hash.get(), move \|&i\| i == index)
244	0	.expect("index not found");
245	0	Self { map, index, bucket }
246	0	}
247		}
248
249		/// A view into a vacant entry in an [`IndexMap`][crate::IndexMap].
250		/// It is part of the [`Entry`] enum.
251		pub struct VacantEntry<'a, K, V> {
252		map: &'a mut Core<K, V>,
253		hash: HashValue,
254		key: K,
255		}
256
257		impl<'a, K, V> VacantEntry<'a, K, V> {
258		/// Return the index where a key-value pair may be inserted.
259	0	pub fn index(&self) -> usize {
260	0	self.map.indices.len()
261	0	}
262
263		/// Gets a reference to the key that was used to find the entry.
264	0	pub fn key(&self) -> &K {
265	0	&self.key
266	0	} Unexecuted instantiation: <indexmap::inner::entry::VacantEntry<alloc::string::String, bson::bson::Bson>>::key Unexecuted instantiation: <indexmap::inner::entry::VacantEntry<_, _>>::key
267
268	0	pub(crate) fn key_mut(&mut self) -> &mut K {
269	0	&mut self.key
270	0	}
271
272		/// Takes ownership of the key, leaving the entry vacant.
273	0	pub fn into_key(self) -> K {
274	0	self.key
275	0	}
276
277		/// Inserts the entry's key and the given value into the map, and returns a mutable reference
278		/// to the value.
279		///
280		/// Computes in O(1) time (amortized average).
281	0	pub fn insert(self, value: V) -> &'a mut V {
282	0	let Self { map, hash, key } = self;
283	0	map.insert_unique(hash, key, value).value_mut()
284	0	} Unexecuted instantiation: <indexmap::inner::entry::VacantEntry<alloc::string::String, bson::bson::Bson>>::insert Unexecuted instantiation: <indexmap::inner::entry::VacantEntry<_, _>>::insert
285
286		/// Inserts the entry's key and the given value into the map, and returns an `OccupiedEntry`.
287		///
288		/// Computes in O(1) time (amortized average).
289	0	pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
290	0	let Self { map, hash, key } = self;
291	0	let index = map.indices.len();
292	0	debug_assert_eq!(index, map.entries.len());
293	0	let bucket = map
294	0	.indices
295	0	.insert_unique(hash.get(), index, get_hash(&map.entries))
296	0	.bucket_index();
297	0	map.push_entry(hash, key, value);
298	0	OccupiedEntry { map, index, bucket }
299	0	}
300
301		/// Inserts the entry's key and the given value into the map at its ordered
302		/// position among sorted keys, and returns the new index and a mutable
303		/// reference to the value.
304		///
305		/// If the existing keys are not already sorted, then the insertion
306		/// index is unspecified (like [`slice::binary_search`]), but the key-value
307		/// pair is inserted at that position regardless.
308		///
309		/// Computes in O(n) time (average).
310	0	pub fn insert_sorted(self, value: V) -> (usize, &'a mut V)
311	0	where
312	0	K: Ord,
313		{
314	0	let slice = crate::map::Slice::from_slice(&self.map.entries);
315	0	let i = slice.binary_search_keys(&self.key).unwrap_err();
316	0	(i, self.shift_insert(i, value))
317	0	}
318
319		/// Inserts the entry's key and the given value into the map at its ordered
320		/// position among keys sorted by `cmp`, and returns the new index and a
321		/// mutable reference to the value.
322		///
323		/// If the existing keys are not already sorted, then the insertion
324		/// index is unspecified (like [`slice::binary_search`]), but the key-value
325		/// pair is inserted at that position regardless.
326		///
327		/// Computes in O(n) time (average).
328	0	pub fn insert_sorted_by<F>(self, value: V, mut cmp: F) -> (usize, &'a mut V)
329	0	where
330	0	F: FnMut(&K, &V, &K, &V) -> Ordering,
331		{
332	0	let slice = crate::map::Slice::from_slice(&self.map.entries);
333	0	let (Ok(i) \| Err(i)) = slice.binary_search_by(\|k, v\| cmp(k, v, &self.key, &value));
334	0	(i, self.shift_insert(i, value))
335	0	}
336
337		/// Inserts the entry's key and the given value into the map at its ordered
338		/// position using a sort-key extraction function, and returns the new index
339		/// and a mutable reference to the value.
340		///
341		/// If the existing keys are not already sorted, then the insertion
342		/// index is unspecified (like [`slice::binary_search`]), but the key-value
343		/// pair is inserted at that position regardless.
344		///
345		/// Computes in O(n) time (average).
346	0	pub fn insert_sorted_by_key<B, F>(self, value: V, mut sort_key: F) -> (usize, &'a mut V)
347	0	where
348	0	B: Ord,
349	0	F: FnMut(&K, &V) -> B,
350		{
351	0	let search_key = sort_key(&self.key, &value);
352	0	let slice = crate::map::Slice::from_slice(&self.map.entries);
353	0	let (Ok(i) \| Err(i)) = slice.binary_search_by_key(&search_key, sort_key);
354	0	(i, self.shift_insert(i, value))
355	0	}
356
357		/// Inserts the entry's key and the given value into the map at the given index,
358		/// shifting others to the right, and returns a mutable reference to the value.
359		///
360		/// *Panics* if `index` is out of bounds.
361		///
362		/// Computes in O(n) time (average).
363		#[track_caller]
364	0	pub fn shift_insert(self, index: usize, value: V) -> &'a mut V {
365	0	self.map
366	0	.shift_insert_unique(index, self.hash, self.key, value)
367	0	.value_mut()
368	0	}
369
370		/// Replaces the key at the given index with this entry's key, returning the
371		/// old key and an `OccupiedEntry` for that index.
372		///
373		/// *Panics* if `index` is out of bounds.
374		///
375		/// Computes in O(1) time (average).
376		#[track_caller]
377	0	pub fn replace_index(self, index: usize) -> (K, OccupiedEntry<'a, K, V>) {
378	0	let Self { map, hash, key } = self;
379
380		// NB: This removal and insertion isn't "no grow" (with unreachable hasher)
381		// because hashbrown's tombstones might force a resize anyway.
382	0	let old_hash = map.entries[index].hash;
383	0	map.indices
384	0	.find_entry(old_hash.get(), move \|&i\| i == index)
385	0	.expect("index not found")
386	0	.remove();
387	0	let bucket = map
388	0	.indices
389	0	.insert_unique(hash.get(), index, get_hash(&map.entries))
390	0	.bucket_index();
391
392	0	let entry = &mut map.entries[index];
393	0	entry.hash = hash;
394	0	let old_key = mem::replace(&mut entry.key, key);
395
396	0	(old_key, OccupiedEntry { map, index, bucket })
397	0	}
398		}