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 pub fn move_index(self, to: usize) {
298 let index = self.index();
299 self.into_ref_mut().move_index(index, to);
300 }
301
302 /// Swaps the position of entry with another.
303 ///
304 /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
305 /// with the current [`.index()`][Self::index] as one of the two being swapped.
306 ///
307 /// ***Panics*** if the `other` index is out of bounds.
308 ///
309 /// Computes in **O(1)** time (average).
310 pub fn swap_indices(self, other: usize) {
311 let index = self.index();
312 self.into_ref_mut().swap_indices(index, other);
313 }
314}
315
316impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for OccupiedEntry<'_, K, V> {
317 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
318 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
319 .field("key", self.key())
320 .field(name:"value", self.get())
321 .finish()
322 }
323}
324
325impl<'a, K, V> From<IndexedEntry<'a, K, V>> for OccupiedEntry<'a, K, V> {
326 fn from(other: IndexedEntry<'a, K, V>) -> Self {
327 let IndexedEntry {
328 map: RefMut { indices: &mut HashTable, entries: &mut Vec> },
329 index: usize,
330 } = other;
331 let hash: HashValue = entries[index].hash;
332 Self {
333 entries,
334 index: indices
335 .find_entry(hash.get(), move |&i| i == index)
336 .expect(msg:"index not found"),
337 }
338 }
339}
340
341/// A view into a vacant entry in an [`IndexMap`][crate::IndexMap].
342/// It is part of the [`Entry`] enum.
343pub struct VacantEntry<'a, K, V> {
344 map: RefMut<'a, K, V>,
345 hash: HashValue,
346 key: K,
347}
348
349impl<'a, K, V> VacantEntry<'a, K, V> {
350 /// Return the index where a key-value pair may be inserted.
351 pub fn index(&self) -> usize {
352 self.map.indices.len()
353 }
354
355 /// Gets a reference to the key that was used to find the entry.
356 pub fn key(&self) -> &K {
357 &self.key
358 }
359
360 pub(crate) fn key_mut(&mut self) -> &mut K {
361 &mut self.key
362 }
363
364 /// Takes ownership of the key, leaving the entry vacant.
365 pub fn into_key(self) -> K {
366 self.key
367 }
368
369 /// Inserts the entry's key and the given value into the map, and returns a mutable reference
370 /// to the value.
371 ///
372 /// Computes in **O(1)** time (amortized average).
373 pub fn insert(self, value: V) -> &'a mut V {
374 self.insert_entry(value).into_mut()
375 }
376
377 /// Inserts the entry's key and the given value into the map, and returns an `OccupiedEntry`.
378 ///
379 /// Computes in **O(1)** time (amortized average).
380 pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
381 let Self { map, hash, key } = self;
382 map.insert_unique(hash, key, value)
383 }
384
385 /// Inserts the entry's key and the given value into the map at its ordered
386 /// position among sorted keys, and returns the new index and a mutable
387 /// reference to the value.
388 ///
389 /// If the existing keys are **not** already sorted, then the insertion
390 /// index is unspecified (like [`slice::binary_search`]), but the key-value
391 /// pair is inserted at that position regardless.
392 ///
393 /// Computes in **O(n)** time (average).
394 pub fn insert_sorted(self, value: V) -> (usize, &'a mut V)
395 where
396 K: Ord,
397 {
398 let slice = crate::map::Slice::from_slice(self.map.entries);
399 let i = slice.binary_search_keys(&self.key).unwrap_err();
400 (i, self.shift_insert(i, value))
401 }
402
403 /// Inserts the entry's key and the given value into the map at the given index,
404 /// shifting others to the right, and returns a mutable reference to the value.
405 ///
406 /// ***Panics*** if `index` is out of bounds.
407 ///
408 /// Computes in **O(n)** time (average).
409 pub fn shift_insert(mut self, index: usize, value: V) -> &'a mut V {
410 self.map
411 .shift_insert_unique(index, self.hash, self.key, value);
412 &mut self.map.entries[index].value
413 }
414}
415
416impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> {
417 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
418 f.debug_tuple(name:"VacantEntry").field(self.key()).finish()
419 }
420}
421
422/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap] obtained by index.
423///
424/// This `struct` is created from the [`get_index_entry`][crate::IndexMap::get_index_entry] method.
425pub struct IndexedEntry<'a, K, V> {
426 map: RefMut<'a, K, V>,
427 // We have a mutable reference to the map, which keeps the index
428 // valid and pointing to the correct entry.
429 index: usize,
430}
431
432impl<'a, K, V> IndexedEntry<'a, K, V> {
433 pub(crate) fn new(map: &'a mut IndexMapCore<K, V>, index: usize) -> Self {
434 Self {
435 map: map.borrow_mut(),
436 index,
437 }
438 }
439
440 /// Return the index of the key-value pair
441 #[inline]
442 pub fn index(&self) -> usize {
443 self.index
444 }
445
446 /// Gets a reference to the entry's key in the map.
447 pub fn key(&self) -> &K {
448 &self.map.entries[self.index].key
449 }
450
451 pub(crate) fn key_mut(&mut self) -> &mut K {
452 &mut self.map.entries[self.index].key
453 }
454
455 /// Gets a reference to the entry's value in the map.
456 pub fn get(&self) -> &V {
457 &self.map.entries[self.index].value
458 }
459
460 /// Gets a mutable reference to the entry's value in the map.
461 ///
462 /// If you need a reference which may outlive the destruction of the
463 /// `IndexedEntry` value, see [`into_mut`][Self::into_mut].
464 pub fn get_mut(&mut self) -> &mut V {
465 &mut self.map.entries[self.index].value
466 }
467
468 /// Sets the value of the entry to `value`, and returns the entry's old value.
469 pub fn insert(&mut self, value: V) -> V {
470 mem::replace(self.get_mut(), value)
471 }
472
473 /// Converts into a mutable reference to the entry's value in the map,
474 /// with a lifetime bound to the map itself.
475 pub fn into_mut(self) -> &'a mut V {
476 &mut self.map.entries[self.index].value
477 }
478
479 /// Remove and return the key, value pair stored in the map for this entry
480 ///
481 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
482 /// the last element of the map and popping it off.
483 /// **This perturbs the position of what used to be the last element!**
484 ///
485 /// Computes in **O(1)** time (average).
486 pub fn swap_remove_entry(mut self) -> (K, V) {
487 self.map.swap_remove_index(self.index).unwrap()
488 }
489
490 /// Remove and return the key, value pair stored in the map for this entry
491 ///
492 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
493 /// elements that follow it, preserving their relative order.
494 /// **This perturbs the index of all of those elements!**
495 ///
496 /// Computes in **O(n)** time (average).
497 pub fn shift_remove_entry(mut self) -> (K, V) {
498 self.map.shift_remove_index(self.index).unwrap()
499 }
500
501 /// Remove the key, value pair stored in the map for this entry, and return the value.
502 ///
503 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
504 /// the last element of the map and popping it off.
505 /// **This perturbs the position of what used to be the last element!**
506 ///
507 /// Computes in **O(1)** time (average).
508 pub fn swap_remove(self) -> V {
509 self.swap_remove_entry().1
510 }
511
512 /// Remove the key, value pair stored in the map for this entry, and return the value.
513 ///
514 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
515 /// elements that follow it, preserving their relative order.
516 /// **This perturbs the index of all of those elements!**
517 ///
518 /// Computes in **O(n)** time (average).
519 pub fn shift_remove(self) -> V {
520 self.shift_remove_entry().1
521 }
522
523 /// Moves the position of the entry to a new index
524 /// by shifting all other entries in-between.
525 ///
526 /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
527 /// coming `from` the current [`.index()`][Self::index].
528 ///
529 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
530 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
531 ///
532 /// ***Panics*** if `to` is out of bounds.
533 ///
534 /// Computes in **O(n)** time (average).
535 pub fn move_index(mut self, to: usize) {
536 self.map.move_index(self.index, to);
537 }
538
539 /// Swaps the position of entry with another.
540 ///
541 /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
542 /// with the current [`.index()`][Self::index] as one of the two being swapped.
543 ///
544 /// ***Panics*** if the `other` index is out of bounds.
545 ///
546 /// Computes in **O(1)** time (average).
547 pub fn swap_indices(mut self, other: usize) {
548 self.map.swap_indices(self.index, other);
549 }
550}
551
552impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IndexedEntry<'_, K, V> {
553 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
554 f&mut DebugStruct<'_, '_>.debug_struct("IndexedEntry")
555 .field("index", &self.index)
556 .field("key", self.key())
557 .field(name:"value", self.get())
558 .finish()
559 }
560}
561
562impl<'a, K, V> From<OccupiedEntry<'a, K, V>> for IndexedEntry<'a, K, V> {
563 fn from(other: OccupiedEntry<'a, K, V>) -> Self {
564 Self {
565 index: other.index(),
566 map: other.into_ref_mut(),
567 }
568 }
569}
570