Struct RawTable 

pub(crate) struct RawTable<T, A: Allocator = Global> {
    table: RawTableInner,
    alloc: A,
    marker: PhantomData<T>,
}

A raw hash table with an unsafe API.

Fields

table: RawTableInner

alloc: A

marker: PhantomData<T>

Implementations

impl<T> RawTable<T, Global>

pub(crate) const fn new() -> Self

Creates a new empty hash table without allocating any memory.

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.

pub(crate) fn with_capacity(capacity: usize) -> Self

Allocates a new hash table with at least enough capacity for inserting the given number of elements without reallocating.

impl<T, A: Allocator> RawTable<T, A>

const TABLE_LAYOUT: TableLayout

pub(crate) const fn new_in(alloc: A) -> Self

Creates a new empty hash table without allocating any memory, using the given allocator.

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.

unsafe fn new_uninitialized( alloc: A, buckets: usize, fallibility: Fallibility, ) -> Result<Self, TryReserveError>

Allocates a new hash table with the given number of buckets.

The control bytes are left uninitialized.

pub(crate) fn with_capacity_in(capacity: usize, alloc: A) -> Self

Allocates a new hash table using the given allocator, with at least enough capacity for inserting the given number of elements without reallocating.

pub(crate) fn allocator(&self) -> &A

Returns a reference to the underlying allocator.

pub(crate) fn data_end(&self) -> NonNull<T>

Returns pointer to one past last data element in the table as viewed from the start point of the allocation.

The caller must ensure that the RawTable outlives the returned NonNull<T>, otherwise using it may result in undefined behavior.

pub(crate) fn allocation_size(&self) -> usize

Returns the total amount of memory allocated internally by the hash table, in bytes.

The returned number is informational only. It is intended to be primarily used for memory profiling.

pub(crate) unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize

Returns the index of a bucket from a Bucket.

pub(crate) unsafe fn bucket(&self, index: usize) -> Bucket<T>

Returns a pointer to an element in the table.

The caller must ensure that the RawTable outlives the returned Bucket<T>, otherwise using it may result in undefined behavior.

Safety

If mem::size_of::<T>() != 0, then the caller of this function must observe the following safety rules:

• The table must already be allocated;

• The index must not be greater than the number returned by the RawTable::num_buckets function, i.e. (index + 1) <= self.num_buckets().

It is safe to call this function with index of zero (index == 0) on a table that has not been allocated, but using the returned Bucket results in undefined behavior.

If mem::size_of::<T>() == 0, then the only requirement is that the index must not be greater than the number returned by the RawTable::num_buckets function, i.e. (index + 1) <= self.num_buckets().

unsafe fn erase_no_drop(&mut self, item: &Bucket<T>)

Erases an element from the table without dropping it.

pub(crate) unsafe fn erase(&mut self, item: Bucket<T>)

Erases an element from the table, dropping it in place.

pub(crate) unsafe fn remove(&mut self, item: Bucket<T>) -> (T, usize)

Removes an element from the table, returning it.

This also returns an index to the newly free bucket.

pub(crate) unsafe fn remove_tagged( &mut self, item: Bucket<T>, ) -> (T, usize, Tag)

Removes an element from the table, returning it.

This also returns an index to the newly free bucket and the former Tag for that bucket.

pub(crate) fn remove_entry( &mut self, hash: u64, eq: impl FnMut(&T) -> bool, ) -> Option<T>

Finds and removes an element from the table, returning it.

pub(crate) fn clear_no_drop(&mut self)

Marks all table buckets as empty without dropping their contents.

pub(crate) fn clear(&mut self)

Removes all elements from the table without freeing the backing memory.

pub(crate) fn shrink_to(&mut self, min_size: usize, hasher: impl Fn(&T) -> u64)

Shrinks the table to fit max(self.len(), min_size) elements.

pub(crate) fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64)

Ensures that at least additional items can be inserted into the table without reallocation.

