mule_map/
mule_map.rs

1use entry::{
2    Entry, OccupiedEntry, OccupiedHashMapEntry, OccupiedVecEntry, VacantEntry, VacantHashMapEntry,
3    VacantVecEntry,
4};
5use key::Key;
6use key::PrimInt;
7use sealed::sealed;
8use std::collections::HashMap;
9use std::fmt::Debug;
10use std::hash::BuildHasher;
11use std::num::NonZero;
12use std::ops::AddAssign;
13
14pub(crate) mod entry;
15pub(crate) mod iterators;
16pub(crate) mod key;
17
18/// [`MuleMap`] is a hybrid between a [`HashMap`] and a lookup table. It improves performance for frequently accessed
19/// keys in a known range. If a key (integer) is in the user specified range, then its value will be stored directly in
20/// the lookup table.
21///
22/// ## Differences between [`HashMap`] and [`MuleMap`]
23///
24/// - **The key, `K`, must be an integer type.** - The key is directly mapped to the index in the lookup, so it must be
25///   an integer.
26/// - **The key, `K`, is passed by value** - Because it is a primitive integer type.
27/// - **The hash builder, `S`,  does not have a default** - You must specify your hash builder. The assumption being
28///   that if you need better performance you will likely also want to use a custom hash function.
29/// - **`TABLE_MIN_VALUE` and `TABLE_SIZE`** -  If a key is between `TABLE_MIN_VALUE` and `TABLE_MIN_VALUE +
30///  TABLE_SIZE` (exclusive), then the value will be stored directly in the lookup table, instead of using the `HashMap`.
31///
32/// **NOTE:** Currently the type of a const generic can’t depend on another generic type argument, so
33///  `TABLE_MIN_VALUE` can’t use the same type as the key. Because of this, We are using [`i128`], but that means we
34///  can’t represent values near [`u128::MAX`]. Hopefully having frequent keys near [`u128::MAX`] is extremely rare.
35///
36/// ## Performance
37///
38/// Benchmarks (using random selection) start to show speed improvements when about 50% of the key accesses are in the
39/// lookup table. Performance is almost identical to `HashMap` with less than 50%.
40///
41/// ## Example
42///
43/// ```
44/// use mule_map::MuleMap;
45/// use std::num::NonZero;
46/// type Hash = fnv_rs::FnvBuildHasher;  // Use whatever hash function you prefer
47///
48/// // Using Entry API
49/// let mut mule_map = MuleMap::<u32, usize, Hash>::new();
50/// assert_eq!(mule_map.get(5), None);
51/// let entry = mule_map.entry(5);
52/// entry.or_insert(10);
53/// assert_eq!(mule_map.get(5), Some(&10));
54///
55/// // Using NonZero and bump
56/// let mut mule_map_non_zero = MuleMap::<u32, NonZero<i32>, Hash>::default();
57///
58/// mule_map_non_zero.bump_non_zero(10);
59/// mule_map_non_zero.bump_non_zero(10);
60/// mule_map_non_zero.bump_non_zero(999_999);
61/// mule_map_non_zero.bump_non_zero(999_999);
62///
63/// assert_eq!(mule_map_non_zero.get(10), NonZero::<i32>::new(2).as_ref());
64/// assert_eq!(mule_map_non_zero.get(999_999),NonZero::<i32>::new(2).as_ref());
65/// ```
66#[derive(Debug, Clone)]
67pub struct MuleMap<
68    K,
69    V,
70    S,
71    const TABLE_MIN_VALUE: i128 = 0,
72    const TABLE_SIZE: usize = { u8::MAX as usize + 1 },
73> {
74    hash_map: HashMap<K, V, S>,
75    table: [Option<V>; TABLE_SIZE],
76}
77
78impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> Default
79    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
80where
81    K: Key<TABLE_MIN_VALUE>,
82    S: Default + BuildHasher,
83    <K as TryFrom<i128>>::Error: Debug,
84{
85    /// Creates an empty [`MuleMap`].
86    ///
87    /// # Example
88    ///
89    /// ```
90    /// type Hash = fnv_rs::FnvBuildHasher;
91    /// let mule_map = mule_map::MuleMap::<u32, usize, Hash>::default();
92    /// assert!(mule_map.is_empty());
93    /// ```
94    ///
95    /// See: [`MuleMap::with_capacity_and_hasher`]
96    ///
97    /// Analogous to [`HashMap::default`]
98    #[must_use]
99    #[inline]
100    fn default() -> Self {
101        Self::new()
102    }
103}
104
105impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> PartialEq
106    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
107where
108    K: Key<TABLE_MIN_VALUE>,
109    V: PartialEq,
110    S: BuildHasher,
111{
112    /// Tests for `self` and `other` values to be equal, and is used by `==`.
113    ///
114    /// # Example
115    ///
116    /// ```
117    /// let mut mule_map1 = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
118    /// mule_map1.bump_int(10);
119    /// mule_map1.bump_int(11);
120    /// mule_map1.bump_int(999_999);
121    /// mule_map1.bump_int(999_999);
122    ///
123    /// let mut mule_map2 = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
124    /// mule_map2.bump_int(10);
125    /// mule_map2.bump_int(11);
126    /// mule_map2.bump_int(999_999);
127    /// mule_map2.bump_int(999_999);
128    ///
129    /// assert!(mule_map1 ==  mule_map2)
130    /// ```
131    #[must_use]
132    #[inline]
133    fn eq(&self, other: &MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>) -> bool {
134        self.hash_map == other.hash_map && self.table == other.table
135    }
136}
137
138impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> Eq
139    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
140where
141    K: Key<TABLE_MIN_VALUE>,
142    V: Eq,
143    S: BuildHasher,
144{
145}
146
147impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> std::ops::Index<K>
148    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
149where
150    K: Key<TABLE_MIN_VALUE>,
151    S: BuildHasher,
152{
153    type Output = V;
154
155    /// Returns a reference to the value corresponding to the supplied key.
156    ///
157    /// # Example
158    ///
159    /// ```
160    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
161    /// mule_map.bump_int(10);
162    /// mule_map.bump_int(999_999);
163    /// assert_eq!(mule_map[10], 1);
164    /// assert_eq!(mule_map[999_999], 1);
165    /// assert!(test_utils::catch_unwind_silent(|| mule_map[123]).is_err());
166    ///
167    /// ```
168    ///
169    /// # Panics
170    ///
171    /// Panics if the key is not present in the `MuleMap`.
172    #[must_use]
173    #[inline]
174    fn index(&self, key: K) -> &V {
175        self.get(key).expect("No entry found for key")
176    }
177}
178
179impl<'a, K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> Extend<(K, &'a V)>
180    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
181where
182    K: Key<TABLE_MIN_VALUE>,
183    S: Default + BuildHasher,
184    V: Copy,
185{
186    /// Extends a collection with the contents of an iterator.
187    ///
188    /// # Example
189    ///
190    /// ```
191    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
192    /// mule_map.extend([(0, &10), (999_999, &3)].into_iter());
193    ///
194    /// let mut mule_map2 = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
195    /// mule_map2.insert(0, 10);
196    /// mule_map2.insert(999_999, 3);
197    /// assert_eq!(mule_map, mule_map2);
198    /// ```
199    #[inline]
200    fn extend<T: IntoIterator<Item = (K, &'a V)>>(&mut self, iter: T) {
201        for (key, val) in iter {
202            self.insert(key, *val);
203        }
204    }
205}
206
207impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> Extend<(K, V)>
208    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
209where
210    K: Key<TABLE_MIN_VALUE>,
211    S: BuildHasher,
212{
213    /// Extends a collection with the contents of an iterator.
214    ///
215    /// # Example
216    ///
217    /// ```
218    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
219    /// mule_map.extend([(0, 10), (999_999, 3)].into_iter());
220    ///
221    /// let mut mule_map2 = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
222    /// mule_map2.insert(0, 10);
223    /// mule_map2.insert(999_999, 3);
224    /// assert_eq!(mule_map, mule_map2);
225    /// ```
226    #[inline]
227    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
228        for (key, val) in iter {
229            self.insert(key, val);
230        }
231    }
232}
233
234impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize, const N: usize>
235    From<[(K, V); N]> for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
236where
237    K: Key<TABLE_MIN_VALUE>,
238    S: BuildHasher + Default,
239    <K as TryFrom<i128>>::Error: Debug,
240{
241    /// Converts a `[(K, V); N]` into a `MuleMap<K, V>`.
242    ///
243    /// If any entries in the array have equal keys,
244    /// all but one of the corresponding values will be dropped.
245    ///
246    /// # Example
247    ///
248    /// ```
249    /// use mule_map::MuleMap;
250    ///
251    /// let mut mule_map = MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
252    /// mule_map.insert(1,2);
253    /// mule_map.insert(3,4);
254    ///
255    /// let map1 = MuleMap::<_, _, fnv_rs::FnvBuildHasher>::from([(1, 2), (3, 4)]);
256    /// let map2: MuleMap<_, _, fnv_rs::FnvBuildHasher> = [(1, 2), (3, 4)].into();
257    ///
258    /// assert_eq!(map1, mule_map);
259    /// assert_eq!(map2, mule_map);
260    /// ```
261    #[must_use]
262    #[inline]
263    fn from(arr: [(K, V); N]) -> Self {
264        let mut map = Self::default();
265        for (key, val) in arr {
266            map.insert(key, val);
267        }
268        map
269    }
270}
271
272impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize> FromIterator<(K, V)>
273    for MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
274where
275    K: Key<TABLE_MIN_VALUE>,
276    S: BuildHasher + Default,
277    <K as TryFrom<i128>>::Error: Debug,
278{
279    /// Constructs a `MuleMap<K, V>` from an iterator of key-value pairs.
280    ///
281    /// If the iterator produces any pairs with equal keys,
282    /// all but one of the corresponding values will be dropped.
283    ///
284    /// # Example
285    ///
286    /// ```
287    /// use mule_map::MuleMap;
288    ///
289    /// let mut mule_map = MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
290    /// mule_map.insert(1,2);
291    /// mule_map.insert(3,4);
292    ///
293    /// let map1 = MuleMap::<_, _, fnv_rs::FnvBuildHasher>::from_iter([(1, 2), (3, 4)].into_iter());
294    ///
295    /// assert_eq!(map1, mule_map);
296    /// ```
297    #[must_use]
298    #[inline]
299    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
300        let mut map = Self::default();
301        map.extend(iter);
302        map
303    }
304}
305
306impl<K, V, S, const TABLE_MIN_VALUE: i128, const TABLE_SIZE: usize>
307    MuleMap<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE>
308where
309    K: Key<TABLE_MIN_VALUE>,
310    S: BuildHasher,
311{
312    // Hard limit, way beyond practical lookup table size. This makes it easier to calculate the key index
313    const STATIC_ASSERT_LIMIT_SIZE_TO_I32_MAX: () =
314        assert!((TABLE_SIZE as u128) <= i32::MAX as u128 + 1);
315
316    // NOTE: using `saturating_sub` to allow for when `TABLE_SIZE == 0`
317    const STATIC_ASSERT_SIZE_FITS_I128: () = assert!(
318        TABLE_MIN_VALUE
319            .checked_add(const { TABLE_SIZE.saturating_sub(1) as i128 })
320            .is_some()
321    );
322
323    const STATIC_ASSERT_ISIZE_FITS_I32: () = assert!(isize::MAX as u128 >= i32::MAX as u128);
324
325    #[must_use]
326    #[inline]
327    pub(crate) fn use_lookup_table(key: K) -> bool {
328        if const { TABLE_SIZE == 0 } {
329            return false;
330        }
331
332        let promoted_sum = K::add_promoted(
333            K::i128_as_promoted(TABLE_MIN_VALUE),
334            K::usize_as_promoted(const { TABLE_SIZE.saturating_sub(1) }),
335        );
336
337        // NOTE: `TABLE_MIN_VALUE + TABLE_SIZE - 1` and TABLE_MIN_VALUE must fit into a key type, K (with correct
338        // promotion during add for signed ints)
339        key <= promoted_sum && key >= K::i128_as_k(TABLE_MIN_VALUE)
340    }
341
342    #[inline]
343    pub(crate) fn check_bounds()
344    where
345        <K as TryFrom<i128>>::Error: Debug,
346    {
347        let () = Self::STATIC_ASSERT_LIMIT_SIZE_TO_I32_MAX;
348        let () = Self::STATIC_ASSERT_SIZE_FITS_I128;
349        let () = Self::STATIC_ASSERT_ISIZE_FITS_I32;
350
351        // NOTE: using `saturating_sub` to allow for when `TABLE_SIZE == 0`
352        // `TABLE_MIN_VALUE + TABLE_SIZE - 1` must fit in i128, because of `STATIC_ASSERT_SIZE_FITS_I128`
353        <i128 as TryInto<K>>::try_into(
354            TABLE_MIN_VALUE + const { TABLE_SIZE.saturating_sub(1) } as i128,
355        )
356        .unwrap_or_else(|_| {
357            panic!(
358                "TABLE_MIN_VALUE ({TABLE_MIN_VALUE:?}) + TABLE_SIZE ({TABLE_SIZE:?}) should fit into key type, K"
359            )
360        });
361
362        <i128 as TryInto<K>>::try_into(TABLE_MIN_VALUE)
363            .expect("TABLE_MIN_VALUE should fit into key type, K");
364    }
365
366    /// Creates an empty [`MuleMap`].
367    ///
368    /// # Example
369    ///
370    /// ```
371    /// type Hash = fnv_rs::FnvBuildHasher;
372    /// let mule_map = mule_map::MuleMap::<u32, usize, Hash>::new();
373    /// assert!(mule_map.is_empty());
374    /// ```
375    ///
376    /// See: [`MuleMap::with_capacity_and_hasher`]
377    ///
378    /// Analogous to [`HashMap::new`]
379    #[must_use]
380    #[inline]
381    pub fn new() -> Self
382    where
383        S: Default,
384        <K as TryFrom<i128>>::Error: Debug,
385    {
386        Self::with_capacity_and_hasher(0, S::default())
387    }
388
389    /// Creates an empty [`MuleMap`] with at least the provided capacity.
390    ///
391    /// # Example
392    ///
393    /// ```
394    /// type Hash = fnv_rs::FnvBuildHasher;
395    /// let mule_map = mule_map::MuleMap::<u32, usize, Hash>::with_capacity(100);
396    /// assert!(mule_map.is_empty());
397    /// ```
398    ///
399    /// See: [`MuleMap::with_capacity_and_hasher`]
400    ///
401    /// Analogous to [`HashMap::with_capacity`]
402    #[must_use]
403    #[inline]
404    pub fn with_capacity(capacity: usize) -> Self
405    where
406        S: Default,
407        <K as TryFrom<i128>>::Error: Debug,
408    {
409        Self::with_capacity_and_hasher(capacity, S::default())
410    }
411
412    /// Creates an empty [`MuleMap`] using `hash_builder`.
413    ///
414    /// # Example
415    ///
416    /// ```
417    /// type Hash = fnv_rs::FnvBuildHasher;
418    /// let mule_map = mule_map::MuleMap::<u32, usize, Hash>::with_hasher(Hash::default());
419    /// assert!(mule_map.is_empty());
420    /// ```
421    ///
422    /// See: [`MuleMap::with_capacity_and_hasher`]
423    ///
424    /// Analogous to [`HashMap::with_hasher`]
425    #[must_use]
426    #[inline]
427    pub fn with_hasher(hash_builder: S) -> Self
428    where
429        <K as TryFrom<i128>>::Error: Debug,
430    {
431        Self::with_capacity_and_hasher(0, hash_builder)
432    }
433
434    /// Creates an empty [`MuleMap`] with at least the provided capacity and using `hash_builder`.
435    ///
436    /// # Example
437    ///
438    /// ```
439    /// type Hash = fnv_rs::FnvBuildHasher;
440    /// let mule_map = mule_map::MuleMap::<u32, usize, Hash>::with_capacity_and_hasher(100, Hash::default());
441    /// assert!(mule_map.is_empty());
442    /// ```
443    ///
444    /// # Panics
445    ///
446    /// Panics if
447    ///  - `TABLE_MIN_VALUE` or `TABLE_MIN_VALUE + TABLE_SIZE - 1` doesn't fit into key type, `K`.
448    ///
449    /// Analogous to [`HashMap::with_capacity_and_hasher`]
450    #[must_use]
451    #[inline]
452    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self
453    where
454        <K as TryFrom<i128>>::Error: Debug,
455    {
456        Self::check_bounds();
457
458        MuleMap::<K, V, S, TABLE_MIN_VALUE, TABLE_SIZE> {
459            hash_map: HashMap::with_capacity_and_hasher(capacity, hash_builder),
460            table: [const { None }; TABLE_SIZE],
461        }
462    }
463
464    /// Returns capacity of the underlying hash map.
465    ///
466    /// # Example
467    ///
468    /// ```
469    /// type Hash = fnv_rs::FnvBuildHasher;
470    /// let mule_map = mule_map::MuleMap::<u32, usize, Hash>::with_capacity(100);
471    /// assert!(mule_map.capacity() >= 100);
472    /// ```
473    ///
474    /// See [`HashMap::capacity`]
475    #[must_use]
476    #[inline]
477    pub fn capacity(&self) -> usize {
478        self.hash_map.capacity()
479    }
480
481    /// Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.
482    ///
483    /// # Example
484    /// ```
485    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
486    /// mule_map.insert(1,2);
487    /// mule_map.insert(999_999,4);
488    /// mule_map.clear();
489    /// assert!(mule_map.is_empty());
490    /// ```
491    ///
492    /// See [`HashMap::clear`]
493    #[inline]
494    pub fn clear(&mut self) {
495        self.hash_map.clear();
496        self.table = [const { None }; TABLE_SIZE];
497    }
498
499    /// Returns true if the map contains a value for the specified key.
500    ///
501    /// # Example
502    /// ```
503    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
504    /// mule_map.insert(1,2);
505    /// mule_map.insert(999_999,4);
506    /// assert!(mule_map.contains_key(999_999));
507    /// assert!(mule_map.contains_key(1));
508    /// assert!(!mule_map.contains_key(2));
509    /// assert!(!mule_map.contains_key(999_998));
510    /// ```
511    /// Analogous to [`HashMap::contains_key`]
512    #[must_use]
513    #[inline]
514    pub fn contains_key(&self, key: K) -> bool {
515        if Self::use_lookup_table(key) {
516            self.table[key.key_index()].is_some()
517        } else {
518            self.hash_map.contains_key(&key)
519        }
520    }
521
522    /// Returns a reference to the value corresponding to the key.
523    ///
524    /// # Example
525    ///
526    /// ```
527    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
528    /// mule_map.insert(1,2);
529    /// mule_map.insert(999_999,4);
530    /// assert_eq!(mule_map.get(999_999), Some(&4));
531    /// assert_eq!(mule_map.get(1), Some(&2));
532    /// assert_eq!(mule_map.get(2), None);
533    /// assert_eq!(mule_map.get(999_998), None);
534    /// ```
535    ///
536    /// Analogous to [`HashMap::get`]
537    #[must_use]
538    #[inline]
539    pub fn get(&self, key: K) -> Option<&V> {
540        if Self::use_lookup_table(key) {
541            self.table[key.key_index()].as_ref()
542        } else {
543            let result = self.hash_map.get(&key);
544            result
545        }
546    }
547
548    /// Returns the key-value pair corresponding to the supplied key.
549    ///
550    /// # Example
551    ///
552    /// ```
553    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
554    /// mule_map.insert(1,2);
555    /// mule_map.insert(999_999,4);
556    /// assert_eq!(mule_map.get_key_value(999_999), Some((999_999, &4)));
557    /// assert_eq!(mule_map.get_key_value(1), Some((1,&2)));
558    /// assert_eq!(mule_map.get_key_value(2), None);
559    /// assert_eq!(mule_map.get_key_value(999_998), None);
560    /// ```
561    ///
562    /// Analogous to [`HashMap::get_key_value`]
563    #[must_use]
564    #[inline]
565    pub fn get_key_value(&self, key: K) -> Option<(K, &V)> {
566        let result = Some(key);
567        result.zip(self.get(key))
568    }
569
570    /// Attempts to get mutable references to N values in the map at once.
571    ///
572    /// ...
573    /// # Example
574    ///
575    /// ```
576    /// let mut map = mule_map::MuleMap::<_, _, fnv_rs::FnvBuildHasher>::from([(1, 1602), (2, 1807), (999_999, 1691), (999_998, 1800)]);
577    ///
578    /// assert_eq!(map.get_disjoint_mut([1, 999_999]), [Some(&mut 1602), Some(&mut 1691)]);
579    /// assert_eq!(map.get_disjoint_mut([2, 4, 999_998, 999_990]), [Some(&mut 1807), None, Some(&mut 1800), None]);
580    /// ```
581    ///
582    /// # Panics
583    /// Panics if any keys are overlapping.
584    ///
585    /// Analogous to [`HashMap::get_disjoint_mut`]
586    #[allow(clippy::reversed_empty_ranges)]
587    pub fn get_disjoint_mut<const N: usize>(&mut self, ks: [K; N]) -> [Option<&'_ mut V>; N]
588    where
589        K: Key<TABLE_MIN_VALUE>,
590    {
591        let mut key_indices = [const { 0..0 }; N];
592        let references: [&K; N] = std::array::from_fn(|i| &ks[i]);
593
594        let mut result = self.hash_map.get_disjoint_mut(references);
595
596        for (i, &key) in ks.iter().enumerate() {
597            if Self::use_lookup_table(key) {
598                #[allow(clippy::range_plus_one)]
599                {
600                    key_indices[i] = key.key_index()..key.key_index() + 1;
601                }
602            }
603        }
604
605        for (i, range) in self
606            .table
607            .get_disjoint_mut(key_indices)
608            .expect("keys should not overlap, or be out of bounds")
609            .into_iter()
610            .enumerate()
611        {
612            for v in range {
613                if v.is_some() {
614                    result[i] = v.as_mut();
615                }
616            }
617        }
618
619        result
620    }
621
622    /// Attempts to get mutable references to `N` values in the map at once, without validating that the values are
623    /// unique.
624    ///
625    /// ...
626    /// # Example
627    ///
628    /// ```
629    /// let mut map = mule_map::MuleMap::<_, _, fnv_rs::FnvBuildHasher>::from([(1, 1602), (2, 1807), (999_999, 1691), (999_998, 1800)]);
630    ///
631    /// assert_eq!(unsafe {map.get_disjoint_unchecked_mut([1, 999_999])}, [Some(&mut 1602), Some(&mut 1691)]);
632    /// assert_eq!(unsafe {map.get_disjoint_unchecked_mut([2, 4, 999_998, 999_990])}, [Some(&mut 1807), None, Some(&mut 1800), None]);
633    /// ```
634    ///
635    /// # Safety
636    /// Calling this method with overlapping keys is undefined behavior even if the resulting references are not used.
637    /// This makes calls to [`HashMap::get_disjoint_unchecked_mut`] and [`slice::get_disjoint_unchecked_mut`]
638    ///
639    /// Analogous to [`HashMap::get_disjoint_unchecked_mut`]
640    #[allow(clippy::reversed_empty_ranges)]
641    pub unsafe fn get_disjoint_unchecked_mut<const N: usize>(
642        &mut self,
643        ks: [K; N],
644    ) -> [Option<&'_ mut V>; N]
645    where
646        K: Key<TABLE_MIN_VALUE>,
647    {
648        let mut key_indices = [const { 0..0 }; N];
649        let references: [&K; N] = std::array::from_fn(|i| &ks[i]);
650
651        let mut result = unsafe { self.hash_map.get_disjoint_unchecked_mut(references) };
652
653        for (i, &key) in ks.iter().enumerate() {
654            if Self::use_lookup_table(key) {
655                #[allow(clippy::range_plus_one)]
656                {
657                    key_indices[i] = key.key_index()..key.key_index() + 1;
658                }
659            }
660        }
661
662        for (i, range) in unsafe {
663            self.table
664                .get_disjoint_unchecked_mut(key_indices)
665                .into_iter()
666                .enumerate()
667        } {
668            for v in range {
669                if v.is_some() {
670                    result[i] = v.as_mut();
671                }
672            }
673        }
674
675        result
676    }
677
678    /// Returns a mutable reference to the value corresponding to the key.
679    ///
680    /// # Example
681    ///
682    /// ```
683    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
684    /// mule_map.insert(1,2);
685    /// mule_map.insert(999_999,4);
686    /// assert_eq!(mule_map.get_mut(999_999), Some(&mut 4));
687    /// assert_eq!(mule_map.get_mut(1), Some(&mut 2));
688    /// assert_eq!(mule_map.get_mut(2), None);
689    /// assert_eq!(mule_map.get_mut(999_998), None);
690    /// ```
691    ///
692    /// Analogous to [`HashMap::get_mut`]
693    #[must_use]
694    #[inline]
695    pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
696        if Self::use_lookup_table(key) {
697            self.table[key.key_index()].as_mut()
698        } else {
699            self.hash_map.get_mut(&key)
700        }
701    }
702
703    /// Returns a reference to the map’s [`BuildHasher`].
704    ///
705    /// # Example
706    ///
707    /// ```
708    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
709    /// assert_eq!(&fnv_rs::FnvBuildHasher::default(), mule_map.hasher());
710    /// ```
711    ///
712    /// Analogous to [`HashMap::hasher`]
713    #[must_use]
714    #[inline]
715    pub fn hasher(&self) -> &S {
716        self.hash_map.hasher()
717    }
718
719    /// Inserts a key-value pair into the map. If the map did not have this key present, None is returned. If the map
720    /// did have this key present, the value is updated, and the old value is returned.
721    ///
722    /// # Example
723    ///
724    /// ```
725    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
726    /// mule_map.insert(1,2);
727    /// mule_map.insert(999_999,4);
728    /// assert_eq!(mule_map.get_key_value(999_999), Some((999_999, &4)));
729    /// assert_eq!(mule_map.get_key_value(1), Some((1,&2)));
730    /// assert_eq!(mule_map.get_key_value(2), None);
731    /// assert_eq!(mule_map.get_key_value(999_998), None);
732    /// ```
733    ///
734    /// Analogous to [`HashMap::insert`]
735    #[inline]
736    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
737        if Self::use_lookup_table(key) {
738            self.table[key.key_index()].replace(value)
739        } else {
740            self.hash_map.insert(key, value)
741        }
742    }
743
744    /// Returns true if the map contains no elements. Checks both the lookup table and the hashmap. Note, there is no
745    /// tracking in the lookup table - in the worst case, we have to check all elements of the lookup table.
746    ///
747    /// # Example
748    ///
749    /// ```
750    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
751    /// assert!(mule_map.is_empty());
752    /// mule_map.insert(1,2);
753    /// assert!(!mule_map.is_empty());
754    /// mule_map.clear();
755    /// assert!(mule_map.is_empty());
756    /// mule_map.insert(999_999,4);
757    /// assert!(!mule_map.is_empty());
758    /// mule_map.clear();
759    /// assert!(mule_map.is_empty());
760    /// ```
761    ///
762    ///  Analogous to [`HashMap::is_empty`]
763    #[must_use]
764    #[inline]
765    pub fn is_empty(&self) -> bool {
766        self.hash_map.is_empty() && !self.table.iter().any(Option::is_some)
767    }
768
769    /// Returns the number of elements in the map. Checks both the lookup table and the hashmap. Note, there is no
770    /// tracking in the lookup table, so this will scan the whole table.
771    ///
772    /// # Example
773    ///
774    /// ```
775    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
776    /// assert_eq!(mule_map.len(), 0);
777    /// mule_map.insert(1,2);
778    /// assert_eq!(mule_map.len(), 1);
779    /// mule_map.insert(999_999,4);
780    /// assert_eq!(mule_map.len(), 2);
781    /// mule_map.clear();
782    /// assert_eq!(mule_map.len(), 0);
783    /// ```
784    ///
785    ///  Analogous to [`HashMap::len`]
786    #[must_use]
787    #[inline]
788    pub fn len(&self) -> usize {
789        self.hash_map.len() + self.table.iter().filter(|&x| x.is_some()).count()
790    }
791
792    /// Removes a key from the map, returning the value at the key if the key was previously in the map.
793    ///
794    /// # Example
795    ///
796    /// ```
797    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
798    /// mule_map.insert(1,2);
799    /// assert_eq!(mule_map.remove(0), None);
800    /// assert!(!mule_map.is_empty());
801    /// assert_eq!(mule_map.remove(1), Some(2));
802    /// assert!(mule_map.is_empty());
803    /// mule_map.insert(999_999,4);
804    /// assert_eq!(mule_map.remove(999_999), Some(4));
805    /// assert!(mule_map.is_empty());
806    /// ```
807    ///
808    ///  Analogous to [`HashMap::remove`]
809    #[inline]
810    pub fn remove(&mut self, key: K) -> Option<V> {
811        if Self::use_lookup_table(key) {
812            self.table[key.key_index()].take()
813        } else {
814            self.hash_map.remove(&key)
815        }
816    }
817
818    /// Removes a key from the map, returning the stored key and value if the key was previously in the map.
819    ///
820    /// # Example
821    ///
822    /// ```
823    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
824    /// mule_map.insert(1,2);
825    /// assert_eq!(mule_map.remove_entry(0), None);
826    /// assert!(!mule_map.is_empty());
827    /// assert_eq!(mule_map.remove_entry(1), Some((1, 2)));
828    /// assert!(mule_map.is_empty());
829    /// mule_map.insert(999_999,4);
830    /// assert_eq!(mule_map.remove_entry(999_999), Some((999_999,4)));
831    /// assert!(mule_map.is_empty());
832    /// ```
833    ///
834    ///  Analogous to [`HashMap::remove_entry`]
835    #[inline]
836    pub fn remove_entry(&mut self, key: K) -> Option<(K, V)> {
837        if Self::use_lookup_table(key) {
838            let result = Some(key);
839            result.zip(self.table[key.key_index()].take())
840        } else {
841            self.hash_map.remove_entry(&key)
842        }
843    }
844
845    /// Calls `reserve` on the underlying [`HashMap`]
846    ///
847    /// # Example
848    ///
849    /// ```
850    /// let mut mule_map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::default();
851    /// mule_map.reserve(100);
852    /// ```
853    ///
854    ///  Analogous to [`HashMap::reserve`]
855    #[inline]
856    pub fn reserve(&mut self, additional: usize) {
857        self.hash_map.reserve(additional);
858    }
859
860    /// Calls `shrink_to` on the underlying [`HashMap`]
861    ///
862    /// # Example
863    ///
864    /// ```
865    /// let mut map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::with_capacity(100);
866    /// map.insert(999_999, 2);
867    /// map.insert(999_998, 4);
868    /// assert!(map.capacity() >= 100);
869    /// map.shrink_to(10);
870    /// assert!(map.capacity() >= 10);
871    /// map.shrink_to(0);
872    /// assert!(map.capacity() >= 2);
873    /// ```
874    ///
875    ///  Analogous to [`HashMap::shrink_to`]
876    #[inline]
877    pub fn shrink_to(&mut self, min_capacity: usize) {
878        self.hash_map.shrink_to(min_capacity);
879    }
880
881    /// Calls `shrink_to_fit` on the underlying [`HashMap`]
882    ///
883    /// # Example
884    ///
885    /// ```
886    /// let mut map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::with_capacity(100);
887    /// map.insert(999_999, 2);
888    /// map.insert(999_998, 4);
889    /// assert!(map.capacity() >= 100);
890    /// map.shrink_to_fit();
891    /// assert!(map.capacity() >= 2);
892    /// ```
893    ///
894    ///  Analogous to [`HashMap::shrink_to_fit`]
895    #[inline]
896    pub fn shrink_to_fit(&mut self) {
897        self.hash_map.shrink_to_fit();
898    }
899
900    /// Calls `try_reserve` on the underlying [`HashMap`]
901    ///
902    ///
903    /// # Example
904    ///
905    /// ```
906    /// let mut map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::new();
907    /// map.try_reserve(10).expect("Should have space to allocate 10 elements");
908    /// ```
909    ///
910    /// # Errors
911    ///
912    /// If the capacity overflows, or the allocator reports a failure, then an error is returned.
913    ///
914    ///  Analogous to [`HashMap::try_reserve`]
915    #[inline]
916    pub fn try_reserve(
917        &mut self,
918        additional: usize,
919    ) -> Result<(), std::collections::TryReserveError> {
920        self.hash_map.try_reserve(additional)
921    }
922
923    /// Modify the values at location `key` by calling `f` on its value. If no value present, create a new value set to
924    /// `default`.
925    ///
926    /// # Example
927    ///
928    /// ```
929    /// let mut map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::new();
930    /// map.modify_or_insert(10, |x| *x += 1, 100);
931    /// assert!(map.get(10) == Some(&100));
932    /// map.modify_or_insert(10, |x| *x += 1, 100);
933    /// assert!(map.get(10) == Some(&101));
934    /// map.modify_or_insert(999_999, |x| *x += 1, 100);
935    /// assert!(map.get(999_999) == Some(&100));
936    /// map.modify_or_insert(999_999, |x| *x += 1, 100);
937    /// assert!(map.get(999_999) == Some(&101));
938    /// ```
939    ///
940    #[inline]
941    pub fn modify_or_insert<F>(&mut self, key: K, f: F, default: V)
942    where
943        F: FnOnce(&mut V),
944    {
945        if Self::use_lookup_table(key) {
946            let value = &mut self.table[key.key_index()];
947            match value {
948                Some(x) => f(x),
949                None => *value = Some(default),
950            }
951        } else {
952            self.hash_map.entry(key).and_modify(f).or_insert(default);
953        }
954    }
955
956    /// Adds 1 to the value stored at location `key`. If the value is not present, the value 1 will be set at that
957    /// location.
958    ///
959    /// *NOTE:* This method can only be called with values that implement `AddAssign`, like primitives. For `NonZero<T>`
960    /// values use [`MuleMap::bump_non_zero`] - It uses the niche optimization for better performance.
961    ///
962    /// # Example
963    ///
964    /// ```
965    /// let mut map = mule_map::MuleMap::<u32, i32, fnv_rs::FnvBuildHasher>::new();
966    /// map.bump_int(10);
967    /// assert!(map.get(10) == Some(&1));
968    /// map.bump_int(10);
969    /// assert!(map.get(10) == Some(&2));
970    /// map.bump_int(999_999);
971    /// assert!(map.get(999_999) == Some(&1));
972    /// map.bump_int(999_999);
973    /// assert!(map.get(999_999) == Some(&2));
974    /// ```
975    ///
976    /// # Panics
977    ///
978    /// May panics if adding 1 results in overflow.
979    #[inline]
980    pub fn bump_int(&mut self, key: K)
981    where
982        V: AddAssign<V> + num_traits::One + num_traits::Zero,
983    {
984        if Self::use_lookup_table(key) {
985            *self.table[key.key_index()].get_or_insert(V::zero()) += V::one();
986        } else {
987            self.hash_map
988                .entry(key)
989                .and_modify(|counter| *counter += V::one())
990                .or_insert(V::one());
991        }
992    }
993
994    /// Adds 1 to the value stored at location `key`. If the value is not present, the value 1 will be set at that
995    /// location. Uses the niche optimization for better performance with `Option<NonZero<T>>`.
996    ///
997    /// *NOTE:* This method can only be called with `NonZero<T>` values. For primitive values use [`MuleMap::bump_int`].
998    ///
999    /// # Example
1000    ///
1001    /// ```
1002    /// use std::num::NonZero;
1003    /// let mut map = mule_map::MuleMap::<u32, NonZero<i32>, fnv_rs::FnvBuildHasher>::new();
1004    /// map.bump_non_zero(10);
1005    ///
1006    /// assert!(map.get(10) == Some(&const { NonZero::new(1).expect("1 is not 0") }));
1007    /// map.bump_non_zero(10);
1008    /// assert!(map.get(10) == Some(&const { NonZero::new(2).expect("2 is not 0") }));
1009    /// map.bump_non_zero(999_999);
1010    /// assert!(map.get(999_999) == Some(&const { NonZero::new(1).expect("1 is not 0") }));
1011    /// map.bump_non_zero(999_999);
1012    /// assert!(map.get(999_999) == Some(&const { NonZero::new(2).expect("2 is not 0") }));
1013    /// ```
1014    ///
1015    /// # Panics
1016    ///
1017    /// Panics if adding 1 results in overflow.
1018    #[inline]
1019    pub fn bump_non_zero(&mut self, key: K)
1020    where
1021        V: NonZeroInt + bytemuck::PodInOption,
1022        <V as NonZeroInt>::UnderlyingType: AddAssign<V::UnderlyingType>,
1023        <V as NonZeroInt>::UnderlyingType: bytemuck::Pod + PrimInt,
1024    {
1025        use num_traits::One;
1026
1027        if Self::use_lookup_table(key) {
1028            *bytemuck::cast_mut::<Option<V>, V::UnderlyingType>(
1029                &mut self.table[key.key_index()],
1030            ) += V::UnderlyingType::one();
1031        } else {
1032            self.hash_map
1033                .entry(key)
1034                .and_modify(|counter| {
1035                    *counter = counter
1036                        .checked_add(V::UnderlyingType::one())
1037                        .expect("Addition should not overflow");
1038                })
1039                .or_insert(V::ONE);
1040        }
1041    }
1042
1043    /// Gets the given key’s corresponding entry in the map for in-place manipulation.
1044    ///
1045    /// # Example
1046    ///
1047    /// ```
1048    /// let mut map = mule_map::MuleMap::<u32, usize, fnv_rs::FnvBuildHasher>::new();
1049    /// map.entry(5).or_insert(3);
1050    /// assert!(map.get(5) == Some(&3));
1051    /// map.entry(5).and_modify(|e| *e += 1).or_insert(1);
1052    /// assert!(map.get(5) == Some(&4));
1053    /// ```
1054    ///
1055    /// Analogous to [`HashMap::entry`]
1056    #[must_use]
1057    #[inline]
1058    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
1059        if Self::use_lookup_table(key) {
1060            let value: &mut Option<V> = &mut self.table[key.key_index()];
1061            match value {
1062                Some(_) => {
1063                    Entry::<K, V>::Occupied(OccupiedEntry::Vec(OccupiedVecEntry { value, key }))
1064                }
1065                None => Entry::<K, V>::Vacant(VacantEntry::Vec(VacantVecEntry { value, key })),
1066            }
1067        } else {
1068            match self.hash_map.entry(key) {
1069                std::collections::hash_map::Entry::Occupied(base) => {
1070                    Entry::<K, V>::Occupied(OccupiedEntry::HashMap(OccupiedHashMapEntry { base }))
1071                }
1072                std::collections::hash_map::Entry::Vacant(base) => {
1073                    Entry::<K, V>::Vacant(VacantEntry::HashMap(VacantHashMapEntry { base }))
1074                }
1075            }
1076        }
1077    }
1078}
1079
1080#[sealed]
1081#[doc(hidden)]
1082pub trait NonZeroInt {
1083    type UnderlyingType;
1084    const ONE: Self;
1085    #[must_use]
1086    #[inline]
1087    fn checked_add(self, other: Self::UnderlyingType) -> Option<Self>
1088    where
1089        Self::UnderlyingType: bytemuck::Pod,
1090        Self::UnderlyingType: AddAssign<Self::UnderlyingType>,
1091        Self: bytemuck::PodInOption,
1092        Self::UnderlyingType: PrimInt,
1093    {
1094        let mut result = Some(self);
1095        let x = bytemuck::cast_mut::<Option<Self>, Self::UnderlyingType>(&mut result);
1096        *x += other;
1097        result
1098    }
1099}
1100
1101macro_rules! impl_non_zero {
1102    (non_zero=$non_zero_type:ty, underlying=$underlying_type:ty) => {
1103        #[sealed]
1104        impl NonZeroInt for $non_zero_type {
1105            const ONE: $non_zero_type = const { NonZero::new(1).expect("1 is not 0") };
1106            type UnderlyingType = $underlying_type;
1107        }
1108    };
1109}
1110
1111impl_non_zero!(non_zero = std::num::NonZeroI8, underlying = i8);
1112impl_non_zero!(non_zero = std::num::NonZeroI16, underlying = i16);
1113impl_non_zero!(non_zero = std::num::NonZeroI32, underlying = i32);
1114impl_non_zero!(non_zero = std::num::NonZeroI64, underlying = i64);
1115impl_non_zero!(non_zero = std::num::NonZeroI128, underlying = i128);
1116impl_non_zero!(non_zero = std::num::NonZeroIsize, underlying = isize);
1117
1118impl_non_zero!(non_zero = std::num::NonZeroU8, underlying = u8);
1119impl_non_zero!(non_zero = std::num::NonZeroU16, underlying = u16);
1120impl_non_zero!(non_zero = std::num::NonZeroU32, underlying = u32);
1121impl_non_zero!(non_zero = std::num::NonZeroU64, underlying = u64);
1122impl_non_zero!(non_zero = std::num::NonZeroU128, underlying = u128);
1123impl_non_zero!(non_zero = std::num::NonZeroUsize, underlying = usize);
1124
1125#[cfg(test)]
1126mod tests {
1127    use super::*;
1128
1129    #[test]
1130    fn use_lookup_table() {
1131        type DefaultRange = MuleMap<i32, i32, fnv_rs::FnvBuildHasher, 0, { u8::MAX as usize + 1 }>;
1132        type NegRange = MuleMap<i32, i32, fnv_rs::FnvBuildHasher, -100, { u8::MAX as usize + 1 }>;
1133        type ZeroSize = MuleMap<i32, i32, fnv_rs::FnvBuildHasher, 0, { u8::MIN as usize }>;
1134
1135        assert!(DefaultRange::use_lookup_table(0));
1136        assert!(!DefaultRange::use_lookup_table(-1));
1137        assert!(DefaultRange::use_lookup_table(255));
1138        assert!(!DefaultRange::use_lookup_table(256));
1139
1140        assert!(NegRange::use_lookup_table(-100));
1141        assert!(!NegRange::use_lookup_table(-101));
1142        assert!(NegRange::use_lookup_table(155));
1143        assert!(!NegRange::use_lookup_table(156));
1144
1145        assert!(!ZeroSize::use_lookup_table(0));
1146        assert!(!ZeroSize::use_lookup_table(1));
1147    }
1148    #[test]
1149    fn check_table_range() {
1150        type BadRange = MuleMap<u8, i32, fnv_rs::FnvBuildHasher, 0, { u8::MAX as usize + 2 }>;
1151        type BadRange2 = MuleMap<u8, i32, fnv_rs::FnvBuildHasher, -1, { u8::MAX as usize }>;
1152        type OkRange = MuleMap<u8, i32, fnv_rs::FnvBuildHasher, 0, { u8::MAX as usize + 1 }>;
1153        type OkRange2 = MuleMap<u8, i32, fnv_rs::FnvBuildHasher, 1, { u8::MAX as usize }>;
1154        type ZeroSize = MuleMap<u8, i32, fnv_rs::FnvBuildHasher, 0, { u8::MIN as usize }>;
1155
1156        assert!(test_utils::catch_unwind_silent(BadRange::new).is_err());
1157        assert!(test_utils::catch_unwind_silent(BadRange2::new).is_err());
1158        assert!(test_utils::catch_unwind_silent(OkRange::new).is_ok());
1159        assert!(test_utils::catch_unwind_silent(OkRange2::new).is_ok());
1160        assert!(test_utils::catch_unwind_silent(ZeroSize::new).is_ok());
1161    }
1162}
mule_map/mule_map.rs

mule_map/
mule_map.rs
