pub mod user;
use std::hash::Hasher;
pub trait HashMap<Entry, Key, Val, Cid, Umeta, BuildHasher>
where
Entry: user::EntryT<Key, Val, Cid, Umeta>,
Key: user::Hash,
Val: user::Val,
Cid: user::Cid,
Umeta: user::Meta<Val>,
BuildHasher: ::std::hash::BuildHasher,
{
fn with_capacity(capacity: usize) -> Self;
fn with_capacity_and_hasher(
capacity: usize,
hash_builder: BuildHasher,
) -> Self;
fn capacity(&self) -> usize;
fn len(&self) -> usize;
fn get_full(&self, key: &Key) -> Option<(usize, &Entry)>;
fn get_full_mut(&mut self, key: &Key) -> Option<(usize, &mut Entry)>;
fn get_index(&self, idx: usize) -> Option<&Entry>;
fn get_index_mut(&mut self, idx: usize) -> Option<&mut Entry>;
unsafe fn index_from_entry(&self, e: &Entry) -> usize;
fn remove(&mut self, item: &Entry) -> Entry;
fn remove_idx(&mut self, idx: usize) -> Entry;
fn clear(&mut self);
fn insert(&mut self, entry: Entry) -> (Option<Entry>, usize, &Entry);
fn insert_mut(
&mut self,
entry: Entry,
) -> (Option<Entry>, usize, &mut Entry);
fn hasher(&self) -> &BuildHasher;
}
pub struct SimpleHmap<
Entry,
Key,
Val,
Cid,
Umeta,
BuildHasher = std::collections::hash_map::RandomState,
> where
Entry: user::EntryT<Key, Val, Cid, Umeta>,
Key: user::Hash,
Val: user::Val,
Cid: user::Cid,
Umeta: user::Meta<Val>,
BuildHasher: ::std::hash::BuildHasher + Default,
{
usage: usize,
table: ::hashbrown::raw::RawTable<Entry>,
hash_builder: BuildHasher,
_k: ::std::marker::PhantomData<Key>,
_v: ::std::marker::PhantomData<Val>,
_c: ::std::marker::PhantomData<Cid>,
_u: ::std::marker::PhantomData<Umeta>,
}
impl<Entry, Key, Val, Cid, Umeta, BuildHasher>
SimpleHmap<Entry, Key, Val, Cid, Umeta, BuildHasher>
where
Entry: user::EntryT<Key, Val, Cid, Umeta>,
Key: user::Hash,
Val: user::Val,
Cid: user::Cid,
Umeta: user::Meta<Val>,
BuildHasher: ::std::hash::BuildHasher + Default,
{
pub fn with_capacity(capacity: usize) -> Self {
let mut res = SimpleHmap {
usage: 0,
table: ::hashbrown::raw::RawTable::<Entry>::with_capacity(capacity),
hash_builder: BuildHasher::default(),
_k: ::std::marker::PhantomData,
_v: ::std::marker::PhantomData,
_c: ::std::marker::PhantomData,
_u: ::std::marker::PhantomData,
};
res.init_all_default(false);
res
}
pub fn with_capacity_and_hasher(
capacity: usize,
hash_builder: BuildHasher,
) -> Self {
let mut res = SimpleHmap {
usage: 0,
table: ::hashbrown::raw::RawTable::<Entry>::with_capacity(capacity),
hash_builder: hash_builder,
_k: ::std::marker::PhantomData,
_v: ::std::marker::PhantomData,
_c: ::std::marker::PhantomData,
_u: ::std::marker::PhantomData,
};
res.init_all_default(false);
res
}
fn init_all_default(&mut self, quick: bool) {
match quick {
false => {
for idx in 0..(self.table.len()) {
unsafe {
let bucket = self.table.bucket(idx);
let default_el = Entry::default();
bucket.write(default_el);
}
}
}
true => {
for idx in 0..(self.table.len()) {
unsafe {
let bucket = self.table.bucket(idx);
let cid = bucket.as_mut().get_cache_id_mut();
*cid = Cid::default();
}
}
}
}
self.usage = 0;
}
pub fn capacity(&self) -> usize {
self.table.capacity()
}
pub fn len(&self) -> usize {
self.usage
}
fn hash(&self, key: &Key) -> u64 {
let mut hasher = self.hash_builder.build_hasher();
key.hash(&mut hasher);
hasher.finish()
}
pub fn get_full(&self, key: &Key) -> Option<(usize, &Entry)> {
let hash = self.hash(key);
match self.table.find(hash, move |x| key.eq(x.get_key())) {
None => None,
Some(bucket) => {
Some((unsafe { self.table.bucket_index(&bucket) }, unsafe {
bucket.as_ref()
}))
}
}
}
pub fn get_full_mut(&mut self, key: &Key) -> Option<(usize, &mut Entry)> {
let hash = self.hash(key);
match self.table.find(hash, move |x| key.eq(x.get_key())) {
None => None,
Some(bucket) => {
Some((unsafe { self.table.bucket_index(&bucket) }, unsafe {
bucket.as_mut()
}))
}
}
}
pub fn get_index(&self, idx: usize) -> Option<&Entry> {
if idx >= self.len() {
return None;
}
let bucket = unsafe { self.table.bucket(idx) };
if unsafe { bucket.as_ref() }.get_cache_id() == Cid::default() {
return None;
}
Some(unsafe { bucket.as_ref() })
}
pub fn get_index_mut(&mut self, idx: usize) -> Option<&mut Entry> {
if idx >= self.len() {
return None;
}
let bucket = unsafe { self.table.bucket(idx) };
if unsafe { bucket.as_ref() }.get_cache_id() == Cid::default() {
return None;
}
Some(unsafe { bucket.as_mut() })
}
unsafe fn index_from_entry(&self, e: &Entry) -> usize {
self.entry_to_idx(e)
}
fn entry_to_idx(&self, e: &Entry) -> usize {
unsafe {
let ep = e as *const Entry;
let end = self.table.data_end();
end.as_ptr().offset_from(ep) as usize
}
}
pub fn remove(&mut self, item: &Entry) -> Entry {
let idx = self.entry_to_idx(item);
self.remove_idx_unsafe(idx)
}
pub fn remove_idx(&mut self, idx: usize) -> Entry {
if idx >= self.capacity() {
return Entry::default();
}
self.remove_idx_unsafe(idx)
}
fn remove_idx_unsafe(&mut self, idx: usize) -> Entry {
unsafe {
let bucket = self.table.bucket(idx);
if bucket.as_ref().get_cache_id() == Cid::default() {
return Entry::default();
}
self.usage -= 1;
let res: Entry = bucket.read();
let old_e_cid = bucket.as_mut().get_cache_id_mut();
*old_e_cid = Cid::default();
res
}
}
pub fn clear(&mut self) {
self.init_all_default(true)
}
pub fn insert(&mut self, entry: Entry) -> (Option<Entry>, usize, &Entry) {
let (clash, idx, entry) = self.insert_mut(entry);
(clash, idx, entry)
}
pub fn insert_mut(
&mut self,
entry: Entry,
) -> (Option<Entry>, usize, &mut Entry) {
self.usage += 1;
let hash = self.hash(entry.get_key());
let non_mut_self = &*self;
let opt_clash_strong = self.table.find(hash, move |x| {
if (&x).get_cache_id() == Cid::default() {
return true;
}
let k = x.get_key();
let h2 = non_mut_self.hash(k);
hash.eq(&h2)
});
let opt_clash_real =
if opt_clash_strong.is_none() && (self.usage == self.capacity()) {
let weak_hash = hash % (self.capacity() as u64);
self.table.find(weak_hash, move |x| {
if (&x).get_cache_id() == Cid::default() {
return true;
}
let k = x.get_key();
let h2 =
non_mut_self.hash(k) % (non_mut_self.capacity() as u64);
weak_hash.eq(&h2)
})
} else {
opt_clash_strong
};
let (opt_clash_copy, bucket) = match opt_clash_real {
None => {
let bucket = self.table.insert_no_grow(hash, entry);
let bucket_idx = unsafe { self.table.bucket_index(&bucket) };
return (None, bucket_idx, unsafe { bucket.as_mut() });
}
Some(bucket) => {
let old_element = if unsafe { bucket.as_ref() }.get_cache_id()
== Cid::default()
{
None
} else {
Some(unsafe { bucket.read() })
};
(old_element, bucket)
}
};
unsafe {
bucket.write(entry);
}
let bucket_idx = unsafe { self.table.bucket_index(&bucket) };
(opt_clash_copy, bucket_idx, unsafe { bucket.as_mut() })
}
pub fn hasher(&self) -> &BuildHasher {
&self.hash_builder
}
}
impl<Entry, Key, Val, Cid, Umeta, BuildHasher>
HashMap<Entry, Key, Val, Cid, Umeta, BuildHasher>
for SimpleHmap<Entry, Key, Val, Cid, Umeta, BuildHasher>
where
Entry: user::EntryT<Key, Val, Cid, Umeta>,
Key: user::Hash,
Val: user::Val,
Cid: user::Cid,
Umeta: user::Meta<Val>,
BuildHasher: ::std::hash::BuildHasher + Default,
{
fn with_capacity(capacity: usize) -> Self {
SimpleHmap::with_capacity(capacity)
}
fn with_capacity_and_hasher(
capacity: usize,
hash_builder: BuildHasher,
) -> Self {
SimpleHmap::with_capacity_and_hasher(capacity, hash_builder)
}
fn capacity(&self) -> usize {
SimpleHmap::capacity(self)
}
fn len(&self) -> usize {
SimpleHmap::len(self)
}
fn get_full(&self, key: &Key) -> Option<(usize, &Entry)> {
SimpleHmap::get_full(self, key)
}
fn get_full_mut(&mut self, key: &Key) -> Option<(usize, &mut Entry)> {
SimpleHmap::get_full_mut(self, key)
}
fn get_index(&self, idx: usize) -> Option<&Entry> {
SimpleHmap::get_index(self, idx)
}
fn get_index_mut(&mut self, idx: usize) -> Option<&mut Entry> {
SimpleHmap::get_index_mut(self, idx)
}
unsafe fn index_from_entry(&self, e: &Entry) -> usize {
SimpleHmap::index_from_entry(self, e)
}
fn remove(&mut self, item: &Entry) -> Entry {
SimpleHmap::remove(self, item)
}
fn remove_idx(&mut self, idx: usize) -> Entry {
SimpleHmap::remove_idx(self, idx)
}
fn clear(&mut self) {
SimpleHmap::clear(self)
}
fn insert(&mut self, entry: Entry) -> (Option<Entry>, usize, &Entry) {
SimpleHmap::insert(self, entry)
}
fn insert_mut(
&mut self,
entry: Entry,
) -> (Option<Entry>, usize, &mut Entry) {
SimpleHmap::insert_mut(self, entry)
}
fn hasher(&self) -> &BuildHasher {
SimpleHmap::hasher(self)
}
}