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