1use super::{equivalent, Entries, IndexMapCore, RefMut};
2use crate::HashValue;
3use core::{fmt, mem};
4use hashbrown::hash_table;
5
6impl<K, V> IndexMapCore<K, V> {
7 pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V>
8 where
9 K: Eq,
10 {
11 let entries: &mut Vec> = &mut self.entries;
12 let eq: impl Fn(&usize) -> bool = equivalent(&key, entries);
13 match self.indices.find_entry(hash.get(), eq) {
14 Ok(index: OccupiedEntry<'_, usize>) => Entry::Occupied(OccupiedEntry { entries, index }),
15 Err(absent: AbsentEntry<'_, usize>) => Entry::Vacant(VacantEntry {
16 map: RefMut::new(indices:absent.into_table(), entries),
17 hash,
18 key,
19 }),
20 }
21 }
22}
23
24/// Entry for an existing key-value pair in an [`IndexMap`][crate::IndexMap]
25/// or a vacant location to insert one.
26pub enum Entry<'a, K, V> {
27 /// Existing slot with equivalent key.
28 Occupied(OccupiedEntry<'a, K, V>),
29 /// Vacant slot (no equivalent key in the map).
30 Vacant(VacantEntry<'a, K, V>),
31}
32
33impl<'a, K, V> Entry<'a, K, V> {
34 /// Return the index where the key-value pair exists or will be inserted.
35 pub fn index(&self) -> usize {
36 match *self {
37 Entry::Occupied(ref entry) => entry.index(),
38 Entry::Vacant(ref entry) => entry.index(),
39 }
40 }
41
42 /// Sets the value of the entry (after inserting if vacant), and returns an `OccupiedEntry`.
43 ///
44 /// Computes in **O(1)** time (amortized average).
45 pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
46 match self {
47 Entry::Occupied(mut entry) => {
48 entry.insert(value);
49 entry
50 }
51 Entry::Vacant(entry) => entry.insert_entry(value),
52 }
53 }
54
55 /// Inserts the given default value in the entry if it is vacant and returns a mutable
56 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
57 ///
58 /// Computes in **O(1)** time (amortized average).
59 pub fn or_insert(self, default: V) -> &'a mut V {
60 match self {
61 Entry::Occupied(entry) => entry.into_mut(),
62 Entry::Vacant(entry) => entry.insert(default),
63 }
64 }
65
66 /// Inserts the result of the `call` function in the entry if it is vacant and returns a mutable
67 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
68 ///
69 /// Computes in **O(1)** time (amortized average).
70 pub fn or_insert_with<F>(self, call: F) -> &'a mut V
71 where
72 F: FnOnce() -> V,
73 {
74 match self {
75 Entry::Occupied(entry) => entry.into_mut(),
76 Entry::Vacant(entry) => entry.insert(call()),
77 }
78 }
79
80 /// Inserts the result of the `call` function with a reference to the entry's key if it is
81 /// vacant, and returns a mutable reference to the new value. Otherwise a mutable reference to
82 /// an already existent value is returned.
83 ///
84 /// Computes in **O(1)** time (amortized average).
85 pub fn or_insert_with_key<F>(self, call: F) -> &'a mut V
86 where
87 F: FnOnce(&K) -> V,
88 {
89 match self {
90 Entry::Occupied(entry) => entry.into_mut(),
91 Entry::Vacant(entry) => {
92 let value = call(&entry.key);
93 entry.insert(value)
94 }
95 }
96 }
97
98 /// Gets a reference to the entry's key, either within the map if occupied,
99 /// or else the new key that was used to find the entry.
100 pub fn key(&self) -> &K {
101 match *self {
102 Entry::Occupied(ref entry) => entry.key(),
103 Entry::Vacant(ref entry) => entry.key(),
104 }
105 }
106
107 /// Modifies the entry if it is occupied.
108 pub fn and_modify<F>(mut self, f: F) -> Self
109 where
110 F: FnOnce(&mut V),
111 {
112 if let Entry::Occupied(entry) = &mut self {
113 f(entry.get_mut());
114 }
115 self
116 }
117
118 /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
119 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
120 ///
121 /// Computes in **O(1)** time (amortized average).
122 pub fn or_default(self) -> &'a mut V
123 where
124 V: Default,
125 {
126 match self {
127 Entry::Occupied(entry) => entry.into_mut(),
128 Entry::Vacant(entry) => entry.insert(V::default()),
129 }
130 }
131}
132
133impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Entry<'_, K, V> {
134 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
135 let mut tuple: DebugTuple<'_, '_> = f.debug_tuple(name:"Entry");
136 match self {
137 Entry::Vacant(v: &VacantEntry<'_, K, V>) => tuple.field(v),
138 Entry::Occupied(o: &OccupiedEntry<'_, K, V>) => tuple.field(o),
139 };
140 tuple.finish()
141 }
142}
143
144/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap].
145/// It is part of the [`Entry`] enum.
146pub struct OccupiedEntry<'a, K, V> {
147 entries: &'a mut Entries<K, V>,
148 index: hash_table::OccupiedEntry<'a, usize>,
149}
150
151impl<'a, K, V> OccupiedEntry<'a, K, V> {
152 pub(crate) fn new(
153 entries: &'a mut Entries<K, V>,
154 index: hash_table::OccupiedEntry<'a, usize>,
155 ) -> Self {
156 Self { entries, index }
157 }
158
159 /// Return the index of the key-value pair
160 #[inline]
161 pub fn index(&self) -> usize {
162 *self.index.get()
163 }
164
165 #[inline]
166 fn into_ref_mut(self) -> RefMut<'a, K, V> {
167 RefMut::new(self.index.into_table(), self.entries)
168 }
169
170 /// Gets a reference to the entry's key in the map.
171 ///
172 /// Note that this is not the key that was used to find the entry. There may be an observable
173 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
174 /// extra fields or the memory address of an allocation.
175 pub fn key(&self) -> &K {
176 &self.entries[self.index()].key
177 }
178
179 pub(crate) fn key_mut(&mut self) -> &mut K {
180 let index = self.index();
181 &mut self.entries[index].key
182 }
183
184 /// Gets a reference to the entry's value in the map.
185 pub fn get(&self) -> &V {
186 &self.entries[self.index()].value
187 }
188
189 /// Gets a mutable reference to the entry's value in the map.
190 ///
191 /// If you need a reference which may outlive the destruction of the
192 /// [`Entry`] value, see [`into_mut`][Self::into_mut].
193 pub fn get_mut(&mut self) -> &mut V {
194 let index = self.index();
195 &mut self.entries[index].value
196 }
197
198 /// Converts into a mutable reference to the entry's value in the map,
199 /// with a lifetime bound to the map itself.
200 pub fn into_mut(self) -> &'a mut V {
201 let index = self.index();
202 &mut self.entries[index].value
203 }
204
205 pub(super) fn into_muts(self) -> (&'a mut K, &'a mut V) {
206 let index = self.index();
207 self.entries[index].muts()
208 }
209
210 /// Sets the value of the entry to `value`, and returns the entry's old value.
211 pub fn insert(&mut self, value: V) -> V {
212 mem::replace(self.get_mut(), value)
213 }
214
215 /// Remove the key, value pair stored in the map for this entry, and return the value.
216 ///
217 /// **NOTE:** This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this
218 /// entry's position with the last element, and it is deprecated in favor of calling that
219 /// explicitly. If you need to preserve the relative order of the keys in the map, use
220 /// [`.shift_remove()`][Self::shift_remove] instead.
221 #[deprecated(note = "`remove` disrupts the map order -- \
222 use `swap_remove` or `shift_remove` for explicit behavior.")]
223 pub fn remove(self) -> V {
224 self.swap_remove()
225 }
226
227 /// Remove the key, value pair stored in the map for this entry, and return the value.
228 ///
229 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
230 /// the last element of the map and popping it off.
231 /// **This perturbs the position of what used to be the last element!**
232 ///
233 /// Computes in **O(1)** time (average).
234 pub fn swap_remove(self) -> V {
235 self.swap_remove_entry().1
236 }
237
238 /// Remove the key, value pair stored in the map for this entry, and return the value.
239 ///
240 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
241 /// elements that follow it, preserving their relative order.
242 /// **This perturbs the index of all of those elements!**
243 ///
244 /// Computes in **O(n)** time (average).
245 pub fn shift_remove(self) -> V {
246 self.shift_remove_entry().1
247 }
248
249 /// Remove and return the key, value pair stored in the map for this entry
250 ///
251 /// **NOTE:** This is equivalent to [`.swap_remove_entry()`][Self::swap_remove_entry],
252 /// replacing this entry's position with the last element, and it is deprecated in favor of
253 /// calling that explicitly. If you need to preserve the relative order of the keys in the map,
254 /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead.
255 #[deprecated(note = "`remove_entry` disrupts the map order -- \
256 use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")]
257 pub fn remove_entry(self) -> (K, V) {
258 self.swap_remove_entry()
259 }
260
261 /// Remove and return the key, value pair stored in the map for this entry
262 ///
263 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
264 /// the last element of the map and popping it off.
265 /// **This perturbs the position of what used to be the last element!**
266 ///
267 /// Computes in **O(1)** time (average).
268 pub fn swap_remove_entry(self) -> (K, V) {
269 let (index, entry) = self.index.remove();
270 RefMut::new(entry.into_table(), self.entries).swap_remove_finish(index)
271 }
272
273 /// Remove and return the key, value pair stored in the map for this entry
274 ///
275 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
276 /// elements that follow it, preserving their relative order.
277 /// **This perturbs the index of all of those elements!**
278 ///
279 /// Computes in **O(n)** time (average).
280 pub fn shift_remove_entry(self) -> (K, V) {
281 let (index, entry) = self.index.remove();
282 RefMut::new(entry.into_table(), self.entries).shift_remove_finish(index)
283 }
284
285 /// Moves the position of the entry to a new index
286 /// by shifting all other entries in-between.
287 ///
288 /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
289 /// coming `from` the current [`.index()`][Self::index].
290 ///
291 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
292 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
293 ///
294 /// ***Panics*** if `to` is out of bounds.
295 ///
296 /// Computes in **O(n)** time (average).
297 #[track_caller]
298 pub fn move_index(self, to: usize) {
299 let index = self.index();
300 self.into_ref_mut().move_index(index, to);
301 }
302
303 /// Swaps the position of entry with another.
304 ///
305 /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
306 /// with the current [`.index()`][Self::index] as one of the two being swapped.
307 ///
308 /// ***Panics*** if the `other` index is out of bounds.
309 ///
310 /// Computes in **O(1)** time (average).
311 pub fn swap_indices(self, other: usize) {
312 let index = self.index();
313 self.into_ref_mut().swap_indices(index, other);
314 }
315}
316
317impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for OccupiedEntry<'_, K, V> {
318 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
319 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
320 .field("key", self.key())
321 .field(name:"value", self.get())
322 .finish()
323 }
324}
325
326impl<'a, K, V> From<IndexedEntry<'a, K, V>> for OccupiedEntry<'a, K, V> {
327 fn from(other: IndexedEntry<'a, K, V>) -> Self {
328 let IndexedEntry {
329 map: RefMut { indices: &mut HashTable, entries: &mut Vec> },
330 index: usize,
331 } = other;
332 let hash: HashValue = entries[index].hash;
333 Self {
334 entries,
335 index: indices
336 .find_entry(hash.get(), move |&i| i == index)
337 .expect(msg:"index not found"),
338 }
339 }
340}
341
342/// A view into a vacant entry in an [`IndexMap`][crate::IndexMap].
343/// It is part of the [`Entry`] enum.
344pub struct VacantEntry<'a, K, V> {
345 map: RefMut<'a, K, V>,
346 hash: HashValue,
347 key: K,
348}
349
350impl<'a, K, V> VacantEntry<'a, K, V> {
351 /// Return the index where a key-value pair may be inserted.
352 pub fn index(&self) -> usize {
353 self.map.indices.len()
354 }
355
356 /// Gets a reference to the key that was used to find the entry.
357 pub fn key(&self) -> &K {
358 &self.key
359 }
360
361 pub(crate) fn key_mut(&mut self) -> &mut K {
362 &mut self.key
363 }
364
365 /// Takes ownership of the key, leaving the entry vacant.
366 pub fn into_key(self) -> K {
367 self.key
368 }
369
370 /// Inserts the entry's key and the given value into the map, and returns a mutable reference
371 /// to the value.
372 ///
373 /// Computes in **O(1)** time (amortized average).
374 pub fn insert(self, value: V) -> &'a mut V {
375 self.insert_entry(value).into_mut()
376 }
377
378 /// Inserts the entry's key and the given value into the map, and returns an `OccupiedEntry`.
379 ///
380 /// Computes in **O(1)** time (amortized average).
381 pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
382 let Self { map, hash, key } = self;
383 map.insert_unique(hash, key, value)
384 }
385
386 /// Inserts the entry's key and the given value into the map at its ordered
387 /// position among sorted keys, and returns the new index and a mutable
388 /// reference to the value.
389 ///
390 /// If the existing keys are **not** already sorted, then the insertion
391 /// index is unspecified (like [`slice::binary_search`]), but the key-value
392 /// pair is inserted at that position regardless.
393 ///
394 /// Computes in **O(n)** time (average).
395 pub fn insert_sorted(self, value: V) -> (usize, &'a mut V)
396 where
397 K: Ord,
398 {
399 let slice = crate::map::Slice::from_slice(self.map.entries);
400 let i = slice.binary_search_keys(&self.key).unwrap_err();
401 (i, self.shift_insert(i, value))
402 }
403
404 /// Inserts the entry's key and the given value into the map at the given index,
405 /// shifting others to the right, and returns a mutable reference to the value.
406 ///
407 /// ***Panics*** if `index` is out of bounds.
408 ///
409 /// Computes in **O(n)** time (average).
410 pub fn shift_insert(mut self, index: usize, value: V) -> &'a mut V {
411 self.map
412 .shift_insert_unique(index, self.hash, self.key, value);
413 &mut self.map.entries[index].value
414 }
415}
416
417impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> {
418 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
419 f.debug_tuple(name:"VacantEntry").field(self.key()).finish()
420 }
421}
422
423/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap] obtained by index.
424///
425/// This `struct` is created from the [`get_index_entry`][crate::IndexMap::get_index_entry] method.
426pub struct IndexedEntry<'a, K, V> {
427 map: RefMut<'a, K, V>,
428 // We have a mutable reference to the map, which keeps the index
429 // valid and pointing to the correct entry.
430 index: usize,
431}
432
433impl<'a, K, V> IndexedEntry<'a, K, V> {
434 pub(crate) fn new(map: &'a mut IndexMapCore<K, V>, index: usize) -> Self {
435 Self {
436 map: map.borrow_mut(),
437 index,
438 }
439 }
440
441 /// Return the index of the key-value pair
442 #[inline]
443 pub fn index(&self) -> usize {
444 self.index
445 }
446
447 /// Gets a reference to the entry's key in the map.
448 pub fn key(&self) -> &K {
449 &self.map.entries[self.index].key
450 }
451
452 pub(crate) fn key_mut(&mut self) -> &mut K {
453 &mut self.map.entries[self.index].key
454 }
455
456 /// Gets a reference to the entry's value in the map.
457 pub fn get(&self) -> &V {
458 &self.map.entries[self.index].value
459 }
460
461 /// Gets a mutable reference to the entry's value in the map.
462 ///
463 /// If you need a reference which may outlive the destruction of the
464 /// `IndexedEntry` value, see [`into_mut`][Self::into_mut].
465 pub fn get_mut(&mut self) -> &mut V {
466 &mut self.map.entries[self.index].value
467 }
468
469 /// Sets the value of the entry to `value`, and returns the entry's old value.
470 pub fn insert(&mut self, value: V) -> V {
471 mem::replace(self.get_mut(), value)
472 }
473
474 /// Converts into a mutable reference to the entry's value in the map,
475 /// with a lifetime bound to the map itself.
476 pub fn into_mut(self) -> &'a mut V {
477 &mut self.map.entries[self.index].value
478 }
479
480 /// Remove and return the key, value pair stored in the map for this entry
481 ///
482 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
483 /// the last element of the map and popping it off.
484 /// **This perturbs the position of what used to be the last element!**
485 ///
486 /// Computes in **O(1)** time (average).
487 pub fn swap_remove_entry(mut self) -> (K, V) {
488 self.map.swap_remove_index(self.index).unwrap()
489 }
490
491 /// Remove and return the key, value pair stored in the map for this entry
492 ///
493 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
494 /// elements that follow it, preserving their relative order.
495 /// **This perturbs the index of all of those elements!**
496 ///
497 /// Computes in **O(n)** time (average).
498 pub fn shift_remove_entry(mut self) -> (K, V) {
499 self.map.shift_remove_index(self.index).unwrap()
500 }
501
502 /// Remove the key, value pair stored in the map for this entry, and return the value.
503 ///
504 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
505 /// the last element of the map and popping it off.
506 /// **This perturbs the position of what used to be the last element!**
507 ///
508 /// Computes in **O(1)** time (average).
509 pub fn swap_remove(self) -> V {
510 self.swap_remove_entry().1
511 }
512
513 /// Remove the key, value pair stored in the map for this entry, and return the value.
514 ///
515 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
516 /// elements that follow it, preserving their relative order.
517 /// **This perturbs the index of all of those elements!**
518 ///
519 /// Computes in **O(n)** time (average).
520 pub fn shift_remove(self) -> V {
521 self.shift_remove_entry().1
522 }
523
524 /// Moves the position of the entry to a new index
525 /// by shifting all other entries in-between.
526 ///
527 /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
528 /// coming `from` the current [`.index()`][Self::index].
529 ///
530 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
531 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
532 ///
533 /// ***Panics*** if `to` is out of bounds.
534 ///
535 /// Computes in **O(n)** time (average).
536 #[track_caller]
537 pub fn move_index(mut self, to: usize) {
538 self.map.move_index(self.index, to);
539 }
540
541 /// Swaps the position of entry with another.
542 ///
543 /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
544 /// with the current [`.index()`][Self::index] as one of the two being swapped.
545 ///
546 /// ***Panics*** if the `other` index is out of bounds.
547 ///
548 /// Computes in **O(1)** time (average).
549 pub fn swap_indices(mut self, other: usize) {
550 self.map.swap_indices(self.index, other);
551 }
552}
553
554impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IndexedEntry<'_, K, V> {
555 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
556 f&mut DebugStruct<'_, '_>.debug_struct("IndexedEntry")
557 .field("index", &self.index)
558 .field("key", self.key())
559 .field(name:"value", self.get())
560 .finish()
561 }
562}
563
564impl<'a, K, V> From<OccupiedEntry<'a, K, V>> for IndexedEntry<'a, K, V> {
565 fn from(other: OccupiedEntry<'a, K, V>) -> Self {
566 Self {
567 index: other.index(),
568 map: other.into_ref_mut(),
569 }
570 }
571}
572