static_map/
lib.rs

1extern crate fxhash;
2use std::hash::Hash;
3use std::borrow::Borrow;
4
5#[derive(Debug, Copy, Clone)]
6pub struct Map<'a, K: 'a, V: 'a> {
7    #[doc(hidden)]
8    pub hashes: &'a [usize],
9
10    #[doc(hidden)]
11    pub entries: &'a [(K, V)],
12}
13
14impl<'a, K, V> Map<'a, K, V>
15    where K: Hash + Eq
16{
17    #[inline]
18    pub fn len(&self) -> usize {
19        self.entries.len()
20    }
21
22    #[inline]
23    pub fn is_empty(&self) -> bool {
24        self.entries.len() == 0
25    }
26
27    #[inline]
28    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&'a V>
29        where K: Borrow<Q>,
30              Q: Hash + Eq
31    {
32        self.get_entry(key).map(|(_, v)| v)
33    }
34
35    #[inline]
36    pub fn get_entry<Q: ?Sized>(&self, key: &Q) -> Option<(&'a K, &'a V)>
37        where K: Borrow<Q>,
38              Q: Hash + Eq
39    {
40        assert!(self.entries.len().is_power_of_two(),
41                "Invalid StaticMap.  The pool must be a power of two.");
42        assert!(self.entries.len() >= 16,
43                "Invalid StaticMap.  The pool must have size >= 16.");
44
45        // The mask yields the number of trailing bits of a
46        // hash key which yeilds its ideal position.
47        let mask = self.len() - 1;
48        let hash = Self::hash(key);
49
50        let mut pos = hash & mask;
51        let mut dist = 0;
52
53        loop {
54            let entry_hash = self.hashes[pos];
55
56            // Hash match found
57            if entry_hash == hash {
58                let entry = &self.entries[pos];
59                if key.eq(entry.0.borrow()) {
60                    return Some((&entry.0, &entry.1));
61                }
62            }
63
64            // A zero hash indicates vacent bin
65            if entry_hash == 0 {
66                return None;
67            }
68
69            // The trailing bits of a hash indicates the position
70            // the hash is stored.  Taking the difference between
71            // the current hash value and the position will yield
72            // the distance from the current key and it's ideal
73            // location.  If the current key's distance from ideal
74            // is greater than distance from our key's ideal then
75            // we know there is no match.  This is the key
76            // characteristic of Robin-Hood hashing.
77            let entry_dist = pos.wrapping_sub(entry_hash) & mask;
78            if dist > entry_dist {
79                return None;
80            }
81
82            pos = pos.wrapping_add(1) & mask;
83            dist += 1;
84        }
85    }
86
87    #[inline]
88    pub fn entries(&self) -> Entries<'a, K, V> {
89        Entries {
90            cursor: 0,
91            hashes: self.hashes,
92            entries: self.entries,
93        }
94    }
95
96    #[inline]
97    pub fn keys(&self) -> Keys<'a, K, V> {
98        Keys { entries: self.entries() }
99    }
100
101    #[inline]
102    pub fn values(&self) -> Values<'a, K, V> {
103        Values { entries: self.entries() }
104    }
105
106    #[inline]
107    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
108        where K: Borrow<Q>,
109              Q: Hash + Eq
110    {
111        self.get_entry(key).is_some()
112    }
113
114    #[inline]
115    fn hash<Q: ?Sized>(key: &Q) -> usize
116        where K: Borrow<Q>,
117              Q: Hash + Eq
118    {
119        fxhash::hash(key) as usize | 1
120    }
121}
122
123pub struct Entries<'a, K: 'a, V: 'a> {
124    cursor: usize,
125    hashes: &'a [usize],
126    entries: &'a [(K, V)],
127}
128
129impl<'a, K: 'a, V: 'a> Iterator for Entries<'a, K, V> {
130    type Item = &'a (K, V);
131    fn next(&mut self) -> Option<Self::Item> {
132        while self.cursor < self.hashes.len() {
133            if self.hashes[self.cursor] != 0 {
134                let result = Some(&self.entries[self.cursor]);
135                self.cursor += 1;
136                return result;
137            }
138            self.cursor += 1
139        }
140
141        None
142    }
143}
144
145pub struct Keys<'a, K: 'a, V: 'a> {
146    entries: Entries<'a, K, V>,
147}
148
149impl<'a, K: 'a, V: 'a> Iterator for Keys<'a, K, V> {
150    type Item = &'a K;
151    fn next(&mut self) -> Option<Self::Item> {
152        self.entries.next().map(|entry| &entry.0)
153    }
154}
155
156pub struct Values<'a, K: 'a, V: 'a> {
157    entries: Entries<'a, K, V>,
158}
159
160impl<'a, K: 'a, V: 'a> Iterator for Values<'a, K, V> {
161    type Item = &'a V;
162    fn next(&mut self) -> Option<Self::Item> {
163        self.entries.next().map(|entry| &entry.1)
164    }
165}
166
167impl<'a, K: 'a, V: 'a> IntoIterator for Map<'a, K, V>
168    where K: Hash + Eq
169{
170    type Item = &'a (K, V);
171    type IntoIter = Entries<'a, K, V>;
172    fn into_iter(self) -> Entries<'a, K, V> {
173        self.entries()
174    }
175}
176
177#[macro_export]
178macro_rules! static_map {
179    (Default: $default:expr, $($key:expr => $value:expr),* $(,)*) => (
180        static_map!(@stringify $default $(@ $key ? $value )*)
181    );
182
183    // This trick for stringifying into a procedural macro was
184    // developed by dtolnay in the proc-macro-hack crate.
185    (@stringify $($tt:tt)*) => ({
186        #[derive(StaticMapMacro)]
187        enum __StaticMap__ {
188            A = static_map!(@zero $($tt)*)
189        }
190
191        __static_map__construct_map!()
192    });
193
194    (@zero $($tt:tt)*) => { 0 }
195}
static_map/lib.rs

static_map/
lib.rs
