hashlink/
linked_hash_map.rs

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

hashlink/
linked_hash_map.rs
