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