use crate::alloc::alloc::{alloc, dealloc, handle_alloc_error};
use crate::scopeguard::guard;
use crate::CollectionAllocErr;
use core::alloc::Layout;
use core::hint;
use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem;
use core::mem::ManuallyDrop;
use core::ptr::NonNull;
cfg_if! {
if #[cfg(all(
target_feature = "sse2",
any(target_arch = "x86", target_arch = "x86_64"),
not(miri)
))] {
mod sse2;
use sse2 as imp;
} else {
#[path = "generic.rs"]
mod generic;
use generic as imp;
}
}
mod bitmask;
use self::bitmask::BitMask;
use self::imp::Group;
#[cfg(feature = "nightly")]
use core::intrinsics::{likely, unlikely};
#[cfg(not(feature = "nightly"))]
#[inline]
fn likely(b: bool) -> bool {
b
}
#[cfg(not(feature = "nightly"))]
#[inline]
fn unlikely(b: bool) -> bool {
b
}
#[cfg(feature = "nightly")]
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
to.offset_from(from) as usize
}
#[cfg(not(feature = "nightly"))]
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
(to as usize - from as usize) / mem::size_of::<T>()
}
#[derive(Copy, Clone)]
enum Fallibility {
Fallible,
Infallible,
}
impl Fallibility {
#[cfg_attr(feature = "inline-more", inline)]
fn capacity_overflow(self) -> CollectionAllocErr {
use Fallibility::*;
match self {
Fallible => CollectionAllocErr::CapacityOverflow,
Infallible => panic!("Hash table capacity overflow"),
}
}
#[cfg_attr(feature = "inline-more", inline)]
fn alloc_err(self, layout: Layout) -> CollectionAllocErr {
use Fallibility::*;
match self {
Fallible => CollectionAllocErr::AllocErr { layout },
Infallible => handle_alloc_error(layout),
}
}
}
const EMPTY: u8 = 0b1111_1111;
const DELETED: u8 = 0b1000_0000;
#[inline]
fn is_full(ctrl: u8) -> bool {
ctrl & 0x80 == 0
}
#[inline]
fn is_special(ctrl: u8) -> bool {
ctrl & 0x80 != 0
}
#[inline]
fn special_is_empty(ctrl: u8) -> bool {
debug_assert!(is_special(ctrl));
ctrl & 0x01 != 0
}
#[inline]
#[allow(clippy::cast_possible_truncation)]
fn h1(hash: u64) -> usize {
hash as usize
}
#[inline]
#[allow(clippy::cast_possible_truncation)]
fn h2(hash: u64) -> u8 {
let hash_len = usize::min(mem::size_of::<usize>(), mem::size_of::<u64>());
let top7 = hash >> (hash_len * 8 - 7);
(top7 & 0x7f) as u8
}
struct ProbeSeq {
bucket_mask: usize,
pos: usize,
stride: usize,
}
impl Iterator for ProbeSeq {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
debug_assert!(
self.stride <= self.bucket_mask,
"Went past end of probe sequence"
);
let result = self.pos;
self.stride += Group::WIDTH;
self.pos += self.stride;
self.pos &= self.bucket_mask;
Some(result)
}
}
#[cfg_attr(feature = "inline-more", inline)]
#[cfg_attr(target_os = "emscripten", inline(never))]
fn capacity_to_buckets(cap: usize) -> Option<usize> {
let adjusted_cap = if cap < 8 {
cap + 1
} else {
cap.checked_mul(8)? / 7
};
Some(adjusted_cap.next_power_of_two())
}
#[cfg_attr(feature = "inline-more", inline)]
fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {
if bucket_mask < 8 {
bucket_mask
} else {
((bucket_mask + 1) / 8) * 7
}
}
#[cfg_attr(feature = "inline-more", inline)]
#[cfg(feature = "nightly")]
fn calculate_layout<T>(buckets: usize) -> Option<(Layout, usize)> {
debug_assert!(buckets.is_power_of_two());
let data = Layout::array::<T>(buckets).ok()?;
let ctrl = unsafe { Layout::from_size_align_unchecked(buckets + Group::WIDTH, Group::WIDTH) };
ctrl.extend(data).ok()
}
#[cfg_attr(feature = "inline-more", inline)]
#[cfg(not(feature = "nightly"))]
fn calculate_layout<T>(buckets: usize) -> Option<(Layout, usize)> {
debug_assert!(buckets.is_power_of_two());
let data_align = usize::max(mem::align_of::<T>(), Group::WIDTH);
let data_offset = (buckets + Group::WIDTH).checked_add(data_align - 1)? & !(data_align - 1);
let len = data_offset.checked_add(mem::size_of::<T>().checked_mul(buckets)?)?;
Some((
unsafe { Layout::from_size_align_unchecked(len, data_align) },
data_offset,
))
}
pub struct Bucket<T> {
ptr: *const T,
}
unsafe impl<T> Send for Bucket<T> {}
impl<T> Clone for Bucket<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Self { ptr: self.ptr }
}
}
impl<T> Bucket<T> {
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn from_base_index(base: *const T, index: usize) -> Self {
let ptr = if mem::size_of::<T>() == 0 {
index as *const T
} else {
base.add(index)
};
Self { ptr }
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn as_ptr(&self) -> *mut T {
if mem::size_of::<T>() == 0 {
mem::align_of::<T>() as *mut T
} else {
self.ptr as *mut T
}
}
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn add(&self, offset: usize) -> Self {
let ptr = if mem::size_of::<T>() == 0 {
(self.ptr as usize + offset) as *const T
} else {
self.ptr.add(offset)
};
Self { ptr }
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn drop(&self) {
self.as_ptr().drop_in_place();
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn read(&self) -> T {
self.as_ptr().read()
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn write(&self, val: T) {
self.as_ptr().write(val);
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn as_ref<'a>(&self) -> &'a T {
&*self.as_ptr()
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn as_mut<'a>(&self) -> &'a mut T {
&mut *self.as_ptr()
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn copy_from_nonoverlapping(&self, other: &Self) {
self.as_ptr().copy_from_nonoverlapping(other.as_ptr(), 1);
}
}
pub struct RawTable<T> {
bucket_mask: usize,
ctrl: NonNull<u8>,
data: NonNull<T>,
growth_left: usize,
items: usize,
marker: PhantomData<T>,
}
impl<T> RawTable<T> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn new() -> Self {
Self {
data: NonNull::dangling(),
ctrl: unsafe { NonNull::new_unchecked(Group::static_empty().as_ptr() as *mut u8) },
bucket_mask: 0,
items: 0,
growth_left: 0,
marker: PhantomData,
}
}
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn new_uninitialized(
buckets: usize,
fallability: Fallibility,
) -> Result<Self, CollectionAllocErr> {
debug_assert!(buckets.is_power_of_two());
let (layout, data_offset) =
calculate_layout::<T>(buckets).ok_or_else(|| fallability.capacity_overflow())?;
let ctrl = NonNull::new(alloc(layout)).ok_or_else(|| fallability.alloc_err(layout))?;
let data = NonNull::new_unchecked(ctrl.as_ptr().add(data_offset) as *mut T);
Ok(Self {
data,
ctrl,
bucket_mask: buckets - 1,
items: 0,
growth_left: bucket_mask_to_capacity(buckets - 1),
marker: PhantomData,
})
}
fn try_with_capacity(
capacity: usize,
fallability: Fallibility,
) -> Result<Self, CollectionAllocErr> {
if capacity == 0 {
Ok(Self::new())
} else {
unsafe {
let buckets =
capacity_to_buckets(capacity).ok_or_else(|| fallability.capacity_overflow())?;
let result = Self::new_uninitialized(buckets, fallability)?;
result.ctrl(0).write_bytes(EMPTY, result.num_ctrl_bytes());
Ok(result)
}
}
}
pub fn with_capacity(capacity: usize) -> Self {
Self::try_with_capacity(capacity, Fallibility::Infallible)
.unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() })
}
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn free_buckets(&mut self) {
let (layout, _) =
calculate_layout::<T>(self.buckets()).unwrap_or_else(|| hint::unreachable_unchecked());
dealloc(self.ctrl.as_ptr(), layout);
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize {
if mem::size_of::<T>() == 0 {
bucket.ptr as usize
} else {
offset_from(bucket.ptr, self.data.as_ptr())
}
}
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn ctrl(&self, index: usize) -> *mut u8 {
debug_assert!(index < self.num_ctrl_bytes());
self.ctrl.as_ptr().add(index)
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn bucket(&self, index: usize) -> Bucket<T> {
debug_assert_ne!(self.bucket_mask, 0);
debug_assert!(index < self.buckets());
Bucket::from_base_index(self.data.as_ptr(), index)
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn erase_no_drop(&mut self, item: &Bucket<T>) {
let index = self.bucket_index(item);
debug_assert!(is_full(*self.ctrl(index)));
let index_before = index.wrapping_sub(Group::WIDTH) & self.bucket_mask;
let empty_before = Group::load(self.ctrl(index_before)).match_empty();
let empty_after = Group::load(self.ctrl(index)).match_empty();
let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH {
DELETED
} else {
self.growth_left += 1;
EMPTY
};
self.set_ctrl(index, ctrl);
self.items -= 1;
}
#[cfg_attr(feature = "inline-more", inline)]
fn probe_seq(&self, hash: u64) -> ProbeSeq {
ProbeSeq {
bucket_mask: self.bucket_mask,
pos: h1(hash) & self.bucket_mask,
stride: 0,
}
}
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn set_ctrl(&self, index: usize, ctrl: u8) {
let index2 = ((index.wrapping_sub(Group::WIDTH)) & self.bucket_mask) + Group::WIDTH;
*self.ctrl(index) = ctrl;
*self.ctrl(index2) = ctrl;
}
#[cfg_attr(feature = "inline-more", inline)]
fn find_insert_slot(&self, hash: u64) -> usize {
for pos in self.probe_seq(hash) {
unsafe {
let group = Group::load(self.ctrl(pos));
if let Some(bit) = group.match_empty_or_deleted().lowest_set_bit() {
let result = (pos + bit) & self.bucket_mask;
if unlikely(is_full(*self.ctrl(result))) {
debug_assert!(self.bucket_mask < Group::WIDTH);
debug_assert_ne!(pos, 0);
return Group::load_aligned(self.ctrl(0))
.match_empty_or_deleted()
.lowest_set_bit_nonzero();
} else {
return result;
}
}
}
}
unreachable!();
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear_no_drop(&mut self) {
if !self.is_empty_singleton() {
unsafe {
self.ctrl(0).write_bytes(EMPTY, self.num_ctrl_bytes());
}
}
self.items = 0;
self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear(&mut self) {
let self_ = guard(self, |self_| self_.clear_no_drop());
if mem::needs_drop::<T>() {
unsafe {
for item in self_.iter() {
item.drop();
}
}
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn shrink_to(&mut self, min_size: usize, hasher: impl Fn(&T) -> u64) {
let min_size = usize::max(self.items, min_size);
if min_size == 0 {
*self = Self::new();
return;
}
let min_buckets = match capacity_to_buckets(min_size) {
Some(buckets) => buckets,
None => return,
};
if min_buckets < self.buckets() {
if self.items == 0 {
*self = Self::with_capacity(min_size)
} else {
self.resize(min_size, hasher, Fallibility::Infallible)
.unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() });
}
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64) {
if additional > self.growth_left {
self.reserve_rehash(additional, hasher, Fallibility::Infallible)
.unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() });
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn try_reserve(
&mut self,
additional: usize,
hasher: impl Fn(&T) -> u64,
) -> Result<(), CollectionAllocErr> {
if additional > self.growth_left {
self.reserve_rehash(additional, hasher, Fallibility::Fallible)
} else {
Ok(())
}
}
#[cold]
#[inline(never)]
fn reserve_rehash(
&mut self,
additional: usize,
hasher: impl Fn(&T) -> u64,
fallability: Fallibility,
) -> Result<(), CollectionAllocErr> {
let new_items = self
.items
.checked_add(additional)
.ok_or_else(|| fallability.capacity_overflow())?;
let full_capacity = bucket_mask_to_capacity(self.bucket_mask);
if new_items <= full_capacity / 2 {
self.rehash_in_place(hasher);
Ok(())
} else {
self.resize(
usize::max(new_items, full_capacity + 1),
hasher,
fallability,
)
}
}
fn rehash_in_place(&mut self, hasher: impl Fn(&T) -> u64) {
unsafe {
for i in (0..self.buckets()).step_by(Group::WIDTH) {
let group = Group::load_aligned(self.ctrl(i));
let group = group.convert_special_to_empty_and_full_to_deleted();
group.store_aligned(self.ctrl(i));
}
if self.buckets() < Group::WIDTH {
self.ctrl(0)
.copy_to(self.ctrl(Group::WIDTH), self.buckets());
} else {
self.ctrl(0)
.copy_to(self.ctrl(self.buckets()), Group::WIDTH);
}
let mut guard = guard(self, |self_| {
if mem::needs_drop::<T>() {
for i in 0..self_.buckets() {
if *self_.ctrl(i) == DELETED {
self_.set_ctrl(i, EMPTY);
self_.bucket(i).drop();
self_.items -= 1;
}
}
}
self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items;
});
'outer: for i in 0..guard.buckets() {
if *guard.ctrl(i) != DELETED {
continue;
}
'inner: loop {
let item = guard.bucket(i);
let hash = hasher(item.as_ref());
let new_i = guard.find_insert_slot(hash);
let probe_index = |pos: usize| {
(pos.wrapping_sub(guard.probe_seq(hash).pos) & guard.bucket_mask)
/ Group::WIDTH
};
if likely(probe_index(i) == probe_index(new_i)) {
guard.set_ctrl(i, h2(hash));
continue 'outer;
}
let prev_ctrl = *guard.ctrl(new_i);
guard.set_ctrl(new_i, h2(hash));
if prev_ctrl == EMPTY {
guard.set_ctrl(i, EMPTY);
guard.bucket(new_i).copy_from_nonoverlapping(&item);
continue 'outer;
} else {
debug_assert_eq!(prev_ctrl, DELETED);
mem::swap(guard.bucket(new_i).as_mut(), item.as_mut());
continue 'inner;
}
}
}
guard.growth_left = bucket_mask_to_capacity(guard.bucket_mask) - guard.items;
mem::forget(guard);
}
}
fn resize(
&mut self,
capacity: usize,
hasher: impl Fn(&T) -> u64,
fallability: Fallibility,
) -> Result<(), CollectionAllocErr> {
unsafe {
debug_assert!(self.items <= capacity);
let mut new_table = Self::try_with_capacity(capacity, fallability)?;
new_table.growth_left -= self.items;
new_table.items = self.items;
let mut new_table = guard(ManuallyDrop::new(new_table), |new_table| {
if !new_table.is_empty_singleton() {
new_table.free_buckets();
}
});
for item in self.iter() {
let hash = hasher(item.as_ref());
let index = new_table.find_insert_slot(hash);
new_table.set_ctrl(index, h2(hash));
new_table.bucket(index).copy_from_nonoverlapping(&item);
}
mem::swap(self, &mut new_table);
Ok(())
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> Bucket<T> {
unsafe {
let mut index = self.find_insert_slot(hash);
let old_ctrl = *self.ctrl(index);
if unlikely(self.growth_left == 0 && special_is_empty(old_ctrl)) {
self.reserve(1, hasher);
index = self.find_insert_slot(hash);
}
let bucket = self.bucket(index);
self.growth_left -= special_is_empty(old_ctrl) as usize;
self.set_ctrl(index, h2(hash));
bucket.write(value);
self.items += 1;
bucket
}
}
#[cfg_attr(feature = "inline-more", inline)]
#[cfg(feature = "rustc-internal-api")]
pub fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> {
unsafe {
let index = self.find_insert_slot(hash);
let bucket = self.bucket(index);
let old_ctrl = *self.ctrl(index);
self.growth_left -= special_is_empty(old_ctrl) as usize;
self.set_ctrl(index, h2(hash));
bucket.write(value);
self.items += 1;
bucket
}
}
#[inline]
pub fn find(&self, hash: u64, mut eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
unsafe {
for pos in self.probe_seq(hash) {
let group = Group::load(self.ctrl(pos));
for bit in group.match_byte(h2(hash)) {
let index = (pos + bit) & self.bucket_mask;
let bucket = self.bucket(index);
if likely(eq(bucket.as_ref())) {
return Some(bucket);
}
}
if likely(group.match_empty().any_bit_set()) {
return None;
}
}
}
unreachable!();
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn capacity(&self) -> usize {
self.items + self.growth_left
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn len(&self) -> usize {
self.items
}
#[cfg_attr(feature = "inline-more", inline)]
pub fn buckets(&self) -> usize {
self.bucket_mask + 1
}
#[cfg_attr(feature = "inline-more", inline)]
fn num_ctrl_bytes(&self) -> usize {
self.bucket_mask + 1 + Group::WIDTH
}
#[cfg_attr(feature = "inline-more", inline)]
fn is_empty_singleton(&self) -> bool {
self.bucket_mask == 0
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn iter(&self) -> RawIter<T> {
let data = Bucket::from_base_index(self.data.as_ptr(), 0);
RawIter {
iter: RawIterRange::new(self.ctrl.as_ptr(), data, self.buckets()),
items: self.items,
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn drain(&mut self) -> RawDrain<'_, T> {
RawDrain {
iter: self.iter(),
table: ManuallyDrop::new(mem::replace(self, Self::new())),
orig_table: NonNull::from(self),
marker: PhantomData,
}
}
#[cfg_attr(feature = "inline-more", inline)]
pub(crate) fn into_alloc(self) -> Option<(NonNull<u8>, Layout)> {
let alloc = if self.is_empty_singleton() {
None
} else {
let (layout, _) = calculate_layout::<T>(self.buckets())
.unwrap_or_else(|| unsafe { hint::unreachable_unchecked() });
Some((self.ctrl.cast(), layout))
};
mem::forget(self);
alloc
}
}
unsafe impl<T> Send for RawTable<T> where T: Send {}
unsafe impl<T> Sync for RawTable<T> where T: Sync {}
impl<T: Clone> Clone for RawTable<T> {
fn clone(&self) -> Self {
if self.is_empty_singleton() {
Self::new()
} else {
unsafe {
let mut new_table = ManuallyDrop::new(
Self::new_uninitialized(self.buckets(), Fallibility::Infallible)
.unwrap_or_else(|_| hint::unreachable_unchecked()),
);
self.ctrl(0)
.copy_to_nonoverlapping(new_table.ctrl(0), self.num_ctrl_bytes());
{
let mut guard = guard((0, &mut new_table), |(index, new_table)| {
if mem::needs_drop::<T>() {
for i in 0..=*index {
if is_full(*new_table.ctrl(i)) {
new_table.bucket(i).drop();
}
}
}
new_table.free_buckets();
});
for from in self.iter() {
let index = self.bucket_index(&from);
let to = guard.1.bucket(index);
to.write(from.as_ref().clone());
guard.0 = index;
}
mem::forget(guard);
}
new_table.items = self.items;
new_table.growth_left = self.growth_left;
ManuallyDrop::into_inner(new_table)
}
}
}
}
#[cfg(feature = "nightly")]
unsafe impl<#[may_dangle] T> Drop for RawTable<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
if !self.is_empty_singleton() {
unsafe {
if mem::needs_drop::<T>() {
for item in self.iter() {
item.drop();
}
}
self.free_buckets();
}
}
}
}
#[cfg(not(feature = "nightly"))]
impl<T> Drop for RawTable<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
if !self.is_empty_singleton() {
unsafe {
if mem::needs_drop::<T>() {
for item in self.iter() {
item.drop();
}
}
self.free_buckets();
}
}
}
}
impl<T> IntoIterator for RawTable<T> {
type Item = T;
type IntoIter = RawIntoIter<T>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> RawIntoIter<T> {
unsafe {
let iter = self.iter();
let alloc = self.into_alloc();
RawIntoIter {
iter,
alloc,
marker: PhantomData,
}
}
}
}
pub(crate) struct RawIterRange<T> {
current_group: BitMask,
data: Bucket<T>,
next_ctrl: *const u8,
end: *const u8,
}
impl<T> RawIterRange<T> {
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn new(ctrl: *const u8, data: Bucket<T>, len: usize) -> Self {
debug_assert_ne!(len, 0);
debug_assert_eq!(ctrl as usize % Group::WIDTH, 0);
let end = ctrl.add(len);
let current_group = Group::load_aligned(ctrl).match_full();
let next_ctrl = ctrl.add(Group::WIDTH);
Self {
current_group,
data,
next_ctrl,
end,
}
}
#[cfg_attr(feature = "inline-more", inline)]
#[cfg(feature = "rayon")]
pub(crate) fn split(mut self) -> (Self, Option<RawIterRange<T>>) {
unsafe {
if self.end <= self.next_ctrl {
(self, None)
} else {
let len = offset_from(self.end, self.next_ctrl);
debug_assert_eq!(len % Group::WIDTH, 0);
let mid = (len / 2) & !(Group::WIDTH - 1);
let tail = Self::new(
self.next_ctrl.add(mid),
self.data.add(Group::WIDTH).add(mid),
len - mid,
);
debug_assert_eq!(self.data.add(Group::WIDTH).add(mid).ptr, tail.data.ptr);
debug_assert_eq!(self.end, tail.end);
self.end = self.next_ctrl.add(mid);
debug_assert_eq!(self.end.add(Group::WIDTH), tail.next_ctrl);
(self, Some(tail))
}
}
}
}
unsafe impl<T> Send for RawIterRange<T> {}
unsafe impl<T> Sync for RawIterRange<T> {}
impl<T> Clone for RawIterRange<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Self {
data: self.data.clone(),
next_ctrl: self.next_ctrl,
current_group: self.current_group,
end: self.end,
}
}
}
impl<T> Iterator for RawIterRange<T> {
type Item = Bucket<T>;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<Bucket<T>> {
unsafe {
loop {
if let Some(index) = self.current_group.lowest_set_bit() {
self.current_group = self.current_group.remove_lowest_bit();
return Some(self.data.add(index));
}
if self.next_ctrl >= self.end {
return None;
}
self.current_group = Group::load_aligned(self.next_ctrl).match_full();
self.data = self.data.add(Group::WIDTH);
self.next_ctrl = self.next_ctrl.add(Group::WIDTH);
}
}
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
(
0,
Some(unsafe { offset_from(self.end, self.next_ctrl) + Group::WIDTH }),
)
}
}
impl<T> FusedIterator for RawIterRange<T> {}
pub struct RawIter<T> {
pub(crate) iter: RawIterRange<T>,
items: usize,
}
impl<T> Clone for RawIter<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Self {
iter: self.iter.clone(),
items: self.items,
}
}
}
impl<T> Iterator for RawIter<T> {
type Item = Bucket<T>;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<Bucket<T>> {
if let Some(b) = self.iter.next() {
self.items -= 1;
Some(b)
} else {
debug_assert_eq!(self.items, 0);
None
}
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.items, Some(self.items))
}
}
impl<T> ExactSizeIterator for RawIter<T> {}
impl<T> FusedIterator for RawIter<T> {}
pub struct RawIntoIter<T> {
iter: RawIter<T>,
alloc: Option<(NonNull<u8>, Layout)>,
marker: PhantomData<T>,
}
impl<T> RawIntoIter<T> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter(&self) -> RawIter<T> {
self.iter.clone()
}
}
unsafe impl<T> Send for RawIntoIter<T> where T: Send {}
unsafe impl<T> Sync for RawIntoIter<T> where T: Sync {}
#[cfg(feature = "nightly")]
unsafe impl<#[may_dangle] T> Drop for RawIntoIter<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
unsafe {
if mem::needs_drop::<T>() {
while let Some(item) = self.iter.next() {
item.drop();
}
}
if let Some((ptr, layout)) = self.alloc {
dealloc(ptr.as_ptr(), layout);
}
}
}
}
#[cfg(not(feature = "nightly"))]
impl<T> Drop for RawIntoIter<T> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
unsafe {
if mem::needs_drop::<T>() {
while let Some(item) = self.iter.next() {
item.drop();
}
}
if let Some((ptr, layout)) = self.alloc {
dealloc(ptr.as_ptr(), layout);
}
}
}
}
impl<T> Iterator for RawIntoIter<T> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<T> {
unsafe { Some(self.iter.next()?.read()) }
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<T> ExactSizeIterator for RawIntoIter<T> {}
impl<T> FusedIterator for RawIntoIter<T> {}
pub struct RawDrain<'a, T> {
iter: RawIter<T>,
table: ManuallyDrop<RawTable<T>>,
orig_table: NonNull<RawTable<T>>,
marker: PhantomData<&'a RawTable<T>>,
}
impl<T> RawDrain<'_, T> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter(&self) -> RawIter<T> {
self.iter.clone()
}
}
unsafe impl<T> Send for RawDrain<'_, T> where T: Send {}
unsafe impl<T> Sync for RawDrain<'_, T> where T: Sync {}
impl<T> Drop for RawDrain<'_, T> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
unsafe {
if mem::needs_drop::<T>() {
while let Some(item) = self.iter.next() {
item.drop();
}
}
self.table.clear_no_drop();
self.orig_table
.as_ptr()
.copy_from_nonoverlapping(&*self.table, 1);
}
}
}
impl<T> Iterator for RawDrain<'_, T> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<T> {
unsafe {
let item = self.iter.next()?;
Some(item.read())
}
}
#[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<T> ExactSizeIterator for RawDrain<'_, T> {}
impl<T> FusedIterator for RawDrain<'_, T> {}