toad_map/
lib.rs

1//! This microcrate contains a `Map` trait that generalizes `HashMap` semantics
2//! to `std`, `alloc` and `no_std` platforms.
3
4// docs
5#![doc(html_root_url = "https://docs.rs/toad-map/0.0.0")]
6#![cfg_attr(any(docsrs, feature = "docs"), feature(doc_cfg))]
7// -
8// style
9#![allow(clippy::unused_unit)]
10// -
11// deny
12#![deny(missing_docs)]
13#![deny(missing_debug_implementations)]
14#![deny(missing_copy_implementations)]
15#![cfg_attr(not(test), deny(unsafe_code))]
16// -
17// warnings
18#![cfg_attr(not(test), warn(unreachable_pub))]
19// -
20// features
21#![cfg_attr(not(feature = "std"), no_std)]
22
23#[cfg(feature = "alloc")]
24extern crate alloc as std_alloc;
25
26use core::borrow::Borrow;
27use core::hash::Hash;
28use core::ops::{Deref, DerefMut};
29use core::{iter, slice};
30#[cfg(feature = "std")]
31use std::collections::{hash_map, HashMap};
32
33#[cfg(feature = "alloc")]
34use std_alloc::collections::{btree_map, BTreeMap};
35use toad_len::Len;
36
37/// Things that can go unhappily when trying to insert into a map
38#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Ord, Eq)]
39pub enum InsertError<V> {
40  /// The new value was inserted successfully but there was already a value in the map for that key.
41  Exists(V),
42  /// The map is at capacity and cannot fit any more pairs.
43  CapacityExhausted,
44}
45
46/// An collection of key-value pairs
47///
48/// # Provided implementations
49/// - [`HashMap`]`<K, V>`
50/// - [`tinyvec::ArrayVec`]`<(K, V)>`
51/// - [`Vec`]`<(K, V)>`
52///
53/// # Requirements
54/// - [`Default`] for creating the map
55/// - [`Extend`] for adding new entries to the map
56/// - [`Len`] for bound checks, empty checks, and accessing the length
57/// - [`FromIterator`] for [`collect`](core::iter::Iterator#method.collect)ing into the map
58/// - [`IntoIterator`] for iterating and destroying the map
59pub trait Map<K: Ord + Eq + Hash, V>:
60  Default + Len + Extend<(K, V)> + FromIterator<(K, V)> + IntoIterator<Item = (K, V)>
61{
62  /// See [`HashMap.insert`]
63  fn insert(&mut self, key: K, val: V) -> Result<(), InsertError<V>>;
64
65  /// See [`HashMap.remove`]
66  fn remove<Q>(&mut self, key: &Q) -> Option<V>
67    where K: Borrow<Q>,
68          Q: Hash + Eq + Ord;
69
70  /// See [`HashMap.get`]
71  fn get<'a, Q: Hash + Eq + Ord>(&'a self, key: &Q) -> Option<&'a V>
72    where K: Borrow<Q> + 'a;
73
74  /// See [`HashMap.get_mut`]
75  fn get_mut<'a, Q: Hash + Eq + Ord>(&'a mut self, key: &Q) -> Option<&'a mut V>
76    where K: Borrow<Q> + 'a;
77
78  /// See [`HashMap.contains_key`]
79  fn has<Q: Hash + Eq + Ord>(&self, key: &Q) -> bool
80    where K: Borrow<Q>
81  {
82    self.get(key).is_some()
83  }
84
85  /// See [`HashMap.iter`]
86  fn iter(&self) -> Iter<'_, K, V>;
87
88  /// See [`HashMap.iter_mut`]
89  fn iter_mut(&mut self) -> IterMut<'_, K, V>;
90}
91
92#[cfg(feature = "alloc")]
93impl<K: Eq + Hash + Ord, V> Map<K, V> for BTreeMap<K, V> {
94  fn insert(&mut self, key: K, val: V) -> Result<(), InsertError<V>> {
95    match self.insert(key, val).map(InsertError::Exists).ok_or(()) {
96      | Ok(e) => Err(e),
97      | Err(()) => Ok(()),
98    }
99  }
100
101  fn remove<Q: Ord>(&mut self, key: &Q) -> Option<V>
102    where K: Borrow<Q>
103  {
104    self.remove(key)
105  }
106
107  fn get<'a, Q: Hash + Eq + Ord>(&'a self, key: &Q) -> Option<&'a V>
108    where K: Borrow<Q> + 'a
109  {
110    self.get(key)
111  }
112
113  fn get_mut<'a, Q: Hash + Eq + Ord>(&'a mut self, key: &Q) -> Option<&'a mut V>
114    where K: Borrow<Q> + 'a
115  {
116    self.get_mut(key)
117  }
118
119  fn iter(&self) -> Iter<'_, K, V> {
120    Iter { array_iter: None,
121           #[cfg(feature = "std")]
122           hashmap_iter: None,
123           btreemap_iter: Some(self.iter()) }
124  }
125
126  fn iter_mut(&mut self) -> IterMut<'_, K, V> {
127    IterMut { array_iter: None,
128              #[cfg(feature = "std")]
129              hashmap_iter: None,
130              btreemap_iter: Some(self.iter_mut()) }
131  }
132}
133
134#[cfg(feature = "std")]
135impl<K: Eq + Hash + Ord, V> Map<K, V> for HashMap<K, V> {
136  fn iter(&self) -> Iter<'_, K, V> {
137    Iter { array_iter: None,
138           btreemap_iter: None,
139           hashmap_iter: Some(self.iter()) }
140  }
141
142  fn iter_mut(&mut self) -> IterMut<'_, K, V> {
143    IterMut { array_iter: None,
144              btreemap_iter: None,
145              hashmap_iter: Some(self.iter_mut()) }
146  }
147
148  fn get<'a, Q: Hash + Eq + Ord>(&'a self, key: &Q) -> Option<&'a V>
149    where K: Borrow<Q> + 'a
150  {
151    self.get(key)
152  }
153
154  fn get_mut<'a, Q: Hash + Eq + Ord>(&'a mut self, key: &Q) -> Option<&'a mut V>
155    where K: Borrow<Q> + 'a
156  {
157    self.get_mut(key)
158  }
159
160  fn insert(&mut self, key: K, val: V) -> Result<(), InsertError<V>> {
161    match self.insert(key, val).map(InsertError::Exists).ok_or(()) {
162      | Ok(e) => Err(e),
163      | Err(()) => Ok(()),
164    }
165  }
166
167  fn remove<Q: Hash + Eq + Ord>(&mut self, key: &Q) -> Option<V>
168    where K: Borrow<Q>
169  {
170    self.remove(key)
171  }
172}
173
174impl<A: tinyvec::Array<Item = (K, V)>, K: Eq + Hash + Ord, V> Map<K, V> for tinyvec::ArrayVec<A> {
175  fn insert(&mut self, key: K, mut val: V) -> Result<(), InsertError<V>> {
176    match self.iter_mut().find(|(k, _)| k == &&key) {
177      | Some((_, exist)) => {
178        core::mem::swap(exist, &mut val);
179        Err(InsertError::Exists(val))
180      },
181      | None => match self.is_full() {
182        | true => Err(InsertError::CapacityExhausted),
183        | false => {
184          self.push((key, val));
185          Ok(())
186        },
187      },
188    }
189  }
190
191  fn remove<Q: Hash + Eq + Ord>(&mut self, key: &Q) -> Option<V>
192    where K: Borrow<Q>
193  {
194    match self.iter()
195              .enumerate()
196              .find(|(_, (k, _))| Borrow::<Q>::borrow(*k) == key)
197    {
198      | Some((ix, _)) => Some(self.remove(ix).1),
199      | None => None,
200    }
201  }
202
203  fn get<'a, Q: Hash + Eq + Ord>(&'a self, key: &Q) -> Option<&'a V>
204    where K: Borrow<Q> + 'a
205  {
206    match self.iter().find(|(k, _)| Borrow::<Q>::borrow(*k) == key) {
207      | Some((_, v)) => Some(v),
208      | None => None,
209    }
210  }
211
212  fn get_mut<'a, Q: Hash + Eq + Ord>(&'a mut self, key: &Q) -> Option<&'a mut V>
213    where K: Borrow<Q> + 'a
214  {
215    match self.iter_mut()
216              .find(|(k, _)| Borrow::<Q>::borrow(*k) == key)
217    {
218      | Some((_, v)) => Some(v),
219      | None => None,
220    }
221  }
222
223  fn iter(&self) -> Iter<'_, K, V> {
224    Iter { array_iter: Some(self.deref().iter().map(Iter::coerce_array_iter)),
225           #[cfg(feature = "alloc")]
226           btreemap_iter: None,
227           #[cfg(feature = "std")]
228           hashmap_iter: None }
229  }
230
231  fn iter_mut(&mut self) -> IterMut<'_, K, V> {
232    IterMut { array_iter: Some(self.deref_mut().iter_mut().map(IterMut::coerce_array_iter)),
233              #[cfg(feature = "alloc")]
234              btreemap_iter: None,
235              #[cfg(feature = "std")]
236              hashmap_iter: None }
237  }
238}
239
240#[cfg(feature = "alloc")]
241impl<K, V> Map<K, V> for std_alloc::vec::Vec<(K, V)> where K: Ord + Hash
242{
243  fn insert(&mut self, key: K, mut val: V) -> Result<(), InsertError<V>> {
244    match self.iter_mut().find(|(k, _)| k == &&key) {
245      | Some((_, exist)) => {
246        core::mem::swap(exist, &mut val);
247        Err(InsertError::Exists(val))
248      },
249      | None => match self.is_full() {
250        | true => Err(InsertError::CapacityExhausted),
251        | false => {
252          self.push((key, val));
253          Ok(())
254        },
255      },
256    }
257  }
258
259  fn remove<Q>(&mut self, key: &Q) -> Option<V>
260    where K: Borrow<Q>,
261          Q: Hash + Eq + Ord
262  {
263    match self.iter()
264              .enumerate()
265              .find(|(_, (k, _))| Borrow::<Q>::borrow(*k) == key)
266    {
267      | Some((ix, _)) => Some(self.remove(ix).1),
268      | None => None,
269    }
270  }
271
272  fn get<'a, Q: Hash + Eq + Ord>(&'a self, key: &Q) -> Option<&'a V>
273    where K: Borrow<Q> + 'a
274  {
275    match self.iter().find(|(k, _)| Borrow::<Q>::borrow(*k) == key) {
276      | Some((_, v)) => Some(v),
277      | None => None,
278    }
279  }
280
281  fn get_mut<'a, Q: Hash + Eq + Ord>(&'a mut self, key: &Q) -> Option<&'a mut V>
282    where K: Borrow<Q> + 'a
283  {
284    match self.iter_mut()
285              .find(|(k, _)| Borrow::<Q>::borrow(*k) == key)
286    {
287      | Some((_, v)) => Some(v),
288      | None => None,
289    }
290  }
291
292  fn iter(&self) -> Iter<'_, K, V> {
293    Iter { array_iter: Some(self.deref().iter().map(Iter::coerce_array_iter)),
294           #[cfg(feature = "alloc")]
295           btreemap_iter: None,
296           #[cfg(feature = "std")]
297           hashmap_iter: None }
298  }
299
300  fn iter_mut(&mut self) -> IterMut<'_, K, V> {
301    IterMut { array_iter: Some(self.deref_mut().iter_mut().map(IterMut::coerce_array_iter)),
302              #[cfg(feature = "alloc")]
303              btreemap_iter: None,
304              #[cfg(feature = "std")]
305              hashmap_iter: None }
306  }
307}
308
309type ArrayIterCoercer<'a, K, V> = fn(&'a (K, V)) -> (&'a K, &'a V);
310type ArrayIterMapped<'a, K, V> = iter::Map<slice::Iter<'a, (K, V)>, ArrayIterCoercer<'a, K, V>>;
311
312type ArrayIterMutCoercer<'a, K, V> = fn(&'a mut (K, V)) -> (&'a K, &'a mut V);
313type ArrayIterMutMapped<'a, K, V> =
314  iter::Map<slice::IterMut<'a, (K, V)>, ArrayIterMutCoercer<'a, K, V>>;
315
316/// An iterator over the entries of a `Map`.
317///
318/// This `struct` is created by the [`iter`] method on [`Map`].
319/// See its documentation for more.
320///
321/// [`iter`]: Map::iter
322///
323/// # Example
324///
325/// ```
326/// use std::collections::HashMap;
327///
328/// use toad_map::Map;
329///
330/// let mut map = HashMap::from([("a", 1)]);
331///
332/// fn do_stuff(map: &impl Map<&'static str, usize>) {
333///   let iter = map.iter();
334/// }
335/// ```
336#[derive(Debug)]
337pub struct Iter<'a, K: Eq + Hash, V> {
338  #[cfg(feature = "std")]
339  hashmap_iter: Option<hash_map::Iter<'a, K, V>>,
340  #[cfg(feature = "alloc")]
341  btreemap_iter: Option<btree_map::Iter<'a, K, V>>,
342  array_iter: Option<ArrayIterMapped<'a, K, V>>,
343}
344
345impl<'a, K: Eq + Hash, V> Iter<'a, K, V> {
346  #[inline(always)]
347  fn coerce_array_iter((k, v): &'a (K, V)) -> (&'a K, &'a V) {
348    (k, v)
349  }
350
351  #[allow(unreachable_code)]
352  fn get_iter(&mut self) -> &mut dyn Iterator<Item = (&'a K, &'a V)> {
353    #[cfg(feature = "std")]
354    {
355      let (a, b, c) = (self.hashmap_iter.as_mut().map(|a| a as &mut _),
356                       self.array_iter.as_mut().map(|a| a as &mut _),
357                       self.btreemap_iter.as_mut().map(|a| a as &mut _));
358      return a.or(b).or(c).unwrap();
359    };
360
361    #[cfg(feature = "alloc")]
362    {
363      let (a, b) = (self.array_iter.as_mut().map(|a| a as &mut _),
364                    self.btreemap_iter.as_mut().map(|a| a as &mut _));
365      return a.or(b).unwrap();
366    }
367
368    // no_std and no alloc; must be array
369    self.array_iter.as_mut().map(|a| a as &mut _).unwrap()
370  }
371}
372
373impl<'a, K: Eq + Hash, V> Iterator for Iter<'a, K, V> {
374  type Item = (&'a K, &'a V);
375
376  fn next(&mut self) -> Option<Self::Item> {
377    self.get_iter().next()
378  }
379}
380
381/// A mutable iterator over the entries of a `Map`.
382///
383/// This `struct` is created by the [`iter_mut`] method on [`Map`]. See its
384/// documentation for more.
385///
386/// [`iter_mut`]: Map::iter_mut
387///
388/// # Example
389///
390/// ```
391/// use std::collections::HashMap;
392///
393/// use toad_map::Map;
394///
395/// let mut map = HashMap::from([("a", 1)]);
396///
397/// fn do_stuff(map: &mut impl Map<&'static str, usize>) {
398///   let iter = map.iter_mut();
399/// }
400/// ```
401#[derive(Debug)]
402pub struct IterMut<'a, K: Eq + Hash, V> {
403  #[cfg(feature = "std")]
404  hashmap_iter: Option<hash_map::IterMut<'a, K, V>>,
405  #[cfg(feature = "alloc")]
406  btreemap_iter: Option<btree_map::IterMut<'a, K, V>>,
407  array_iter: Option<ArrayIterMutMapped<'a, K, V>>,
408}
409
410impl<'a, K: Eq + Hash, V> IterMut<'a, K, V> {
411  #[inline(always)]
412  fn coerce_array_iter((k, v): &'a mut (K, V)) -> (&'a K, &'a mut V) {
413    (k, v)
414  }
415
416  #[allow(unreachable_code)]
417  fn get_iter(&mut self) -> &mut dyn Iterator<Item = (&'a K, &'a mut V)> {
418    #[cfg(feature = "std")]
419    {
420      let (a, b, c) = (self.hashmap_iter.as_mut().map(|a| a as &mut _),
421                       self.array_iter.as_mut().map(|a| a as &mut _),
422                       self.btreemap_iter.as_mut().map(|a| a as &mut _));
423      return a.or(b).or(c).unwrap();
424    };
425
426    #[cfg(feature = "alloc")]
427    {
428      let (a, b) = (self.array_iter.as_mut().map(|a| a as &mut _),
429                    self.btreemap_iter.as_mut().map(|a| a as &mut _));
430      return a.or(b).unwrap();
431    }
432
433    // no_std and no alloc; must be array
434    self.array_iter.as_mut().map(|a| a as &mut _).unwrap()
435  }
436}
437
438impl<'a, K: Eq + Hash, V> Iterator for IterMut<'a, K, V> {
439  type Item = (&'a K, &'a mut V);
440
441  fn next(&mut self) -> Option<Self::Item> {
442    self.get_iter().next()
443  }
444}
445
446#[cfg(test)]
447mod tests {
448  use super::*;
449
450  fn impls(
451    )
452      -> (impl Map<String, String>,
453          impl Map<String, String>,
454          impl Map<String, String>,
455          impl Map<String, String>)
456  {
457    (HashMap::<String, String>::from([("foo".into(), "bar".into())]),
458     BTreeMap::<String, String>::from([("foo".into(), "bar".into())]),
459     tinyvec::array_vec!([(String, String); 16] => ("foo".into(), "bar".into())),
460     vec![("foo".to_string(), "bar".to_string())])
461  }
462
463  macro_rules! each_impl {
464    ($work:expr) => {{
465      let (hm, bt, av, vc) = impls();
466      println!("hashmap");
467      $work(hm);
468      println!("btreemap");
469      $work(bt);
470      println!("arrayvec");
471      $work(av);
472      println!("vec");
473      $work(vc);
474    }};
475  }
476
477  #[test]
478  fn get() {
479    fn test_get<M: Map<String, String>>(map: M) {
480      assert_eq!(map.get(&"foo".to_string()), Some(&"bar".into()));
481      assert_eq!(map.get(&"foot".to_string()), None);
482    }
483
484    each_impl!(test_get);
485  }
486
487  #[test]
488  fn get_mut() {
489    fn test_get_mut<M: Map<String, String>>(mut map: M) {
490      let old = map.get_mut(&"foo".to_string()).unwrap();
491      *old = format!("{}f", old);
492
493      assert_eq!(map.get(&"foo".to_string()), Some(&"barf".into()));
494    }
495
496    each_impl!(test_get_mut);
497  }
498
499  #[test]
500  fn insert() {
501    fn test_insert<M: Map<String, String>>(mut map: M) {
502      let old = map.insert("foot".to_string(), "butt".to_string());
503
504      assert_eq!(old, Ok(()));
505      assert_eq!(map.get(&"foo".to_string()).unwrap().as_str(), "bar");
506      assert_eq!(map.get(&"foot".to_string()).unwrap().as_str(), "butt");
507
508      let old = map.insert("foot".to_string(), "squat".to_string());
509      assert_eq!(old, Err(InsertError::Exists("butt".to_string())));
510      assert_eq!(map.get(&"foot".to_string()).unwrap().as_str(), "squat");
511    }
512
513    each_impl!(test_insert);
514  }
515
516  #[test]
517  fn remove() {
518    fn test_remove<M: Map<String, String>>(mut map: M) {
519      let old = map.remove(&"foo".to_string());
520      assert_eq!(old, Some("bar".to_string()));
521
522      let old = map.remove(&"foo".to_string());
523      assert_eq!(old, None);
524    }
525
526    each_impl!(test_remove);
527  }
528
529  #[test]
530  fn has() {
531    fn test_has<M: Map<String, String>>(map: M) {
532      assert!(map.has(&"foo".to_string()));
533      assert!(!map.has(&"foot".to_string()));
534    }
535
536    each_impl!(test_has);
537  }
538
539  #[test]
540  fn into_iter() {
541    fn test_into_iter<M: Map<String, String>>(mut map: M) {
542      map.insert("a".into(), "a".into()).unwrap();
543      map.insert("b".into(), "b".into()).unwrap();
544      map.insert("c".into(), "c".into()).unwrap();
545
546      let mut kvs = map.into_iter().collect::<Vec<_>>();
547      kvs.sort();
548
549      assert_eq!(kvs,
550                 vec![("a".into(), "a".into()),
551                      ("b".into(), "b".into()),
552                      ("c".into(), "c".into()),
553                      ("foo".into(), "bar".into()),]);
554    }
555
556    each_impl!(test_into_iter);
557  }
558
559  #[test]
560  fn iter() {
561    fn test_iter<M: Map<String, String>>(mut map: M) {
562      map.insert("a".into(), "a".into()).unwrap();
563      map.insert("b".into(), "b".into()).unwrap();
564      map.insert("c".into(), "c".into()).unwrap();
565
566      let mut kvs = map.iter().collect::<Vec<_>>();
567      kvs.sort();
568
569      assert_eq!(kvs,
570                 vec![(&"a".into(), &"a".into()),
571                      (&"b".into(), &"b".into()),
572                      (&"c".into(), &"c".into()),
573                      (&"foo".into(), &"bar".into()),]);
574    }
575
576    each_impl!(test_iter);
577  }
578
579  #[test]
580  fn iter_mut() {
581    fn test_iter_mut<M: Map<String, String>>(mut map: M) {
582      map.insert("a".into(), "a".into()).unwrap();
583      map.insert("b".into(), "b".into()).unwrap();
584      map.insert("c".into(), "c".into()).unwrap();
585
586      let mut kvs = map.iter_mut().collect::<Vec<_>>();
587      kvs.sort();
588
589      assert_eq!(kvs,
590                 vec![(&"a".into(), &mut "a".into()),
591                      (&"b".into(), &mut "b".into()),
592                      (&"c".into(), &mut "c".into()),
593                      (&"foo".into(), &mut "bar".into()),]);
594    }
595
596    each_impl!(test_iter_mut);
597  }
598}
toad_map/lib.rs

toad_map/
lib.rs