pub(crate) fn try_reserve( &mut self, additional: usize, hasher: impl Fn(&T) -> u64, ) -> Result<(), TryReserveError>

Tries to ensure that at least additional items can be inserted into the table without reallocation.

unsafe fn reserve_rehash( &mut self, additional: usize, hasher: impl Fn(&T) -> u64, fallibility: Fallibility, ) -> Result<(), TryReserveError>

Out-of-line slow path for reserve and try_reserve.

Safety

The RawTableInner must have properly initialized control bytes, otherwise calling this function results in undefined behavior

unsafe fn resize( &mut self, capacity: usize, hasher: impl Fn(&T) -> u64, fallibility: Fallibility, ) -> Result<(), TryReserveError>

Allocates a new table of a different size and moves the contents of the current table into it.

Safety

The RawTableInner must have properly initialized control bytes, otherwise calling this function results in undefined behavior

The caller of this function must ensure that capacity >= self.table.items otherwise:

• If self.table.items != 0, calling of this function with capacity equal to 0 (capacity == 0) results in undefined behavior.

• If self.table.items > capacity_to_buckets(capacity, Self::TABLE_LAYOUT) calling this function are never return (will loop infinitely).

See RawTableInner::find_insert_index for more information.

pub(crate) fn insert( &mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64, ) -> Bucket<T>

Inserts a new element into the table, and returns its raw bucket.

This does not check if the given element already exists in the table.

pub(crate) fn insert_entry( &mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64, ) -> &mut T

Inserts a new element into the table, and returns a mutable reference to it.

This does not check if the given element already exists in the table.

pub(crate) unsafe fn replace_bucket_with<F>( &mut self, bucket: Bucket<T>, f: F, ) -> Option<Tag>

where F: FnOnce(T) -> Option<T>,

Temporarily removes a bucket, applying the given function to the removed element and optionally put back the returned value in the same bucket.

Returns tag for bucket if the bucket is emptied out.

This does not check if the given bucket is actually occupied.

pub(crate) fn find_or_find_insert_index( &mut self, hash: u64, eq: impl FnMut(&T) -> bool, hasher: impl Fn(&T) -> u64, ) -> Result<Bucket<T>, usize>

Searches for an element in the table. If the element is not found, returns Err with the position of a slot where an element with the same hash could be inserted.

This function may resize the table if additional space is required for inserting an element.

pub(crate) unsafe fn insert_at_index( &mut self, hash: u64, index: usize, value: T, ) -> Bucket<T>

Inserts a new element into the table at the given index with the given hash, and returns its raw bucket.

Safety

index must point to a slot previously returned by find_or_find_insert_index, and no mutation of the table must have occurred since that call.

pub(crate) unsafe fn insert_tagged_at_index( &mut self, tag: Tag, index: usize, value: T, ) -> Bucket<T>

Inserts a new element into the table at the given index with the given tag, and returns its raw bucket.

Safety

index must point to a slot previously returned by find_or_find_insert_index, and no mutation of the table must have occurred since that call.

pub(crate) fn find( &self, hash: u64, eq: impl FnMut(&T) -> bool, ) -> Option<Bucket<T>>

Searches for an element in the table.

