#![cfg_attr(nightly, feature(test))]
#![cfg_attr(nightly, feature(drain_filter))]
#![cfg_attr(nightly, feature(const_fn))]
#[cfg(nightly)] extern crate test;
const MAX: usize = 256;
use std::borrow::Borrow;
pub mod iter;
use iter::*;
pub mod entry;
pub use entry::Entry;
mod init;
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(std::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)>
{
std::mem::replace(&mut self.0[usize::from(k.collapse())], Some((k,v)))
}
}
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, Default)]
pub struct Map<TKey, TValue>(Vec<Page<TKey,TValue>>);
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)
{
#[cfg(nightly)]
self.0.drain_filter(|x| x.len() <1);
#[cfg(not(nightly))]
{
let mut i = 0;
while i != self.0.len() {
if self.0[i].len() <1 {
self.0.remove(i);
} else {
i += 1;
}
}
}
}
pub fn len(&self) -> usize
{
self.pages().map(Page::len).sum()
}
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 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
{
if pages == 0 {
panic!("Got 0 capacity, this is invalid.");
}
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(std::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
}
}
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())
}
}
use std::hash::{Hash, Hasher,};
impl<T: 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
}
}
#[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)
}