1// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A `HashMap` wrapper that holds key-value pairs in insertion order.
12//!
13//! # Examples
14//!
15//! ```
16//! use linked_hash_map::LinkedHashMap;
17//!
18//! let mut map = LinkedHashMap::new();
19//! map.insert(2, 20);
20//! map.insert(1, 10);
21//! map.insert(3, 30);
22//! assert_eq!(map[&1], 10);
23//! assert_eq!(map[&2], 20);
24//! assert_eq!(map[&3], 30);
25//!
26//! let items: Vec<(i32, i32)> = map.iter().map(|t| (*t.0, *t.1)).collect();
27//! assert_eq!(items, [(2, 20), (1, 10), (3, 30)]);
28//! ```
29
30#![forbid(missing_docs)]
31#![cfg_attr(all(feature = "nightly", test), feature(test))]
32
33// Optional Serde support
34#[cfg(feature = "serde_impl")]
35pub mod serde;
36// Optional Heapsize support
37#[cfg(feature = "heapsize_impl")]
38mod heapsize;
39#[cfg(test)]
40mod tests;
41
42use std::borrow::Borrow;
43use std::cmp::Ordering;
44use std::collections::hash_map::{self, HashMap};
45use std::fmt;
46use std::hash::{BuildHasher, Hash, Hasher};
47use std::iter;
48use std::marker;
49use std::mem;
50use std::ops::{Index, IndexMut};
51use std::ptr::{self, addr_of_mut};
52
53struct KeyRef<K> {
54 k: *const K,
55}
56
57struct Node<K, V> {
58 next: *mut Node<K, V>,
59 prev: *mut Node<K, V>,
60 key: K,
61 value: V,
62}
63
64/// A linked hash map.
65pub struct LinkedHashMap<K, V, S = hash_map::RandomState> {
66 map: HashMap<KeyRef<K>, *mut Node<K, V>, S>,
67 head: *mut Node<K, V>,
68 free: *mut Node<K, V>,
69}
70
71impl<K: Hash> Hash for KeyRef<K> {
72 fn hash<H: Hasher>(&self, state: &mut H) {
73 unsafe { (*self.k).hash(state) }
74 }
75}
76
77impl<K: PartialEq> PartialEq for KeyRef<K> {
78 fn eq(&self, other: &Self) -> bool {
79 unsafe { (*self.k).eq(&*other.k) }
80 }
81}
82
83impl<K: Eq> Eq for KeyRef<K> {}
84
85// This type exists only to support borrowing `KeyRef`s, which cannot be borrowed to `Q` directly
86// due to conflicting implementations of `Borrow`. The layout of `&Qey<Q>` must be identical to
87// `&Q` in order to support transmuting in the `Qey::from_ref` method.
88#[derive(Hash, PartialEq, Eq)]
89#[repr(transparent)]
90struct Qey<Q: ?Sized>(Q);
91
92impl<Q: ?Sized> Qey<Q> {
93 fn from_ref(q: &Q) -> &Self {
94 unsafe { mem::transmute(src:q) }
95 }
96}
97
98impl<K, Q: ?Sized> Borrow<Qey<Q>> for KeyRef<K>
99where
100 K: Borrow<Q>,
101{
102 fn borrow(&self) -> &Qey<Q> {
103 Qey::from_ref(unsafe { (*self.k).borrow() })
104 }
105}
106
107impl<K, V> Node<K, V> {
108 fn new(k: K, v: V) -> Self {
109 Node {
110 key: k,
111 value: v,
112 next: ptr::null_mut(),
113 prev: ptr::null_mut(),
114 }
115 }
116}
117
118// drop empty node without dropping its key and value
119unsafe fn drop_empty_node<K, V>(the_box: *mut Node<K, V>) {
120 // Safety:
121 // In this crate all `Node` is allocated via `Box` or `alloc`, and `Box` uses the
122 // Global allocator for its allocation,
123 // (https://doc.rust-lang.org/std/boxed/index.html#memory-layout) so we can safely
124 // deallocate the pointer to `Node` by calling `dealloc` method
125 let layout: Layout = std::alloc::Layout::new::<Node<K, V>>();
126 std::alloc::dealloc(ptr:the_box as *mut u8, layout);
127}
128
129impl<K: Hash + Eq, V> LinkedHashMap<K, V> {
130 /// Creates a linked hash map.
131 pub fn new() -> Self {
132 Self::with_map(HashMap::new())
133 }
134
135 /// Creates an empty linked hash map with the given initial capacity.
136 pub fn with_capacity(capacity: usize) -> Self {
137 Self::with_map(HashMap::with_capacity(capacity))
138 }
139}
140
141impl<K, V, S> LinkedHashMap<K, V, S> {
142 #[inline]
143 fn detach(&mut self, node: *mut Node<K, V>) {
144 unsafe {
145 (*(*node).prev).next = (*node).next;
146 (*(*node).next).prev = (*node).prev;
147 }
148 }
149
150 #[inline]
151 fn attach(&mut self, node: *mut Node<K, V>) {
152 unsafe {
153 (*node).next = (*self.head).next;
154 (*node).prev = self.head;
155 (*self.head).next = node;
156 (*(*node).next).prev = node;
157 }
158 }
159
160 // Caller must check `!self.head.is_null()`
161 unsafe fn drop_entries(&mut self) {
162 let mut cur = (*self.head).next;
163 while cur != self.head {
164 let next = (*cur).next;
165 Box::from_raw(cur);
166 cur = next;
167 }
168 }
169
170 fn clear_free_list(&mut self) {
171 unsafe {
172 let mut free = self.free;
173 while !free.is_null() {
174 let next_free = (*free).next;
175 drop_empty_node(free);
176 free = next_free;
177 }
178 self.free = ptr::null_mut();
179 }
180 }
181
182 fn ensure_guard_node(&mut self) {
183 if self.head.is_null() {
184 // allocate the guard node if not present
185 unsafe {
186 let node_layout = std::alloc::Layout::new::<Node<K, V>>();
187 self.head = std::alloc::alloc(node_layout) as *mut Node<K, V>;
188 (*self.head).next = self.head;
189 (*self.head).prev = self.head;
190 }
191 }
192 }
193}
194
195impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
196 fn with_map(map: HashMap<KeyRef<K>, *mut Node<K, V>, S>) -> Self {
197 LinkedHashMap {
198 map,
199 head: ptr::null_mut(),
200 free: ptr::null_mut(),
201 }
202 }
203
204 /// Creates an empty linked hash map with the given initial hash builder.
205 pub fn with_hasher(hash_builder: S) -> Self {
206 Self::with_map(HashMap::with_hasher(hash_builder))
207 }
208
209 /// Creates an empty linked hash map with the given initial capacity and hash builder.
210 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
211 Self::with_map(HashMap::with_capacity_and_hasher(capacity, hash_builder))
212 }
213
214 /// Reserves capacity for at least `additional` more elements to be inserted into the map. The
215 /// map may reserve more space to avoid frequent allocations.
216 ///
217 /// # Panics
218 ///
219 /// Panics if the new allocation size overflows `usize.`
220 pub fn reserve(&mut self, additional: usize) {
221 self.map.reserve(additional);
222 }
223
224 /// Shrinks the capacity of the map as much as possible. It will drop down as much as possible
225 /// while maintaining the internal rules and possibly leaving some space in accordance with the
226 /// resize policy.
227 pub fn shrink_to_fit(&mut self) {
228 self.map.shrink_to_fit();
229 self.clear_free_list();
230 }
231
232 /// Gets the given key's corresponding entry in the map for in-place manipulation.
233 ///
234 /// # Examples
235 ///
236 /// ```
237 /// use linked_hash_map::LinkedHashMap;
238 ///
239 /// let mut letters = LinkedHashMap::new();
240 ///
241 /// for ch in "a short treatise on fungi".chars() {
242 /// let counter = letters.entry(ch).or_insert(0);
243 /// *counter += 1;
244 /// }
245 ///
246 /// assert_eq!(letters[&'s'], 2);
247 /// assert_eq!(letters[&'t'], 3);
248 /// assert_eq!(letters[&'u'], 1);
249 /// assert_eq!(letters.get(&'y'), None);
250 /// ```
251 pub fn entry(&mut self, k: K) -> Entry<K, V, S> {
252 let self_ptr: *mut Self = self;
253
254 if let Some(entry) = self.map.get_mut(&KeyRef { k: &k }) {
255 return Entry::Occupied(OccupiedEntry {
256 entry: *entry,
257 map: self_ptr,
258 marker: marker::PhantomData,
259 });
260 }
261
262 Entry::Vacant(VacantEntry { key: k, map: self })
263 }
264
265 /// Returns an iterator visiting all entries in insertion order.
266 /// Iterator element type is `OccupiedEntry<K, V, S>`. Allows for removal
267 /// as well as replacing the entry.
268 ///
269 /// # Examples
270 /// ```
271 /// use linked_hash_map::LinkedHashMap;
272 ///
273 /// let mut map = LinkedHashMap::new();
274 /// map.insert("a", 10);
275 /// map.insert("c", 30);
276 /// map.insert("b", 20);
277 ///
278 /// {
279 /// let mut iter = map.entries();
280 /// let mut entry = iter.next().unwrap();
281 /// assert_eq!(&"a", entry.key());
282 /// *entry.get_mut() = 17;
283 /// }
284 ///
285 /// assert_eq!(&17, map.get(&"a").unwrap());
286 /// ```
287 pub fn entries(&mut self) -> Entries<K, V, S> {
288 let head = if !self.head.is_null() {
289 unsafe { (*self.head).prev }
290 } else {
291 ptr::null_mut()
292 };
293 Entries {
294 map: self,
295 head,
296 remaining: self.len(),
297 marker: marker::PhantomData,
298 }
299 }
300
301 /// Inserts a key-value pair into the map. If the key already existed, the old value is
302 /// returned.
303 ///
304 /// # Examples
305 ///
306 /// ```
307 /// use linked_hash_map::LinkedHashMap;
308 /// let mut map = LinkedHashMap::new();
309 ///
310 /// map.insert(1, "a");
311 /// map.insert(2, "b");
312 /// assert_eq!(map[&1], "a");
313 /// assert_eq!(map[&2], "b");
314 /// ```
315 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
316 self.ensure_guard_node();
317
318 let (node, old_val) = match self.map.get(&KeyRef { k: &k }) {
319 Some(node) => {
320 let old_val = unsafe { ptr::replace(&mut (**node).value, v) };
321 (*node, Some(old_val))
322 }
323 None => {
324 let node = if self.free.is_null() {
325 Box::into_raw(Box::new(Node::new(k, v)))
326 } else {
327 // use a recycled box
328 unsafe {
329 let free = self.free;
330 self.free = (*free).next;
331 ptr::write(free, Node::new(k, v));
332 free
333 }
334 };
335 (node, None)
336 }
337 };
338 match old_val {
339 Some(_) => {
340 // Existing node, just update LRU position
341 self.detach(node);
342 self.attach(node);
343 }
344 None => {
345 let keyref = unsafe { &(*node).key };
346 self.map.insert(KeyRef { k: keyref }, node);
347 self.attach(node);
348 }
349 }
350 old_val
351 }
352
353 /// Checks if the map contains the given key.
354 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
355 where
356 K: Borrow<Q>,
357 Q: Eq + Hash,
358 {
359 self.map.contains_key(Qey::from_ref(k))
360 }
361
362 /// Returns the value corresponding to the key in the map.
363 ///
364 /// # Examples
365 ///
366 /// ```
367 /// use linked_hash_map::LinkedHashMap;
368 /// let mut map = LinkedHashMap::new();
369 ///
370 /// map.insert(1, "a");
371 /// map.insert(2, "b");
372 /// map.insert(2, "c");
373 /// map.insert(3, "d");
374 ///
375 /// assert_eq!(map.get(&1), Some(&"a"));
376 /// assert_eq!(map.get(&2), Some(&"c"));
377 /// ```
378 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
379 where
380 K: Borrow<Q>,
381 Q: Eq + Hash,
382 {
383 self.map
384 .get(Qey::from_ref(k))
385 .map(|e| unsafe { &(**e).value })
386 }
387
388 /// Returns the mutable reference corresponding to the key in the map.
389 ///
390 /// # Examples
391 ///
392 /// ```
393 /// use linked_hash_map::LinkedHashMap;
394 /// let mut map = LinkedHashMap::new();
395 ///
396 /// map.insert(1, "a");
397 /// map.insert(2, "b");
398 ///
399 /// *map.get_mut(&1).unwrap() = "c";
400 /// assert_eq!(map.get(&1), Some(&"c"));
401 /// ```
402 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
403 where
404 K: Borrow<Q>,
405 Q: Eq + Hash,
406 {
407 self.map
408 .get(Qey::from_ref(k))
409 .map(|e| unsafe { &mut (**e).value })
410 }
411
412 /// Returns the value corresponding to the key in the map.
413 ///
414 /// If value is found, it is moved to the end of the list.
415 /// This operation can be used in implemenation of LRU cache.
416 ///
417 /// # Examples
418 ///
419 /// ```
420 /// use linked_hash_map::LinkedHashMap;
421 /// let mut map = LinkedHashMap::new();
422 ///
423 /// map.insert(1, "a");
424 /// map.insert(2, "b");
425 /// map.insert(3, "d");
426 ///
427 /// assert_eq!(map.get_refresh(&2), Some(&mut "b"));
428 ///
429 /// assert_eq!((&2, &"b"), map.iter().rev().next().unwrap());
430 /// ```
431 pub fn get_refresh<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
432 where
433 K: Borrow<Q>,
434 Q: Eq + Hash,
435 {
436 let (value, node_ptr_opt) = match self.map.get(Qey::from_ref(k)) {
437 None => (None, None),
438 Some(node) => (Some(unsafe { &mut (**node).value }), Some(*node)),
439 };
440 if let Some(node_ptr) = node_ptr_opt {
441 self.detach(node_ptr);
442 self.attach(node_ptr);
443 }
444 value
445 }
446
447 /// Removes and returns the value corresponding to the key from the map.
448 ///
449 /// # Examples
450 ///
451 /// ```
452 /// use linked_hash_map::LinkedHashMap;
453 /// let mut map = LinkedHashMap::new();
454 ///
455 /// map.insert(2, "a");
456 ///
457 /// assert_eq!(map.remove(&1), None);
458 /// assert_eq!(map.remove(&2), Some("a"));
459 /// assert_eq!(map.remove(&2), None);
460 /// assert_eq!(map.len(), 0);
461 /// ```
462 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
463 where
464 K: Borrow<Q>,
465 Q: Eq + Hash,
466 {
467 let removed = self.map.remove(Qey::from_ref(k));
468 removed.map(|node| {
469 self.detach(node);
470 unsafe {
471 // add to free list
472 (*node).next = self.free;
473 self.free = node;
474 // drop the key and return the value
475 drop(ptr::read(&(*node).key));
476 ptr::read(&(*node).value)
477 }
478 })
479 }
480
481 /// Returns the maximum number of key-value pairs the map can hold without reallocating.
482 ///
483 /// # Examples
484 ///
485 /// ```
486 /// use linked_hash_map::LinkedHashMap;
487 /// let mut map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
488 /// let capacity = map.capacity();
489 /// ```
490 pub fn capacity(&self) -> usize {
491 self.map.capacity()
492 }
493
494 /// Removes the first entry.
495 ///
496 /// Can be used in implementation of LRU cache.
497 ///
498 /// # Examples
499 ///
500 /// ```
501 /// use linked_hash_map::LinkedHashMap;
502 /// let mut map = LinkedHashMap::new();
503 /// map.insert(1, 10);
504 /// map.insert(2, 20);
505 /// map.pop_front();
506 /// assert_eq!(map.get(&1), None);
507 /// assert_eq!(map.get(&2), Some(&20));
508 /// ```
509 #[inline]
510 pub fn pop_front(&mut self) -> Option<(K, V)> {
511 if self.is_empty() {
512 return None;
513 }
514 let lru = unsafe { (*self.head).prev };
515 self.detach(lru);
516 self.map
517 .remove(&KeyRef {
518 k: unsafe { &(*lru).key },
519 })
520 .map(|e| {
521 let e = *unsafe { Box::from_raw(e) };
522 (e.key, e.value)
523 })
524 }
525
526 /// Gets the first entry.
527 ///
528 /// # Examples
529 ///
530 /// ```
531 /// use linked_hash_map::LinkedHashMap;
532 /// let mut map = LinkedHashMap::new();
533 /// map.insert(1, 10);
534 /// map.insert(2, 20);
535 /// assert_eq!(map.front(), Some((&1, &10)));
536 /// ```
537 #[inline]
538 pub fn front(&self) -> Option<(&K, &V)> {
539 if self.is_empty() {
540 return None;
541 }
542 let lru = unsafe { (*self.head).prev };
543 self.map
544 .get(&KeyRef {
545 k: unsafe { &(*lru).key },
546 })
547 .map(|e| unsafe { (&(**e).key, &(**e).value) })
548 }
549
550 /// Removes the last entry.
551 ///
552 /// # Examples
553 ///
554 /// ```
555 /// use linked_hash_map::LinkedHashMap;
556 /// let mut map = LinkedHashMap::new();
557 /// map.insert(1, 10);
558 /// map.insert(2, 20);
559 /// map.pop_back();
560 /// assert_eq!(map.get(&1), Some(&10));
561 /// assert_eq!(map.get(&2), None);
562 /// ```
563 #[inline]
564 pub fn pop_back(&mut self) -> Option<(K, V)> {
565 if self.is_empty() {
566 return None;
567 }
568 let mru = unsafe { (*self.head).next };
569 self.detach(mru);
570 self.map
571 .remove(&KeyRef {
572 k: unsafe { &(*mru).key },
573 })
574 .map(|e| {
575 let e = *unsafe { Box::from_raw(e) };
576 (e.key, e.value)
577 })
578 }
579
580 /// Gets the last entry.
581 ///
582 /// # Examples
583 ///
584 /// ```
585 /// use linked_hash_map::LinkedHashMap;
586 /// let mut map = LinkedHashMap::new();
587 /// map.insert(1, 10);
588 /// map.insert(2, 20);
589 /// assert_eq!(map.back(), Some((&2, &20)));
590 /// ```
591 #[inline]
592 pub fn back(&self) -> Option<(&K, &V)> {
593 if self.is_empty() {
594 return None;
595 }
596 let mru = unsafe { (*self.head).next };
597 self.map
598 .get(&KeyRef {
599 k: unsafe { &(*mru).key },
600 })
601 .map(|e| unsafe { (&(**e).key, &(**e).value) })
602 }
603
604 /// Returns the number of key-value pairs in the map.
605 pub fn len(&self) -> usize {
606 self.map.len()
607 }
608
609 /// Returns whether the map is currently empty.
610 pub fn is_empty(&self) -> bool {
611 self.len() == 0
612 }
613
614 /// Returns a reference to the map's hasher.
615 pub fn hasher(&self) -> &S {
616 self.map.hasher()
617 }
618
619 /// Clears the map of all key-value pairs.
620 pub fn clear(&mut self) {
621 self.map.clear();
622 // update the guard node if present
623 if !self.head.is_null() {
624 unsafe {
625 self.drop_entries();
626 (*self.head).prev = self.head;
627 (*self.head).next = self.head;
628 }
629 }
630 }
631
632 /// Returns a double-ended iterator visiting all key-value pairs in order of insertion.
633 /// Iterator element type is `(&'a K, &'a V)`
634 ///
635 /// # Examples
636 /// ```
637 /// use linked_hash_map::LinkedHashMap;
638 ///
639 /// let mut map = LinkedHashMap::new();
640 /// map.insert("a", 10);
641 /// map.insert("c", 30);
642 /// map.insert("b", 20);
643 ///
644 /// let mut iter = map.iter();
645 /// assert_eq!((&"a", &10), iter.next().unwrap());
646 /// assert_eq!((&"c", &30), iter.next().unwrap());
647 /// assert_eq!((&"b", &20), iter.next().unwrap());
648 /// assert_eq!(None, iter.next());
649 /// ```
650 pub fn iter(&self) -> Iter<K, V> {
651 let head = if self.head.is_null() {
652 ptr::null_mut()
653 } else {
654 unsafe { (*self.head).prev }
655 };
656 Iter {
657 head,
658 tail: self.head,
659 remaining: self.len(),
660 marker: marker::PhantomData,
661 }
662 }
663
664 /// Returns a double-ended iterator visiting all key-value pairs in order of insertion.
665 /// Iterator element type is `(&'a K, &'a mut V)`
666 /// # Examples
667 /// ```
668 /// use linked_hash_map::LinkedHashMap;
669 ///
670 /// let mut map = LinkedHashMap::new();
671 /// map.insert("a", 10);
672 /// map.insert("c", 30);
673 /// map.insert("b", 20);
674 ///
675 /// {
676 /// let mut iter = map.iter_mut();
677 /// let mut entry = iter.next().unwrap();
678 /// assert_eq!(&"a", entry.0);
679 /// *entry.1 = 17;
680 /// }
681 ///
682 /// assert_eq!(&17, map.get(&"a").unwrap());
683 /// ```
684 pub fn iter_mut(&mut self) -> IterMut<K, V> {
685 let head = if self.head.is_null() {
686 ptr::null_mut()
687 } else {
688 unsafe { (*self.head).prev }
689 };
690 IterMut {
691 head,
692 tail: self.head,
693 remaining: self.len(),
694 marker: marker::PhantomData,
695 }
696 }
697
698 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
699 /// allocated memory for reuse.
700 ///
701 /// If the returned iterator is dropped before being fully consumed, it
702 /// drops the remaining key-value pairs. The returned iterator keeps a
703 /// mutable borrow on the vector to optimize its implementation.
704 ///
705 /// Current performance implications (why to use this over into_iter()):
706 ///
707 /// * Clears the inner HashMap instead of dropping it
708 /// * Puts all drained nodes in the free-list instead of deallocating them
709 /// * Avoids deallocating the sentinel node
710 pub fn drain(&mut self) -> Drain<K, V> {
711 let len = self.len();
712 // Map should be empty now, regardless of current state
713 self.map.clear();
714 let (head, tail) = if len != 0 {
715 // This is basically the same as IntoIter's impl, but we don't
716 // deallocate/drop anything. Instead we make the sentinel head node
717 // point at itself (same state you get from removing the last element from a map),
718 // and then append the entire list to the free list. At this point all the entries
719 // have essentially been fed into mem::forget. The Drain iterator will then iterate
720 // over those nodes in the freelist (using `len` to know where to stop) and `read`
721 // the values out of the nodes, "unforgetting" them.
722 //
723 // This design results in no observable consequences for mem::forgetting the
724 // drain iterator, because the drain iterator has no responsibility to "fix up"
725 // things during iteration/destruction. That said, you will effectively mem::forget
726 // any elements that weren't yielded yet.
727 unsafe {
728 debug_assert!(!self.head.is_null());
729 debug_assert!(!(*self.head).prev.is_null());
730 debug_assert!((*self.head).prev != self.head);
731 let head = (*self.head).prev;
732 let tail = (*self.head).next;
733 (*self.head).prev = self.head;
734 (*self.head).next = self.head;
735 (*head).next = self.free;
736 (*tail).prev = ptr::null_mut();
737 self.free = tail;
738 (head, tail)
739 }
740 } else {
741 (ptr::null_mut(), ptr::null_mut())
742 };
743
744 Drain {
745 head,
746 tail,
747 remaining: len,
748 marker: marker::PhantomData,
749 }
750 }
751
752 /// Returns a double-ended iterator visiting all key in order of insertion.
753 ///
754 /// # Examples
755 /// ```
756 /// use linked_hash_map::LinkedHashMap;
757 ///
758 /// let mut map = LinkedHashMap::new();
759 /// map.insert('a', 10);
760 /// map.insert('c', 30);
761 /// map.insert('b', 20);
762 ///
763 /// let mut keys = map.keys();
764 /// assert_eq!(&'a', keys.next().unwrap());
765 /// assert_eq!(&'c', keys.next().unwrap());
766 /// assert_eq!(&'b', keys.next().unwrap());
767 /// assert_eq!(None, keys.next());
768 /// ```
769 pub fn keys(&self) -> Keys<K, V> {
770 Keys { inner: self.iter() }
771 }
772
773 /// Returns a double-ended iterator visiting all values in order of insertion.
774 ///
775 /// # Examples
776 /// ```
777 /// use linked_hash_map::LinkedHashMap;
778 ///
779 /// let mut map = LinkedHashMap::new();
780 /// map.insert('a', 10);
781 /// map.insert('c', 30);
782 /// map.insert('b', 20);
783 ///
784 /// let mut values = map.values();
785 /// assert_eq!(&10, values.next().unwrap());
786 /// assert_eq!(&30, values.next().unwrap());
787 /// assert_eq!(&20, values.next().unwrap());
788 /// assert_eq!(None, values.next());
789 /// ```
790 pub fn values(&self) -> Values<K, V> {
791 Values { inner: self.iter() }
792 }
793}
794
795impl<'a, K, V, S, Q: ?Sized> Index<&'a Q> for LinkedHashMap<K, V, S>
796where
797 K: Hash + Eq + Borrow<Q>,
798 S: BuildHasher,
799 Q: Eq + Hash,
800{
801 type Output = V;
802
803 fn index(&self, index: &'a Q) -> &V {
804 self.get(index).expect(msg:"no entry found for key")
805 }
806}
807
808impl<'a, K, V, S, Q: ?Sized> IndexMut<&'a Q> for LinkedHashMap<K, V, S>
809where
810 K: Hash + Eq + Borrow<Q>,
811 S: BuildHasher,
812 Q: Eq + Hash,
813{
814 fn index_mut(&mut self, index: &'a Q) -> &mut V {
815 self.get_mut(index).expect(msg:"no entry found for key")
816 }
817}
818
819impl<K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone> Clone for LinkedHashMap<K, V, S> {
820 fn clone(&self) -> Self {
821 let mut map: LinkedHashMap = Self::with_hasher(self.map.hasher().clone());
822 map.extend(self.iter().map(|(k: &K, v: &V)| (k.clone(), v.clone())));
823 map
824 }
825}
826
827impl<K: Hash + Eq, V, S: BuildHasher + Default> Default for LinkedHashMap<K, V, S> {
828 fn default() -> Self {
829 Self::with_hasher(S::default())
830 }
831}
832
833impl<K: Hash + Eq, V, S: BuildHasher> Extend<(K, V)> for LinkedHashMap<K, V, S> {
834 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
835 for (k: K, v: V) in iter {
836 self.insert(k, v);
837 }
838 }
839}
840
841impl<'a, K, V, S> Extend<(&'a K, &'a V)> for LinkedHashMap<K, V, S>
842where
843 K: 'a + Hash + Eq + Copy,
844 V: 'a + Copy,
845 S: BuildHasher,
846{
847 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
848 for (&k: K, &v: V) in iter {
849 self.insert(k, v);
850 }
851 }
852}
853
854impl<K: Hash + Eq, V, S: BuildHasher + Default> iter::FromIterator<(K, V)>
855 for LinkedHashMap<K, V, S>
856{
857 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
858 let iter: ::IntoIter = iter.into_iter();
859 let mut map: LinkedHashMap = Self::with_capacity_and_hasher(capacity:iter.size_hint().0, S::default());
860 map.extend(iter);
861 map
862 }
863}
864
865impl<A: fmt::Debug + Hash + Eq, B: fmt::Debug, S: BuildHasher> fmt::Debug
866 for LinkedHashMap<A, B, S>
867{
868 /// Returns a string that lists the key-value pairs in insertion order.
869 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
870 f.debug_map().entries(self).finish()
871 }
872}
873
874impl<K: Hash + Eq, V: PartialEq, S: BuildHasher> PartialEq for LinkedHashMap<K, V, S> {
875 fn eq(&self, other: &Self) -> bool {
876 self.len() == other.len() && self.iter().eq(other)
877 }
878}
879
880impl<K: Hash + Eq, V: Eq, S: BuildHasher> Eq for LinkedHashMap<K, V, S> {}
881
882impl<K: Hash + Eq + PartialOrd, V: PartialOrd, S: BuildHasher> PartialOrd
883 for LinkedHashMap<K, V, S>
884{
885 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
886 self.iter().partial_cmp(other)
887 }
888
889 fn lt(&self, other: &Self) -> bool {
890 self.iter().lt(other)
891 }
892
893 fn le(&self, other: &Self) -> bool {
894 self.iter().le(other)
895 }
896
897 fn ge(&self, other: &Self) -> bool {
898 self.iter().ge(other)
899 }
900
901 fn gt(&self, other: &Self) -> bool {
902 self.iter().gt(other)
903 }
904}
905
906impl<K: Hash + Eq + Ord, V: Ord, S: BuildHasher> Ord for LinkedHashMap<K, V, S> {
907 fn cmp(&self, other: &Self) -> Ordering {
908 self.iter().cmp(other)
909 }
910}
911
912impl<K: Hash + Eq, V: Hash, S: BuildHasher> Hash for LinkedHashMap<K, V, S> {
913 fn hash<H: Hasher>(&self, h: &mut H) {
914 for e: (&K, &V) in self.iter() {
915 e.hash(state:h);
916 }
917 }
918}
919
920unsafe impl<K: Send, V: Send, S: Send> Send for LinkedHashMap<K, V, S> {}
921
922unsafe impl<K: Sync, V: Sync, S: Sync> Sync for LinkedHashMap<K, V, S> {}
923
924impl<K, V, S> Drop for LinkedHashMap<K, V, S> {
925 fn drop(&mut self) {
926 if !self.head.is_null() {
927 unsafe {
928 self.drop_entries();
929 drop_empty_node(self.head);
930 }
931 }
932 self.clear_free_list();
933 }
934}
935
936/// An insertion-order iterator over a `LinkedHashMap`'s entries, with immutable references to the
937/// values.
938pub struct Iter<'a, K: 'a, V: 'a> {
939 head: *const Node<K, V>,
940 tail: *const Node<K, V>,
941 remaining: usize,
942 marker: marker::PhantomData<(&'a K, &'a V)>,
943}
944
945/// An insertion-order iterator over a `LinkedHashMap`'s entries, with mutable references to the
946/// values.
947pub struct IterMut<'a, K: 'a, V: 'a> {
948 head: *mut Node<K, V>,
949 tail: *mut Node<K, V>,
950 remaining: usize,
951 marker: marker::PhantomData<(&'a K, &'a mut V)>,
952}
953
954/// A consuming insertion-order iterator over a `LinkedHashMap`'s entries.
955pub struct IntoIter<K, V> {
956 head: *mut Node<K, V>,
957 tail: *mut Node<K, V>,
958 remaining: usize,
959 marker: marker::PhantomData<(K, V)>,
960}
961
962/// A draining insertion-order iterator over a `LinkedHashMap`'s entries.
963pub struct Drain<'a, K, V> {
964 head: *mut Node<K, V>,
965 tail: *mut Node<K, V>,
966 remaining: usize,
967 marker: marker::PhantomData<&'a mut (K, V)>,
968}
969
970/// An insertion-order iterator over a `LinkedHashMap`'s entries represented as
971/// an `OccupiedEntry`.
972pub struct Entries<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
973 map: *mut LinkedHashMap<K, V, S>,
974 head: *mut Node<K, V>,
975 remaining: usize,
976 marker: marker::PhantomData<(&'a K, &'a mut V, &'a S)>,
977}
978
979unsafe impl<'a, K, V> Send for Iter<'a, K, V>
980where
981 K: Send,
982 V: Send,
983{
984}
985
986unsafe impl<'a, K, V> Send for IterMut<'a, K, V>
987where
988 K: Send,
989 V: Send,
990{
991}
992
993unsafe impl<'a, K, V> Send for Drain<'a, K, V>
994where
995 K: Send,
996 V: Send,
997{
998}
999
1000unsafe impl<K, V> Send for IntoIter<K, V>
1001where
1002 K: Send,
1003 V: Send,
1004{
1005}
1006
1007unsafe impl<'a, K, V, S> Send for Entries<'a, K, V, S>
1008where
1009 K: Send,
1010 V: Send,
1011 S: Send,
1012{
1013}
1014
1015unsafe impl<'a, K, V> Sync for Iter<'a, K, V>
1016where
1017 K: Sync,
1018 V: Sync,
1019{
1020}
1021
1022unsafe impl<'a, K, V> Sync for IterMut<'a, K, V>
1023where
1024 K: Sync,
1025 V: Sync,
1026{
1027}
1028
1029unsafe impl<'a, K, V> Sync for Drain<'a, K, V>
1030where
1031 K: Sync,
1032 V: Sync,
1033{
1034}
1035unsafe impl<K, V> Sync for IntoIter<K, V>
1036where
1037 K: Sync,
1038 V: Sync,
1039{
1040}
1041
1042unsafe impl<'a, K, V, S> Sync for Entries<'a, K, V, S>
1043where
1044 K: Sync,
1045 V: Sync,
1046 S: Sync,
1047{
1048}
1049
1050impl<'a, K, V> Clone for Iter<'a, K, V> {
1051 fn clone(&self) -> Self {
1052 Iter { ..*self }
1053 }
1054}
1055
1056impl<K, V> Clone for IntoIter<K, V>
1057where
1058 K: Clone,
1059 V: Clone,
1060{
1061 fn clone(&self) -> Self {
1062 if self.remaining == 0 {
1063 return IntoIter { ..*self };
1064 }
1065
1066 fn clone_node<K, V>(e: *mut Node<K, V>) -> *mut Node<K, V>
1067 where
1068 K: Clone,
1069 V: Clone,
1070 {
1071 Box::into_raw(Box::new(Node::new(unsafe { (*e).key.clone() }, unsafe {
1072 (*e).value.clone()
1073 })))
1074 }
1075
1076 let mut cur = self.head;
1077 let head = clone_node(cur);
1078 let mut tail = head;
1079 for _ in 1..self.remaining {
1080 unsafe {
1081 (*tail).prev = clone_node((*cur).prev);
1082 (*(*tail).prev).next = tail;
1083 tail = (*tail).prev;
1084 cur = (*cur).prev;
1085 }
1086 }
1087
1088 IntoIter {
1089 head,
1090 tail,
1091 remaining: self.remaining,
1092 marker: marker::PhantomData,
1093 }
1094 }
1095}
1096
1097impl<'a, K, V> Iterator for Iter<'a, K, V> {
1098 type Item = (&'a K, &'a V);
1099
1100 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1101 if self.head == self.tail {
1102 None
1103 } else {
1104 self.remaining -= 1;
1105 unsafe {
1106 let r: Option<(&K, &V)> = Some((&(*self.head).key, &(*self.head).value));
1107 self.head = (*self.head).prev;
1108 r
1109 }
1110 }
1111 }
1112
1113 fn size_hint(&self) -> (usize, Option<usize>) {
1114 (self.remaining, Some(self.remaining))
1115 }
1116}
1117
1118impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1119 type Item = (&'a K, &'a mut V);
1120
1121 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1122 if self.head == self.tail {
1123 None
1124 } else {
1125 self.remaining -= 1;
1126 unsafe {
1127 let r: Option<(&K, &mut V)> = Some((&(*self.head).key, &mut (*self.head).value));
1128 self.head = (*self.head).prev;
1129 r
1130 }
1131 }
1132 }
1133
1134 fn size_hint(&self) -> (usize, Option<usize>) {
1135 (self.remaining, Some(self.remaining))
1136 }
1137}
1138
1139impl<K, V> Iterator for IntoIter<K, V> {
1140 type Item = (K, V);
1141
1142 fn next(&mut self) -> Option<(K, V)> {
1143 if self.remaining == 0 {
1144 return None;
1145 }
1146 self.remaining -= 1;
1147 unsafe {
1148 let prev: *mut Node = (*self.head).prev;
1149 let e: Node = *Box::from_raw(self.head);
1150 self.head = prev;
1151 Some((e.key, e.value))
1152 }
1153 }
1154
1155 fn size_hint(&self) -> (usize, Option<usize>) {
1156 (self.remaining, Some(self.remaining))
1157 }
1158}
1159
1160impl<'a, K, V> Iterator for Drain<'a, K, V> {
1161 type Item = (K, V);
1162
1163 fn next(&mut self) -> Option<(K, V)> {
1164 if self.remaining == 0 {
1165 return None;
1166 }
1167 self.remaining -= 1;
1168 unsafe {
1169 let prev: *mut Node = (*self.head).prev;
1170 // Read the values out, the node is in the free-list already so these will
1171 // be treated as uninit memory.
1172 let k: K = addr_of_mut!((*self.head).key).read();
1173 let v: V = addr_of_mut!((*self.head).value).read();
1174 self.head = prev;
1175 Some((k, v))
1176 }
1177 }
1178
1179 fn size_hint(&self) -> (usize, Option<usize>) {
1180 (self.remaining, Some(self.remaining))
1181 }
1182}
1183
1184impl<'a, K, V> DoubleEndedIterator for Drain<'a, K, V> {
1185 fn next_back(&mut self) -> Option<(K, V)> {
1186 if self.remaining == 0 {
1187 return None;
1188 }
1189 self.remaining -= 1;
1190 unsafe {
1191 let next: *mut Node = (*self.tail).next;
1192 // Read the values out, the node is in the free-list already so these will
1193 // be treated as uninit memory.
1194 let k: K = addr_of_mut!((*self.tail).key).read();
1195 let v: V = addr_of_mut!((*self.tail).value).read();
1196 self.tail = next;
1197 Some((k, v))
1198 }
1199 }
1200}
1201
1202impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1203 fn len(&self) -> usize {
1204 self.remaining
1205 }
1206}
1207
1208impl<'a, K, V, S: BuildHasher> Iterator for Entries<'a, K, V, S> {
1209 type Item = OccupiedEntry<'a, K, V, S>;
1210
1211 fn next(&mut self) -> Option<OccupiedEntry<'a, K, V, S>> {
1212 if self.remaining == 0 {
1213 None
1214 } else {
1215 self.remaining -= 1;
1216 unsafe {
1217 let r = Some(OccupiedEntry {
1218 map: self.map,
1219 entry: self.head,
1220 marker: marker::PhantomData,
1221 });
1222
1223 self.head = (*self.head).prev;
1224 r
1225 }
1226 }
1227 }
1228
1229 fn size_hint(&self) -> (usize, Option<usize>) {
1230 (self.remaining, Some(self.remaining))
1231 }
1232}
1233
1234impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
1235 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1236 if self.head == self.tail {
1237 None
1238 } else {
1239 self.remaining -= 1;
1240 unsafe {
1241 self.tail = (*self.tail).next;
1242 Some((&(*self.tail).key, &(*self.tail).value))
1243 }
1244 }
1245 }
1246}
1247
1248impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1249 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1250 if self.head == self.tail {
1251 None
1252 } else {
1253 self.remaining -= 1;
1254 unsafe {
1255 self.tail = (*self.tail).next;
1256 Some((&(*self.tail).key, &mut (*self.tail).value))
1257 }
1258 }
1259 }
1260}
1261
1262impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1263 fn next_back(&mut self) -> Option<(K, V)> {
1264 if self.remaining == 0 {
1265 return None;
1266 }
1267 self.remaining -= 1;
1268 unsafe {
1269 let next: *mut Node = (*self.tail).next;
1270 let e: Node = *Box::from_raw(self.tail);
1271 self.tail = next;
1272 Some((e.key, e.value))
1273 }
1274 }
1275}
1276
1277impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
1278 fn len(&self) -> usize {
1279 self.remaining
1280 }
1281}
1282
1283impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1284 fn len(&self) -> usize {
1285 self.remaining
1286 }
1287}
1288
1289impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1290 fn len(&self) -> usize {
1291 self.remaining
1292 }
1293}
1294
1295impl<K, V> Drop for IntoIter<K, V> {
1296 fn drop(&mut self) {
1297 for _ in 0..self.remaining {
1298 unsafe {
1299 let next: *mut Node = (*self.tail).next;
1300 Box::from_raw(self.tail);
1301 self.tail = next;
1302 }
1303 }
1304 }
1305}
1306
1307impl<'a, K, V> Drop for Drain<'a, K, V> {
1308 fn drop(&mut self) {
1309 for _ in self {}
1310 }
1311}
1312
1313/// An insertion-order iterator over a `LinkedHashMap`'s keys.
1314pub struct Keys<'a, K: 'a, V: 'a> {
1315 inner: Iter<'a, K, V>,
1316}
1317
1318impl<'a, K, V> Clone for Keys<'a, K, V> {
1319 fn clone(&self) -> Self {
1320 Keys {
1321 inner: self.inner.clone(),
1322 }
1323 }
1324}
1325
1326impl<'a, K, V> Iterator for Keys<'a, K, V> {
1327 type Item = &'a K;
1328
1329 #[inline]
1330 fn next(&mut self) -> Option<&'a K> {
1331 self.inner.next().map(|e: (&'a K, &'a V)| e.0)
1332 }
1333 #[inline]
1334 fn size_hint(&self) -> (usize, Option<usize>) {
1335 self.inner.size_hint()
1336 }
1337}
1338
1339impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1340 #[inline]
1341 fn next_back(&mut self) -> Option<&'a K> {
1342 self.inner.next_back().map(|e: (&'a K, &'a V)| e.0)
1343 }
1344}
1345
1346impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1347 fn len(&self) -> usize {
1348 self.inner.len()
1349 }
1350}
1351
1352/// An insertion-order iterator over a `LinkedHashMap`'s values.
1353pub struct Values<'a, K: 'a, V: 'a> {
1354 inner: Iter<'a, K, V>,
1355}
1356
1357impl<'a, K, V> Clone for Values<'a, K, V> {
1358 fn clone(&self) -> Self {
1359 Values {
1360 inner: self.inner.clone(),
1361 }
1362 }
1363}
1364
1365impl<'a, K, V> Iterator for Values<'a, K, V> {
1366 type Item = &'a V;
1367
1368 #[inline]
1369 fn next(&mut self) -> Option<&'a V> {
1370 self.inner.next().map(|e: (&'a K, &'a V)| e.1)
1371 }
1372 #[inline]
1373 fn size_hint(&self) -> (usize, Option<usize>) {
1374 self.inner.size_hint()
1375 }
1376}
1377
1378impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1379 #[inline]
1380 fn next_back(&mut self) -> Option<&'a V> {
1381 self.inner.next_back().map(|e: (&'a K, &'a V)| e.1)
1382 }
1383}
1384
1385impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1386 fn len(&self) -> usize {
1387 self.inner.len()
1388 }
1389}
1390
1391impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a LinkedHashMap<K, V, S> {
1392 type Item = (&'a K, &'a V);
1393 type IntoIter = Iter<'a, K, V>;
1394 fn into_iter(self) -> Iter<'a, K, V> {
1395 self.iter()
1396 }
1397}
1398
1399impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a mut LinkedHashMap<K, V, S> {
1400 type Item = (&'a K, &'a mut V);
1401 type IntoIter = IterMut<'a, K, V>;
1402 fn into_iter(self) -> IterMut<'a, K, V> {
1403 self.iter_mut()
1404 }
1405}
1406
1407impl<K: Hash + Eq, V, S: BuildHasher> IntoIterator for LinkedHashMap<K, V, S> {
1408 type Item = (K, V);
1409 type IntoIter = IntoIter<K, V>;
1410 fn into_iter(mut self) -> IntoIter<K, V> {
1411 let (head, tail) = if !self.head.is_null() {
1412 unsafe { ((*self.head).prev, (*self.head).next) }
1413 } else {
1414 (ptr::null_mut(), ptr::null_mut())
1415 };
1416 let len = self.len();
1417
1418 if !self.head.is_null() {
1419 unsafe { drop_empty_node(self.head) }
1420 }
1421 self.clear_free_list();
1422 // drop the HashMap but not the LinkedHashMap
1423 unsafe {
1424 ptr::drop_in_place(&mut self.map);
1425 }
1426 mem::forget(self);
1427
1428 IntoIter {
1429 head,
1430 tail,
1431 remaining: len,
1432 marker: marker::PhantomData,
1433 }
1434 }
1435}
1436
1437/// A view into a single location in a map, which may be vacant or occupied.
1438pub enum Entry<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
1439 /// An occupied Entry.
1440 Occupied(OccupiedEntry<'a, K, V, S>),
1441 /// A vacant Entry.
1442 Vacant(VacantEntry<'a, K, V, S>),
1443}
1444
1445/// A view into a single occupied location in a `LinkedHashMap`.
1446pub struct OccupiedEntry<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
1447 entry: *mut Node<K, V>,
1448 map: *mut LinkedHashMap<K, V, S>,
1449 marker: marker::PhantomData<&'a K>,
1450}
1451
1452/// A view into a single empty location in a `LinkedHashMap`.
1453pub struct VacantEntry<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
1454 key: K,
1455 map: &'a mut LinkedHashMap<K, V, S>,
1456}
1457
1458impl<'a, K: Hash + Eq, V, S: BuildHasher> Entry<'a, K, V, S> {
1459 /// Returns the entry key
1460 ///
1461 /// # Examples
1462 ///
1463 /// ```
1464 /// use linked_hash_map::LinkedHashMap;
1465 ///
1466 /// let mut map = LinkedHashMap::<String, u32>::new();
1467 ///
1468 /// assert_eq!("hello", map.entry("hello".to_string()).key());
1469 /// ```
1470 pub fn key(&self) -> &K {
1471 match *self {
1472 Entry::Occupied(ref e) => e.key(),
1473 Entry::Vacant(ref e) => e.key(),
1474 }
1475 }
1476
1477 /// Ensures a value is in the entry by inserting the default if empty, and returns
1478 /// a mutable reference to the value in the entry.
1479 pub fn or_insert(self, default: V) -> &'a mut V {
1480 match self {
1481 Entry::Occupied(entry) => entry.into_mut(),
1482 Entry::Vacant(entry) => entry.insert(default),
1483 }
1484 }
1485
1486 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1487 /// and returns a mutable reference to the value in the entry.
1488 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1489 match self {
1490 Entry::Occupied(entry) => entry.into_mut(),
1491 Entry::Vacant(entry) => entry.insert(default()),
1492 }
1493 }
1494
1495 /// Provides in-place mutable access to an occupied entry before any
1496 /// potential inserts into the map.
1497 pub fn and_modify<F>(self, f: F) -> Self
1498 where
1499 F: FnOnce(&mut V),
1500 {
1501 match self {
1502 Entry::Occupied(mut entry) => {
1503 f(entry.get_mut());
1504 Entry::Occupied(entry)
1505 }
1506 Entry::Vacant(entry) => Entry::Vacant(entry),
1507 }
1508 }
1509
1510 /// Ensures a value is in the entry by inserting the default value if empty,
1511 /// and returns a mutable reference to the value in the entry.
1512 pub fn or_default(self) -> &'a mut V
1513 where
1514 V: Default,
1515 {
1516 match self {
1517 Entry::Occupied(entry) => entry.into_mut(),
1518 Entry::Vacant(entry) => entry.insert(V::default()),
1519 }
1520 }
1521}
1522
1523impl<'a, K: Hash + Eq, V, S: BuildHasher> OccupiedEntry<'a, K, V, S> {
1524 /// Gets a reference to the entry key
1525 ///
1526 /// # Examples
1527 ///
1528 /// ```
1529 /// use linked_hash_map::LinkedHashMap;
1530 ///
1531 /// let mut map = LinkedHashMap::new();
1532 ///
1533 /// map.insert("foo".to_string(), 1);
1534 /// assert_eq!("foo", map.entry("foo".to_string()).key());
1535 /// ```
1536 pub fn key(&self) -> &K {
1537 unsafe { &(*self.entry).key }
1538 }
1539
1540 /// Gets a reference to the value in the entry.
1541 pub fn get(&self) -> &V {
1542 unsafe { &(*self.entry).value }
1543 }
1544
1545 /// Gets a mutable reference to the value in the entry.
1546 pub fn get_mut(&mut self) -> &mut V {
1547 unsafe { &mut (*self.entry).value }
1548 }
1549
1550 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1551 /// with a lifetime bound to the map itself
1552 pub fn into_mut(self) -> &'a mut V {
1553 unsafe { &mut (*self.entry).value }
1554 }
1555
1556 /// Sets the value of the entry, and returns the entry's old value
1557 pub fn insert(&mut self, value: V) -> V {
1558 unsafe {
1559 (*self.map).ensure_guard_node();
1560
1561 let old_val = mem::replace(&mut (*self.entry).value, value);
1562 let node_ptr: *mut Node<K, V> = self.entry;
1563
1564 // Existing node, just update LRU position
1565 (*self.map).detach(node_ptr);
1566 (*self.map).attach(node_ptr);
1567
1568 old_val
1569 }
1570 }
1571
1572 /// Takes the value out of the entry, and returns it
1573 pub fn remove(self) -> V {
1574 unsafe { (*self.map).remove(&(*self.entry).key) }.unwrap()
1575 }
1576}
1577
1578impl<'a, K: 'a + Hash + Eq, V: 'a, S: BuildHasher> VacantEntry<'a, K, V, S> {
1579 /// Gets a reference to the entry key
1580 ///
1581 /// # Examples
1582 ///
1583 /// ```
1584 /// use linked_hash_map::LinkedHashMap;
1585 ///
1586 /// let mut map = LinkedHashMap::<String, u32>::new();
1587 ///
1588 /// assert_eq!("foo", map.entry("foo".to_string()).key());
1589 /// ```
1590 pub fn key(&self) -> &K {
1591 &self.key
1592 }
1593
1594 /// Sets the value of the entry with the VacantEntry's key,
1595 /// and returns a mutable reference to it
1596 pub fn insert(self, value: V) -> &'a mut V {
1597 self.map.ensure_guard_node();
1598
1599 let node = if self.map.free.is_null() {
1600 Box::into_raw(Box::new(Node::new(self.key, value)))
1601 } else {
1602 // use a recycled box
1603 unsafe {
1604 let free = self.map.free;
1605 self.map.free = (*free).next;
1606 ptr::write(free, Node::new(self.key, value));
1607 free
1608 }
1609 };
1610
1611 let keyref = unsafe { &(*node).key };
1612
1613 self.map.attach(node);
1614
1615 let ret = self.map.map.entry(KeyRef { k: keyref }).or_insert(node);
1616 unsafe { &mut (**ret).value }
1617 }
1618}
1619