use crate::raw::{RawIntoIter, RawIter, RawTable};
use core::borrow::Borrow;
use core::fmt::{self, Debug};
use core::hash::{BuildHasher, Hash, Hasher};
use core::iter::{FromIterator, FusedIterator};
use core::marker::PhantomData;
use core::mem;
use core::ops::Index;
use hashbrown::hash_map::DefaultHashBuilder;
pub struct HashMap<K, V, S = DefaultHashBuilder> {
hash_builder: S,
table: RawTable<(K, V)>,
}
impl<K: Clone, V: Clone, S: Clone> Clone for HashMap<K, V, S> {
fn clone(&self) -> Self {
Self {
hash_builder: self.hash_builder.clone(),
table: self.table.clone(),
}
}
fn clone_from(&mut self, source: &Self) {
self.table.clone_from(&source.table);
self.hash_builder.clone_from(&source.hash_builder);
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub(crate) fn make_hash<K: Hash + ?Sized>(hash_builder: &impl BuildHasher, val: &K) -> u64 {
let mut state = hash_builder.build_hasher();
val.hash(&mut state);
state.finish()
}
#[cfg(feature = "ahash")]
impl<K, V> HashMap<K, V, DefaultHashBuilder> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn new() -> Self {
Self::default()
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, DefaultHashBuilder::default())
}
}
impl<K, V, S> HashMap<K, V, S> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn with_hasher(hash_builder: S) -> Self {
Self {
hash_builder,
table: RawTable::new(),
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
Self {
hash_builder,
table: RawTable::with_capacity(capacity),
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn hasher(&self) -> &S {
&self.hash_builder
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn capacity(&self) -> usize {
self.table.capacity()
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn keys(&self) -> Keys<'_, K, V> {
Keys { inner: self.iter() }
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn values(&self) -> Values<'_, K, V> {
Values { inner: self.iter() }
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
ValuesMut {
inner: self.iter_mut(),
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter(&self) -> Iter<'_, K, V> {
unsafe {
Iter {
inner: self.table.iter(),
marker: PhantomData,
}
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
unsafe {
IterMut {
inner: self.table.iter(),
marker: PhantomData,
}
}
}
#[cfg(test)]
#[cfg_attr(feature = "inline-more", inline)]
fn raw_capacity(&self) -> usize {
self.table.buckets()
}
#[cfg(test)]
fn is_split(&self) -> bool {
self.table.is_split()
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn len(&self) -> usize {
self.table.len()
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear(&mut self) {
self.table.clear();
}
}
impl<K, V, S> HashMap<K, V, S>
where
K: Eq + Hash,
S: BuildHasher,
{
#[inline]
pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
self.get_key_value(k).map(|(_, v)| v)
}
#[inline]
pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let hash = make_hash(&self.hash_builder, k);
self.table
.find(hash, |x| k.eq(x.0.borrow()))
.map(|item| unsafe {
let &(ref key, ref value) = item.as_ref();
(key, value)
})
}
#[inline]
pub fn get_key_value_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<(&K, &mut V)>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let hash = make_hash(&self.hash_builder, k);
self.table
.find(hash, |x| k.eq(x.0.borrow()))
.map(|item| unsafe {
let &mut (ref key, ref mut value) = item.as_mut();
(key, value)
})
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
where
K: Borrow<Q>,
Q: Hash + Eq,
{
self.get(k).is_some()
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
let hash = make_hash(&self.hash_builder, k);
self.table
.find(hash, |x| k.eq(x.0.borrow()))
.map(|item| unsafe { &mut item.as_mut().1 })
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
let hash = make_hash(&self.hash_builder, &k);
if let Some(item) = self.table.find(hash, |x| k.eq(&x.0)) {
let v = Some(mem::replace(unsafe { &mut item.as_mut().1 }, v));
if item.will_move() {
debug_assert!(self.table.is_split());
let hash_builder = &self.hash_builder;
self.table.carry(|x| make_hash(hash_builder, &x.0));
}
v
} else {
let hash_builder = &self.hash_builder;
self.table
.insert(hash, (k, v), |x| make_hash(hash_builder, &x.0));
None
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
self.remove_entry(k).map(|(_, v)| v)
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
Q: Hash + Eq,
{
unsafe {
let hash = make_hash(&self.hash_builder, &k);
if let Some(item) = self.table.find(hash, |x| k.eq(x.0.borrow())) {
self.table.erase_no_drop(&item);
Some(item.read())
} else {
None
}
}
}
}
impl<K, V, S> PartialEq for HashMap<K, V, S>
where
K: Eq + Hash,
V: PartialEq,
S: BuildHasher,
{
fn eq(&self, other: &Self) -> bool {
if self.len() != other.len() {
return false;
}
self.iter()
.all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
}
}
impl<K, V, S> Eq for HashMap<K, V, S>
where
K: Eq + Hash,
V: Eq,
S: BuildHasher,
{
}
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()
}
}
impl<K, V, S> Default for HashMap<K, V, S>
where
S: Default,
{
#[cfg_attr(feature = "inline-more", inline)]
fn default() -> Self {
Self::with_hasher(Default::default())
}
}
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;
#[cfg_attr(feature = "inline-more", inline)]
fn index(&self, key: &Q) -> &V {
self.get(key).expect("no entry found for key")
}
}
pub struct Iter<'a, K, V> {
inner: RawIter<(K, V)>,
marker: PhantomData<(&'a K, &'a V)>,
}
impl<K, V> Clone for Iter<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Iter {
inner: self.inner.clone(),
marker: PhantomData,
}
}
}
impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
pub struct IterMut<'a, K, V> {
inner: RawIter<(K, V)>,
marker: PhantomData<(&'a K, &'a mut V)>,
}
unsafe impl<K: Send, V: Send> Send for IterMut<'_, K, V> {}
impl<K, V> IterMut<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn iter(&self) -> Iter<'_, K, V> {
Iter {
inner: self.inner.clone(),
marker: PhantomData,
}
}
}
pub struct IntoIter<K, V> {
inner: RawIntoIter<(K, V)>,
}
impl<K, V> IntoIter<K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn iter(&self) -> Iter<'_, K, V> {
Iter {
inner: self.inner.iter(),
marker: PhantomData,
}
}
}
pub struct Keys<'a, K, V> {
inner: Iter<'a, K, V>,
}
impl<K, V> Clone for Keys<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Keys {
inner: self.inner.clone(),
}
}
}
impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
pub struct Values<'a, K, V> {
inner: Iter<'a, K, V>,
}
impl<K, V> Clone for Values<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Values {
inner: self.inner.clone(),
}
}
}
impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
pub struct ValuesMut<'a, K, V> {
inner: IterMut<'a, K, V>,
}
impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> Iter<'a, K, V> {
self.iter()
}
}
impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> IterMut<'a, K, V> {
self.iter_mut()
}
}
impl<K, V, S> IntoIterator for HashMap<K, V, S> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> IntoIter<K, V> {
IntoIter {
inner: self.table.into_iter(),
}
}
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<(&'a K, &'a V)> {
self.inner.next().map(|x| unsafe {
let r = x.as_ref();
(&r.0, &r.1)
})
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<K, V> FusedIterator for Iter<'_, K, V> {}
impl<'a, K, V> Iterator for IterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
self.inner.next().map(|x| unsafe {
let r = x.as_mut();
(&r.0, &mut r.1)
})
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<K, V> FusedIterator for IterMut<'_, K, V> {}
impl<K, V> fmt::Debug for IterMut<'_, K, V>
where
K: fmt::Debug,
V: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
impl<K, V> Iterator for IntoIter<K, V> {
type Item = (K, V);
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<(K, V)> {
self.inner.next()
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K, V> ExactSizeIterator for IntoIter<K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<K, V> FusedIterator for IntoIter<K, V> {}
impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
impl<'a, K, V> Iterator for Keys<'a, K, V> {
type Item = &'a K;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<&'a K> {
self.inner.next().map(|(k, _)| k)
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<K, V> FusedIterator for Keys<'_, K, V> {}
impl<'a, K, V> Iterator for Values<'a, K, V> {
type Item = &'a V;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<&'a V> {
self.inner.next().map(|(_, v)| v)
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K, V> ExactSizeIterator for Values<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<K, V> FusedIterator for Values<'_, K, V> {}
impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
type Item = &'a mut V;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<&'a mut V> {
self.inner.next().map(|(_, v)| v)
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
impl<K, V> fmt::Debug for ValuesMut<'_, K, V>
where
K: fmt::Debug,
V: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.inner.iter()).finish()
}
}
impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
where
K: Eq + Hash,
S: BuildHasher + Default,
{
#[cfg_attr(feature = "inline-more", inline)]
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
let iter = iter.into_iter();
let mut map = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
iter.for_each(|(k, v)| {
map.insert(k, v);
});
map
}
}
#[allow(dead_code)]
fn assert_covariance() {
fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
v
}
fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
v
}
fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
v
}
fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
v
}
fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
v
}
fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
v
}
fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
v
}
fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
v
}
fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
v
}
fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
v
}
}
#[cfg(test)]
mod test_map {
use super::DefaultHashBuilder;
use super::HashMap;
use std::cell::RefCell;
use std::usize;
use std::vec::Vec;
#[test]
fn test_zero_capacities() {
type HM = HashMap<i32, i32>;
let m = HM::new();
assert_eq!(m.capacity(), 0);
let m = HM::default();
assert_eq!(m.capacity(), 0);
let m = HM::with_hasher(DefaultHashBuilder::default());
assert_eq!(m.capacity(), 0);
let m = HM::with_capacity(0);
assert_eq!(m.capacity(), 0);
let m = HM::with_capacity_and_hasher(0, DefaultHashBuilder::default());
assert_eq!(m.capacity(), 0);
}
#[test]
fn test_create_capacity_zero() {
let mut m = HashMap::with_capacity(0);
assert!(m.insert(1, 1).is_none());
assert!(m.contains_key(&1));
assert!(!m.contains_key(&0));
}
#[test]
fn test_insert() {
let mut m = HashMap::new();
assert_eq!(m.len(), 0);
assert!(m.insert(1, 2).is_none());
assert_eq!(m.len(), 1);
assert!(m.insert(2, 4).is_none());
assert_eq!(m.len(), 2);
assert_eq!(*m.get(&1).unwrap(), 2);
assert_eq!(*m.get(&2).unwrap(), 4);
}
#[test]
fn test_split_insert() {
assert_eq!(crate::raw::R, 4);
let mut m = HashMap::new();
assert_eq!(m.capacity(), 0);
for i in 1..=3 {
m.insert(i, i);
assert_eq!(m.get(&i), Some(&i));
assert_eq!(m.capacity(), 3);
}
assert!(!m.is_split());
m.insert(4, 4);
assert_eq!(m.capacity(), 7);
assert!(!m.is_split());
assert_eq!(m.table.len(), 4);
for i in 1..=4 {
assert_eq!(m.get(&i), Some(&i));
}
for i in 5..=7 {
m.insert(i, i);
assert_eq!(m.get(&i), Some(&i));
assert_eq!(m.capacity(), 7);
}
m.insert(8, 8);
assert_eq!(m.capacity(), 14);
assert!(m.is_split());
assert_eq!(m.table.main().len(), 1 + crate::raw::R);
assert_eq!(
m.table.leftovers().map(|t| t.len()),
Some(8 - (1 + crate::raw::R))
);
for i in 1..=8 {
assert_eq!(m.get(&i), Some(&i));
}
assert_eq!(m.iter().count(), 8);
for i in 1..=8 {
assert!(m.iter().any(|(&e, _)| e == i));
}
assert_eq!(m.iter_mut().count(), 8);
for i in 1..=8 {
assert!(m.iter_mut().any(|(&e, _)| e == i));
}
m.insert(9, 9);
assert!(!m.is_split());
assert_eq!(m.table.len(), 9);
assert_eq!(m.capacity(), 14);
for i in 1..=9 {
assert_eq!(m.get(&i), Some(&i));
}
}
#[test]
fn test_clone() {
let mut m = HashMap::new();
for i in 1..=8 {
assert_eq!(m.len(), i - 1);
assert!(m.insert(i, i + 1).is_none());
}
assert_eq!(m.len(), 8);
let m2 = m.clone();
for i in 1..=8 {
assert_eq!(m2.get(&i).copied(), Some(i + 1));
}
assert_eq!(m2.len(), 8);
}
#[test]
fn test_clone_from() {
let mut m = HashMap::new();
let mut m2 = HashMap::new();
for i in 1..=8 {
assert_eq!(m.len(), i - 1);
assert!(m.insert(i, i + 1).is_none());
}
assert_eq!(m.len(), 8);
m2.clone_from(&m);
for i in 1..=8 {
assert_eq!(m2.get(&i).copied(), Some(i + 1));
}
assert_eq!(m2.len(), 8);
}
thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) }
#[derive(Hash, PartialEq, Eq)]
struct Droppable {
k: usize,
}
impl Droppable {
fn new(k: usize) -> Droppable {
DROP_VECTOR.with(|slot| {
slot.borrow_mut()[k] += 1;
});
Droppable { k }
}
}
impl Drop for Droppable {
fn drop(&mut self) {
DROP_VECTOR.with(|slot| {
slot.borrow_mut()[self.k] -= 1;
});
}
}
impl Clone for Droppable {
fn clone(&self) -> Self {
Droppable::new(self.k)
}
}
#[test]
fn test_drops() {
DROP_VECTOR.with(|slot| {
*slot.borrow_mut() = vec![0; 200];
});
{
let mut m = HashMap::new();
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 0);
}
});
for i in 0..100 {
let d1 = Droppable::new(i);
let d2 = Droppable::new(i + 100);
m.insert(d1, d2);
}
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 1);
}
});
for i in 0..50 {
let k = Droppable::new(i);
let v = m.remove(&k);
assert!(v.is_some());
DROP_VECTOR.with(|v| {
assert_eq!(v.borrow()[i], 1);
assert_eq!(v.borrow()[i + 100], 1);
});
}
DROP_VECTOR.with(|v| {
for i in 0..50 {
assert_eq!(v.borrow()[i], 0);
assert_eq!(v.borrow()[i + 100], 0);
}
for i in 50..100 {
assert_eq!(v.borrow()[i], 1);
assert_eq!(v.borrow()[i + 100], 1);
}
});
}
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 0);
}
});
}
#[test]
fn test_into_iter_drops() {
DROP_VECTOR.with(|v| {
*v.borrow_mut() = vec![0; 200];
});
let hm = {
let mut hm = HashMap::new();
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 0);
}
});
for i in 0..100 {
let d1 = Droppable::new(i);
let d2 = Droppable::new(i + 100);
hm.insert(d1, d2);
}
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 1);
}
});
hm
};
drop(hm.clone());
{
let mut half = hm.into_iter().take(50);
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 1);
}
});
for _ in half.by_ref() {}
DROP_VECTOR.with(|v| {
let nk = (0..100).filter(|&i| v.borrow()[i] == 1).count();
let nv = (0..100).filter(|&i| v.borrow()[i + 100] == 1).count();
assert_eq!(nk, 50);
assert_eq!(nv, 50);
});
};
DROP_VECTOR.with(|v| {
for i in 0..200 {
assert_eq!(v.borrow()[i], 0);
}
});
}
#[test]
fn test_empty_remove() {
let mut m: HashMap<i32, bool> = HashMap::new();
assert_eq!(m.remove(&0), None);
}
#[test]
fn test_empty_iter() {
let mut m: HashMap<i32, bool> = HashMap::new();
assert_eq!(m.keys().next(), None);
assert_eq!(m.values().next(), None);
assert_eq!(m.values_mut().next(), None);
assert_eq!(m.iter().next(), None);
assert_eq!(m.iter_mut().next(), None);
assert_eq!(m.len(), 0);
assert!(m.is_empty());
assert_eq!(m.into_iter().next(), None);
}
#[test]
#[cfg_attr(miri, ignore)]
#[ignore]
fn test_lots_of_insertions() {
let mut m = HashMap::new();
for _ in 0..10 {
assert!(m.is_empty());
for i in 1..1001 {
assert!(m.insert(i, i).is_none());
for j in 1..=i {
let r = m.get(&j);
assert_eq!(r, Some(&j));
}
for j in i + 1..1001 {
let r = m.get(&j);
assert_eq!(r, None);
}
}
for i in 1001..2001 {
assert!(!m.contains_key(&i));
}
for i in 1..1001 {
assert!(m.remove(&i).is_some());
for j in 1..=i {
assert!(!m.contains_key(&j));
}
for j in i + 1..1001 {
assert!(m.contains_key(&j));
}
}
for i in 1..1001 {
assert!(!m.contains_key(&i));
}
for i in 1..1001 {
assert!(m.insert(i, i).is_none());
}
for i in (1..1001).rev() {
assert!(m.remove(&i).is_some());
for j in i..1001 {
assert!(!m.contains_key(&j));
}
for j in 1..i {
assert!(m.contains_key(&j));
}
}
}
}
#[test]
fn test_find_mut() {
let mut m = HashMap::new();
for i in 1..=6 {
m.insert(1000 + i, i);
}
assert!(!m.is_split());
assert!(m.insert(1, 12).is_none());
assert!(!m.is_split());
assert!(m.insert(2, 8).is_none());
assert!(m.is_split());
assert!(m.insert(5, 14).is_none());
let new = 100;
match m.get_mut(&5) {
None => panic!(),
Some(x) => *x = new,
}
assert_eq!(m.get(&5), Some(&new));
}
#[test]
fn test_insert_overwrite() {
let mut m = HashMap::new();
for i in 1..=7 {
m.insert(1000 + i, i);
}
assert!(!m.is_split());
assert!(m.insert(1, 2).is_none());
assert!(m.is_split());
assert_eq!(*m.get(&1).unwrap(), 2);
assert!(!m.insert(1, 3).is_none());
assert_eq!(*m.get(&1).unwrap(), 3);
}
#[test]
fn test_insert_conflicts() {
let mut m = HashMap::with_capacity(4);
for i in 1..=7 {
m.insert(1000 + i, i);
}
assert!(!m.is_split());
assert!(m.insert(1, 2).is_none());
assert!(m.is_split());
assert!(m.insert(5, 3).is_none());
assert!(m.insert(9, 4).is_none());
assert_eq!(*m.get(&9).unwrap(), 4);
assert_eq!(*m.get(&5).unwrap(), 3);
assert_eq!(*m.get(&1).unwrap(), 2);
}
#[test]
fn test_conflict_remove() {
let mut m = HashMap::with_capacity(4);
for i in 1..=5 {
m.insert(1000 + i, i);
}
assert!(!m.is_split());
assert!(m.insert(1, 2).is_none());
assert_eq!(*m.get(&1).unwrap(), 2);
assert!(m.insert(5, 3).is_none());
assert!(!m.is_split());
assert_eq!(*m.get(&1).unwrap(), 2);
assert_eq!(*m.get(&5).unwrap(), 3);
assert!(m.insert(9, 4).is_none());
assert!(m.is_split());
assert_eq!(*m.get(&1).unwrap(), 2);
assert_eq!(*m.get(&5).unwrap(), 3);
assert_eq!(*m.get(&9).unwrap(), 4);
assert!(m.remove(&1).is_some());
assert_eq!(*m.get(&9).unwrap(), 4);
assert_eq!(*m.get(&5).unwrap(), 3);
}
#[test]
fn test_is_empty() {
let mut m = HashMap::with_capacity(4);
assert!(m.insert(1, 2).is_none());
assert!(!m.is_empty());
assert!(m.remove(&1).is_some());
assert!(m.is_empty());
}
#[test]
fn test_remove() {
let mut m = HashMap::new();
m.insert(1, 2);
assert_eq!(m.remove(&1), Some(2));
assert_eq!(m.remove(&1), None);
}
#[test]
fn test_remove_entry() {
let mut m = HashMap::new();
m.insert(1, 2);
assert_eq!(m.remove_entry(&1), Some((1, 2)));
assert_eq!(m.remove(&1), None);
}
#[test]
fn test_iterate() {
let mut m = HashMap::with_capacity(4);
for i in 0..32 {
assert!(m.insert(i, i * 2).is_none());
}
assert!(m.is_split());
assert_eq!(m.len(), 32);
let mut observed: u32 = 0;
for (k, v) in &m {
assert_eq!(*v, *k * 2);
observed |= 1 << *k;
}
assert_eq!(observed, 0xFFFF_FFFF);
}
#[test]
fn test_keys() {
let mut map = HashMap::new();
for (k, v) in (1..).zip(1000..).take(8) {
map.insert(k, v);
}
assert!(map.is_split());
let keys: Vec<_> = map.keys().cloned().collect();
assert_eq!(keys.len(), 8);
for i in 1..=8 {
assert!(keys.contains(&i));
}
}
#[test]
fn test_values() {
let mut map = HashMap::new();
for (k, v) in (1..).zip(1000..).take(8) {
map.insert(k, v);
}
assert!(map.is_split());
let values: Vec<_> = map.values().cloned().collect();
assert_eq!(values.len(), 8);
for c in 1000..=1007 {
assert!(values.contains(&c));
}
}
#[test]
fn test_values_mut() {
let mut map = HashMap::new();
for v in (1..).take(8) {
map.insert(v, v);
}
assert!(map.is_split());
for value in map.values_mut() {
*value = (*value) * 2
}
let values: Vec<_> = map.values().cloned().collect();
assert_eq!(values.len(), 8);
for v in 1..=8 {
let v = 2 * v;
assert!(values.contains(&v));
}
}
#[test]
fn test_find() {
let mut m = HashMap::new();
assert!(m.get(&1).is_none());
m.insert(1, 2);
match m.get(&1) {
None => panic!(),
Some(v) => assert_eq!(*v, 2),
}
assert!(!m.is_split());
for i in 1..=7 {
m.insert(1000 + i, i);
}
assert!(m.is_split());
match m.get(&1) {
None => panic!(),
Some(v) => assert_eq!(*v, 2),
}
m.insert(1000 + 8, 8);
assert!(!m.is_split());
match m.get(&1) {
None => panic!(),
Some(v) => assert_eq!(*v, 2),
}
}
#[test]
fn test_eq() {
let mut m1 = HashMap::new();
for (k, v) in (1..).zip(1000..).take(8) {
m1.insert(k, v);
}
let mut m2 = HashMap::new();
for (k, v) in (1..).zip(1000..).take(7) {
m2.insert(k, v);
}
assert!(m1 != m2);
m2.insert(8, 1007);
assert_eq!(m1, m2);
}
#[test]
fn test_show() {
let mut map = HashMap::new();
let empty: HashMap<i32, i32> = HashMap::new();
map.insert(1, 2);
map.insert(3, 4);
let map_str = format!("{:?}", map);
assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
assert_eq!(format!("{:?}", empty), "{}");
}
#[test]
fn test_expand() {
let mut m = HashMap::new();
assert_eq!(m.len(), 0);
assert!(m.is_empty());
let mut i = 0;
let old_raw_cap = m.raw_capacity();
while old_raw_cap == m.raw_capacity() {
m.insert(i, i);
i += 1;
}
assert_eq!(m.len(), i);
assert!(!m.is_empty());
}
#[test]
fn test_from_iter() {
let xs = (0..8).map(|v| (v, v));
let map: HashMap<_, _> = xs.clone().collect();
for (k, v) in xs.clone() {
assert_eq!(map.get(&k), Some(&v));
}
assert_eq!(map.iter().len(), xs.len());
}
#[test]
fn test_size_hint() {
let xs = (0..8).map(|v| (v, v));
let map: HashMap<_, _> = xs.clone().collect();
let mut iter = map.iter();
for _ in iter.by_ref().take(3) {}
assert_eq!(iter.size_hint(), (8 - 3, Some(8 - 3)));
}
#[test]
fn test_iter_len() {
let xs = (0..8).map(|v| (v, v));
let map: HashMap<_, _> = xs.clone().collect();
let mut iter = map.iter();
for _ in iter.by_ref().take(3) {}
assert_eq!(iter.len(), 8 - 3);
}
#[test]
fn test_mut_size_hint() {
let xs = (0..8).map(|v| (v, v));
let mut map: HashMap<_, _> = xs.clone().collect();
let mut iter = map.iter_mut();
for _ in iter.by_ref().take(3) {}
assert_eq!(iter.size_hint(), (8 - 3, Some(8 - 3)));
}
#[test]
fn test_iter_mut_len() {
let xs = (0..8).map(|v| (v, v));
let mut map: HashMap<_, _> = xs.clone().collect();
let mut iter = map.iter_mut();
for _ in iter.by_ref().take(3) {}
assert_eq!(iter.len(), 8 - 3);
}
#[test]
fn test_index() {
let mut map = HashMap::new();
for i in 1..=8 {
map.insert(i, i);
}
assert!(map.is_split());
assert_eq!(map[&2], 2);
}
#[test]
#[should_panic]
fn test_index_nonexistent() {
let mut map = HashMap::new();
for i in 1..=8 {
map.insert(i, i);
}
assert!(map.is_split());
map[&9];
}
#[test]
fn test_capacity_not_less_than_len() {
let mut a = HashMap::new();
let mut item = 0;
for _ in 0..116 {
a.insert(item, 0);
item += 1;
}
assert!(a.capacity() > a.len());
let free = a.capacity() - a.len();
for _ in 0..free {
a.insert(item, 0);
item += 1;
}
assert_eq!(a.len(), a.capacity());
a.insert(item, 0);
assert!(a.capacity() > a.len());
}
}