1 use super::either_iter
::EitherIter
;
2 use crate::fx
::FxHashMap
;
3 use arrayvec
::ArrayVec
;
6 use std
::iter
::FromIterator
;
9 // For pointer-sized arguments arrays
10 // are faster than set/map for up to 64
13 // On the other hand such a big array
14 // hurts cache performance, makes passing
15 // sso structures around very expensive.
17 // Biggest performance benefit is gained
18 // for reasonably small arrays that stay
19 // small in vast majority of cases.
21 // '8' is choosen as a sane default, to be
24 // Note: As of now ArrayVec design prevents
25 // us from making it user-customizable.
26 const SSO_ARRAY_SIZE
: usize = 8;
28 /// Small-storage-optimized implementation of a map.
30 /// Stores elements in a small array up to a certain length
31 /// and switches to `HashMap` when that length is exceeded.
33 // FIXME: Implements subset of HashMap API.
35 // Missing HashMap API:
37 // try_reserve (unstable)
38 // shrink_to (unstable)
39 // drain_filter (unstable)
40 // into_keys/into_values (unstable)
41 // all raw_entry-related
42 // PartialEq/Eq (requires sorting the array)
43 // Entry::or_insert_with_key
44 // Vacant/Occupied entries and related
46 // FIXME: In HashMap most methods accepting key reference
47 // accept reference to generic `Q` where `K: Borrow<Q>`.
49 // However, using this approach in `HashMap::get` apparently
50 // breaks inlining and noticeably reduces performance.
52 // Performance *should* be the same given that borrow is
53 // a NOP in most cases, but in practice that's not the case.
55 // Further investigation is required.
59 // SsoHashMap::get_mut
60 // SsoHashMap::get_entry
61 // SsoHashMap::get_key_value
62 // SsoHashMap::contains_key
64 // SsoHashMap::remove_entry
69 // SsoHashSet::contains
72 pub enum SsoHashMap
<K
, V
> {
73 Array(ArrayVec
<[(K
, V
); SSO_ARRAY_SIZE
]>),
77 impl<K
, V
> SsoHashMap
<K
, V
> {
78 /// Creates an empty `SsoHashMap`.
80 pub fn new() -> Self {
81 SsoHashMap
::Array(ArrayVec
::new())
84 /// Creates an empty `SsoHashMap` with the specified capacity.
85 pub fn with_capacity(cap
: usize) -> Self {
86 if cap
<= SSO_ARRAY_SIZE
{
89 SsoHashMap
::Map(FxHashMap
::with_capacity_and_hasher(cap
, Default
::default()))
93 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
95 pub fn clear(&mut self) {
97 SsoHashMap
::Array(array
) => array
.clear(),
98 SsoHashMap
::Map(map
) => map
.clear(),
102 /// Returns the number of elements the map can hold without reallocating.
103 pub fn capacity(&self) -> usize {
105 SsoHashMap
::Array(_
) => SSO_ARRAY_SIZE
,
106 SsoHashMap
::Map(map
) => map
.capacity(),
110 /// Returns the number of elements in the map.
111 pub fn len(&self) -> usize {
113 SsoHashMap
::Array(array
) => array
.len(),
114 SsoHashMap
::Map(map
) => map
.len(),
118 /// Returns `true` if the map contains no elements.
119 pub fn is_empty(&self) -> bool
{
121 SsoHashMap
::Array(array
) => array
.is_empty(),
122 SsoHashMap
::Map(map
) => map
.is_empty(),
126 /// An iterator visiting all key-value pairs in arbitrary order.
127 /// The iterator element type is `(&'a K, &'a V)`.
129 pub fn iter(&self) -> <&Self as IntoIterator
>::IntoIter
{
133 /// An iterator visiting all key-value pairs in arbitrary order,
134 /// with mutable references to the values.
135 /// The iterator element type is `(&'a K, &'a mut V)`.
137 pub fn iter_mut(&mut self) -> impl Iterator
<Item
= (&'_ K
, &'_
mut V
)> {
141 /// An iterator visiting all keys in arbitrary order.
142 /// The iterator element type is `&'a K`.
143 pub fn keys(&self) -> impl Iterator
<Item
= &'_ K
> {
145 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.iter().map(|(k
, _v
)| k
)),
146 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.keys()),
150 /// An iterator visiting all values in arbitrary order.
151 /// The iterator element type is `&'a V`.
152 pub fn values(&self) -> impl Iterator
<Item
= &'_ V
> {
154 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.iter().map(|(_k
, v
)| v
)),
155 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.values()),
159 /// An iterator visiting all values mutably in arbitrary order.
160 /// The iterator element type is `&'a mut V`.
161 pub fn values_mut(&mut self) -> impl Iterator
<Item
= &'_
mut V
> {
163 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.iter_mut().map(|(_k
, v
)| v
)),
164 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.values_mut()),
168 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
169 /// allocated memory for reuse.
170 pub fn drain(&mut self) -> impl Iterator
<Item
= (K
, V
)> + '_
{
172 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.drain(..)),
173 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.drain()),
178 impl<K
: Eq
+ Hash
, V
> SsoHashMap
<K
, V
> {
179 /// Changes underlying storage from array to hashmap
180 /// if array is full.
181 fn migrate_if_full(&mut self) {
182 if let SsoHashMap
::Array(array
) = self {
184 *self = SsoHashMap
::Map(array
.drain(..).collect());
189 /// Reserves capacity for at least `additional` more elements to be inserted
190 /// in the `SsoHashMap`. The collection may reserve more space to avoid
191 /// frequent reallocations.
192 pub fn reserve(&mut self, additional
: usize) {
194 SsoHashMap
::Array(array
) => {
195 if SSO_ARRAY_SIZE
< (array
.len() + additional
) {
196 let mut map
: FxHashMap
<K
, V
> = array
.drain(..).collect();
197 map
.reserve(additional
);
198 *self = SsoHashMap
::Map(map
);
201 SsoHashMap
::Map(map
) => map
.reserve(additional
),
205 /// Shrinks the capacity of the map as much as possible. It will drop
206 /// down as much as possible while maintaining the internal rules
207 /// and possibly leaving some space in accordance with the resize policy.
208 pub fn shrink_to_fit(&mut self) {
209 if let SsoHashMap
::Map(map
) = self {
210 if map
.len() <= SSO_ARRAY_SIZE
{
211 *self = SsoHashMap
::Array(map
.drain().collect());
218 /// Retains only the elements specified by the predicate.
219 pub fn retain
<F
>(&mut self, mut f
: F
)
221 F
: FnMut(&K
, &mut V
) -> bool
,
224 SsoHashMap
::Array(array
) => array
.retain(|(k
, v
)| f(k
, v
)),
225 SsoHashMap
::Map(map
) => map
.retain(f
),
229 /// Inserts a key-value pair into the map.
231 /// If the map did not have this key present, [`None`] is returned.
233 /// If the map did have this key present, the value is updated, and the old
234 /// value is returned. The key is not updated, though; this matters for
235 /// types that can be `==` without being identical. See the [module-level
236 /// documentation] for more.
237 pub fn insert(&mut self, key
: K
, value
: V
) -> Option
<V
> {
239 SsoHashMap
::Array(array
) => {
240 for (k
, v
) in array
.iter_mut() {
242 let old_value
= std
::mem
::replace(v
, value
);
243 return Some(old_value
);
246 if let Err(error
) = array
.try_push((key
, value
)) {
247 let mut map
: FxHashMap
<K
, V
> = array
.drain(..).collect();
248 let (key
, value
) = error
.element();
249 map
.insert(key
, value
);
250 *self = SsoHashMap
::Map(map
);
254 SsoHashMap
::Map(map
) => map
.insert(key
, value
),
258 /// Removes a key from the map, returning the value at the key if the key
259 /// was previously in the map.
260 pub fn remove(&mut self, key
: &K
) -> Option
<V
> {
262 SsoHashMap
::Array(array
) => {
263 if let Some(index
) = array
.iter().position(|(k
, _v
)| k
== key
) {
264 Some(array
.swap_remove(index
).1)
269 SsoHashMap
::Map(map
) => map
.remove(key
),
273 /// Removes a key from the map, returning the stored key and value if the
274 /// key was previously in the map.
275 pub fn remove_entry(&mut self, key
: &K
) -> Option
<(K
, V
)> {
277 SsoHashMap
::Array(array
) => {
278 if let Some(index
) = array
.iter().position(|(k
, _v
)| k
== key
) {
279 Some(array
.swap_remove(index
))
284 SsoHashMap
::Map(map
) => map
.remove_entry(key
),
288 /// Returns a reference to the value corresponding to the key.
289 pub fn get(&self, key
: &K
) -> Option
<&V
> {
291 SsoHashMap
::Array(array
) => {
292 for (k
, v
) in array
{
299 SsoHashMap
::Map(map
) => map
.get(key
),
303 /// Returns a mutable reference to the value corresponding to the key.
304 pub fn get_mut(&mut self, key
: &K
) -> Option
<&mut V
> {
306 SsoHashMap
::Array(array
) => {
307 for (k
, v
) in array
{
314 SsoHashMap
::Map(map
) => map
.get_mut(key
),
318 /// Returns the key-value pair corresponding to the supplied key.
319 pub fn get_key_value(&self, key
: &K
) -> Option
<(&K
, &V
)> {
321 SsoHashMap
::Array(array
) => {
322 for (k
, v
) in array
{
329 SsoHashMap
::Map(map
) => map
.get_key_value(key
),
333 /// Returns `true` if the map contains a value for the specified key.
334 pub fn contains_key(&self, key
: &K
) -> bool
{
336 SsoHashMap
::Array(array
) => array
.iter().any(|(k
, _v
)| k
== key
),
337 SsoHashMap
::Map(map
) => map
.contains_key(key
),
341 /// Gets the given key's corresponding entry in the map for in-place manipulation.
343 pub fn entry(&mut self, key
: K
) -> Entry
<'_
, K
, V
> {
344 Entry { ssomap: self, key }
348 impl<K
, V
> Default
for SsoHashMap
<K
, V
> {
350 fn default() -> Self {
355 impl<K
: Eq
+ Hash
, V
> FromIterator
<(K
, V
)> for SsoHashMap
<K
, V
> {
356 fn from_iter
<I
: IntoIterator
<Item
= (K
, V
)>>(iter
: I
) -> SsoHashMap
<K
, V
> {
357 let mut map
: SsoHashMap
<K
, V
> = Default
::default();
363 impl<K
: Eq
+ Hash
, V
> Extend
<(K
, V
)> for SsoHashMap
<K
, V
> {
364 fn extend
<I
>(&mut self, iter
: I
)
366 I
: IntoIterator
<Item
= (K
, V
)>,
368 for (key
, value
) in iter
.into_iter() {
369 self.insert(key
, value
);
374 fn extend_one(&mut self, (k
, v
): (K
, V
)) {
378 fn extend_reserve(&mut self, additional
: usize) {
380 SsoHashMap
::Array(array
) => {
381 if SSO_ARRAY_SIZE
< (array
.len() + additional
) {
382 let mut map
: FxHashMap
<K
, V
> = array
.drain(..).collect();
383 map
.extend_reserve(additional
);
384 *self = SsoHashMap
::Map(map
);
387 SsoHashMap
::Map(map
) => map
.extend_reserve(additional
),
392 impl<'a
, K
, V
> Extend
<(&'a K
, &'a V
)> for SsoHashMap
<K
, V
>
397 fn extend
<T
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: T
) {
398 self.extend(iter
.into_iter().map(|(k
, v
)| (*k
, *v
)))
402 fn extend_one(&mut self, (&k
, &v
): (&'a K
, &'a V
)) {
407 fn extend_reserve(&mut self, additional
: usize) {
408 Extend
::<(K
, V
)>::extend_reserve(self, additional
)
412 impl<K
, V
> IntoIterator
for SsoHashMap
<K
, V
> {
413 type IntoIter
= EitherIter
<
414 <ArrayVec
<[(K
, V
); 8]> as IntoIterator
>::IntoIter
,
415 <FxHashMap
<K
, V
> as IntoIterator
>::IntoIter
,
417 type Item
= <Self::IntoIter
as Iterator
>::Item
;
419 fn into_iter(self) -> Self::IntoIter
{
421 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.into_iter()),
422 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.into_iter()),
427 /// adapts Item of array reference iterator to Item of hashmap reference iterator.
429 fn adapt_array_ref_it
<K
, V
>(pair
: &'
a (K
, V
)) -> (&'a K
, &'a V
) {
434 /// adapts Item of array mut reference iterator to Item of hashmap mut reference iterator.
436 fn adapt_array_mut_it
<K
, V
>(pair
: &'a
mut (K
, V
)) -> (&'a K
, &'a
mut V
) {
441 impl<'a
, K
, V
> IntoIterator
for &'a SsoHashMap
<K
, V
> {
442 type IntoIter
= EitherIter
<
444 <&'a ArrayVec
<[(K
, V
); 8]> as IntoIterator
>::IntoIter
,
445 fn(&'
a (K
, V
)) -> (&'a K
, &'a V
),
447 <&'a FxHashMap
<K
, V
> as IntoIterator
>::IntoIter
,
449 type Item
= <Self::IntoIter
as Iterator
>::Item
;
451 fn into_iter(self) -> Self::IntoIter
{
453 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.into_iter().map(adapt_array_ref_it
)),
454 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.iter()),
459 impl<'a
, K
, V
> IntoIterator
for &'a
mut SsoHashMap
<K
, V
> {
460 type IntoIter
= EitherIter
<
462 <&'a
mut ArrayVec
<[(K
, V
); 8]> as IntoIterator
>::IntoIter
,
463 fn(&'a
mut (K
, V
)) -> (&'a K
, &'a
mut V
),
465 <&'a
mut FxHashMap
<K
, V
> as IntoIterator
>::IntoIter
,
467 type Item
= <Self::IntoIter
as Iterator
>::Item
;
469 fn into_iter(self) -> Self::IntoIter
{
471 SsoHashMap
::Array(array
) => EitherIter
::Left(array
.into_iter().map(adapt_array_mut_it
)),
472 SsoHashMap
::Map(map
) => EitherIter
::Right(map
.iter_mut()),
477 impl<K
, V
> fmt
::Debug
for SsoHashMap
<K
, V
>
482 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
483 f
.debug_map().entries(self.iter()).finish()
487 impl<'a
, K
, V
> Index
<&'a K
> for SsoHashMap
<K
, V
>
494 fn index(&self, key
: &K
) -> &V
{
495 self.get(key
).expect("no entry found for key")
499 /// A view into a single entry in a map.
500 pub struct Entry
<'a
, K
, V
> {
501 ssomap
: &'a
mut SsoHashMap
<K
, V
>,
505 impl<'a
, K
: Eq
+ Hash
, V
> Entry
<'a
, K
, V
> {
506 /// Provides in-place mutable access to an occupied entry before any
507 /// potential inserts into the map.
508 pub fn and_modify
<F
>(self, f
: F
) -> Self
512 if let Some(value
) = self.ssomap
.get_mut(&self.key
) {
518 /// Ensures a value is in the entry by inserting the default if empty, and returns
519 /// a mutable reference to the value in the entry.
521 pub fn or_insert(self, value
: V
) -> &'a
mut V
{
522 self.or_insert_with(|| value
)
525 /// Ensures a value is in the entry by inserting the result of the default function if empty,
526 /// and returns a mutable reference to the value in the entry.
527 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
528 self.ssomap
.migrate_if_full();
530 SsoHashMap
::Array(array
) => {
531 let key_ref
= &self.key
;
532 let found_index
= array
.iter().position(|(k
, _v
)| k
== key_ref
);
533 let index
= if let Some(index
) = found_index
{
536 let index
= array
.len();
537 array
.try_push((self.key
, default())).unwrap();
542 SsoHashMap
::Map(map
) => map
.entry(self.key
).or_insert_with(default),
546 /// Returns a reference to this entry's key.
548 pub fn key(&self) -> &K
{
553 impl<'a
, K
: Eq
+ Hash
, V
: Default
> Entry
<'a
, K
, V
> {
554 /// Ensures a value is in the entry by inserting the default value if empty,
555 /// and returns a mutable reference to the value in the entry.
557 pub fn or_default(self) -> &'a
mut V
{
558 self.or_insert_with(Default
::default)