use std::alloc::{handle_alloc_error, Alloc, Global, Layout, LayoutErr};
use std::collections::CollectionAllocErr;
use std::hash::{BuildHasher, Hash, Hasher};
use std::marker;
use std::mem;
use std::mem::{needs_drop, size_of};
use std::ops::{Deref, DerefMut};
use std::ptr::{self, NonNull, Unique};
use self::BucketState::*;
type HashUint = usize;
const EMPTY_BUCKET: HashUint = 0;
const EMPTY: usize = 1;
struct TaggedHashUintPtr(Unique<HashUint>);
impl TaggedHashUintPtr {
#[inline]
unsafe fn new(ptr: *mut HashUint) -> Self {
debug_assert!(ptr as usize & 1 == 0 || ptr as usize == EMPTY as usize);
TaggedHashUintPtr(Unique::new_unchecked(ptr))
}
#[inline]
fn set_tag(&mut self, value: bool) {
let mut usize_ptr = self.0.as_ptr() as usize;
unsafe {
if value {
usize_ptr |= 1;
} else {
usize_ptr &= !1;
}
self.0 = Unique::new_unchecked(usize_ptr as *mut HashUint)
}
}
#[inline]
fn tag(&self) -> bool {
(self.0.as_ptr() as usize) & 1 == 1
}
#[inline]
fn ptr(&self) -> *mut HashUint {
(self.0.as_ptr() as usize & !1) as *mut HashUint
}
}
pub struct RawTable<K, V> {
capacity_mask: usize,
size: usize,
hashes: TaggedHashUintPtr,
marker: marker::PhantomData<(K, V)>,
}
pub struct RawBucket<K, V> {
hash_start: *mut HashUint,
pair_start: *const (K, V),
idx: usize,
_marker: marker::PhantomData<(K, V)>,
}
impl<K, V> Copy for RawBucket<K, V> {}
impl<K, V> Clone for RawBucket<K, V> {
fn clone(&self) -> RawBucket<K, V> {
*self
}
}
pub struct Bucket<K, V, M> {
raw: RawBucket<K, V>,
table: M,
}
impl<K, V, M: Copy> Copy for Bucket<K, V, M> {}
impl<K, V, M: Copy> Clone for Bucket<K, V, M> {
fn clone(&self) -> Bucket<K, V, M> {
*self
}
}
pub struct EmptyBucket<K, V, M> {
raw: RawBucket<K, V>,
table: M,
}
pub struct FullBucket<K, V, M> {
raw: RawBucket<K, V>,
table: M,
}
pub type FullBucketMut<'table, K, V> = FullBucket<K, V, &'table mut RawTable<K, V>>;
pub enum BucketState<K, V, M> {
Empty(EmptyBucket<K, V, M>),
Full(FullBucket<K, V, M>),
}
pub struct GapThenFull<K, V, M> {
gap: EmptyBucket<K, V, ()>,
full: FullBucket<K, V, M>,
}
#[derive(PartialEq, Eq, Copy, Clone, PartialOrd, Ord)]
pub struct SafeHash {
hash: HashUint,
}
impl SafeHash {
#[inline(always)]
pub fn inspect(&self) -> HashUint {
self.hash
}
#[inline(always)]
fn new(hash: u64) -> Self {
let hash_bits = size_of::<HashUint>() * 8;
SafeHash {
hash: (1 << (hash_bits - 1)) | (hash as HashUint),
}
}
}
pub fn make_hash<T: ?Sized, S>(hash_state: &S, t: &T) -> SafeHash
where
T: Hash,
S: BuildHasher,
{
let mut state = hash_state.build_hasher();
t.hash(&mut state);
SafeHash::new(state.finish())
}
#[test]
fn can_alias_safehash_as_hash() {
assert_eq!(size_of::<SafeHash>(), size_of::<HashUint>())
}
impl<K, V> RawBucket<K, V> {
unsafe fn hash(&self) -> *mut HashUint {
self.hash_start.offset(self.idx as isize)
}
unsafe fn pair(&self) -> *mut (K, V) {
self.pair_start.offset(self.idx as isize) as *mut (K, V)
}
unsafe fn hash_pair(&self) -> (*mut HashUint, *mut (K, V)) {
(self.hash(), self.pair())
}
}
impl<K, V, M> FullBucket<K, V, M> {
pub fn table(&self) -> &M {
&self.table
}
pub fn table_mut(&mut self) -> &mut M {
&mut self.table
}
pub fn into_table(self) -> M {
self.table
}
pub fn index(&self) -> usize {
self.raw.idx
}
pub fn raw(&self) -> RawBucket<K, V> {
self.raw
}
}
impl<K, V, M> EmptyBucket<K, V, M> {
pub fn table(&self) -> &M {
&self.table
}
pub fn table_mut(&mut self) -> &mut M {
&mut self.table
}
}
impl<K, V, M> Bucket<K, V, M> {
pub fn index(&self) -> usize {
self.raw.idx
}
pub fn into_table(self) -> M {
self.table
}
}
impl<K, V, M> Deref for FullBucket<K, V, M>
where
M: Deref<Target = RawTable<K, V>>,
{
type Target = RawTable<K, V>;
fn deref(&self) -> &RawTable<K, V> {
&self.table
}
}
pub trait Put<K, V> {
unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V>;
}
impl<'t, K, V> Put<K, V> for &'t mut RawTable<K, V> {
unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
*self
}
}
impl<K, V, M> Put<K, V> for Bucket<K, V, M>
where
M: Put<K, V>,
{
unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
self.table.borrow_table_mut()
}
}
impl<K, V, M> Put<K, V> for FullBucket<K, V, M>
where
M: Put<K, V>,
{
unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
self.table.borrow_table_mut()
}
}
impl<K, V, M: Deref<Target = RawTable<K, V>>> Bucket<K, V, M> {
pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> {
Bucket::at_index(table, hash.inspect() as usize)
}
pub fn new_from(r: RawBucket<K, V>, t: M) -> Bucket<K, V, M> {
Bucket { raw: r, table: t }
}
pub fn at_index(table: M, ib_index: usize) -> Bucket<K, V, M> {
debug_assert!(
table.capacity() > 0,
"Table should have capacity at this point"
);
let ib_index = ib_index & table.capacity_mask;
Bucket {
raw: table.raw_bucket_at(ib_index),
table,
}
}
pub fn first(table: M) -> Bucket<K, V, M> {
Bucket {
raw: table.raw_bucket_at(0),
table,
}
}
pub fn head_bucket(table: M) -> Bucket<K, V, M> {
let mut bucket = Bucket::first(table);
loop {
bucket = match bucket.peek() {
Full(full) => {
if full.displacement() == 0 {
bucket = full.into_bucket();
break;
}
full.into_bucket()
}
Empty(b) => {
b.into_bucket()
}
};
bucket.next();
}
bucket
}
pub fn peek(self) -> BucketState<K, V, M> {
match unsafe { *self.raw.hash() } {
EMPTY_BUCKET => Empty(EmptyBucket {
raw: self.raw,
table: self.table,
}),
_ => Full(FullBucket {
raw: self.raw,
table: self.table,
}),
}
}
pub fn next(&mut self) {
self.raw.idx = self.raw.idx.wrapping_add(1) & self.table.capacity_mask;
}
pub fn prev(&mut self) {
self.raw.idx = self.raw.idx.wrapping_sub(1) & self.table.capacity_mask;
}
}
impl<K, V, M: Deref<Target = RawTable<K, V>>> EmptyBucket<K, V, M> {
#[inline]
pub fn next(self) -> Bucket<K, V, M> {
let mut bucket = self.into_bucket();
bucket.next();
bucket
}
#[inline]
pub fn into_bucket(self) -> Bucket<K, V, M> {
Bucket {
raw: self.raw,
table: self.table,
}
}
pub fn gap_peek(self) -> Result<GapThenFull<K, V, M>, Bucket<K, V, M>> {
let gap = EmptyBucket {
raw: self.raw,
table: (),
};
match self.next().peek() {
Full(bucket) => Ok(GapThenFull { gap, full: bucket }),
Empty(e) => Err(e.into_bucket()),
}
}
}
impl<K, V, M> EmptyBucket<K, V, M>
where
M: Put<K, V>,
{
pub fn put(mut self, hash: SafeHash, key: K, value: V) -> FullBucket<K, V, M> {
unsafe {
*self.raw.hash() = hash.inspect();
ptr::write(self.raw.pair(), (key, value));
self.table.borrow_table_mut().size += 1;
}
FullBucket {
raw: self.raw,
table: self.table,
}
}
}
impl<K, V, M: Deref<Target = RawTable<K, V>>> FullBucket<K, V, M> {
#[inline]
pub fn next(self) -> Bucket<K, V, M> {
let mut bucket = self.into_bucket();
bucket.next();
bucket
}
#[inline]
pub fn into_bucket(self) -> Bucket<K, V, M> {
Bucket {
raw: self.raw,
table: self.table,
}
}
pub fn stash(self) -> FullBucket<K, V, Self> {
FullBucket {
raw: self.raw,
table: self,
}
}
pub fn displacement(&self) -> usize {
(self.raw.idx.wrapping_sub(self.hash().inspect() as usize)) & self.table.capacity_mask
}
#[inline]
pub fn hash(&self) -> SafeHash {
unsafe {
SafeHash {
hash: *self.raw.hash(),
}
}
}
pub fn read(&self) -> (&K, &V) {
unsafe {
let pair_ptr = self.raw.pair();
(&(*pair_ptr).0, &(*pair_ptr).1)
}
}
}
impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
pub fn take(self) -> (EmptyBucket<K, V, &'t mut RawTable<K, V>>, K, V) {
self.table.size -= 1;
unsafe {
*self.raw.hash() = EMPTY_BUCKET;
let (k, v) = ptr::read(self.raw.pair());
(
EmptyBucket {
raw: self.raw,
table: self.table,
},
k,
v,
)
}
}
}
impl<K, V, M> FullBucket<K, V, M>
where
M: Put<K, V>,
{
pub fn replace(&mut self, h: SafeHash, k: K, v: V) -> (SafeHash, K, V) {
unsafe {
let old_hash = ptr::replace(self.raw.hash() as *mut SafeHash, h);
let (old_key, old_val) = ptr::replace(self.raw.pair(), (k, v));
(old_hash, old_key, old_val)
}
}
}
impl<K, V, M> FullBucket<K, V, M>
where
M: Deref<Target = RawTable<K, V>> + DerefMut,
{
pub fn read_mut(&mut self) -> (&mut K, &mut V) {
unsafe {
let pair_ptr = self.raw.pair();
(&mut (*pair_ptr).0, &mut (*pair_ptr).1)
}
}
}
impl<'t, K, V, M> FullBucket<K, V, M>
where
M: Deref<Target = RawTable<K, V>> + 't,
{
pub fn into_refs(self) -> (&'t K, &'t V) {
unsafe {
let pair_ptr = self.raw.pair();
(&(*pair_ptr).0, &(*pair_ptr).1)
}
}
}
impl<'t, K, V, M> FullBucket<K, V, M>
where
M: Deref<Target = RawTable<K, V>> + DerefMut + 't,
{
pub fn into_mut_refs(self) -> (&'t mut K, &'t mut V) {
unsafe {
let pair_ptr = self.raw.pair();
(&mut (*pair_ptr).0, &mut (*pair_ptr).1)
}
}
}
impl<K, V, M> GapThenFull<K, V, M>
where
M: Deref<Target = RawTable<K, V>>,
{
#[inline]
pub fn full(&self) -> &FullBucket<K, V, M> {
&self.full
}
pub fn into_table(self) -> M {
self.full.into_table()
}
pub fn shift(mut self) -> Result<GapThenFull<K, V, M>, Bucket<K, V, M>> {
unsafe {
let (gap_hash, gap_pair) = self.gap.raw.hash_pair();
let (full_hash, full_pair) = self.full.raw.hash_pair();
*gap_hash = mem::replace(&mut *full_hash, EMPTY_BUCKET);
ptr::copy_nonoverlapping(full_pair, gap_pair, 1);
}
let FullBucket { raw: prev_raw, .. } = self.full;
match self.full.next().peek() {
Full(bucket) => {
self.gap.raw = prev_raw;
self.full = bucket;
Ok(self)
}
Empty(b) => Err(b.into_bucket()),
}
}
}
fn calculate_layout<K, V>(capacity: usize) -> Result<(Layout, usize), LayoutErr> {
let hashes = Layout::array::<HashUint>(capacity)?;
let pairs = Layout::array::<(K, V)>(capacity)?;
hashes.extend(pairs)
}
pub(crate) enum Fallibility {
#[allow(unused)]
Fallible,
Infallible,
}
use self::Fallibility::*;
impl<K, V> RawTable<K, V> {
unsafe fn new_uninitialized_internal(
capacity: usize,
fallibility: Fallibility,
) -> Result<RawTable<K, V>, CollectionAllocErr> {
if capacity == 0 {
return Ok(RawTable {
size: 0,
capacity_mask: capacity.wrapping_sub(1),
hashes: TaggedHashUintPtr::new(EMPTY as *mut HashUint),
marker: marker::PhantomData,
});
}
let (layout, _) = calculate_layout::<K, V>(capacity)?;
let buffer = Global.alloc(layout).map_err(|e| match fallibility {
Infallible => handle_alloc_error(layout),
Fallible => e,
})?;
Ok(RawTable {
capacity_mask: capacity.wrapping_sub(1),
size: 0,
hashes: TaggedHashUintPtr::new(buffer.cast().as_ptr()),
marker: marker::PhantomData,
})
}
unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V> {
match Self::new_uninitialized_internal(capacity, Infallible) {
Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
Err(CollectionAllocErr::AllocErr) => unreachable!(),
Ok(table) => table,
}
}
fn raw_bucket_at(&self, index: usize) -> RawBucket<K, V> {
let (_, pairs_offset) = calculate_layout::<K, V>(self.capacity()).unwrap();
let buffer = self.hashes.ptr() as *mut u8;
unsafe {
RawBucket {
hash_start: buffer as *mut HashUint,
pair_start: buffer.add(pairs_offset) as *const (K, V),
idx: index,
_marker: marker::PhantomData,
}
}
}
fn new_internal(
capacity: usize,
fallibility: Fallibility,
) -> Result<RawTable<K, V>, CollectionAllocErr> {
unsafe {
let ret = RawTable::new_uninitialized_internal(capacity, fallibility)?;
if capacity > 0 {
ptr::write_bytes(ret.hashes.ptr(), 0, capacity);
}
Ok(ret)
}
}
#[allow(unused)]
pub fn try_new(capacity: usize) -> Result<RawTable<K, V>, CollectionAllocErr> {
Self::new_internal(capacity, Fallible)
}
pub fn new(capacity: usize) -> RawTable<K, V> {
match Self::new_internal(capacity, Infallible) {
Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
Err(CollectionAllocErr::AllocErr) => unreachable!(),
Ok(table) => table,
}
}
pub fn capacity(&self) -> usize {
self.capacity_mask.wrapping_add(1)
}
pub fn size(&self) -> usize {
self.size
}
fn raw_buckets(&self) -> RawBuckets<K, V> {
RawBuckets {
raw: self.raw_bucket_at(0),
elems_left: self.size,
marker: marker::PhantomData,
}
}
pub fn iter(&self) -> Iter<K, V> {
Iter {
iter: self.raw_buckets(),
}
}
pub fn iter_mut(&mut self) -> IterMut<K, V> {
IterMut {
iter: self.raw_buckets(),
_marker: marker::PhantomData,
}
}
pub fn into_iter(self) -> IntoIter<K, V> {
let RawBuckets {
raw, elems_left, ..
} = self.raw_buckets();
IntoIter {
iter: RawBuckets {
raw,
elems_left,
marker: marker::PhantomData,
},
table: self,
}
}
pub fn drain(&mut self) -> Drain<K, V> {
let RawBuckets {
raw, elems_left, ..
} = self.raw_buckets();
Drain {
iter: RawBuckets {
raw,
elems_left,
marker: marker::PhantomData,
},
table: NonNull::from(self),
marker: marker::PhantomData,
}
}
unsafe fn rev_drop_buckets(&mut self) {
let mut raw = self.raw_bucket_at(self.capacity());
let mut elems_left = self.size;
while elems_left != 0 {
raw.idx -= 1;
if *raw.hash() != EMPTY_BUCKET {
elems_left -= 1;
ptr::drop_in_place(raw.pair());
}
}
}
pub fn set_tag(&mut self, value: bool) {
self.hashes.set_tag(value)
}
pub fn tag(&self) -> bool {
self.hashes.tag()
}
}
struct RawBuckets<'a, K, V> {
raw: RawBucket<K, V>,
elems_left: usize,
marker: marker::PhantomData<&'a ()>,
}
impl<'a, K, V> Clone for RawBuckets<'a, K, V> {
fn clone(&self) -> RawBuckets<'a, K, V> {
RawBuckets {
raw: self.raw,
elems_left: self.elems_left,
marker: marker::PhantomData,
}
}
}
impl<'a, K, V> Iterator for RawBuckets<'a, K, V> {
type Item = RawBucket<K, V>;
fn next(&mut self) -> Option<RawBucket<K, V>> {
if self.elems_left == 0 {
return None;
}
loop {
unsafe {
let item = self.raw;
self.raw.idx += 1;
if *item.hash() != EMPTY_BUCKET {
self.elems_left -= 1;
return Some(item);
}
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.elems_left, Some(self.elems_left))
}
}
impl<'a, K, V> ExactSizeIterator for RawBuckets<'a, K, V> {
fn len(&self) -> usize {
self.elems_left
}
}
pub struct Iter<'a, K: 'a, V: 'a> {
iter: RawBuckets<'a, K, V>,
}
unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
impl<'a, K, V> Clone for Iter<'a, K, V> {
fn clone(&self) -> Iter<'a, K, V> {
Iter {
iter: self.iter.clone(),
}
}
}
pub struct IterMut<'a, K: 'a, V: 'a> {
iter: RawBuckets<'a, K, V>,
_marker: marker::PhantomData<&'a mut V>,
}
unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
impl<'a, K: 'a, V: 'a> IterMut<'a, K, V> {
pub fn iter(&self) -> Iter<K, V> {
Iter {
iter: self.iter.clone(),
}
}
}
pub struct IntoIter<K, V> {
table: RawTable<K, V>,
iter: RawBuckets<'static, K, V>,
}
unsafe impl<K: Sync, V: Sync> Sync for IntoIter<K, V> {}
unsafe impl<K: Send, V: Send> Send for IntoIter<K, V> {}
impl<K, V> IntoIter<K, V> {
pub fn iter(&self) -> Iter<K, V> {
Iter {
iter: self.iter.clone(),
}
}
}
pub struct Drain<'a, K: 'a, V: 'a> {
table: NonNull<RawTable<K, V>>,
iter: RawBuckets<'static, K, V>,
marker: marker::PhantomData<&'a RawTable<K, V>>,
}
unsafe impl<'a, K: Sync, V: Sync> Sync for Drain<'a, K, V> {}
unsafe impl<'a, K: Send, V: Send> Send for Drain<'a, K, V> {}
impl<'a, K, V> Drain<'a, K, V> {
pub fn iter(&self) -> Iter<K, V> {
Iter {
iter: self.iter.clone(),
}
}
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<(&'a K, &'a V)> {
self.iter.next().map(|raw| unsafe {
let pair_ptr = raw.pair();
(&(*pair_ptr).0, &(*pair_ptr).1)
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K, V> Iterator for IterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
self.iter.next().map(|raw| unsafe {
let pair_ptr = raw.pair();
(&(*pair_ptr).0, &mut (*pair_ptr).1)
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<K, V> Iterator for IntoIter<K, V> {
type Item = (SafeHash, K, V);
fn next(&mut self) -> Option<(SafeHash, K, V)> {
self.iter.next().map(|raw| {
self.table.size -= 1;
unsafe {
let (k, v) = ptr::read(raw.pair());
(SafeHash { hash: *raw.hash() }, k, v)
}
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<K, V> ExactSizeIterator for IntoIter<K, V> {
fn len(&self) -> usize {
self.iter().len()
}
}
impl<'a, K, V> Iterator for Drain<'a, K, V> {
type Item = (SafeHash, K, V);
#[inline]
fn next(&mut self) -> Option<(SafeHash, K, V)> {
self.iter.next().map(|raw| unsafe {
self.table.as_mut().size -= 1;
let (k, v) = ptr::read(raw.pair());
(
SafeHash {
hash: ptr::replace(&mut *raw.hash(), EMPTY_BUCKET),
},
k,
v,
)
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K: 'a, V: 'a> Drop for Drain<'a, K, V> {
fn drop(&mut self) {
self.for_each(drop);
}
}
impl<K: Clone, V: Clone> Clone for RawTable<K, V> {
fn clone(&self) -> RawTable<K, V> {
unsafe {
let cap = self.capacity();
let mut new_ht = RawTable::new_uninitialized(cap);
let mut new_buckets = new_ht.raw_bucket_at(0);
let mut buckets = self.raw_bucket_at(0);
while buckets.idx < cap {
*new_buckets.hash() = *buckets.hash();
if *new_buckets.hash() != EMPTY_BUCKET {
let pair_ptr = buckets.pair();
let kv = ((*pair_ptr).0.clone(), (*pair_ptr).1.clone());
ptr::write(new_buckets.pair(), kv);
}
buckets.idx += 1;
new_buckets.idx += 1;
}
new_ht.size = self.size();
new_ht.set_tag(self.tag());
new_ht
}
}
}
unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for RawTable<K, V> {
fn drop(&mut self) {
if self.capacity() == 0 {
return;
}
unsafe {
if needs_drop::<(K, V)>() {
self.rev_drop_buckets();
}
}
let (layout, _) = calculate_layout::<K, V>(self.capacity()).unwrap();
unsafe {
Global.dealloc(NonNull::new_unchecked(self.hashes.ptr()).cast(), layout);
}
}
}