diff options
Diffstat (limited to 'src/raw/mod.rs')
| -rw-r--r-- | src/raw/mod.rs | 670 |
1 files changed, 424 insertions, 246 deletions
diff --git a/src/raw/mod.rs b/src/raw/mod.rs index 3ae6980..5fe0a72 100644 --- a/src/raw/mod.rs +++ b/src/raw/mod.rs @@ -1,16 +1,13 @@ use crate::alloc::alloc::{handle_alloc_error, Layout}; use crate::scopeguard::guard; use crate::TryReserveError; -#[cfg(feature = "nightly")] -use crate::UnavailableMutError; -use core::hint; use core::iter::FusedIterator; use core::marker::PhantomData; use core::mem; use core::mem::ManuallyDrop; -#[cfg(feature = "nightly")] use core::mem::MaybeUninit; use core::ptr::NonNull; +use core::{hint, ptr}; cfg_if! { // Use the SSE2 implementation if possible: it allows us to scan 16 buckets @@ -59,7 +56,7 @@ fn cold() {} #[inline] fn likely(b: bool) -> bool { if !b { - cold() + cold(); } b } @@ -67,18 +64,18 @@ fn likely(b: bool) -> bool { #[inline] fn unlikely(b: bool) -> bool { if b { - cold() + cold(); } b } #[cfg(feature = "nightly")] -#[cfg_attr(feature = "inline-more", inline)] +#[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)] +#[inline] unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize { (to as usize - from as usize) / mem::size_of::<T>() } @@ -211,7 +208,7 @@ fn capacity_to_buckets(cap: usize) -> Option<usize> { // Any overflows will have been caught by the checked_mul. Also, any // rounding errors from the division above will be cleaned up by - // next_power_of_two (which can't overflow because of the previous divison). + // next_power_of_two (which can't overflow because of the previous division). Some(adjusted_cap.next_power_of_two()) } @@ -292,14 +289,14 @@ pub struct Bucket<T> { unsafe impl<T> Send for Bucket<T> {} impl<T> Clone for Bucket<T> { - #[cfg_attr(feature = "inline-more", inline)] + #[inline] fn clone(&self) -> Self { Self { ptr: self.ptr } } } impl<T> Bucket<T> { - #[cfg_attr(feature = "inline-more", inline)] + #[inline] unsafe fn from_base_index(base: NonNull<T>, index: usize) -> Self { let ptr = if mem::size_of::<T>() == 0 { // won't overflow because index must be less than length @@ -311,7 +308,7 @@ impl<T> Bucket<T> { ptr: NonNull::new_unchecked(ptr), } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] unsafe fn to_base_index(&self, base: NonNull<T>) -> usize { if mem::size_of::<T>() == 0 { self.ptr.as_ptr() as usize - 1 @@ -319,7 +316,7 @@ impl<T> Bucket<T> { offset_from(base.as_ptr(), self.ptr.as_ptr()) } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub fn as_ptr(&self) -> *mut T { if mem::size_of::<T>() == 0 { // Just return an arbitrary ZST pointer which is properly aligned @@ -328,7 +325,7 @@ impl<T> Bucket<T> { unsafe { self.ptr.as_ptr().sub(1) } } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] unsafe fn next_n(&self, offset: usize) -> Self { let ptr = if mem::size_of::<T>() == 0 { (self.ptr.as_ptr() as usize + offset) as *mut T @@ -343,23 +340,24 @@ impl<T> Bucket<T> { pub unsafe fn drop(&self) { self.as_ptr().drop_in_place(); } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn read(&self) -> T { self.as_ptr().read() } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn write(&self, val: T) { self.as_ptr().write(val); } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn as_ref<'a>(&self) -> &'a T { &*self.as_ptr() } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn as_mut<'a>(&self) -> &'a mut T { &mut *self.as_ptr() } - #[cfg_attr(feature = "inline-more", inline)] + #[cfg(feature = "raw")] + #[inline] pub unsafe fn copy_from_nonoverlapping(&self, other: &Self) { self.as_ptr().copy_from_nonoverlapping(other.as_ptr(), 1); } @@ -398,7 +396,7 @@ impl<T> RawTable<T, Global> { /// In effect this returns a table with exactly 1 bucket. However we can /// leave the data pointer dangling since that bucket is never written to /// due to our load factor forcing us to always have at least 1 free bucket. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub const fn new() -> Self { Self { table: RawTableInner::new_in(Global), @@ -427,7 +425,7 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// In effect this returns a table with exactly 1 bucket. However we can /// leave the data pointer dangling since that bucket is never written to /// due to our load factor forcing us to always have at least 1 free bucket. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub fn new_in(alloc: A) -> Self { Self { table: RawTableInner::new_in(alloc), @@ -492,33 +490,39 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { } } + /// Returns a reference to the underlying allocator. + #[inline] + pub fn allocator(&self) -> &A { + &self.table.alloc + } + /// Deallocates the table without dropping any entries. #[cfg_attr(feature = "inline-more", inline)] unsafe fn free_buckets(&mut self) { - self.table.free_buckets(TableLayout::new::<T>()) + self.table.free_buckets(TableLayout::new::<T>()); } /// Returns pointer to one past last element of data table. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn data_end(&self) -> NonNull<T> { NonNull::new_unchecked(self.table.ctrl.as_ptr().cast()) } /// Returns pointer to start of data table. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] #[cfg(feature = "nightly")] pub unsafe fn data_start(&self) -> *mut T { self.data_end().as_ptr().wrapping_sub(self.buckets()) } /// Returns the index of a bucket from a `Bucket`. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize { bucket.to_base_index(self.data_end()) } /// Returns a pointer to an element in the table. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn bucket(&self, index: usize) -> Bucket<T> { debug_assert_ne!(self.table.bucket_mask, 0); debug_assert!(index < self.buckets()); @@ -530,7 +534,7 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { #[deprecated(since = "0.8.1", note = "use erase or remove instead")] pub unsafe fn erase_no_drop(&mut self, item: &Bucket<T>) { let index = self.bucket_index(item); - self.table.erase(index) + self.table.erase(index); } /// Erases an element from the table, dropping it in place. @@ -550,7 +554,9 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { pub fn erase_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> bool { // Avoid `Option::map` because it bloats LLVM IR. if let Some(bucket) = self.find(hash, eq) { - unsafe { self.erase(bucket) }; + unsafe { + self.erase(bucket); + } true } else { false @@ -579,7 +585,7 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// Marks all table buckets as empty without dropping their contents. #[cfg_attr(feature = "inline-more", inline)] pub fn clear_no_drop(&mut self) { - self.table.clear_no_drop() + self.table.clear_no_drop(); } /// Removes all elements from the table without freeing the backing memory. @@ -593,7 +599,7 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { } unsafe fn drop_elements(&mut self) { - if mem::needs_drop::<T>() && self.len() != 0 { + if mem::needs_drop::<T>() && !self.is_empty() { for item in self.iter() { item.drop(); } @@ -624,7 +630,7 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { if min_buckets < self.buckets() { // Fast path if the table is empty if self.table.items == 0 { - *self = Self::with_capacity_in(min_size, self.table.alloc.clone()) + *self = Self::with_capacity_in(min_size, self.table.alloc.clone()); } else { // Avoid `Result::unwrap_or_else` because it bloats LLVM IR. if self @@ -676,102 +682,18 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { hasher: impl Fn(&T) -> u64, fallibility: Fallibility, ) -> Result<(), TryReserveError> { - // Avoid `Option::ok_or_else` because it bloats LLVM IR. - let new_items = match self.table.items.checked_add(additional) { - Some(new_items) => new_items, - None => return Err(fallibility.capacity_overflow()), - }; - let full_capacity = bucket_mask_to_capacity(self.table.bucket_mask); - if new_items <= full_capacity / 2 { - // Rehash in-place without re-allocating if we have plenty of spare - // capacity that is locked up due to DELETED entries. - self.rehash_in_place(hasher); - Ok(()) - } else { - // Otherwise, conservatively resize to at least the next size up - // to avoid churning deletes into frequent rehashes. - self.resize( - usize::max(new_items, full_capacity + 1), - hasher, - fallibility, - ) - } - } - - /// Rehashes the contents of the table in place (i.e. without changing the - /// allocation). - /// - /// If `hasher` panics then some the table's contents may be lost. - fn rehash_in_place(&mut self, hasher: impl Fn(&T) -> u64) { unsafe { - // If the hash function panics then properly clean up any elements - // that we haven't rehashed yet. We unfortunately can't preserve the - // element since we lost their hash and have no way of recovering it - // without risking another panic. - self.table.prepare_rehash_in_place(); - - let mut guard = guard(&mut self.table, move |self_| { + self.table.reserve_rehash_inner( + additional, + &|table, index| hasher(table.bucket::<T>(index).as_ref()), + fallibility, + TableLayout::new::<T>(), if mem::needs_drop::<T>() { - for i in 0..self_.buckets() { - if *self_.ctrl(i) == DELETED { - self_.set_ctrl(i, EMPTY); - self_.bucket::<T>(i).drop(); - self_.items -= 1; - } - } - } - self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items; - }); - - // At this point, DELETED elements are elements that we haven't - // rehashed yet. Find them and re-insert them at their ideal - // position. - 'outer: for i in 0..guard.buckets() { - if *guard.ctrl(i) != DELETED { - continue; - } - - 'inner: loop { - // Hash the current item - let item = guard.bucket(i); - let hash = hasher(item.as_ref()); - - // Search for a suitable place to put it - let new_i = guard.find_insert_slot(hash); - - // Probing works by scanning through all of the control - // bytes in groups, which may not be aligned to the group - // size. If both the new and old position fall within the - // same unaligned group, then there is no benefit in moving - // it and we can just continue to the next item. - if likely(guard.is_in_same_group(i, new_i, hash)) { - guard.set_ctrl_h2(i, hash); - continue 'outer; - } - - // We are moving the current item to a new position. Write - // our H2 to the control byte of the new position. - let prev_ctrl = guard.replace_ctrl_h2(new_i, hash); - if prev_ctrl == EMPTY { - guard.set_ctrl(i, EMPTY); - // If the target slot is empty, simply move the current - // element into the new slot and clear the old control - // byte. - guard.bucket(new_i).copy_from_nonoverlapping(&item); - continue 'outer; - } else { - // If the target slot is occupied, swap the two elements - // and then continue processing the element that we just - // swapped into the old slot. - 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); + Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T))) + } else { + None + }, + ) } } @@ -784,30 +706,12 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { fallibility: Fallibility, ) -> Result<(), TryReserveError> { unsafe { - let mut new_table = - self.table - .prepare_resize(TableLayout::new::<T>(), capacity, fallibility)?; - - // Copy all elements to the new table. - for item in self.iter() { - // This may panic. - let hash = hasher(item.as_ref()); - - // We can use a simpler version of insert() here since: - // - there are no DELETED entries. - // - we know there is enough space in the table. - // - all elements are unique. - let (index, _) = new_table.prepare_insert_slot(hash); - new_table.bucket(index).copy_from_nonoverlapping(&item); - } - - // We successfully copied all elements without panicking. Now replace - // self with the new table. The old table will have its memory freed but - // the items will not be dropped (since they have been moved into the - // new table). - mem::swap(&mut self.table, &mut new_table); - - Ok(()) + self.table.resize_inner( + capacity, + &|table, index| hasher(table.bucket::<T>(index).as_ref()), + fallibility, + TableLayout::new::<T>(), + ) } } @@ -872,19 +776,17 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// This does not check if the given element already exists in the table. #[cfg_attr(feature = "inline-more", inline)] #[cfg(any(feature = "raw", feature = "rustc-internal-api"))] - pub fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> { - unsafe { - let (index, old_ctrl) = self.table.prepare_insert_slot(hash); - let bucket = self.table.bucket(index); + pub unsafe fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> { + let (index, old_ctrl) = self.table.prepare_insert_slot(hash); + let bucket = self.table.bucket(index); - // If we are replacing a DELETED entry then we don't need to update - // the load counter. - self.table.growth_left -= special_is_empty(old_ctrl) as usize; + // If we are replacing a DELETED entry then we don't need to update + // the load counter. + self.table.growth_left -= special_is_empty(old_ctrl) as usize; - bucket.write(value); - self.table.items += 1; - bucket - } + bucket.write(value); + self.table.items += 1; + bucket } /// Temporary removes a bucket, applying the given function to the removed @@ -917,14 +819,14 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// Searches for an element in the table. #[inline] pub fn find(&self, hash: u64, mut eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>> { - unsafe { - for bucket in self.iter_hash(hash) { - let elm = bucket.as_ref(); - if likely(eq(elm)) { - return Some(bucket); - } - } - None + let result = self.table.find_inner(hash, &mut |index| unsafe { + eq(self.bucket(index).as_ref()) + }); + + // Avoid `Option::map` because it bloats LLVM IR. + match result { + Some(index) => Some(unsafe { self.bucket(index) }), + None => None, } } @@ -950,79 +852,84 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// Attempts to get mutable references to `N` entries in the table at once. /// - /// Returns an array of length `N` with the results of each query. For soundness, - /// at most one mutable reference will be returned to any entry. An - /// `Err(UnavailableMutError::Duplicate(i))` in the returned array indicates that a suitable - /// entry exists, but a mutable reference to it already occurs at index `i` in the returned - /// array. + /// Returns an array of length `N` with the results of each query. + /// + /// At most one mutable reference will be returned to any entry. `None` will be returned if any + /// of the hashes are duplicates. `None` will be returned if the hash is not found. /// /// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to /// the `i`th key to be looked up. - /// - /// This method is available only if the `nightly` feature is enabled. - #[cfg(feature = "nightly")] - pub fn get_each_mut<const N: usize>( + pub fn get_many_mut<const N: usize>( &mut self, hashes: [u64; N], - mut eq: impl FnMut(usize, &T) -> bool, - ) -> [Result<&'_ mut T, UnavailableMutError>; N] { - // Collect the requested buckets. - // TODO use `MaybeUninit::uninit_array` here instead once that's stable. - let mut buckets: [MaybeUninit<Option<Bucket<T>>>; N] = - unsafe { MaybeUninit::uninit().assume_init() }; - for i in 0..N { - buckets[i] = MaybeUninit::new(self.find(hashes[i], |k| eq(i, k))); + eq: impl FnMut(usize, &T) -> bool, + ) -> Option<[&'_ mut T; N]> { + unsafe { + let ptrs = self.get_many_mut_pointers(hashes, eq)?; + + for (i, &cur) in ptrs.iter().enumerate() { + if ptrs[..i].iter().any(|&prev| ptr::eq::<T>(prev, cur)) { + return None; + } + } + // All bucket are distinct from all previous buckets so we're clear to return the result + // of the lookup. + + // TODO use `MaybeUninit::array_assume_init` here instead once that's stable. + Some(mem::transmute_copy(&ptrs)) } - let buckets: [Option<Bucket<T>>; N] = unsafe { MaybeUninit::array_assume_init(buckets) }; + } - // Walk through the buckets, checking for duplicates and building up the output array. + pub unsafe fn get_many_unchecked_mut<const N: usize>( + &mut self, + hashes: [u64; N], + eq: impl FnMut(usize, &T) -> bool, + ) -> Option<[&'_ mut T; N]> { + let ptrs = self.get_many_mut_pointers(hashes, eq)?; + Some(mem::transmute_copy(&ptrs)) + } + + unsafe fn get_many_mut_pointers<const N: usize>( + &mut self, + hashes: [u64; N], + mut eq: impl FnMut(usize, &T) -> bool, + ) -> Option<[*mut T; N]> { // TODO use `MaybeUninit::uninit_array` here instead once that's stable. - let mut out: [MaybeUninit<Result<&'_ mut T, UnavailableMutError>>; N] = - unsafe { MaybeUninit::uninit().assume_init() }; - for i in 0..N { - out[i] = MaybeUninit::new( - #[allow(clippy::never_loop)] - 'outer: loop { - for j in 0..i { - match (&buckets[j], &buckets[i]) { - // These two buckets are the same, and we can't safely return a second - // mutable reference to the same entry. - (Some(prev), Some(cur)) if prev.as_ptr() == cur.as_ptr() => { - break 'outer Err(UnavailableMutError::Duplicate(j)); - } - _ => {} - } - } - // This bucket is distinct from all previous buckets (or it doesn't exist), so - // we're clear to return the result of the lookup. - break match &buckets[i] { - None => Err(UnavailableMutError::Absent), - Some(bkt) => unsafe { Ok(bkt.as_mut()) }, - }; - }, - ) + let mut outs: MaybeUninit<[*mut T; N]> = MaybeUninit::uninit(); + let outs_ptr = outs.as_mut_ptr(); + + for (i, &hash) in hashes.iter().enumerate() { + let cur = self.find(hash, |k| eq(i, k))?; + *(*outs_ptr).get_unchecked_mut(i) = cur.as_mut(); } - unsafe { MaybeUninit::array_assume_init(out) } + // TODO use `MaybeUninit::array_assume_init` here instead once that's stable. + Some(outs.assume_init()) } /// Returns the number of elements the map can hold without reallocating. /// /// This number is a lower bound; the table might be able to hold /// more, but is guaranteed to be able to hold at least this many. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub fn capacity(&self) -> usize { self.table.items + self.table.growth_left } /// Returns the number of elements in the table. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub fn len(&self) -> usize { self.table.items } + /// Returns `true` if the table contains no elements. + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + /// Returns the number of buckets in the table. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub fn buckets(&self) -> usize { self.table.bucket_mask + 1 } @@ -1031,7 +938,7 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// the caller to ensure that the `RawTable` outlives the `RawIter`. /// Because we cannot make the `next` method unsafe on the `RawIter` /// struct, we have to make the `iter` method unsafe. - #[cfg_attr(feature = "inline-more", inline)] + #[inline] pub unsafe fn iter(&self) -> RawIter<T> { let data = Bucket::from_base_index(self.data_end(), 0); RawIter { @@ -1042,12 +949,15 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { /// Returns an iterator over occupied buckets that could match a given hash. /// - /// In rare cases, the iterator may return a bucket with a different hash. + /// `RawTable` only stores 7 bits of the hash value, so this iterator may + /// return items that have a hash value different than the one provided. You + /// should always validate the returned values before using them. /// /// It is up to the caller to ensure that the `RawTable` outlives the /// `RawIterHash`. Because we cannot make the `next` method unsafe on the /// `RawIterHash` struct, we have to make the `iter_hash` method unsafe. #[cfg_attr(feature = "inline-more", inline)] + #[cfg(feature = "raw")] pub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<'_, T, A> { RawIterHash::new(self, hash) } @@ -1121,11 +1031,21 @@ impl<T, A: Allocator + Clone> RawTable<T, A> { } } -unsafe impl<T, A: Allocator + Clone> Send for RawTable<T, A> where T: Send {} -unsafe impl<T, A: Allocator + Clone> Sync for RawTable<T, A> where T: Sync {} +unsafe impl<T, A: Allocator + Clone> Send for RawTable<T, A> +where + T: Send, + A: Send, +{ +} +unsafe impl<T, A: Allocator + Clone> Sync for RawTable<T, A> +where + T: Sync, + A: Sync, +{ +} impl<A> RawTableInner<A> { - #[cfg_attr(feature = "inline-more", inline)] + #[inline] const fn new_in(alloc: A) -> Self { Self { // Be careful to cast the entire slice to a raw pointer. @@ -1154,6 +1074,15 @@ impl<A: Allocator + Clone> RawTableInner<A> { None => return Err(fallibility.capacity_overflow()), }; + // We need an additional check to ensure that the allocation doesn't + // exceed `isize::MAX`. We can skip this check on 64-bit systems since + // such allocations will never succeed anyways. + // + // This mirrors what Vec does in the standard library. + if mem::size_of::<usize>() < 8 && layout.size() > isize::MAX as usize { + return Err(fallibility.capacity_overflow()); + } + let ptr: NonNull<u8> = match do_alloc(&alloc, layout) { Ok(block) => block.cast(), Err(_) => return Err(fallibility.alloc_err(layout)), @@ -1221,7 +1150,7 @@ impl<A: Allocator + Clone> RawTableInner<A> { // EMPTY entries. These will unfortunately trigger a // match, but once masked may point to a full bucket that // is already occupied. We detect this situation here and - // perform a second scan starting at the begining of the + // perform a second scan starting at the beginning of the // table. This second scan is guaranteed to find an empty // slot (due to the load factor) before hitting the trailing // control bytes (containing EMPTY). @@ -1240,6 +1169,32 @@ impl<A: Allocator + Clone> RawTableInner<A> { } } + /// Searches for an element in the table. This uses dynamic dispatch to reduce the amount of + /// code generated, but it is eliminated by LLVM optimizations. + #[inline] + fn find_inner(&self, hash: u64, eq: &mut dyn FnMut(usize) -> bool) -> Option<usize> { + let h2_hash = h2(hash); + let mut probe_seq = self.probe_seq(hash); + + loop { + let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) }; + + for bit in group.match_byte(h2_hash) { + let index = (probe_seq.pos + bit) & self.bucket_mask; + + if likely(eq(index)) { + return Some(index); + } + } + + if likely(group.match_empty().any_bit_set()) { + return None; + } + + probe_seq.move_next(self.bucket_mask); + } + } + #[allow(clippy::mut_mut)] #[inline] unsafe fn prepare_rehash_in_place(&mut self) { @@ -1263,14 +1218,22 @@ impl<A: Allocator + Clone> RawTableInner<A> { } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] unsafe fn bucket<T>(&self, index: usize) -> Bucket<T> { debug_assert_ne!(self.bucket_mask, 0); debug_assert!(index < self.buckets()); Bucket::from_base_index(self.data_end(), index) } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] + unsafe fn bucket_ptr(&self, index: usize, size_of: usize) -> *mut u8 { + debug_assert_ne!(self.bucket_mask, 0); + debug_assert!(index < self.buckets()); + let base: *mut u8 = self.data_end().as_ptr(); + base.sub((index + 1) * size_of) + } + + #[inline] unsafe fn data_end<T>(&self) -> NonNull<T> { NonNull::new_unchecked(self.ctrl.as_ptr().cast()) } @@ -1305,7 +1268,7 @@ impl<A: Allocator + Clone> RawTableInner<A> { #[inline] unsafe fn record_item_insert_at(&mut self, index: usize, old_ctrl: u8, hash: u64) { - self.growth_left -= special_is_empty(old_ctrl) as usize; + self.growth_left -= usize::from(special_is_empty(old_ctrl)); self.set_ctrl_h2(index, hash); self.items += 1; } @@ -1322,7 +1285,7 @@ impl<A: Allocator + Clone> RawTableInner<A> { /// the end of the array. #[inline] unsafe fn set_ctrl_h2(&self, index: usize, hash: u64) { - self.set_ctrl(index, h2(hash)) + self.set_ctrl(index, h2(hash)); } #[inline] @@ -1415,6 +1378,179 @@ impl<A: Allocator + Clone> RawTableInner<A> { })) } + /// Reserves or rehashes to make room for `additional` more elements. + /// + /// This uses dynamic dispatch to reduce the amount of + /// code generated, but it is eliminated by LLVM optimizations when inlined. + #[allow(clippy::inline_always)] + #[inline(always)] + unsafe fn reserve_rehash_inner( + &mut self, + additional: usize, + hasher: &dyn Fn(&mut Self, usize) -> u64, + fallibility: Fallibility, + layout: TableLayout, + drop: Option<fn(*mut u8)>, + ) -> Result<(), TryReserveError> { + // Avoid `Option::ok_or_else` because it bloats LLVM IR. + let new_items = match self.items.checked_add(additional) { + Some(new_items) => new_items, + None => return Err(fallibility.capacity_overflow()), + }; + let full_capacity = bucket_mask_to_capacity(self.bucket_mask); + if new_items <= full_capacity / 2 { + // Rehash in-place without re-allocating if we have plenty of spare + // capacity that is locked up due to DELETED entries. + self.rehash_in_place(hasher, layout.size, drop); + Ok(()) + } else { + // Otherwise, conservatively resize to at least the next size up + // to avoid churning deletes into frequent rehashes. + self.resize_inner( + usize::max(new_items, full_capacity + 1), + hasher, + fallibility, + layout, + ) + } + } + + /// Allocates a new table of a different size and moves the contents of the + /// current table into it. + /// + /// This uses dynamic dispatch to reduce the amount of + /// code generated, but it is eliminated by LLVM optimizations when inlined. + #[allow(clippy::inline_always)] + #[inline(always)] + unsafe fn resize_inner( + &mut self, + capacity: usize, + hasher: &dyn Fn(&mut Self, usize) -> u64, + fallibility: Fallibility, + layout: TableLayout, + ) -> Result<(), TryReserveError> { + let mut new_table = self.prepare_resize(layout, capacity, fallibility)?; + + // Copy all elements to the new table. + for i in 0..self.buckets() { + if !is_full(*self.ctrl(i)) { + continue; + } + + // This may panic. + let hash = hasher(self, i); + + // We can use a simpler version of insert() here since: + // - there are no DELETED entries. + // - we know there is enough space in the table. + // - all elements are unique. + let (index, _) = new_table.prepare_insert_slot(hash); + + ptr::copy_nonoverlapping( + self.bucket_ptr(i, layout.size), + new_table.bucket_ptr(index, layout.size), + layout.size, + ); + } + + // We successfully copied all elements without panicking. Now replace + // self with the new table. The old table will have its memory freed but + // the items will not be dropped (since they have been moved into the + // new table). + mem::swap(self, &mut new_table); + + Ok(()) + } + + /// Rehashes the contents of the table in place (i.e. without changing the + /// allocation). + /// + /// If `hasher` panics then some the table's contents may be lost. + /// + /// This uses dynamic dispatch to reduce the amount of + /// code generated, but it is eliminated by LLVM optimizations when inlined. + #[allow(clippy::inline_always)] + #[cfg_attr(feature = "inline-more", inline(always))] + #[cfg_attr(not(feature = "inline-more"), inline)] + unsafe fn rehash_in_place( + &mut self, + hasher: &dyn Fn(&mut Self, usize) -> u64, + size_of: usize, + drop: Option<fn(*mut u8)>, + ) { + // If the hash function panics then properly clean up any elements + // that we haven't rehashed yet. We unfortunately can't preserve the + // element since we lost their hash and have no way of recovering it + // without risking another panic. + self.prepare_rehash_in_place(); + + let mut guard = guard(self, move |self_| { + if let Some(drop) = drop { + for i in 0..self_.buckets() { + if *self_.ctrl(i) == DELETED { + self_.set_ctrl(i, EMPTY); + drop(self_.bucket_ptr(i, size_of)); + self_.items -= 1; + } + } + } + self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items; + }); + + // At this point, DELETED elements are elements that we haven't + // rehashed yet. Find them and re-insert them at their ideal + // position. + 'outer: for i in 0..guard.buckets() { + if *guard.ctrl(i) != DELETED { + continue; + } + + let i_p = guard.bucket_ptr(i, size_of); + + 'inner: loop { + // Hash the current item + let hash = hasher(*guard, i); + + // Search for a suitable place to put it + let new_i = guard.find_insert_slot(hash); + let new_i_p = guard.bucket_ptr(new_i, size_of); + + // Probing works by scanning through all of the control + // bytes in groups, which may not be aligned to the group + // size. If both the new and old position fall within the + // same unaligned group, then there is no benefit in moving + // it and we can just continue to the next item. + if likely(guard.is_in_same_group(i, new_i, hash)) { + guard.set_ctrl_h2(i, hash); + continue 'outer; + } + + // We are moving the current item to a new position. Write + // our H2 to the control byte of the new position. + let prev_ctrl = guard.replace_ctrl_h2(new_i, hash); + if prev_ctrl == EMPTY { + guard.set_ctrl(i, EMPTY); + // If the target slot is empty, simply move the current + // element into the new slot and clear the old control + // byte. + ptr::copy_nonoverlapping(i_p, new_i_p, size_of); + continue 'outer; + } else { + // If the target slot is occupied, swap the two elements + // and then continue processing the element that we just + // swapped into the old slot. + debug_assert_eq!(prev_ctrl, DELETED); + ptr::swap_nonoverlapping(i_p, new_i_p, size_of); + continue 'inner; + } + } + } + + guard.growth_left = bucket_mask_to_capacity(guard.bucket_mask) - guard.items; + + mem::forget(guard); + } + #[inline] unsafe fn free_buckets(&mut self, table_layout: TableLayout) { // Avoid `Option::unwrap_or_else` because it bloats LLVM IR. @@ -1454,7 +1590,7 @@ impl<A: Allocator + Clone> RawTableInner<A> { // // Note that in this context `leading_zeros` refers to the bytes at the // end of a group, while `trailing_zeros` refers to the bytes at the - // begining of a group. + // beginning of a group. let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH { DELETED } else { @@ -1524,7 +1660,7 @@ impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> { self.clone_from_spec(source, |self_| { // We need to leave the table in an empty state. - self_.clear_no_drop() + self_.clear_no_drop(); }); } } @@ -1536,8 +1672,8 @@ trait RawTableClone { unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self)); } impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A> { - #[cfg_attr(feature = "inline-more", inline)] default_fn! { + #[cfg_attr(feature = "inline-more", inline)] unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self)) { self.clone_from_impl(source, on_panic); } @@ -1574,7 +1710,7 @@ impl<T: Clone, A: Allocator + Clone> RawTable<T, A> { // to make sure we drop only the elements that have been // cloned so far. let mut guard = guard((0, &mut *self), |(index, self_)| { - if mem::needs_drop::<T>() && self_.len() != 0 { + if mem::needs_drop::<T>() && !self_.is_empty() { for i in 0..=*index { if is_full(*self_.table.ctrl(i)) { self_.bucket(i).drop(); @@ -1650,7 +1786,7 @@ impl<T: Clone, A: Allocator + Clone> RawTable<T, A> { } impl<T, A: Allocator + Clone + Default> Default for RawTable<T, A> { - #[cfg_attr(feature = "inline-more", inline)] + #[inline] fn default() -> Self { Self::new_in(Default::default()) } @@ -1824,13 +1960,17 @@ impl<T> Iterator for RawIterRange<T> { } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { // We don't have an item count, so just guess based on the range size. - ( - 0, - Some(unsafe { offset_from(self.end, self.next_ctrl) + Group::WIDTH }), - ) + let remaining_buckets = if self.end > self.next_ctrl { + unsafe { offset_from(self.end, self.next_ctrl) } + } else { + 0 + }; + + // Add a group width to include the group we are currently processing. + (0, Some(Group::WIDTH + remaining_buckets)) } } @@ -1871,7 +2011,7 @@ impl<T> RawIter<T> { /// For the iterator to remain valid, this method must be called once /// for each insert before `next` is called again. /// - /// This method does not guarantee that an insertion of a bucket witha greater + /// This method does not guarantee that an insertion of a bucket with a greater /// index than the last one yielded will be reflected in the iterator. /// /// This method should be called _after_ the given insert is made. @@ -1923,7 +2063,7 @@ impl<T> RawIter<T> { // If it did, we're done. // - Otherwise, update the iterator cached group so that it won't // yield a to-be-removed bucket, or _will_ yield a to-be-added bucket. - // We'll also need ot update the item count accordingly. + // We'll also need to update the item count accordingly. if let Some(index) = self.iter.current_group.lowest_set_bit() { let next_bucket = self.iter.data.next_n(index); if b.as_ptr() > next_bucket.as_ptr() { @@ -2006,7 +2146,7 @@ impl<T> Iterator for RawIter<T> { } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { (self.items, Some(self.items)) } @@ -2030,8 +2170,18 @@ impl<T, A: Allocator + Clone> RawIntoIter<T, A> { } } -unsafe impl<T, A: Allocator + Clone> Send for RawIntoIter<T, A> where T: Send {} -unsafe impl<T, A: Allocator + Clone> Sync for RawIntoIter<T, A> where T: Sync {} +unsafe impl<T, A: Allocator + Clone> Send for RawIntoIter<T, A> +where + T: Send, + A: Send, +{ +} +unsafe impl<T, A: Allocator + Clone> Sync for RawIntoIter<T, A> +where + T: Sync, + A: Sync, +{ +} #[cfg(feature = "nightly")] unsafe impl<#[may_dangle] T, A: Allocator + Clone> Drop for RawIntoIter<T, A> { @@ -2072,7 +2222,7 @@ impl<T, A: Allocator + Clone> Iterator for RawIntoIter<T, A> { unsafe { Some(self.iter.next()?.read()) } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } @@ -2103,8 +2253,18 @@ impl<T, A: Allocator + Clone> RawDrain<'_, T, A> { } } -unsafe impl<T, A: Allocator + Copy> Send for RawDrain<'_, T, A> where T: Send {} -unsafe impl<T, A: Allocator + Copy> Sync for RawDrain<'_, T, A> where T: Sync {} +unsafe impl<T, A: Allocator + Copy> Send for RawDrain<'_, T, A> +where + T: Send, + A: Send, +{ +} +unsafe impl<T, A: Allocator + Copy> Sync for RawDrain<'_, T, A> +where + T: Sync, + A: Sync, +{ +} impl<T, A: Allocator + Clone> Drop for RawDrain<'_, T, A> { #[cfg_attr(feature = "inline-more", inline)] @@ -2136,7 +2296,7 @@ impl<T, A: Allocator + Clone> Iterator for RawDrain<'_, T, A> { } } - #[cfg_attr(feature = "inline-more", inline)] + #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } @@ -2147,7 +2307,9 @@ impl<T, A: Allocator + Clone> FusedIterator for RawDrain<'_, T, A> {} /// Iterator over occupied buckets that could match a given hash. /// -/// In rare cases, the iterator may return a bucket with a different hash. +/// `RawTable` only stores 7 bits of the hash value, so this iterator may return +/// items that have a hash value different than the one provided. You should +/// always validate the returned values before using them. pub struct RawIterHash<'a, T, A: Allocator + Clone = Global> { inner: RawIterHashInner<'a, A>, _marker: PhantomData<T>, @@ -2170,6 +2332,7 @@ struct RawIterHashInner<'a, A: Allocator + Clone> { impl<'a, T, A: Allocator + Clone> RawIterHash<'a, T, A> { #[cfg_attr(feature = "inline-more", inline)] + #[cfg(feature = "raw")] fn new(table: &'a RawTable<T, A>, hash: u64) -> Self { RawIterHash { inner: RawIterHashInner::new(&table.table, hash), @@ -2179,6 +2342,7 @@ impl<'a, T, A: Allocator + Clone> RawIterHash<'a, T, A> { } impl<'a, A: Allocator + Clone> RawIterHashInner<'a, A> { #[cfg_attr(feature = "inline-more", inline)] + #[cfg(feature = "raw")] fn new(table: &'a RawTableInner<A>, hash: u64) -> Self { unsafe { let h2_hash = h2(hash); @@ -2235,6 +2399,20 @@ impl<'a, A: Allocator + Clone> Iterator for RawIterHashInner<'a, A> { mod test_map { use super::*; + fn rehash_in_place<T>(table: &mut RawTable<T>, hasher: impl Fn(&T) -> u64) { + unsafe { + table.table.rehash_in_place( + &|table, index| hasher(table.bucket::<T>(index).as_ref()), + mem::size_of::<T>(), + if mem::needs_drop::<T>() { + Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T))) + } else { + None + }, + ); + } + } + #[test] fn rehash() { let mut table = RawTable::new(); @@ -2250,7 +2428,7 @@ mod test_map { assert!(table.find(i + 100, |x| *x == i + 100).is_none()); } - table.rehash_in_place(hasher); + rehash_in_place(&mut table, hasher); for i in 0..100 { unsafe { |