terminal_linked_hash_map/
lib.rs

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 terminal_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(test, feature(test))]
32
33use std::borrow::Borrow;
34use std::cmp::Ordering;
35use std::collections::hash_map::HashMap;
36use std::fmt;
37use std::hash::{Hash, Hasher};
38use std::iter;
39use std::marker;
40use std::mem;
41use std::ops::{Index, IndexMut};
42use std::ptr;
43
44struct KeyRef<K> { k: *const K }
45
46struct LinkedHashMapEntry<K, V> {
47    next: *mut LinkedHashMapEntry<K, V>,
48    prev: *mut LinkedHashMapEntry<K, V>,
49    key: K,
50    value: V,
51}
52
53/// A linked hash map.
54pub struct LinkedHashMap<K, V> {
55    map: HashMap<KeyRef<K>, Box<LinkedHashMapEntry<K, V>>>,
56    head: *mut LinkedHashMapEntry<K, V>,
57    free: *mut LinkedHashMapEntry<K, V>,
58}
59
60impl<K: Hash> Hash for KeyRef<K> {
61    fn hash<H: Hasher>(&self, state: &mut H) {
62        unsafe { (*self.k).hash(state) }
63    }
64}
65
66impl<K: PartialEq> PartialEq for KeyRef<K> {
67    fn eq(&self, other: &Self) -> bool {
68        unsafe{ (*self.k).eq(&*other.k) }
69    }
70}
71
72impl<K: Eq> Eq for KeyRef<K> {}
73
74// This type exists only to support borrowing `KeyRef`s, which cannot be borrowed to `Q` directly
75// due to conflicting implementations of `Borrow`. The layout of `&Qey<Q>` must be identical to
76// `&Q` in order to support transmuting in the `Qey::from_ref` method.
77#[derive(Hash, PartialEq, Eq)]
78struct Qey<Q: ?Sized>(Q);
79
80impl<Q: ?Sized> Qey<Q> {
81    fn from_ref(q: &Q) -> &Self { unsafe { mem::transmute(q) } }
82}
83
84impl<K, Q: ?Sized> Borrow<Qey<Q>> for KeyRef<K> where K: Borrow<Q> {
85    fn borrow(&self) -> &Qey<Q> {
86        Qey::from_ref(unsafe { (*self.k).borrow() })
87    }
88}
89
90impl<K, V> LinkedHashMapEntry<K, V> {
91    fn new(k: K, v: V) -> Self {
92        LinkedHashMapEntry {
93            key: k,
94            value: v,
95            next: ptr::null_mut(),
96            prev: ptr::null_mut(),
97        }
98    }
99}
100
101unsafe fn drop_empty_entry_box<K, V>(the_box: *mut LinkedHashMapEntry<K, V>) {
102    // Prevent compiler from trying to drop the un-initialized key and values in the node.
103    let LinkedHashMapEntry { key, value, .. } = *Box::from_raw(the_box);
104    mem::forget(key);
105    mem::forget(value);
106}
107
108impl<K: Hash + Eq, V> LinkedHashMap<K, V> {
109    /// Creates a linked hash map.
110    pub fn new() -> Self { Self::with_map(HashMap::new()) }
111
112    /// Creates an empty linked hash map with the given initial capacity.
113    pub fn with_capacity(capacity: usize) -> Self {
114        Self::with_map(HashMap::with_capacity(capacity))
115    }
116}
117
118impl<K, V> LinkedHashMap<K, V> {
119    fn clear_free_list(&mut self) {
120        unsafe {
121            let mut free = self.free;
122            while ! free.is_null() {
123                let next_free = (*free).next;
124                drop_empty_entry_box(free);
125                free = next_free;
126            }
127            self.free = ptr::null_mut();
128        }
129    }
130}
131
132impl<K: Hash + Eq, V> LinkedHashMap<K, V> {
133    fn with_map(map: HashMap<KeyRef<K>, Box<LinkedHashMapEntry<K, V>>>) -> Self {
134        LinkedHashMap {
135            map: map,
136            head: ptr::null_mut(),
137            free: ptr::null_mut(),
138        }
139    }
140
141    /// Reserves capacity for at least `additional` more elements to be inserted into the map. The
142    /// map may reserve more space to avoid frequent allocations.
143    ///
144    /// # Panics
145    ///
146    /// Panics if the new allocation size overflows `usize.`
147    pub fn reserve(&mut self, additional: usize) { self.map.reserve(additional); }
148
149    /// Shrinks the capacity of the map as much as possible. It will drop down as much as possible
150    /// while maintaining the internal rules and possibly leaving some space in accordance with the
151    /// resize policy.
152    pub fn shrink_to_fit(&mut self) {
153        self.map.shrink_to_fit();
154        self.clear_free_list();
155    }
156
157    /// Inserts a key-value pair into the map. If the key already existed, the old value is
158    /// returned.
159    ///
160    /// # Examples
161    ///
162    /// ```
163    /// use terminal_linked_hash_map::LinkedHashMap;
164    /// let mut map = LinkedHashMap::new();
165    ///
166    /// map.insert(1, "a");
167    /// map.insert(2, "b");
168    /// assert_eq!(map[&1], "a");
169    /// assert_eq!(map[&2], "b");
170    /// ```
171    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
172        if self.head.is_null() {
173            // allocate the guard node if not present
174            unsafe {
175                self.head = Box::into_raw(Box::new(mem::uninitialized()));
176                (*self.head).next = self.head;
177                (*self.head).prev = self.head;
178            }
179        }
180        let (node_ptr, node_opt, old_val) = match self.map.get_mut(&KeyRef{k: &k}) {
181            Some(node) => {
182                let old_val = mem::replace(&mut node.value, v);
183                let node_ptr: *mut LinkedHashMapEntry<K, V> = &mut **node;
184                (node_ptr, None, Some(old_val))
185            }
186            None => {
187                let mut node = if self.free.is_null() {
188                    Box::new(LinkedHashMapEntry::new(k, v))
189                } else {
190                    // use a recycled box
191                    unsafe {
192                        let free = self.free;
193                        self.free = (*free).next;
194                        ptr::write(free, LinkedHashMapEntry::new(k, v));
195                        Box::from_raw(free)
196                    }
197                };
198                let node_ptr: *mut LinkedHashMapEntry<K, V> = &mut *node;
199                (node_ptr, Some(node), None)
200            }
201        };
202        match node_opt {
203            None => {
204                // Existing node, just update LRU position
205                self.detach(node_ptr);
206                self.attach(node_ptr);
207            }
208            Some(node) => {
209                let keyref = unsafe { &(*node_ptr).key };
210                self.map.insert(KeyRef{k: keyref}, node);
211                self.attach(node_ptr);
212            }
213        }
214        old_val
215    }
216
217    /// Checks if the map contains the given key.
218    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool where K: Borrow<Q>, Q: Eq + Hash {
219        self.map.contains_key(Qey::from_ref(k))
220    }
221
222    /// Returns the value corresponding to the key in the map.
223    ///
224    /// # Examples
225    ///
226    /// ```
227    /// use terminal_linked_hash_map::LinkedHashMap;
228    /// let mut map = LinkedHashMap::new();
229    ///
230    /// map.insert(1, "a");
231    /// map.insert(2, "b");
232    /// map.insert(2, "c");
233    /// map.insert(3, "d");
234    ///
235    /// assert_eq!(map.get(&1), Some(&"a"));
236    /// assert_eq!(map.get(&2), Some(&"c"));
237    /// ```
238    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> where K: Borrow<Q>, Q: Eq + Hash {
239        self.map.get(Qey::from_ref(k)).map(|e| &e.value)
240    }
241
242    /// Returns the mutable reference corresponding to the key in the map.
243    ///
244    /// # Examples
245    ///
246    /// ```
247    /// use terminal_linked_hash_map::LinkedHashMap;
248    /// let mut map = LinkedHashMap::new();
249    ///
250    /// map.insert(1, "a");
251    /// map.insert(2, "b");
252    ///
253    /// *map.get_mut(&1).unwrap() = "c";
254    /// assert_eq!(map.get(&1), Some(&"c"));
255    /// ```
256    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash {
257        self.map.get_mut(Qey::from_ref(k)).map(|e| &mut e.value)
258    }
259
260    /// Returns the value corresponding to the key in the map.
261    ///
262    /// If value is found, it is moved to the end of the list.
263    /// This operation can be used in implemenation of LRU cache.
264    ///
265    /// # Examples
266    ///
267    /// ```
268    /// use terminal_linked_hash_map::LinkedHashMap;
269    /// let mut map = LinkedHashMap::new();
270    ///
271    /// map.insert(1, "a");
272    /// map.insert(2, "b");
273    /// map.insert(3, "d");
274    ///
275    /// assert_eq!(map.get_refresh(&2), Some(&mut "b"));
276    ///
277    /// assert_eq!((&2, &"b"), map.iter().rev().next().unwrap());
278    /// ```
279    pub fn get_refresh<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash {
280        let (value, node_ptr_opt) = match self.map.get_mut(Qey::from_ref(k)) {
281            None => (None, None),
282            Some(node) => {
283                let node_ptr: *mut LinkedHashMapEntry<K, V> = &mut **node;
284                (Some(unsafe { &mut(*node_ptr).value }), Some(node_ptr))
285            }
286        };
287        if let Some(node_ptr) = node_ptr_opt {
288            self.detach(node_ptr);
289            self.attach(node_ptr);
290        }
291        return value;
292    }
293
294    /// Removes and returns the value corresponding to the key from the map.
295    ///
296    /// # Examples
297    ///
298    /// ```
299    /// use terminal_linked_hash_map::LinkedHashMap;
300    /// let mut map = LinkedHashMap::new();
301    ///
302    /// map.insert(2, "a");
303    ///
304    /// assert_eq!(map.remove(&1), None);
305    /// assert_eq!(map.remove(&2), Some("a"));
306    /// assert_eq!(map.remove(&2), None);
307    /// assert_eq!(map.len(), 0);
308    /// ```
309    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> where K: Borrow<Q>, Q: Eq + Hash {
310        let removed = self.map.remove(Qey::from_ref(k));
311        removed.map(|mut node| {
312            let node_ptr: *mut LinkedHashMapEntry<K,V> = &mut *node;
313            self.detach(node_ptr);
314            unsafe {
315                // add to free list
316                (*node_ptr).next = self.free;
317                self.free = node_ptr;
318                // forget the box but drop the key and return the value
319                mem::forget(node);
320                drop(ptr::read(&(*node_ptr).key));
321                ptr::read(&(*node_ptr).value)
322            }
323        })
324    }
325
326    /// Returns the maximum number of key-value pairs the map can hold without reallocating.
327    ///
328    /// # Examples
329    ///
330    /// ```
331    /// use terminal_linked_hash_map::LinkedHashMap;
332    /// let mut map: LinkedHashMap<i32, &str> = LinkedHashMap::new();
333    /// let capacity = map.capacity();
334    /// ```
335    pub fn capacity(&self) -> usize {
336        self.map.capacity()
337    }
338
339    /// Removes the first entry.
340    ///
341    /// Can be used in implementation of LRU cache.
342    ///
343    /// # Examples
344    ///
345    /// ```
346    /// use terminal_linked_hash_map::LinkedHashMap;
347    /// let mut map = LinkedHashMap::new();
348    /// map.insert(1, 10);
349    /// map.insert(2, 20);
350    /// map.pop_front();
351    /// assert_eq!(map.get(&1), None);
352    /// assert_eq!(map.get(&2), Some(&20));
353    /// ```
354    #[inline]
355    pub fn pop_front(&mut self) -> Option<(K, V)> {
356        if self.len() > 0 {
357            let lru = unsafe { (*self.head).prev };
358            self.detach(lru);
359            return self.map
360                .remove(&KeyRef{k: unsafe { &(*lru).key }})
361                .map(|e| { let e = *e; (e.key, e.value) })
362        }
363        None
364    }
365
366    /// Gets the first entry.
367    ///
368    /// # Examples
369    ///
370    /// ```
371    /// use terminal_linked_hash_map::LinkedHashMap;
372    /// let mut map = LinkedHashMap::new();
373    /// map.insert(1, 10);
374    /// map.insert(2, 20);
375    /// assert_eq!(map.front(), Some((&1, &10)));
376    /// ```
377    #[inline]
378    pub fn front(&self) -> Option<(&K, &V)> {
379        if self.len() > 0 {
380            let lru = unsafe { (*self.head).prev };
381            return self.map.get(&KeyRef{k: unsafe { &(*lru).key }})
382                .map(|e| (&e.key, &e.value))
383        }
384        None
385    }
386
387    /// Removes the last entry.
388    ///
389    /// # Examples
390    ///
391    /// ```
392    /// use terminal_linked_hash_map::LinkedHashMap;
393    /// let mut map = LinkedHashMap::new();
394    /// map.insert(1, 10);
395    /// map.insert(2, 20);
396    /// map.pop_back();
397    /// assert_eq!(map.get(&1), Some(&10));
398    /// assert_eq!(map.get(&2), None);
399    /// ```
400    #[inline]
401    pub fn pop_back(&mut self) -> Option<(K, V)> {
402        if self.len() > 0 {
403            let mru = unsafe { (*self.head).next };
404            self.detach(mru);
405            return self.map
406                .remove(&KeyRef{k: unsafe { &(*mru).key }})
407                .map(|e| { let e = *e; (e.key, e.value) })
408        }
409        None
410    }
411
412    /// Gets the last entry.
413    ///
414    /// # Examples
415    ///
416    /// ```
417    /// use terminal_linked_hash_map::LinkedHashMap;
418    /// let mut map = LinkedHashMap::new();
419    /// map.insert(1, 10);
420    /// map.insert(2, 20);
421    /// assert_eq!(map.back(), Some((&2, &20)));
422    /// ```
423    #[inline]
424    pub fn back(&mut self) -> Option<(&K, &V)> {
425        if self.len() > 0 {
426            let mru = unsafe { (*self.head).next };
427            return self.map.get(&KeyRef{k: unsafe { &(*mru).key }})
428                .map(|e| (&e.key, &e.value))
429        }
430        None
431    }
432
433    /// Returns the number of key-value pairs in the map.
434    pub fn len(&self) -> usize { self.map.len() }
435
436    /// Returns whether the map is currently empty.
437    pub fn is_empty(&self) -> bool { self.len() == 0 }
438
439    /// Clears the map of all key-value pairs.
440    pub fn clear(&mut self) {
441        self.map.clear();
442        // update the guard node if present
443        if ! self.head.is_null() {
444            unsafe {
445                (*self.head).prev = self.head;
446                (*self.head).next = self.head;
447            }
448        }
449    }
450
451    /// Returns a double-ended iterator visiting all key-value pairs in order of insertion.
452    /// Iterator element type is `(&'a K, &'a V)`
453    ///
454    /// # Examples
455    /// ```
456    /// use terminal_linked_hash_map::LinkedHashMap;
457    ///
458    /// let mut map = LinkedHashMap::new();
459    /// map.insert("a", 10);
460    /// map.insert("c", 30);
461    /// map.insert("b", 20);
462    ///
463    /// let mut iter = map.iter();
464    /// assert_eq!((&"a", &10), iter.next().unwrap());
465    /// assert_eq!((&"c", &30), iter.next().unwrap());
466    /// assert_eq!((&"b", &20), iter.next().unwrap());
467    /// assert_eq!(None, iter.next());
468    /// ```
469    pub fn iter(&self) -> Iter<K, V> {
470        let head = if ! self.head.is_null() {
471            unsafe { (*self.head).prev }
472        } else {
473            ptr::null_mut()
474        };
475        Iter {
476            head: head,
477            tail: self.head,
478            remaining: self.len(),
479            marker: marker::PhantomData,
480        }
481    }
482
483    /// Returns a double-ended iterator visiting all key-value pairs in order of insertion.
484    /// Iterator element type is `(&'a K, &'a mut V)`
485    /// # Examples
486    /// ```
487    /// use terminal_linked_hash_map::LinkedHashMap;
488    ///
489    /// let mut map = LinkedHashMap::new();
490    /// map.insert("a", 10);
491    /// map.insert("c", 30);
492    /// map.insert("b", 20);
493    ///
494    /// {
495    ///     let mut iter = map.iter_mut();
496    ///     let mut entry = iter.next().unwrap();
497    ///     assert_eq!(&"a", entry.0);
498    ///     *entry.1 = 17;
499    /// }
500    ///
501    /// assert_eq!(&17, map.get(&"a").unwrap());
502    /// ```
503    pub fn iter_mut(&mut self) -> IterMut<K, V> {
504        let head = if ! self.head.is_null() {
505            unsafe { (*self.head).prev }
506        } else {
507            ptr::null_mut()
508        };
509        IterMut {
510            head: head,
511            tail: self.head,
512            remaining: self.len(),
513            marker: marker::PhantomData,
514        }
515    }
516
517    /// Returns a double-ended iterator visiting all key in order of insertion.
518    ///
519    /// # Examples
520    /// ```
521    /// use terminal_linked_hash_map::LinkedHashMap;
522    ///
523    /// let mut map = LinkedHashMap::new();
524    /// map.insert('a', 10);
525    /// map.insert('c', 30);
526    /// map.insert('b', 20);
527    ///
528    /// let mut keys = map.keys();
529    /// assert_eq!(&'a', keys.next().unwrap());
530    /// assert_eq!(&'c', keys.next().unwrap());
531    /// assert_eq!(&'b', keys.next().unwrap());
532    /// assert_eq!(None, keys.next());
533    /// ```
534    pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
535        fn first<A, B>((a, _): (A, B)) -> A { a }
536        let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn ptr
537
538        Keys { inner: self.iter().map(first) }
539    }
540
541    /// Returns a double-ended iterator visiting all values in order of insertion.
542    ///
543    /// # Examples
544    /// ```
545    /// use terminal_linked_hash_map::LinkedHashMap;
546    ///
547    /// let mut map = LinkedHashMap::new();
548    /// map.insert('a', 10);
549    /// map.insert('c', 30);
550    /// map.insert('b', 20);
551    ///
552    /// let mut values = map.values();
553    /// assert_eq!(&10, values.next().unwrap());
554    /// assert_eq!(&30, values.next().unwrap());
555    /// assert_eq!(&20, values.next().unwrap());
556    /// assert_eq!(None, values.next());
557    /// ```
558    pub fn values<'a>(&'a self) -> Values<'a, K, V> {
559        fn second<A, B>((_, b): (A, B)) -> B { b }
560        let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn ptr
561
562        Values { inner: self.iter().map(second) }
563    }
564}
565
566impl<'a, K, V, Q: ?Sized> Index<&'a Q> for LinkedHashMap<K, V>
567    where K: Hash + Eq + Borrow<Q>, Q: Eq + Hash
568{
569    type Output = V;
570
571    fn index(&self, index: &'a Q) -> &V {
572        self.get(index).expect("no entry found for key")
573    }
574}
575
576impl<'a, K, V, Q: ?Sized> IndexMut<&'a Q> for LinkedHashMap<K, V>
577    where K: Hash + Eq + Borrow<Q>, Q: Eq + Hash
578{
579    fn index_mut(&mut self, index: &'a Q) -> &mut V {
580        self.get_mut(index).expect("no entry found for key")
581    }
582}
583
584impl<K: Hash + Eq, V> LinkedHashMap<K, V> {
585    #[inline]
586    fn detach(&mut self, node: *mut LinkedHashMapEntry<K, V>) {
587        unsafe {
588            (*(*node).prev).next = (*node).next;
589            (*(*node).next).prev = (*node).prev;
590        }
591    }
592
593    #[inline]
594    fn attach(&mut self, node: *mut LinkedHashMapEntry<K, V>) {
595        unsafe {
596            (*node).next = (*self.head).next;
597            (*node).prev = self.head;
598            (*self.head).next = node;
599            (*(*node).next).prev = node;
600        }
601    }
602}
603
604// FIXME: `HashMap` doesn't expose its hash state, so we cannot clone fully parameterized
605// `LinkedHashMap`s without cloning the original map and clearing it. For now, only
606// `LinkedHashMap<K, V>`s implement `Clone`.
607impl<K: Hash + Eq + Clone, V: Clone> Clone for LinkedHashMap<K, V> {
608    fn clone(&self) -> Self {
609        self.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
610    }
611}
612
613impl<K: Hash + Eq, V> Default for LinkedHashMap<K, V> {
614    fn default() -> Self { LinkedHashMap::new() }
615}
616
617impl<K: Hash + Eq, V> Extend<(K, V)> for LinkedHashMap<K, V> {
618    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
619        for (k, v) in iter {
620            self.insert(k, v);
621        }
622    }
623}
624
625impl<K: Hash + Eq, V> iter::FromIterator<(K, V)> for LinkedHashMap<K, V> {
626    fn from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self {
627        let iter = iter.into_iter();
628        let mut map = Self::with_capacity(iter.size_hint().0);
629        map.extend(iter);
630        map
631    }
632}
633
634impl<A: fmt::Debug + Hash + Eq, B: fmt::Debug> fmt::Debug for LinkedHashMap<A, B> {
635    /// Returns a string that lists the key-value pairs in insertion order.
636    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
637        f.debug_map().entries(self).finish()
638    }
639}
640
641impl<K: Hash + Eq, V: PartialEq> PartialEq for LinkedHashMap<K, V> {
642    fn eq(&self, other: &Self) -> bool {
643        self.len() == other.len() && self.iter().eq(other)
644    }
645
646    fn ne(&self, other: &Self) -> bool {
647        self.len() != other.len() || self.iter().ne(other)
648    }
649}
650
651impl<K: Hash + Eq, V: Eq> Eq for LinkedHashMap<K, V> {}
652
653impl<K: Hash + Eq + PartialOrd, V: PartialOrd> PartialOrd for LinkedHashMap<K, V> {
654    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
655        self.iter().partial_cmp(other)
656    }
657
658    fn lt(&self, other: &Self) -> bool {
659        self.iter().lt(other)
660    }
661
662    fn le(&self, other: &Self) -> bool {
663        self.iter().le(other)
664    }
665
666    fn ge(&self, other: &Self) -> bool {
667        self.iter().ge(other)
668    }
669
670    fn gt(&self, other: &Self) -> bool {
671        self.iter().gt(other)
672    }
673}
674
675impl<K: Hash + Eq + Ord, V: Ord> Ord for LinkedHashMap<K, V> {
676    fn cmp(&self, other: &Self) -> Ordering {
677        self.iter().cmp(other)
678    }
679}
680
681impl<K: Hash + Eq, V: Hash> Hash for LinkedHashMap<K, V> {
682    fn hash<H: Hasher>(&self, h: &mut H) { for e in self.iter() { e.hash(h); } }
683}
684
685unsafe impl<K: Send, V: Send> Send for LinkedHashMap<K, V> {}
686
687unsafe impl<K: Sync, V: Sync> Sync for LinkedHashMap<K, V> {}
688
689impl<K, V> Drop for LinkedHashMap<K, V> {
690    fn drop(&mut self) {
691        unsafe {
692            if ! self.head.is_null() {
693                drop_empty_entry_box(self.head);
694            }
695            self.clear_free_list();
696        }
697    }
698}
699
700/// An insertion-order iterator over a `LinkedHashMap`'s entries, with immutable references to the
701/// values.
702pub struct Iter<'a, K: 'a, V: 'a> {
703    head: *const LinkedHashMapEntry<K, V>,
704    tail: *const LinkedHashMapEntry<K, V>,
705    remaining: usize,
706    marker: marker::PhantomData<(&'a K, &'a V)>,
707}
708
709/// An insertion-order iterator over a `LinkedHashMap`'s entries, with mutable references to the
710/// values.
711pub struct IterMut<'a, K: 'a, V: 'a> {
712    head: *mut LinkedHashMapEntry<K, V>,
713    tail: *mut LinkedHashMapEntry<K, V>,
714    remaining: usize,
715    marker: marker::PhantomData<(&'a K, &'a mut V)>,
716}
717
718unsafe impl<'a, K, V> Send for Iter<'a, K, V> where K: Send, V: Send {}
719
720unsafe impl<'a, K, V> Send for IterMut<'a, K, V> where K: Send, V: Send {}
721
722unsafe impl<'a, K, V> Sync for Iter<'a, K, V> where K: Sync, V: Sync {}
723
724unsafe impl<'a, K, V> Sync for IterMut<'a, K, V> where K: Sync, V: Sync {}
725
726impl<'a, K, V> Clone for Iter<'a, K, V> {
727    fn clone(&self) -> Self { Iter { ..*self } }
728}
729
730impl<'a, K, V> Iterator for Iter<'a, K, V> {
731    type Item = (&'a K, &'a V);
732
733    fn next(&mut self) -> Option<(&'a K, &'a V)> {
734        if self.head == self.tail {
735            None
736        } else {
737            self.remaining -= 1;
738            unsafe {
739                let r = Some((&(*self.head).key, &(*self.head).value));
740                self.head = (*self.head).prev;
741                r
742            }
743        }
744    }
745
746    fn size_hint(&self) -> (usize, Option<usize>) {
747        (self.remaining, Some(self.remaining))
748    }
749}
750
751impl<'a, K, V> Iterator for IterMut<'a, K, V> {
752    type Item = (&'a K, &'a mut V);
753
754    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
755        if self.head == self.tail {
756            None
757        } else {
758            self.remaining -= 1;
759            unsafe {
760                let r = Some((&(*self.head).key, &mut (*self.head).value));
761                self.head = (*self.head).prev;
762                r
763            }
764        }
765    }
766
767    fn size_hint(&self) -> (usize, Option<usize>) {
768        (self.remaining, Some(self.remaining))
769    }
770}
771
772impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
773    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
774        if self.head == self.tail {
775            None
776        } else {
777            self.remaining -= 1;
778            unsafe {
779                self.tail = (*self.tail).next;
780                let r = Some((&(*self.tail).key, &(*self.tail).value));
781                r
782            }
783        }
784    }
785}
786
787impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
788    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
789        if self.head == self.tail {
790            None
791        } else {
792            self.remaining -= 1;
793            unsafe {
794                self.tail = (*self.tail).next;
795                let r = Some((&(*self.tail).key, &mut (*self.tail).value));
796                r
797            }
798        }
799    }
800}
801
802impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
803    fn len(&self) -> usize { self.remaining }
804}
805
806impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
807    fn len(&self) -> usize { self.remaining }
808}
809
810/// An insertion-order iterator over a `LinkedHashMap`'s keys.
811pub struct Keys<'a, K: 'a, V: 'a> {
812    inner: iter::Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
813}
814
815impl<'a, K, V> Clone for Keys<'a, K, V> {
816    fn clone(&self) -> Self { Keys { inner: self.inner.clone() } }
817}
818
819impl<'a, K, V> Iterator for Keys<'a, K, V> {
820    type Item = &'a K;
821
822    #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
823    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
824}
825
826impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
827    #[inline] fn next_back(&mut self) -> Option<(&'a K)> { self.inner.next_back() }
828}
829
830impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
831    fn len(&self) -> usize { self.inner.len() }
832}
833
834/// An insertion-order iterator over a `LinkedHashMap`'s values.
835pub struct Values<'a, K: 'a, V: 'a> {
836    inner: iter::Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
837}
838
839impl<'a, K, V> Clone for Values<'a, K, V> {
840    fn clone(&self) -> Self { Values { inner: self.inner.clone() } }
841}
842
843impl<'a, K, V> Iterator for Values<'a, K, V> {
844    type Item = &'a V;
845
846    #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
847    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
848}
849
850impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
851    #[inline] fn next_back(&mut self) -> Option<(&'a V)> { self.inner.next_back() }
852}
853
854impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
855    fn len(&self) -> usize { self.inner.len() }
856}
857
858impl<'a, K: Hash + Eq, V> IntoIterator for &'a LinkedHashMap<K, V> {
859    type Item = (&'a K, &'a V);
860    type IntoIter = Iter<'a, K, V>;
861    fn into_iter(self) -> Iter<'a, K, V> { self.iter() }
862}
863
864impl<'a, K: Hash + Eq, V> IntoIterator for &'a mut LinkedHashMap<K, V> {
865    type Item = (&'a K, &'a mut V);
866    type IntoIter = IterMut<'a, K, V>;
867    fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() }
868}
869
870#[cfg(test)]
871mod bench {
872    extern crate test;
873
874    use super::LinkedHashMap;
875
876    #[bench]
877    fn not_recycled_cycling(b: &mut test::Bencher) {
878        let mut hash_map = LinkedHashMap::with_capacity(1000);
879        for i in 0usize..1000 {
880            hash_map.insert(i, i);
881        }
882        b.iter(|| {
883            for i in 0usize..1000 {
884                hash_map.remove(&i);
885            }
886            hash_map.clear_free_list();
887            for i in 0usize..1000 {
888                hash_map.insert(i, i);
889            }
890        })
891    }
892
893    #[bench]
894    fn recycled_cycling(b: &mut test::Bencher) {
895        let mut hash_map = LinkedHashMap::with_capacity(1000);
896        for i in 0usize..1000 {
897            hash_map.insert(i, i);
898        }
899        b.iter(|| {
900            for i in 0usize..1000 {
901                hash_map.remove(&i);
902            }
903            for i in 0usize..1000 {
904                hash_map.insert(i, i);
905            }
906        })
907    }
908}
terminal_linked_hash_map/lib.rs

terminal_linked_hash_map/
lib.rs
