1 //! This is the core implementation that doesn't depend on the hasher at all.
2 //!
3 //! The methods of `IndexMapCore` don't use any Hash properties of K.
4 //!
5 //! It's cleaner to separate them out, then the compiler checks that we are not
6 //! using Hash at all in these methods.
7 //!
8 //! However, we should probably not let this show in the public API or docs.
9
10 mod raw;
11
12 use hashbrown::raw::RawTable;
13
14 use crate::vec::{Drain, Vec};
15 use core::cmp;
16 use core::fmt;
17 use core::mem::replace;
18 use core::ops::RangeBounds;
19
20 use crate::equivalent::Equivalent;
21 use crate::util::{enumerate, simplify_range};
22 use crate::{Bucket, Entries, HashValue};
23
24 /// Core of the map that does not depend on S
25 pub(crate) struct IndexMapCore<K, V> {
26 /// indices mapping from the entry hash to its index.
27 indices: RawTable<usize>,
28 /// entries is a dense vec of entries in their order.
29 entries: Vec<Bucket<K, V>>,
30 }
31
32 #[inline(always)]
get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_33 fn get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_ {
34 move |&i| entries[i].hash.get()
35 }
36
37 #[inline]
equivalent<'a, K, V, Q: ?Sized + Equivalent<K>>( key: &'a Q, entries: &'a [Bucket<K, V>], ) -> impl Fn(&usize) -> bool + 'a38 fn equivalent<'a, K, V, Q: ?Sized + Equivalent<K>>(
39 key: &'a Q,
40 entries: &'a [Bucket<K, V>],
41 ) -> impl Fn(&usize) -> bool + 'a {
42 move |&i| Q::equivalent(key, &entries[i].key)
43 }
44
45 #[inline]
erase_index(table: &mut RawTable<usize>, hash: HashValue, index: usize)46 fn erase_index(table: &mut RawTable<usize>, hash: HashValue, index: usize) {
47 table.erase_entry(hash.get(), move |&i| i == index);
48 }
49
50 #[inline]
update_index(table: &mut RawTable<usize>, hash: HashValue, old: usize, new: usize)51 fn update_index(table: &mut RawTable<usize>, hash: HashValue, old: usize, new: usize) {
52 let index = table
53 .get_mut(hash.get(), move |&i| i == old)
54 .expect("index not found");
55 *index = new;
56 }
57
58 impl<K, V> Clone for IndexMapCore<K, V>
59 where
60 K: Clone,
61 V: Clone,
62 {
clone(&self) -> Self63 fn clone(&self) -> Self {
64 let indices = self.indices.clone();
65 let mut entries = Vec::with_capacity(indices.capacity());
66 entries.clone_from(&self.entries);
67 IndexMapCore { indices, entries }
68 }
69
clone_from(&mut self, other: &Self)70 fn clone_from(&mut self, other: &Self) {
71 let hasher = get_hash(&other.entries);
72 self.indices.clone_from_with_hasher(&other.indices, hasher);
73 if self.entries.capacity() < other.entries.len() {
74 // If we must resize, match the indices capacity
75 self.reserve_entries();
76 }
77 self.entries.clone_from(&other.entries);
78 }
79 }
80
81 impl<K, V> fmt::Debug for IndexMapCore<K, V>
82 where
83 K: fmt::Debug,
84 V: fmt::Debug,
85 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result86 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
87 f.debug_struct("IndexMapCore")
88 .field("indices", &raw::DebugIndices(&self.indices))
89 .field("entries", &self.entries)
90 .finish()
91 }
92 }
93
94 impl<K, V> Entries for IndexMapCore<K, V> {
95 type Entry = Bucket<K, V>;
96
97 #[inline]
into_entries(self) -> Vec<Self::Entry>98 fn into_entries(self) -> Vec<Self::Entry> {
99 self.entries
100 }
101
102 #[inline]
as_entries(&self) -> &[Self::Entry]103 fn as_entries(&self) -> &[Self::Entry] {
104 &self.entries
105 }
106
107 #[inline]
as_entries_mut(&mut self) -> &mut [Self::Entry]108 fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
109 &mut self.entries
110 }
111
with_entries<F>(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]),112 fn with_entries<F>(&mut self, f: F)
113 where
114 F: FnOnce(&mut [Self::Entry]),
115 {
116 f(&mut self.entries);
117 self.rebuild_hash_table();
118 }
119 }
120
121 impl<K, V> IndexMapCore<K, V> {
122 #[inline]
new() -> Self123 pub(crate) const fn new() -> Self {
124 IndexMapCore {
125 indices: RawTable::new(),
126 entries: Vec::new(),
127 }
128 }
129
130 #[inline]
with_capacity(n: usize) -> Self131 pub(crate) fn with_capacity(n: usize) -> Self {
132 IndexMapCore {
133 indices: RawTable::with_capacity(n),
134 entries: Vec::with_capacity(n),
135 }
136 }
137
138 #[inline]
len(&self) -> usize139 pub(crate) fn len(&self) -> usize {
140 self.indices.len()
141 }
142
143 #[inline]
capacity(&self) -> usize144 pub(crate) fn capacity(&self) -> usize {
145 cmp::min(self.indices.capacity(), self.entries.capacity())
146 }
147
clear(&mut self)148 pub(crate) fn clear(&mut self) {
149 self.indices.clear();
150 self.entries.clear();
151 }
152
truncate(&mut self, len: usize)153 pub(crate) fn truncate(&mut self, len: usize) {
154 if len < self.len() {
155 self.erase_indices(len, self.entries.len());
156 self.entries.truncate(len);
157 }
158 }
159
drain<R>(&mut self, range: R) -> Drain<'_, Bucket<K, V>> where R: RangeBounds<usize>,160 pub(crate) fn drain<R>(&mut self, range: R) -> Drain<'_, Bucket<K, V>>
161 where
162 R: RangeBounds<usize>,
163 {
164 let range = simplify_range(range, self.entries.len());
165 self.erase_indices(range.start, range.end);
166 self.entries.drain(range)
167 }
168
169 #[cfg(feature = "rayon")]
par_drain<R>(&mut self, range: R) -> rayon::vec::Drain<'_, Bucket<K, V>> where K: Send, V: Send, R: RangeBounds<usize>,170 pub(crate) fn par_drain<R>(&mut self, range: R) -> rayon::vec::Drain<'_, Bucket<K, V>>
171 where
172 K: Send,
173 V: Send,
174 R: RangeBounds<usize>,
175 {
176 use rayon::iter::ParallelDrainRange;
177 let range = simplify_range(range, self.entries.len());
178 self.erase_indices(range.start, range.end);
179 self.entries.par_drain(range)
180 }
181
split_off(&mut self, at: usize) -> Self182 pub(crate) fn split_off(&mut self, at: usize) -> Self {
183 assert!(at <= self.entries.len());
184 self.erase_indices(at, self.entries.len());
185 let entries = self.entries.split_off(at);
186
187 let mut indices = RawTable::with_capacity(entries.len());
188 for (i, entry) in enumerate(&entries) {
189 indices.insert_no_grow(entry.hash.get(), i);
190 }
191 Self { indices, entries }
192 }
193
194 /// Reserve capacity for `additional` more key-value pairs.
reserve(&mut self, additional: usize)195 pub(crate) fn reserve(&mut self, additional: usize) {
196 self.indices.reserve(additional, get_hash(&self.entries));
197 self.reserve_entries();
198 }
199
200 /// Reserve entries capacity to match the indices
reserve_entries(&mut self)201 fn reserve_entries(&mut self) {
202 let additional = self.indices.capacity() - self.entries.len();
203 self.entries.reserve_exact(additional);
204 }
205
206 /// Shrink the capacity of the map as much as possible.
shrink_to_fit(&mut self)207 pub(crate) fn shrink_to_fit(&mut self) {
208 self.indices.shrink_to(0, get_hash(&self.entries));
209 self.entries.shrink_to_fit();
210 }
211
212 /// Remove the last key-value pair
pop(&mut self) -> Option<(K, V)>213 pub(crate) fn pop(&mut self) -> Option<(K, V)> {
214 if let Some(entry) = self.entries.pop() {
215 let last = self.entries.len();
216 erase_index(&mut self.indices, entry.hash, last);
217 Some((entry.key, entry.value))
218 } else {
219 None
220 }
221 }
222
223 /// Append a key-value pair, *without* checking whether it already exists,
224 /// and return the pair's new index.
push(&mut self, hash: HashValue, key: K, value: V) -> usize225 fn push(&mut self, hash: HashValue, key: K, value: V) -> usize {
226 let i = self.entries.len();
227 self.indices.insert(hash.get(), i, get_hash(&self.entries));
228 if i == self.entries.capacity() {
229 // Reserve our own capacity synced to the indices,
230 // rather than letting `Vec::push` just double it.
231 self.reserve_entries();
232 }
233 self.entries.push(Bucket { hash, key, value });
234 i
235 }
236
237 /// Return the index in `entries` where an equivalent key can be found
get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize> where Q: ?Sized + Equivalent<K>,238 pub(crate) fn get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize>
239 where
240 Q: ?Sized + Equivalent<K>,
241 {
242 let eq = equivalent(key, &self.entries);
243 self.indices.get(hash.get(), eq).copied()
244 }
245
insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option<V>) where K: Eq,246 pub(crate) fn insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option<V>)
247 where
248 K: Eq,
249 {
250 match self.get_index_of(hash, &key) {
251 Some(i) => (i, Some(replace(&mut self.entries[i].value, value))),
252 None => (self.push(hash, key, value), None),
253 }
254 }
255
256 /// Remove an entry by shifting all entries that follow it
shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> where Q: ?Sized + Equivalent<K>,257 pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
258 where
259 Q: ?Sized + Equivalent<K>,
260 {
261 let eq = equivalent(key, &self.entries);
262 match self.indices.remove_entry(hash.get(), eq) {
263 Some(index) => {
264 let (key, value) = self.shift_remove_finish(index);
265 Some((index, key, value))
266 }
267 None => None,
268 }
269 }
270
271 /// Remove an entry by shifting all entries that follow it
shift_remove_index(&mut self, index: usize) -> Option<(K, V)>272 pub(crate) fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> {
273 match self.entries.get(index) {
274 Some(entry) => {
275 erase_index(&mut self.indices, entry.hash, index);
276 Some(self.shift_remove_finish(index))
277 }
278 None => None,
279 }
280 }
281
282 /// Remove an entry by shifting all entries that follow it
283 ///
284 /// The index should already be removed from `self.indices`.
shift_remove_finish(&mut self, index: usize) -> (K, V)285 fn shift_remove_finish(&mut self, index: usize) -> (K, V) {
286 // use Vec::remove, but then we need to update the indices that point
287 // to all of the other entries that have to move
288 let entry = self.entries.remove(index);
289
290 // correct indices that point to the entries that followed the removed entry.
291 // use a heuristic between a full sweep vs. a `find()` for every shifted item.
292 let raw_capacity = self.indices.buckets();
293 let shifted_entries = &self.entries[index..];
294 if shifted_entries.len() > raw_capacity / 2 {
295 // shift all indices greater than `index`
296 for i in self.indices_mut() {
297 if *i > index {
298 *i -= 1;
299 }
300 }
301 } else {
302 // find each following entry to shift its index
303 for (i, entry) in (index + 1..).zip(shifted_entries) {
304 update_index(&mut self.indices, entry.hash, i, i - 1);
305 }
306 }
307
308 (entry.key, entry.value)
309 }
310
311 /// Remove an entry by swapping it with the last
swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> where Q: ?Sized + Equivalent<K>,312 pub(crate) fn swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
313 where
314 Q: ?Sized + Equivalent<K>,
315 {
316 let eq = equivalent(key, &self.entries);
317 match self.indices.remove_entry(hash.get(), eq) {
318 Some(index) => {
319 let (key, value) = self.swap_remove_finish(index);
320 Some((index, key, value))
321 }
322 None => None,
323 }
324 }
325
326 /// Remove an entry by swapping it with the last
swap_remove_index(&mut self, index: usize) -> Option<(K, V)>327 pub(crate) fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> {
328 match self.entries.get(index) {
329 Some(entry) => {
330 erase_index(&mut self.indices, entry.hash, index);
331 Some(self.swap_remove_finish(index))
332 }
333 None => None,
334 }
335 }
336
337 /// Finish removing an entry by swapping it with the last
338 ///
339 /// The index should already be removed from `self.indices`.
swap_remove_finish(&mut self, index: usize) -> (K, V)340 fn swap_remove_finish(&mut self, index: usize) -> (K, V) {
341 // use swap_remove, but then we need to update the index that points
342 // to the other entry that has to move
343 let entry = self.entries.swap_remove(index);
344
345 // correct index that points to the entry that had to swap places
346 if let Some(entry) = self.entries.get(index) {
347 // was not last element
348 // examine new element in `index` and find it in indices
349 let last = self.entries.len();
350 update_index(&mut self.indices, entry.hash, last, index);
351 }
352
353 (entry.key, entry.value)
354 }
355
356 /// Erase `start..end` from `indices`, and shift `end..` indices down to `start..`
357 ///
358 /// All of these items should still be at their original location in `entries`.
359 /// This is used by `drain`, which will let `Vec::drain` do the work on `entries`.
erase_indices(&mut self, start: usize, end: usize)360 fn erase_indices(&mut self, start: usize, end: usize) {
361 let (init, shifted_entries) = self.entries.split_at(end);
362 let (start_entries, erased_entries) = init.split_at(start);
363
364 let erased = erased_entries.len();
365 let shifted = shifted_entries.len();
366 let half_capacity = self.indices.buckets() / 2;
367
368 // Use a heuristic between different strategies
369 if erased == 0 {
370 // Degenerate case, nothing to do
371 } else if start + shifted < half_capacity && start < erased {
372 // Reinsert everything, as there are few kept indices
373 self.indices.clear();
374
375 // Reinsert stable indices
376 for (i, entry) in enumerate(start_entries) {
377 self.indices.insert_no_grow(entry.hash.get(), i);
378 }
379
380 // Reinsert shifted indices
381 for (i, entry) in (start..).zip(shifted_entries) {
382 self.indices.insert_no_grow(entry.hash.get(), i);
383 }
384 } else if erased + shifted < half_capacity {
385 // Find each affected index, as there are few to adjust
386
387 // Find erased indices
388 for (i, entry) in (start..).zip(erased_entries) {
389 erase_index(&mut self.indices, entry.hash, i);
390 }
391
392 // Find shifted indices
393 for ((new, old), entry) in (start..).zip(end..).zip(shifted_entries) {
394 update_index(&mut self.indices, entry.hash, old, new);
395 }
396 } else {
397 // Sweep the whole table for adjustments
398 self.erase_indices_sweep(start, end);
399 }
400
401 debug_assert_eq!(self.indices.len(), start + shifted);
402 }
403
retain_in_order<F>(&mut self, mut keep: F) where F: FnMut(&mut K, &mut V) -> bool,404 pub(crate) fn retain_in_order<F>(&mut self, mut keep: F)
405 where
406 F: FnMut(&mut K, &mut V) -> bool,
407 {
408 // Like Vec::retain in self.entries, but with mutable K and V.
409 // We swap-shift all the items we want to keep, truncate the rest,
410 // then rebuild the raw hash table with the new indexes.
411 let len = self.entries.len();
412 let mut n_deleted = 0;
413 for i in 0..len {
414 let will_keep = {
415 let entry = &mut self.entries[i];
416 keep(&mut entry.key, &mut entry.value)
417 };
418 if !will_keep {
419 n_deleted += 1;
420 } else if n_deleted > 0 {
421 self.entries.swap(i - n_deleted, i);
422 }
423 }
424 if n_deleted > 0 {
425 self.entries.truncate(len - n_deleted);
426 self.rebuild_hash_table();
427 }
428 }
429
rebuild_hash_table(&mut self)430 fn rebuild_hash_table(&mut self) {
431 self.indices.clear();
432 debug_assert!(self.indices.capacity() >= self.entries.len());
433 for (i, entry) in enumerate(&self.entries) {
434 // We should never have to reallocate, so there's no need for a real hasher.
435 self.indices.insert_no_grow(entry.hash.get(), i);
436 }
437 }
438
reverse(&mut self)439 pub(crate) fn reverse(&mut self) {
440 self.entries.reverse();
441
442 // No need to save hash indices, can easily calculate what they should
443 // be, given that this is an in-place reversal.
444 let len = self.entries.len();
445 for i in self.indices_mut() {
446 *i = len - *i - 1;
447 }
448 }
449 }
450
451 /// Entry for an existing key-value pair or a vacant location to
452 /// insert one.
453 pub enum Entry<'a, K, V> {
454 /// Existing slot with equivalent key.
455 Occupied(OccupiedEntry<'a, K, V>),
456 /// Vacant slot (no equivalent key in the map).
457 Vacant(VacantEntry<'a, K, V>),
458 }
459
460 impl<'a, K, V> Entry<'a, K, V> {
461 /// Inserts the given default value in the entry if it is vacant and returns a mutable
462 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
463 ///
464 /// Computes in **O(1)** time (amortized average).
or_insert(self, default: V) -> &'a mut V465 pub fn or_insert(self, default: V) -> &'a mut V {
466 match self {
467 Entry::Occupied(entry) => entry.into_mut(),
468 Entry::Vacant(entry) => entry.insert(default),
469 }
470 }
471
472 /// Inserts the result of the `call` function in the entry if it is vacant and returns a mutable
473 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
474 ///
475 /// Computes in **O(1)** time (amortized average).
or_insert_with<F>(self, call: F) -> &'a mut V where F: FnOnce() -> V,476 pub fn or_insert_with<F>(self, call: F) -> &'a mut V
477 where
478 F: FnOnce() -> V,
479 {
480 match self {
481 Entry::Occupied(entry) => entry.into_mut(),
482 Entry::Vacant(entry) => entry.insert(call()),
483 }
484 }
485
486 /// Inserts the result of the `call` function with a reference to the entry's key if it is
487 /// vacant, and returns a mutable reference to the new value. Otherwise a mutable reference to
488 /// an already existent value is returned.
489 ///
490 /// Computes in **O(1)** time (amortized average).
or_insert_with_key<F>(self, call: F) -> &'a mut V where F: FnOnce(&K) -> V,491 pub fn or_insert_with_key<F>(self, call: F) -> &'a mut V
492 where
493 F: FnOnce(&K) -> V,
494 {
495 match self {
496 Entry::Occupied(entry) => entry.into_mut(),
497 Entry::Vacant(entry) => {
498 let value = call(&entry.key);
499 entry.insert(value)
500 }
501 }
502 }
503
504 /// Gets a reference to the entry's key, either within the map if occupied,
505 /// or else the new key that was used to find the entry.
key(&self) -> &K506 pub fn key(&self) -> &K {
507 match *self {
508 Entry::Occupied(ref entry) => entry.key(),
509 Entry::Vacant(ref entry) => entry.key(),
510 }
511 }
512
513 /// Return the index where the key-value pair exists or will be inserted.
index(&self) -> usize514 pub fn index(&self) -> usize {
515 match *self {
516 Entry::Occupied(ref entry) => entry.index(),
517 Entry::Vacant(ref entry) => entry.index(),
518 }
519 }
520
521 /// Modifies the entry if it is occupied.
and_modify<F>(self, f: F) -> Self where F: FnOnce(&mut V),522 pub fn and_modify<F>(self, f: F) -> Self
523 where
524 F: FnOnce(&mut V),
525 {
526 match self {
527 Entry::Occupied(mut o) => {
528 f(o.get_mut());
529 Entry::Occupied(o)
530 }
531 x => x,
532 }
533 }
534
535 /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
536 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
537 ///
538 /// Computes in **O(1)** time (amortized average).
or_default(self) -> &'a mut V where V: Default,539 pub fn or_default(self) -> &'a mut V
540 where
541 V: Default,
542 {
543 match self {
544 Entry::Occupied(entry) => entry.into_mut(),
545 Entry::Vacant(entry) => entry.insert(V::default()),
546 }
547 }
548 }
549
550 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Entry<'_, K, V> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result551 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
552 match *self {
553 Entry::Vacant(ref v) => f.debug_tuple(stringify!(Entry)).field(v).finish(),
554 Entry::Occupied(ref o) => f.debug_tuple(stringify!(Entry)).field(o).finish(),
555 }
556 }
557 }
558
559 pub use self::raw::OccupiedEntry;
560
561 // Extra methods that don't threaten the unsafe encapsulation.
562 impl<K, V> OccupiedEntry<'_, K, V> {
563 /// Sets the value of the entry to `value`, and returns the entry's old value.
insert(&mut self, value: V) -> V564 pub fn insert(&mut self, value: V) -> V {
565 replace(self.get_mut(), value)
566 }
567
568 /// Remove the key, value pair stored in the map for this entry, and return the value.
569 ///
570 /// **NOTE:** This is equivalent to `.swap_remove()`.
remove(self) -> V571 pub fn remove(self) -> V {
572 self.swap_remove()
573 }
574
575 /// Remove the key, value pair stored in the map for this entry, and return the value.
576 ///
577 /// Like `Vec::swap_remove`, the pair is removed by swapping it with the
578 /// last element of the map and popping it off. **This perturbs
579 /// the position of what used to be the last element!**
580 ///
581 /// Computes in **O(1)** time (average).
swap_remove(self) -> V582 pub fn swap_remove(self) -> V {
583 self.swap_remove_entry().1
584 }
585
586 /// Remove the key, value pair stored in the map for this entry, and return the value.
587 ///
588 /// Like `Vec::remove`, the pair is removed by shifting all of the
589 /// elements that follow it, preserving their relative order.
590 /// **This perturbs the index of all of those elements!**
591 ///
592 /// Computes in **O(n)** time (average).
shift_remove(self) -> V593 pub fn shift_remove(self) -> V {
594 self.shift_remove_entry().1
595 }
596
597 /// Remove and return the key, value pair stored in the map for this entry
598 ///
599 /// **NOTE:** This is equivalent to `.swap_remove_entry()`.
remove_entry(self) -> (K, V)600 pub fn remove_entry(self) -> (K, V) {
601 self.swap_remove_entry()
602 }
603 }
604
605 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for OccupiedEntry<'_, K, V> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result606 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
607 f.debug_struct(stringify!(OccupiedEntry))
608 .field("key", self.key())
609 .field("value", self.get())
610 .finish()
611 }
612 }
613
614 /// A view into a vacant entry in a `IndexMap`.
615 /// It is part of the [`Entry`] enum.
616 ///
617 /// [`Entry`]: enum.Entry.html
618 pub struct VacantEntry<'a, K, V> {
619 map: &'a mut IndexMapCore<K, V>,
620 hash: HashValue,
621 key: K,
622 }
623
624 impl<'a, K, V> VacantEntry<'a, K, V> {
625 /// Gets a reference to the key that was used to find the entry.
key(&self) -> &K626 pub fn key(&self) -> &K {
627 &self.key
628 }
629
630 /// Takes ownership of the key, leaving the entry vacant.
into_key(self) -> K631 pub fn into_key(self) -> K {
632 self.key
633 }
634
635 /// Return the index where the key-value pair will be inserted.
index(&self) -> usize636 pub fn index(&self) -> usize {
637 self.map.len()
638 }
639
640 /// Inserts the entry's key and the given value into the map, and returns a mutable reference
641 /// to the value.
insert(self, value: V) -> &'a mut V642 pub fn insert(self, value: V) -> &'a mut V {
643 let i = self.map.push(self.hash, self.key, value);
644 &mut self.map.entries[i].value
645 }
646 }
647
648 impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result649 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
650 f.debug_tuple(stringify!(VacantEntry))
651 .field(self.key())
652 .finish()
653 }
654 }
655
656 #[test]
assert_send_sync()657 fn assert_send_sync() {
658 fn assert_send_sync<T: Send + Sync>() {}
659 assert_send_sync::<IndexMapCore<i32, i32>>();
660 assert_send_sync::<Entry<'_, i32, i32>>();
661 }
662