small_map/
lib.rs

1#![allow(clippy::manual_map)]
2#![cfg_attr(feature = "nightly", allow(internal_features))]
3#![cfg_attr(feature = "nightly", feature(core_intrinsics))]
4
5//! A small inline SIMD-accelerated hashmap designed for small amounts of data.
6//!
7//! `SmallMap` stores data inline when the number of elements is small (up to N),
8//! and automatically spills to the heap when it grows beyond that threshold.
9//!
10//! # Examples
11//!
12//! ```
13//! use small_map::SmallMap;
14//!
15//! let mut map: SmallMap<8, &str, i32> = SmallMap::new();
16//! map.insert("a", 1);
17//! map.insert("b", 2);
18//!
19//! assert_eq!(map.get(&"a"), Some(&1));
20//! assert!(map.contains_key(&"b"));
21//! assert!(map.is_inline()); // Still stored inline
22//! ```
23
24use core::{
25    hash::{BuildHasher, Hash},
26    hint::unreachable_unchecked,
27    iter::FusedIterator,
28    ops::Index,
29};
30use std::{
31    collections::hash_map::RandomState,
32    fmt::{self, Debug},
33};
34
35use hashbrown::HashMap;
36use inline::Inline;
37
38#[macro_use]
39mod macros;
40mod inline;
41mod raw;
42
43pub use hashbrown::Equivalent;
44
45#[cfg(feature = "serde")]
46mod serde;
47
48#[cfg(feature = "fxhash")]
49pub type FxSmallMap<const N: usize, K, V> =
50    SmallMap<N, K, V, core::hash::BuildHasherDefault<rustc_hash::FxHasher>>;
51#[cfg(feature = "ahash")]
52pub type ASmallMap<const N: usize, K, V> =
53    SmallMap<N, K, V, core::hash::BuildHasherDefault<ahash::AHasher>>;
54
55#[derive(Clone)]
56pub enum SmallMap<const N: usize, K, V, S = RandomState> {
57    Heap(HashMap<K, V, S>),
58    Inline(Inline<N, K, V, S>),
59}
60
61impl<const N: usize, K, V, S> Debug for SmallMap<N, K, V, S>
62where
63    K: Debug,
64    V: Debug,
65{
66    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
67        f.debug_map().entries(self.iter()).finish()
68    }
69}
70
71impl<const N: usize, K, V, S: Default> Default for SmallMap<N, K, V, S> {
72    /// Creates an empty `SmallMap<N, K, V, S>`, with the `Default` value for the hasher.
73    ///
74    /// # Examples
75    ///
76    /// ```
77    /// use std::collections::hash_map::RandomState;
78    ///
79    /// use small_map::SmallMap;
80    ///
81    /// // You can specify all types of SmallMap, including N and hasher.
82    /// // Created map is empty and don't allocate memory
83    /// let map: SmallMap<8, u32, String> = SmallMap::default();
84    /// assert_eq!(map.capacity(), 8);
85    /// let map: SmallMap<8, u32, String, RandomState> = SmallMap::default();
86    /// assert_eq!(map.capacity(), 8);
87    /// ```
88    #[inline]
89    fn default() -> Self {
90        Self::with_hasher(Default::default())
91    }
92}
93
94impl<const N: usize, K, V, S: Default> SmallMap<N, K, V, S> {
95    /// Creates an empty `SmallMap`.
96    #[inline]
97    pub fn new() -> Self {
98        Self::with_hasher(Default::default())
99    }
100
101    /// Creates an empty `SmallMap` with the specified capacity.
102    ///
103    /// The hash map will be able to hold at least `capacity` elements without
104    /// reallocating. If `capacity` is smaller than N, the hash map will not allocate.
105    #[inline]
106    pub fn with_capacity(capacity: usize) -> Self {
107        if capacity > N {
108            Self::Heap(HashMap::with_capacity_and_hasher(
109                capacity,
110                Default::default(),
111            ))
112        } else {
113            Self::Inline(Inline::new(Default::default()))
114        }
115    }
116}
117
118impl<const N: usize, K, V, S> SmallMap<N, K, V, S> {
119    /// Creates an empty `SmallMap` which will use the given hash builder to hash
120    /// keys. It will be allocated with the given allocator.
121    ///
122    /// The hash map is initially created with a capacity of N, so it will not allocate until it
123    /// its size bigger than inline size N.
124    /// # Examples
125    ///
126    /// ```
127    /// use core::hash::BuildHasherDefault;
128    ///
129    /// use small_map::SmallMap;
130    ///
131    /// let s = BuildHasherDefault::<ahash::AHasher>::default();
132    /// let mut map = SmallMap::<8, _, _, _>::with_hasher(s);
133    /// map.insert(1, 2);
134    /// ```
135    #[inline]
136    pub const fn with_hasher(hash_builder: S) -> Self {
137        Self::Inline(Inline::new(hash_builder))
138    }
139
140    /// Creates an empty `SmallMap` with the specified capacity, using `hash_builder`
141    /// to hash the keys.
142    ///
143    /// The hash map will be able to hold at least `capacity` elements without
144    /// reallocating. If `capacity` is smaller than or eq to N, the hash map will not allocate.
145    #[inline]
146    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
147        if capacity > N {
148            Self::Heap(HashMap::with_capacity_and_hasher(capacity, hash_builder))
149        } else {
150            Self::Inline(Inline::new(hash_builder))
151        }
152    }
153
154    /// What branch it is now.
155    #[inline]
156    pub fn is_inline(&self) -> bool {
157        matches!(self, Self::Inline(..))
158    }
159
160    /// Returns the number of elements the map can hold without reallocating.
161    ///
162    /// This number is a lower bound; the `SmallMap<N, K, V>` might be able to hold
163    /// more, but is guaranteed to be able to hold at least this many.
164    ///
165    /// # Examples
166    ///
167    /// ```
168    /// use small_map::SmallMap;
169    ///
170    /// let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(100);
171    /// assert_eq!(map.len(), 0);
172    /// assert!(map.capacity() >= 100);
173    ///
174    /// let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(2);
175    /// assert_eq!(map.len(), 0);
176    /// assert!(map.capacity() >= 8);
177    /// ```
178    #[inline]
179    pub fn capacity(&self) -> usize {
180        match self {
181            SmallMap::Heap(inner) => inner.capacity(),
182            SmallMap::Inline(_) => N,
183        }
184    }
185}
186
187impl<const N: usize, K, V, S> SmallMap<N, K, V, S>
188where
189    K: Eq + Hash,
190    S: BuildHasher,
191{
192    /// Returns a reference to the value corresponding to the key.
193    ///
194    /// # Examples
195    ///
196    /// ```
197    /// use small_map::SmallMap;
198    ///
199    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
200    /// map.insert(1, "a");
201    /// assert_eq!(map.get(&1), Some(&"a"));
202    /// assert_eq!(map.get(&2), None);
203    /// ```
204    #[inline]
205    pub fn get<Q>(&self, k: &Q) -> Option<&V>
206    where
207        Q: ?Sized + Hash + Equivalent<K>,
208    {
209        match self {
210            SmallMap::Heap(inner) => inner.get(k),
211            SmallMap::Inline(inner) => inner.get(k),
212        }
213    }
214
215    /// Returns a mutable reference to the value corresponding to the key.
216    ///
217    /// # Examples
218    ///
219    /// ```
220    /// use small_map::SmallMap;
221    ///
222    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
223    /// map.insert(1, 10);
224    /// if let Some(v) = map.get_mut(&1) {
225    ///     *v = 20;
226    /// }
227    /// assert_eq!(map.get(&1), Some(&20));
228    /// ```
229    #[inline]
230    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
231    where
232        Q: ?Sized + Hash + Equivalent<K>,
233    {
234        match self {
235            SmallMap::Heap(inner) => inner.get_mut(k),
236            SmallMap::Inline(inner) => inner.get_mut(k),
237        }
238    }
239
240    /// Returns the key-value pair corresponding to the supplied key.
241    ///
242    /// # Examples
243    ///
244    /// ```
245    /// use small_map::SmallMap;
246    ///
247    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
248    /// map.insert(1, "a");
249    /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
250    /// assert_eq!(map.get_key_value(&2), None);
251    /// ```
252    #[inline]
253    pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
254    where
255        Q: ?Sized + Hash + Equivalent<K>,
256    {
257        match self {
258            SmallMap::Heap(inner) => inner.get_key_value(k),
259            SmallMap::Inline(inner) => inner.get_key_value(k),
260        }
261    }
262
263    /// Returns `true` if the map contains a value for the specified key.
264    ///
265    /// # Examples
266    ///
267    /// ```
268    /// use small_map::SmallMap;
269    ///
270    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
271    /// map.insert(1, "a");
272    /// assert!(map.contains_key(&1));
273    /// assert!(!map.contains_key(&2));
274    /// ```
275    #[inline]
276    pub fn contains_key<Q>(&self, k: &Q) -> bool
277    where
278        Q: ?Sized + Hash + Equivalent<K>,
279    {
280        self.get(k).is_some()
281    }
282
283    /// Inserts a key-value pair into the map.
284    ///
285    /// If the map did not have this key present, `None` is returned.
286    /// If the map did have this key present, the value is updated, and the old value is returned.
287    ///
288    /// # Examples
289    ///
290    /// ```
291    /// use small_map::SmallMap;
292    ///
293    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
294    /// assert_eq!(map.insert(1, "a"), None);
295    /// assert_eq!(map.insert(1, "b"), Some("a"));
296    /// assert_eq!(map.get(&1), Some(&"b"));
297    /// ```
298    #[inline]
299    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
300        match self {
301            SmallMap::Heap(inner) => inner.insert(key, value),
302            SmallMap::Inline(inner) => {
303                if raw::util::likely(!inner.is_full()) {
304                    return inner.insert(key, value);
305                }
306                let heap = HashMap::with_capacity_and_hasher(N + 1, unsafe { inner.take_hasher() });
307
308                let heap = match core::mem::replace(self, SmallMap::Heap(heap)) {
309                    SmallMap::Heap(_) => unsafe { unreachable_unchecked() },
310                    SmallMap::Inline(inline) => {
311                        let heap = match self {
312                            SmallMap::Heap(heap) => heap,
313                            SmallMap::Inline(_) => unsafe { unreachable_unchecked() },
314                        };
315                        for (k, v) in inline.into_iter() {
316                            // SAFETY: We're moving elements from inline storage to heap.
317                            // All keys are unique because they came from a valid map.
318                            unsafe { heap.insert_unique_unchecked(k, v) };
319                        }
320                        heap
321                    }
322                };
323                heap.insert(key, value)
324            }
325        }
326    }
327
328    /// Removes a key from the map, returning the value at the key if the key was previously in the
329    /// map.
330    ///
331    /// # Examples
332    ///
333    /// ```
334    /// use small_map::SmallMap;
335    ///
336    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
337    /// map.insert(1, "a");
338    /// assert_eq!(map.remove(&1), Some("a"));
339    /// assert_eq!(map.remove(&1), None);
340    /// ```
341    #[inline]
342    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
343    where
344        Q: ?Sized + Hash + Equivalent<K>,
345    {
346        // Avoid `Option::map` because it bloats LLVM IR.
347        match self.remove_entry(k) {
348            Some((_, v)) => Some(v),
349            None => None,
350        }
351    }
352
353    /// Removes a key from the map, returning the stored key and value if the key was previously in
354    /// the map.
355    ///
356    /// # Examples
357    ///
358    /// ```
359    /// use small_map::SmallMap;
360    ///
361    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
362    /// map.insert(1, "a");
363    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
364    /// assert_eq!(map.remove_entry(&1), None);
365    /// ```
366    #[inline]
367    pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
368    where
369        Q: ?Sized + Hash + Equivalent<K>,
370    {
371        match self {
372            SmallMap::Heap(inner) => inner.remove_entry(k),
373            SmallMap::Inline(inner) => inner.remove_entry(k),
374        }
375    }
376
377    /// Retains only the elements specified by the predicate.
378    ///
379    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
380    ///
381    /// # Examples
382    ///
383    /// ```
384    /// use small_map::SmallMap;
385    ///
386    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
387    /// for i in 0..8 {
388    ///     map.insert(i, i * 10);
389    /// }
390    /// map.retain(|&k, _| k % 2 == 0);
391    /// assert_eq!(map.len(), 4);
392    /// ```
393    #[inline]
394    pub fn retain<F>(&mut self, mut f: F)
395    where
396        F: FnMut(&K, &mut V) -> bool,
397    {
398        match self {
399            SmallMap::Heap(inner) => inner.retain(f),
400            SmallMap::Inline(inner) => inner.retain(&mut f),
401        }
402    }
403}
404
405impl<const N: usize, K, V, S> SmallMap<N, K, V, S>
406where
407    S: Clone,
408{
409    /// Clears the map.
410    ///
411    /// This method clears the map as resets it to the Inline state.
412    ///
413    /// # Examples
414    ///
415    /// ```
416    /// use small_map::SmallMap;
417    ///
418    /// let mut map: SmallMap<8, i32, ()> = SmallMap::new();
419    /// for i in 0..16 {
420    ///     map.insert(i, ());
421    /// }
422    /// assert!(!map.is_inline());
423    /// assert_eq!(map.len(), 16);
424    ///
425    /// map.clear();
426    /// assert!(map.is_inline());
427    /// assert_eq!(map.len(), 0);
428    /// ```
429    #[inline]
430    pub fn clear(&mut self) {
431        let hash_builder = match self {
432            // Too bad there's no HashMap::take_hasher()
433            SmallMap::Heap(inner) => inner.hasher().clone(),
434            // Safety: We're about to destroy this inner, so it doesn't need its hasher
435            SmallMap::Inline(inner) => unsafe { inner.take_hasher() },
436        };
437        *self = Self::Inline(Inline::new(hash_builder))
438    }
439}
440
441pub enum Iter<'a, const N: usize, K, V> {
442    Heap(hashbrown::hash_map::Iter<'a, K, V>),
443    Inline(inline::Iter<'a, N, K, V>),
444}
445
446impl<'a, const N: usize, K, V> Iterator for Iter<'a, N, K, V> {
447    type Item = (&'a K, &'a V);
448
449    #[inline]
450    fn next(&mut self) -> Option<(&'a K, &'a V)> {
451        match self {
452            Iter::Heap(inner) => inner.next(),
453            Iter::Inline(inner) => inner.next(),
454        }
455    }
456    #[inline]
457    fn size_hint(&self) -> (usize, Option<usize>) {
458        match self {
459            Iter::Heap(inner) => inner.size_hint(),
460            Iter::Inline(inner) => inner.size_hint(),
461        }
462    }
463}
464
465impl<const N: usize, K, V> ExactSizeIterator for Iter<'_, N, K, V> {
466    #[inline]
467    fn len(&self) -> usize {
468        match self {
469            Iter::Heap(inner) => inner.len(),
470            Iter::Inline(inner) => inner.len(),
471        }
472    }
473}
474
475impl<const N: usize, K, V> FusedIterator for Iter<'_, N, K, V> {}
476
477/// An iterator over the keys of a `SmallMap`.
478pub struct Keys<'a, const N: usize, K, V> {
479    inner: Iter<'a, N, K, V>,
480}
481
482impl<'a, const N: usize, K, V> Iterator for Keys<'a, N, K, V> {
483    type Item = &'a K;
484
485    #[inline]
486    fn next(&mut self) -> Option<&'a K> {
487        match self.inner.next() {
488            Some((k, _)) => Some(k),
489            None => None,
490        }
491    }
492
493    #[inline]
494    fn size_hint(&self) -> (usize, Option<usize>) {
495        self.inner.size_hint()
496    }
497}
498
499impl<const N: usize, K, V> ExactSizeIterator for Keys<'_, N, K, V> {
500    #[inline]
501    fn len(&self) -> usize {
502        self.inner.len()
503    }
504}
505
506impl<const N: usize, K, V> FusedIterator for Keys<'_, N, K, V> {}
507
508/// An iterator over the values of a `SmallMap`.
509pub struct Values<'a, const N: usize, K, V> {
510    inner: Iter<'a, N, K, V>,
511}
512
513impl<'a, const N: usize, K, V> Iterator for Values<'a, N, K, V> {
514    type Item = &'a V;
515
516    #[inline]
517    fn next(&mut self) -> Option<&'a V> {
518        match self.inner.next() {
519            Some((_, v)) => Some(v),
520            None => None,
521        }
522    }
523
524    #[inline]
525    fn size_hint(&self) -> (usize, Option<usize>) {
526        self.inner.size_hint()
527    }
528}
529
530impl<const N: usize, K, V> ExactSizeIterator for Values<'_, N, K, V> {
531    #[inline]
532    fn len(&self) -> usize {
533        self.inner.len()
534    }
535}
536
537impl<const N: usize, K, V> FusedIterator for Values<'_, N, K, V> {}
538
539/// A consuming iterator over the keys of a `SmallMap`.
540pub struct IntoKeys<const N: usize, K, V> {
541    inner: IntoIter<N, K, V>,
542}
543
544impl<const N: usize, K, V> Iterator for IntoKeys<N, K, V> {
545    type Item = K;
546
547    #[inline]
548    fn next(&mut self) -> Option<K> {
549        match self.inner.next() {
550            Some((k, _)) => Some(k),
551            None => None,
552        }
553    }
554
555    #[inline]
556    fn size_hint(&self) -> (usize, Option<usize>) {
557        self.inner.size_hint()
558    }
559}
560
561impl<const N: usize, K, V> ExactSizeIterator for IntoKeys<N, K, V> {
562    #[inline]
563    fn len(&self) -> usize {
564        self.inner.len()
565    }
566}
567
568impl<const N: usize, K, V> FusedIterator for IntoKeys<N, K, V> {}
569
570/// A consuming iterator over the values of a `SmallMap`.
571pub struct IntoValues<const N: usize, K, V> {
572    inner: IntoIter<N, K, V>,
573}
574
575impl<const N: usize, K, V> Iterator for IntoValues<N, K, V> {
576    type Item = V;
577
578    #[inline]
579    fn next(&mut self) -> Option<V> {
580        match self.inner.next() {
581            Some((_, v)) => Some(v),
582            None => None,
583        }
584    }
585
586    #[inline]
587    fn size_hint(&self) -> (usize, Option<usize>) {
588        self.inner.size_hint()
589    }
590}
591
592impl<const N: usize, K, V> ExactSizeIterator for IntoValues<N, K, V> {
593    #[inline]
594    fn len(&self) -> usize {
595        self.inner.len()
596    }
597}
598
599impl<const N: usize, K, V> FusedIterator for IntoValues<N, K, V> {}
600
601pub enum IntoIter<const N: usize, K, V> {
602    Heap(hashbrown::hash_map::IntoIter<K, V>),
603    Inline(inline::IntoIter<N, K, V>),
604}
605
606impl<const N: usize, K, V> Iterator for IntoIter<N, K, V> {
607    type Item = (K, V);
608
609    #[inline]
610    fn next(&mut self) -> Option<(K, V)> {
611        match self {
612            IntoIter::Heap(inner) => inner.next(),
613            IntoIter::Inline(inner) => inner.next(),
614        }
615    }
616    #[inline]
617    fn size_hint(&self) -> (usize, Option<usize>) {
618        match self {
619            IntoIter::Heap(inner) => inner.size_hint(),
620            IntoIter::Inline(inner) => inner.size_hint(),
621        }
622    }
623}
624impl<const N: usize, K, V> ExactSizeIterator for IntoIter<N, K, V> {
625    #[inline]
626    fn len(&self) -> usize {
627        match self {
628            IntoIter::Heap(inner) => inner.len(),
629            IntoIter::Inline(inner) => inner.len(),
630        }
631    }
632}
633impl<const N: usize, K, V> FusedIterator for IntoIter<N, K, V> {}
634
635impl<const N: usize, K, V, S> IntoIterator for SmallMap<N, K, V, S> {
636    type Item = (K, V);
637    type IntoIter = IntoIter<N, K, V>;
638
639    /// Creates a consuming iterator, that is, one that moves each key-value
640    /// pair out of the map in arbitrary order. The map cannot be used after
641    /// calling this.
642    #[inline]
643    fn into_iter(self) -> IntoIter<N, K, V> {
644        match self {
645            SmallMap::Heap(inner) => IntoIter::Heap(inner.into_iter()),
646            SmallMap::Inline(inner) => IntoIter::Inline(inner.into_iter()),
647        }
648    }
649}
650
651impl<'a, const N: usize, K, V, S> IntoIterator for &'a SmallMap<N, K, V, S> {
652    type Item = (&'a K, &'a V);
653    type IntoIter = Iter<'a, N, K, V>;
654
655    /// Creates an iterator over the entries of a `HashMap` in arbitrary order.
656    /// The iterator element type is `(&'a K, &'a V)`.
657    #[inline]
658    fn into_iter(self) -> Iter<'a, N, K, V> {
659        match self {
660            SmallMap::Heap(inner) => Iter::Heap(inner.iter()),
661            SmallMap::Inline(inner) => Iter::Inline(inner.iter()),
662        }
663    }
664}
665
666impl<const N: usize, K, V, S> SmallMap<N, K, V, S> {
667    /// Returns the number of elements in the map.
668    ///
669    /// # Examples
670    ///
671    /// ```
672    /// use small_map::SmallMap;
673    ///
674    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
675    /// assert_eq!(map.len(), 0);
676    /// map.insert(1, 10);
677    /// assert_eq!(map.len(), 1);
678    /// ```
679    #[inline]
680    pub fn len(&self) -> usize {
681        match self {
682            SmallMap::Heap(inner) => inner.len(),
683            SmallMap::Inline(inner) => inner.len(),
684        }
685    }
686
687    /// Returns `true` if the map contains no elements.
688    ///
689    /// # Examples
690    ///
691    /// ```
692    /// use small_map::SmallMap;
693    ///
694    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
695    /// assert!(map.is_empty());
696    /// map.insert(1, 10);
697    /// assert!(!map.is_empty());
698    /// ```
699    #[inline]
700    pub fn is_empty(&self) -> bool {
701        match self {
702            SmallMap::Heap(inner) => inner.is_empty(),
703            SmallMap::Inline(inner) => inner.is_empty(),
704        }
705    }
706
707    /// An iterator visiting all key-value pairs in arbitrary order.
708    ///
709    /// # Examples
710    ///
711    /// ```
712    /// use small_map::SmallMap;
713    ///
714    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
715    /// map.insert("a", 1);
716    /// map.insert("b", 2);
717    ///
718    /// for (key, val) in map.iter() {
719    ///     println!("key: {key} val: {val}");
720    /// }
721    /// ```
722    #[inline]
723    pub fn iter(&self) -> Iter<'_, N, K, V> {
724        match self {
725            SmallMap::Heap(inner) => Iter::Heap(inner.iter()),
726            SmallMap::Inline(inner) => Iter::Inline(inner.iter()),
727        }
728    }
729
730    /// An iterator visiting all keys in arbitrary order.
731    ///
732    /// # Examples
733    ///
734    /// ```
735    /// use small_map::SmallMap;
736    ///
737    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
738    /// map.insert("a", 1);
739    /// map.insert("b", 2);
740    ///
741    /// for key in map.keys() {
742    ///     println!("{key}");
743    /// }
744    /// ```
745    #[inline]
746    pub fn keys(&self) -> Keys<'_, N, K, V> {
747        Keys { inner: self.iter() }
748    }
749
750    /// An iterator visiting all values in arbitrary order.
751    ///
752    /// # Examples
753    ///
754    /// ```
755    /// use small_map::SmallMap;
756    ///
757    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
758    /// map.insert("a", 1);
759    /// map.insert("b", 2);
760    ///
761    /// for val in map.values() {
762    ///     println!("{val}");
763    /// }
764    /// ```
765    #[inline]
766    pub fn values(&self) -> Values<'_, N, K, V> {
767        Values { inner: self.iter() }
768    }
769
770    /// Creates a consuming iterator visiting all the keys in arbitrary order.
771    ///
772    /// # Examples
773    ///
774    /// ```
775    /// use small_map::SmallMap;
776    ///
777    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
778    /// map.insert("a", 1);
779    /// map.insert("b", 2);
780    ///
781    /// let keys: Vec<_> = map.into_keys().collect();
782    /// ```
783    #[inline]
784    pub fn into_keys(self) -> IntoKeys<N, K, V> {
785        IntoKeys {
786            inner: self.into_iter(),
787        }
788    }
789
790    /// Creates a consuming iterator visiting all the values in arbitrary order.
791    ///
792    /// # Examples
793    ///
794    /// ```
795    /// use small_map::SmallMap;
796    ///
797    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
798    /// map.insert("a", 1);
799    /// map.insert("b", 2);
800    ///
801    /// let values: Vec<_> = map.into_values().collect();
802    /// ```
803    #[inline]
804    pub fn into_values(self) -> IntoValues<N, K, V> {
805        IntoValues {
806            inner: self.into_iter(),
807        }
808    }
809}
810
811// PartialEq implementation
812impl<const N: usize, K, V, S> PartialEq for SmallMap<N, K, V, S>
813where
814    K: Eq + Hash,
815    V: PartialEq,
816    S: BuildHasher,
817{
818    fn eq(&self, other: &Self) -> bool {
819        if self.len() != other.len() {
820            return false;
821        }
822        self.iter()
823            .all(|(key, value)| other.get(key) == Some(value))
824    }
825}
826
827impl<const N: usize, K, V, S> Eq for SmallMap<N, K, V, S>
828where
829    K: Eq + Hash,
830    V: Eq,
831    S: BuildHasher,
832{
833}
834
835// Index implementation
836impl<const N: usize, K, V, S, Q> Index<&Q> for SmallMap<N, K, V, S>
837where
838    K: Eq + Hash,
839    Q: ?Sized + Hash + Equivalent<K>,
840    S: BuildHasher,
841{
842    type Output = V;
843
844    /// Returns a reference to the value corresponding to the supplied key.
845    ///
846    /// # Panics
847    ///
848    /// Panics if the key is not present in the `SmallMap`.
849    #[inline]
850    fn index(&self, key: &Q) -> &V {
851        self.get(key).expect("no entry found for key")
852    }
853}
854
855// Extend implementation
856impl<const N: usize, K, V, S> Extend<(K, V)> for SmallMap<N, K, V, S>
857where
858    K: Eq + Hash,
859    S: BuildHasher,
860{
861    #[inline]
862    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
863        for (k, v) in iter {
864            self.insert(k, v);
865        }
866    }
867}
868
869// FromIterator implementation
870impl<const N: usize, K, V, S> FromIterator<(K, V)> for SmallMap<N, K, V, S>
871where
872    K: Eq + Hash,
873    S: BuildHasher + Default,
874{
875    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
876        let mut map = SmallMap::new();
877        map.extend(iter);
878        map
879    }
880}
881
882#[cfg(test)]
883mod tests {
884    use std::{cell::RefCell, rc::Rc};
885
886    use ahash::RandomState;
887    use hashbrown::HashMap;
888    use rand::Rng;
889
890    use crate::SmallMap;
891
892    #[test]
893    fn basic_op() {
894        let mut map = SmallMap::<16, String, String>::default();
895        map.insert("hello".to_string(), "world".to_string());
896        assert_eq!(map.len(), 1);
897        assert_eq!(map.get("hello").unwrap(), "world");
898        map.insert("hello2".to_string(), "world2".to_string());
899        assert_eq!(map.get("hello2").unwrap(), "world2");
900        assert_eq!(map.len(), 2);
901
902        assert_eq!(
903            map.remove_entry("hello").unwrap(),
904            ("hello".to_string(), "world".to_string())
905        );
906        assert_eq!(map.len(), 1);
907        assert_eq!(map.get("hello2").unwrap(), "world2");
908        assert_eq!(map.remove("hello2").unwrap(), "world2".to_string());
909        assert_eq!(map.len(), 0);
910        assert!(map.get("hello").is_none());
911
912        map.insert("hello3".to_string(), "world3".to_string());
913        map.insert("hello4".to_string(), "world4".to_string());
914        assert_eq!(map.len(), 2);
915        map.clear();
916        assert_eq!(map.len(), 0);
917        assert!(map.get("hello3").is_none());
918        assert!(map.get("hello4").is_none());
919    }
920
921    #[test]
922    fn multi_group_with_padding() {
923        let mut map = SmallMap::<33, i32, i32>::default();
924        for i in 0..33 {
925            map.insert(i, i * 2);
926        }
927        for i in 0..33 {
928            assert_eq!(*map.get(&i).unwrap(), i * 2);
929        }
930        assert!(map.is_inline());
931
932        for i in 33..64 {
933            map.insert(i, i * 2);
934        }
935        assert!(!map.is_inline());
936        for i in 0..64 {
937            assert_eq!(*map.get(&i).unwrap(), i * 2);
938        }
939    }
940
941    #[test]
942    fn clear_to_inline() {
943        let mut map = SmallMap::<16, i32, i32>::default();
944        for i in 0..32 {
945            map.insert(i, i * 2);
946        }
947        assert!(!map.is_inline());
948        map.clear();
949        assert!(map.is_inline());
950    }
951
952    #[test]
953    fn fuzzing() {
954        let mut smallmap = SmallMap::<16, i32, i32>::default();
955        let mut hashmap = HashMap::<i32, i32, RandomState>::default();
956        for _ in 0..1000000 {
957            let op = Operation::random();
958            op.exec(&mut smallmap, &mut hashmap);
959        }
960
961        enum Operation {
962            Insert(i32, i32),
963            Remove(i32),
964            Get(i32),
965            ModifyIfExist(i32, i32),
966        }
967        impl Operation {
968            fn random() -> Self {
969                let mut rng = rand::rng();
970
971                let choice: u8 = rng.random();
972                match choice % 4 {
973                    0 => Operation::Insert(rng.random_range(0..32), rng.random()),
974                    1 => Operation::Remove(rng.random_range(0..32)),
975                    2 => Operation::Get(rng.random_range(0..32)),
976                    3 => Operation::ModifyIfExist(rng.random_range(0..32), rng.random()),
977                    _ => unreachable!(),
978                }
979            }
980
981            fn exec<const N: usize, S1: core::hash::BuildHasher, S2: core::hash::BuildHasher>(
982                self,
983                sm: &mut SmallMap<N, i32, i32, S1>,
984                hm: &mut HashMap<i32, i32, S2>,
985            ) {
986                match self {
987                    Operation::Insert(k, v) => {
988                        if sm.len() == sm.capacity() {
989                            return;
990                        }
991                        assert_eq!(sm.insert(k, v), hm.insert(k, v));
992                        assert!(sm.is_inline());
993                    }
994                    Operation::Remove(k) => {
995                        assert_eq!(sm.remove(&k), hm.remove(&k));
996                    }
997                    Operation::Get(k) => {
998                        assert_eq!(sm.get(&k), hm.get(&k));
999                    }
1000                    Operation::ModifyIfExist(k, nv) => {
1001                        let (sv, hv) = (sm.get_mut(&k), hm.get_mut(&k));
1002                        assert_eq!(sv, hv);
1003                        if let Some(v) = sv {
1004                            *v = nv;
1005                        }
1006                        if let Some(v) = hv {
1007                            *v = nv;
1008                        }
1009                    }
1010                }
1011            }
1012        }
1013    }
1014
1015    #[test]
1016    fn drop_chk() {
1017        let (probe1, checker1) = drop_checker();
1018        let (probe2, checker2) = drop_checker();
1019        let (probe3, checker3) = drop_checker();
1020        let mut map = SmallMap::<8, _, _>::default();
1021        map.insert(1, probe1);
1022        map.insert(2, probe2);
1023        map.insert(3, probe3);
1024        assert_eq!(map.len(), 3);
1025        let mut it = map.into_iter();
1026        drop(it.next());
1027        drop(it);
1028        checker1.assert_drop();
1029        checker2.assert_drop();
1030        checker3.assert_drop();
1031
1032        fn drop_checker() -> (DropProbe, DropChecker) {
1033            let flag = Rc::new(RefCell::new(false));
1034            (DropProbe { flag: flag.clone() }, DropChecker { flag })
1035        }
1036
1037        struct DropChecker {
1038            flag: Rc<RefCell<bool>>,
1039        }
1040
1041        impl DropChecker {
1042            fn assert_drop(self) {
1043                assert!(*self.flag.borrow())
1044            }
1045        }
1046
1047        struct DropProbe {
1048            flag: Rc<RefCell<bool>>,
1049        }
1050
1051        impl Drop for DropProbe {
1052            fn drop(&mut self) {
1053                *self.flag.borrow_mut() = true;
1054            }
1055        }
1056    }
1057
1058    #[test]
1059    fn clone_after_delete() {
1060        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1061
1062        map.insert(1, "one".to_string());
1063        map.insert(2, "two".to_string());
1064        map.insert(3, "three".to_string());
1065
1066        assert_eq!(map.len(), 3);
1067        assert!(map.is_inline());
1068
1069        map.remove(&2);
1070        assert_eq!(map.len(), 2);
1071
1072        let cloned = map.clone();
1073
1074        assert_eq!(cloned.len(), 2);
1075        assert_eq!(cloned.get(&1), Some(&"one".to_string()));
1076        assert_eq!(cloned.get(&3), Some(&"three".to_string()));
1077        assert_eq!(cloned.get(&2), None);
1078
1079        let mut count = 0;
1080        for _ in cloned.iter() {
1081            count += 1;
1082        }
1083        assert_eq!(count, 2);
1084    }
1085
1086    #[test]
1087    fn clone_after_multiple_deletes() {
1088        let mut map: SmallMap<16, i32, i32> = SmallMap::new();
1089
1090        for i in 0..10 {
1091            map.insert(i, i * 100);
1092        }
1093        assert_eq!(map.len(), 10);
1094
1095        for i in (0..10).step_by(2) {
1096            map.remove(&i);
1097        }
1098        assert_eq!(map.len(), 5);
1099
1100        let cloned = map.clone();
1101        assert_eq!(cloned.len(), 5);
1102
1103        for i in (1..10).step_by(2) {
1104            assert_eq!(cloned.get(&i), Some(&(i * 100)));
1105        }
1106
1107        for i in (0..10).step_by(2) {
1108            assert_eq!(cloned.get(&i), None);
1109        }
1110
1111        let collected: Vec<_> = cloned.iter().collect();
1112        assert_eq!(collected.len(), 5);
1113    }
1114
1115    #[test]
1116    fn insert_into_cloned_after_delete() {
1117        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1118
1119        map.insert(1, "one".to_string());
1120        map.insert(2, "two".to_string());
1121        map.insert(3, "three".to_string());
1122
1123        map.remove(&2);
1124
1125        let mut cloned = map.clone();
1126
1127        cloned.insert(4, "four".to_string());
1128
1129        assert_eq!(cloned.len(), 3);
1130        assert_eq!(cloned.get(&1), Some(&"one".to_string()));
1131        assert_eq!(cloned.get(&3), Some(&"three".to_string()));
1132        assert_eq!(cloned.get(&4), Some(&"four".to_string()));
1133    }
1134
1135    #[test]
1136    fn into_iter_cloned_after_delete() {
1137        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1138
1139        map.insert(1, "one".to_string());
1140        map.insert(2, "two".to_string());
1141        map.insert(3, "three".to_string());
1142
1143        map.remove(&2);
1144
1145        let cloned = map.clone();
1146
1147        let items: Vec<_> = cloned.into_iter().collect();
1148        assert_eq!(items.len(), 2);
1149    }
1150
1151    #[test]
1152    fn clone_compaction() {
1153        // Test that clone compacts the data array
1154        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1155
1156        // Fill with gaps: insert 0-7, then delete evens
1157        for i in 0..8 {
1158            map.insert(i, i * 10);
1159        }
1160        for i in (0..8).step_by(2) {
1161            map.remove(&i);
1162        }
1163
1164        // Clone should compact: 4 elements at indices 0-3
1165        let cloned = map.clone();
1166        assert_eq!(cloned.len(), 4);
1167
1168        // Verify all odd keys are present
1169        for i in (1..8).step_by(2) {
1170            assert_eq!(cloned.get(&i), Some(&(i * 10)));
1171        }
1172
1173        // Insert into cloned should work correctly
1174        let mut cloned = cloned;
1175        cloned.insert(100, 1000);
1176        assert_eq!(cloned.len(), 5);
1177        assert_eq!(cloned.get(&100), Some(&1000));
1178    }
1179
1180    #[test]
1181    fn clone_empty_after_delete_all() {
1182        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1183
1184        map.insert(1, 10);
1185        map.insert(2, 20);
1186        map.remove(&1);
1187        map.remove(&2);
1188
1189        assert_eq!(map.len(), 0);
1190
1191        let cloned = map.clone();
1192        assert_eq!(cloned.len(), 0);
1193        assert!(cloned.is_empty());
1194
1195        // Should be able to insert into cloned empty map
1196        let mut cloned = cloned;
1197        cloned.insert(3, 30);
1198        assert_eq!(cloned.get(&3), Some(&30));
1199    }
1200
1201    #[test]
1202    fn contains_key_test() {
1203        let mut map: SmallMap<8, i32, &str> = SmallMap::new();
1204        map.insert(1, "a");
1205        map.insert(2, "b");
1206
1207        assert!(map.contains_key(&1));
1208        assert!(map.contains_key(&2));
1209        assert!(!map.contains_key(&3));
1210
1211        map.remove(&1);
1212        assert!(!map.contains_key(&1));
1213    }
1214
1215    #[test]
1216    fn keys_values_test() {
1217        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1218        for i in 0..5 {
1219            map.insert(i, i * 10);
1220        }
1221
1222        let keys: Vec<_> = map.keys().cloned().collect();
1223        assert_eq!(keys.len(), 5);
1224        for i in 0..5 {
1225            assert!(keys.contains(&i));
1226        }
1227
1228        let values: Vec<_> = map.values().cloned().collect();
1229        assert_eq!(values.len(), 5);
1230        for i in 0..5 {
1231            assert!(values.contains(&(i * 10)));
1232        }
1233    }
1234
1235    #[test]
1236    fn into_keys_values_test() {
1237        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1238        for i in 0..5 {
1239            map.insert(i, i * 10);
1240        }
1241
1242        let keys: Vec<_> = map.clone().into_keys().collect();
1243        assert_eq!(keys.len(), 5);
1244
1245        let values: Vec<_> = map.into_values().collect();
1246        assert_eq!(values.len(), 5);
1247    }
1248
1249    #[test]
1250    fn retain_test() {
1251        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1252        for i in 0..8 {
1253            map.insert(i, i * 10);
1254        }
1255
1256        map.retain(|&k, _| k % 2 == 0);
1257        assert_eq!(map.len(), 4);
1258
1259        for i in (0..8).step_by(2) {
1260            assert!(map.contains_key(&i));
1261        }
1262        for i in (1..8).step_by(2) {
1263            assert!(!map.contains_key(&i));
1264        }
1265    }
1266
1267    #[test]
1268    fn partial_eq_test() {
1269        let mut map1: SmallMap<8, i32, i32> = SmallMap::new();
1270        let mut map2: SmallMap<8, i32, i32> = SmallMap::new();
1271
1272        map1.insert(1, 10);
1273        map1.insert(2, 20);
1274
1275        map2.insert(2, 20);
1276        map2.insert(1, 10);
1277
1278        assert_eq!(map1, map2);
1279
1280        map2.insert(3, 30);
1281        assert_ne!(map1, map2);
1282    }
1283
1284    #[test]
1285    fn index_test() {
1286        let mut map: SmallMap<8, i32, &str> = SmallMap::new();
1287        map.insert(1, "a");
1288        map.insert(2, "b");
1289
1290        assert_eq!(map[&1], "a");
1291        assert_eq!(map[&2], "b");
1292    }
1293
1294    #[test]
1295    #[should_panic(expected = "no entry found for key")]
1296    fn index_panic_test() {
1297        let map: SmallMap<8, i32, &str> = SmallMap::new();
1298        let _ = map[&1];
1299    }
1300
1301    #[test]
1302    fn extend_test() {
1303        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1304        map.insert(1, 10);
1305
1306        map.extend([(2, 20), (3, 30)]);
1307        assert_eq!(map.len(), 3);
1308        assert_eq!(map.get(&2), Some(&20));
1309        assert_eq!(map.get(&3), Some(&30));
1310    }
1311
1312    #[test]
1313    fn from_iterator_test() {
1314        let map: SmallMap<8, i32, i32> = [(1, 10), (2, 20), (3, 30)].into_iter().collect();
1315        assert_eq!(map.len(), 3);
1316        assert_eq!(map.get(&1), Some(&10));
1317        assert_eq!(map.get(&2), Some(&20));
1318        assert_eq!(map.get(&3), Some(&30));
1319    }
1320
1321    #[test]
1322    fn retain_heap_test() {
1323        let mut map: SmallMap<4, i32, i32> = SmallMap::new();
1324        for i in 0..10 {
1325            map.insert(i, i * 10);
1326        }
1327        assert!(!map.is_inline());
1328
1329        map.retain(|&k, _| k % 2 == 0);
1330        assert_eq!(map.len(), 5);
1331    }
1332}
small_map/lib.rs

small_map/
lib.rs
