indexmap/map/core/raw_entry_v1.rs
1//! Opt-in access to the experimental raw entry API.
2//!
3//! This module is designed to mimic the raw entry API of [`HashMap`][std::collections::hash_map],
4//! matching its unstable state as of Rust 1.75. See the tracking issue
5//! [rust#56167](https://github.com/rust-lang/rust/issues/56167) for more details.
6//!
7//! The trait [`RawEntryApiV1`] and the `_v1` suffix on its methods are meant to insulate this for
8//! the future, in case later breaking changes are needed. If the standard library stabilizes its
9//! `hash_raw_entry` feature (or some replacement), matching *inherent* methods will be added to
10//! `IndexMap` without such an opt-in trait.
11
12use super::raw::RawTableEntry;
13use super::IndexMapCore;
14use crate::{Equivalent, HashValue, IndexMap};
15use core::fmt;
16use core::hash::{BuildHasher, Hash, Hasher};
17use core::marker::PhantomData;
18use core::mem;
19
20/// Opt-in access to the experimental raw entry API.
21///
22/// See the [`raw_entry_v1`][self] module documentation for more information.
23pub trait RawEntryApiV1<K, V, S>: private::Sealed {
24 /// Creates a raw immutable entry builder for the [`IndexMap`].
25 ///
26 /// Raw entries provide the lowest level of control for searching and
27 /// manipulating a map. They must be manually initialized with a hash and
28 /// then manually searched.
29 ///
30 /// This is useful for
31 /// * Hash memoization
32 /// * Using a search key that doesn't work with the [`Equivalent`] trait
33 /// * Using custom comparison logic without newtype wrappers
34 ///
35 /// Unless you are in such a situation, higher-level and more foolproof APIs like
36 /// [`get`][IndexMap::get] should be preferred.
37 ///
38 /// Immutable raw entries have very limited use; you might instead want
39 /// [`raw_entry_mut_v1`][Self::raw_entry_mut_v1].
40 ///
41 /// # Examples
42 ///
43 /// ```
44 /// use core::hash::{BuildHasher, Hash};
45 /// use indexmap::map::{IndexMap, RawEntryApiV1};
46 ///
47 /// let mut map = IndexMap::new();
48 /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
49 ///
50 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
51 /// use core::hash::Hasher;
52 /// let mut state = hash_builder.build_hasher();
53 /// key.hash(&mut state);
54 /// state.finish()
55 /// }
56 ///
57 /// for k in ["a", "b", "c", "d", "e", "f"] {
58 /// let hash = compute_hash(map.hasher(), k);
59 /// let i = map.get_index_of(k);
60 /// let v = map.get(k);
61 /// let kv = map.get_key_value(k);
62 /// let ikv = map.get_full(k);
63 ///
64 /// println!("Key: {} and value: {:?}", k, v);
65 ///
66 /// assert_eq!(map.raw_entry_v1().from_key(k), kv);
67 /// assert_eq!(map.raw_entry_v1().from_hash(hash, |q| *q == k), kv);
68 /// assert_eq!(map.raw_entry_v1().from_key_hashed_nocheck(hash, k), kv);
69 /// assert_eq!(map.raw_entry_v1().from_hash_full(hash, |q| *q == k), ikv);
70 /// assert_eq!(map.raw_entry_v1().index_from_hash(hash, |q| *q == k), i);
71 /// }
72 /// ```
73 fn raw_entry_v1(&self) -> RawEntryBuilder<'_, K, V, S>;
74
75 /// Creates a raw entry builder for the [`IndexMap`].
76 ///
77 /// Raw entries provide the lowest level of control for searching and
78 /// manipulating a map. They must be manually initialized with a hash and
79 /// then manually searched. After this, insertions into a vacant entry
80 /// still require an owned key to be provided.
81 ///
82 /// Raw entries are useful for such exotic situations as:
83 ///
84 /// * Hash memoization
85 /// * Deferring the creation of an owned key until it is known to be required
86 /// * Using a search key that doesn't work with the [`Equivalent`] trait
87 /// * Using custom comparison logic without newtype wrappers
88 ///
89 /// Because raw entries provide much more low-level control, it's much easier
90 /// to put the `IndexMap` into an inconsistent state which, while memory-safe,
91 /// will cause the map to produce seemingly random results. Higher-level and more
92 /// foolproof APIs like [`entry`][IndexMap::entry] should be preferred when possible.
93 ///
94 /// Raw entries give mutable access to the keys. This must not be used
95 /// to modify how the key would compare or hash, as the map will not re-evaluate
96 /// where the key should go, meaning the keys may become "lost" if their
97 /// location does not reflect their state. For instance, if you change a key
98 /// so that the map now contains keys which compare equal, search may start
99 /// acting erratically, with two keys randomly masking each other. Implementations
100 /// are free to assume this doesn't happen (within the limits of memory-safety).
101 ///
102 /// # Examples
103 ///
104 /// ```
105 /// use core::hash::{BuildHasher, Hash};
106 /// use indexmap::map::{IndexMap, RawEntryApiV1};
107 /// use indexmap::map::raw_entry_v1::RawEntryMut;
108 ///
109 /// let mut map = IndexMap::new();
110 /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
111 ///
112 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
113 /// use core::hash::Hasher;
114 /// let mut state = hash_builder.build_hasher();
115 /// key.hash(&mut state);
116 /// state.finish()
117 /// }
118 ///
119 /// // Existing key (insert and update)
120 /// match map.raw_entry_mut_v1().from_key("a") {
121 /// RawEntryMut::Vacant(_) => unreachable!(),
122 /// RawEntryMut::Occupied(mut view) => {
123 /// assert_eq!(view.index(), 0);
124 /// assert_eq!(view.get(), &100);
125 /// let v = view.get_mut();
126 /// let new_v = (*v) * 10;
127 /// *v = new_v;
128 /// assert_eq!(view.insert(1111), 1000);
129 /// }
130 /// }
131 ///
132 /// assert_eq!(map["a"], 1111);
133 /// assert_eq!(map.len(), 3);
134 ///
135 /// // Existing key (take)
136 /// let hash = compute_hash(map.hasher(), "c");
137 /// match map.raw_entry_mut_v1().from_key_hashed_nocheck(hash, "c") {
138 /// RawEntryMut::Vacant(_) => unreachable!(),
139 /// RawEntryMut::Occupied(view) => {
140 /// assert_eq!(view.index(), 2);
141 /// assert_eq!(view.shift_remove_entry(), ("c", 300));
142 /// }
143 /// }
144 /// assert_eq!(map.raw_entry_v1().from_key("c"), None);
145 /// assert_eq!(map.len(), 2);
146 ///
147 /// // Nonexistent key (insert and update)
148 /// let key = "d";
149 /// let hash = compute_hash(map.hasher(), key);
150 /// match map.raw_entry_mut_v1().from_hash(hash, |q| *q == key) {
151 /// RawEntryMut::Occupied(_) => unreachable!(),
152 /// RawEntryMut::Vacant(view) => {
153 /// assert_eq!(view.index(), 2);
154 /// let (k, value) = view.insert("d", 4000);
155 /// assert_eq!((*k, *value), ("d", 4000));
156 /// *value = 40000;
157 /// }
158 /// }
159 /// assert_eq!(map["d"], 40000);
160 /// assert_eq!(map.len(), 3);
161 ///
162 /// match map.raw_entry_mut_v1().from_hash(hash, |q| *q == key) {
163 /// RawEntryMut::Vacant(_) => unreachable!(),
164 /// RawEntryMut::Occupied(view) => {
165 /// assert_eq!(view.index(), 2);
166 /// assert_eq!(view.swap_remove_entry(), ("d", 40000));
167 /// }
168 /// }
169 /// assert_eq!(map.get("d"), None);
170 /// assert_eq!(map.len(), 2);
171 /// ```
172 fn raw_entry_mut_v1(&mut self) -> RawEntryBuilderMut<'_, K, V, S>;
173}
174
175impl<K, V, S> RawEntryApiV1<K, V, S> for IndexMap<K, V, S> {
176 fn raw_entry_v1(&self) -> RawEntryBuilder<'_, K, V, S> {
177 RawEntryBuilder { map: self }
178 }
179
180 fn raw_entry_mut_v1(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
181 RawEntryBuilderMut { map: self }
182 }
183}
184
185/// A builder for computing where in an [`IndexMap`] a key-value pair would be stored.
186///
187/// This `struct` is created by the [`IndexMap::raw_entry_v1`] method, provided by the
188/// [`RawEntryApiV1`] trait. See its documentation for more.
189pub struct RawEntryBuilder<'a, K, V, S> {
190 map: &'a IndexMap<K, V, S>,
191}
192
193impl<K, V, S> fmt::Debug for RawEntryBuilder<'_, K, V, S> {
194 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
195 f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
196 }
197}
198
199impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S> {
200 /// Access an entry by key.
201 pub fn from_key<Q>(self, key: &Q) -> Option<(&'a K, &'a V)>
202 where
203 S: BuildHasher,
204 Q: ?Sized + Hash + Equivalent<K>,
205 {
206 self.map.get_key_value(key)
207 }
208
209 /// Access an entry by a key and its hash.
210 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> Option<(&'a K, &'a V)>
211 where
212 Q: ?Sized + Equivalent<K>,
213 {
214 let hash = HashValue(hash as usize);
215 let i = self.map.core.get_index_of(hash, key)?;
216 self.map.get_index(i)
217 }
218
219 /// Access an entry by hash.
220 pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
221 where
222 F: FnMut(&K) -> bool,
223 {
224 let map = self.map;
225 let i = self.index_from_hash(hash, is_match)?;
226 map.get_index(i)
227 }
228
229 /// Access an entry by hash, including its index.
230 pub fn from_hash_full<F>(self, hash: u64, is_match: F) -> Option<(usize, &'a K, &'a V)>
231 where
232 F: FnMut(&K) -> bool,
233 {
234 let map = self.map;
235 let i = self.index_from_hash(hash, is_match)?;
236 let (key, value) = map.get_index(i)?;
237 Some((i, key, value))
238 }
239
240 /// Access the index of an entry by hash.
241 pub fn index_from_hash<F>(self, hash: u64, mut is_match: F) -> Option<usize>
242 where
243 F: FnMut(&K) -> bool,
244 {
245 let hash = HashValue(hash as usize);
246 let entries = &*self.map.core.entries;
247 let eq = move |&i: &usize| is_match(&entries[i].key);
248 self.map.core.indices.get(hash.get(), eq).copied()
249 }
250}
251
252/// A builder for computing where in an [`IndexMap`] a key-value pair would be stored.
253///
254/// This `struct` is created by the [`IndexMap::raw_entry_mut_v1`] method, provided by the
255/// [`RawEntryApiV1`] trait. See its documentation for more.
256pub struct RawEntryBuilderMut<'a, K, V, S> {
257 map: &'a mut IndexMap<K, V, S>,
258}
259
260impl<K, V, S> fmt::Debug for RawEntryBuilderMut<'_, K, V, S> {
261 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
262 f.debug_struct("RawEntryBuilderMut").finish_non_exhaustive()
263 }
264}
265
266impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S> {
267 /// Access an entry by key.
268 pub fn from_key<Q>(self, key: &Q) -> RawEntryMut<'a, K, V, S>
269 where
270 S: BuildHasher,
271 Q: ?Sized + Hash + Equivalent<K>,
272 {
273 let hash = self.map.hash(key);
274 self.from_key_hashed_nocheck(hash.get(), key)
275 }
276
277 /// Access an entry by a key and its hash.
278 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> RawEntryMut<'a, K, V, S>
279 where
280 Q: ?Sized + Equivalent<K>,
281 {
282 self.from_hash(hash, |k| Q::equivalent(key, k))
283 }
284
285 /// Access an entry by hash.
286 pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
287 where
288 F: FnMut(&K) -> bool,
289 {
290 let hash = HashValue(hash as usize);
291 match self.map.core.raw_entry(hash, is_match) {
292 Ok(raw) => RawEntryMut::Occupied(RawOccupiedEntryMut {
293 raw,
294 hash_builder: PhantomData,
295 }),
296 Err(map) => RawEntryMut::Vacant(RawVacantEntryMut {
297 map,
298 hash_builder: &self.map.hash_builder,
299 }),
300 }
301 }
302}
303
304/// Raw entry for an existing key-value pair or a vacant location to
305/// insert one.
306pub enum RawEntryMut<'a, K, V, S> {
307 /// Existing slot with equivalent key.
308 Occupied(RawOccupiedEntryMut<'a, K, V, S>),
309 /// Vacant slot (no equivalent key in the map).
310 Vacant(RawVacantEntryMut<'a, K, V, S>),
311}
312
313impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawEntryMut<'_, K, V, S> {
314 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
315 let mut tuple = f.debug_tuple("RawEntryMut");
316 match self {
317 Self::Vacant(v) => tuple.field(v),
318 Self::Occupied(o) => tuple.field(o),
319 };
320 tuple.finish()
321 }
322}
323
324impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
325 /// Return the index where the key-value pair exists or may be inserted.
326 #[inline]
327 pub fn index(&self) -> usize {
328 match self {
329 Self::Occupied(entry) => entry.index(),
330 Self::Vacant(entry) => entry.index(),
331 }
332 }
333
334 /// Inserts the given default key and value in the entry if it is vacant and returns mutable
335 /// references to them. Otherwise mutable references to an already existent pair are returned.
336 pub fn or_insert(self, default_key: K, default_value: V) -> (&'a mut K, &'a mut V)
337 where
338 K: Hash,
339 S: BuildHasher,
340 {
341 match self {
342 Self::Occupied(entry) => entry.into_key_value_mut(),
343 Self::Vacant(entry) => entry.insert(default_key, default_value),
344 }
345 }
346
347 /// Inserts the result of the `call` function in the entry if it is vacant and returns mutable
348 /// references to them. Otherwise mutable references to an already existent pair are returned.
349 pub fn or_insert_with<F>(self, call: F) -> (&'a mut K, &'a mut V)
350 where
351 F: FnOnce() -> (K, V),
352 K: Hash,
353 S: BuildHasher,
354 {
355 match self {
356 Self::Occupied(entry) => entry.into_key_value_mut(),
357 Self::Vacant(entry) => {
358 let (key, value) = call();
359 entry.insert(key, value)
360 }
361 }
362 }
363
364 /// Modifies the entry if it is occupied.
365 pub fn and_modify<F>(mut self, f: F) -> Self
366 where
367 F: FnOnce(&mut K, &mut V),
368 {
369 if let Self::Occupied(entry) = &mut self {
370 let (k, v) = entry.get_key_value_mut();
371 f(k, v);
372 }
373 self
374 }
375}
376
377/// A raw view into an occupied entry in an [`IndexMap`].
378/// It is part of the [`RawEntryMut`] enum.
379pub struct RawOccupiedEntryMut<'a, K, V, S> {
380 raw: RawTableEntry<'a, K, V>,
381 hash_builder: PhantomData<&'a S>,
382}
383
384impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawOccupiedEntryMut<'_, K, V, S> {
385 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
386 f.debug_struct("RawOccupiedEntryMut")
387 .field("key", self.key())
388 .field("value", self.get())
389 .finish_non_exhaustive()
390 }
391}
392
393impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
394 /// Return the index of the key-value pair
395 #[inline]
396 pub fn index(&self) -> usize {
397 self.raw.index()
398 }
399
400 /// Gets a reference to the entry's key in the map.
401 ///
402 /// Note that this is not the key that was used to find the entry. There may be an observable
403 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
404 /// extra fields or the memory address of an allocation.
405 pub fn key(&self) -> &K {
406 &self.raw.bucket().key
407 }
408
409 /// Gets a mutable reference to the entry's key in the map.
410 ///
411 /// Note that this is not the key that was used to find the entry. There may be an observable
412 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
413 /// extra fields or the memory address of an allocation.
414 pub fn key_mut(&mut self) -> &mut K {
415 &mut self.raw.bucket_mut().key
416 }
417
418 /// Converts into a mutable reference to the entry's key in the map,
419 /// with a lifetime bound to the map itself.
420 ///
421 /// Note that this is not the key that was used to find the entry. There may be an observable
422 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
423 /// extra fields or the memory address of an allocation.
424 pub fn into_key(self) -> &'a mut K {
425 &mut self.raw.into_bucket().key
426 }
427
428 /// Gets a reference to the entry's value in the map.
429 pub fn get(&self) -> &V {
430 &self.raw.bucket().value
431 }
432
433 /// Gets a mutable reference to the entry's value in the map.
434 ///
435 /// If you need a reference which may outlive the destruction of the
436 /// [`RawEntryMut`] value, see [`into_mut`][Self::into_mut].
437 pub fn get_mut(&mut self) -> &mut V {
438 &mut self.raw.bucket_mut().value
439 }
440
441 /// Converts into a mutable reference to the entry's value in the map,
442 /// with a lifetime bound to the map itself.
443 pub fn into_mut(self) -> &'a mut V {
444 &mut self.raw.into_bucket().value
445 }
446
447 /// Gets a reference to the entry's key and value in the map.
448 pub fn get_key_value(&self) -> (&K, &V) {
449 self.raw.bucket().refs()
450 }
451
452 /// Gets a reference to the entry's key and value in the map.
453 pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
454 self.raw.bucket_mut().muts()
455 }
456
457 /// Converts into a mutable reference to the entry's key and value in the map,
458 /// with a lifetime bound to the map itself.
459 pub fn into_key_value_mut(self) -> (&'a mut K, &'a mut V) {
460 self.raw.into_bucket().muts()
461 }
462
463 /// Sets the value of the entry, and returns the entry's old value.
464 pub fn insert(&mut self, value: V) -> V {
465 mem::replace(self.get_mut(), value)
466 }
467
468 /// Sets the key of the entry, and returns the entry's old key.
469 pub fn insert_key(&mut self, key: K) -> K {
470 mem::replace(self.key_mut(), key)
471 }
472
473 /// Remove the key, value pair stored in the map for this entry, and return the value.
474 ///
475 /// **NOTE:** This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this
476 /// entry's position with the last element, and it is deprecated in favor of calling that
477 /// explicitly. If you need to preserve the relative order of the keys in the map, use
478 /// [`.shift_remove()`][Self::shift_remove] instead.
479 #[deprecated(note = "`remove` disrupts the map order -- \
480 use `swap_remove` or `shift_remove` for explicit behavior.")]
481 pub fn remove(self) -> V {
482 self.swap_remove()
483 }
484
485 /// Remove the key, value pair stored in the map for this entry, and return the value.
486 ///
487 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
488 /// the last element of the map and popping it off.
489 /// **This perturbs the position of what used to be the last element!**
490 ///
491 /// Computes in **O(1)** time (average).
492 pub fn swap_remove(self) -> V {
493 self.swap_remove_entry().1
494 }
495
496 /// Remove the key, value pair stored in the map for this entry, and return the value.
497 ///
498 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
499 /// elements that follow it, preserving their relative order.
500 /// **This perturbs the index of all of those elements!**
501 ///
502 /// Computes in **O(n)** time (average).
503 pub fn shift_remove(self) -> V {
504 self.shift_remove_entry().1
505 }
506
507 /// Remove and return the key, value pair stored in the map for this entry
508 ///
509 /// **NOTE:** This is equivalent to [`.swap_remove_entry()`][Self::swap_remove_entry],
510 /// replacing this entry's position with the last element, and it is deprecated in favor of
511 /// calling that explicitly. If you need to preserve the relative order of the keys in the map,
512 /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead.
513 #[deprecated(note = "`remove_entry` disrupts the map order -- \
514 use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")]
515 pub fn remove_entry(self) -> (K, V) {
516 self.swap_remove_entry()
517 }
518
519 /// Remove and return the key, value pair stored in the map for this entry
520 ///
521 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
522 /// the last element of the map and popping it off.
523 /// **This perturbs the position of what used to be the last element!**
524 ///
525 /// Computes in **O(1)** time (average).
526 pub fn swap_remove_entry(self) -> (K, V) {
527 let (map, index) = self.raw.remove_index();
528 map.swap_remove_finish(index)
529 }
530
531 /// Remove and return the key, value pair stored in the map for this entry
532 ///
533 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
534 /// elements that follow it, preserving their relative order.
535 /// **This perturbs the index of all of those elements!**
536 ///
537 /// Computes in **O(n)** time (average).
538 pub fn shift_remove_entry(self) -> (K, V) {
539 let (map, index) = self.raw.remove_index();
540 map.shift_remove_finish(index)
541 }
542
543 /// Moves the position of the entry to a new index
544 /// by shifting all other entries in-between.
545 ///
546 /// This is equivalent to [`IndexMap::move_index`]
547 /// coming `from` the current [`.index()`][Self::index].
548 ///
549 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
550 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
551 ///
552 /// ***Panics*** if `to` is out of bounds.
553 ///
554 /// Computes in **O(n)** time (average).
555 pub fn move_index(self, to: usize) {
556 let (map, index) = self.raw.into_inner();
557 map.move_index(index, to);
558 }
559
560 /// Swaps the position of entry with another.
561 ///
562 /// This is equivalent to [`IndexMap::swap_indices`]
563 /// with the current [`.index()`][Self::index] as one of the two being swapped.
564 ///
565 /// ***Panics*** if the `other` index is out of bounds.
566 ///
567 /// Computes in **O(1)** time (average).
568 pub fn swap_indices(self, other: usize) {
569 let (map, index) = self.raw.into_inner();
570 map.swap_indices(index, other)
571 }
572}
573
574/// A view into a vacant raw entry in an [`IndexMap`].
575/// It is part of the [`RawEntryMut`] enum.
576pub struct RawVacantEntryMut<'a, K, V, S> {
577 map: &'a mut IndexMapCore<K, V>,
578 hash_builder: &'a S,
579}
580
581impl<K, V, S> fmt::Debug for RawVacantEntryMut<'_, K, V, S> {
582 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
583 f.debug_struct("RawVacantEntryMut").finish_non_exhaustive()
584 }
585}
586
587impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
588 /// Return the index where a key-value pair may be inserted.
589 pub fn index(&self) -> usize {
590 self.map.indices.len()
591 }
592
593 /// Inserts the given key and value into the map,
594 /// and returns mutable references to them.
595 pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
596 where
597 K: Hash,
598 S: BuildHasher,
599 {
600 let mut h = self.hash_builder.build_hasher();
601 key.hash(&mut h);
602 self.insert_hashed_nocheck(h.finish(), key, value)
603 }
604
605 /// Inserts the given key and value into the map with the provided hash,
606 /// and returns mutable references to them.
607 pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) {
608 let hash = HashValue(hash as usize);
609 let i = self.map.insert_unique(hash, key, value);
610 self.map.entries[i].muts()
611 }
612
613 /// Inserts the given key and value into the map at the given index,
614 /// shifting others to the right, and returns mutable references to them.
615 ///
616 /// ***Panics*** if `index` is out of bounds.
617 ///
618 /// Computes in **O(n)** time (average).
619 pub fn shift_insert(self, index: usize, key: K, value: V) -> (&'a mut K, &'a mut V)
620 where
621 K: Hash,
622 S: BuildHasher,
623 {
624 let mut h = self.hash_builder.build_hasher();
625 key.hash(&mut h);
626 self.shift_insert_hashed_nocheck(index, h.finish(), key, value)
627 }
628
629 /// Inserts the given key and value into the map with the provided hash
630 /// at the given index, and returns mutable references to them.
631 ///
632 /// ***Panics*** if `index` is out of bounds.
633 ///
634 /// Computes in **O(n)** time (average).
635 pub fn shift_insert_hashed_nocheck(
636 self,
637 index: usize,
638 hash: u64,
639 key: K,
640 value: V,
641 ) -> (&'a mut K, &'a mut V) {
642 let hash = HashValue(hash as usize);
643 self.map.shift_insert_unique(index, hash, key, value);
644 self.map.entries[index].muts()
645 }
646}
647
648mod private {
649 pub trait Sealed {}
650
651 impl<K, V, S> Sealed for super::IndexMap<K, V, S> {}
652}