1 use std::{
2 borrow::Borrow,
3 cmp::Ordering,
4 fmt,
5 hash::{BuildHasher, Hash, Hasher},
6 iter::FromIterator,
7 marker::PhantomData,
8 mem::{self, MaybeUninit},
9 ops::{Index, IndexMut},
10 ptr::{self, NonNull},
11 };
12
13 use hashbrown::{hash_map, HashMap};
14
15 pub type TryReserveError = hashbrown::TryReserveError;
16
17 /// A version of `HashMap` that has a user controllable order for its entries.
18 ///
19 /// It achieves this by keeping its entries in an internal linked list and using a `HashMap` to
20 /// point at nodes in this linked list.
21 ///
22 /// The order of entries defaults to "insertion order", but the user can also modify the order of
23 /// existing entries by manually moving them to the front or back.
24 ///
25 /// There are two kinds of methods that modify the order of the internal list:
26 ///
27 /// * Methods that have names like `to_front` and `to_back` will unsurprisingly move an existing
28 /// entry to the front or back
29 /// * Methods that have the word `insert` will insert a new entry ot the back of the list, and if
30 /// that method might replace an entry, that method will *also move that existing entry to the
31 /// back*.
32 pub struct LinkedHashMap<K, V, S = hash_map::DefaultHashBuilder> {
33 map: HashMap<NonNull<Node<K, V>>, (), NullHasher>,
34 // We need to keep any custom hash builder outside of the HashMap so we can access it alongside
35 // the entry API without mutable aliasing.
36 hash_builder: S,
37 // Circular linked list of nodes. If `values` is non-null, it will point to a "guard node"
38 // which will never have an initialized key or value, `values.prev` will contain the last key /
39 // value in the list, `values.next` will contain the first key / value in the list.
40 values: Option<NonNull<Node<K, V>>>,
41 // *Singly* linked list of free nodes. The `prev` pointers in the free list should be assumed
42 // invalid.
43 free: Option<NonNull<Node<K, V>>>,
44 }
45
46 impl<K, V> LinkedHashMap<K, V> {
47 #[inline]
new() -> Self48 pub fn new() -> Self {
49 Self {
50 hash_builder: hash_map::DefaultHashBuilder::default(),
51 map: HashMap::with_hasher(NullHasher),
52 values: None,
53 free: None,
54 }
55 }
56
57 #[inline]
with_capacity(capacity: usize) -> Self58 pub fn with_capacity(capacity: usize) -> Self {
59 Self {
60 hash_builder: hash_map::DefaultHashBuilder::default(),
61 map: HashMap::with_capacity_and_hasher(capacity, NullHasher),
62 values: None,
63 free: None,
64 }
65 }
66 }
67
68 impl<K, V, S> LinkedHashMap<K, V, S> {
69 #[inline]
with_hasher(hash_builder: S) -> Self70 pub fn with_hasher(hash_builder: S) -> Self {
71 Self {
72 hash_builder,
73 map: HashMap::with_hasher(NullHasher),
74 values: None,
75 free: None,
76 }
77 }
78
79 #[inline]
with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self80 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
81 Self {
82 hash_builder,
83 map: HashMap::with_capacity_and_hasher(capacity, NullHasher),
84 values: None,
85 free: None,
86 }
87 }
88
89 #[inline]
reserve(&mut self, additional: usize)90 pub fn reserve(&mut self, additional: usize) {
91 self.map.reserve(additional);
92 }
93
94 #[inline]
try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>95 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
96 self.map.try_reserve(additional)
97 }
98
99 #[inline]
shrink_to_fit(&mut self)100 pub fn shrink_to_fit(&mut self) {
101 self.map.shrink_to_fit();
102 unsafe { drop_free_nodes(self.free) };
103 self.free = None;
104 }
105
106 #[inline]
len(&self) -> usize107 pub fn len(&self) -> usize {
108 self.map.len()
109 }
110
111 #[inline]
is_empty(&self) -> bool112 pub fn is_empty(&self) -> bool {
113 self.len() == 0
114 }
115
116 #[inline]
clear(&mut self)117 pub fn clear(&mut self) {
118 self.map.clear();
119 if let Some(mut values) = self.values {
120 unsafe {
121 drop_value_nodes(values);
122 values.as_mut().links.value = ValueLinks {
123 prev: values,
124 next: values,
125 };
126 }
127 }
128 }
129
130 #[inline]
iter(&self) -> Iter<K, V>131 pub fn iter(&self) -> Iter<K, V> {
132 let (head, tail) = if let Some(values) = self.values {
133 unsafe {
134 let ValueLinks { next, prev } = values.as_ref().links.value;
135 (next.as_ptr(), prev.as_ptr())
136 }
137 } else {
138 (ptr::null_mut(), ptr::null_mut())
139 };
140
141 Iter {
142 head,
143 tail,
144 remaining: self.len(),
145 marker: PhantomData,
146 }
147 }
148
149 #[inline]
iter_mut(&mut self) -> IterMut<K, V>150 pub fn iter_mut(&mut self) -> IterMut<K, V> {
151 let (head, tail) = if let Some(values) = self.values {
152 unsafe {
153 let ValueLinks { next, prev } = values.as_ref().links.value;
154 (Some(next), Some(prev))
155 }
156 } else {
157 (None, None)
158 };
159
160 IterMut {
161 head,
162 tail,
163 remaining: self.len(),
164 marker: PhantomData,
165 }
166 }
167
168 #[inline]
drain(&mut self) -> Drain<'_, K, V>169 pub fn drain(&mut self) -> Drain<'_, K, V> {
170 unsafe {
171 let (head, tail) = if let Some(mut values) = self.values {
172 let ValueLinks { next, prev } = values.as_ref().links.value;
173 values.as_mut().links.value = ValueLinks {
174 next: values,
175 prev: values,
176 };
177 (Some(next), Some(prev))
178 } else {
179 (None, None)
180 };
181 let len = self.len();
182
183 self.map.clear();
184
185 Drain {
186 free: (&mut self.free).into(),
187 head,
188 tail,
189 remaining: len,
190 marker: PhantomData,
191 }
192 }
193 }
194
195 #[inline]
keys(&self) -> Keys<K, V>196 pub fn keys(&self) -> Keys<K, V> {
197 Keys { inner: self.iter() }
198 }
199
200 #[inline]
values(&self) -> Values<K, V>201 pub fn values(&self) -> Values<K, V> {
202 Values { inner: self.iter() }
203 }
204
205 #[inline]
values_mut(&mut self) -> ValuesMut<K, V>206 pub fn values_mut(&mut self) -> ValuesMut<K, V> {
207 ValuesMut {
208 inner: self.iter_mut(),
209 }
210 }
211
212 #[inline]
front(&self) -> Option<(&K, &V)>213 pub fn front(&self) -> Option<(&K, &V)> {
214 if self.is_empty() {
215 return None;
216 }
217 unsafe {
218 let front = (*self.values.as_ptr()).links.value.next.as_ptr();
219 let (key, value) = (*front).entry_ref();
220 Some((key, value))
221 }
222 }
223
224 #[inline]
back(&self) -> Option<(&K, &V)>225 pub fn back(&self) -> Option<(&K, &V)> {
226 if self.is_empty() {
227 return None;
228 }
229 unsafe {
230 let back = &*(*self.values.as_ptr()).links.value.prev.as_ptr();
231 let (key, value) = (*back).entry_ref();
232 Some((key, value))
233 }
234 }
235
236 #[inline]
retain<F>(&mut self, mut f: F) where F: FnMut(&K, &mut V) -> bool,237 pub fn retain<F>(&mut self, mut f: F)
238 where
239 F: FnMut(&K, &mut V) -> bool,
240 {
241 // We do not drop the key and value when a value is filtered from the map during the call to
242 // `retain`. We need to be very careful not to have a live `HashMap` entry pointing to
243 // either a dangling `Node` or a `Node` with dropped keys / values. Since the key and value
244 // types may panic on drop, they may short-circuit the entry in the map actually being
245 // removed. Instead, we push the removed nodes onto the free list eagerly, then try and
246 // drop the keys and values for any newly freed nodes *after* `HashMap::retain` has
247 // completely finished.
248 struct DropFilteredValues<'a, K, V> {
249 free: &'a mut Option<NonNull<Node<K, V>>>,
250 cur_free: Option<NonNull<Node<K, V>>>,
251 }
252
253 impl<'a, K, V> DropFilteredValues<'a, K, V> {
254 #[inline]
255 fn drop_later(&mut self, node: NonNull<Node<K, V>>) {
256 unsafe {
257 detach_node(node);
258 push_free(&mut self.cur_free, node);
259 }
260 }
261 }
262
263 impl<'a, K, V> Drop for DropFilteredValues<'a, K, V> {
264 fn drop(&mut self) {
265 unsafe {
266 let end_free = self.cur_free;
267 while self.cur_free != *self.free {
268 let cur_free = self.cur_free.as_ptr();
269 (*cur_free).take_entry();
270 self.cur_free = (*cur_free).links.free.next;
271 }
272 *self.free = end_free;
273 }
274 }
275 }
276
277 let free = self.free;
278 let mut drop_filtered_values = DropFilteredValues {
279 free: &mut self.free,
280 cur_free: free,
281 };
282
283 self.map.retain(|&node, _| unsafe {
284 let (k, v) = (*node.as_ptr()).entry_mut();
285 if f(k, v) {
286 true
287 } else {
288 drop_filtered_values.drop_later(node);
289 false
290 }
291 });
292 }
293
294 #[inline]
hasher(&self) -> &S295 pub fn hasher(&self) -> &S {
296 &self.hash_builder
297 }
298
299 #[inline]
capacity(&self) -> usize300 pub fn capacity(&self) -> usize {
301 self.map.capacity()
302 }
303 }
304
305 impl<K, V, S> LinkedHashMap<K, V, S>
306 where
307 K: Eq + Hash,
308 S: BuildHasher,
309 {
310 #[inline]
entry(&mut self, key: K) -> Entry<'_, K, V, S>311 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S> {
312 match self.raw_entry_mut().from_key(&key) {
313 RawEntryMut::Occupied(occupied) => Entry::Occupied(OccupiedEntry {
314 key,
315 raw_entry: occupied,
316 }),
317 RawEntryMut::Vacant(vacant) => Entry::Vacant(VacantEntry {
318 key,
319 raw_entry: vacant,
320 }),
321 }
322 }
323
324 #[inline]
get<Q>(&self, k: &Q) -> Option<&V> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,325 pub fn get<Q>(&self, k: &Q) -> Option<&V>
326 where
327 K: Borrow<Q>,
328 Q: Hash + Eq + ?Sized,
329 {
330 self.raw_entry().from_key(k).map(|(_, v)| v)
331 }
332
333 #[inline]
get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,334 pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
335 where
336 K: Borrow<Q>,
337 Q: Hash + Eq + ?Sized,
338 {
339 self.raw_entry().from_key(k)
340 }
341
342 #[inline]
contains_key<Q>(&self, k: &Q) -> bool where K: Borrow<Q>, Q: Hash + Eq + ?Sized,343 pub fn contains_key<Q>(&self, k: &Q) -> bool
344 where
345 K: Borrow<Q>,
346 Q: Hash + Eq + ?Sized,
347 {
348 self.get(k).is_some()
349 }
350
351 #[inline]
get_mut<Q>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,352 pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
353 where
354 K: Borrow<Q>,
355 Q: Hash + Eq + ?Sized,
356 {
357 match self.raw_entry_mut().from_key(k) {
358 RawEntryMut::Occupied(occupied) => Some(occupied.into_mut()),
359 RawEntryMut::Vacant(_) => None,
360 }
361 }
362
363 /// Inserts the given key / value pair at the *back* of the internal linked list.
364 ///
365 /// Returns the previously set value, if one existed prior to this call. After this call,
366 /// calling `LinkedHashMap::back` will return a reference to this key / value pair.
367 #[inline]
insert(&mut self, k: K, v: V) -> Option<V>368 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
369 match self.raw_entry_mut().from_key(&k) {
370 RawEntryMut::Occupied(mut occupied) => {
371 occupied.to_back();
372 Some(occupied.replace_value(v))
373 }
374 RawEntryMut::Vacant(vacant) => {
375 vacant.insert(k, v);
376 None
377 }
378 }
379 }
380
381 #[inline]
remove<Q>(&mut self, k: &Q) -> Option<V> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,382 pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
383 where
384 K: Borrow<Q>,
385 Q: Hash + Eq + ?Sized,
386 {
387 match self.raw_entry_mut().from_key(&k) {
388 RawEntryMut::Occupied(occupied) => Some(occupied.remove()),
389 RawEntryMut::Vacant(_) => None,
390 }
391 }
392
393 #[inline]
remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,394 pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
395 where
396 K: Borrow<Q>,
397 Q: Hash + Eq + ?Sized,
398 {
399 match self.raw_entry_mut().from_key(&k) {
400 RawEntryMut::Occupied(occupied) => Some(occupied.remove_entry()),
401 RawEntryMut::Vacant(_) => None,
402 }
403 }
404
405 #[inline]
pop_front(&mut self) -> Option<(K, V)>406 pub fn pop_front(&mut self) -> Option<(K, V)> {
407 if self.is_empty() {
408 return None;
409 }
410 unsafe {
411 let front = (*self.values.as_ptr()).links.value.next;
412 match self.map.raw_entry_mut().from_hash(
413 hash_key(&self.hash_builder, front.as_ref().key_ref()),
414 |k| (*k).as_ref().key_ref().eq(front.as_ref().key_ref()),
415 ) {
416 hash_map::RawEntryMut::Occupied(occupied) => {
417 Some(remove_node(&mut self.free, occupied.remove_entry().0))
418 }
419 hash_map::RawEntryMut::Vacant(_) => None,
420 }
421 }
422 }
423
424 #[inline]
pop_back(&mut self) -> Option<(K, V)>425 pub fn pop_back(&mut self) -> Option<(K, V)> {
426 if self.is_empty() {
427 return None;
428 }
429 unsafe {
430 let back = (*self.values.as_ptr()).links.value.prev;
431 match self
432 .map
433 .raw_entry_mut()
434 .from_hash(hash_key(&self.hash_builder, back.as_ref().key_ref()), |k| {
435 (*k).as_ref().key_ref().eq(back.as_ref().key_ref())
436 }) {
437 hash_map::RawEntryMut::Occupied(occupied) => {
438 Some(remove_node(&mut self.free, occupied.remove_entry().0))
439 }
440 hash_map::RawEntryMut::Vacant(_) => None,
441 }
442 }
443 }
444 }
445
446 impl<K, V, S> LinkedHashMap<K, V, S>
447 where
448 S: BuildHasher,
449 {
450 #[inline]
raw_entry(&self) -> RawEntryBuilder<'_, K, V, S>451 pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
452 RawEntryBuilder {
453 hash_builder: &self.hash_builder,
454 entry: self.map.raw_entry(),
455 }
456 }
457
458 #[inline]
raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S>459 pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
460 RawEntryBuilderMut {
461 hash_builder: &self.hash_builder,
462 values: &mut self.values,
463 free: &mut self.free,
464 entry: self.map.raw_entry_mut(),
465 }
466 }
467 }
468
469 impl<K, V, S> Default for LinkedHashMap<K, V, S>
470 where
471 S: Default,
472 {
473 #[inline]
default() -> Self474 fn default() -> Self {
475 Self::with_hasher(S::default())
476 }
477 }
478
479 impl<K: Hash + Eq, V, S: BuildHasher + Default> FromIterator<(K, V)> for LinkedHashMap<K, V, S> {
480 #[inline]
from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self481 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
482 let iter = iter.into_iter();
483 let mut map = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
484 map.extend(iter);
485 map
486 }
487 }
488
489 impl<K, V, S> fmt::Debug for LinkedHashMap<K, V, S>
490 where
491 K: fmt::Debug,
492 V: fmt::Debug,
493 {
494 #[inline]
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result495 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
496 f.debug_map().entries(self).finish()
497 }
498 }
499
500 impl<K: Hash + Eq, V: PartialEq, S: BuildHasher> PartialEq for LinkedHashMap<K, V, S> {
501 #[inline]
eq(&self, other: &Self) -> bool502 fn eq(&self, other: &Self) -> bool {
503 self.len() == other.len() && self.iter().eq(other)
504 }
505 }
506
507 impl<K: Hash + Eq, V: Eq, S: BuildHasher> Eq for LinkedHashMap<K, V, S> {}
508
509 impl<K: Hash + Eq + PartialOrd, V: PartialOrd, S: BuildHasher> PartialOrd
510 for LinkedHashMap<K, V, S>
511 {
512 #[inline]
partial_cmp(&self, other: &Self) -> Option<Ordering>513 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
514 self.iter().partial_cmp(other)
515 }
516
517 #[inline]
lt(&self, other: &Self) -> bool518 fn lt(&self, other: &Self) -> bool {
519 self.iter().lt(other)
520 }
521
522 #[inline]
le(&self, other: &Self) -> bool523 fn le(&self, other: &Self) -> bool {
524 self.iter().le(other)
525 }
526
527 #[inline]
ge(&self, other: &Self) -> bool528 fn ge(&self, other: &Self) -> bool {
529 self.iter().ge(other)
530 }
531
532 #[inline]
gt(&self, other: &Self) -> bool533 fn gt(&self, other: &Self) -> bool {
534 self.iter().gt(other)
535 }
536 }
537
538 impl<K: Hash + Eq + Ord, V: Ord, S: BuildHasher> Ord for LinkedHashMap<K, V, S> {
539 #[inline]
cmp(&self, other: &Self) -> Ordering540 fn cmp(&self, other: &Self) -> Ordering {
541 self.iter().cmp(other)
542 }
543 }
544
545 impl<K: Hash + Eq, V: Hash, S: BuildHasher> Hash for LinkedHashMap<K, V, S> {
546 #[inline]
hash<H: Hasher>(&self, h: &mut H)547 fn hash<H: Hasher>(&self, h: &mut H) {
548 for e in self.iter() {
549 e.hash(h);
550 }
551 }
552 }
553
554 impl<K, V, S> Drop for LinkedHashMap<K, V, S> {
555 #[inline]
drop(&mut self)556 fn drop(&mut self) {
557 unsafe {
558 if let Some(values) = self.values {
559 drop_value_nodes(values);
560 Box::from_raw(values.as_ptr());
561 }
562 drop_free_nodes(self.free);
563 }
564 }
565 }
566
567 unsafe impl<K: Send, V: Send, S: Send> Send for LinkedHashMap<K, V, S> {}
568 unsafe impl<K: Sync, V: Sync, S: Sync> Sync for LinkedHashMap<K, V, S> {}
569
570 impl<'a, K, V, S, Q> Index<&'a Q> for LinkedHashMap<K, V, S>
571 where
572 K: Hash + Eq + Borrow<Q>,
573 S: BuildHasher,
574 Q: Eq + Hash + ?Sized,
575 {
576 type Output = V;
577
578 #[inline]
index(&self, index: &'a Q) -> &V579 fn index(&self, index: &'a Q) -> &V {
580 self.get(index).expect("no entry found for key")
581 }
582 }
583
584 impl<'a, K, V, S, Q> IndexMut<&'a Q> for LinkedHashMap<K, V, S>
585 where
586 K: Hash + Eq + Borrow<Q>,
587 S: BuildHasher,
588 Q: Eq + Hash + ?Sized,
589 {
590 #[inline]
index_mut(&mut self, index: &'a Q) -> &mut V591 fn index_mut(&mut self, index: &'a Q) -> &mut V {
592 self.get_mut(index).expect("no entry found for key")
593 }
594 }
595
596 impl<K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone> Clone for LinkedHashMap<K, V, S> {
597 #[inline]
clone(&self) -> Self598 fn clone(&self) -> Self {
599 let mut map = Self::with_hasher(self.hash_builder.clone());
600 map.extend(self.iter().map(|(k, v)| (k.clone(), v.clone())));
601 map
602 }
603 }
604
605 impl<K: Hash + Eq, V, S: BuildHasher> Extend<(K, V)> for LinkedHashMap<K, V, S> {
606 #[inline]
extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)607 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
608 for (k, v) in iter {
609 self.insert(k, v);
610 }
611 }
612 }
613
614 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for LinkedHashMap<K, V, S>
615 where
616 K: 'a + Hash + Eq + Copy,
617 V: 'a + Copy,
618 S: BuildHasher,
619 {
620 #[inline]
extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I)621 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
622 for (&k, &v) in iter {
623 self.insert(k, v);
624 }
625 }
626 }
627
628 pub enum Entry<'a, K, V, S> {
629 Occupied(OccupiedEntry<'a, K, V>),
630 Vacant(VacantEntry<'a, K, V, S>),
631 }
632
633 impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for Entry<'_, K, V, S> {
634 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result635 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
636 match *self {
637 Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
638 Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
639 }
640 }
641 }
642
643 impl<'a, K, V, S> Entry<'a, K, V, S> {
644 /// If this entry is vacant, inserts a new entry with the given value and returns a reference to
645 /// it.
646 ///
647 /// If this entry is occupied, this method *moves the occupied entry to the back of the internal
648 /// linked list* and returns a reference to the existing value.
649 #[inline]
or_insert(self, default: V) -> &'a mut V where K: Hash, S: BuildHasher,650 pub fn or_insert(self, default: V) -> &'a mut V
651 where
652 K: Hash,
653 S: BuildHasher,
654 {
655 match self {
656 Entry::Occupied(mut entry) => {
657 entry.to_back();
658 entry.into_mut()
659 }
660 Entry::Vacant(entry) => entry.insert(default),
661 }
662 }
663
664 /// Similar to `Entry::or_insert`, but accepts a function to construct a new value if this entry
665 /// is vacant.
666 #[inline]
or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V where K: Hash, S: BuildHasher,667 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
668 where
669 K: Hash,
670 S: BuildHasher,
671 {
672 match self {
673 Entry::Occupied(mut entry) => {
674 entry.to_back();
675 entry.into_mut()
676 }
677 Entry::Vacant(entry) => entry.insert(default()),
678 }
679 }
680
681 #[inline]
key(&self) -> &K682 pub fn key(&self) -> &K {
683 match *self {
684 Entry::Occupied(ref entry) => entry.key(),
685 Entry::Vacant(ref entry) => entry.key(),
686 }
687 }
688
689 #[inline]
and_modify<F>(self, f: F) -> Self where F: FnOnce(&mut V),690 pub fn and_modify<F>(self, f: F) -> Self
691 where
692 F: FnOnce(&mut V),
693 {
694 match self {
695 Entry::Occupied(mut entry) => {
696 f(entry.get_mut());
697 Entry::Occupied(entry)
698 }
699 Entry::Vacant(entry) => Entry::Vacant(entry),
700 }
701 }
702 }
703
704 pub struct OccupiedEntry<'a, K, V> {
705 key: K,
706 raw_entry: RawOccupiedEntryMut<'a, K, V>,
707 }
708
709 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for OccupiedEntry<'_, K, V> {
710 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result711 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
712 f.debug_struct("OccupiedEntry")
713 .field("key", self.key())
714 .field("value", self.get())
715 .finish()
716 }
717 }
718
719 impl<'a, K, V> OccupiedEntry<'a, K, V> {
720 #[inline]
key(&self) -> &K721 pub fn key(&self) -> &K {
722 self.raw_entry.key()
723 }
724
725 #[inline]
remove_entry(self) -> (K, V)726 pub fn remove_entry(self) -> (K, V) {
727 self.raw_entry.remove_entry()
728 }
729
730 #[inline]
get(&self) -> &V731 pub fn get(&self) -> &V {
732 self.raw_entry.get()
733 }
734
735 #[inline]
get_mut(&mut self) -> &mut V736 pub fn get_mut(&mut self) -> &mut V {
737 self.raw_entry.get_mut()
738 }
739
740 #[inline]
into_mut(self) -> &'a mut V741 pub fn into_mut(self) -> &'a mut V {
742 self.raw_entry.into_mut()
743 }
744
745 #[inline]
to_back(&mut self)746 pub fn to_back(&mut self) {
747 self.raw_entry.to_back()
748 }
749
750 #[inline]
to_front(&mut self)751 pub fn to_front(&mut self) {
752 self.raw_entry.to_front()
753 }
754
755 /// Replaces this entry's value with the provided value.
756 ///
757 /// Similarly to `LinkedHashMap::insert`, this moves the existing entry to the back of the
758 /// internal linked list.
759 #[inline]
insert(&mut self, value: V) -> V760 pub fn insert(&mut self, value: V) -> V {
761 self.raw_entry.to_back();
762 self.raw_entry.replace_value(value)
763 }
764
765 #[inline]
remove(self) -> V766 pub fn remove(self) -> V {
767 self.raw_entry.remove()
768 }
769
770 /// Similar to `OccupiedEntry::replace_entry`, but *does* move the entry to the back of the
771 /// internal linked list.
772 #[inline]
insert_entry(mut self, value: V) -> (K, V)773 pub fn insert_entry(mut self, value: V) -> (K, V) {
774 self.raw_entry.to_back();
775 self.replace_entry(value)
776 }
777
778 /// Replaces the entry's key with the key provided to `LinkedHashMap::entry`, and replaces the
779 /// entry's value with the given `value` parameter.
780 ///
781 /// Does *not* move the entry to the back of the internal linked list.
replace_entry(mut self, value: V) -> (K, V)782 pub fn replace_entry(mut self, value: V) -> (K, V) {
783 let old_key = mem::replace(self.raw_entry.key_mut(), self.key);
784 let old_value = mem::replace(self.raw_entry.get_mut(), value);
785 (old_key, old_value)
786 }
787
788 /// Replaces this entry's key with the key provided to `LinkedHashMap::entry`.
789 ///
790 /// Does *not* move the entry to the back of the internal linked list.
791 #[inline]
replace_key(mut self) -> K792 pub fn replace_key(mut self) -> K {
793 mem::replace(self.raw_entry.key_mut(), self.key)
794 }
795 }
796
797 pub struct VacantEntry<'a, K, V, S> {
798 key: K,
799 raw_entry: RawVacantEntryMut<'a, K, V, S>,
800 }
801
802 impl<K: fmt::Debug, V, S> fmt::Debug for VacantEntry<'_, K, V, S> {
803 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result804 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
805 f.debug_tuple("VacantEntry").field(self.key()).finish()
806 }
807 }
808
809 impl<'a, K, V, S> VacantEntry<'a, K, V, S> {
810 #[inline]
key(&self) -> &K811 pub fn key(&self) -> &K {
812 &self.key
813 }
814
815 #[inline]
into_key(self) -> K816 pub fn into_key(self) -> K {
817 self.key
818 }
819
820 /// Insert's the key for this vacant entry paired with the given value as a new entry at the
821 /// *back* of the internal linked list.
822 #[inline]
insert(self, value: V) -> &'a mut V where K: Hash, S: BuildHasher,823 pub fn insert(self, value: V) -> &'a mut V
824 where
825 K: Hash,
826 S: BuildHasher,
827 {
828 self.raw_entry.insert(self.key, value).1
829 }
830 }
831
832 pub struct RawEntryBuilder<'a, K, V, S> {
833 hash_builder: &'a S,
834 entry: hash_map::RawEntryBuilder<'a, NonNull<Node<K, V>>, (), NullHasher>,
835 }
836
837 impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
838 where
839 S: BuildHasher,
840 {
841 #[inline]
from_key<Q>(self, k: &Q) -> Option<(&'a K, &'a V)> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,842 pub fn from_key<Q>(self, k: &Q) -> Option<(&'a K, &'a V)>
843 where
844 K: Borrow<Q>,
845 Q: Hash + Eq + ?Sized,
846 {
847 let hash = hash_key(self.hash_builder, k);
848 self.from_key_hashed_nocheck(hash, k)
849 }
850
851 #[inline]
from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,852 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
853 where
854 K: Borrow<Q>,
855 Q: Hash + Eq + ?Sized,
856 {
857 self.from_hash(hash, move |o| k.eq(o.borrow()))
858 }
859
860 #[inline]
from_hash( self, hash: u64, mut is_match: impl FnMut(&K) -> bool, ) -> Option<(&'a K, &'a V)>861 pub fn from_hash(
862 self,
863 hash: u64,
864 mut is_match: impl FnMut(&K) -> bool,
865 ) -> Option<(&'a K, &'a V)> {
866 unsafe {
867 let node = *self
868 .entry
869 .from_hash(hash, move |k| is_match((*k).as_ref().key_ref()))?
870 .0;
871
872 let (key, value) = (*node.as_ptr()).entry_ref();
873 Some((key, value))
874 }
875 }
876 }
877
878 unsafe impl<'a, K, V, S> Send for RawEntryBuilder<'a, K, V, S>
879 where
880 K: Send,
881 V: Send,
882 S: Send,
883 {
884 }
885
886 unsafe impl<'a, K, V, S> Sync for RawEntryBuilder<'a, K, V, S>
887 where
888 K: Sync,
889 V: Sync,
890 S: Sync,
891 {
892 }
893
894 pub struct RawEntryBuilderMut<'a, K, V, S> {
895 hash_builder: &'a S,
896 values: &'a mut Option<NonNull<Node<K, V>>>,
897 free: &'a mut Option<NonNull<Node<K, V>>>,
898 entry: hash_map::RawEntryBuilderMut<'a, NonNull<Node<K, V>>, (), NullHasher>,
899 }
900
901 impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S>
902 where
903 S: BuildHasher,
904 {
905 #[inline]
from_key<Q>(self, k: &Q) -> RawEntryMut<'a, K, V, S> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,906 pub fn from_key<Q>(self, k: &Q) -> RawEntryMut<'a, K, V, S>
907 where
908 K: Borrow<Q>,
909 Q: Hash + Eq + ?Sized,
910 {
911 let hash = hash_key(self.hash_builder, k);
912 self.from_key_hashed_nocheck(hash, k)
913 }
914
915 #[inline]
from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S> where K: Borrow<Q>, Q: Hash + Eq + ?Sized,916 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S>
917 where
918 K: Borrow<Q>,
919 Q: Hash + Eq + ?Sized,
920 {
921 self.from_hash(hash, move |o| k.eq(o.borrow()))
922 }
923
924 #[inline]
from_hash( self, hash: u64, mut is_match: impl FnMut(&K) -> bool, ) -> RawEntryMut<'a, K, V, S>925 pub fn from_hash(
926 self,
927 hash: u64,
928 mut is_match: impl FnMut(&K) -> bool,
929 ) -> RawEntryMut<'a, K, V, S> {
930 let entry = self
931 .entry
932 .from_hash(hash, move |k| is_match(unsafe { (*k).as_ref().key_ref() }));
933
934 match entry {
935 hash_map::RawEntryMut::Occupied(occupied) => {
936 RawEntryMut::Occupied(RawOccupiedEntryMut {
937 free: self.free,
938 values: self.values,
939 entry: occupied,
940 })
941 }
942 hash_map::RawEntryMut::Vacant(vacant) => RawEntryMut::Vacant(RawVacantEntryMut {
943 hash_builder: self.hash_builder,
944 values: self.values,
945 free: self.free,
946 entry: vacant,
947 }),
948 }
949 }
950 }
951
952 unsafe impl<'a, K, V, S> Send for RawEntryBuilderMut<'a, K, V, S>
953 where
954 K: Send,
955 V: Send,
956 S: Send,
957 {
958 }
959
960 unsafe impl<'a, K, V, S> Sync for RawEntryBuilderMut<'a, K, V, S>
961 where
962 K: Sync,
963 V: Sync,
964 S: Sync,
965 {
966 }
967
968 pub enum RawEntryMut<'a, K, V, S> {
969 Occupied(RawOccupiedEntryMut<'a, K, V>),
970 Vacant(RawVacantEntryMut<'a, K, V, S>),
971 }
972
973 impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
974 /// Similarly to `Entry::or_insert`, if this entry is occupied, it will move the existing entry
975 /// to the back of the internal linked list.
976 #[inline]
or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V) where K: Hash, S: BuildHasher,977 pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V)
978 where
979 K: Hash,
980 S: BuildHasher,
981 {
982 match self {
983 RawEntryMut::Occupied(mut entry) => {
984 entry.to_back();
985 entry.into_key_value()
986 }
987 RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val),
988 }
989 }
990
991 /// Similarly to `Entry::or_insert_with`, if this entry is occupied, it will move the existing
992 /// entry to the back of the internal linked list.
993 #[inline]
or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V) where F: FnOnce() -> (K, V), K: Hash, S: BuildHasher,994 pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V)
995 where
996 F: FnOnce() -> (K, V),
997 K: Hash,
998 S: BuildHasher,
999 {
1000 match self {
1001 RawEntryMut::Occupied(mut entry) => {
1002 entry.to_back();
1003 entry.into_key_value()
1004 }
1005 RawEntryMut::Vacant(entry) => {
1006 let (k, v) = default();
1007 entry.insert(k, v)
1008 }
1009 }
1010 }
1011
1012 #[inline]
and_modify<F>(self, f: F) -> Self where F: FnOnce(&mut K, &mut V),1013 pub fn and_modify<F>(self, f: F) -> Self
1014 where
1015 F: FnOnce(&mut K, &mut V),
1016 {
1017 match self {
1018 RawEntryMut::Occupied(mut entry) => {
1019 {
1020 let (k, v) = entry.get_key_value_mut();
1021 f(k, v);
1022 }
1023 RawEntryMut::Occupied(entry)
1024 }
1025 RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry),
1026 }
1027 }
1028 }
1029
1030 pub struct RawOccupiedEntryMut<'a, K, V> {
1031 free: &'a mut Option<NonNull<Node<K, V>>>,
1032 values: &'a mut Option<NonNull<Node<K, V>>>,
1033 entry: hash_map::RawOccupiedEntryMut<'a, NonNull<Node<K, V>>, (), NullHasher>,
1034 }
1035
1036 impl<'a, K, V> RawOccupiedEntryMut<'a, K, V> {
1037 #[inline]
key(&self) -> &K1038 pub fn key(&self) -> &K {
1039 self.get_key_value().0
1040 }
1041
1042 #[inline]
key_mut(&mut self) -> &mut K1043 pub fn key_mut(&mut self) -> &mut K {
1044 self.get_key_value_mut().0
1045 }
1046
1047 #[inline]
into_key(self) -> &'a mut K1048 pub fn into_key(self) -> &'a mut K {
1049 self.into_key_value().0
1050 }
1051
1052 #[inline]
get(&self) -> &V1053 pub fn get(&self) -> &V {
1054 self.get_key_value().1
1055 }
1056
1057 #[inline]
get_mut(&mut self) -> &mut V1058 pub fn get_mut(&mut self) -> &mut V {
1059 self.get_key_value_mut().1
1060 }
1061
1062 #[inline]
into_mut(self) -> &'a mut V1063 pub fn into_mut(self) -> &'a mut V {
1064 self.into_key_value().1
1065 }
1066
1067 #[inline]
get_key_value(&self) -> (&K, &V)1068 pub fn get_key_value(&self) -> (&K, &V) {
1069 unsafe {
1070 let node = *self.entry.key();
1071 let (key, value) = (*node.as_ptr()).entry_ref();
1072 (key, value)
1073 }
1074 }
1075
1076 #[inline]
get_key_value_mut(&mut self) -> (&mut K, &mut V)1077 pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
1078 unsafe {
1079 let node = *self.entry.key_mut();
1080 let (key, value) = (*node.as_ptr()).entry_mut();
1081 (key, value)
1082 }
1083 }
1084
1085 #[inline]
into_key_value(self) -> (&'a mut K, &'a mut V)1086 pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
1087 unsafe {
1088 let node = *self.entry.into_key();
1089 let (key, value) = (*node.as_ptr()).entry_mut();
1090 (key, value)
1091 }
1092 }
1093
1094 #[inline]
to_back(&mut self)1095 pub fn to_back(&mut self) {
1096 unsafe {
1097 let node = *self.entry.key_mut();
1098 detach_node(node);
1099 attach_before(node, NonNull::new_unchecked(self.values.as_ptr()));
1100 }
1101 }
1102
1103 #[inline]
to_front(&mut self)1104 pub fn to_front(&mut self) {
1105 unsafe {
1106 let node = *self.entry.key_mut();
1107 detach_node(node);
1108 attach_before(node, (*self.values.as_ptr()).links.value.next);
1109 }
1110 }
1111
1112 #[inline]
replace_value(&mut self, value: V) -> V1113 pub fn replace_value(&mut self, value: V) -> V {
1114 unsafe {
1115 let mut node = *self.entry.key_mut();
1116 mem::replace(&mut node.as_mut().entry_mut().1, value)
1117 }
1118 }
1119
1120 #[inline]
replace_key(&mut self, key: K) -> K1121 pub fn replace_key(&mut self, key: K) -> K {
1122 unsafe {
1123 let mut node = *self.entry.key_mut();
1124 mem::replace(&mut node.as_mut().entry_mut().0, key)
1125 }
1126 }
1127
1128 #[inline]
remove(self) -> V1129 pub fn remove(self) -> V {
1130 self.remove_entry().1
1131 }
1132
1133 #[inline]
remove_entry(self) -> (K, V)1134 pub fn remove_entry(self) -> (K, V) {
1135 let node = self.entry.remove_entry().0;
1136 unsafe { remove_node(self.free, node) }
1137 }
1138 }
1139
1140 pub struct RawVacantEntryMut<'a, K, V, S> {
1141 hash_builder: &'a S,
1142 values: &'a mut Option<NonNull<Node<K, V>>>,
1143 free: &'a mut Option<NonNull<Node<K, V>>>,
1144 entry: hash_map::RawVacantEntryMut<'a, NonNull<Node<K, V>>, (), NullHasher>,
1145 }
1146
1147 impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
1148 #[inline]
insert(self, key: K, value: V) -> (&'a mut K, &'a mut V) where K: Hash, S: BuildHasher,1149 pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
1150 where
1151 K: Hash,
1152 S: BuildHasher,
1153 {
1154 let hash = hash_key(self.hash_builder, &key);
1155 self.insert_hashed_nocheck(hash, key, value)
1156 }
1157
1158 #[inline]
insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) where K: Hash, S: BuildHasher,1159 pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
1160 where
1161 K: Hash,
1162 S: BuildHasher,
1163 {
1164 let hash_builder = self.hash_builder;
1165 self.insert_with_hasher(hash, key, value, |k| hash_key(hash_builder, k))
1166 }
1167
1168 #[inline]
insert_with_hasher( self, hash: u64, key: K, value: V, hasher: impl Fn(&K) -> u64, ) -> (&'a mut K, &'a mut V) where S: BuildHasher,1169 pub fn insert_with_hasher(
1170 self,
1171 hash: u64,
1172 key: K,
1173 value: V,
1174 hasher: impl Fn(&K) -> u64,
1175 ) -> (&'a mut K, &'a mut V)
1176 where
1177 S: BuildHasher,
1178 {
1179 unsafe {
1180 ensure_guard_node(self.values);
1181 let mut new_node = allocate_node(self.free);
1182 new_node.as_mut().put_entry((key, value));
1183 attach_before(new_node, NonNull::new_unchecked(self.values.as_ptr()));
1184
1185 let node = *self
1186 .entry
1187 .insert_with_hasher(hash, new_node, (), move |k| hasher((*k).as_ref().key_ref()))
1188 .0;
1189
1190 let (key, value) = (*node.as_ptr()).entry_mut();
1191 (key, value)
1192 }
1193 }
1194 }
1195
1196 impl<K, V, S> fmt::Debug for RawEntryBuilderMut<'_, K, V, S> {
1197 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1198 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1199 f.debug_struct("RawEntryBuilder").finish()
1200 }
1201 }
1202
1203 impl<K: fmt::Debug, V: fmt::Debug, S> fmt::Debug for RawEntryMut<'_, K, V, S> {
1204 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1205 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1206 match *self {
1207 RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(),
1208 RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(),
1209 }
1210 }
1211 }
1212
1213 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RawOccupiedEntryMut<'_, K, V> {
1214 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1215 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1216 f.debug_struct("RawOccupiedEntryMut")
1217 .field("key", self.key())
1218 .field("value", self.get())
1219 .finish()
1220 }
1221 }
1222
1223 impl<K, V, S> fmt::Debug for RawVacantEntryMut<'_, K, V, S> {
1224 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1225 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1226 f.debug_struct("RawVacantEntryMut").finish()
1227 }
1228 }
1229
1230 impl<K, V, S> fmt::Debug for RawEntryBuilder<'_, K, V, S> {
1231 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1232 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1233 f.debug_struct("RawEntryBuilder").finish()
1234 }
1235 }
1236
1237 unsafe impl<'a, K, V> Send for RawOccupiedEntryMut<'a, K, V>
1238 where
1239 K: Send,
1240 V: Send,
1241 {
1242 }
1243
1244 unsafe impl<'a, K, V> Sync for RawOccupiedEntryMut<'a, K, V>
1245 where
1246 K: Sync,
1247 V: Sync,
1248 {
1249 }
1250
1251 unsafe impl<'a, K, V, S> Send for RawVacantEntryMut<'a, K, V, S>
1252 where
1253 K: Send,
1254 V: Send,
1255 S: Send,
1256 {
1257 }
1258
1259 unsafe impl<'a, K, V, S> Sync for RawVacantEntryMut<'a, K, V, S>
1260 where
1261 K: Sync,
1262 V: Sync,
1263 S: Sync,
1264 {
1265 }
1266
1267 pub struct Iter<'a, K, V> {
1268 head: *const Node<K, V>,
1269 tail: *const Node<K, V>,
1270 remaining: usize,
1271 marker: PhantomData<(&'a K, &'a V)>,
1272 }
1273
1274 pub struct IterMut<'a, K, V> {
1275 head: Option<NonNull<Node<K, V>>>,
1276 tail: Option<NonNull<Node<K, V>>>,
1277 remaining: usize,
1278 marker: PhantomData<(&'a K, &'a mut V)>,
1279 }
1280
1281 pub struct IntoIter<K, V> {
1282 head: Option<NonNull<Node<K, V>>>,
1283 tail: Option<NonNull<Node<K, V>>>,
1284 remaining: usize,
1285 marker: PhantomData<(K, V)>,
1286 }
1287
1288 pub struct Drain<'a, K, V> {
1289 free: NonNull<Option<NonNull<Node<K, V>>>>,
1290 head: Option<NonNull<Node<K, V>>>,
1291 tail: Option<NonNull<Node<K, V>>>,
1292 remaining: usize,
1293 // We want `Drain` to be covariant
1294 marker: PhantomData<(K, V, &'a LinkedHashMap<K, V>)>,
1295 }
1296
1297 impl<K, V> IterMut<'_, K, V> {
1298 #[inline]
iter(&self) -> Iter<'_, K, V>1299 pub(crate) fn iter(&self) -> Iter<'_, K, V> {
1300 Iter {
1301 head: self.head.as_ptr(),
1302 tail: self.tail.as_ptr(),
1303 remaining: self.remaining,
1304 marker: PhantomData,
1305 }
1306 }
1307 }
1308
1309 impl<K, V> IntoIter<K, V> {
1310 #[inline]
iter(&self) -> Iter<'_, K, V>1311 pub(crate) fn iter(&self) -> Iter<'_, K, V> {
1312 Iter {
1313 head: self.head.as_ptr(),
1314 tail: self.tail.as_ptr(),
1315 remaining: self.remaining,
1316 marker: PhantomData,
1317 }
1318 }
1319 }
1320
1321 impl<K, V> Drain<'_, K, V> {
1322 #[inline]
iter(&self) -> Iter<'_, K, V>1323 pub(crate) fn iter(&self) -> Iter<'_, K, V> {
1324 Iter {
1325 head: self.head.as_ptr(),
1326 tail: self.tail.as_ptr(),
1327 remaining: self.remaining,
1328 marker: PhantomData,
1329 }
1330 }
1331 }
1332
1333 unsafe impl<'a, K, V> Send for Iter<'a, K, V>
1334 where
1335 K: Send,
1336 V: Send,
1337 {
1338 }
1339
1340 unsafe impl<'a, K, V> Send for IterMut<'a, K, V>
1341 where
1342 K: Send,
1343 V: Send,
1344 {
1345 }
1346
1347 unsafe impl<K, V> Send for IntoIter<K, V>
1348 where
1349 K: Send,
1350 V: Send,
1351 {
1352 }
1353
1354 unsafe impl<'a, K, V> Send for Drain<'a, K, V>
1355 where
1356 K: Send,
1357 V: Send,
1358 {
1359 }
1360
1361 unsafe impl<'a, K, V> Sync for Iter<'a, K, V>
1362 where
1363 K: Sync,
1364 V: Sync,
1365 {
1366 }
1367
1368 unsafe impl<'a, K, V> Sync for IterMut<'a, K, V>
1369 where
1370 K: Sync,
1371 V: Sync,
1372 {
1373 }
1374
1375 unsafe impl<K, V> Sync for IntoIter<K, V>
1376 where
1377 K: Sync,
1378 V: Sync,
1379 {
1380 }
1381
1382 unsafe impl<'a, K, V> Sync for Drain<'a, K, V>
1383 where
1384 K: Sync,
1385 V: Sync,
1386 {
1387 }
1388
1389 impl<'a, K, V> Clone for Iter<'a, K, V> {
1390 #[inline]
clone(&self) -> Self1391 fn clone(&self) -> Self {
1392 Iter { ..*self }
1393 }
1394 }
1395
1396 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
1397 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1398 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1399 f.debug_list().entries(self.clone()).finish()
1400 }
1401 }
1402
1403 impl<K, V> fmt::Debug for IterMut<'_, K, V>
1404 where
1405 K: fmt::Debug,
1406 V: fmt::Debug,
1407 {
1408 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1409 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1410 f.debug_list().entries(self.iter()).finish()
1411 }
1412 }
1413
1414 impl<K, V> fmt::Debug for IntoIter<K, V>
1415 where
1416 K: fmt::Debug,
1417 V: fmt::Debug,
1418 {
1419 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1420 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1421 f.debug_list().entries(self.iter()).finish()
1422 }
1423 }
1424
1425 impl<K, V> fmt::Debug for Drain<'_, K, V>
1426 where
1427 K: fmt::Debug,
1428 V: fmt::Debug,
1429 {
1430 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1431 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1432 f.debug_list().entries(self.iter()).finish()
1433 }
1434 }
1435
1436 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1437 type Item = (&'a K, &'a V);
1438
1439 #[inline]
next(&mut self) -> Option<(&'a K, &'a V)>1440 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1441 if self.remaining == 0 {
1442 None
1443 } else {
1444 self.remaining -= 1;
1445 unsafe {
1446 let (key, value) = (*self.head).entry_ref();
1447 self.head = (*self.head).links.value.next.as_ptr();
1448 Some((key, value))
1449 }
1450 }
1451 }
1452
1453 #[inline]
size_hint(&self) -> (usize, Option<usize>)1454 fn size_hint(&self) -> (usize, Option<usize>) {
1455 (self.remaining, Some(self.remaining))
1456 }
1457 }
1458
1459 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1460 type Item = (&'a K, &'a mut V);
1461
1462 #[inline]
next(&mut self) -> Option<(&'a K, &'a mut V)>1463 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1464 if self.remaining == 0 {
1465 None
1466 } else {
1467 self.remaining -= 1;
1468 unsafe {
1469 let head = self.head.as_ptr();
1470 let (key, value) = (*head).entry_mut();
1471 self.head = Some((*head).links.value.next);
1472 Some((key, value))
1473 }
1474 }
1475 }
1476
1477 #[inline]
size_hint(&self) -> (usize, Option<usize>)1478 fn size_hint(&self) -> (usize, Option<usize>) {
1479 (self.remaining, Some(self.remaining))
1480 }
1481 }
1482
1483 impl<K, V> Iterator for IntoIter<K, V> {
1484 type Item = (K, V);
1485
1486 #[inline]
next(&mut self) -> Option<(K, V)>1487 fn next(&mut self) -> Option<(K, V)> {
1488 if self.remaining == 0 {
1489 return None;
1490 }
1491 self.remaining -= 1;
1492 unsafe {
1493 let head = self.head.as_ptr();
1494 self.head = Some((*head).links.value.next);
1495 let mut e = Box::from_raw(head);
1496 Some(e.take_entry())
1497 }
1498 }
1499
1500 #[inline]
size_hint(&self) -> (usize, Option<usize>)1501 fn size_hint(&self) -> (usize, Option<usize>) {
1502 (self.remaining, Some(self.remaining))
1503 }
1504 }
1505
1506 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1507 type Item = (K, V);
1508
1509 #[inline]
next(&mut self) -> Option<(K, V)>1510 fn next(&mut self) -> Option<(K, V)> {
1511 if self.remaining == 0 {
1512 return None;
1513 }
1514 self.remaining -= 1;
1515 unsafe {
1516 let mut head = NonNull::new_unchecked(self.head.as_ptr());
1517 self.head = Some(head.as_ref().links.value.next);
1518 let entry = head.as_mut().take_entry();
1519 push_free(self.free.as_mut(), head);
1520 Some(entry)
1521 }
1522 }
1523
1524 #[inline]
size_hint(&self) -> (usize, Option<usize>)1525 fn size_hint(&self) -> (usize, Option<usize>) {
1526 (self.remaining, Some(self.remaining))
1527 }
1528 }
1529
1530 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1531 #[inline]
next_back(&mut self) -> Option<(&'a K, &'a V)>1532 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1533 if self.remaining == 0 {
1534 None
1535 } else {
1536 self.remaining -= 1;
1537 unsafe {
1538 let tail = self.tail;
1539 self.tail = (*tail).links.value.prev.as_ptr();
1540 let (key, value) = (*tail).entry_ref();
1541 Some((key, value))
1542 }
1543 }
1544 }
1545 }
1546
1547 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1548 #[inline]
next_back(&mut self) -> Option<(&'a K, &'a mut V)>1549 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1550 if self.remaining == 0 {
1551 None
1552 } else {
1553 self.remaining -= 1;
1554 unsafe {
1555 let tail = self.tail.as_ptr();
1556 self.tail = Some((*tail).links.value.prev);
1557 let (key, value) = (*tail).entry_mut();
1558 Some((key, value))
1559 }
1560 }
1561 }
1562 }
1563
1564 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1565 #[inline]
next_back(&mut self) -> Option<(K, V)>1566 fn next_back(&mut self) -> Option<(K, V)> {
1567 if self.remaining == 0 {
1568 return None;
1569 }
1570 self.remaining -= 1;
1571 unsafe {
1572 let mut e = *Box::from_raw(self.tail.as_ptr());
1573 self.tail = Some(e.links.value.prev);
1574 Some(e.take_entry())
1575 }
1576 }
1577 }
1578
1579 impl<'a, K, V> DoubleEndedIterator for Drain<'a, K, V> {
1580 #[inline]
next_back(&mut self) -> Option<(K, V)>1581 fn next_back(&mut self) -> Option<(K, V)> {
1582 if self.remaining == 0 {
1583 return None;
1584 }
1585 self.remaining -= 1;
1586 unsafe {
1587 let mut tail = NonNull::new_unchecked(self.tail.as_ptr());
1588 self.tail = Some(tail.as_ref().links.value.prev);
1589 let entry = tail.as_mut().take_entry();
1590 push_free(&mut *self.free.as_ptr(), tail);
1591 Some(entry)
1592 }
1593 }
1594 }
1595
1596 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
1597
1598 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
1599
1600 impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
1601
1602 impl<K, V> Drop for IntoIter<K, V> {
1603 #[inline]
drop(&mut self)1604 fn drop(&mut self) {
1605 for _ in 0..self.remaining {
1606 unsafe {
1607 let tail = self.tail.as_ptr();
1608 self.tail = Some((*tail).links.value.prev);
1609 (*tail).take_entry();
1610 Box::from_raw(tail);
1611 }
1612 }
1613 }
1614 }
1615
1616 impl<'a, K, V> Drop for Drain<'a, K, V> {
1617 #[inline]
drop(&mut self)1618 fn drop(&mut self) {
1619 for _ in 0..self.remaining {
1620 unsafe {
1621 let mut tail = NonNull::new_unchecked(self.tail.as_ptr());
1622 self.tail = Some(tail.as_ref().links.value.prev);
1623 tail.as_mut().take_entry();
1624 push_free(&mut *self.free.as_ptr(), tail);
1625 }
1626 }
1627 }
1628 }
1629
1630 pub struct Keys<'a, K, V> {
1631 inner: Iter<'a, K, V>,
1632 }
1633
1634 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
1635 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1636 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1637 f.debug_list().entries(self.clone()).finish()
1638 }
1639 }
1640
1641 impl<'a, K, V> Clone for Keys<'a, K, V> {
1642 #[inline]
clone(&self) -> Keys<'a, K, V>1643 fn clone(&self) -> Keys<'a, K, V> {
1644 Keys {
1645 inner: self.inner.clone(),
1646 }
1647 }
1648 }
1649
1650 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1651 type Item = &'a K;
1652
1653 #[inline]
next(&mut self) -> Option<&'a K>1654 fn next(&mut self) -> Option<&'a K> {
1655 self.inner.next().map(|e| e.0)
1656 }
1657
1658 #[inline]
size_hint(&self) -> (usize, Option<usize>)1659 fn size_hint(&self) -> (usize, Option<usize>) {
1660 self.inner.size_hint()
1661 }
1662 }
1663
1664 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1665 #[inline]
next_back(&mut self) -> Option<&'a K>1666 fn next_back(&mut self) -> Option<&'a K> {
1667 self.inner.next_back().map(|e| e.0)
1668 }
1669 }
1670
1671 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1672 #[inline]
len(&self) -> usize1673 fn len(&self) -> usize {
1674 self.inner.len()
1675 }
1676 }
1677
1678 pub struct Values<'a, K, V> {
1679 inner: Iter<'a, K, V>,
1680 }
1681
1682 impl<K, V> Clone for Values<'_, K, V> {
1683 #[inline]
clone(&self) -> Self1684 fn clone(&self) -> Self {
1685 Values {
1686 inner: self.inner.clone(),
1687 }
1688 }
1689 }
1690
1691 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
1692 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1693 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1694 f.debug_list().entries(self.clone()).finish()
1695 }
1696 }
1697
1698 impl<'a, K, V> Iterator for Values<'a, K, V> {
1699 type Item = &'a V;
1700
1701 #[inline]
next(&mut self) -> Option<&'a V>1702 fn next(&mut self) -> Option<&'a V> {
1703 self.inner.next().map(|e| e.1)
1704 }
1705
1706 #[inline]
size_hint(&self) -> (usize, Option<usize>)1707 fn size_hint(&self) -> (usize, Option<usize>) {
1708 self.inner.size_hint()
1709 }
1710 }
1711
1712 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1713 #[inline]
next_back(&mut self) -> Option<&'a V>1714 fn next_back(&mut self) -> Option<&'a V> {
1715 self.inner.next_back().map(|e| e.1)
1716 }
1717 }
1718
1719 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1720 #[inline]
len(&self) -> usize1721 fn len(&self) -> usize {
1722 self.inner.len()
1723 }
1724 }
1725
1726 pub struct ValuesMut<'a, K, V> {
1727 inner: IterMut<'a, K, V>,
1728 }
1729
1730 impl<K, V> fmt::Debug for ValuesMut<'_, K, V>
1731 where
1732 K: fmt::Debug,
1733 V: fmt::Debug,
1734 {
1735 #[inline]
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1736 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1737 f.debug_list().entries(self.inner.iter()).finish()
1738 }
1739 }
1740
1741 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1742 type Item = &'a mut V;
1743
1744 #[inline]
next(&mut self) -> Option<&'a mut V>1745 fn next(&mut self) -> Option<&'a mut V> {
1746 self.inner.next().map(|e| e.1)
1747 }
1748
1749 #[inline]
size_hint(&self) -> (usize, Option<usize>)1750 fn size_hint(&self) -> (usize, Option<usize>) {
1751 self.inner.size_hint()
1752 }
1753 }
1754
1755 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1756 #[inline]
next_back(&mut self) -> Option<&'a mut V>1757 fn next_back(&mut self) -> Option<&'a mut V> {
1758 self.inner.next_back().map(|e| e.1)
1759 }
1760 }
1761
1762 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
1763 #[inline]
len(&self) -> usize1764 fn len(&self) -> usize {
1765 self.inner.len()
1766 }
1767 }
1768
1769 impl<'a, K, V, S> IntoIterator for &'a LinkedHashMap<K, V, S> {
1770 type Item = (&'a K, &'a V);
1771 type IntoIter = Iter<'a, K, V>;
1772
1773 #[inline]
into_iter(self) -> Iter<'a, K, V>1774 fn into_iter(self) -> Iter<'a, K, V> {
1775 self.iter()
1776 }
1777 }
1778
1779 impl<'a, K, V, S> IntoIterator for &'a mut LinkedHashMap<K, V, S> {
1780 type Item = (&'a K, &'a mut V);
1781 type IntoIter = IterMut<'a, K, V>;
1782
1783 #[inline]
into_iter(self) -> IterMut<'a, K, V>1784 fn into_iter(self) -> IterMut<'a, K, V> {
1785 self.iter_mut()
1786 }
1787 }
1788
1789 impl<K, V, S> IntoIterator for LinkedHashMap<K, V, S> {
1790 type Item = (K, V);
1791 type IntoIter = IntoIter<K, V>;
1792
1793 #[inline]
into_iter(mut self) -> IntoIter<K, V>1794 fn into_iter(mut self) -> IntoIter<K, V> {
1795 unsafe {
1796 let (head, tail) = if let Some(values) = self.values {
1797 let ValueLinks {
1798 next: head,
1799 prev: tail,
1800 } = values.as_ref().links.value;
1801
1802 Box::from_raw(self.values.as_ptr());
1803 self.values = None;
1804
1805 (Some(head), Some(tail))
1806 } else {
1807 (None, None)
1808 };
1809 let len = self.len();
1810
1811 drop_free_nodes(self.free);
1812 self.free = None;
1813
1814 self.map.clear();
1815
1816 IntoIter {
1817 head,
1818 tail,
1819 remaining: len,
1820 marker: PhantomData,
1821 }
1822 }
1823 }
1824 }
1825
1826 // A ZST that asserts that the inner HashMap will not do its own key hashing
1827 struct NullHasher;
1828
1829 impl BuildHasher for NullHasher {
1830 type Hasher = Self;
1831
1832 #[inline]
build_hasher(&self) -> Self1833 fn build_hasher(&self) -> Self {
1834 Self
1835 }
1836 }
1837
1838 impl Hasher for NullHasher {
1839 #[inline]
write(&mut self, _bytes: &[u8])1840 fn write(&mut self, _bytes: &[u8]) {
1841 unreachable!("inner map should not be using its built-in hasher")
1842 }
1843
1844 #[inline]
finish(&self) -> u641845 fn finish(&self) -> u64 {
1846 unreachable!("inner map should not be using its built-in hasher")
1847 }
1848 }
1849
1850 struct ValueLinks<K, V> {
1851 next: NonNull<Node<K, V>>,
1852 prev: NonNull<Node<K, V>>,
1853 }
1854
1855 impl<K, V> Clone for ValueLinks<K, V> {
1856 #[inline]
clone(&self) -> Self1857 fn clone(&self) -> Self {
1858 ValueLinks {
1859 next: self.next,
1860 prev: self.prev,
1861 }
1862 }
1863 }
1864
1865 impl<K, V> Copy for ValueLinks<K, V> {}
1866
1867 struct FreeLink<K, V> {
1868 next: Option<NonNull<Node<K, V>>>,
1869 }
1870
1871 impl<K, V> Clone for FreeLink<K, V> {
1872 #[inline]
clone(&self) -> Self1873 fn clone(&self) -> Self {
1874 FreeLink { next: self.next }
1875 }
1876 }
1877
1878 impl<K, V> Copy for FreeLink<K, V> {}
1879
1880 union Links<K, V> {
1881 value: ValueLinks<K, V>,
1882 free: FreeLink<K, V>,
1883 }
1884
1885 struct Node<K, V> {
1886 entry: MaybeUninit<(K, V)>,
1887 links: Links<K, V>,
1888 }
1889
1890 impl<K, V> Node<K, V> {
1891 #[inline]
put_entry(&mut self, entry: (K, V))1892 unsafe fn put_entry(&mut self, entry: (K, V)) {
1893 self.entry.as_mut_ptr().write(entry)
1894 }
1895
1896 #[inline]
entry_ref(&self) -> &(K, V)1897 unsafe fn entry_ref(&self) -> &(K, V) {
1898 &*self.entry.as_ptr()
1899 }
1900
1901 #[inline]
key_ref(&self) -> &K1902 unsafe fn key_ref(&self) -> &K {
1903 &(*self.entry.as_ptr()).0
1904 }
1905
1906 #[inline]
entry_mut(&mut self) -> &mut (K, V)1907 unsafe fn entry_mut(&mut self) -> &mut (K, V) {
1908 &mut *self.entry.as_mut_ptr()
1909 }
1910
1911 #[inline]
take_entry(&mut self) -> (K, V)1912 unsafe fn take_entry(&mut self) -> (K, V) {
1913 self.entry.as_ptr().read()
1914 }
1915 }
1916
1917 trait OptNonNullExt<T> {
as_ptr(self) -> *mut T1918 fn as_ptr(self) -> *mut T;
1919 }
1920
1921 impl<T> OptNonNullExt<T> for Option<NonNull<T>> {
1922 #[inline]
as_ptr(self) -> *mut T1923 fn as_ptr(self) -> *mut T {
1924 match self {
1925 Some(ptr) => ptr.as_ptr(),
1926 None => ptr::null_mut(),
1927 }
1928 }
1929 }
1930
1931 // Allocate a circular list guard node if not present.
1932 #[inline]
ensure_guard_node<K, V>(head: &mut Option<NonNull<Node<K, V>>>)1933 unsafe fn ensure_guard_node<K, V>(head: &mut Option<NonNull<Node<K, V>>>) {
1934 if head.is_none() {
1935 let mut p = NonNull::new_unchecked(Box::into_raw(Box::new(Node {
1936 entry: MaybeUninit::uninit(),
1937 links: Links {
1938 value: ValueLinks {
1939 next: NonNull::dangling(),
1940 prev: NonNull::dangling(),
1941 },
1942 },
1943 })));
1944 p.as_mut().links.value = ValueLinks { next: p, prev: p };
1945 *head = Some(p);
1946 }
1947 }
1948
1949 // Attach the `to_attach` node to the existing circular list *before* `node`.
1950 #[inline]
attach_before<K, V>(mut to_attach: NonNull<Node<K, V>>, mut node: NonNull<Node<K, V>>)1951 unsafe fn attach_before<K, V>(mut to_attach: NonNull<Node<K, V>>, mut node: NonNull<Node<K, V>>) {
1952 to_attach.as_mut().links.value = ValueLinks {
1953 prev: node.as_ref().links.value.prev,
1954 next: node,
1955 };
1956 node.as_mut().links.value.prev = to_attach;
1957 (*to_attach.as_mut().links.value.prev.as_ptr())
1958 .links
1959 .value
1960 .next = to_attach;
1961 }
1962
1963 #[inline]
detach_node<K, V>(mut node: NonNull<Node<K, V>>)1964 unsafe fn detach_node<K, V>(mut node: NonNull<Node<K, V>>) {
1965 node.as_mut().links.value.prev.as_mut().links.value.next = node.as_ref().links.value.next;
1966 node.as_mut().links.value.next.as_mut().links.value.prev = node.as_ref().links.value.prev;
1967 }
1968
1969 #[inline]
push_free<K, V>( free_list: &mut Option<NonNull<Node<K, V>>>, mut node: NonNull<Node<K, V>>, )1970 unsafe fn push_free<K, V>(
1971 free_list: &mut Option<NonNull<Node<K, V>>>,
1972 mut node: NonNull<Node<K, V>>,
1973 ) {
1974 node.as_mut().links.free.next = *free_list;
1975 *free_list = Some(node);
1976 }
1977
1978 #[inline]
pop_free<K, V>( free_list: &mut Option<NonNull<Node<K, V>>>, ) -> Option<NonNull<Node<K, V>>>1979 unsafe fn pop_free<K, V>(
1980 free_list: &mut Option<NonNull<Node<K, V>>>,
1981 ) -> Option<NonNull<Node<K, V>>> {
1982 if let Some(free) = *free_list {
1983 *free_list = free.as_ref().links.free.next;
1984 Some(free)
1985 } else {
1986 None
1987 }
1988 }
1989
1990 #[inline]
allocate_node<K, V>(free_list: &mut Option<NonNull<Node<K, V>>>) -> NonNull<Node<K, V>>1991 unsafe fn allocate_node<K, V>(free_list: &mut Option<NonNull<Node<K, V>>>) -> NonNull<Node<K, V>> {
1992 if let Some(mut free) = pop_free(free_list) {
1993 free.as_mut().links.value = ValueLinks {
1994 next: NonNull::dangling(),
1995 prev: NonNull::dangling(),
1996 };
1997 free
1998 } else {
1999 NonNull::new_unchecked(Box::into_raw(Box::new(Node {
2000 entry: MaybeUninit::uninit(),
2001 links: Links {
2002 value: ValueLinks {
2003 next: NonNull::dangling(),
2004 prev: NonNull::dangling(),
2005 },
2006 },
2007 })))
2008 }
2009 }
2010
2011 // Given node is assumed to be the guard node and is *not* dropped.
2012 #[inline]
drop_value_nodes<K, V>(guard: NonNull<Node<K, V>>)2013 unsafe fn drop_value_nodes<K, V>(guard: NonNull<Node<K, V>>) {
2014 let mut cur = guard.as_ref().links.value.prev;
2015 while cur != guard {
2016 let prev = cur.as_ref().links.value.prev;
2017 cur.as_mut().take_entry();
2018 Box::from_raw(cur.as_ptr());
2019 cur = prev;
2020 }
2021 }
2022
2023 // Drops all linked free nodes starting with the given node. Free nodes are only non-circular
2024 // singly linked, and should have uninitialized keys / values.
2025 #[inline]
drop_free_nodes<K, V>(mut free: Option<NonNull<Node<K, V>>>)2026 unsafe fn drop_free_nodes<K, V>(mut free: Option<NonNull<Node<K, V>>>) {
2027 while let Some(some_free) = free {
2028 let next_free = some_free.as_ref().links.free.next;
2029 Box::from_raw(some_free.as_ptr());
2030 free = next_free;
2031 }
2032 }
2033
2034 #[inline]
remove_node<K, V>( free_list: &mut Option<NonNull<Node<K, V>>>, mut node: NonNull<Node<K, V>>, ) -> (K, V)2035 unsafe fn remove_node<K, V>(
2036 free_list: &mut Option<NonNull<Node<K, V>>>,
2037 mut node: NonNull<Node<K, V>>,
2038 ) -> (K, V) {
2039 detach_node(node);
2040 push_free(free_list, node);
2041 node.as_mut().take_entry()
2042 }
2043
2044 #[inline]
hash_key<S, Q>(s: &S, k: &Q) -> u64 where S: BuildHasher, Q: Hash + ?Sized,2045 fn hash_key<S, Q>(s: &S, k: &Q) -> u64
2046 where
2047 S: BuildHasher,
2048 Q: Hash + ?Sized,
2049 {
2050 let mut hasher = s.build_hasher();
2051 k.hash(&mut hasher);
2052 hasher.finish()
2053 }
2054