#![warn(unused_extern_crates)]
#![cfg_attr(
feature = "cargo-clippy",
deny(
clippy::all,
clippy::unwrap_used,
clippy::unnecessary_unwrap,
clippy::pedantic
),
// We might want to revisit inline_always
allow(clippy::module_name_repetitions, clippy::inline_always)
)]
#![deny(missing_docs)]
mod entry;
mod iter;
mod macros;
mod raw_entry;
#[cfg(feature = "serde")]
mod serde;
mod vecmap;
pub use crate::entry::*;
pub use crate::iter::*;
pub use crate::raw_entry::*;
use crate::vecmap::VecMap;
use core::borrow::Borrow;
use core::hash::{BuildHasher, Hash};
use hashbrown::{self, HashMap as HashBrown};
use std::default::Default;
use std::fmt::{self, Debug};
use std::ops::Index;
#[cfg(feature = "fxhash")]
pub use fxhash::FxBuildHasher as DefaultHashBuilder;
#[cfg(not(feature = "fxhash"))]
pub use hashbrown::hash_map::DefaultHashBuilder;
pub const VEC_LIMIT_UPPER: usize = 32;
#[derive(Clone)]
pub struct HashMap<K, V, S = DefaultHashBuilder>(HashMapInt<K, V, S>);
impl<K, V, S: Default> Default for HashMap<K, V, S> {
#[inline]
fn default() -> Self {
Self(HashMapInt::default())
}
}
impl<K, V, S> Debug for HashMap<K, V, S>
where
K: Debug,
V: Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
#[derive(Clone)]
enum HashMapInt<K, V, S = DefaultHashBuilder> {
Map(HashBrown<K, V, S>),
Vec(VecMap<K, V, S>),
None,
}
impl<K, V, S: Default> Default for HashMapInt<K, V, S> {
#[inline]
fn default() -> Self {
Self::Vec(VecMap::default())
}
}
impl<K, V> HashMap<K, V, DefaultHashBuilder> {
#[inline]
#[must_use]
pub fn new() -> Self {
Self(HashMapInt::Vec(VecMap::new()))
}
#[inline]
#[must_use]
pub fn with_capacity(capacity: usize) -> Self {
Self(if capacity > VEC_LIMIT_UPPER {
HashMapInt::Map(HashBrown::with_capacity_and_hasher(
capacity,
DefaultHashBuilder::default(),
))
} else {
HashMapInt::Vec(VecMap::with_capacity(capacity))
})
}
#[inline]
#[must_use]
pub fn vec_with_capacity(capacity: usize) -> Self {
Self(HashMapInt::Vec(VecMap::with_capacity(capacity)))
}
}
impl<K, V, S> HashMap<K, V, S> {
#[inline]
pub fn with_hasher(hash_builder: S) -> Self {
Self(HashMapInt::Map(HashBrown::with_hasher(hash_builder)))
}
#[inline]
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
Self(HashMapInt::Map(HashBrown::with_capacity_and_hasher(
capacity,
hash_builder,
)))
}
pub fn hasher(&self) -> &S {
match &self.0 {
HashMapInt::Map(m) => m.hasher(),
HashMapInt::Vec(m) => m.hasher(),
HashMapInt::None => unreachable!(),
}
}
#[inline]
#[allow(clippy::missing_panics_doc)]
pub fn capacity(&self) -> usize {
match &self.0 {
HashMapInt::Map(m) => m.capacity(),
HashMapInt::Vec(m) => m.capacity(),
HashMapInt::None => unimplemented!(),
}
}
pub fn keys(&self) -> Keys<'_, K, V> {
Keys { inner: self.iter() }
}
pub fn values(&self) -> Values<'_, K, V> {
Values { inner: self.iter() }
}
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
ValuesMut {
inner: self.iter_mut(),
}
}
pub fn iter(&self) -> Iter<'_, K, V> {
match &self.0 {
HashMapInt::Map(m) => IterInt::Map(m.iter()).into(),
HashMapInt::Vec(m) => IterInt::Vec(m.iter()).into(),
HashMapInt::None => unreachable!(),
}
}
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
match &mut self.0 {
HashMapInt::Map(m) => IterMutInt::Map(m.iter_mut()).into(),
HashMapInt::Vec(m) => IterMutInt::Vec(m.iter_mut()).into(),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn len(&self) -> usize {
match &self.0 {
HashMapInt::Map(m) => m.len(),
HashMapInt::Vec(m) => m.len(),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn is_empty(&self) -> bool {
match &self.0 {
HashMapInt::Map(m) => m.is_empty(),
HashMapInt::Vec(m) => m.is_empty(),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn drain(&mut self) -> Drain<K, V> {
match &mut self.0 {
HashMapInt::Map(m) => Drain(DrainInt::Map(m.drain())),
HashMapInt::Vec(m) => Drain(DrainInt::Vec(m.drain())),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn clear(&mut self) {
match &mut self.0 {
HashMapInt::Map(m) => m.clear(),
HashMapInt::Vec(m) => m.clear(),
HashMapInt::None => unreachable!(),
}
}
}
impl<K, V, S> HashMap<K, V, S>
where
K: Eq + Hash,
S: BuildHasher,
{
#[inline]
pub fn reserve(&mut self, additional: usize) {
match &mut self.0 {
HashMapInt::Map(m) => m.reserve(additional),
HashMapInt::Vec(m) => m.reserve(additional),
HashMapInt::None => unreachable!(),
}
}
pub fn shrink_to_fit(&mut self) {
match &mut self.0 {
HashMapInt::Map(m) => m.shrink_to_fit(),
HashMapInt::Vec(m) => m.shrink_to_fit(),
HashMapInt::None => unreachable!(),
}
}
pub fn entry(&mut self, key: K) -> Entry<K, V, S> {
match &mut self.0 {
HashMapInt::Map(m) => m.entry(key).into(),
HashMapInt::Vec(m) => m.entry(key).into(),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
match &self.0 {
HashMapInt::Map(m) => m.get(k),
HashMapInt::Vec(m) => m.get(k),
HashMapInt::None => unreachable!(),
}
}
pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
where
K: Borrow<Q>,
Q: Hash + Eq,
{
match &self.0 {
HashMapInt::Map(m) => m.contains_key(k),
HashMapInt::Vec(m) => m.contains_key(k),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
match &mut self.0 {
HashMapInt::Map(m) => m.get_mut(k),
HashMapInt::Vec(m) => m.get_mut(k),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn insert(&mut self, k: K, v: V) -> Option<V>
where
S: Default,
{
match &mut self.0 {
HashMapInt::Map(m) => m.insert(k, v),
HashMapInt::Vec(m) => {
if m.len() >= VEC_LIMIT_UPPER {
let r;
self.0 = match std::mem::replace(&mut self.0, HashMapInt::None) {
HashMapInt::Vec(mut m) => {
let mut m1: HashBrown<K, V, S> = m.drain().collect();
r = m1.insert(k, v);
HashMapInt::Map(m1)
}
_ => unreachable!(),
};
r
} else {
m.insert(k, v)
}
}
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
match &mut self.0 {
HashMapInt::Map(m) => m.remove(k),
HashMapInt::Vec(m) => m.remove(k),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
match &mut self.0 {
HashMapInt::Map(m) => m.remove_entry(k),
HashMapInt::Vec(m) => m.remove_entry(k),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn retain<F>(&mut self, f: F)
where
F: FnMut(&K, &mut V) -> bool,
{
match &mut self.0 {
HashMapInt::Map(m) => m.retain(f),
HashMapInt::Vec(m) => m.retain(f),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn insert_nocheck(&mut self, k: K, v: V) {
match &mut self.0 {
HashMapInt::Map(m) => {
m.insert(k, v);
}
HashMapInt::Vec(m) => m.insert_nocheck(k, v),
HashMapInt::None => unreachable!(),
}
}
pub fn is_map(&self) -> bool {
match &self.0 {
HashMapInt::Map(_m) => true,
HashMapInt::Vec(_m) => false,
HashMapInt::None => unreachable!(),
}
}
pub fn is_vec(&self) -> bool {
match &self.0 {
HashMapInt::Map(_m) => false,
HashMapInt::Vec(_m) => true,
HashMapInt::None => unreachable!(),
}
}
}
impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
where
K: Eq + Hash + Borrow<Q>,
Q: Eq + Hash,
S: BuildHasher,
{
type Output = V;
#[inline]
fn index(&self, key: &Q) -> &V {
self.get(key).expect("no entry found for key")
}
}
impl<K, V, S> HashMap<K, V, S>
where
S: BuildHasher,
K: Eq + Hash,
{
#[inline]
pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
match &mut self.0 {
HashMapInt::Vec(m) => RawEntryBuilderMut::from(m.raw_entry_mut()),
HashMapInt::Map(m) => RawEntryBuilderMut::from(m.raw_entry_mut()),
HashMapInt::None => unreachable!(),
}
}
#[inline]
pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
match &self.0 {
HashMapInt::Vec(m) => RawEntryBuilder::from(m.raw_entry()),
HashMapInt::Map(m) => RawEntryBuilder::from(m.raw_entry()),
HashMapInt::None => unreachable!(),
}
}
}
impl<K, V, S, S1> PartialEq<HashMap<K, V, S1>> for HashMap<K, V, S>
where
K: Eq + Hash,
V: PartialEq,
S1: BuildHasher,
{
fn eq(&self, other: &HashMap<K, V, S1>) -> bool {
if self.len() != other.len() {
return false;
}
self.iter()
.all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
}
}
pub struct Keys<'a, K, V> {
inner: Iter<'a, K, V>,
}
impl<'a, K, V> Iterator for Keys<'a, K, V> {
type Item = &'a K;
#[inline]
fn next(&mut self) -> Option<&'a K> {
self.inner.next().map(|(k, _)| k)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
pub struct Values<'a, K, V> {
inner: Iter<'a, K, V>,
}
impl<'a, K, V> Iterator for Values<'a, K, V> {
type Item = &'a V;
#[inline]
fn next(&mut self) -> Option<&'a V> {
self.inner.next().map(|(_, v)| v)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
pub struct ValuesMut<'a, K, V> {
inner: IterMut<'a, K, V>,
}
impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
type Item = &'a mut V;
#[inline]
fn next(&mut self) -> Option<&'a mut V> {
self.inner.next().map(|(_, v)| v)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
pub struct Drain<'a, K, V>(DrainInt<'a, K, V>);
enum DrainInt<'a, K, V> {
Map(hashbrown::hash_map::Drain<'a, K, V>),
Vec(std::vec::Drain<'a, (K, V)>),
}
impl<'a, K, V> Iterator for Drain<'a, K, V> {
type Item = (K, V);
#[inline]
fn next(&mut self) -> Option<Self::Item> {
match &mut self.0 {
DrainInt::Map(m) => m.next(),
DrainInt::Vec(m) => m.next(),
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
match &self.0 {
DrainInt::Map(m) => m.size_hint(),
DrainInt::Vec(m) => m.size_hint(),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn scale_up() {
let mut v = HashMap::new();
assert!(v.is_vec());
for i in 1..33 {
v.insert(i, i);
assert!(v.is_vec());
}
v.insert(33, 33);
assert!(v.is_map());
}
#[test]
fn str_key() {
let mut v: HashMap<String, u32> = HashMap::new();
v.insert("hello".to_owned(), 42);
assert_eq!(v["hello"], 42);
}
#[test]
fn add_remove() {
let mut v = HashMap::new();
v.insert(1, 1);
v.insert(2, 2);
v.insert(3, 3);
assert_eq!(v.get(&1), Some(&1));
assert_eq!(v.get(&2), Some(&2));
assert_eq!(v.get(&3), Some(&3));
v.remove(&2);
assert_eq!(v.get(&1), Some(&1));
assert_eq!(v.get(&2), None);
assert_eq!(v.get(&3), Some(&3));
}
}