#![cfg_attr(any(not(test), not(feature = "std")), no_std)]
#![cfg_attr(nightly, feature(test))]
#![cfg_attr(nightly, feature(never_type))]
#[cfg(all(nightly, test))] extern crate test;
extern crate alloc;
const MAX: usize = 256;
use alloc::vec;
use alloc::vec::Vec;
use core::borrow::Borrow;
pub mod iter;
use iter::*;
pub mod entry;
pub use entry::Entry;
pub mod space;
pub mod primitive;
pub use primitive::Primitive;
mod init;
mod private {
pub trait Sealed{}
}
pub type Set<T> = Map<T,()>;
#[macro_export ]macro_rules! smallmap {
() => {
$crate::Map::new()
};
($({$key:expr => $value:expr}),* $(,)?) => {
{
let mut map = $crate::Map::new();
$(
map.insert($key, $value);
)*
map
}
}
}
pub trait Collapse: Eq
{
fn collapse(&self) -> u8;
}
#[repr(transparent)]
pub struct Page<TKey,TValue>([Option<(TKey, TValue)>; MAX]);
mod page_impls;
impl<K,V> Page<K,V>
where K: Collapse
{
#[cfg(nightly)]
pub const fn new() -> Self
{
Self(init::blank_page())
}
#[cfg(not(nightly))]
pub fn new() -> Self
{
Self(init::blank_page())
}
pub fn len(&self) -> usize
{
self.0.iter().map(Option::as_ref).filter_map(core::convert::identity).count()
}
pub fn iter(&self) -> PageElements<'_, K,V>
{
PageElements(self.0.iter())
}
pub fn iter_mut(&mut self) -> PageElementsMut<'_, K,V>
{
PageElementsMut(self.0.iter_mut())
}
fn search<Q: ?Sized>(&self, key: &Q) -> &Option<(K,V)>
where Q: Collapse
{
&self.0[usize::from(key.collapse())]
}
fn search_mut<Q: ?Sized>(&mut self, key: &Q) -> &mut Option<(K,V)>
where Q: Collapse
{
&mut self.0[usize::from(key.collapse())]
}
fn replace(&mut self, k: K, v: V) -> Option<(K,V)>
{
core::mem::replace(&mut self.0[usize::from(k.collapse())], Some((k,v)))
}
}
impl<K: Collapse, V> core::iter::FromIterator<(K, V)> for Map<K,V>
{
fn from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self
{
let mut this = Self::new();
for (key, value) in iter.into_iter()
{
this.insert(key, value);
}
this
}
}
impl<K,V> IntoIterator for Page<K,V>
where K: Collapse
{
type Item= (K,V);
type IntoIter = IntoPageElements<K,V>;
fn into_iter(self) -> Self::IntoIter
{
IntoPageElements(self.0, 0)
}
}
impl<K,V> Default for Page<K,V>
where K: Collapse
{
#[inline]
fn default() -> Self
{
Self::new()
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Map<TKey, TValue>(Vec<Page<TKey,TValue>>);
#[cfg(feature = "serde")]
struct MapVisitor<TKey, TValue> {
_pd: core::marker::PhantomData<(TKey, TValue)>,
}
#[cfg(feature = "serde")]
impl<'de, TKey, TValue> serde::de::Deserialize<'de> for Map<TKey, TValue> where TKey: Collapse + serde::Deserialize<'de>, TValue: serde::Deserialize<'de> {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: serde::Deserializer<'de> {
deserializer.deserialize_map(MapVisitor { _pd: core::marker::PhantomData::default() })
}
}
#[cfg(feature = "serde")]
impl<'de, TKey, TValue> serde::de::Visitor<'de> for MapVisitor<TKey, TValue> where TKey: Collapse + serde::Deserialize<'de>, TValue: serde::Deserialize<'de> {
type Value = Map<TKey, TValue>;
fn expecting(&self, formatter: &mut core::fmt::Formatter) -> core::fmt::Result {
formatter.write_str("A map")
}
fn visit_map<A>(self, mut access: A) -> Result<Self::Value, A::Error> where A: serde::de::MapAccess<'de> {
let mut map = Map::with_capacity(access.size_hint().unwrap_or(1));
while let Some((key, value)) = access.next_entry()? {
map.insert(key, value);
}
Ok(map)
}
}
#[cfg(feature = "serde")]
impl<TKey, TValue> serde::Serialize for Map<TKey, TValue> where TKey: Collapse + serde::Serialize, TValue: serde::Serialize {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: serde::Serializer {
let mut m = serializer.serialize_map(Some(self.len()))?;
for (k, v) in self.iter() {
m.serialize_entry(k, v)?;
}
m.end()
}
}
impl<K,V> Map<K,V>
{
#[inline(always)]
#[allow(dead_code)] pub(crate) fn internal_size_bytes(&self) -> usize
{
self.0.capacity() * core::mem::size_of::<Page<K,V>>()
}
}
impl<K,V> Map<K,V>
where K: Collapse
{
fn new_page(&mut self) -> &mut Page<K,V>
{
let len = self.0.len();
self.0.push(Page::new());
&mut self.0[len]
}
#[inline(always)] fn fuck_entry(&mut self, key: K) -> Option<Entry<'_, K, V>>
{
for page in self.0.iter_mut()
{
let re = page.search_mut(&key);
match re {
Some((ref ok, _)) if key.eq(ok.borrow()) => {
return Some(Entry::Occupied(entry::OccupiedEntry(re)));
},
None => {
return Some(Entry::Vacant(entry::VacantEntry(re, key)));
},
_ => (),
}
}
None
}
pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
{
if let None = self.0.iter()
.filter(|x| x.search(&key).as_ref().and_then(|(k, v)| if k==&key {None} else {Some((k,v))}).is_none())
.next() {
self.new_page();
}
self.fuck_entry(key).unwrap()
}
pub fn clean(&mut self)
{
self.0.retain(|x| x.len() >= 1);
}
pub fn len(&self) -> usize
{
self.pages().map(Page::len).sum()
}
pub fn is_empty(&self) -> bool
{
self.0[0].iter().next().is_none()
}
pub fn num_pages(&self) -> usize
{
self.0.len()
}
pub fn into_pages(self) -> Vec<Page<K,V>>
{
self.0
}
pub fn pages(&self) -> Pages<'_, K, V>
{
iter::Pages(self.0.iter())
}
pub fn pages_mut(&mut self) -> PagesMut<'_, K, V>
{
iter::PagesMut(self.0.iter_mut())
}
pub fn iter(&self) -> Iter<'_, K, V>
{
Iter(None, self.pages())
}
pub fn keys(&self) -> impl Iterator<Item = &K> {
self.iter().map(|(k, _)| k)
}
pub fn values(&self) -> impl Iterator<Item = &V> {
self.iter().map(|(_, v)| v)
}
pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
self.iter_mut().map(|(_, v)| v)
}
pub fn iter_mut(&mut self) -> IterMut<'_, K, V>
{
IterMut(None, self.pages_mut())
}
pub fn new() -> Self
{
Self(vec![Page::new()])
}
pub fn with_capacity(pages: usize) -> Self
{
#[cold] fn cap_too_low() -> !
{
panic!("Got 0 capacity, this is invalid.")
}
if pages == 0 {
cap_too_low()
}
let mut p = Vec::with_capacity(pages);
p.push(Page::new());
Self(p)
}
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where K: Borrow<Q>,
Q: Collapse + Eq
{
for page in self.0.iter_mut()
{
match page.search_mut(key) {
Some((ref ok, ov)) if key.eq(ok.borrow()) => {
return Some(ov);
},
_ => (),
}
}
None
}
#[inline] pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
where K: Borrow<Q>,
Q: Collapse + Eq
{
self.get(key).is_some()
}
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where K: Borrow<Q>,
Q: Collapse + Eq
{
for page in self.0.iter()
{
match page.search(key) {
Some((ref ok, ov)) if key.eq(ok.borrow()) => {
return Some(ov);
},
_ => (),
}
}
None
}
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
where K: Borrow<Q>,
Q: Collapse + Eq
{
for page in self.0.iter_mut()
{
let v = page.search_mut(key);
match v {
Some((ref ok, _)) if key.eq(ok.borrow()) => {
return v.take().map(|(_, v)| v);
},
_ => (),
}
}
None
}
pub fn insert(&mut self, key: K, value: V) -> Option<V>
{
for page in self.0.iter_mut()
{
match page.search_mut(&key) {
Some((ref ok, ov)) if ok.eq(&key) => {
return Some(core::mem::replace(ov, value));
},
empty @ None => {
return empty.replace((key, value))
.map(|(_, v)| v);
},
_ => (),
}
}
let mut page = Page::new();
page.replace(key, value);
self.0.push(page);
None
}
pub fn reverse(self) -> Map<V,K>
where V: Collapse
{
let mut output = Map::with_capacity(self.num_pages());
for (k,v) in self.into_iter()
{
output.insert(v, k);
}
output
}
}
impl<K: Collapse, V> Default for Map<K,V>
{
#[inline]
fn default() -> Self
{
Self::new()
}
}
impl<K: Collapse, V> IntoIterator for Map<K,V>
{
type Item= (K,V);
type IntoIter = IntoIter<K,V>;
fn into_iter(self) -> Self::IntoIter
{
IntoIter(None, self.0.into_iter())
}
}
impl<K: Collapse, V> core::iter::Extend<(K,V)> for Map<K,V>
{
fn extend<T: IntoIterator<Item = (K,V)>>(&mut self, iter: T) {
for (key, value) in iter.into_iter()
{
self.insert(key,value);
}
}
}
use core::hash::{Hash, Hasher,};
use core::ops::{Index, IndexMut};
#[cfg(feature = "serde")]
use serde::ser::SerializeMap;
impl<T: ?Sized + Hash + Eq> Collapse for T
{
fn collapse(&self) -> u8 {
struct CollapseHasher(u8);
macro_rules! hash_type {
($nm:ident, u8) => {
#[inline(always)] fn $nm(&mut self, i: u8)
{
self.0 ^= i;
}
};
($nm:ident, i8) => {
#[inline(always)] fn $nm(&mut self, i: i8)
{
self.0 ^= i as u8;
}
};
($nm:ident, $ty:tt) => {
#[inline] fn $nm(&mut self, i: $ty)
{
self.0 ^= (i % MAX as $ty) as u8;
}
};
}
impl Hasher for CollapseHasher
{
#[inline] fn finish(&self) -> u64
{
self.0 as u64
}
#[inline] fn write(&mut self, buffer: &[u8])
{
self.0 ^= collapse(buffer);
}
hash_type!(write_u8, u8);
hash_type!(write_i8, i8);
hash_type!(write_i16, i16);
hash_type!(write_u16, u16);
hash_type!(write_i32, i32);
hash_type!(write_u32, u32);
hash_type!(write_i64, i64);
hash_type!(write_u64, u64);
hash_type!(write_u128, u128);
hash_type!(write_isize, isize);
hash_type!(write_usize, usize);
}
let mut h = CollapseHasher(0);
self.hash(&mut h);
h.0
}
}
impl<K, Q, V> Index<&Q> for Map<K, V>
where
K: Collapse + Borrow<Q>,
Q: ?Sized + Collapse + Eq,
{
type Output = V;
fn index(&self, key: &Q) -> &Self::Output {
self.get(key).expect("Key not found")
}
}
impl<K, Q, V> IndexMut<&Q> for Map<K, V>
where
K: Collapse + Borrow<Q>,
Q: ?Sized + Collapse + Eq,
{
fn index_mut(&mut self, key: &Q) -> &mut Self::Output {
self.get_mut(key).expect("Key not found")
}
}
#[cfg(test)]
mod tests;
#[inline] pub fn collapse<T: AsRef<[u8]>>(bytes: T) -> u8
{
bytes.as_ref().iter().copied().fold(0, |a, b| a ^ b)
}
#[inline] pub fn collapse_iter<T: IntoIterator<Item=u8>>(bytes: T) -> u8
{
bytes.into_iter().fold(0, |a, b| a ^ b)
}