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
43/// Re-exported from [`hashbrown`] for custom key equivalence lookups.
44///
45/// Allows using a different type for lookups than the key type stored in the map.
46pub use hashbrown::Equivalent;
47
48#[cfg(feature = "serde")]
49mod serde;
50
51/// Type alias for [`SmallMap`] using [`rapidhash`](https://docs.rs/rapidhash) as the heap hasher.
52///
53/// Since rapidhash is a fast hasher, `LINEAR_THRESHOLD` is set to 8 to prefer SIMD search earlier.
54///
55/// Requires the `rapidhash` feature.
56#[cfg(feature = "rapidhash")]
57pub type RapidSmallMap<const N: usize, K, V> =
58    SmallMap<N, K, V, rapidhash::fast::RandomState, DefaultInlineHasher, 8>;
59
60/// Type alias for [`SmallMap`] using [`rustc_hash::FxBuildHasher`] as the heap hasher.
61///
62/// Requires the `fxhash` feature.
63#[cfg(feature = "fxhash")]
64pub type FxSmallMap<const N: usize, K, V> = SmallMap<N, K, V, rustc_hash::FxBuildHasher>;
65
66/// Type alias for [`SmallMap`] using [`ahash::AHasher`] as the heap hasher.
67///
68/// Requires the `ahash` feature.
69#[cfg(feature = "ahash")]
70pub type ASmallMap<const N: usize, K, V> =
71    SmallMap<N, K, V, core::hash::BuildHasherDefault<ahash::AHasher>>;
72
73#[cfg(feature = "rapidhash")]
74type DefaultInlineHasher = rapidhash::fast::RandomState;
75#[cfg(all(not(feature = "rapidhash"), feature = "fxhash"))]
76type DefaultInlineHasher = rustc_hash::FxBuildHasher;
77#[cfg(all(not(feature = "rapidhash"), not(feature = "fxhash"), feature = "ahash"))]
78type DefaultInlineHasher = core::hash::BuildHasherDefault<ahash::AHasher>;
79#[cfg(all(
80    not(feature = "rapidhash"),
81    not(feature = "fxhash"),
82    not(feature = "ahash")
83))]
84type DefaultInlineHasher = RandomState;
85
86/// Default threshold for switching from linear search to SIMD hash search.
87/// When `N` or `len` is less than this value, linear search is used.
88/// Equal to the SIMD group width (16 on SSE2, 8 on NEON/generic).
89pub const DEFAULT_LINEAR_THRESHOLD: usize = raw::Group::WIDTH;
90
91/// A hybrid map that stores data inline when small, and spills to heap when it grows.
92///
93/// # Type Parameters
94///
95/// - `N`: Maximum number of elements to store inline (must be > 0). When the map exceeds this size,
96///   it automatically spills to a heap-allocated `HashMap`.
97///
98/// - `K`: Key type. Must implement `Eq + Hash` for most operations.
99///
100/// - `V`: Value type.
101///
102/// - `SH`: Hasher for heap storage. Default: [`RandomState`]. This hasher is used when the map
103///   spills to heap. Note: The standard library's `RandomState` provides HashDoS resistance but is
104///   not the fastest option. Consider your security vs performance requirements - for
105///   non-adversarial workloads, faster alternatives like `rapidhash` or `fxhash` can improve
106///   performance significantly (though they are not cryptographically secure).
107///
108/// - `SI`: Hasher for inline storage. Default: `DefaultInlineHasher` (rapidhash if available,
109///   otherwise fxhash, ahash, or RandomState based on features). This hasher is used for
110///   SIMD-accelerated lookups in inline mode. Since inline storage only handles a small number of
111///   elements, HashDoS resistance is generally not a concern here - performance is the priority. We
112///   recommend using the default value and enabling the `rapidhash` or `fxhash` feature for best
113///   performance.
114///
115/// - `LINEAR_THRESHOLD`: Threshold for switching between linear and SIMD search. Default:
116///   [`DEFAULT_LINEAR_THRESHOLD`] (equal to SIMD group width, typically 16 on SSE2). When `N <
117///   LINEAR_THRESHOLD` or `len < LINEAR_THRESHOLD`, linear search is used; otherwise,
118///   SIMD-accelerated hash search is used.
119///
120///   **How to choose this value**: The optimal threshold depends on the tradeoff between
121///   hash computation cost and key comparison cost:
122///   - **Linear search**: `len` key comparisons (direct equality checks).
123///   - **SIMD search**: 1 hash computation + `len / GROUP_WIDTH` SIMD operations + a few key
124///     comparisons.
125///
126///   If key comparison is cheap (e.g., integers, short strings), a higher threshold favors
127///   linear search which avoids hash overhead. If key comparison is expensive (e.g., long
128///   strings, complex types), a lower threshold makes SIMD search more attractive.
129///
130///   **Recommendation**: Values above 16 are generally not recommended. The default value
131///   works well for most use cases. Set to `0` to disable linear search entirely.
132///
133/// # Examples
134///
135/// ```
136/// use small_map::SmallMap;
137///
138/// // Basic usage with defaults
139/// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
140/// map.insert("a", 1);
141///
142/// // Custom hasher
143/// use std::collections::hash_map::RandomState;
144/// let mut map: SmallMap<8, &str, i32, RandomState> = SmallMap::new();
145///
146/// // Custom linear threshold (force SIMD search even for small maps)
147/// let mut map: SmallMap<8, &str, i32, RandomState, RandomState, 4> = SmallMap::new();
148/// ```
149#[derive(Clone)]
150pub enum SmallMap<
151    const N: usize,
152    K,
153    V,
154    SH = RandomState,
155    SI = DefaultInlineHasher,
156    const LINEAR_THRESHOLD: usize = DEFAULT_LINEAR_THRESHOLD,
157> {
158    /// Heap-allocated storage using `hashbrown::HashMap`.
159    Heap(HashMap<K, V, SH>),
160    /// Inline storage with SIMD-accelerated lookups.
161    Inline(Inline<N, K, V, SH, SI, LINEAR_THRESHOLD>),
162}
163
164impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> Debug
165    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
166where
167    K: Debug,
168    V: Debug,
169{
170    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
171        f.debug_map().entries(self.iter()).finish()
172    }
173}
174
175impl<const N: usize, K, V, SH: Default, SI: Default, const LINEAR_THRESHOLD: usize> Default
176    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
177{
178    /// Creates an empty `SmallMap<N, K, V, SH, SI>`, with the `Default` value for the hasher.
179    ///
180    /// # Examples
181    ///
182    /// ```
183    /// use std::collections::hash_map::RandomState;
184    ///
185    /// use small_map::SmallMap;
186    ///
187    /// // You can specify all types of SmallMap, including N and hasher.
188    /// // Created map is empty and don't allocate memory
189    /// let map: SmallMap<8, u32, String> = SmallMap::default();
190    /// assert_eq!(map.capacity(), 8);
191    /// let map: SmallMap<8, u32, String, RandomState> = SmallMap::default();
192    /// assert_eq!(map.capacity(), 8);
193    /// ```
194    #[inline]
195    fn default() -> Self {
196        Self::with_hashers(Default::default(), Default::default())
197    }
198}
199
200impl<const N: usize, K, V, SH: Default, SI: Default, const LINEAR_THRESHOLD: usize>
201    SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
202{
203    /// Creates an empty `SmallMap`.
204    #[inline]
205    pub fn new() -> Self {
206        Self::with_hashers(Default::default(), Default::default())
207    }
208
209    /// Creates an empty `SmallMap` with the specified capacity.
210    ///
211    /// The hash map will be able to hold at least `capacity` elements without
212    /// reallocating. If `capacity` is smaller than N, the hash map will not allocate.
213    #[inline]
214    pub fn with_capacity(capacity: usize) -> Self {
215        if capacity > N {
216            Self::Heap(HashMap::with_capacity_and_hasher(
217                capacity,
218                Default::default(),
219            ))
220        } else {
221            Self::Inline(Inline::new(Default::default(), Default::default()))
222        }
223    }
224}
225
226impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize>
227    SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
228{
229    /// Creates an empty `SmallMap` which will use the given hash builder to hash
230    /// keys. It will be allocated with the given allocator.
231    ///
232    /// The hash map is initially created with a capacity of N, so it will not allocate until it
233    /// its size bigger than inline size N.
234    /// # Examples
235    ///
236    /// ```
237    /// use std::hash::{BuildHasherDefault, DefaultHasher};
238    ///
239    /// use small_map::SmallMap;
240    ///
241    /// let s = BuildHasherDefault::<DefaultHasher>::default();
242    /// let mut map = SmallMap::<8, _, _, _>::with_hasher(s);
243    /// map.insert(1, 2);
244    /// ```
245    #[inline]
246    pub fn with_hasher(hash_builder: SH) -> Self
247    where
248        SI: Default,
249    {
250        Self::Inline(Inline::new(SI::default(), hash_builder))
251    }
252
253    /// Creates an empty `SmallMap` which will use the given hash builders to hash
254    /// keys. It will be allocated with the given allocator.
255    /// # Examples
256    /// ```
257    /// use std::collections::hash_map::RandomState;
258    ///
259    /// use small_map::SmallMap;
260    /// let heap_hasher = RandomState::new();
261    /// let inline_hasher = RandomState::new();
262    /// let mut map = SmallMap::<8, _, _, _, _>::with_hashers(heap_hasher, inline_hasher);
263    /// map.insert(1, 2);
264    /// ```
265    #[inline]
266    pub const fn with_hashers(heap_hasher: SH, inline_hasher: SI) -> Self {
267        Self::Inline(Inline::new(inline_hasher, heap_hasher))
268    }
269
270    /// Creates an empty `SmallMap` with the specified capacity, using `heap_hasher`
271    /// to hash the keys.
272    ///
273    /// The hash map will be able to hold at least `capacity` elements without
274    /// reallocating. If `capacity` is smaller than or eq to N, the hash map will not allocate.
275    #[inline]
276    pub fn with_capacity_and_hasher(capacity: usize, heap_hasher: SH) -> Self
277    where
278        SI: Default,
279    {
280        if capacity > N {
281            Self::Heap(HashMap::with_capacity_and_hasher(capacity, heap_hasher))
282        } else {
283            Self::Inline(Inline::new(SI::default(), heap_hasher))
284        }
285    }
286
287    /// Creates an empty `SmallMap` with the specified capacity, using `heap_hasher`
288    /// to hash the keys for heap storage, and `inline_hasher` for inline storage.
289    ///
290    /// # Examples
291    /// ```
292    /// use std::collections::hash_map::RandomState;
293    ///
294    /// use small_map::SmallMap;
295    /// let heap_hasher = RandomState::new();
296    /// let inline_hasher = RandomState::new();
297    /// let mut map =
298    ///     SmallMap::<8, _, _, _, _>::with_capacity_and_hashers(16, heap_hasher, inline_hasher);
299    /// map.insert(1, 2);
300    /// ```
301    #[inline]
302    pub fn with_capacity_and_hashers(capacity: usize, heap_hasher: SH, inline_hasher: SI) -> Self {
303        if capacity > N {
304            Self::Heap(HashMap::with_capacity_and_hasher(capacity, heap_hasher))
305        } else {
306            Self::Inline(Inline::new(inline_hasher, heap_hasher))
307        }
308    }
309
310    /// What branch it is now.
311    #[inline]
312    pub fn is_inline(&self) -> bool {
313        matches!(self, Self::Inline(..))
314    }
315
316    /// Returns the number of elements the map can hold without reallocating.
317    ///
318    /// This number is a lower bound; the `SmallMap<N, K, V>` might be able to hold
319    /// more, but is guaranteed to be able to hold at least this many.
320    ///
321    /// # Examples
322    ///
323    /// ```
324    /// use small_map::SmallMap;
325    ///
326    /// let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(100);
327    /// assert_eq!(map.len(), 0);
328    /// assert!(map.capacity() >= 100);
329    ///
330    /// let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(2);
331    /// assert_eq!(map.len(), 0);
332    /// assert!(map.capacity() >= 8);
333    /// ```
334    #[inline]
335    pub fn capacity(&self) -> usize {
336        match self {
337            SmallMap::Heap(inner) => inner.capacity(),
338            SmallMap::Inline(_) => N,
339        }
340    }
341}
342
343impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize>
344    SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
345where
346    K: Eq + Hash,
347    SH: BuildHasher,
348    SI: BuildHasher,
349{
350    /// Returns a reference to the value corresponding to the key.
351    ///
352    /// # Examples
353    ///
354    /// ```
355    /// use small_map::SmallMap;
356    ///
357    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
358    /// map.insert(1, "a");
359    /// assert_eq!(map.get(&1), Some(&"a"));
360    /// assert_eq!(map.get(&2), None);
361    /// ```
362    #[inline]
363    pub fn get<Q>(&self, k: &Q) -> Option<&V>
364    where
365        Q: ?Sized + Hash + Equivalent<K>,
366    {
367        match self {
368            SmallMap::Heap(inner) => inner.get(k),
369            SmallMap::Inline(inner) => inner.get(k),
370        }
371    }
372
373    /// Returns a mutable reference to the value corresponding to the key.
374    ///
375    /// # Examples
376    ///
377    /// ```
378    /// use small_map::SmallMap;
379    ///
380    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
381    /// map.insert(1, 10);
382    /// if let Some(v) = map.get_mut(&1) {
383    ///     *v = 20;
384    /// }
385    /// assert_eq!(map.get(&1), Some(&20));
386    /// ```
387    #[inline]
388    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
389    where
390        Q: ?Sized + Hash + Equivalent<K>,
391    {
392        match self {
393            SmallMap::Heap(inner) => inner.get_mut(k),
394            SmallMap::Inline(inner) => inner.get_mut(k),
395        }
396    }
397
398    /// Returns the key-value pair corresponding to the supplied key.
399    ///
400    /// # Examples
401    ///
402    /// ```
403    /// use small_map::SmallMap;
404    ///
405    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
406    /// map.insert(1, "a");
407    /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
408    /// assert_eq!(map.get_key_value(&2), None);
409    /// ```
410    #[inline]
411    pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
412    where
413        Q: ?Sized + Hash + Equivalent<K>,
414    {
415        match self {
416            SmallMap::Heap(inner) => inner.get_key_value(k),
417            SmallMap::Inline(inner) => inner.get_key_value(k),
418        }
419    }
420
421    /// Returns `true` if the map contains a value for the specified key.
422    ///
423    /// # Examples
424    ///
425    /// ```
426    /// use small_map::SmallMap;
427    ///
428    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
429    /// map.insert(1, "a");
430    /// assert!(map.contains_key(&1));
431    /// assert!(!map.contains_key(&2));
432    /// ```
433    #[inline]
434    pub fn contains_key<Q>(&self, k: &Q) -> bool
435    where
436        Q: ?Sized + Hash + Equivalent<K>,
437    {
438        self.get(k).is_some()
439    }
440
441    /// Inserts a key-value pair into the map.
442    ///
443    /// If the map did not have this key present, `None` is returned.
444    /// If the map did have this key present, the value is updated, and the old value is returned.
445    ///
446    /// # Examples
447    ///
448    /// ```
449    /// use small_map::SmallMap;
450    ///
451    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
452    /// assert_eq!(map.insert(1, "a"), None);
453    /// assert_eq!(map.insert(1, "b"), Some("a"));
454    /// assert_eq!(map.get(&1), Some(&"b"));
455    /// ```
456    #[inline]
457    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
458        match self {
459            SmallMap::Heap(inner) => inner.insert(key, value),
460            SmallMap::Inline(inner) => {
461                if raw::util::likely(!inner.is_full()) {
462                    return inner.insert(key, value);
463                }
464                // SAFETY: We just checked that inline is full.
465                unsafe { self.spill_to_heap() }.insert(key, value)
466            }
467        }
468    }
469
470    /// Inserts a key-value pair into the map without checking if the key already exists.
471    ///
472    /// Returns a reference to the key and a mutable reference to the value.
473    ///
474    /// # Safety
475    ///
476    /// The caller must ensure that the key does not already exist in the map.
477    /// Inserting a duplicate key will result in undefined behavior (e.g., memory leaks,
478    /// incorrect iteration, or other inconsistencies).
479    ///
480    /// # Examples
481    ///
482    /// ```
483    /// use small_map::SmallMap;
484    ///
485    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
486    /// // SAFETY: We know the key doesn't exist because the map is empty.
487    /// unsafe { map.insert_unique_unchecked(1, "a") };
488    /// assert_eq!(map.get(&1), Some(&"a"));
489    /// ```
490    #[inline]
491    pub unsafe fn insert_unique_unchecked(&mut self, key: K, value: V) -> (&K, &mut V) {
492        let needs_spill = matches!(self, SmallMap::Inline(inner) if inner.is_full());
493        if needs_spill {
494            return self.spill_to_heap().insert_unique_unchecked(key, value);
495        }
496        match self {
497            SmallMap::Heap(inner) => inner.insert_unique_unchecked(key, value),
498            SmallMap::Inline(inner) => inner.insert_unique_unchecked(key, value),
499        }
500    }
501
502    /// Spills inline storage to heap. Returns mutable reference to the heap HashMap.
503    /// Only call when self is Inline and is full.
504    #[cold]
505    #[inline(never)]
506    unsafe fn spill_to_heap(&mut self) -> &mut HashMap<K, V, SH> {
507        let heap = match self {
508            SmallMap::Inline(inner) => {
509                HashMap::with_capacity_and_hasher(N * 2, inner.take_heap_hasher())
510            }
511            SmallMap::Heap(_) => unreachable_unchecked(),
512        };
513
514        match core::mem::replace(self, SmallMap::Heap(heap)) {
515            SmallMap::Heap(_) => unreachable_unchecked(),
516            SmallMap::Inline(inline) => {
517                let heap = match self {
518                    SmallMap::Heap(heap) => heap,
519                    SmallMap::Inline(_) => unreachable_unchecked(),
520                };
521                for (k, v) in inline.into_iter() {
522                    heap.insert_unique_unchecked(k, v);
523                }
524                heap
525            }
526        }
527    }
528
529    /// Removes a key from the map, returning the value at the key if the key was previously in the
530    /// map.
531    ///
532    /// # Examples
533    ///
534    /// ```
535    /// use small_map::SmallMap;
536    ///
537    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
538    /// map.insert(1, "a");
539    /// assert_eq!(map.remove(&1), Some("a"));
540    /// assert_eq!(map.remove(&1), None);
541    /// ```
542    #[inline]
543    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
544    where
545        Q: ?Sized + Hash + Equivalent<K>,
546    {
547        // Avoid `Option::map` because it bloats LLVM IR.
548        match self.remove_entry(k) {
549            Some((_, v)) => Some(v),
550            None => None,
551        }
552    }
553
554    /// Removes a key from the map, returning the stored key and value if the key was previously in
555    /// the map.
556    ///
557    /// # Examples
558    ///
559    /// ```
560    /// use small_map::SmallMap;
561    ///
562    /// let mut map: SmallMap<8, i32, &str> = SmallMap::new();
563    /// map.insert(1, "a");
564    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
565    /// assert_eq!(map.remove_entry(&1), None);
566    /// ```
567    #[inline]
568    pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
569    where
570        Q: ?Sized + Hash + Equivalent<K>,
571    {
572        match self {
573            SmallMap::Heap(inner) => inner.remove_entry(k),
574            SmallMap::Inline(inner) => inner.remove_entry(k),
575        }
576    }
577
578    /// Retains only the elements specified by the predicate.
579    ///
580    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
581    ///
582    /// # Examples
583    ///
584    /// ```
585    /// use small_map::SmallMap;
586    ///
587    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
588    /// for i in 0..8 {
589    ///     map.insert(i, i * 10);
590    /// }
591    /// map.retain(|&k, _| k % 2 == 0);
592    /// assert_eq!(map.len(), 4);
593    /// ```
594    #[inline]
595    pub fn retain<F>(&mut self, mut f: F)
596    where
597        F: FnMut(&K, &mut V) -> bool,
598    {
599        match self {
600            SmallMap::Heap(inner) => inner.retain(f),
601            SmallMap::Inline(inner) => inner.retain(&mut f),
602        }
603    }
604}
605
606impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize>
607    SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
608{
609    /// Clears the map.
610    ///
611    /// This method clears the map and keeps the allocated memory for reuse.
612    ///
613    /// # Examples
614    ///
615    /// ```
616    /// use small_map::SmallMap;
617    ///
618    /// let mut map: SmallMap<8, i32, ()> = SmallMap::new();
619    /// for i in 0..16 {
620    ///     map.insert(i, ());
621    /// }
622    /// assert!(!map.is_inline());
623    /// assert_eq!(map.len(), 16);
624    ///
625    /// map.clear();
626    /// assert!(!map.is_inline());
627    /// assert_eq!(map.len(), 0);
628    /// ```
629    #[inline]
630    pub fn clear(&mut self) {
631        match self {
632            SmallMap::Heap(inner) => {
633                inner.clear();
634            }
635            // Safety: We're about to destroy this inner, so it doesn't need its hasher
636            SmallMap::Inline(inner) => unsafe {
637                *self = Self::Inline(Inline::new(
638                    inner.take_inline_hasher(),
639                    inner.take_heap_hasher(),
640                ))
641            },
642        }
643    }
644}
645
646pub enum Iter<'a, const N: usize, K, V> {
647    Heap(hashbrown::hash_map::Iter<'a, K, V>),
648    Inline(inline::Iter<'a, N, K, V>),
649}
650
651impl<'a, const N: usize, K, V> Iterator for Iter<'a, N, K, V> {
652    type Item = (&'a K, &'a V);
653
654    #[inline]
655    fn next(&mut self) -> Option<(&'a K, &'a V)> {
656        match self {
657            Iter::Heap(inner) => inner.next(),
658            Iter::Inline(inner) => inner.next(),
659        }
660    }
661    #[inline]
662    fn size_hint(&self) -> (usize, Option<usize>) {
663        match self {
664            Iter::Heap(inner) => inner.size_hint(),
665            Iter::Inline(inner) => inner.size_hint(),
666        }
667    }
668}
669
670impl<const N: usize, K, V> ExactSizeIterator for Iter<'_, N, K, V> {
671    #[inline]
672    fn len(&self) -> usize {
673        match self {
674            Iter::Heap(inner) => inner.len(),
675            Iter::Inline(inner) => inner.len(),
676        }
677    }
678}
679
680impl<const N: usize, K, V> FusedIterator for Iter<'_, N, K, V> {}
681
682impl<'a, const N: usize, K, V> Clone for Iter<'a, N, K, V> {
683    #[inline]
684    fn clone(&self) -> Self {
685        match self {
686            Iter::Heap(inner) => Iter::Heap(inner.clone()),
687            Iter::Inline(inner) => Iter::Inline(inner.clone()),
688        }
689    }
690}
691
692/// An iterator over the keys of a `SmallMap`.
693pub struct Keys<'a, const N: usize, K, V> {
694    inner: Iter<'a, N, K, V>,
695}
696
697impl<'a, const N: usize, K, V> Iterator for Keys<'a, N, K, V> {
698    type Item = &'a K;
699
700    #[inline]
701    fn next(&mut self) -> Option<&'a K> {
702        match self.inner.next() {
703            Some((k, _)) => Some(k),
704            None => None,
705        }
706    }
707
708    #[inline]
709    fn size_hint(&self) -> (usize, Option<usize>) {
710        self.inner.size_hint()
711    }
712}
713
714impl<const N: usize, K, V> ExactSizeIterator for Keys<'_, N, K, V> {
715    #[inline]
716    fn len(&self) -> usize {
717        self.inner.len()
718    }
719}
720
721impl<const N: usize, K, V> FusedIterator for Keys<'_, N, K, V> {}
722
723/// An iterator over the values of a `SmallMap`.
724pub struct Values<'a, const N: usize, K, V> {
725    inner: Iter<'a, N, K, V>,
726}
727
728impl<'a, const N: usize, K, V> Iterator for Values<'a, N, K, V> {
729    type Item = &'a V;
730
731    #[inline]
732    fn next(&mut self) -> Option<&'a V> {
733        match self.inner.next() {
734            Some((_, v)) => Some(v),
735            None => None,
736        }
737    }
738
739    #[inline]
740    fn size_hint(&self) -> (usize, Option<usize>) {
741        self.inner.size_hint()
742    }
743}
744
745impl<const N: usize, K, V> ExactSizeIterator for Values<'_, N, K, V> {
746    #[inline]
747    fn len(&self) -> usize {
748        self.inner.len()
749    }
750}
751
752impl<const N: usize, K, V> FusedIterator for Values<'_, N, K, V> {}
753
754/// A consuming iterator over the keys of a `SmallMap`.
755pub struct IntoKeys<const N: usize, K, V> {
756    inner: IntoIter<N, K, V>,
757}
758
759impl<const N: usize, K, V> Iterator for IntoKeys<N, K, V> {
760    type Item = K;
761
762    #[inline]
763    fn next(&mut self) -> Option<K> {
764        match self.inner.next() {
765            Some((k, _)) => Some(k),
766            None => None,
767        }
768    }
769
770    #[inline]
771    fn size_hint(&self) -> (usize, Option<usize>) {
772        self.inner.size_hint()
773    }
774}
775
776impl<const N: usize, K, V> ExactSizeIterator for IntoKeys<N, K, V> {
777    #[inline]
778    fn len(&self) -> usize {
779        self.inner.len()
780    }
781}
782
783impl<const N: usize, K, V> FusedIterator for IntoKeys<N, K, V> {}
784
785/// A consuming iterator over the values of a `SmallMap`.
786pub struct IntoValues<const N: usize, K, V> {
787    inner: IntoIter<N, K, V>,
788}
789
790impl<const N: usize, K, V> Iterator for IntoValues<N, K, V> {
791    type Item = V;
792
793    #[inline]
794    fn next(&mut self) -> Option<V> {
795        match self.inner.next() {
796            Some((_, v)) => Some(v),
797            None => None,
798        }
799    }
800
801    #[inline]
802    fn size_hint(&self) -> (usize, Option<usize>) {
803        self.inner.size_hint()
804    }
805}
806
807impl<const N: usize, K, V> ExactSizeIterator for IntoValues<N, K, V> {
808    #[inline]
809    fn len(&self) -> usize {
810        self.inner.len()
811    }
812}
813
814impl<const N: usize, K, V> FusedIterator for IntoValues<N, K, V> {}
815
816pub enum IntoIter<const N: usize, K, V> {
817    Heap(hashbrown::hash_map::IntoIter<K, V>),
818    Inline(inline::IntoIter<N, K, V>),
819}
820
821impl<const N: usize, K, V> Iterator for IntoIter<N, K, V> {
822    type Item = (K, V);
823
824    #[inline]
825    fn next(&mut self) -> Option<(K, V)> {
826        match self {
827            IntoIter::Heap(inner) => inner.next(),
828            IntoIter::Inline(inner) => inner.next(),
829        }
830    }
831    #[inline]
832    fn size_hint(&self) -> (usize, Option<usize>) {
833        match self {
834            IntoIter::Heap(inner) => inner.size_hint(),
835            IntoIter::Inline(inner) => inner.size_hint(),
836        }
837    }
838}
839impl<const N: usize, K, V> ExactSizeIterator for IntoIter<N, K, V> {
840    #[inline]
841    fn len(&self) -> usize {
842        match self {
843            IntoIter::Heap(inner) => inner.len(),
844            IntoIter::Inline(inner) => inner.len(),
845        }
846    }
847}
848
849impl<const N: usize, K, V> FusedIterator for IntoIter<N, K, V> {}
850
851impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> IntoIterator
852    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
853{
854    type Item = (K, V);
855    type IntoIter = IntoIter<N, K, V>;
856
857    /// Creates a consuming iterator, that is, one that moves each key-value
858    /// pair out of the map in arbitrary order. The map cannot be used after
859    /// calling this.
860    #[inline]
861    fn into_iter(self) -> IntoIter<N, K, V> {
862        match self {
863            SmallMap::Heap(inner) => IntoIter::Heap(inner.into_iter()),
864            SmallMap::Inline(inner) => IntoIter::Inline(inner.into_iter()),
865        }
866    }
867}
868
869impl<'a, const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> IntoIterator
870    for &'a SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
871{
872    type Item = (&'a K, &'a V);
873    type IntoIter = Iter<'a, N, K, V>;
874
875    /// Creates an iterator over the entries of a `HashMap` in arbitrary order.
876    /// The iterator element type is `(&'a K, &'a V)`.
877    #[inline]
878    fn into_iter(self) -> Iter<'a, N, K, V> {
879        match self {
880            SmallMap::Heap(inner) => Iter::Heap(inner.iter()),
881            SmallMap::Inline(inner) => Iter::Inline(inner.iter()),
882        }
883    }
884}
885
886impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize>
887    SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
888{
889    /// Returns the number of elements in the map.
890    ///
891    /// # Examples
892    ///
893    /// ```
894    /// use small_map::SmallMap;
895    ///
896    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
897    /// assert_eq!(map.len(), 0);
898    /// map.insert(1, 10);
899    /// assert_eq!(map.len(), 1);
900    /// ```
901    #[inline]
902    pub fn len(&self) -> usize {
903        match self {
904            SmallMap::Heap(inner) => inner.len(),
905            SmallMap::Inline(inner) => inner.len(),
906        }
907    }
908
909    /// Returns `true` if the map contains no elements.
910    ///
911    /// # Examples
912    ///
913    /// ```
914    /// use small_map::SmallMap;
915    ///
916    /// let mut map: SmallMap<8, i32, i32> = SmallMap::new();
917    /// assert!(map.is_empty());
918    /// map.insert(1, 10);
919    /// assert!(!map.is_empty());
920    /// ```
921    #[inline]
922    pub fn is_empty(&self) -> bool {
923        match self {
924            SmallMap::Heap(inner) => inner.is_empty(),
925            SmallMap::Inline(inner) => inner.is_empty(),
926        }
927    }
928
929    /// An iterator visiting all key-value pairs in arbitrary order.
930    ///
931    /// # Examples
932    ///
933    /// ```
934    /// use small_map::SmallMap;
935    ///
936    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
937    /// map.insert("a", 1);
938    /// map.insert("b", 2);
939    ///
940    /// for (key, val) in map.iter() {
941    ///     println!("key: {key} val: {val}");
942    /// }
943    /// ```
944    #[inline]
945    pub fn iter(&self) -> Iter<'_, N, K, V> {
946        match self {
947            SmallMap::Heap(inner) => Iter::Heap(inner.iter()),
948            SmallMap::Inline(inner) => Iter::Inline(inner.iter()),
949        }
950    }
951
952    /// An iterator visiting all keys in arbitrary order.
953    ///
954    /// # Examples
955    ///
956    /// ```
957    /// use small_map::SmallMap;
958    ///
959    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
960    /// map.insert("a", 1);
961    /// map.insert("b", 2);
962    ///
963    /// for key in map.keys() {
964    ///     println!("{key}");
965    /// }
966    /// ```
967    #[inline]
968    pub fn keys(&self) -> Keys<'_, N, K, V> {
969        Keys { inner: self.iter() }
970    }
971
972    /// An iterator visiting all values in arbitrary order.
973    ///
974    /// # Examples
975    ///
976    /// ```
977    /// use small_map::SmallMap;
978    ///
979    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
980    /// map.insert("a", 1);
981    /// map.insert("b", 2);
982    ///
983    /// for val in map.values() {
984    ///     println!("{val}");
985    /// }
986    /// ```
987    #[inline]
988    pub fn values(&self) -> Values<'_, N, K, V> {
989        Values { inner: self.iter() }
990    }
991
992    /// Creates a consuming iterator visiting all the keys in arbitrary order.
993    ///
994    /// # Examples
995    ///
996    /// ```
997    /// use small_map::SmallMap;
998    ///
999    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
1000    /// map.insert("a", 1);
1001    /// map.insert("b", 2);
1002    ///
1003    /// let keys: Vec<_> = map.into_keys().collect();
1004    /// ```
1005    #[inline]
1006    pub fn into_keys(self) -> IntoKeys<N, K, V> {
1007        IntoKeys {
1008            inner: self.into_iter(),
1009        }
1010    }
1011
1012    /// Creates a consuming iterator visiting all the values in arbitrary order.
1013    ///
1014    /// # Examples
1015    ///
1016    /// ```
1017    /// use small_map::SmallMap;
1018    ///
1019    /// let mut map: SmallMap<8, &str, i32> = SmallMap::new();
1020    /// map.insert("a", 1);
1021    /// map.insert("b", 2);
1022    ///
1023    /// let values: Vec<_> = map.into_values().collect();
1024    /// ```
1025    #[inline]
1026    pub fn into_values(self) -> IntoValues<N, K, V> {
1027        IntoValues {
1028            inner: self.into_iter(),
1029        }
1030    }
1031}
1032
1033// PartialEq implementation
1034impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> PartialEq
1035    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
1036where
1037    K: Eq + Hash,
1038    V: PartialEq,
1039    SH: BuildHasher,
1040    SI: BuildHasher,
1041{
1042    fn eq(&self, other: &Self) -> bool {
1043        if self.len() != other.len() {
1044            return false;
1045        }
1046        self.iter()
1047            .all(|(key, value)| other.get(key) == Some(value))
1048    }
1049}
1050
1051impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> Eq
1052    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
1053where
1054    K: Eq + Hash,
1055    V: Eq,
1056    SH: BuildHasher,
1057    SI: BuildHasher,
1058{
1059}
1060
1061// Index implementation
1062impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize, Q> Index<&Q>
1063    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
1064where
1065    K: Eq + Hash,
1066    Q: ?Sized + Hash + Equivalent<K>,
1067    SH: BuildHasher,
1068    SI: BuildHasher,
1069{
1070    type Output = V;
1071
1072    /// Returns a reference to the value corresponding to the supplied key.
1073    ///
1074    /// # Panics
1075    ///
1076    /// Panics if the key is not present in the `SmallMap`.
1077    #[inline]
1078    fn index(&self, key: &Q) -> &V {
1079        self.get(key).expect("no entry found for key")
1080    }
1081}
1082
1083// Extend implementation
1084impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> Extend<(K, V)>
1085    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
1086where
1087    K: Eq + Hash,
1088    SH: BuildHasher,
1089    SI: BuildHasher,
1090{
1091    #[inline]
1092    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
1093        for (k, v) in iter {
1094            self.insert(k, v);
1095        }
1096    }
1097}
1098
1099// FromIterator implementation
1100impl<const N: usize, K, V, SH, SI, const LINEAR_THRESHOLD: usize> FromIterator<(K, V)>
1101    for SmallMap<N, K, V, SH, SI, LINEAR_THRESHOLD>
1102where
1103    K: Eq + Hash,
1104    SH: BuildHasher + Default,
1105    SI: BuildHasher + Default,
1106{
1107    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
1108        let mut map = SmallMap::new();
1109        map.extend(iter);
1110        map
1111    }
1112}
1113
1114#[cfg(test)]
1115mod tests {
1116    use std::{cell::RefCell, collections::hash_map::RandomState, rc::Rc};
1117
1118    use hashbrown::HashMap;
1119    use rand::Rng;
1120
1121    use crate::SmallMap;
1122
1123    #[test]
1124    fn basic_op() {
1125        let mut map = SmallMap::<16, String, String>::default();
1126        map.insert("hello".to_string(), "world".to_string());
1127        assert_eq!(map.len(), 1);
1128        assert_eq!(map.get("hello").unwrap(), "world");
1129        map.insert("hello2".to_string(), "world2".to_string());
1130        assert_eq!(map.get("hello2").unwrap(), "world2");
1131        assert_eq!(map.len(), 2);
1132
1133        assert_eq!(
1134            map.remove_entry("hello").unwrap(),
1135            ("hello".to_string(), "world".to_string())
1136        );
1137        assert_eq!(map.len(), 1);
1138        assert_eq!(map.get("hello2").unwrap(), "world2");
1139        assert_eq!(map.remove("hello2").unwrap(), "world2".to_string());
1140        assert_eq!(map.len(), 0);
1141        assert!(map.get("hello").is_none());
1142
1143        map.insert("hello3".to_string(), "world3".to_string());
1144        map.insert("hello4".to_string(), "world4".to_string());
1145        assert_eq!(map.len(), 2);
1146        map.clear();
1147        assert_eq!(map.len(), 0);
1148        assert!(map.get("hello3").is_none());
1149        assert!(map.get("hello4").is_none());
1150    }
1151
1152    #[test]
1153    fn multi_group_with_padding() {
1154        let mut map = SmallMap::<33, i32, i32>::default();
1155        for i in 0..33 {
1156            map.insert(i, i * 2);
1157        }
1158        for i in 0..33 {
1159            assert_eq!(*map.get(&i).unwrap(), i * 2);
1160        }
1161        assert!(map.is_inline());
1162
1163        for i in 33..64 {
1164            map.insert(i, i * 2);
1165        }
1166        assert!(!map.is_inline());
1167        for i in 0..64 {
1168            assert_eq!(*map.get(&i).unwrap(), i * 2);
1169        }
1170    }
1171
1172    #[test]
1173    fn clear_keep_state() {
1174        let mut map = SmallMap::<16, i32, i32>::default();
1175        for i in 0..32 {
1176            map.insert(i, i * 2);
1177        }
1178        assert!(!map.is_inline());
1179        map.clear();
1180        assert!(!map.is_inline());
1181    }
1182
1183    #[test]
1184    fn fuzzing() {
1185        let mut smallmap = SmallMap::<16, i32, i32>::default();
1186        let mut hashmap = HashMap::<i32, i32, RandomState>::default();
1187        for _ in 0..1000000 {
1188            let op = Operation::random();
1189            op.exec(&mut smallmap, &mut hashmap);
1190        }
1191
1192        enum Operation {
1193            Insert(i32, i32),
1194            Remove(i32),
1195            Get(i32),
1196            ModifyIfExist(i32, i32),
1197        }
1198        impl Operation {
1199            fn random() -> Self {
1200                let mut rng = rand::rng();
1201
1202                let choice: u8 = rng.random();
1203                match choice % 4 {
1204                    0 => Operation::Insert(rng.random_range(0..32), rng.random()),
1205                    1 => Operation::Remove(rng.random_range(0..32)),
1206                    2 => Operation::Get(rng.random_range(0..32)),
1207                    3 => Operation::ModifyIfExist(rng.random_range(0..32), rng.random()),
1208                    _ => unreachable!(),
1209                }
1210            }
1211
1212            fn exec<const N: usize, S1: core::hash::BuildHasher, S2: core::hash::BuildHasher>(
1213                self,
1214                sm: &mut SmallMap<N, i32, i32, S1>,
1215                hm: &mut HashMap<i32, i32, S2>,
1216            ) {
1217                match self {
1218                    Operation::Insert(k, v) => {
1219                        if sm.len() == sm.capacity() {
1220                            return;
1221                        }
1222                        assert_eq!(sm.insert(k, v), hm.insert(k, v));
1223                        assert!(sm.is_inline());
1224                    }
1225                    Operation::Remove(k) => {
1226                        assert_eq!(sm.remove(&k), hm.remove(&k));
1227                    }
1228                    Operation::Get(k) => {
1229                        assert_eq!(sm.get(&k), hm.get(&k));
1230                    }
1231                    Operation::ModifyIfExist(k, nv) => {
1232                        let (sv, hv) = (sm.get_mut(&k), hm.get_mut(&k));
1233                        assert_eq!(sv, hv);
1234                        if let Some(v) = sv {
1235                            *v = nv;
1236                        }
1237                        if let Some(v) = hv {
1238                            *v = nv;
1239                        }
1240                    }
1241                }
1242            }
1243        }
1244    }
1245
1246    #[test]
1247    fn drop_chk() {
1248        let (probe1, checker1) = drop_checker();
1249        let (probe2, checker2) = drop_checker();
1250        let (probe3, checker3) = drop_checker();
1251        let mut map = SmallMap::<8, _, _>::default();
1252        map.insert(1, probe1);
1253        map.insert(2, probe2);
1254        map.insert(3, probe3);
1255        assert_eq!(map.len(), 3);
1256        let mut it = map.into_iter();
1257        drop(it.next());
1258        drop(it);
1259        checker1.assert_drop();
1260        checker2.assert_drop();
1261        checker3.assert_drop();
1262
1263        fn drop_checker() -> (DropProbe, DropChecker) {
1264            let flag = Rc::new(RefCell::new(false));
1265            (DropProbe { flag: flag.clone() }, DropChecker { flag })
1266        }
1267
1268        struct DropChecker {
1269            flag: Rc<RefCell<bool>>,
1270        }
1271
1272        impl DropChecker {
1273            fn assert_drop(self) {
1274                assert!(*self.flag.borrow())
1275            }
1276        }
1277
1278        struct DropProbe {
1279            flag: Rc<RefCell<bool>>,
1280        }
1281
1282        impl Drop for DropProbe {
1283            fn drop(&mut self) {
1284                *self.flag.borrow_mut() = true;
1285            }
1286        }
1287    }
1288
1289    #[test]
1290    fn clone_after_delete() {
1291        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1292
1293        map.insert(1, "one".to_string());
1294        map.insert(2, "two".to_string());
1295        map.insert(3, "three".to_string());
1296
1297        assert_eq!(map.len(), 3);
1298        assert!(map.is_inline());
1299
1300        map.remove(&2);
1301        assert_eq!(map.len(), 2);
1302
1303        let cloned = map.clone();
1304
1305        assert_eq!(cloned.len(), 2);
1306        assert_eq!(cloned.get(&1), Some(&"one".to_string()));
1307        assert_eq!(cloned.get(&3), Some(&"three".to_string()));
1308        assert_eq!(cloned.get(&2), None);
1309
1310        let mut count = 0;
1311        for _ in cloned.iter() {
1312            count += 1;
1313        }
1314        assert_eq!(count, 2);
1315    }
1316
1317    #[test]
1318    fn clone_after_multiple_deletes() {
1319        let mut map: SmallMap<16, i32, i32> = SmallMap::new();
1320
1321        for i in 0..10 {
1322            map.insert(i, i * 100);
1323        }
1324        assert_eq!(map.len(), 10);
1325
1326        for i in (0..10).step_by(2) {
1327            map.remove(&i);
1328        }
1329        assert_eq!(map.len(), 5);
1330
1331        let cloned = map.clone();
1332        assert_eq!(cloned.len(), 5);
1333
1334        for i in (1..10).step_by(2) {
1335            assert_eq!(cloned.get(&i), Some(&(i * 100)));
1336        }
1337
1338        for i in (0..10).step_by(2) {
1339            assert_eq!(cloned.get(&i), None);
1340        }
1341
1342        let collected: Vec<_> = cloned.iter().collect();
1343        assert_eq!(collected.len(), 5);
1344    }
1345
1346    #[test]
1347    fn insert_into_cloned_after_delete() {
1348        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1349
1350        map.insert(1, "one".to_string());
1351        map.insert(2, "two".to_string());
1352        map.insert(3, "three".to_string());
1353
1354        map.remove(&2);
1355
1356        let mut cloned = map.clone();
1357
1358        cloned.insert(4, "four".to_string());
1359
1360        assert_eq!(cloned.len(), 3);
1361        assert_eq!(cloned.get(&1), Some(&"one".to_string()));
1362        assert_eq!(cloned.get(&3), Some(&"three".to_string()));
1363        assert_eq!(cloned.get(&4), Some(&"four".to_string()));
1364    }
1365
1366    #[test]
1367    fn into_iter_cloned_after_delete() {
1368        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1369
1370        map.insert(1, "one".to_string());
1371        map.insert(2, "two".to_string());
1372        map.insert(3, "three".to_string());
1373
1374        map.remove(&2);
1375
1376        let cloned = map.clone();
1377
1378        let items: Vec<_> = cloned.into_iter().collect();
1379        assert_eq!(items.len(), 2);
1380    }
1381
1382    #[test]
1383    fn clone_compaction() {
1384        // Test that clone compacts the data array
1385        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1386
1387        // Fill with gaps: insert 0-7, then delete evens
1388        for i in 0..8 {
1389            map.insert(i, i * 10);
1390        }
1391        for i in (0..8).step_by(2) {
1392            map.remove(&i);
1393        }
1394
1395        // Clone should compact: 4 elements at indices 0-3
1396        let cloned = map.clone();
1397        assert_eq!(cloned.len(), 4);
1398
1399        // Verify all odd keys are present
1400        for i in (1..8).step_by(2) {
1401            assert_eq!(cloned.get(&i), Some(&(i * 10)));
1402        }
1403
1404        // Insert into cloned should work correctly
1405        let mut cloned = cloned;
1406        cloned.insert(100, 1000);
1407        assert_eq!(cloned.len(), 5);
1408        assert_eq!(cloned.get(&100), Some(&1000));
1409    }
1410
1411    #[test]
1412    fn clone_empty_after_delete_all() {
1413        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1414
1415        map.insert(1, 10);
1416        map.insert(2, 20);
1417        map.remove(&1);
1418        map.remove(&2);
1419
1420        assert_eq!(map.len(), 0);
1421
1422        let cloned = map.clone();
1423        assert_eq!(cloned.len(), 0);
1424        assert!(cloned.is_empty());
1425
1426        // Should be able to insert into cloned empty map
1427        let mut cloned = cloned;
1428        cloned.insert(3, 30);
1429        assert_eq!(cloned.get(&3), Some(&30));
1430    }
1431
1432    #[test]
1433    fn contains_key_test() {
1434        let mut map: SmallMap<8, i32, &str> = SmallMap::new();
1435        map.insert(1, "a");
1436        map.insert(2, "b");
1437
1438        assert!(map.contains_key(&1));
1439        assert!(map.contains_key(&2));
1440        assert!(!map.contains_key(&3));
1441
1442        map.remove(&1);
1443        assert!(!map.contains_key(&1));
1444    }
1445
1446    #[test]
1447    fn keys_values_test() {
1448        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1449        for i in 0..5 {
1450            map.insert(i, i * 10);
1451        }
1452
1453        let keys: Vec<_> = map.keys().cloned().collect();
1454        assert_eq!(keys.len(), 5);
1455        for i in 0..5 {
1456            assert!(keys.contains(&i));
1457        }
1458
1459        let values: Vec<_> = map.values().cloned().collect();
1460        assert_eq!(values.len(), 5);
1461        for i in 0..5 {
1462            assert!(values.contains(&(i * 10)));
1463        }
1464    }
1465
1466    #[test]
1467    fn into_keys_values_test() {
1468        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1469        for i in 0..5 {
1470            map.insert(i, i * 10);
1471        }
1472
1473        let keys: Vec<_> = map.clone().into_keys().collect();
1474        assert_eq!(keys.len(), 5);
1475
1476        let values: Vec<_> = map.into_values().collect();
1477        assert_eq!(values.len(), 5);
1478    }
1479
1480    #[test]
1481    fn retain_test() {
1482        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1483        for i in 0..8 {
1484            map.insert(i, i * 10);
1485        }
1486
1487        map.retain(|&k, _| k % 2 == 0);
1488        assert_eq!(map.len(), 4);
1489
1490        for i in (0..8).step_by(2) {
1491            assert!(map.contains_key(&i));
1492        }
1493        for i in (1..8).step_by(2) {
1494            assert!(!map.contains_key(&i));
1495        }
1496    }
1497
1498    #[test]
1499    fn partial_eq_test() {
1500        let mut map1: SmallMap<8, i32, i32> = SmallMap::new();
1501        let mut map2: SmallMap<8, i32, i32> = SmallMap::new();
1502
1503        map1.insert(1, 10);
1504        map1.insert(2, 20);
1505
1506        map2.insert(2, 20);
1507        map2.insert(1, 10);
1508
1509        assert_eq!(map1, map2);
1510
1511        map2.insert(3, 30);
1512        assert_ne!(map1, map2);
1513    }
1514
1515    #[test]
1516    fn index_test() {
1517        let mut map: SmallMap<8, i32, &str> = SmallMap::new();
1518        map.insert(1, "a");
1519        map.insert(2, "b");
1520
1521        assert_eq!(map[&1], "a");
1522        assert_eq!(map[&2], "b");
1523    }
1524
1525    #[test]
1526    #[should_panic(expected = "no entry found for key")]
1527    fn index_panic_test() {
1528        let map: SmallMap<8, i32, &str> = SmallMap::new();
1529        let _ = map[&1];
1530    }
1531
1532    #[test]
1533    fn extend_test() {
1534        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1535        map.insert(1, 10);
1536
1537        map.extend([(2, 20), (3, 30)]);
1538        assert_eq!(map.len(), 3);
1539        assert_eq!(map.get(&2), Some(&20));
1540        assert_eq!(map.get(&3), Some(&30));
1541    }
1542
1543    #[test]
1544    fn from_iterator_test() {
1545        let map: SmallMap<8, i32, i32> = [(1, 10), (2, 20), (3, 30)].into_iter().collect();
1546        assert_eq!(map.len(), 3);
1547        assert_eq!(map.get(&1), Some(&10));
1548        assert_eq!(map.get(&2), Some(&20));
1549        assert_eq!(map.get(&3), Some(&30));
1550    }
1551
1552    #[test]
1553    fn retain_heap_test() {
1554        let mut map: SmallMap<4, i32, i32> = SmallMap::new();
1555        for i in 0..10 {
1556            map.insert(i, i * 10);
1557        }
1558        assert!(!map.is_inline());
1559
1560        map.retain(|&k, _| k % 2 == 0);
1561        assert_eq!(map.len(), 5);
1562    }
1563
1564    #[test]
1565    fn insert_unique_unchecked_test() {
1566        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1567
1568        // Insert using unsafe method
1569        unsafe {
1570            map.insert_unique_unchecked(1, 10);
1571            map.insert_unique_unchecked(2, 20);
1572            map.insert_unique_unchecked(3, 30);
1573        }
1574
1575        assert_eq!(map.len(), 3);
1576        assert_eq!(map.get(&1), Some(&10));
1577        assert_eq!(map.get(&2), Some(&20));
1578        assert_eq!(map.get(&3), Some(&30));
1579    }
1580
1581    #[test]
1582    fn insert_unique_unchecked_spill_test() {
1583        let mut map: SmallMap<4, i32, i32> = SmallMap::new();
1584
1585        // Fill inline storage
1586        for i in 0..4 {
1587            unsafe { map.insert_unique_unchecked(i, i * 10) };
1588        }
1589        assert!(map.is_inline());
1590
1591        // Spill to heap
1592        unsafe { map.insert_unique_unchecked(4, 40) };
1593        assert!(!map.is_inline());
1594
1595        // Verify all elements
1596        for i in 0..5 {
1597            assert_eq!(map.get(&i), Some(&(i * 10)));
1598        }
1599    }
1600
1601    #[test]
1602    fn single_element_operations() {
1603        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1604
1605        // Insert single
1606        map.insert(42, 420);
1607        assert_eq!(map.len(), 1);
1608        assert_eq!(map.get(&42), Some(&420));
1609
1610        // Update single
1611        map.insert(42, 421);
1612        assert_eq!(map.len(), 1);
1613        assert_eq!(map.get(&42), Some(&421));
1614
1615        // Remove single
1616        assert_eq!(map.remove(&42), Some(421));
1617        assert_eq!(map.len(), 0);
1618        assert!(map.is_empty());
1619
1620        // Get from empty
1621        assert_eq!(map.get(&42), None);
1622    }
1623
1624    #[test]
1625    fn min_capacity_n1() {
1626        let mut map: SmallMap<1, i32, i32> = SmallMap::new();
1627
1628        map.insert(1, 10);
1629        assert_eq!(map.len(), 1);
1630        assert!(map.is_inline());
1631
1632        // Spill to heap on second insert
1633        map.insert(2, 20);
1634        assert_eq!(map.len(), 2);
1635        assert!(!map.is_inline());
1636
1637        assert_eq!(map.get(&1), Some(&10));
1638        assert_eq!(map.get(&2), Some(&20));
1639    }
1640
1641    #[test]
1642    fn linear_search_threshold() {
1643        // Test with N <= Group::WIDTH (16 on SSE2, 8 on NEON)
1644        // This should use linear search
1645        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1646
1647        for i in 0..8 {
1648            map.insert(i, i * 10);
1649        }
1650
1651        // All lookups should work (linear search path)
1652        for i in 0..8 {
1653            assert_eq!(map.get(&i), Some(&(i * 10)));
1654        }
1655
1656        // Non-existent keys
1657        assert_eq!(map.get(&100), None);
1658        assert_eq!(map.get(&-1), None);
1659    }
1660
1661    #[test]
1662    fn simd_search_path() {
1663        // Test with N > Group::WIDTH to trigger SIMD path
1664        let mut map: SmallMap<32, i32, i32> = SmallMap::new();
1665
1666        for i in 0..32 {
1667            map.insert(i, i * 10);
1668        }
1669
1670        // All lookups should work (SIMD search path)
1671        for i in 0..32 {
1672            assert_eq!(map.get(&i), Some(&(i * 10)));
1673        }
1674
1675        // Non-existent keys
1676        assert_eq!(map.get(&100), None);
1677    }
1678
1679    #[test]
1680    fn iterator_clone() {
1681        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1682        for i in 0..5 {
1683            map.insert(i, i * 10);
1684        }
1685
1686        let iter = map.iter();
1687        let cloned_iter = iter.clone();
1688
1689        let items1: Vec<_> = iter.collect();
1690        let items2: Vec<_> = cloned_iter.collect();
1691
1692        assert_eq!(items1.len(), items2.len());
1693    }
1694
1695    #[test]
1696    fn get_key_value_test() {
1697        let mut map: SmallMap<8, String, i32> = SmallMap::new();
1698        map.insert("hello".to_string(), 42);
1699
1700        let (k, v) = map.get_key_value("hello").unwrap();
1701        assert_eq!(k, "hello");
1702        assert_eq!(*v, 42);
1703
1704        assert!(map.get_key_value("world").is_none());
1705    }
1706
1707    #[test]
1708    fn get_mut_modify() {
1709        let mut map: SmallMap<8, i32, Vec<i32>> = SmallMap::new();
1710        map.insert(1, vec![1, 2, 3]);
1711
1712        if let Some(v) = map.get_mut(&1) {
1713            v.push(4);
1714            v.push(5);
1715        }
1716
1717        assert_eq!(map.get(&1), Some(&vec![1, 2, 3, 4, 5]));
1718    }
1719
1720    #[test]
1721    fn retain_all() {
1722        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1723        for i in 0..5 {
1724            map.insert(i, i);
1725        }
1726
1727        map.retain(|_, _| true);
1728        assert_eq!(map.len(), 5);
1729    }
1730
1731    #[test]
1732    fn retain_none() {
1733        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1734        for i in 0..5 {
1735            map.insert(i, i);
1736        }
1737
1738        map.retain(|_, _| false);
1739        assert_eq!(map.len(), 0);
1740        assert!(map.is_empty());
1741    }
1742
1743    #[test]
1744    fn retain_modify_value() {
1745        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1746        for i in 0..5 {
1747            map.insert(i, i);
1748        }
1749
1750        map.retain(|_, v| {
1751            *v *= 10;
1752            true
1753        });
1754
1755        for i in 0..5 {
1756            assert_eq!(map.get(&i), Some(&(i * 10)));
1757        }
1758    }
1759
1760    #[test]
1761    fn swap_delete_order_preservation() {
1762        // Test that swap-delete doesn't break iteration
1763        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1764        for i in 0..5 {
1765            map.insert(i, i * 10);
1766        }
1767
1768        // Remove middle element
1769        map.remove(&2);
1770
1771        // Remaining elements should still be accessible
1772        assert_eq!(map.get(&0), Some(&0));
1773        assert_eq!(map.get(&1), Some(&10));
1774        assert_eq!(map.get(&2), None);
1775        assert_eq!(map.get(&3), Some(&30));
1776        assert_eq!(map.get(&4), Some(&40));
1777
1778        // Iteration should yield 4 elements
1779        assert_eq!(map.iter().count(), 4);
1780    }
1781
1782    #[test]
1783    fn repeated_insert_remove() {
1784        let mut map: SmallMap<4, i32, i32> = SmallMap::new();
1785
1786        for _ in 0..100 {
1787            map.insert(1, 10);
1788            map.insert(2, 20);
1789            map.insert(3, 30);
1790            assert_eq!(map.len(), 3);
1791
1792            map.remove(&2);
1793            assert_eq!(map.len(), 2);
1794            assert_eq!(map.get(&1), Some(&10));
1795            assert_eq!(map.get(&3), Some(&30));
1796
1797            map.remove(&1);
1798            map.remove(&3);
1799            assert!(map.is_empty());
1800        }
1801    }
1802
1803    #[test]
1804    fn remove_nonexistent() {
1805        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1806        map.insert(1, 10);
1807
1808        assert_eq!(map.remove(&999), None);
1809        assert_eq!(map.remove_entry(&999), None);
1810        assert_eq!(map.len(), 1);
1811    }
1812
1813    #[test]
1814    fn capacity_boundary() {
1815        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1816
1817        // Fill to capacity
1818        for i in 0..8 {
1819            map.insert(i, i);
1820        }
1821        assert!(map.is_inline());
1822        assert_eq!(map.capacity(), 8);
1823
1824        // One more triggers spill
1825        map.insert(8, 8);
1826        assert!(!map.is_inline());
1827        assert!(map.capacity() >= 9);
1828    }
1829
1830    #[test]
1831    fn with_capacity_inline() {
1832        let map: SmallMap<16, i32, i32> = SmallMap::with_capacity(8);
1833        assert!(map.is_inline());
1834        assert_eq!(map.capacity(), 16);
1835    }
1836
1837    #[test]
1838    fn with_capacity_heap() {
1839        let map: SmallMap<8, i32, i32> = SmallMap::with_capacity(100);
1840        assert!(!map.is_inline());
1841        assert!(map.capacity() >= 100);
1842    }
1843
1844    #[test]
1845    fn empty_map_operations() {
1846        let map: SmallMap<8, i32, i32> = SmallMap::new();
1847
1848        assert!(map.is_empty());
1849        assert_eq!(map.len(), 0);
1850        assert_eq!(map.get(&1), None);
1851        assert!(!map.contains_key(&1));
1852        assert_eq!(map.iter().count(), 0);
1853        assert_eq!(map.keys().count(), 0);
1854        assert_eq!(map.values().count(), 0);
1855    }
1856
1857    #[test]
1858    fn string_keys() {
1859        let mut map: SmallMap<8, String, i32> = SmallMap::new();
1860
1861        map.insert("alpha".to_string(), 1);
1862        map.insert("beta".to_string(), 2);
1863        map.insert("gamma".to_string(), 3);
1864
1865        // Query with &str (Equivalent trait)
1866        assert_eq!(map.get("alpha"), Some(&1));
1867        assert_eq!(map.get("beta"), Some(&2));
1868        assert_eq!(map.get("gamma"), Some(&3));
1869        assert_eq!(map.get("delta"), None);
1870
1871        assert_eq!(map.remove("beta"), Some(2));
1872        assert_eq!(map.get("beta"), None);
1873    }
1874
1875    #[test]
1876    fn update_existing_key() {
1877        let mut map: SmallMap<8, i32, String> = SmallMap::new();
1878
1879        map.insert(1, "first".to_string());
1880        assert_eq!(
1881            map.insert(1, "second".to_string()),
1882            Some("first".to_string())
1883        );
1884        assert_eq!(map.get(&1), Some(&"second".to_string()));
1885        assert_eq!(map.len(), 1);
1886    }
1887
1888    #[test]
1889    fn large_n_inline() {
1890        let mut map: SmallMap<256, i32, i32> = SmallMap::new();
1891
1892        for i in 0..256 {
1893            map.insert(i, i * 2);
1894        }
1895
1896        assert!(map.is_inline());
1897        assert_eq!(map.len(), 256);
1898
1899        for i in 0..256 {
1900            assert_eq!(map.get(&i), Some(&(i * 2)));
1901        }
1902    }
1903
1904    #[test]
1905    fn iter_after_partial_remove() {
1906        let mut map: SmallMap<8, i32, i32> = SmallMap::new();
1907        for i in 0..8 {
1908            map.insert(i, i);
1909        }
1910
1911        // Remove every other element
1912        for i in (0..8).step_by(2) {
1913            map.remove(&i);
1914        }
1915
1916        let items: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
1917        assert_eq!(items.len(), 4);
1918
1919        // Verify remaining elements
1920        for (k, v) in items {
1921            assert_eq!(k % 2, 1); // Only odd keys remain
1922            assert_eq!(k, v);
1923        }
1924    }
1925
1926    #[test]
1927    fn into_iter_drop_partial() {
1928        use std::sync::atomic::{AtomicUsize, Ordering};
1929
1930        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
1931
1932        struct DropCounter(#[allow(dead_code)] i32);
1933        impl Drop for DropCounter {
1934            fn drop(&mut self) {
1935                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
1936            }
1937        }
1938
1939        DROP_COUNT.store(0, Ordering::SeqCst);
1940
1941        let mut map: SmallMap<8, i32, DropCounter> = SmallMap::new();
1942        for i in 0..5 {
1943            map.insert(i, DropCounter(i));
1944        }
1945
1946        let mut iter = map.into_iter();
1947        // Consume only 2 elements
1948        let _ = iter.next();
1949        let _ = iter.next();
1950        // Drop the iterator (should drop remaining 3)
1951        drop(iter);
1952
1953        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 5);
1954    }
1955
1956    #[test]
1957    fn default_hasher_types() {
1958        // Test with default hasher
1959        let mut map1: SmallMap<8, i32, i32> = SmallMap::new();
1960        map1.insert(1, 10);
1961        assert_eq!(map1.get(&1), Some(&10));
1962
1963        // Test with explicit RandomState
1964        let mut map2: SmallMap<8, i32, i32, RandomState> = SmallMap::default();
1965        map2.insert(1, 10);
1966        assert_eq!(map2.get(&1), Some(&10));
1967    }
1968
1969    #[test]
1970    fn panic_safe_clone_test() {
1971        use std::sync::atomic::{AtomicUsize, Ordering};
1972
1973        static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
1974
1975        struct PanicOnClone {
1976            should_panic: bool,
1977            #[allow(dead_code)]
1978            data: i32,
1979        }
1980
1981        impl Clone for PanicOnClone {
1982            fn clone(&self) -> Self {
1983                if self.should_panic {
1984                    panic!("Panic on clone!");
1985                }
1986                Self {
1987                    should_panic: self.should_panic,
1988                    data: self.data,
1989                }
1990            }
1991        }
1992
1993        impl Drop for PanicOnClone {
1994            fn drop(&mut self) {
1995                DROP_COUNT.fetch_add(1, Ordering::SeqCst);
1996            }
1997        }
1998
1999        // Setup:
2000        // Map has 3 items.
2001        let mut map = SmallMap::<4, i32, PanicOnClone>::with_capacity(4);
2002        map.insert(
2003            1,
2004            PanicOnClone {
2005                should_panic: false,
2006                data: 10,
2007            },
2008        );
2009        map.insert(
2010            2,
2011            PanicOnClone {
2012                should_panic: true, // This one will panic
2013                data: 20,
2014            },
2015        );
2016        map.insert(
2017            3,
2018            PanicOnClone {
2019                should_panic: false,
2020                data: 30,
2021            },
2022        );
2023
2024        let res = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
2025            let _ = map.clone();
2026        }));
2027
2028        assert!(res.is_err());
2029        // Original map should still be valid/safe to drop
2030        // Dropping map...
2031        drop(map);
2032
2033        // Check leak
2034        // 3 items in map. Panic on 2nd item clone.
2035        // 1st item cloned successfully.
2036        // On panic:
2037        // - Cloned 1st item should be dropped (by DropGuard).
2038        // - Original 3 items should be dropped (when map is dropped).
2039        // Total drops: 1 (cloned) + 3 (original) = 4.
2040        assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 4);
2041    }
2042
2043    #[test]
2044    fn test_inline_insert_unique_hash_consistency() {
2045        // N=8, LINEAR_THRESHOLD=4
2046        // Group::WIDTH = 16 (SSE2) or 8 (NEON) or 8 (Generic).
2047        // If Group::WIDTH == 16, N <= Group::WIDTH (8 <= 16) is True.
2048        // N < LINEAR_THRESHOLD (8 < 4) is False.
2049        // MIN_LINEAR_LEN = 4.
2050
2051        // We use a custom threshold of 4.
2052        type BugMap = SmallMap<8, i32, i32, RandomState, RandomState, 4>;
2053        let mut map = BugMap::new();
2054
2055        unsafe {
2056            map.insert_unique_unchecked(1, 10);
2057            map.insert_unique_unchecked(2, 20);
2058            map.insert_unique_unchecked(3, 30);
2059            map.insert_unique_unchecked(4, 40);
2060            map.insert_unique_unchecked(5, 50);
2061        }
2062
2063        // Now len=5.
2064        // find logic:
2065        // if N < LINEAR_THRESHOLD (8<4 False) || len < MIN_LINEAR_LEN (5<4 False)
2066        // -> SIMD Search.
2067
2068        // If insert_unique_unchecked skipped hash updates (because N <= Group::WIDTH),
2069        // SIMD search will fail to find keys (hashes are 0/garbage).
2070
2071        // If Group::WIDTH is 8 (Generic/Neon), then N <= Group::WIDTH (8<=8) is True.
2072        // So the bug exists there too.
2073
2074        // Only if Group::WIDTH < 8 (impossible) would the bug be hidden.
2075
2076        assert_eq!(map.get(&1), Some(&10), "Failed to find 1");
2077        assert_eq!(map.get(&5), Some(&50), "Failed to find 5");
2078    }
2079}
small_map/lib.rs

small_map/
lib.rs
