linked_hash_map/
lib.rs

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

linked_hash_map/
lib.rs
