chain_map/
lib.rs

1//! The [`ChainMap`] type groups a chain of [`HashMap`]s together in precedence
2//! order and provides a single, unified view into the values. The semantics
3//! for keys are the same as for a [`HashMap`], however the value associated
4//! with a given key is the value of that key in the highest-precedence map
5//! that contains the key.
6//!
7//! ## Rust Version
8//!
9//! This version of chain-map requires Rust 1.31 or later.
10//!
11//! # Precedence
12//!
13//! Maps added to the [`ChainMap`] earlier have precedence over those added
14//! later. So the first map added to the chain will have the highest
15//! precedence, while the most recent map added will have the lowest.
16//!
17//! # Performance
18//!
19//! Each read of the [`ChainMap`] will read the chain of maps in order, so each
20//! operation will complete in worst-case O(N), with `N` the number of maps in
21//! the chain. As a result, this should only be used for cases where the number
22//! of reads is low compared to the number of elements in each map.
23//!
24//! # Examples
25//!
26//! ```
27//! use std::collections::HashMap;
28//! use chain_map::ChainMap;
29//!
30//! let mut first_map = HashMap::new();
31//! first_map.insert("first", 10);
32//!
33//! let mut second_map = HashMap::new();
34//! second_map.insert("first", 20);
35//! second_map.insert("second", 20);
36//!
37//! let mut third_map = HashMap::new();
38//! third_map.insert("first", 30);
39//! third_map.insert("second", 30);
40//! third_map.insert("third", 30);
41//!
42//! let mut chain: ChainMap<_, _> =
43//!     vec![first_map, second_map, third_map].into_iter().collect();
44//! assert_eq!(chain.get("first"), Some(&10));
45//! assert_eq!(chain["second"], 20);
46//! assert!(chain.contains_key("third"));
47//! assert!(!chain.contains_key("fourth"));
48//! ```
49//!
50//! [`ChainMap`]: struct.ChainMap.html
51//! [`HashMap`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
52
53use std::borrow::Borrow;
54use std::collections::hash_map::RandomState;
55use std::collections::HashMap;
56use std::fmt::{self, Debug};
57use std::hash::{BuildHasher, Hash};
58use std::iter::FromIterator;
59use std::ops::Index;
60
61#[derive(Clone)]
62/// The `ChainMap` type. See [the module level documentation](index.html) for
63/// more.
64pub struct ChainMap<K, V, S = RandomState> {
65    inner: Vec<HashMap<K, V, S>>,
66}
67
68impl<K, V, S> ChainMap<K, V, S> {
69    /// Creates an empty `ChainMap`.
70    ///
71    /// The chain is initially created with a capacity of 0, so it will not
72    /// allocated until a [`HashMap`] is inserted into the chain.
73    ///
74    /// # Examples
75    ///
76    /// ```
77    /// use chain_map::ChainMap;
78    /// let mut chain: ChainMap<&str, i32> = ChainMap::new();
79    /// ```
80    ///
81    /// [`HashMap`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
82    pub fn new() -> Self {
83        Self::default()
84    }
85
86    /// Creates a `ChainMap` with the specified capacity.
87    ///
88    /// Will be able to hold at least `capacity` [`HashMap`]s without
89    /// reallocating. If `capacity` is 0, the chain will not allocate.
90    ///
91    /// # Examples
92    ///
93    /// ```
94    /// use chain_map::ChainMap;
95    /// let mut chain: ChainMap<&str, i32> = ChainMap::with_capacity(10);
96    /// ```
97    ///
98    /// [`HashMap`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
99    pub fn with_capacity(capacity: usize) -> Self {
100        ChainMap {
101            inner: Vec::with_capacity(capacity),
102        }
103    }
104
105    /// Appends a map to the lowest-precedence end of the chain
106    ///
107    /// # Panics
108    ///
109    /// Panics if the number of maps in the chain overflows a [`usize`].
110    ///
111    /// # Examples
112    ///
113    /// ```
114    /// use std::collections::HashMap;
115    /// use chain_map::ChainMap;
116    ///
117    /// let mut hash = HashMap::new();
118    /// hash.insert("key", "value");
119    ///
120    /// let mut chain = ChainMap::new();
121    /// chain.push_map(hash);
122    /// ```
123    ///
124    /// [`usize`]: https://doc.rust-lang.org/std/primitive.usize.html
125    pub fn push_map(&mut self, map: HashMap<K, V, S>) {
126        self.inner.push(map)
127    }
128}
129
130impl<K, V, S> ChainMap<K, V, S>
131where
132    K: Hash + Eq,
133    S: BuildHasher,
134{
135    /// Returns `true` if the `ChainMap` contains a value for the given key.
136    ///
137    /// As with [`HashMap::contains_key`], the supplied key may be any borrowed
138    /// form of the key type, but `Hash` and `Eq` on the borrowed form _must_
139    /// match those for the key type.
140    ///
141    /// # Examples
142    ///
143    /// ```
144    /// use std::collections::HashMap;
145    /// use chain_map::ChainMap;
146    ///
147    /// let mut hash = HashMap::new();
148    /// hash.insert("key", "value");
149    ///
150    /// let mut chain = ChainMap::new();
151    /// chain.push_map(hash);
152    /// assert!(chain.contains_key("key"));
153    /// ```
154    ///
155    /// [`HashMap::contains_key`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.contains_key
156    pub fn contains_key<Q>(&self, k: &Q) -> bool
157    where
158        K: Borrow<Q>,
159        Q: Hash + Eq + ?Sized,
160    {
161        self.inner.iter().any(|map| map.contains_key(k))
162    }
163
164    /// Returns the highest-precedence value associated with the given key.
165    ///
166    /// As with [`HashMap::get`], the supplied key may be any borrowed form of
167    /// the key type, but `Hash` and `Eq` on the borrowed form _must_ match
168    /// those for the key type.
169    ///
170    /// # Examples
171    ///
172    /// ```
173    /// use std::collections::HashMap;
174    /// use chain_map::ChainMap;
175    ///
176    /// let mut hash = HashMap::new();
177    /// hash.insert("key", "value");
178    ///
179    /// let mut chain = ChainMap::new();
180    /// chain.push_map(hash);
181    /// assert_eq!(chain.get("key"), Some(&"value"));
182    /// ```
183    ///
184    /// [`HashMap::get`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get
185    pub fn get<Q>(&self, k: &Q) -> Option<&V>
186    where
187        K: Borrow<Q>,
188        Q: Hash + Eq + ?Sized,
189    {
190        self.inner.iter().find_map(|map| map.get(k))
191    }
192}
193
194impl<K, V, S> Default for ChainMap<K, V, S> {
195    fn default() -> Self {
196        ChainMap { inner: Vec::new() }
197    }
198}
199
200impl<K, Q, V, S> Index<&Q> for ChainMap<K, V, S>
201where
202    K: Eq + Hash + Borrow<Q>,
203    Q: Eq + Hash + ?Sized,
204    S: BuildHasher,
205{
206    type Output = V;
207
208    fn index(&self, k: &Q) -> &V {
209        self.get(k).expect("no entry found for key")
210    }
211}
212
213impl<K, V, S> FromIterator<HashMap<K, V, S>> for ChainMap<K, V, S> {
214    fn from_iter<I>(iter: I) -> Self
215    where
216        I: IntoIterator<Item = HashMap<K, V, S>>,
217    {
218        ChainMap {
219            inner: Vec::from_iter(iter),
220        }
221    }
222}
223
224impl<K, V, S> Extend<HashMap<K, V, S>> for ChainMap<K, V, S> {
225    fn extend<I>(&mut self, iter: I)
226    where
227        I: IntoIterator<Item = HashMap<K, V, S>>,
228    {
229        self.inner.extend(iter)
230    }
231}
232
233impl<K, V, S> Debug for ChainMap<K, V, S>
234where
235    K: Eq + Hash + Debug,
236    V: Debug,
237    S: BuildHasher,
238{
239    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
240        f.debug_struct("ChainMap")
241            .field("inner", &self.inner)
242            .finish()
243    }
244}
245
246impl<K, V, S> PartialEq for ChainMap<K, V, S>
247where
248    K: Eq + Hash,
249    V: PartialEq,
250    S: BuildHasher,
251{
252    fn eq(&self, other: &ChainMap<K, V, S>) -> bool {
253        self.inner.eq(&other.inner)
254    }
255}
256
257impl<K, V, S> Eq for ChainMap<K, V, S>
258where
259    K: Eq + Hash,
260    V: Eq,
261    S: BuildHasher,
262{
263}
264
265#[cfg(test)]
266mod tests {
267    use super::*;
268
269    #[test]
270    fn push_map_adds_to_chain() {
271        let mut first_map = HashMap::new();
272        first_map.insert("first", 1);
273
274        let mut chain = ChainMap::new();
275        chain.push_map(first_map);
276
277        assert_eq!(chain.get("first"), Some(&1));
278        assert_eq!(chain.get("second"), None);
279
280        let mut second_map = HashMap::new();
281        second_map.insert("second", 2);
282
283        chain.push_map(second_map);
284
285        assert_eq!(chain.get("second"), Some(&2));
286    }
287
288    #[test]
289    fn contains_key_searches_all_maps() {
290        let mut first_map = HashMap::new();
291        first_map.insert("first", 1);
292
293        let mut second_map = HashMap::new();
294        second_map.insert("second", 2);
295
296        let mut third_map = HashMap::new();
297        third_map.insert("third", 3);
298
299        let chain: ChainMap<_, _> = vec![first_map, second_map, third_map].into_iter().collect();
300        assert!(chain.contains_key("first"));
301        assert!(chain.contains_key("second"));
302        assert!(chain.contains_key("third"));
303        assert!(!chain.contains_key("fourth"));
304    }
305
306    #[test]
307    fn get_follows_precedence_order() {
308        let mut first_map = HashMap::new();
309        first_map.insert("first", 1);
310
311        let mut second_map = HashMap::new();
312        second_map.insert("first", 1);
313        second_map.insert("second", 2);
314
315        let mut third_map = HashMap::new();
316        third_map.insert("first", 3);
317        third_map.insert("second", 3);
318        third_map.insert("third", 3);
319
320        let chain: ChainMap<_, _> = vec![first_map, second_map, third_map].into_iter().collect();
321
322        assert_eq!(chain.get("first"), Some(&1));
323        assert_eq!(chain.get("second"), Some(&2));
324        assert_eq!(chain.get("third"), Some(&3));
325        assert_eq!(chain.get("fourth"), None);
326    }
327
328    #[test]
329    fn index_follows_precedence_order() {
330        let mut first_map = HashMap::new();
331        first_map.insert("first", 1);
332
333        let mut second_map = HashMap::new();
334        second_map.insert("first", 1);
335        second_map.insert("second", 2);
336
337        let mut third_map = HashMap::new();
338        third_map.insert("first", 3);
339        third_map.insert("second", 3);
340        third_map.insert("third", 3);
341
342        let chain: ChainMap<_, _> = vec![first_map, second_map, third_map].into_iter().collect();
343
344        assert_eq!(chain["first"], 1);
345        assert_eq!(chain["second"], 2);
346        assert_eq!(chain["third"], 3);
347    }
348
349    #[test]
350    #[should_panic]
351    fn index_panics_when_key_is_not_present() {
352        let chain: ChainMap<&str, i32> = ChainMap::new();
353
354        let _ = chain["notset"];
355    }
356
357    #[test]
358    fn extend_adds_to_end_of_chain() {
359        let mut first_map = HashMap::new();
360        first_map.insert("first", 1);
361
362        let mut second_map = HashMap::new();
363        second_map.insert("first", 1);
364        second_map.insert("second", 2);
365
366        let mut third_map = HashMap::new();
367        third_map.insert("first", 3);
368        third_map.insert("second", 3);
369        third_map.insert("third", 3);
370
371        let mut chain: ChainMap<_, _> =
372            vec![first_map, second_map, third_map].into_iter().collect();
373
374        assert_eq!(chain.get("first"), Some(&1));
375        assert_eq!(chain.get("second"), Some(&2));
376        assert_eq!(chain.get("third"), Some(&3));
377        assert_eq!(chain.get("fourth"), None);
378
379        let mut fourth_map = HashMap::new();
380        fourth_map.insert("first", 4);
381        fourth_map.insert("second", 4);
382        fourth_map.insert("third", 4);
383        fourth_map.insert("fourth", 4);
384
385        chain.extend(vec![fourth_map]);
386
387        assert_eq!(chain.get("first"), Some(&1));
388        assert_eq!(chain.get("second"), Some(&2));
389        assert_eq!(chain.get("third"), Some(&3));
390        assert_eq!(chain.get("fourth"), Some(&4));
391    }
392}
chain_map/lib.rs

chain_map/
lib.rs
