use std::fmt;
use std::fmt::Debug;
use std::hash::Hash;
use std::hash::Hasher;
use std::marker::PhantomData;
use std::mem;
use allocative::Allocative;
use equivalent::Equivalent;
use hashbrown::raw::RawTable;
use serde::Deserialize;
use serde::Serialize;
use crate::hashed::Hashed;
pub use crate::small_map::iter::IntoIter;
pub use crate::small_map::iter::IntoIterHashed;
pub use crate::small_map::iter::IntoKeys;
pub use crate::small_map::iter::IntoValues;
pub use crate::small_map::iter::Iter;
pub use crate::small_map::iter::IterHashed;
pub use crate::small_map::iter::IterMut;
pub use crate::small_map::iter::IterMutUnchecked;
pub use crate::small_map::iter::Keys;
pub use crate::small_map::iter::Values;
pub use crate::small_map::iter::ValuesMut;
use crate::vec_map::VecMap;
use crate::StarlarkHashValue;
mod iter;
#[cfg(rust_nightly)]
const NO_INDEX_THRESHOLD: usize = 32;
#[cfg(not(rust_nightly))]
const NO_INDEX_THRESHOLD: usize = 16;
#[repr(C)]
#[derive(Clone, Allocative)]
pub struct SmallMap<K, V> {
entries: VecMap<K, V>,
index: Option<Box<RawTable<usize>>>,
}
impl<K, V> Default for SmallMap<K, V> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<K: Debug, V: Debug> Debug for SmallMap<K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<K, V> SmallMap<K, V> {
#[inline]
pub const fn new() -> Self {
Self {
entries: VecMap::new(),
index: None,
}
}
#[inline]
pub fn with_capacity(n: usize) -> Self {
if n <= NO_INDEX_THRESHOLD {
SmallMap {
entries: VecMap::with_capacity(n),
index: None,
}
} else {
SmallMap {
entries: VecMap::with_capacity(n),
index: Some(Box::new(RawTable::with_capacity(n))),
}
}
}
#[cfg(test)]
fn assert_invariants(&self)
where
K: Eq,
{
if let Some(index) = &self.index {
assert_eq!(index.len(), self.entries.len());
for (i, (k, _)) in self.entries.iter_hashed().enumerate() {
let j = *index
.get(k.hash().promote(), |j| {
&self.entries.get_index(*j).unwrap().0 == k.key()
})
.unwrap();
assert_eq!(i, j);
}
} else {
assert!(self.entries.len() <= NO_INDEX_THRESHOLD);
}
}
pub fn maybe_drop_index(&mut self) {
if self.entries.len() <= NO_INDEX_THRESHOLD {
self.index = None;
}
}
#[inline]
pub fn keys(&self) -> Keys<K, V> {
Keys {
iter: self.entries.keys(),
}
}
#[inline]
pub fn values(&self) -> Values<K, V> {
Values {
iter: self.entries.values(),
}
}
#[inline]
pub fn into_keys(self) -> IntoKeys<K, V> {
IntoKeys {
iter: self.entries.into_iter(),
}
}
#[inline]
pub fn into_values(self) -> IntoValues<K, V> {
IntoValues {
iter: self.entries.into_iter(),
}
}
#[inline]
pub fn values_mut(&mut self) -> ValuesMut<K, V> {
ValuesMut {
iter: self.entries.values_mut(),
}
}
#[inline]
pub fn iter(&self) -> Iter<'_, K, V> {
Iter {
iter: self.entries.iter(),
}
}
#[inline]
pub fn iter_hashed(&self) -> IterHashed<K, V> {
IterHashed {
iter: self.entries.iter_hashed(),
}
}
#[inline]
pub fn into_iter_hashed(self) -> IntoIterHashed<K, V> {
IntoIterHashed {
iter: self.entries.into_iter_hashed(),
}
}
#[inline]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
IterMut {
iter: self.entries.iter_mut(),
}
}
#[inline]
pub fn iter_mut_unchecked(&mut self) -> IterMutUnchecked<'_, K, V> {
IterMutUnchecked {
iter: self.entries.iter_mut_unchecked(),
}
}
#[inline]
fn into_iter(self) -> IntoIter<K, V> {
IntoIter {
iter: self.entries.into_iter(),
}
}
#[inline]
pub fn get_hashed<Q>(&self, key: Hashed<&Q>) -> Option<&V>
where
Q: Equivalent<K> + ?Sized,
{
self.get_index_of_hashed(key)
.map(|index| unsafe { self.entries.get_unchecked(index).1 })
}
#[inline]
pub fn get_hashed_by_value<Q>(&self, key: Hashed<Q>) -> Option<&V>
where
Q: Equivalent<K>,
{
self.get_index_of_hashed_by_value(key)
.map(|index| unsafe { self.entries.get_unchecked(index).1 })
}
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
Q: Hash + Equivalent<K> + ?Sized,
{
self.get_hashed(Hashed::new(key))
}
#[inline]
pub fn get_full<Q>(&self, key: &Q) -> Option<(usize, &K, &V)>
where
Q: Hash + Equivalent<K> + ?Sized,
{
self.get_full_hashed(Hashed::new(key))
}
#[inline]
pub fn get_full_hashed<Q>(&self, key: Hashed<&Q>) -> Option<(usize, &K, &V)>
where
Q: Equivalent<K> + ?Sized,
{
self.get_index_of_hashed(key).map(|index| {
let (key, value) = unsafe { self.entries.get_unchecked(index) };
(index, *key.key(), value)
})
}
#[inline]
fn get_index_of_hashed_raw_with_index(
&self,
hash: StarlarkHashValue,
mut eq: impl FnMut(&K) -> bool,
index: &RawTable<usize>,
) -> Option<usize> {
index
.get(hash.promote(), |&index| unsafe {
eq(self.entries.get_unchecked(index).0.key())
})
.copied()
}
#[inline]
pub(crate) fn get_index_of_hashed_raw(
&self,
hash: StarlarkHashValue,
eq: impl FnMut(&K) -> bool,
) -> Option<usize> {
match &self.index {
None => self.entries.get_index_of_hashed_raw(hash, eq),
Some(index) => self.get_index_of_hashed_raw_with_index(hash, eq, index),
}
}
#[inline]
pub fn get_index_of_hashed<Q>(&self, key: Hashed<&Q>) -> Option<usize>
where
Q: Equivalent<K> + ?Sized,
{
self.get_index_of_hashed_raw(key.hash(), |k| key.key().equivalent(k))
}
#[inline]
pub fn get_index_of_hashed_by_value<Q>(&self, key: Hashed<Q>) -> Option<usize>
where
Q: Equivalent<K>,
{
self.get_index_of_hashed_raw(key.hash(), |k| key.key().equivalent(k))
}
#[inline]
pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
self.entries.get_index(index)
}
#[inline]
pub fn get_index_of<Q>(&self, key: &Q) -> Option<usize>
where
Q: Hash + Equivalent<K> + ?Sized,
{
self.get_index_of_hashed(Hashed::new(key))
}
#[inline]
pub fn get_mut_hashed<Q>(&mut self, key: Hashed<&Q>) -> Option<&mut V>
where
Q: Equivalent<K> + ?Sized,
{
let i = self.get_index_of_hashed(key)?;
debug_assert!(i < self.entries.len());
Some(unsafe { self.entries.get_unchecked_mut(i).1 })
}
#[inline]
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
Q: Hash + Equivalent<K> + ?Sized,
{
self.get_mut_hashed(Hashed::new(key))
}
#[inline]
pub fn contains_key_hashed<Q>(&self, key: Hashed<&Q>) -> bool
where
Q: Equivalent<K> + ?Sized,
{
self.get_index_of_hashed(key).is_some()
}
#[inline]
pub fn contains_key_hashed_by_value<Q>(&self, key: Hashed<Q>) -> bool
where
Q: Equivalent<K>,
{
self.get_index_of_hashed_by_value(key).is_some()
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
Q: Hash + Equivalent<K> + ?Sized,
{
self.contains_key_hashed(Hashed::new(key))
}
#[inline]
pub fn reserve(&mut self, additional: usize)
where
K: Eq,
{
self.entries.reserve(additional);
if let Some(index) = &mut self.index {
index.reserve(additional, Self::hasher(&self.entries));
} else if self.len() + additional > NO_INDEX_THRESHOLD {
self.create_index(self.len() + additional);
}
}
#[inline]
pub fn capacity(&self) -> usize {
self.entries.capacity()
}
pub fn first(&self) -> Option<(&K, &V)> {
self.iter().next()
}
pub fn last(&self) -> Option<(&K, &V)> {
self.iter().next_back()
}
#[cold]
fn create_index(&mut self, capacity: usize) {
debug_assert!(self.index.is_none());
debug_assert!(capacity >= self.entries.len());
let mut index = RawTable::with_capacity(capacity);
for (i, (k, _)) in self.entries.iter_hashed().enumerate() {
unsafe { index.insert_no_grow(k.hash().promote(), i) };
}
self.index = Some(Box::new(index));
}
#[inline(always)]
fn hasher(entries: &VecMap<K, V>) -> impl Fn(&usize) -> u64 + '_ {
move |&index| {
debug_assert!(index < entries.len());
unsafe { entries.get_unchecked(index).0.hash().promote() }
}
}
#[inline]
pub fn insert_hashed_unique_unchecked(&mut self, key: Hashed<K>, val: V) -> (&K, &mut V) {
let hash = key.hash();
let entry_index = self.entries.len();
self.entries.insert_hashed_unique_unchecked(key, val);
if let Some(index) = &mut self.index {
index.insert(hash.promote(), entry_index, Self::hasher(&self.entries));
} else if self.entries.len() == NO_INDEX_THRESHOLD + 1 {
self.create_index(self.entries.len());
} else {
debug_assert!(self.entries.len() < NO_INDEX_THRESHOLD + 1);
}
unsafe {
let (key, value) = self.entries.get_unchecked_mut(self.entries.len() - 1);
(key.key(), value)
}
}
#[inline]
pub fn insert_hashed(&mut self, key: Hashed<K>, val: V) -> Option<V>
where
K: Eq,
{
match self.get_index_of_hashed_raw(key.hash(), |k| key.key().equivalent(k)) {
None => {
self.insert_hashed_unique_unchecked(key, val);
None
}
Some(i) => unsafe {
debug_assert!(i < self.entries.len());
Some(mem::replace(self.entries.get_unchecked_mut(i).1, val))
},
}
}
#[inline]
pub fn insert(&mut self, key: K, val: V) -> Option<V>
where
K: Hash + Eq,
{
self.insert_hashed(Hashed::new(key), val)
}
#[inline]
pub fn insert_unique_unchecked(&mut self, key: K, val: V) -> (&K, &mut V)
where
K: Hash,
{
self.insert_hashed_unique_unchecked(Hashed::new(key), val)
}
pub fn remove_hashed<Q>(&mut self, key: Hashed<&Q>) -> Option<V>
where
Q: ?Sized + Equivalent<K>,
{
self.remove_hashed_entry(key).map(|(_k, v)| v)
}
pub fn remove_hashed_entry<Q>(&mut self, key: Hashed<&Q>) -> Option<(K, V)>
where
Q: ?Sized + Equivalent<K>,
{
let hash = key.hash();
if let Some(index) = &mut self.index {
let entries = &self.entries;
let i = index.remove_entry(hash.promote(), |&i| unsafe {
key.key().equivalent(entries.get_unchecked(i).0.key())
})?;
unsafe {
if i != self.entries.len() - 1 {
for bucket in index.iter() {
debug_assert!(*bucket.as_ref() != i);
if *bucket.as_mut() > i {
*bucket.as_mut() -= 1;
}
}
}
}
let (key, value) = self.entries.remove(i);
Some((key.into_key(), value))
} else {
self.entries.remove_hashed_entry(key)
}
}
pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
Q: ?Sized + Hash + Equivalent<K>,
{
self.remove_hashed(Hashed::new(key))
}
pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
Q: ?Sized + Hash + Equivalent<K>,
{
self.remove_hashed_entry(Hashed::new(key))
}
#[inline]
pub fn entry_hashed(&mut self, key: Hashed<K>) -> Entry<'_, K, V>
where
K: Eq,
{
match self.get_index_of_hashed_raw(key.hash(), |k| key.key().equivalent(k)) {
Some(i) => {
let (key, value) = unsafe { self.entries.get_unchecked_mut(i) };
Entry::Occupied(OccupiedEntry {
key: key.key(),
value,
})
}
None => Entry::Vacant(VacantEntry { key, map: self }),
}
}
pub fn pop(&mut self) -> Option<(K, V)> {
match self.entries.pop() {
None => None,
Some((key, value)) => {
if let Some(index) = &mut self.index {
let removed =
index.remove_entry(key.hash().promote(), |&i| i == self.entries.len());
debug_assert!(removed.unwrap() == self.entries.len());
}
Some((key.into_key(), value))
}
}
}
#[inline]
pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
where
K: Eq + Hash,
{
self.entry_hashed(Hashed::new(key))
}
#[inline]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
#[inline]
pub fn len(&self) -> usize {
self.entries.len()
}
#[inline]
pub fn clear(&mut self) {
self.entries.clear();
if let Some(index) = &mut self.index {
index.clear();
}
}
#[cfg(test)]
fn state_check(&self) {
if let Some(index) = &self.index {
assert_eq!(self.entries.len(), index.len());
let mut set_fields = vec![false; self.entries.len()];
unsafe {
for bucket in index.iter() {
let i = *bucket.as_ref();
let prev = mem::replace(&mut set_fields[i], true);
assert!(!prev);
}
}
} else {
assert!(self.entries.len() <= NO_INDEX_THRESHOLD);
}
}
fn is_sorted_by_key(&self) -> bool
where
K: Ord,
{
self.entries.is_sorted_by_key()
}
pub fn sort_keys(&mut self)
where
K: Ord,
{
if self.is_sorted_by_key() {
return;
}
struct RebuildIndexOnDrop<'a, K, V> {
map: &'a mut SmallMap<K, V>,
}
impl<'a, K, V> Drop for RebuildIndexOnDrop<'a, K, V> {
fn drop(&mut self) {
if let Some(index) = &mut self.map.index {
index.clear();
for (i, (k, _)) in self.map.entries.iter_hashed().enumerate() {
unsafe { index.insert_no_grow(k.hash().promote(), i) };
}
}
}
}
let map = RebuildIndexOnDrop { map: self };
map.map.entries.sort_keys();
}
pub fn eq_ordered(&self, other: &Self) -> bool
where
K: PartialEq,
V: PartialEq,
{
self.entries.eq_ordered(&other.entries)
}
pub fn hash_ordered<H: Hasher>(&self, state: &mut H)
where
K: Hash,
V: Hash,
{
self.entries.hash_ordered(state)
}
pub fn reverse(&mut self) {
self.entries.reverse();
if let Some(index) = &mut self.index {
let len = self.entries.len();
unsafe {
for entry in index.iter() {
*entry.as_mut() = len - 1 - *entry.as_ref();
}
}
}
}
}
pub struct OccupiedEntry<'a, K, V> {
key: &'a K,
value: &'a mut V,
}
pub struct VacantEntry<'a, K, V> {
key: Hashed<K>,
map: &'a mut SmallMap<K, V>,
}
pub enum Entry<'a, K, V> {
Occupied(OccupiedEntry<'a, K, V>),
Vacant(VacantEntry<'a, K, V>),
}
impl<'a, K, V> OccupiedEntry<'a, K, V> {
#[inline]
pub fn key(&self) -> &K {
self.key
}
#[inline]
pub fn get(&self) -> &V {
self.value
}
#[inline]
pub fn get_mut(&mut self) -> &mut V {
self.value
}
#[inline]
pub fn into_mut(self) -> &'a mut V {
self.value
}
#[inline]
pub(crate) fn into_mut_entry(self) -> (&'a K, &'a mut V) {
(self.key, self.value)
}
}
impl<'a, K, V> VacantEntry<'a, K, V>
where
K: Eq,
{
#[inline]
pub fn key(&self) -> &K {
self.key.key()
}
#[inline]
pub fn insert(self, value: V) -> &'a mut V {
self.insert_entry(value).1
}
#[inline]
pub(crate) fn insert_entry(self, value: V) -> (&'a K, &'a mut V) {
self.map.insert_hashed_unique_unchecked(self.key, value)
}
}
impl<'a, K, V> Entry<'a, K, V>
where
K: Eq,
{
#[inline]
pub fn key(&self) -> &K {
match self {
Entry::Occupied(e) => e.key(),
Entry::Vacant(e) => e.key(),
}
}
#[inline]
pub fn or_insert(self, default: V) -> &'a mut V {
self.or_insert_with(|| default)
}
#[inline]
pub fn or_insert_with(self, default: impl FnOnce() -> V) -> &'a mut V {
self.or_insert_entry_with(default).1
}
#[inline]
pub fn or_default(self) -> &'a mut V
where
V: Default,
{
#[allow(clippy::unwrap_or_default)] self.or_insert_with(V::default)
}
#[inline]
pub(crate) fn or_insert_entry_with(self, default: impl FnOnce() -> V) -> (&'a K, &'a mut V) {
match self {
Entry::Occupied(e) => e.into_mut_entry(),
Entry::Vacant(e) => e.insert_entry(default()),
}
}
}
impl<K, V> FromIterator<(K, V)> for SmallMap<K, V>
where
K: Hash + Eq,
{
fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
let iter = iter.into_iter();
let mut mp = Self::with_capacity(iter.size_hint().0);
for (k, v) in iter {
mp.insert(k, v);
}
mp
}
}
impl<K, V> FromIterator<(Hashed<K>, V)> for SmallMap<K, V>
where
K: Eq,
{
fn from_iter<I: IntoIterator<Item = (Hashed<K>, V)>>(iter: I) -> Self {
let iter = iter.into_iter();
let mut mp = Self::with_capacity(iter.size_hint().0);
for (k, v) in iter {
mp.insert_hashed(k, v);
}
mp
}
}
impl<K, V> IntoIterator for SmallMap<K, V> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.into_iter()
}
}
impl<'a, K, V> IntoIterator for &'a SmallMap<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, K, V> IntoIterator for &'a mut SmallMap<K, V> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<K: Eq, V: PartialEq> PartialEq for SmallMap<K, V> {
fn eq(&self, other: &Self) -> bool {
self.len() == other.len()
&& self
.iter_hashed()
.all(|(k, v)| other.get_hashed(k) == Some(v))
}
}
impl<K: Eq, V: Eq> Eq for SmallMap<K, V> {}
impl<K, V> Extend<(K, V)> for SmallMap<K, V>
where
K: Hash + Eq,
{
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
for (k, v) in iter {
self.insert(k, v);
}
}
}
#[macro_export]
macro_rules! smallmap {
(@single $($x:tt)*) => (());
(@count $($rest:expr),*) => (<[()]>::len(&[$(smallmap!(@single $rest)),*]));
($($key:expr => $value:expr,)+) => { smallmap!($($key => $value),+) };
($($key:expr => $value:expr),*) => {
{
let cap = smallmap!(@count $($key),*);
#[allow(unused_mut)]
let mut map = $crate::small_map::SmallMap::with_capacity(cap);
$(
map.insert($key, $value);
)*
map
}
};
}
impl<K: Serialize, V: Serialize> Serialize for SmallMap<K, V> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
serializer.collect_map(self.iter())
}
}
impl<'de, K, V> Deserialize<'de> for SmallMap<K, V>
where
K: Deserialize<'de> + Hash + Eq,
V: Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::Deserializer<'de>,
{
struct MapVisitor<K, V> {
marker: PhantomData<SmallMap<K, V>>,
}
impl<'de, K, V> serde::de::Visitor<'de> for MapVisitor<K, V>
where
K: Deserialize<'de> + Hash + Eq,
V: Deserialize<'de>,
{
type Value = SmallMap<K, V>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("a map")
}
#[inline]
fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
where
A: serde::de::MapAccess<'de>,
{
let mut values = SmallMap::with_capacity(map.size_hint().unwrap_or(0));
while let Some((key, value)) = map.next_entry()? {
values.insert(key, value);
}
Ok(values)
}
}
let visitor = MapVisitor {
marker: PhantomData,
};
deserializer.deserialize_map(visitor)
}
}
#[cfg(test)]
mod tests {
use std::cmp::Ordering;
use std::panic::catch_unwind;
use std::panic::AssertUnwindSafe;
use super::*;
#[test]
fn empty_map() {
let m = SmallMap::<i8, &str>::new();
assert_eq!(m.is_empty(), true);
assert_eq!(m.len(), 0);
assert_eq!(m.iter().next(), None);
}
#[test]
#[allow(clippy::map_identity)]
fn few_entries() {
let entries1 = [(0, 'a'), (1, 'b')];
let m1 = entries1.iter().copied().collect::<SmallMap<_, _>>();
let entries2 = [(1, 'b'), (0, 'a')];
let m2 = entries2.iter().copied().collect::<SmallMap<_, _>>();
assert_eq!(m1.is_empty(), false);
assert_eq!(m1.len(), 2);
assert_eq!(m2.is_empty(), false);
assert_eq!(m2.len(), 2);
assert_eq!(m1.iter().eq(entries1.iter().map(|(k, v)| (k, v))), true);
assert_eq!(m2.iter().eq(entries2.iter().map(|(k, v)| (k, v))), true);
assert_eq!(m1.iter().eq(m2.iter()), false);
assert_eq!(m1.eq(&m1), true);
assert_eq!(m2.eq(&m2), true);
assert_eq!(m1, m2);
assert_eq!(m1.get(&0), Some(&'a'));
assert_eq!(m1.get(&3), None);
assert_eq!(m2.get(&1), Some(&'b'));
assert_eq!(m2.get(&3), None);
assert_eq!(m1.get_index(0), Some((&0, &'a')));
assert_eq!(m1.get_index(1), Some((&1, &'b')));
assert_eq!(m1.get_index(2), None);
assert_ne!(m1, smallmap! { 0 => 'a', 1 => 'c' });
let iter = m1.iter();
let (values1, values2): (Vec<_>, Vec<_>) = (iter.clone().collect(), iter.collect());
assert_eq!(values1, values2);
}
#[test]
fn many_entries() {
let numbers = 0..26;
let letters = 'a'..='z';
let entries1 = numbers.zip(letters);
let m1 = entries1.clone().collect::<SmallMap<_, _>>();
let numbers = (0..26).rev();
let letters = ('a'..='z').rev();
let entries2 = numbers.zip(letters);
let m2 = entries2.clone().collect::<SmallMap<_, _>>();
assert_eq!(m1.is_empty(), false);
assert_eq!(m1.len(), 26);
assert_eq!(m2.is_empty(), false);
assert_eq!(m2.len(), 26);
assert_eq!(m1.clone().into_iter().eq(entries1), true);
assert_eq!(m2.clone().into_iter().eq(entries2), true);
assert_eq!(m1.iter().eq(m2.iter()), false);
assert_eq!(m1.eq(&m1), true);
assert_eq!(m2.eq(&m2), true);
assert_eq!(m1, m2);
assert_eq!(m1.get(&1), Some(&'b'));
assert_eq!(m1.get(&30), None);
assert_eq!(m2.get(&0), Some(&'a'));
assert_eq!(m2.get(&30), None);
assert_eq!(m2.get_full(&0), Some((25, &0, &'a')));
assert_eq!(m2.get_full(&25), Some((0, &25, &'z')));
assert_eq!(m2.get_full(&29), None);
let not_m1 = {
let mut m = m1.clone();
m.remove(&1);
m
};
assert_ne!(m1, not_m1);
let iter = m1.iter();
let (values1, values2): (Vec<_>, Vec<_>) = (iter.clone().collect(), iter.collect());
assert_eq!(values1, values2);
}
#[test]
fn test_smallmap_macro() {
let map = smallmap![1 => "a", 3 => "b"];
let mut i = map.into_iter();
assert_eq!(i.next(), Some((1, "a")));
assert_eq!(i.next(), Some((3, "b")));
assert_eq!(i.next(), None);
}
#[test]
fn test_clone() {
let map = smallmap![1 => "a", 3 => "b"];
let iter = map.iter();
let values1: Vec<_> = iter.clone().collect();
let values2: Vec<_> = iter.collect();
assert_eq!(vec![(&1, &"a"), (&3, &"b")], values1);
assert_eq!(values1, values2);
let iter = map.keys();
let values1: Vec<_> = iter.clone().collect();
let values2: Vec<_> = iter.collect();
assert_eq!(vec![&1, &3], values1);
assert_eq!(values1, values2);
let iter = map.values();
let values1: Vec<_> = iter.clone().collect();
let values2: Vec<_> = iter.collect();
assert_eq!(vec![&"a", &"b"], values1);
assert_eq!(values1, values2);
}
#[test]
fn test_duplicate_hashes() {
#[derive(PartialEq, Eq, Debug)]
struct K(i32);
#[allow(clippy::derived_hash_with_manual_eq)]
impl Hash for K {
fn hash<H: Hasher>(&self, _state: &mut H) {}
}
let mut map = smallmap![K(1) => "test", K(3) => "more"];
assert_eq!(map.get(&K(1)), Some(&"test"));
assert_eq!(map.get(&K(2)), None);
assert_eq!(map.get(&K(3)), Some(&"more"));
assert_eq!(map.insert(K(2), "magic"), None);
assert_eq!(map.get(&K(2)), Some(&"magic"));
assert_eq!(map.remove(&K(1)), Some("test"));
assert_eq!(map.get(&K(1)), None);
assert_eq!(map.keys().collect::<Vec<_>>(), vec![&K(3), &K(2)]);
}
#[test]
fn test_smallmap_debug() {
let s = format!("{:?}", smallmap![1 => "test", 2 => "more"]);
assert_eq!(s, "{1: \"test\", 2: \"more\"}")
}
#[test]
fn entry() {
let mut map = SmallMap::new();
for i in 0..100 {
match map.entry(i) {
Entry::Vacant(e) => {
e.insert(i * 2);
}
Entry::Occupied(..) => panic!(),
}
match map.entry(i) {
Entry::Occupied(..) => {}
Entry::Vacant(..) => panic!(),
}
}
}
#[test]
fn test_pop_small() {
let mut map = SmallMap::new();
for i in 0..=5 {
map.insert(i, i * 10);
}
for i in (0..=5).rev() {
assert_eq!((i, i * 10), map.pop().unwrap());
map.state_check();
}
assert!(map.is_empty());
}
#[test]
fn test_pop_large() {
let mut map = SmallMap::new();
for i in 0..=500 {
map.insert(i, i * 10);
}
for i in (0..=500).rev() {
assert_eq!((i, i * 10), map.pop().unwrap());
if i % 100 == 0 {
map.state_check();
}
}
assert!(map.is_empty());
}
#[test]
fn test_first() {
let mut map = SmallMap::new();
map.insert(1, 10);
assert_eq!(map.first(), Some((&1, &10)));
map.insert(2, 20);
assert_eq!(map.first(), Some((&1, &10)));
map.remove(&1);
assert_eq!(map.first(), Some((&2, &20)));
}
#[test]
fn test_last() {
let mut map = SmallMap::new();
map.insert(1, 10);
assert_eq!(map.last(), Some((&1, &10)));
map.insert(2, 20);
assert_eq!(map.last(), Some((&2, &20)));
map.insert(1, 100);
assert_eq!(map.last(), Some((&2, &20)));
}
#[test]
fn test_sort_keys_no_index() {
let mut map = SmallMap::new();
map.insert(2, 20);
map.insert(1, 10);
map.insert(3, 30);
map.sort_keys();
assert_eq!(
vec![(&1, &10), (&2, &20), (&3, &30)],
map.iter().collect::<Vec<_>>()
);
assert_eq!(&10, map.get(&1).unwrap());
assert_eq!(&20, map.get(&2).unwrap());
assert_eq!(&30, map.get(&3).unwrap());
}
#[test]
fn test_sort_keys_with_index() {
let mut map = SmallMap::new();
for i in 1..=100 {
map.insert(i, i * 10);
}
map.sort_keys();
assert_eq!(
(1..=100).map(|i| (i, i * 10)).collect::<Vec<_>>(),
map.iter().map(|(k, v)| (*k, *v)).collect::<Vec<_>>()
);
for i in 1..=100 {
assert_eq!(i * 10, *map.get(&i).unwrap());
}
}
#[test]
fn test_sort_keys_updates_index_on_panic() {
#[derive(Hash, PartialEq, Eq, Debug)]
struct Key(u32);
impl PartialOrd for Key {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Key {
fn cmp(&self, other: &Self) -> Ordering {
if self.0 < 10 && other.0 < 10 {
panic!("panic in Ord::cmp")
}
self.0.cmp(&other.0)
}
}
let mut map = SmallMap::new();
for i in (1..=100).rev() {
map.insert(Key(i), i * 10);
}
catch_unwind(AssertUnwindSafe(|| map.sort_keys())).unwrap_err();
map.assert_invariants();
}
#[test]
fn test_eq_ordered() {
let m0 = SmallMap::from_iter([(1, 2), (3, 4)]);
let m1 = SmallMap::from_iter([(1, 2), (3, 4)]);
let m2 = SmallMap::from_iter([(3, 4), (1, 2)]);
let m3 = SmallMap::from_iter([(3, 4)]);
assert!(m0.eq_ordered(&m0));
assert!(m0.eq_ordered(&m1));
assert!(!m0.eq_ordered(&m2));
assert!(!m0.eq_ordered(&m3));
}
#[test]
fn test_remove() {
let mut m = (0..100).map(|i| (i, i * 10)).collect::<SmallMap<_, _>>();
assert_eq!(Some((1, 10)), m.remove_entry(&1));
assert_eq!(Some(&30), m.get(&3));
m.assert_invariants();
}
#[test]
fn test_remove_last() {
let mut m = (0..100).map(|i| (i, i * 10)).collect::<SmallMap<_, _>>();
assert_eq!(Some((99, 990)), m.remove_entry(&99));
assert_eq!(Some(&980), m.get(&98));
m.assert_invariants();
}
#[test]
fn test_json() {
let mp = smallmap! {"a".to_owned() => 1, "b".to_owned() => 2};
let expected = serde_json::json!({
"a": 1,
"b": 2,
});
assert_eq!(serde_json::to_value(&mp).unwrap(), expected);
assert_eq!(
serde_json::from_value::<SmallMap<String, i32>>(expected).unwrap(),
mp
);
}
#[test]
fn test_reverse_small() {
let mut map = SmallMap::new();
map.insert("a".to_owned(), "b".to_owned());
map.insert("c".to_owned(), "d".to_owned());
map.reverse();
assert_eq!(Some("b"), map.get("a").map(|s| s.as_str()));
assert_eq!(Some("d"), map.get("c").map(|s| s.as_str()));
assert_eq!(
vec![
("c".to_owned(), "d".to_owned()),
("a".to_owned(), "b".to_owned())
],
map.into_iter().collect::<Vec<_>>()
);
}
#[test]
fn test_reverse_large() {
let mut map = SmallMap::new();
for i in 0..100 {
map.insert(i.to_string(), (i * 10).to_string());
}
let expected = map
.iter()
.rev()
.map(|(k, v)| (k.clone(), v.clone()))
.collect::<Vec<_>>();
map.reverse();
for i in 0..100 {
assert_eq!(Some(&(i * 10).to_string()), map.get(&i.to_string()));
}
assert_eq!(
expected,
map.iter()
.map(|(k, v)| (k.clone(), v.clone()))
.collect::<Vec<_>>()
);
}
}