pub(crate) fn get(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>

Gets a reference to an element in the table.

pub(crate) fn get_mut( &mut self, hash: u64, eq: impl FnMut(&T) -> bool, ) -> Option<&mut T>

Gets a mutable reference to an element in the table.

pub(crate) fn get_bucket(&self, index: usize) -> Option<&T>

Gets a reference to an element in the table at the given bucket index.

pub(crate) fn get_bucket_mut(&mut self, index: usize) -> Option<&mut T>

Gets a mutable reference to an element in the table at the given bucket index.

pub(crate) fn checked_bucket(&self, index: usize) -> Option<Bucket<T>>

Returns a pointer to an element in the table, but only after verifying that the index is in-bounds and the bucket is occupied.

pub(crate) fn get_disjoint_mut<const N: usize>( &mut self, hashes: [u64; N], eq: impl FnMut(usize, &T) -> bool, ) -> [Option<&mut T>; N]

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.

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 ith key to be looked up.

pub(crate) unsafe fn get_disjoint_unchecked_mut<const N: usize>( &mut self, hashes: [u64; N], eq: impl FnMut(usize, &T) -> bool, ) -> [Option<&mut T>; N]

unsafe fn get_disjoint_mut_pointers<const N: usize>( &mut self, hashes: [u64; N], eq: impl FnMut(usize, &T) -> bool, ) -> [Option<NonNull<T>>; N]

pub(crate) fn capacity(&self) -> usize

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.

pub(crate) fn len(&self) -> usize

Returns the number of elements in the table.

pub(crate) fn is_empty(&self) -> bool

Returns true if the table contains no elements.

pub(crate) fn num_buckets(&self) -> usize

Returns the number of buckets in the table.

pub(crate) unsafe fn is_bucket_full(&self, index: usize) -> bool

Checks whether the bucket at index is full.

Safety

The caller must ensure index is less than the number of buckets.

pub(crate) unsafe fn iter(&self) -> RawIter<T>

Returns an iterator over every element in the table. It is up to 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.

pub(crate) unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<T>

Returns an iterator over occupied buckets that could match a given 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.

pub(crate) unsafe fn iter_hash_buckets(&self, hash: u64) -> RawIterHashIndices

Returns an iterator over occupied bucket indices that could match a given 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 RawIterHashIndices. Because we cannot make the next method unsafe on the RawIterHashIndices struct, we have to make the iter_hash_buckets method unsafe.

pub(crate) unsafe fn full_buckets_indices(&self) -> FullBucketsIndices

Returns an iterator over full buckets indices in the table.

See RawTableInner::full_buckets_indices for safety conditions.

pub(crate) fn drain(&mut self) -> RawDrain<'_, T, A>

Returns an iterator which removes all elements from the table without freeing the memory.

pub(crate) unsafe fn drain_iter_from( &mut self, iter: RawIter<T>, ) -> RawDrain<'_, T, A>

Returns an iterator which removes all elements from the table without freeing the memory.

Iteration starts at the provided iterator’s current location.

It is up to the caller to ensure that the iterator is valid for this RawTable and covers all items that remain in the table.

pub(crate) unsafe fn into_iter_from(self, iter: RawIter<T>) -> RawIntoIter<T, A>

Returns an iterator which consumes all elements from the table.

Iteration starts at the provided iterator’s current location.

It is up to the caller to ensure that the iterator is valid for this RawTable and covers all items that remain in the table.

pub(crate) fn into_allocation(self) -> Option<(NonNull<u8>, Layout, A)>

Converts the table into a raw allocation. The contents of the table should be dropped using a RawIter before freeing the allocation.

impl<T: Clone, A: Allocator + Clone> RawTable<T, A>

unsafe fn clone_from_impl(&mut self, source: &Self)

Common code for clone and clone_from. Assumes:

• self.num_buckets() == source.num_buckets().
• Any existing elements have been dropped.
• The control bytes are not initialized yet.

Trait Implementations

impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, A: Allocator + Default> Default for RawTable<T, A>

fn default() -> Self

Returns the “default value” for a type.

impl<T, A: Allocator> Drop for RawTable<T, A>

Available on non-crate feature nightly only.

fn drop(&mut self)

Executes the destructor for this type.

impl<T, A: Allocator> IntoIterator for RawTable<T, A>

type Item = T

The type of the elements being iterated over.

type IntoIter = RawIntoIter<T, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> RawIntoIter<T, A>

Creates an iterator from a value.

impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A>

unsafe fn clone_from_spec(&mut self, source: &Self)

impl<T, A> Send for RawTable<T, A>

where T: Send, A: Send + Allocator,

impl<T, A> Sync for RawTable<T, A>

where T: Sync, A: Sync + Allocator,