auto_hash_map/
map.rs

1use std::{
2    borrow::Borrow,
3    fmt::{Debug, Formatter},
4    hash::{BuildHasher, BuildHasherDefault, Hash},
5    marker::PhantomData,
6};
7
8use bincode::{
9    Decode, Encode,
10    de::Decoder,
11    enc::Encoder,
12    error::{DecodeError, EncodeError},
13    impl_borrow_decode,
14};
15use hashbrown::hash_map::HashMap;
16use rustc_hash::FxHasher;
17use serde::{
18    Deserialize, Deserializer, Serialize, Serializer,
19    de::{MapAccess, Visitor},
20    ser::SerializeMap,
21};
22use shrink_to_fit::ShrinkToFit;
23use smallvec::SmallVec;
24
25use crate::{MAX_LIST_SIZE, MIN_HASH_SIZE};
26
27#[derive(Clone)]
28pub enum AutoMap<K, V, H = BuildHasherDefault<FxHasher>, const I: usize = 0> {
29    List(SmallVec<[(K, V); I]>),
30    Map(Box<HashMap<K, V, H>>),
31}
32
33impl<K, V, H, const I: usize> Default for AutoMap<K, V, H, I> {
34    fn default() -> Self {
35        Self::List(Default::default())
36    }
37}
38
39impl<K: Debug, V: Debug, H, const I: usize> Debug for AutoMap<K, V, H, I> {
40    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
41        f.debug_map().entries(self.iter()).finish()
42    }
43}
44
45impl<K, V> AutoMap<K, V, BuildHasherDefault<FxHasher>, 0> {
46    /// see [HashMap::new](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.new)
47    pub const fn new() -> Self {
48        AutoMap::List(SmallVec::new_const())
49    }
50
51    /// see [HashMap::with_capacity](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.with_capacity)
52    pub fn with_capacity(capacity: usize) -> Self {
53        if capacity < MAX_LIST_SIZE {
54            AutoMap::List(SmallVec::with_capacity(capacity))
55        } else {
56            AutoMap::Map(Box::new(HashMap::with_capacity_and_hasher(
57                capacity,
58                Default::default(),
59            )))
60        }
61    }
62}
63
64impl<K, V, H, const I: usize> AutoMap<K, V, H, I> {
65    /// see [HashMap::with_hasher](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html#method.with_hasher)
66    pub const fn with_hasher() -> Self {
67        AutoMap::List(SmallVec::new_const())
68    }
69
70    /// see [HashMap::with_capacity_and_hasher](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html#method.with_capacity_and_hasher)
71    pub fn with_capacity_and_hasher(capacity: usize, hasher: H) -> Self {
72        if capacity <= MAX_LIST_SIZE {
73            AutoMap::List(SmallVec::with_capacity(capacity))
74        } else {
75            AutoMap::Map(Box::new(HashMap::with_capacity_and_hasher(
76                capacity, hasher,
77            )))
78        }
79    }
80
81    /// see [HashMap::clear](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html#method.clear)
82    pub fn clear(&mut self) {
83        match self {
84            AutoMap::List(list) => list.clear(),
85            AutoMap::Map(map) => map.clear(),
86        }
87    }
88}
89
90impl<K: Eq + Hash, V, H: BuildHasher + Default, const I: usize> AutoMap<K, V, H, I> {
91    fn convert_to_map(&mut self) -> &mut HashMap<K, V, H> {
92        if let AutoMap::List(list) = self {
93            let mut map = HashMap::with_capacity_and_hasher(MAX_LIST_SIZE * 2, Default::default());
94            map.extend(list.drain(..));
95            *self = AutoMap::Map(Box::new(map));
96        }
97        if let AutoMap::Map(map) = self {
98            map
99        } else {
100            unreachable!()
101        }
102    }
103
104    fn convert_to_list(&mut self) -> &mut SmallVec<[(K, V); I]> {
105        if let AutoMap::Map(map) = self {
106            let mut list = SmallVec::with_capacity(MAX_LIST_SIZE);
107            list.extend(map.drain());
108            *self = AutoMap::List(list);
109        }
110        if let AutoMap::List(list) = self {
111            list
112        } else {
113            unreachable!()
114        }
115    }
116
117    /// see [HashMap::insert](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.insert)
118    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
119        match self {
120            AutoMap::List(list) => {
121                for (k, v) in list.iter_mut() {
122                    if *k == key {
123                        return Some(std::mem::replace(v, value));
124                    }
125                }
126                if list.len() >= MAX_LIST_SIZE {
127                    let map = self.convert_to_map();
128                    map.insert(key, value);
129                } else {
130                    list.push((key, value));
131                }
132                None
133            }
134            AutoMap::Map(map) => map.insert(key, value),
135        }
136    }
137
138    /// see [HashMap::remove](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.remove)
139    pub fn remove(&mut self, key: &K) -> Option<V> {
140        match self {
141            AutoMap::List(list) => {
142                for i in 0..list.len() {
143                    if list[i].0 == *key {
144                        return Some(list.swap_remove(i).1);
145                    }
146                }
147                None
148            }
149            AutoMap::Map(map) => map.remove(key),
150        }
151    }
152
153    /// see [HashMap::extend](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.extend)
154    pub fn extend(&mut self, iter: impl IntoIterator<Item = (K, V)>) {
155        let iter = iter.into_iter();
156        match self {
157            AutoMap::List(list) => {
158                let (lower, _) = iter.size_hint();
159                if list.len() + lower > MAX_LIST_SIZE {
160                    let map = self.convert_to_map();
161                    map.extend(iter);
162                    // The hint is not enforced
163                    if map.len() < MIN_HASH_SIZE {
164                        self.convert_to_list();
165                    }
166                    return;
167                }
168                for (k, v) in iter {
169                    self.insert(k, v);
170                }
171            }
172            AutoMap::Map(map) => {
173                map.extend(iter);
174            }
175        }
176    }
177
178    /// see [HashMap::entry](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.entry)
179    pub fn entry(&mut self, key: K) -> Entry<'_, K, V, H, I> {
180        let this = self as *mut Self;
181        match self {
182            AutoMap::List(list) => match list.iter().position(|(k, _)| *k == key) {
183                Some(index) => Entry::Occupied(OccupiedEntry::List { list, index }),
184                None => Entry::Vacant(VacantEntry::List { this, list, key }),
185            },
186            AutoMap::Map(map) => match map.entry(key) {
187                hashbrown::hash_map::Entry::Occupied(entry) => {
188                    Entry::Occupied(OccupiedEntry::Map { this, entry })
189                }
190                hashbrown::hash_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry::Map(entry)),
191            },
192        }
193    }
194
195    pub fn raw_entry_mut<Q>(&mut self, key: &Q) -> RawEntry<'_, K, V, H, I>
196    where
197        K: Borrow<Q>,
198        Q: Hash + Eq + ?Sized,
199    {
200        let this = self as *mut Self;
201        match self {
202            AutoMap::List(list) => match list.iter().position(|(k, _)| k.borrow() == key) {
203                Some(index) => RawEntry::Occupied(OccupiedRawEntry::List { list, index }),
204                None => RawEntry::Vacant(VacantRawEntry::List { this, list }),
205            },
206            AutoMap::Map(map) => match map.raw_entry_mut().from_key(key) {
207                hashbrown::hash_map::RawEntryMut::Occupied(entry) => {
208                    RawEntry::Occupied(OccupiedRawEntry::Map { this, entry })
209                }
210                hashbrown::hash_map::RawEntryMut::Vacant(entry) => {
211                    RawEntry::Vacant(VacantRawEntry::Map(entry))
212                }
213            },
214        }
215    }
216
217    /// see [HashMap::retain](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.retain)
218    pub fn retain<F>(&mut self, mut f: F)
219    where
220        F: FnMut(&K, &mut V) -> bool,
221    {
222        match self {
223            AutoMap::List(list) => {
224                // Don't use `Vec::retain`, as that uses a slower algorithm to maintain order,
225                // which we don't care about
226                let mut len = list.len();
227                let mut i = 0;
228                while i < len {
229                    let (key, value) = &mut list[i];
230                    if !f(key, value) {
231                        list.swap_remove(i);
232                        len -= 1;
233                    } else {
234                        i += 1;
235                    }
236                }
237            }
238            AutoMap::Map(map) => {
239                map.retain(f);
240            }
241        }
242    }
243
244    pub fn extract_if<'l, F>(&'l mut self, f: F) -> ExtractIfIter<'l, K, V, I, F>
245    where
246        F: for<'a, 'b> FnMut(&'a K, &'b mut V) -> bool,
247    {
248        match self {
249            AutoMap::List(list) => ExtractIfIter::List { list, index: 0, f },
250            AutoMap::Map(map) => ExtractIfIter::Map(map.extract_if(f)),
251        }
252    }
253
254    /// see [HashMap::shrink_to_fit](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.shrink_to_fit)
255    pub fn shrink_to_fit(&mut self) {
256        match self {
257            AutoMap::List(list) => list.shrink_to_fit(),
258            AutoMap::Map(map) => {
259                if map.len() <= MAX_LIST_SIZE {
260                    let mut list = SmallVec::with_capacity(map.len());
261                    list.extend(map.drain());
262                    *self = AutoMap::List(list);
263                } else {
264                    map.shrink_to_fit();
265                }
266            }
267        }
268    }
269
270    pub fn shrink_amortized(&mut self) {
271        match self {
272            AutoMap::List(list) => {
273                if list.capacity() > list.len() * 3 {
274                    list.shrink_to_fit();
275                }
276            }
277            AutoMap::Map(map) => {
278                if map.len() <= MIN_HASH_SIZE {
279                    let mut list = SmallVec::with_capacity(map.len());
280                    list.extend(map.drain());
281                    *self = AutoMap::List(list);
282                } else if map.capacity() > map.len() * 3 {
283                    map.shrink_to_fit();
284                }
285            }
286        }
287    }
288}
289
290impl<K: Eq + Hash, V, H: BuildHasher, const I: usize> AutoMap<K, V, H, I> {
291    /// see [HashMap::get](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get)
292    pub fn get<Q>(&self, key: &Q) -> Option<&V>
293    where
294        K: Borrow<Q>,
295        Q: Hash + Eq + ?Sized,
296    {
297        match self {
298            AutoMap::List(list) => list
299                .iter()
300                .find_map(|(k, v)| if *k.borrow() == *key { Some(v) } else { None }),
301            AutoMap::Map(map) => map.get(key),
302        }
303    }
304
305    /// see [HashMap::get_mut](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.get_mut)
306    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
307        match self {
308            AutoMap::List(list) => list
309                .iter_mut()
310                .find_map(|(k, v)| if *k == *key { Some(v) } else { None }),
311            AutoMap::Map(map) => map.get_mut(key),
312        }
313    }
314
315    /// see [HashMap::contains_key](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.contains_key)
316    pub fn contains_key(&self, key: &K) -> bool {
317        match self {
318            AutoMap::List(list) => list.iter().any(|(k, _)| *k == *key),
319            AutoMap::Map(map) => map.contains_key(key),
320        }
321    }
322}
323
324impl<K, V, H, const I: usize> AutoMap<K, V, H, I> {
325    /// see [HashMap::iter](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.iter)
326    pub fn iter(&self) -> Iter<'_, K, V> {
327        match self {
328            AutoMap::List(list) => Iter::List(list.iter()),
329            AutoMap::Map(map) => Iter::Map(map.iter()),
330        }
331    }
332    /// see [HashMap::iter_mut](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.iter_mut)
333    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
334        match self {
335            AutoMap::List(list) => IterMut::List(list.iter_mut()),
336            AutoMap::Map(map) => IterMut::Map(map.iter_mut()),
337        }
338    }
339
340    /// see [HashMap::is_empty](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.is_empty)
341    pub fn is_empty(&self) -> bool {
342        match self {
343            AutoMap::List(list) => list.is_empty(),
344            AutoMap::Map(map) => map.is_empty(),
345        }
346    }
347
348    /// see [HashMap::len](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.len)
349    pub fn len(&self) -> usize {
350        match self {
351            AutoMap::List(list) => list.len(),
352            AutoMap::Map(map) => map.len(),
353        }
354    }
355
356    /// see [HashMap::values_mut](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.values_mut)
357    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
358        match self {
359            AutoMap::List(list) => ValuesMut::List(list.iter_mut()),
360            AutoMap::Map(map) => ValuesMut::Map(map.values_mut()),
361        }
362    }
363
364    /// see [HashMap::values](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.values)
365    pub fn values(&self) -> Values<'_, K, V> {
366        match self {
367            AutoMap::List(list) => Values::List(list.iter()),
368            AutoMap::Map(map) => Values::Map(map.values()),
369        }
370    }
371
372    /// see [HashMap::into_values](https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.into_values)
373    pub fn into_values(self) -> IntoValues<K, V, I> {
374        match self {
375            AutoMap::List(list) => IntoValues::List(list.into_iter()),
376            AutoMap::Map(map) => IntoValues::Map(map.into_values()),
377        }
378    }
379}
380
381impl<K, V, H, const I: usize> IntoIterator for AutoMap<K, V, H, I> {
382    type Item = (K, V);
383    type IntoIter = IntoIter<K, V, I>;
384
385    fn into_iter(self) -> Self::IntoIter {
386        match self {
387            AutoMap::List(list) => IntoIter::List(list.into_iter()),
388            AutoMap::Map(map) => IntoIter::Map(map.into_iter()),
389        }
390    }
391}
392
393impl<'a, K, V, H, const I: usize> IntoIterator for &'a AutoMap<K, V, H, I> {
394    type Item = (&'a K, &'a V);
395    type IntoIter = Iter<'a, K, V>;
396
397    fn into_iter(self) -> Self::IntoIter {
398        self.iter()
399    }
400}
401
402pub enum Iter<'a, K, V> {
403    List(std::slice::Iter<'a, (K, V)>),
404    Map(hashbrown::hash_map::Iter<'a, K, V>),
405}
406
407impl<'a, K, V> Iterator for Iter<'a, K, V> {
408    type Item = (&'a K, &'a V);
409
410    // This clippy lint doesn't account for lifetimes
411    #[allow(clippy::map_identity)]
412    fn next(&mut self) -> Option<Self::Item> {
413        match self {
414            Iter::List(iter) => iter.next().map(|(k, v)| (k, v)),
415            Iter::Map(iter) => iter.next(),
416        }
417    }
418
419    fn size_hint(&self) -> (usize, Option<usize>) {
420        match self {
421            Iter::List(iter) => iter.size_hint(),
422            Iter::Map(iter) => iter.size_hint(),
423        }
424    }
425}
426
427impl<K, V> Clone for Iter<'_, K, V> {
428    fn clone(&self) -> Self {
429        match self {
430            Iter::List(iter) => Iter::List(iter.clone()),
431            Iter::Map(iter) => Iter::Map(iter.clone()),
432        }
433    }
434}
435
436pub enum IterMut<'a, K, V> {
437    List(std::slice::IterMut<'a, (K, V)>),
438    Map(hashbrown::hash_map::IterMut<'a, K, V>),
439}
440
441impl<'a, K, V> Iterator for IterMut<'a, K, V> {
442    type Item = (&'a K, &'a mut V);
443
444    fn next(&mut self) -> Option<Self::Item> {
445        match self {
446            IterMut::List(iter) => iter.next().map(|(k, v)| (&*k, v)),
447            IterMut::Map(iter) => iter.next(),
448        }
449    }
450
451    fn size_hint(&self) -> (usize, Option<usize>) {
452        match self {
453            IterMut::List(iter) => iter.size_hint(),
454            IterMut::Map(iter) => iter.size_hint(),
455        }
456    }
457}
458
459pub enum IntoIter<K, V, const I: usize> {
460    List(smallvec::IntoIter<[(K, V); I]>),
461    Map(hashbrown::hash_map::IntoIter<K, V>),
462}
463
464impl<K, V, const I: usize> Iterator for IntoIter<K, V, I> {
465    type Item = (K, V);
466
467    fn next(&mut self) -> Option<Self::Item> {
468        match self {
469            IntoIter::List(iter) => iter.next(),
470            IntoIter::Map(iter) => iter.next(),
471        }
472    }
473
474    fn size_hint(&self) -> (usize, Option<usize>) {
475        match self {
476            IntoIter::List(iter) => iter.size_hint(),
477            IntoIter::Map(iter) => iter.size_hint(),
478        }
479    }
480}
481
482pub enum Values<'a, K, V> {
483    List(std::slice::Iter<'a, (K, V)>),
484    Map(hashbrown::hash_map::Values<'a, K, V>),
485}
486
487impl<'a, K, V> Iterator for Values<'a, K, V> {
488    type Item = &'a V;
489
490    fn next(&mut self) -> Option<Self::Item> {
491        match self {
492            Values::List(iter) => iter.next().map(|(_, v)| v),
493            Values::Map(iter) => iter.next(),
494        }
495    }
496
497    fn size_hint(&self) -> (usize, Option<usize>) {
498        match self {
499            Values::List(iter) => iter.size_hint(),
500            Values::Map(iter) => iter.size_hint(),
501        }
502    }
503}
504
505pub enum ValuesMut<'a, K, V> {
506    List(std::slice::IterMut<'a, (K, V)>),
507    Map(hashbrown::hash_map::ValuesMut<'a, K, V>),
508}
509
510impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
511    type Item = &'a mut V;
512
513    fn next(&mut self) -> Option<Self::Item> {
514        match self {
515            ValuesMut::List(iter) => iter.next().map(|(_, v)| v),
516            ValuesMut::Map(iter) => iter.next(),
517        }
518    }
519
520    fn size_hint(&self) -> (usize, Option<usize>) {
521        match self {
522            ValuesMut::List(iter) => iter.size_hint(),
523            ValuesMut::Map(iter) => iter.size_hint(),
524        }
525    }
526}
527
528pub enum IntoValues<K, V, const I: usize> {
529    List(smallvec::IntoIter<[(K, V); I]>),
530    Map(hashbrown::hash_map::IntoValues<K, V>),
531}
532
533impl<K, V, const I: usize> Iterator for IntoValues<K, V, I> {
534    type Item = V;
535
536    fn next(&mut self) -> Option<Self::Item> {
537        match self {
538            IntoValues::List(iter) => iter.next().map(|(_, v)| v),
539            IntoValues::Map(iter) => iter.next(),
540        }
541    }
542
543    fn size_hint(&self) -> (usize, Option<usize>) {
544        match self {
545            IntoValues::List(iter) => iter.size_hint(),
546            IntoValues::Map(iter) => iter.size_hint(),
547        }
548    }
549}
550
551pub enum Entry<'a, K, V, H, const I: usize> {
552    Occupied(OccupiedEntry<'a, K, V, H, I>),
553    Vacant(VacantEntry<'a, K, V, H, I>),
554}
555
556impl<'a, K: Eq + Hash, V, H: BuildHasher + Default + 'a, const I: usize> Entry<'a, K, V, H, I> {
557    /// see [HashMap::Entry::or_insert](https://doc.rust-lang.org/std/collections/hash_map/enum.Entry.html#method.or_insert)
558    pub fn or_insert_with(self, default: impl FnOnce() -> V) -> &'a mut V {
559        match self {
560            Entry::Occupied(entry) => entry.into_mut(),
561            Entry::Vacant(entry) => entry.insert(default()),
562        }
563    }
564
565    /// see [HashMap::Entry::or_insert](https://doc.rust-lang.org/std/collections/hash_map/enum.Entry.html#method.or_insert)
566    pub fn or_insert(self, default: V) -> &'a mut V {
567        match self {
568            Entry::Occupied(entry) => entry.into_mut(),
569            Entry::Vacant(entry) => entry.insert(default),
570        }
571    }
572}
573
574impl<'a, K: Eq + Hash, V: Default, H: BuildHasher + Default + 'a, const I: usize>
575    Entry<'a, K, V, H, I>
576{
577    /// see [HashMap::Entry::or_default](https://doc.rust-lang.org/std/collections/hash_map/enum.Entry.html#method.or_default)
578    pub fn or_default(self) -> &'a mut V {
579        match self {
580            Entry::Occupied(entry) => entry.into_mut(),
581            Entry::Vacant(entry) => entry.insert(Default::default()),
582        }
583    }
584}
585
586pub enum OccupiedEntry<'a, K, V, H, const I: usize> {
587    List {
588        list: &'a mut SmallVec<[(K, V); I]>,
589        index: usize,
590    },
591    Map {
592        this: *mut AutoMap<K, V, H, I>,
593        entry: hashbrown::hash_map::OccupiedEntry<'a, K, V, H>,
594    },
595}
596
597impl<'a, K: Eq + Hash, V, H: BuildHasher, const I: usize> OccupiedEntry<'a, K, V, H, I> {
598    /// see [HashMap::OccupiedEntry::get_mut](https://doc.rust-lang.org/std/collections/hash_map/enum.OccupiedEntry.html#method.get_mut)
599    pub fn get_mut(&mut self) -> &mut V {
600        match self {
601            OccupiedEntry::List { list, index } => &mut list[*index].1,
602            OccupiedEntry::Map { entry, .. } => entry.get_mut(),
603        }
604    }
605
606    /// see [HashMap::OccupiedEntry::into_mut](https://doc.rust-lang.org/std/collections/hash_map/enum.OccupiedEntry.html#method.into_mut)
607    pub fn into_mut(self) -> &'a mut V {
608        match self {
609            OccupiedEntry::List { list, index } => &mut list[index].1,
610            OccupiedEntry::Map { entry, .. } => entry.into_mut(),
611        }
612    }
613}
614
615impl<K: Eq + Hash, V, H: BuildHasher + Default, const I: usize> OccupiedEntry<'_, K, V, H, I> {
616    /// see [HashMap::OccupiedEntry::remove](https://doc.rust-lang.org/std/collections/hash_map/enum.OccupiedEntry.html#method.remove)
617    pub fn remove(self) -> V {
618        match self {
619            OccupiedEntry::List { list, index } => list.swap_remove(index).1,
620            OccupiedEntry::Map { entry, this: _ } => entry.remove(),
621        }
622    }
623
624    pub fn replace_entry_with(self, func: impl FnOnce(&K, V) -> Option<V>) {
625        match self {
626            OccupiedEntry::List { list, index } => {
627                let (key, value) = list.swap_remove(index);
628                if let Some(value) = func(&key, value) {
629                    list.push((key, value));
630                }
631            }
632            OccupiedEntry::Map { entry, .. } => {
633                entry.replace_entry_with(func);
634            }
635        }
636    }
637}
638
639pub enum VacantEntry<'a, K, V, H, const I: usize> {
640    List {
641        this: *mut AutoMap<K, V, H, I>,
642        list: &'a mut SmallVec<[(K, V); I]>,
643        key: K,
644    },
645    Map(hashbrown::hash_map::VacantEntry<'a, K, V, H>),
646}
647
648impl<'a, K: Eq + Hash, V, H: BuildHasher + Default + 'a, const I: usize>
649    VacantEntry<'a, K, V, H, I>
650{
651    /// see [HashMap::VacantEntry::insert](https://doc.rust-lang.org/std/collections/hash_map/enum.VacantEntry.html#method.insert)
652    pub fn insert(self, value: V) -> &'a mut V {
653        match self {
654            VacantEntry::List { this, list, key } => {
655                if list.len() >= MAX_LIST_SIZE {
656                    let this = unsafe { &mut *this };
657                    this.convert_to_map().entry(key).or_insert(value)
658                } else {
659                    list.push((key, value));
660                    &mut list.last_mut().unwrap().1
661                }
662            }
663            VacantEntry::Map(entry) => entry.insert(value),
664        }
665    }
666}
667
668pub enum RawEntry<'a, K, V, H, const I: usize> {
669    Occupied(OccupiedRawEntry<'a, K, V, H, I>),
670    Vacant(VacantRawEntry<'a, K, V, H, I>),
671}
672
673pub enum OccupiedRawEntry<'a, K, V, H, const I: usize> {
674    List {
675        list: &'a mut SmallVec<[(K, V); I]>,
676        index: usize,
677    },
678    Map {
679        this: *mut AutoMap<K, V, H, I>,
680        entry: hashbrown::hash_map::RawOccupiedEntryMut<'a, K, V, H>,
681    },
682}
683
684impl<'a, K: Eq + Hash, V, H: BuildHasher, const I: usize> OccupiedRawEntry<'a, K, V, H, I> {
685    /// see [HashMap::RawOccupiedEntryMut::get_mut](https://doc.rust-lang.org/std/collections/hash_map/struct.RawOccupiedEntryMut.html#method.get_mut)
686    pub fn get_mut(&mut self) -> &mut V {
687        match self {
688            OccupiedRawEntry::List { list, index } => &mut list[*index].1,
689            OccupiedRawEntry::Map { entry, .. } => entry.get_mut(),
690        }
691    }
692
693    /// see [HashMap::RawOccupiedEntryMut::into_mut](https://doc.rust-lang.org/std/collections/hash_map/struct.RawOccupiedEntryMut.html#method.into_mut)
694    pub fn into_mut(self) -> &'a mut V {
695        match self {
696            OccupiedRawEntry::List { list, index } => &mut list[index].1,
697            OccupiedRawEntry::Map { entry, .. } => entry.into_mut(),
698        }
699    }
700}
701
702impl<K: Eq + Hash, V, H: BuildHasher + Default, const I: usize> OccupiedRawEntry<'_, K, V, H, I> {
703    /// see [HashMap::OccupiedEntry::remove](https://doc.rust-lang.org/std/collections/hash_map/enum.OccupiedEntry.html#method.remove)
704    pub fn remove(self) -> V {
705        match self {
706            OccupiedRawEntry::List { list, index } => list.swap_remove(index).1,
707            OccupiedRawEntry::Map { entry, this: _ } => entry.remove(),
708        }
709    }
710}
711
712pub enum VacantRawEntry<'a, K, V, H, const I: usize> {
713    List {
714        this: *mut AutoMap<K, V, H, I>,
715        list: &'a mut SmallVec<[(K, V); I]>,
716    },
717    Map(hashbrown::hash_map::RawVacantEntryMut<'a, K, V, H>),
718}
719
720impl<'a, K: Eq + Hash, V, H: BuildHasher + Default + 'a, const I: usize>
721    VacantRawEntry<'a, K, V, H, I>
722{
723    /// see [HashMap::RawVacantEntryMut::insert](https://doc.rust-lang.org/std/collections/hash_map/struct.RawVacantEntryMut.html#method.insert)
724    pub fn insert(self, key: K, value: V) -> &'a mut V {
725        match self {
726            VacantRawEntry::List { this, list } => {
727                if list.len() >= MAX_LIST_SIZE {
728                    let this = unsafe { &mut *this };
729                    this.convert_to_map().entry(key).or_insert(value)
730                } else {
731                    list.push((key, value));
732                    &mut list.last_mut().unwrap().1
733                }
734            }
735            VacantRawEntry::Map(entry) => entry.insert(key, value).1,
736        }
737    }
738}
739
740impl<K, V, H, const I: usize> Serialize for AutoMap<K, V, H, I>
741where
742    K: Eq + Hash + Serialize,
743    V: Serialize,
744    H: BuildHasher,
745{
746    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
747    where
748        S: Serializer,
749    {
750        match self {
751            AutoMap::List(list) => {
752                let mut map = serializer.serialize_map(Some(list.len()))?;
753                for (k, v) in list {
754                    map.serialize_entry(k, v)?;
755                }
756                map.end()
757            }
758            AutoMap::Map(map) => (**map).serialize(serializer),
759        }
760    }
761}
762
763impl<'de, K, V, H, const I: usize> Deserialize<'de> for AutoMap<K, V, H, I>
764where
765    K: Eq + Hash + Deserialize<'de>,
766    V: Deserialize<'de>,
767    H: BuildHasher + Default,
768{
769    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
770    where
771        D: Deserializer<'de>,
772    {
773        struct AutoMapVisitor<K, V, H, const I: usize> {
774            phantom: PhantomData<AutoMap<K, V, H, I>>,
775        }
776
777        impl<'de, K, V, H, const I: usize> Visitor<'de> for AutoMapVisitor<K, V, H, I>
778        where
779            K: Eq + Hash + Deserialize<'de>,
780            V: Deserialize<'de>,
781            H: BuildHasher + Default,
782        {
783            type Value = AutoMap<K, V, H, I>;
784
785            fn expecting(&self, formatter: &mut Formatter) -> std::fmt::Result {
786                formatter.write_str("a map")
787            }
788
789            fn visit_map<M>(self, mut m: M) -> Result<Self::Value, M::Error>
790            where
791                M: MapAccess<'de>,
792            {
793                if let Some(size) = m.size_hint() {
794                    if size < MAX_LIST_SIZE {
795                        let mut list = SmallVec::with_capacity(size);
796                        while let Some((k, v)) = m.next_entry()? {
797                            list.push((k, v));
798                        }
799                        return Ok(AutoMap::List(list));
800                    } else {
801                        let mut map =
802                            Box::new(HashMap::with_capacity_and_hasher(size, H::default()));
803                        while let Some((k, v)) = m.next_entry()? {
804                            map.insert(k, v);
805                        }
806                        return Ok(AutoMap::Map(map));
807                    }
808                }
809                let mut map = AutoMap::with_hasher();
810                while let Some((k, v)) = m.next_entry()? {
811                    map.insert(k, v);
812                }
813                Ok(map)
814            }
815        }
816
817        deserializer.deserialize_map(AutoMapVisitor {
818            phantom: PhantomData::<AutoMap<K, V, H, I>>,
819        })
820    }
821}
822
823impl<K, V, H, const I: usize> Encode for AutoMap<K, V, H, I>
824where
825    K: Encode,
826    V: Encode,
827{
828    fn encode<E: Encoder>(&self, encoder: &mut E) -> Result<(), EncodeError> {
829        // Encode the length first
830        self.len().encode(encoder)?;
831        // Then encode each key-value tuple
832        for entry in self.iter() {
833            entry.encode(encoder)?;
834        }
835        Ok(())
836    }
837}
838
839impl<Context, K, V, H, const I: usize> Decode<Context> for AutoMap<K, V, H, I>
840where
841    K: Decode<Context> + Eq + Hash,
842    V: Decode<Context>,
843    H: BuildHasher + Default,
844{
845    fn decode<D: Decoder<Context = Context>>(decoder: &mut D) -> Result<Self, DecodeError> {
846        let len = usize::decode(decoder)?;
847        if len <= MAX_LIST_SIZE {
848            let mut list = SmallVec::with_capacity(len);
849            for _ in 0..len {
850                let entry = <(K, V)>::decode(decoder)?;
851                list.push(entry);
852            }
853            Ok(AutoMap::List(list))
854        } else {
855            let mut map = HashMap::with_capacity_and_hasher(len, H::default());
856            for _ in 0..len {
857                let (key, value) = <(K, V)>::decode(decoder)?;
858                map.insert(key, value);
859            }
860            Ok(AutoMap::Map(Box::new(map)))
861        }
862    }
863}
864
865impl_borrow_decode!(
866    AutoMap<K, V, H, I>,
867    K: Decode<__Context> + Eq + Hash,
868    V: Decode<__Context>,
869    H: BuildHasher + Default,
870    const I: usize,
871);
872
873impl<K: Eq + Hash, V: Eq, H: BuildHasher, const I: usize> PartialEq for AutoMap<K, V, H, I> {
874    fn eq(&self, other: &Self) -> bool {
875        match (self, other) {
876            (AutoMap::Map(a), AutoMap::Map(b)) => a == b,
877            (AutoMap::List(a), b) => {
878                if a.len() != b.len() {
879                    return false;
880                }
881                a.iter().all(|(k, v)| b.get(k) == Some(v))
882            }
883            (a, AutoMap::List(b)) => {
884                if a.len() != b.len() {
885                    return false;
886                }
887                b.iter().all(|(k, v)| a.get(k) == Some(v))
888            }
889        }
890    }
891}
892
893impl<K: Eq + Hash, V: Eq, H: BuildHasher, const I: usize> Eq for AutoMap<K, V, H, I>
894where
895    K: Eq,
896    V: Eq,
897{
898}
899
900impl<K: Eq + Hash, V: Eq + Hash, MH: BuildHasher + Default, const I: usize> Hash
901    for AutoMap<K, V, MH, I>
902{
903    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
904        // Hash the length first to distinguish maps of different sizes
905        self.len().hash(state);
906
907        // Use a commutative approach to ensure equal maps have equal hashes
908        // regardless of iteration order
909        let mut combined_hash = 0u64;
910
911        let hash_builder = MH::default();
912        for (k, v) in self.iter() {
913            use std::hash::Hasher;
914
915            // Hash each key-value pair independently
916            let mut entry_hasher = hash_builder.build_hasher();
917            k.hash(&mut entry_hasher);
918            v.hash(&mut entry_hasher);
919            let entry_hash = entry_hasher.finish();
920
921            // Combine using addition to make it order-independent (wrapping_add is commutative)
922            combined_hash = combined_hash.wrapping_add(entry_hash);
923        }
924
925        // Hash the combined result
926        combined_hash.hash(state);
927    }
928}
929
930impl<K, V, H, const I: usize> FromIterator<(K, V)> for AutoMap<K, V, H, I>
931where
932    K: Eq + Hash,
933    H: BuildHasher + Default,
934{
935    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
936        let iter = iter.into_iter();
937        let (lower, _) = iter.size_hint();
938        if lower > MAX_LIST_SIZE {
939            let map = iter.collect::<HashMap<K, V, H>>();
940            // The hint is not enforced
941            if map.len() < MIN_HASH_SIZE {
942                return AutoMap::List(map.into_iter().collect());
943            }
944            return AutoMap::Map(Box::new(map));
945        }
946        let mut map = AutoMap::with_hasher();
947        for (k, v) in iter {
948            map.insert(k, v);
949        }
950        map
951    }
952}
953
954pub enum ExtractIfIter<'l, K, V, const I: usize, F>
955where
956    F: for<'a, 'b> FnMut(&'a K, &'b mut V) -> bool,
957{
958    List {
959        list: &'l mut SmallVec<[(K, V); I]>,
960        index: usize,
961        f: F,
962    },
963    Map(hashbrown::hash_map::ExtractIf<'l, K, V, F>),
964}
965
966impl<K, V, const I: usize, F> Iterator for ExtractIfIter<'_, K, V, I, F>
967where
968    F: for<'a, 'b> FnMut(&'a K, &'b mut V) -> bool,
969{
970    type Item = (K, V);
971
972    fn next(&mut self) -> Option<Self::Item> {
973        match self {
974            ExtractIfIter::List { list, index, f } => {
975                while *index < list.len() {
976                    let (key, value) = &mut list[*index];
977                    if f(key, value) {
978                        let item = list.swap_remove(*index);
979                        return Some(item);
980                    } else {
981                        *index += 1;
982                    }
983                }
984                None
985            }
986            ExtractIfIter::Map(extract_if) => extract_if.next(),
987        }
988    }
989}
990
991impl<K, V, H, const I: usize> ShrinkToFit for AutoMap<K, V, H, I>
992where
993    K: Eq + Hash,
994    V: Eq,
995    H: BuildHasher + Default,
996{
997    fn shrink_to_fit(&mut self) {
998        if self.len() < MIN_HASH_SIZE {
999            self.convert_to_list();
1000        }
1001
1002        match self {
1003            AutoMap::List(list) => list.shrink_to_fit(),
1004            AutoMap::Map(map) => {
1005                hashbrown::HashMap::shrink_to_fit(map);
1006            }
1007        }
1008    }
1009}
1010#[cfg(test)]
1011mod tests {
1012    use super::*;
1013
1014    #[test]
1015    fn test_auto_map() {
1016        let mut map = AutoMap::new();
1017        for i in 0..MAX_LIST_SIZE * 2 {
1018            map.insert(i, i);
1019        }
1020        for i in 0..MAX_LIST_SIZE * 2 {
1021            assert_eq!(map.get(&i), Some(&i));
1022        }
1023        assert_eq!(map.get(&(MAX_LIST_SIZE * 2)), None);
1024        for i in 0..MAX_LIST_SIZE * 2 {
1025            assert_eq!(map.remove(&(MAX_LIST_SIZE * 2)), None);
1026            assert_eq!(map.remove(&i), Some(i));
1027        }
1028        assert_eq!(map.remove(&(MAX_LIST_SIZE * 2)), None);
1029    }
1030
1031    #[test]
1032    fn test_extract_if_map() {
1033        let mut map = AutoMap::new();
1034        for i in 0..MAX_LIST_SIZE * 2 {
1035            map.insert(i, i);
1036        }
1037        let iter = map.extract_if(|_, v| *v % 2 == 0);
1038        assert_eq!(iter.count(), MAX_LIST_SIZE);
1039        assert_eq!(map.len(), MAX_LIST_SIZE);
1040    }
1041
1042    #[test]
1043    fn test_extract_if_list() {
1044        let mut map = AutoMap::new();
1045        for i in 0..MIN_HASH_SIZE {
1046            map.insert(i, i);
1047        }
1048        let iter = map.extract_if(|_, v| *v % 2 == 0);
1049        assert_eq!(iter.count(), MIN_HASH_SIZE / 2);
1050        assert_eq!(map.len(), MIN_HASH_SIZE / 2);
1051    }
1052
1053    #[test]
1054    fn test_extract_if_list2() {
1055        let mut map = AutoMap::new();
1056        for i in 0..MIN_HASH_SIZE {
1057            map.insert(i, i);
1058        }
1059        let iter = map.extract_if(|_, v| *v < 5);
1060        assert_eq!(iter.count(), 5);
1061        assert_eq!(map.len(), MIN_HASH_SIZE - 5);
1062    }
1063}
auto_hash_map/map.rs

auto_hash_map/
map.rs
