ringmap/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//! `RingMap` without such an opt-in trait.
11
12use super::{Entries, OffsetIndex, RefMut};
13use crate::{Equivalent, HashValue, RingMap};
14use core::fmt;
15use core::hash::{BuildHasher, Hash, Hasher};
16use core::marker::PhantomData;
17use core::mem;
18use hashbrown::hash_table;
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 [`RingMap`].
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`][RingMap::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 ringmap::map::{RingMap, RawEntryApiV1};
46 ///
47 /// let mut map = RingMap::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 [`RingMap`].
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 `RingMap` 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`][RingMap::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 ringmap::map::{RingMap, RawEntryApiV1};
107 /// use ringmap::map::raw_entry_v1::RawEntryMut;
108 ///
109 /// let mut map = RingMap::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.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_back_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 RingMap<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 [`RingMap`] a key-value pair would be stored.
186///
187/// This `struct` is created by the [`RingMap::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 RingMap<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 offset = self.map.core.offset;
248 let eq = move |&i: &OffsetIndex| is_match(&entries[i.get(offset)].key);
249 let oi = self.map.core.indices.find(hash.get(), eq)?;
250 Some(oi.get(offset))
251 }
252}
253
254/// A builder for computing where in an [`RingMap`] a key-value pair would be stored.
255///
256/// This `struct` is created by the [`RingMap::raw_entry_mut_v1`] method, provided by the
257/// [`RawEntryApiV1`] trait. See its documentation for more.
258pub struct RawEntryBuilderMut<'a, K, V, S> {
259 map: &'a mut RingMap<K, V, S>,
260}
261
262impl<K, V, S> fmt::Debug for RawEntryBuilderMut<'_, K, V, S> {
263 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
264 f.debug_struct("RawEntryBuilderMut").finish_non_exhaustive()
265 }
266}
267
268impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S> {
269 /// Access an entry by key.
270 pub fn from_key<Q>(self, key: &Q) -> RawEntryMut<'a, K, V, S>
271 where
272 S: BuildHasher,
273 Q: ?Sized + Hash + Equivalent<K>,
274 {
275 let hash = self.map.hash(key);
276 self.from_key_hashed_nocheck(hash.get(), key)
277 }
278
279 /// Access an entry by a key and its hash.
280 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, key: &Q) -> RawEntryMut<'a, K, V, S>
281 where
282 Q: ?Sized + Equivalent<K>,
283 {
284 self.from_hash(hash, |k| Q::equivalent(key, k))
285 }
286
287 /// Access an entry by hash.
288 pub fn from_hash<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S>
289 where
290 F: FnMut(&K) -> bool,
291 {
292 let ref_entries = &self.map.core.entries;
293 let offset = self.map.core.offset;
294 let eq = move |&i: &OffsetIndex| is_match(&ref_entries[i.get(offset)].key);
295 match self.map.core.indices.find_entry(hash, eq) {
296 Ok(index) => RawEntryMut::Occupied(RawOccupiedEntryMut {
297 entries: &mut self.map.core.entries,
298 offset: &mut self.map.core.offset,
299 index,
300 hash_builder: PhantomData,
301 }),
302 Err(absent) => RawEntryMut::Vacant(RawVacantEntryMut {
303 map: RefMut::new(
304 absent.into_table(),
305 &mut self.map.core.entries,
306 &mut self.map.core.offset,
307 ),
308 hash_builder: &self.map.hash_builder,
309 }),
310 }
311 }
312}
313
314/// Raw entry for an existing key-value pair or a vacant location to
315/// insert one.
316pub enum RawEntryMut<'a, K, V, S> {
317 /// Existing slot with equivalent key.
318 Occupied(RawOccupiedEntryMut<'a, K, V, S>),
319 /// Vacant slot (no equivalent key in the map).
320 Vacant(RawVacantEntryMut<'a, K, V, S>),
321}
322
323impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawEntryMut<'_, K, V, S> {
324 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
325 let mut tuple = f.debug_tuple("RawEntryMut");
326 match self {
327 Self::Vacant(v) => tuple.field(v),
328 Self::Occupied(o) => tuple.field(o),
329 };
330 tuple.finish()
331 }
332}
333
334impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
335 /// Return the index where the key-value pair exists or may be inserted.
336 #[inline]
337 pub fn index(&self) -> usize {
338 match self {
339 Self::Occupied(entry) => entry.index(),
340 Self::Vacant(entry) => entry.index(),
341 }
342 }
343
344 /// Inserts the given default key and value in the entry if it is vacant and returns mutable
345 /// references to them. Otherwise mutable references to an already existent pair are returned.
346 pub fn or_insert(self, default_key: K, default_value: V) -> (&'a mut K, &'a mut V)
347 where
348 K: Hash,
349 S: BuildHasher,
350 {
351 match self {
352 Self::Occupied(entry) => entry.into_key_value_mut(),
353 Self::Vacant(entry) => entry.insert(default_key, default_value),
354 }
355 }
356
357 /// Inserts the result of the `call` function in the entry if it is vacant and returns mutable
358 /// references to them. Otherwise mutable references to an already existent pair are returned.
359 pub fn or_insert_with<F>(self, call: F) -> (&'a mut K, &'a mut V)
360 where
361 F: FnOnce() -> (K, V),
362 K: Hash,
363 S: BuildHasher,
364 {
365 match self {
366 Self::Occupied(entry) => entry.into_key_value_mut(),
367 Self::Vacant(entry) => {
368 let (key, value) = call();
369 entry.insert(key, value)
370 }
371 }
372 }
373
374 /// Modifies the entry if it is occupied.
375 pub fn and_modify<F>(mut self, f: F) -> Self
376 where
377 F: FnOnce(&mut K, &mut V),
378 {
379 if let Self::Occupied(entry) = &mut self {
380 let (k, v) = entry.get_key_value_mut();
381 f(k, v);
382 }
383 self
384 }
385}
386
387/// A raw view into an occupied entry in an [`RingMap`].
388/// It is part of the [`RawEntryMut`] enum.
389pub struct RawOccupiedEntryMut<'a, K, V, S> {
390 entries: &'a mut Entries<K, V>,
391 offset: &'a mut usize,
392 index: hash_table::OccupiedEntry<'a, OffsetIndex>,
393 hash_builder: PhantomData<&'a S>,
394}
395
396impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawOccupiedEntryMut<'_, K, V, S> {
397 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
398 f.debug_struct("RawOccupiedEntryMut")
399 .field("key", self.key())
400 .field("value", self.get())
401 .finish_non_exhaustive()
402 }
403}
404
405impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
406 /// Return the index of the key-value pair
407 #[inline]
408 pub fn index(&self) -> usize {
409 self.index.get().get(*self.offset)
410 }
411
412 #[inline]
413 fn into_ref_mut(self) -> RefMut<'a, K, V> {
414 RefMut::new(self.index.into_table(), self.entries, self.offset)
415 }
416
417 /// Gets a reference to the entry's key in the map.
418 ///
419 /// Note that this is not the key that was used to find the entry. There may be an observable
420 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
421 /// extra fields or the memory address of an allocation.
422 pub fn key(&self) -> &K {
423 &self.entries[self.index()].key
424 }
425
426 /// Gets a mutable reference to the entry's key in the map.
427 ///
428 /// Note that this is not the key that was used to find the entry. There may be an observable
429 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
430 /// extra fields or the memory address of an allocation.
431 pub fn key_mut(&mut self) -> &mut K {
432 let index = self.index();
433 &mut self.entries[index].key
434 }
435
436 /// Converts into a mutable reference to the entry's key in the map,
437 /// with a lifetime bound to the map itself.
438 ///
439 /// Note that this is not the key that was used to find the entry. There may be an observable
440 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
441 /// extra fields or the memory address of an allocation.
442 pub fn into_key(self) -> &'a mut K {
443 let index = self.index();
444 &mut self.entries[index].key
445 }
446
447 /// Gets a reference to the entry's value in the map.
448 pub fn get(&self) -> &V {
449 &self.entries[self.index()].value
450 }
451
452 /// Gets a mutable reference to the entry's value in the map.
453 ///
454 /// If you need a reference which may outlive the destruction of the
455 /// [`RawEntryMut`] value, see [`into_mut`][Self::into_mut].
456 pub fn get_mut(&mut self) -> &mut V {
457 let index = self.index();
458 &mut self.entries[index].value
459 }
460
461 /// Converts into a mutable reference to the entry's value in the map,
462 /// with a lifetime bound to the map itself.
463 pub fn into_mut(self) -> &'a mut V {
464 let index = self.index();
465 &mut self.entries[index].value
466 }
467
468 /// Gets a reference to the entry's key and value in the map.
469 pub fn get_key_value(&self) -> (&K, &V) {
470 self.entries[self.index()].refs()
471 }
472
473 /// Gets a reference to the entry's key and value in the map.
474 pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
475 let index = self.index();
476 self.entries[index].muts()
477 }
478
479 /// Converts into a mutable reference to the entry's key and value in the map,
480 /// with a lifetime bound to the map itself.
481 pub fn into_key_value_mut(self) -> (&'a mut K, &'a mut V) {
482 let index = self.index();
483 self.entries[index].muts()
484 }
485
486 /// Sets the value of the entry, and returns the entry's old value.
487 pub fn insert(&mut self, value: V) -> V {
488 mem::replace(self.get_mut(), value)
489 }
490
491 /// Sets the key of the entry, and returns the entry's old key.
492 pub fn insert_key(&mut self, key: K) -> K {
493 mem::replace(self.key_mut(), key)
494 }
495
496 /// Remove the key, value pair stored in the map for this entry, and return the value.
497 ///
498 /// Like [`VecDeque::remove`][super::VecDeque::remove], the pair is removed by shifting all of the
499 /// elements either before or after it, preserving their relative order.
500 /// **This perturbs the index of all of the following elements!**
501 ///
502 /// Computes in **O(n)** time (average).
503 pub fn remove(self) -> V {
504 self.remove_entry().1
505 }
506
507 /// Remove and return the key, value pair stored in the map for this entry
508 ///
509 /// Like [`VecDeque::remove`][super::VecDeque::remove], the pair is removed by shifting all of the
510 /// elements either before or after it, preserving their relative order.
511 /// **This perturbs the index of all of the following elements!**
512 ///
513 /// Computes in **O(n)** time (average).
514 pub fn remove_entry(self) -> (K, V) {
515 let (index, entry) = self.index.remove();
516 let index = index.get(*self.offset);
517 RefMut::new(entry.into_table(), self.entries, self.offset).shift_remove_finish(index)
518 }
519
520 /// Remove the key, value pair stored in the map for this entry, and return the value.
521 ///
522 /// Like [`VecDeque::swap_remove_back`][super::VecDeque::swap_remove_back], the pair is removed
523 /// by swapping it with the last element of the map and popping it off.
524 /// **This perturbs the position of what used to be the last element!**
525 ///
526 /// Computes in **O(1)** time (average).
527 pub fn swap_remove_back(self) -> V {
528 self.swap_remove_back_entry().1
529 }
530
531 /// Remove and return the key, value pair stored in the map for this entry
532 ///
533 /// Like [`VecDeque::swap_remove_back`][super::VecDeque::swap_remove_back], the pair is removed
534 /// by swapping it with the last element of the map and popping it off.
535 /// **This perturbs the position of what used to be the last element!**
536 ///
537 /// Computes in **O(1)** time (average).
538 pub fn swap_remove_back_entry(self) -> (K, V) {
539 let (index, entry) = self.index.remove();
540 let index = index.get(*self.offset);
541 RefMut::new(entry.into_table(), self.entries, self.offset).swap_remove_back_finish(index)
542 }
543
544 /// Remove the key, value pair stored in the map for this entry, and return the value.
545 ///
546 /// Like [`VecDeque::swap_remove_front`][super::VecDeque::swap_remove_front], the pair is removed
547 /// by swapping it with the first element of the map and popping it off.
548 /// **This perturbs the position of what used to be the first element!**
549 ///
550 /// Computes in **O(1)** time (average).
551 pub fn swap_remove_front(self) -> V {
552 self.swap_remove_front_entry().1
553 }
554
555 /// Remove and return the key, value pair stored in the map for this entry
556 ///
557 /// Like [`VecDeque::swap_remove_front`][super::VecDeque::swap_remove_front], the pair is removed
558 /// by swapping it with the first element of the map and popping it off.
559 /// **This perturbs the position of what used to be the first element!**
560 ///
561 /// Computes in **O(1)** time (average).
562 pub fn swap_remove_front_entry(self) -> (K, V) {
563 let (index, entry) = self.index.remove();
564 let index = index.get(*self.offset);
565 RefMut::new(entry.into_table(), self.entries, self.offset).swap_remove_front_finish(index)
566 }
567
568 /// Moves the position of the entry to a new index
569 /// by shifting all other entries in-between.
570 ///
571 /// This is equivalent to [`RingMap::move_index`]
572 /// coming `from` the current [`.index()`][Self::index].
573 ///
574 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
575 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
576 ///
577 /// ***Panics*** if `to` is out of bounds.
578 ///
579 /// Computes in **O(n)** time (average).
580 #[track_caller]
581 pub fn move_index(self, to: usize) {
582 let index = self.index();
583 self.into_ref_mut().move_index(index, to);
584 }
585
586 /// Swaps the position of entry with another.
587 ///
588 /// This is equivalent to [`RingMap::swap_indices`]
589 /// with the current [`.index()`][Self::index] as one of the two being swapped.
590 ///
591 /// ***Panics*** if the `other` index is out of bounds.
592 ///
593 /// Computes in **O(1)** time (average).
594 #[track_caller]
595 pub fn swap_indices(self, other: usize) {
596 let index = self.index();
597 self.into_ref_mut().swap_indices(index, other);
598 }
599}
600
601/// A view into a vacant raw entry in an [`RingMap`].
602/// It is part of the [`RawEntryMut`] enum.
603pub struct RawVacantEntryMut<'a, K, V, S> {
604 map: RefMut<'a, K, V>,
605 hash_builder: &'a S,
606}
607
608impl<K, V, S> fmt::Debug for RawVacantEntryMut<'_, K, V, S> {
609 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
610 f.debug_struct("RawVacantEntryMut").finish_non_exhaustive()
611 }
612}
613
614impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
615 /// Return the index where a key-value pair may be inserted.
616 pub fn index(&self) -> usize {
617 self.map.indices.len()
618 }
619
620 /// Inserts the given key and value into the map,
621 /// and returns mutable references to them.
622 pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
623 where
624 K: Hash,
625 S: BuildHasher,
626 {
627 let mut h = self.hash_builder.build_hasher();
628 key.hash(&mut h);
629 self.insert_hashed_nocheck(h.finish(), key, value)
630 }
631
632 /// Inserts the given key and value into the map with the provided hash,
633 /// and returns mutable references to them.
634 pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) {
635 let hash = HashValue(hash as usize);
636 self.map.push_back_unique(hash, key, value).into_muts()
637 }
638
639 /// Inserts the given key and value into the map at the given index,
640 /// shifting others to the right, and returns mutable references to them.
641 ///
642 /// ***Panics*** if `index` is out of bounds.
643 ///
644 /// Computes in **O(n)** time (average).
645 #[track_caller]
646 pub fn shift_insert(self, index: usize, key: K, value: V) -> (&'a mut K, &'a mut V)
647 where
648 K: Hash,
649 S: BuildHasher,
650 {
651 let mut h = self.hash_builder.build_hasher();
652 key.hash(&mut h);
653 self.shift_insert_hashed_nocheck(index, h.finish(), key, value)
654 }
655
656 /// Inserts the given key and value into the map with the provided hash
657 /// at the given index, and returns mutable references to them.
658 ///
659 /// ***Panics*** if `index` is out of bounds.
660 ///
661 /// Computes in **O(n)** time (average).
662 #[track_caller]
663 pub fn shift_insert_hashed_nocheck(
664 mut self,
665 index: usize,
666 hash: u64,
667 key: K,
668 value: V,
669 ) -> (&'a mut K, &'a mut V) {
670 let hash = HashValue(hash as usize);
671 self.map.shift_insert_unique(index, hash, key, value);
672 self.map.entries[index].muts()
673 }
674}
675
676mod private {
677 pub trait Sealed {}
678
679 impl<K, V, S> Sealed for super::RingMap<K, V, S> {}
680}