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 #![cfg_attr(feature = "clippy", feature(plugin))]
34 #![cfg_attr(feature = "clippy", plugin(clippy))]
35 #![cfg_attr(feature = "clippy", deny(clippy))]
36
37 // Optional Serde support
38 #[cfg(feature = "serde_impl")]
39 pub mod serde;
40 // Optional Heapsize support
41 #[cfg(feature = "heapsize_impl")]
42 mod heapsize;
43
44 use std::borrow::Borrow;
45 use std::cmp::Ordering;
46 use std::collections::hash_map::{self, HashMap};
47 use std::fmt;
48 use std::hash::{BuildHasher, Hash, Hasher};
49 use std::iter;
50 use std::marker;
51 use std::mem;
52 use std::ops::{Index, IndexMut};
53 use std::ptr;
54
55 struct KeyRef<K> { k: *const K }
56
57 struct 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.
65 pub 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
71 impl<K: Hash> Hash for KeyRef<K> {
hash<H: Hasher>(&self, state: &mut H)72 fn hash<H: Hasher>(&self, state: &mut H) {
73 unsafe { (*self.k).hash(state) }
74 }
75 }
76
77 impl<K: PartialEq> PartialEq for KeyRef<K> {
eq(&self, other: &Self) -> bool78 fn eq(&self, other: &Self) -> bool {
79 unsafe{ (*self.k).eq(&*other.k) }
80 }
81 }
82
83 impl<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)]
90 struct Qey<Q: ?Sized>(Q);
91
92 impl<Q: ?Sized> Qey<Q> {
from_ref(q: &Q) -> &Self93 fn from_ref(q: &Q) -> &Self { unsafe { mem::transmute(q) } }
94 }
95
96 impl<K, Q: ?Sized> Borrow<Qey<Q>> for KeyRef<K> where K: Borrow<Q> {
borrow(&self) -> &Qey<Q>97 fn borrow(&self) -> &Qey<Q> {
98 Qey::from_ref(unsafe { (*self.k).borrow() })
99 }
100 }
101
102 impl<K, V> Node<K, V> {
new(k: K, v: V) -> Self103 fn new(k: K, v: V) -> Self {
104 Node {
105 key: k,
106 value: v,
107 next: ptr::null_mut(),
108 prev: ptr::null_mut(),
109 }
110 }
111 }
112
113 // drop empty node without dropping its key and value
drop_empty_node<K, V>(the_box: *mut Node<K, V>)114 unsafe fn drop_empty_node<K, V>(the_box: *mut Node<K, V>) {
115 // Safety:
116 // In this crate all `Node` is allocated via `Box` or `alloc`, and `Box` uses the
117 // Global allocator for its allocation,
118 // (https://doc.rust-lang.org/std/boxed/index.html#memory-layout) so we can safely
119 // deallocate the pointer to `Node` by calling `dealloc` method
120 let layout = std::alloc::Layout::new::<Node<K, V>>();
121 std::alloc::dealloc(the_box as *mut u8, layout);
122 }
123
124 impl<K: Hash + Eq, V> LinkedHashMap<K, V> {
125 /// Creates a linked hash map.
new() -> Self126 pub fn new() -> Self { Self::with_map(HashMap::new()) }
127
128 /// Creates an empty linked hash map with the given initial capacity.
with_capacity(capacity: usize) -> Self129 pub fn with_capacity(capacity: usize) -> Self {
130 Self::with_map(HashMap::with_capacity(capacity))
131 }
132 }
133
134 impl<K, V, S> LinkedHashMap<K, V, S> {
135 #[inline]
detach(&mut self, node: *mut Node<K, V>)136 fn detach(&mut self, node: *mut Node<K, V>) {
137 unsafe {
138 (*(*node).prev).next = (*node).next;
139 (*(*node).next).prev = (*node).prev;
140 }
141 }
142
143 #[inline]
attach(&mut self, node: *mut Node<K, V>)144 fn attach(&mut self, node: *mut Node<K, V>) {
145 unsafe {
146 (*node).next = (*self.head).next;
147 (*node).prev = self.head;
148 (*self.head).next = node;
149 (*(*node).next).prev = node;
150 }
151 }
152
153 // Caller must check `!self.head.is_null()`
drop_entries(&mut self)154 unsafe fn drop_entries(&mut self) {
155 let mut cur = (*self.head).next;
156 while cur != self.head {
157 let next = (*cur).next;
158 Box::from_raw(cur);
159 cur = next;
160 }
161 }
162
clear_free_list(&mut self)163 fn clear_free_list(&mut self) {
164 unsafe {
165 let mut free = self.free;
166 while ! free.is_null() {
167 let next_free = (*free).next;
168 drop_empty_node(free);
169 free = next_free;
170 }
171 self.free = ptr::null_mut();
172 }
173 }
174
ensure_guard_node(&mut self)175 fn ensure_guard_node(&mut self) {
176 if self.head.is_null() {
177 // allocate the guard node if not present
178 unsafe {
179 let node_layout = std::alloc::Layout::new::<Node<K, V>>();
180 self.head = std::alloc::alloc(node_layout) as *mut Node<K, V>;
181 (*self.head).next = self.head;
182 (*self.head).prev = self.head;
183 }
184 }
185 }
186 }
187
188 impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
with_map(map: HashMap<KeyRef<K>, *mut Node<K, V>, S>) -> Self189 fn with_map(map: HashMap<KeyRef<K>, *mut Node<K, V>, S>) -> Self {
190 LinkedHashMap {
191 map: map,
192 head: ptr::null_mut(),
193 free: ptr::null_mut(),
194 }
195 }
196
197 /// Creates an empty linked hash map with the given initial hash builder.
with_hasher(hash_builder: S) -> Self198 pub fn with_hasher(hash_builder: S) -> Self {
199 Self::with_map(HashMap::with_hasher(hash_builder))
200 }
201
202 /// Creates an empty linked hash map with the given initial capacity and hash builder.
with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self203 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
204 Self::with_map(HashMap::with_capacity_and_hasher(capacity, hash_builder))
205 }
206
207 /// Reserves capacity for at least `additional` more elements to be inserted into the map. The
208 /// map may reserve more space to avoid frequent allocations.
209 ///
210 /// # Panics
211 ///
212 /// Panics if the new allocation size overflows `usize.`
reserve(&mut self, additional: usize)213 pub fn reserve(&mut self, additional: usize) { self.map.reserve(additional); }
214
215 /// Shrinks the capacity of the map as much as possible. It will drop down as much as possible
216 /// while maintaining the internal rules and possibly leaving some space in accordance with the
217 /// resize policy.
shrink_to_fit(&mut self)218 pub fn shrink_to_fit(&mut self) {
219 self.map.shrink_to_fit();
220 self.clear_free_list();
221 }
222
223 /// Gets the given key's corresponding entry in the map for in-place manipulation.
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// use linked_hash_map::LinkedHashMap;
229 ///
230 /// let mut letters = LinkedHashMap::new();
231 ///
232 /// for ch in "a short treatise on fungi".chars() {
233 /// let counter = letters.entry(ch).or_insert(0);
234 /// *counter += 1;
235 /// }
236 ///
237 /// assert_eq!(letters[&'s'], 2);
238 /// assert_eq!(letters[&'t'], 3);
239 /// assert_eq!(letters[&'u'], 1);
240 /// assert_eq!(letters.get(&'y'), None);
241 /// ```
entry(&mut self, k: K) -> Entry<K, V, S>242 pub fn entry(&mut self, k: K) -> Entry<K, V, S> {
243 let self_ptr: *mut Self = self;
244
245 if let Some(entry) = self.map.get_mut(&KeyRef{k: &k}) {
246 return Entry::Occupied(OccupiedEntry {
247 entry: *entry,
248 map: self_ptr,
249 marker: marker::PhantomData,
250 });
251 }
252
253 Entry::Vacant(VacantEntry {
254 key: k,
255 map: self,
256 })
257 }
258
259 /// Returns an iterator visiting all entries in insertion order.
260 /// Iterator element type is `OccupiedEntry<K, V, S>`. Allows for removal
261 /// as well as replacing the entry.
262 ///
263 /// # Examples
264 /// ```
265 /// use linked_hash_map::LinkedHashMap;
266 ///
267 /// let mut map = LinkedHashMap::new();
268 /// map.insert("a", 10);
269 /// map.insert("c", 30);
270 /// map.insert("b", 20);
271 ///
272 /// {
273 /// let mut iter = map.entries();
274 /// let mut entry = iter.next().unwrap();
275 /// assert_eq!(&"a", entry.key());
276 /// *entry.get_mut() = 17;
277 /// }
278 ///
279 /// assert_eq!(&17, map.get(&"a").unwrap());
280 /// ```
entries(&mut self) -> Entries<K, V, S>281 pub fn entries(&mut self) -> Entries<K, V, S> {
282 let head = if ! self.head.is_null() {
283 unsafe { (*self.head).prev }
284 } else {
285 ptr::null_mut()
286 };
287 Entries {
288 map: self,
289 head: head,
290 remaining: self.len(),
291 marker: marker::PhantomData,
292 }
293 }
294
295 /// Inserts a key-value pair into the map. If the key already existed, the old value is
296 /// returned.
297 ///
298 /// # Examples
299 ///
300 /// ```
301 /// use linked_hash_map::LinkedHashMap;
302 /// let mut map = LinkedHashMap::new();
303 ///
304 /// map.insert(1, "a");
305 /// map.insert(2, "b");
306 /// assert_eq!(map[&1], "a");
307 /// assert_eq!(map[&2], "b");
308 /// ```
insert(&mut self, k: K, v: V) -> Option<V>309 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
310 self.ensure_guard_node();
311
312 let (node, old_val) = match self.map.get(&KeyRef{k: &k}) {
313 Some(node) => {
314 let old_val = unsafe { ptr::replace(&mut (**node).value, v) };
315 (*node, Some(old_val))
316 }
317 None => {
318 let node = if self.free.is_null() {
319 Box::into_raw(Box::new(Node::new(k, v)))
320 } else {
321 // use a recycled box
322 unsafe {
323 let free = self.free;
324 self.free = (*free).next;
325 ptr::write(free, Node::new(k, v));
326 free
327 }
328 };
329 (node, None)
330 }
331 };
332 match old_val {
333 Some(_) => {
334 // Existing node, just update LRU position
335 self.detach(node);
336 self.attach(node);
337 }
338 None => {
339 let keyref = unsafe { &(*node).key };
340 self.map.insert(KeyRef{k: keyref}, node);
341 self.attach(node);
342 }
343 }
344 old_val
345 }
346
347 /// Checks if the map contains the given key.
contains_key<Q: ?Sized>(&self, k: &Q) -> bool where K: Borrow<Q>, Q: Eq + Hash348 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool where K: Borrow<Q>, Q: Eq + Hash {
349 self.map.contains_key(Qey::from_ref(k))
350 }
351
352 /// Returns the value corresponding to the key in the map.
353 ///
354 /// # Examples
355 ///
356 /// ```
357 /// use linked_hash_map::LinkedHashMap;
358 /// let mut map = LinkedHashMap::new();
359 ///
360 /// map.insert(1, "a");
361 /// map.insert(2, "b");
362 /// map.insert(2, "c");
363 /// map.insert(3, "d");
364 ///
365 /// assert_eq!(map.get(&1), Some(&"a"));
366 /// assert_eq!(map.get(&2), Some(&"c"));
367 /// ```
get<Q: ?Sized>(&self, k: &Q) -> Option<&V> where K: Borrow<Q>, Q: Eq + Hash368 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> where K: Borrow<Q>, Q: Eq + Hash {
369 self.map.get(Qey::from_ref(k)).map(|e| unsafe { &(**e).value })
370 }
371
372 /// Returns the mutable reference corresponding to the key in the map.
373 ///
374 /// # Examples
375 ///
376 /// ```
377 /// use linked_hash_map::LinkedHashMap;
378 /// let mut map = LinkedHashMap::new();
379 ///
380 /// map.insert(1, "a");
381 /// map.insert(2, "b");
382 ///
383 /// *map.get_mut(&1).unwrap() = "c";
384 /// assert_eq!(map.get(&1), Some(&"c"));
385 /// ```
get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash386 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash {
387 self.map.get(Qey::from_ref(k)).map(|e| unsafe { &mut (**e).value })
388 }
389
390 /// Returns the value corresponding to the key in the map.
391 ///
392 /// If value is found, it is moved to the end of the list.
393 /// This operation can be used in implemenation of LRU cache.
394 ///
395 /// # Examples
396 ///
397 /// ```
398 /// use linked_hash_map::LinkedHashMap;
399 /// let mut map = LinkedHashMap::new();
400 ///
401 /// map.insert(1, "a");
402 /// map.insert(2, "b");
403 /// map.insert(3, "d");
404 ///
405 /// assert_eq!(map.get_refresh(&2), Some(&mut "b"));
406 ///
407 /// assert_eq!((&2, &"b"), map.iter().rev().next().unwrap());
408 /// ```
get_refresh<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash409 pub fn get_refresh<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash {
410 let (value, node_ptr_opt) = match self.map.get(Qey::from_ref(k)) {
411 None => (None, None),
412 Some(node) => {
413 (Some(unsafe { &mut (**node).value }), Some(*node))
414 }
415 };
416 if let Some(node_ptr) = node_ptr_opt {
417 self.detach(node_ptr);
418 self.attach(node_ptr);
419 }
420 value
421 }
422
423 /// Removes and returns the value corresponding to the key from the map.
424 ///
425 /// # Examples
426 ///
427 /// ```
428 /// use linked_hash_map::LinkedHashMap;
429 /// let mut map = LinkedHashMap::new();
430 ///
431 /// map.insert(2, "a");
432 ///
433 /// assert_eq!(map.remove(&1), None);
434 /// assert_eq!(map.remove(&2), Some("a"));
435 /// assert_eq!(map.remove(&2), None);
436 /// assert_eq!(map.len(), 0);
437 /// ```
remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> where K: Borrow<Q>, Q: Eq + Hash438 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> where K: Borrow<Q>, Q: Eq + Hash {
439 let removed = self.map.remove(Qey::from_ref(k));
440 removed.map(|node| {
441 self.detach(node);
442 unsafe {
443 // add to free list
444 (*node).next = self.free;
445 self.free = node;
446 // drop the key and return the value
447 drop(ptr::read(&(*node).key));
448 ptr::read(&(*node).value)
449 }
450 })
451 }
452
453 /// Returns the maximum number of key-value pairs the map can hold without reallocating.
454 ///
455 /// # Examples
456 ///
457 /// ```
458 /// use linked_hash_map::LinkedHashMap;
459 /// let mut map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
460 /// let capacity = map.capacity();
461 /// ```
capacity(&self) -> usize462 pub fn capacity(&self) -> usize {
463 self.map.capacity()
464 }
465
466 /// Removes the first entry.
467 ///
468 /// Can be used in implementation of LRU cache.
469 ///
470 /// # Examples
471 ///
472 /// ```
473 /// use linked_hash_map::LinkedHashMap;
474 /// let mut map = LinkedHashMap::new();
475 /// map.insert(1, 10);
476 /// map.insert(2, 20);
477 /// map.pop_front();
478 /// assert_eq!(map.get(&1), None);
479 /// assert_eq!(map.get(&2), Some(&20));
480 /// ```
481 #[inline]
pop_front(&mut self) -> Option<(K, V)>482 pub fn pop_front(&mut self) -> Option<(K, V)> {
483 if self.is_empty() {
484 return None
485 }
486 let lru = unsafe { (*self.head).prev };
487 self.detach(lru);
488 self.map
489 .remove(&KeyRef{k: unsafe { &(*lru).key }})
490 .map(|e| {
491 let e = *unsafe { Box::from_raw(e) };
492 (e.key, e.value)
493 })
494 }
495
496 /// Gets the first entry.
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 /// assert_eq!(map.front(), Some((&1, &10)));
506 /// ```
507 #[inline]
front(&self) -> Option<(&K, &V)>508 pub fn front(&self) -> Option<(&K, &V)> {
509 if self.is_empty() {
510 return None
511 }
512 let lru = unsafe { (*self.head).prev };
513 self.map
514 .get(&KeyRef{k: unsafe { &(*lru).key }})
515 .map(|e| unsafe { (&(**e).key, &(**e).value) })
516 }
517
518 /// Removes the last entry.
519 ///
520 /// # Examples
521 ///
522 /// ```
523 /// use linked_hash_map::LinkedHashMap;
524 /// let mut map = LinkedHashMap::new();
525 /// map.insert(1, 10);
526 /// map.insert(2, 20);
527 /// map.pop_back();
528 /// assert_eq!(map.get(&1), Some(&10));
529 /// assert_eq!(map.get(&2), None);
530 /// ```
531 #[inline]
pop_back(&mut self) -> Option<(K, V)>532 pub fn pop_back(&mut self) -> Option<(K, V)> {
533 if self.is_empty() {
534 return None
535 }
536 let mru = unsafe { (*self.head).next };
537 self.detach(mru);
538 self.map
539 .remove(&KeyRef{k: unsafe { &(*mru).key }})
540 .map(|e| {
541 let e = *unsafe { Box::from_raw(e) };
542 (e.key, e.value)
543 })
544 }
545
546 /// Gets the last entry.
547 ///
548 /// # Examples
549 ///
550 /// ```
551 /// use linked_hash_map::LinkedHashMap;
552 /// let mut map = LinkedHashMap::new();
553 /// map.insert(1, 10);
554 /// map.insert(2, 20);
555 /// assert_eq!(map.back(), Some((&2, &20)));
556 /// ```
557 #[inline]
back(&mut self) -> Option<(&K, &V)>558 pub fn back(&mut self) -> Option<(&K, &V)> {
559 if self.is_empty() {
560 return None
561 }
562 let mru = unsafe { (*self.head).next };
563 self.map
564 .get(&KeyRef{k: unsafe { &(*mru).key }})
565 .map(|e| unsafe { (&(**e).key, &(**e).value) })
566 }
567
568 /// Returns the number of key-value pairs in the map.
len(&self) -> usize569 pub fn len(&self) -> usize { self.map.len() }
570
571 /// Returns whether the map is currently empty.
is_empty(&self) -> bool572 pub fn is_empty(&self) -> bool { self.len() == 0 }
573
574 /// Returns a reference to the map's hasher.
hasher(&self) -> &S575 pub fn hasher(&self) -> &S {
576 self.map.hasher()
577 }
578
579 /// Clears the map of all key-value pairs.
clear(&mut self)580 pub fn clear(&mut self) {
581 self.map.clear();
582 // update the guard node if present
583 if ! self.head.is_null() {
584 unsafe {
585 self.drop_entries();
586 (*self.head).prev = self.head;
587 (*self.head).next = self.head;
588 }
589 }
590 }
591
592 /// Returns a double-ended iterator visiting all key-value pairs in order of insertion.
593 /// Iterator element type is `(&'a K, &'a V)`
594 ///
595 /// # Examples
596 /// ```
597 /// use linked_hash_map::LinkedHashMap;
598 ///
599 /// let mut map = LinkedHashMap::new();
600 /// map.insert("a", 10);
601 /// map.insert("c", 30);
602 /// map.insert("b", 20);
603 ///
604 /// let mut iter = map.iter();
605 /// assert_eq!((&"a", &10), iter.next().unwrap());
606 /// assert_eq!((&"c", &30), iter.next().unwrap());
607 /// assert_eq!((&"b", &20), iter.next().unwrap());
608 /// assert_eq!(None, iter.next());
609 /// ```
iter(&self) -> Iter<K, V>610 pub fn iter(&self) -> Iter<K, V> {
611 let head = if self.head.is_null() {
612 ptr::null_mut()
613 } else {
614 unsafe { (*self.head).prev }
615 };
616 Iter {
617 head: head,
618 tail: self.head,
619 remaining: self.len(),
620 marker: marker::PhantomData,
621 }
622 }
623
624 /// Returns a double-ended iterator visiting all key-value pairs in order of insertion.
625 /// Iterator element type is `(&'a K, &'a mut V)`
626 /// # Examples
627 /// ```
628 /// use linked_hash_map::LinkedHashMap;
629 ///
630 /// let mut map = LinkedHashMap::new();
631 /// map.insert("a", 10);
632 /// map.insert("c", 30);
633 /// map.insert("b", 20);
634 ///
635 /// {
636 /// let mut iter = map.iter_mut();
637 /// let mut entry = iter.next().unwrap();
638 /// assert_eq!(&"a", entry.0);
639 /// *entry.1 = 17;
640 /// }
641 ///
642 /// assert_eq!(&17, map.get(&"a").unwrap());
643 /// ```
iter_mut(&mut self) -> IterMut<K, V>644 pub fn iter_mut(&mut self) -> IterMut<K, V> {
645 let head = if self.head.is_null() {
646 ptr::null_mut()
647 } else {
648 unsafe { (*self.head).prev }
649 };
650 IterMut {
651 head: head,
652 tail: self.head,
653 remaining: self.len(),
654 marker: marker::PhantomData,
655 }
656 }
657
658 /// Returns a double-ended iterator visiting all key in order of insertion.
659 ///
660 /// # Examples
661 /// ```
662 /// use linked_hash_map::LinkedHashMap;
663 ///
664 /// let mut map = LinkedHashMap::new();
665 /// map.insert('a', 10);
666 /// map.insert('c', 30);
667 /// map.insert('b', 20);
668 ///
669 /// let mut keys = map.keys();
670 /// assert_eq!(&'a', keys.next().unwrap());
671 /// assert_eq!(&'c', keys.next().unwrap());
672 /// assert_eq!(&'b', keys.next().unwrap());
673 /// assert_eq!(None, keys.next());
674 /// ```
keys(&self) -> Keys<K, V>675 pub fn keys(&self) -> Keys<K, V> {
676 Keys { inner: self.iter() }
677 }
678
679 /// Returns a double-ended iterator visiting all values in order of insertion.
680 ///
681 /// # Examples
682 /// ```
683 /// use linked_hash_map::LinkedHashMap;
684 ///
685 /// let mut map = LinkedHashMap::new();
686 /// map.insert('a', 10);
687 /// map.insert('c', 30);
688 /// map.insert('b', 20);
689 ///
690 /// let mut values = map.values();
691 /// assert_eq!(&10, values.next().unwrap());
692 /// assert_eq!(&30, values.next().unwrap());
693 /// assert_eq!(&20, values.next().unwrap());
694 /// assert_eq!(None, values.next());
695 /// ```
values(&self) -> Values<K, V>696 pub fn values(&self) -> Values<K, V> {
697 Values { inner: self.iter() }
698 }
699 }
700
701 impl<'a, K, V, S, Q: ?Sized> Index<&'a Q> for LinkedHashMap<K, V, S>
702 where K: Hash + Eq + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
703 {
704 type Output = V;
705
index(&self, index: &'a Q) -> &V706 fn index(&self, index: &'a Q) -> &V {
707 self.get(index).expect("no entry found for key")
708 }
709 }
710
711 impl<'a, K, V, S, Q: ?Sized> IndexMut<&'a Q> for LinkedHashMap<K, V, S>
712 where K: Hash + Eq + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
713 {
index_mut(&mut self, index: &'a Q) -> &mut V714 fn index_mut(&mut self, index: &'a Q) -> &mut V {
715 self.get_mut(index).expect("no entry found for key")
716 }
717 }
718
719 impl<K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone> Clone for LinkedHashMap<K, V, S> {
clone(&self) -> Self720 fn clone(&self) -> Self {
721 let mut map = Self::with_hasher(self.map.hasher().clone());
722 map.extend(self.iter().map(|(k, v)| (k.clone(), v.clone())));
723 map
724 }
725 }
726
727 impl<K: Hash + Eq, V, S: BuildHasher + Default> Default for LinkedHashMap<K, V, S> {
default() -> Self728 fn default() -> Self { Self::with_hasher(S::default()) }
729 }
730
731 impl<K: Hash + Eq, V, S: BuildHasher> Extend<(K, V)> for LinkedHashMap<K, V, S> {
extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I)732 fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I) {
733 for (k, v) in iter {
734 self.insert(k, v);
735 }
736 }
737 }
738
739 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for LinkedHashMap<K, V, S>
740 where K: 'a + Hash + Eq + Copy, V: 'a + Copy, S: BuildHasher,
741 {
extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I)742 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
743 for (&k, &v) in iter {
744 self.insert(k, v);
745 }
746 }
747 }
748
749 impl<K: Hash + Eq, V, S: BuildHasher + Default> iter::FromIterator<(K, V)> for LinkedHashMap<K, V, S> {
from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self750 fn from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self {
751 let iter = iter.into_iter();
752 let mut map = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
753 map.extend(iter);
754 map
755 }
756 }
757
758 impl<A: fmt::Debug + Hash + Eq, B: fmt::Debug, S: BuildHasher> fmt::Debug for LinkedHashMap<A, B, S> {
759 /// Returns a string that lists the key-value pairs in insertion order.
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result760 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
761 f.debug_map().entries(self).finish()
762 }
763 }
764
765 impl<K: Hash + Eq, V: PartialEq, S: BuildHasher> PartialEq for LinkedHashMap<K, V, S> {
eq(&self, other: &Self) -> bool766 fn eq(&self, other: &Self) -> bool {
767 self.len() == other.len() && self.iter().eq(other)
768 }
769 }
770
771 impl<K: Hash + Eq, V: Eq, S: BuildHasher> Eq for LinkedHashMap<K, V, S> {}
772
773 impl<K: Hash + Eq + PartialOrd, V: PartialOrd, S: BuildHasher> PartialOrd for LinkedHashMap<K, V, S> {
partial_cmp(&self, other: &Self) -> Option<Ordering>774 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
775 self.iter().partial_cmp(other)
776 }
777
lt(&self, other: &Self) -> bool778 fn lt(&self, other: &Self) -> bool {
779 self.iter().lt(other)
780 }
781
le(&self, other: &Self) -> bool782 fn le(&self, other: &Self) -> bool {
783 self.iter().le(other)
784 }
785
ge(&self, other: &Self) -> bool786 fn ge(&self, other: &Self) -> bool {
787 self.iter().ge(other)
788 }
789
gt(&self, other: &Self) -> bool790 fn gt(&self, other: &Self) -> bool {
791 self.iter().gt(other)
792 }
793 }
794
795 impl<K: Hash + Eq + Ord, V: Ord, S: BuildHasher> Ord for LinkedHashMap<K, V, S> {
cmp(&self, other: &Self) -> Ordering796 fn cmp(&self, other: &Self) -> Ordering {
797 self.iter().cmp(other)
798 }
799 }
800
801 impl<K: Hash + Eq, V: Hash, S: BuildHasher> Hash for LinkedHashMap<K, V, S> {
hash<H: Hasher>(&self, h: &mut H)802 fn hash<H: Hasher>(&self, h: &mut H) { for e in self.iter() { e.hash(h); } }
803 }
804
805 unsafe impl<K: Send, V: Send, S: Send> Send for LinkedHashMap<K, V, S> {}
806
807 unsafe impl<K: Sync, V: Sync, S: Sync> Sync for LinkedHashMap<K, V, S> {}
808
809 impl<K, V, S> Drop for LinkedHashMap<K, V, S> {
drop(&mut self)810 fn drop(&mut self) {
811 if !self.head.is_null() {
812 unsafe {
813 self.drop_entries();
814 drop_empty_node(self.head);
815 }
816 }
817 self.clear_free_list();
818 }
819 }
820
821 /// An insertion-order iterator over a `LinkedHashMap`'s entries, with immutable references to the
822 /// values.
823 pub struct Iter<'a, K: 'a, V: 'a> {
824 head: *const Node<K, V>,
825 tail: *const Node<K, V>,
826 remaining: usize,
827 marker: marker::PhantomData<(&'a K, &'a V)>,
828 }
829
830 /// An insertion-order iterator over a `LinkedHashMap`'s entries, with mutable references to the
831 /// values.
832 pub struct IterMut<'a, K: 'a, V: 'a> {
833 head: *mut Node<K, V>,
834 tail: *mut Node<K, V>,
835 remaining: usize,
836 marker: marker::PhantomData<(&'a K, &'a mut V)>,
837 }
838
839 /// A consuming insertion-order iterator over a `LinkedHashMap`'s entries.
840 pub struct IntoIter<K, V> {
841 head: *mut Node<K, V>,
842 tail: *mut Node<K, V>,
843 remaining: usize,
844 marker: marker::PhantomData<(K, V)>,
845 }
846
847 /// An insertion-order iterator over a `LinkedHashMap`'s entries represented as
848 /// an `OccupiedEntry`.
849 pub struct Entries<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
850 map: *mut LinkedHashMap<K, V, S>,
851 head: *mut Node<K, V>,
852 remaining: usize,
853 marker: marker::PhantomData<(&'a K, &'a mut V, &'a S)>,
854 }
855
856 unsafe impl<'a, K, V> Send for Iter<'a, K, V> where K: Send, V: Send {}
857
858 unsafe impl<'a, K, V> Send for IterMut<'a, K, V> where K: Send, V: Send {}
859
860 unsafe impl<K, V> Send for IntoIter<K, V> where K: Send, V: Send {}
861
862 unsafe impl<'a, K, V, S> Send for Entries<'a, K, V, S> where K: Send, V: Send, S: Send {}
863
864 unsafe impl<'a, K, V> Sync for Iter<'a, K, V> where K: Sync, V: Sync {}
865
866 unsafe impl<'a, K, V> Sync for IterMut<'a, K, V> where K: Sync, V: Sync {}
867
868 unsafe impl<K, V> Sync for IntoIter<K, V> where K: Sync, V: Sync {}
869
870 unsafe impl<'a, K, V, S> Sync for Entries<'a, K, V, S> where K: Sync, V: Sync, S: Sync {}
871
872 impl<'a, K, V> Clone for Iter<'a, K, V> {
clone(&self) -> Self873 fn clone(&self) -> Self { Iter { ..*self } }
874 }
875
876 impl<K, V> Clone for IntoIter<K, V> where K: Clone, V: Clone {
clone(&self) -> Self877 fn clone(&self) -> Self {
878 if self.remaining == 0 {
879 return IntoIter { ..*self }
880 }
881
882 fn clone_node<K, V>(e: *mut Node<K, V>) -> *mut Node<K, V>
883 where K: Clone, V: Clone,
884 {
885 Box::into_raw(Box::new(Node::new(
886 unsafe { (*e).key.clone() }, unsafe { (*e).value.clone() }
887 )))
888 }
889
890 let mut cur = self.head;
891 let head = clone_node(cur);
892 let mut tail = head;
893 for _ in 1..self.remaining {
894 unsafe {
895 (*tail).prev = clone_node((*cur).prev);
896 (*(*tail).prev).next = tail;
897 tail = (*tail).prev;
898 cur = (*cur).prev;
899 }
900 }
901
902 IntoIter {
903 head: head,
904 tail: tail,
905 remaining: self.remaining,
906 marker: marker::PhantomData,
907 }
908 }
909 }
910
911 impl<'a, K, V> Iterator for Iter<'a, K, V> {
912 type Item = (&'a K, &'a V);
913
next(&mut self) -> Option<(&'a K, &'a V)>914 fn next(&mut self) -> Option<(&'a K, &'a V)> {
915 if self.head == self.tail {
916 None
917 } else {
918 self.remaining -= 1;
919 unsafe {
920 let r = Some((&(*self.head).key, &(*self.head).value));
921 self.head = (*self.head).prev;
922 r
923 }
924 }
925 }
926
size_hint(&self) -> (usize, Option<usize>)927 fn size_hint(&self) -> (usize, Option<usize>) {
928 (self.remaining, Some(self.remaining))
929 }
930 }
931
932 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
933 type Item = (&'a K, &'a mut V);
934
next(&mut self) -> Option<(&'a K, &'a mut V)>935 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
936 if self.head == self.tail {
937 None
938 } else {
939 self.remaining -= 1;
940 unsafe {
941 let r = Some((&(*self.head).key, &mut (*self.head).value));
942 self.head = (*self.head).prev;
943 r
944 }
945 }
946 }
947
size_hint(&self) -> (usize, Option<usize>)948 fn size_hint(&self) -> (usize, Option<usize>) {
949 (self.remaining, Some(self.remaining))
950 }
951 }
952
953 impl<K, V> Iterator for IntoIter<K, V> {
954 type Item = (K, V);
955
next(&mut self) -> Option<(K, V)>956 fn next(&mut self) -> Option<(K, V)> {
957 if self.remaining == 0 {
958 return None
959 }
960 self.remaining -= 1;
961 unsafe {
962 let prev = (*self.head).prev;
963 let e = *Box::from_raw(self.head);
964 self.head = prev;
965 Some((e.key, e.value))
966 }
967 }
968
size_hint(&self) -> (usize, Option<usize>)969 fn size_hint(&self) -> (usize, Option<usize>) {
970 (self.remaining, Some(self.remaining))
971 }
972 }
973
974 impl<'a, K, V, S: BuildHasher> Iterator for Entries<'a, K, V, S> {
975 type Item = OccupiedEntry<'a, K, V, S>;
976
next(&mut self) -> Option<OccupiedEntry<'a, K, V, S>>977 fn next(&mut self) -> Option<OccupiedEntry<'a, K, V, S>> {
978 if self.remaining == 0 {
979 None
980 } else {
981 self.remaining -= 1;
982 unsafe {
983 let r = Some(OccupiedEntry {
984 map: self.map,
985 entry: self.head,
986 marker: marker::PhantomData,
987 });
988
989 self.head = (*self.head).prev;
990 r
991 }
992 }
993 }
994
size_hint(&self) -> (usize, Option<usize>)995 fn size_hint(&self) -> (usize, Option<usize>) {
996 (self.remaining, Some(self.remaining))
997 }
998 }
999
1000 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
next_back(&mut self) -> Option<(&'a K, &'a V)>1001 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1002 if self.head == self.tail {
1003 None
1004 } else {
1005 self.remaining -= 1;
1006 unsafe {
1007 self.tail = (*self.tail).next;
1008 Some((&(*self.tail).key, &(*self.tail).value))
1009 }
1010 }
1011 }
1012 }
1013
1014 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
next_back(&mut self) -> Option<(&'a K, &'a mut V)>1015 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1016 if self.head == self.tail {
1017 None
1018 } else {
1019 self.remaining -= 1;
1020 unsafe {
1021 self.tail = (*self.tail).next;
1022 Some((&(*self.tail).key, &mut (*self.tail).value))
1023 }
1024 }
1025 }
1026 }
1027
1028 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
next_back(&mut self) -> Option<(K, V)>1029 fn next_back(&mut self) -> Option<(K, V)> {
1030 if self.remaining == 0 {
1031 return None
1032 }
1033 self.remaining -= 1;
1034 unsafe {
1035 let next = (*self.tail).next;
1036 let e = *Box::from_raw(self.tail);
1037 self.tail = next;
1038 Some((e.key, e.value))
1039 }
1040 }
1041 }
1042
1043 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
len(&self) -> usize1044 fn len(&self) -> usize { self.remaining }
1045 }
1046
1047 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
len(&self) -> usize1048 fn len(&self) -> usize { self.remaining }
1049 }
1050
1051 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
len(&self) -> usize1052 fn len(&self) -> usize { self.remaining }
1053 }
1054
1055 impl<K, V> Drop for IntoIter<K, V> {
drop(&mut self)1056 fn drop(&mut self) {
1057 for _ in 0..self.remaining {
1058 unsafe {
1059 let next = (*self.tail).next;
1060 Box::from_raw(self.tail);
1061 self.tail = next;
1062 }
1063 }
1064 }
1065 }
1066
1067 /// An insertion-order iterator over a `LinkedHashMap`'s keys.
1068 pub struct Keys<'a, K: 'a, V: 'a> {
1069 inner: Iter<'a, K, V>,
1070 }
1071
1072 impl<'a, K, V> Clone for Keys<'a, K, V> {
clone(&self) -> Self1073 fn clone(&self) -> Self { Keys { inner: self.inner.clone() } }
1074 }
1075
1076 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1077 type Item = &'a K;
1078
next(&mut self) -> Option<&'a K>1079 #[inline] fn next(&mut self) -> Option<&'a K> { self.inner.next().map(|e| e.0) }
size_hint(&self) -> (usize, Option<usize>)1080 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1081 }
1082
1083 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
next_back(&mut self) -> Option<&'a K>1084 #[inline] fn next_back(&mut self) -> Option<&'a K> { self.inner.next_back().map(|e| e.0) }
1085 }
1086
1087 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
len(&self) -> usize1088 fn len(&self) -> usize { self.inner.len() }
1089 }
1090
1091 /// An insertion-order iterator over a `LinkedHashMap`'s values.
1092 pub struct Values<'a, K: 'a, V: 'a> {
1093 inner: Iter<'a, K, V>,
1094 }
1095
1096 impl<'a, K, V> Clone for Values<'a, K, V> {
clone(&self) -> Self1097 fn clone(&self) -> Self { Values { inner: self.inner.clone() } }
1098 }
1099
1100 impl<'a, K, V> Iterator for Values<'a, K, V> {
1101 type Item = &'a V;
1102
next(&mut self) -> Option<&'a V>1103 #[inline] fn next(&mut self) -> Option<&'a V> { self.inner.next().map(|e| e.1) }
size_hint(&self) -> (usize, Option<usize>)1104 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1105 }
1106
1107 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
next_back(&mut self) -> Option<&'a V>1108 #[inline] fn next_back(&mut self) -> Option<&'a V> { self.inner.next_back().map(|e| e.1) }
1109 }
1110
1111 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
len(&self) -> usize1112 fn len(&self) -> usize { self.inner.len() }
1113 }
1114
1115 impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a LinkedHashMap<K, V, S> {
1116 type Item = (&'a K, &'a V);
1117 type IntoIter = Iter<'a, K, V>;
into_iter(self) -> Iter<'a, K, V>1118 fn into_iter(self) -> Iter<'a, K, V> { self.iter() }
1119 }
1120
1121 impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a mut LinkedHashMap<K, V, S> {
1122 type Item = (&'a K, &'a mut V);
1123 type IntoIter = IterMut<'a, K, V>;
into_iter(self) -> IterMut<'a, K, V>1124 fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() }
1125 }
1126
1127 impl<K: Hash + Eq, V, S: BuildHasher> IntoIterator for LinkedHashMap<K, V, S> {
1128 type Item = (K, V);
1129 type IntoIter = IntoIter<K, V>;
into_iter(mut self) -> IntoIter<K, V>1130 fn into_iter(mut self) -> IntoIter<K, V> {
1131 let (head, tail) = if !self.head.is_null() {
1132 unsafe { ((*self.head).prev, (*self.head).next) }
1133 } else {
1134 (ptr::null_mut(), ptr::null_mut())
1135 };
1136 let len = self.len();
1137
1138 if !self.head.is_null() {
1139 unsafe { drop_empty_node(self.head) }
1140 }
1141 self.clear_free_list();
1142 // drop the HashMap but not the LinkedHashMap
1143 unsafe { ptr::drop_in_place(&mut self.map); }
1144 mem::forget(self);
1145
1146 IntoIter {
1147 head: head,
1148 tail: tail,
1149 remaining: len,
1150 marker: marker::PhantomData,
1151 }
1152 }
1153 }
1154
1155 /// A view into a single location in a map, which may be vacant or occupied.
1156 pub enum Entry<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
1157 /// An occupied Entry.
1158 Occupied(OccupiedEntry<'a, K, V, S>),
1159 /// A vacant Entry.
1160 Vacant(VacantEntry<'a, K, V, S>),
1161 }
1162
1163 /// A view into a single occupied location in a `LinkedHashMap`.
1164 pub struct OccupiedEntry<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
1165 entry: *mut Node<K, V>,
1166 map: *mut LinkedHashMap<K, V, S>,
1167 marker: marker::PhantomData<&'a K>,
1168 }
1169
1170 /// A view into a single empty location in a `LinkedHashMap`.
1171 pub struct VacantEntry<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
1172 key: K,
1173 map: &'a mut LinkedHashMap<K, V, S>,
1174 }
1175
1176 impl<'a, K: Hash + Eq, V, S: BuildHasher> Entry<'a, K, V, S> {
1177 /// Returns the entry key
1178 ///
1179 /// # Examples
1180 ///
1181 /// ```
1182 /// use linked_hash_map::LinkedHashMap;
1183 ///
1184 /// let mut map = LinkedHashMap::<String, u32>::new();
1185 ///
1186 /// assert_eq!("hello", map.entry("hello".to_string()).key());
1187 /// ```
key(&self) -> &K1188 pub fn key(&self) -> &K {
1189 match *self {
1190 Entry::Occupied(ref e) => e.key(),
1191 Entry::Vacant(ref e) => e.key(),
1192 }
1193 }
1194
1195 /// Ensures a value is in the entry by inserting the default if empty, and returns
1196 /// a mutable reference to the value in the entry.
or_insert(self, default: V) -> &'a mut V1197 pub fn or_insert(self, default: V) -> &'a mut V {
1198 match self {
1199 Entry::Occupied(entry) => entry.into_mut(),
1200 Entry::Vacant(entry) => entry.insert(default),
1201 }
1202 }
1203
1204 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1205 /// and returns a mutable reference to the value in the entry.
or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V1206 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1207 match self {
1208 Entry::Occupied(entry) => entry.into_mut(),
1209 Entry::Vacant(entry) => entry.insert(default()),
1210 }
1211 }
1212 }
1213
1214 impl<'a, K: Hash + Eq, V, S: BuildHasher> OccupiedEntry<'a, K, V, S> {
1215 /// Gets a reference to the entry key
1216 ///
1217 /// # Examples
1218 ///
1219 /// ```
1220 /// use linked_hash_map::LinkedHashMap;
1221 ///
1222 /// let mut map = LinkedHashMap::new();
1223 ///
1224 /// map.insert("foo".to_string(), 1);
1225 /// assert_eq!("foo", map.entry("foo".to_string()).key());
1226 /// ```
key(&self) -> &K1227 pub fn key(&self) -> &K {
1228 unsafe { &(*self.entry).key }
1229 }
1230
1231 /// Gets a reference to the value in the entry.
get(&self) -> &V1232 pub fn get(&self) -> &V {
1233 unsafe { &(*self.entry).value }
1234 }
1235
1236 /// Gets a mutable reference to the value in the entry.
get_mut(&mut self) -> &mut V1237 pub fn get_mut(&mut self) -> &mut V {
1238 unsafe { &mut (*self.entry).value }
1239 }
1240
1241 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1242 /// with a lifetime bound to the map itself
into_mut(self) -> &'a mut V1243 pub fn into_mut(self) -> &'a mut V {
1244 unsafe { &mut (*self.entry).value }
1245 }
1246
1247 /// Sets the value of the entry, and returns the entry's old value
insert(&mut self, value: V) -> V1248 pub fn insert(&mut self, value: V) -> V {
1249 unsafe {
1250 (*self.map).ensure_guard_node();
1251
1252 let old_val = mem::replace(&mut (*self.entry).value, value);
1253 let node_ptr: *mut Node<K, V> = self.entry;
1254
1255 // Existing node, just update LRU position
1256 (*self.map).detach(node_ptr);
1257 (*self.map).attach(node_ptr);
1258
1259 old_val
1260 }
1261 }
1262
1263 /// Takes the value out of the entry, and returns it
remove(self) -> V1264 pub fn remove(self) -> V {
1265 unsafe { (*self.map).remove(&(*self.entry).key) }.unwrap()
1266 }
1267 }
1268
1269 impl<'a, K: 'a + Hash + Eq, V: 'a, S: BuildHasher> VacantEntry<'a, K, V, S> {
1270 /// Gets a reference to the entry key
1271 ///
1272 /// # Examples
1273 ///
1274 /// ```
1275 /// use linked_hash_map::LinkedHashMap;
1276 ///
1277 /// let mut map = LinkedHashMap::<String, u32>::new();
1278 ///
1279 /// assert_eq!("foo", map.entry("foo".to_string()).key());
1280 /// ```
key(&self) -> &K1281 pub fn key(&self) -> &K {
1282 &self.key
1283 }
1284
1285 /// Sets the value of the entry with the VacantEntry's key,
1286 /// and returns a mutable reference to it
insert(self, value: V) -> &'a mut V1287 pub fn insert(self, value: V) -> &'a mut V {
1288 self.map.ensure_guard_node();
1289
1290 let node = if self.map.free.is_null() {
1291 Box::into_raw(Box::new(Node::new(self.key, value)))
1292 } else {
1293 // use a recycled box
1294 unsafe {
1295 let free = self.map.free;
1296 self.map.free = (*free).next;
1297 ptr::write(free, Node::new(self.key, value));
1298 free
1299 }
1300 };
1301
1302 let keyref = unsafe { &(*node).key };
1303
1304 self.map.attach(node);
1305
1306 let ret = self.map.map.entry(KeyRef{k: keyref}).or_insert(node);
1307 unsafe { &mut (**ret).value }
1308 }
1309 }
1310
1311 #[cfg(all(feature = "nightly", test))]
1312 mod bench {
1313 extern crate test;
1314
1315 use super::LinkedHashMap;
1316
1317 #[bench]
not_recycled_cycling(b: &mut test::Bencher)1318 fn not_recycled_cycling(b: &mut test::Bencher) {
1319 let mut hash_map = LinkedHashMap::with_capacity(1000);
1320 for i in 0usize..1000 {
1321 hash_map.insert(i, i);
1322 }
1323 b.iter(|| {
1324 for i in 0usize..1000 {
1325 hash_map.remove(&i);
1326 }
1327 hash_map.clear_free_list();
1328 for i in 0usize..1000 {
1329 hash_map.insert(i, i);
1330 }
1331 })
1332 }
1333
1334 #[bench]
recycled_cycling(b: &mut test::Bencher)1335 fn recycled_cycling(b: &mut test::Bencher) {
1336 let mut hash_map = LinkedHashMap::with_capacity(1000);
1337 for i in 0usize..1000 {
1338 hash_map.insert(i, i);
1339 }
1340 b.iter(|| {
1341 for i in 0usize..1000 {
1342 hash_map.remove(&i);
1343 }
1344 for i in 0usize..1000 {
1345 hash_map.insert(i, i);
1346 }
1347 })
1348 }
1349 }
1350