Struct hashbrown::raw::RawTableInner

struct RawTableInner<A> {
    bucket_mask: usize,
    ctrl: NonNull<u8>,
    growth_left: usize,
    items: usize,
    alloc: A,
}

Non-generic part of RawTable which allows functions to be instantiated only once regardless of how many different key-value types are used.

Fields

bucket_mask: usize

ctrl: NonNull<u8>

growth_left: usize

items: usize

alloc: A

Implementations

impl<A> RawTableInner<A>

const fn new_in(alloc: A) -> 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 accessed due to our load factor forcing us to always have at least 1 free bucket.

impl<A: Allocator + Clone> RawTableInner<A>

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

Allocates a new RawTableInner with the given number of buckets. The control bytes and buckets are left uninitialized.

Safety

The caller of this function must ensure that the buckets is power of two and also initialize all control bytes of the length self.bucket_mask + 1 + Group::WIDTH with the EMPTY bytes.

See also Allocator API for other safety concerns.

fn fallible_with_capacity( alloc: A, table_layout: TableLayout, capacity: usize, fallibility: Fallibility ) -> Result<Self, TryReserveError>

Attempts to allocate a new RawTableInner with at least enough capacity for inserting the given number of elements without reallocating.

All the control bytes are initialized with the EMPTY bytes.

unsafe fn fix_insert_slot(&self, index: usize) -> InsertSlot

Fixes up an insertion slot due to false positives for groups smaller than the group width. This must only be used on insertion slots found by find_insert_slot_in_group.

fn find_insert_slot_in_group( &self, group: &Group, probe_seq: &ProbeSeq ) -> Option<usize>

Finds the position to insert something in a group. This may have false positives and must be fixed up with fix_insert_slot before it’s used.

fn find_or_find_insert_slot_inner( &self, hash: u64, eq: &mut dyn FnMut(usize) -> bool ) -> Result<usize, InsertSlot>

Searches for an element in the table, or a potential slot where that element could be inserted.

This uses dynamic dispatch to reduce the amount of code generated, but that is eliminated by LLVM optimizations.

unsafe fn prepare_insert_slot(&self, hash: u64) -> (usize, u8)

Searches for an empty or deleted bucket which is suitable for inserting a new element and sets the hash for that slot.

There must be at least 1 empty bucket in the table.

fn find_insert_slot(&self, hash: u64) -> InsertSlot

Searches for an empty or deleted bucket which is suitable for inserting a new element, returning the index for the new Bucket.

This function does not make any changes to the data part of the table, or any changes to the items or growth_left field of the table.

The table must have at least 1 empty or deleted bucket, otherwise this function will never return (will go into an infinite loop) for tables larger than the group width, or return an index outside of the table indices range if the table is less than the group width.

Note

Calling this function is always safe, but attempting to write data at the index returned by this function when the table is less than the group width and if there was not at least one empty bucket in the table will cause immediate undefined behavior. This is because in this case the function will return self.bucket_mask + 1 as an index due to the trailing EMPTY control bytes outside the table range.

fn find_inner( &self, hash: u64, eq: &mut dyn FnMut(usize) -> bool ) -> Option<usize>

Searches for an element in a table, returning the index of the found element. This uses dynamic dispatch to reduce the amount of code generated, but it is eliminated by LLVM optimizations.

This function does not make any changes to the data part of the table, or any changes to the items or growth_left field of the table.

The table must have at least 1 empty bucket, otherwise, if the eq: &mut dyn FnMut(usize) -> bool function does not return true, this function will also never return (will go into an infinite loop).

unsafe fn prepare_rehash_in_place(&mut self)

Prepares for rehashing data in place (that is, without allocating new memory). Converts all full index control bytes to DELETED and all DELETED control bytes to EMPTY, i.e. performs the following conversion:

• EMPTY control bytes -> EMPTY;
• DELETED control bytes -> EMPTY;
• FULL control bytes -> DELETED.

This function does not make any changes to the data parts of the table, or any changes to the the items or growth_left field of the table.

Safety

You must observe the following safety rules when calling this function:

• The RawTableInner has already been allocated;

• The caller of this function must convert the DELETED bytes back to FULL bytes when re-inserting them into their ideal position (which was impossible to do during the first insert due to tombstones). If the caller does not do this, then calling this function may result in a memory leak.

Calling this function on a table that has not been allocated results in undefined behavior.

See also Bucket::as_ptr method, for more information about of properly removing or saving data element from / into the RawTable / RawTableInner.

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

unsafe fn bucket_ptr(&self, index: usize, size_of: usize) -> *mut u8

unsafe fn data_end<T>(&self) -> NonNull<T>

fn probe_seq(&self, hash: u64) -> ProbeSeq

Returns an iterator-like object for a probe sequence on the table.

This iterator never terminates, but is guaranteed to visit each bucket group exactly once. The loop using probe_seq must terminate upon reaching a group containing an empty bucket.

unsafe fn record_item_insert_at( &mut self, index: usize, old_ctrl: u8, hash: u64 )

fn is_in_same_group(&self, i: usize, new_i: usize, hash: u64) -> bool

unsafe fn set_ctrl_h2(&self, index: usize, hash: u64)

Sets a control byte to the hash, and possibly also the replicated control byte at the end of the array.

This function does not make any changes to the data parts of the table, or any changes to the the items or growth_left field of the table.

Safety

The safety rules are directly derived from the safety rules for RawTableInner::set_ctrl method. Thus, in order to uphold the safety contracts for the method, you must observe the following rules when calling this function:

• The RawTableInner has already been allocated;

• The index must not be greater than the RawTableInner.bucket_mask, i.e. index <= RawTableInner.bucket_mask or, in other words, (index + 1) must be no greater than the number returned by the function RawTableInner::buckets.

Calling this function on a table that has not been allocated results in undefined behavior.

See also Bucket::as_ptr method, for more information about of properly removing or saving data element from / into the RawTable / RawTableInner.

unsafe fn replace_ctrl_h2(&self, index: usize, hash: u64) -> u8

Replaces the hash in the control byte at the given index with the provided one, and possibly also replicates the new control byte at the end of the array of control bytes, returning the old control byte.

This function does not make any changes to the data parts of the table, or any changes to the the items or growth_left field of the table.

Safety

The safety rules are directly derived from the safety rules for RawTableInner::set_ctrl_h2 and RawTableInner::ctrl methods. Thus, in order to uphold the safety contracts for both methods, you must observe the following rules when calling this function:

• The RawTableInner has already been allocated;

• The index must not be greater than the RawTableInner.bucket_mask, i.e. index <= RawTableInner.bucket_mask or, in other words, (index + 1) must be no greater than the number returned by the function RawTableInner::buckets.

Calling this function on a table that has not been allocated results in undefined behavior.

See also Bucket::as_ptr method, for more information about of properly removing or saving data element from / into the RawTable / RawTableInner.

unsafe fn set_ctrl(&self, index: usize, ctrl: u8)

Sets a control byte, and possibly also the replicated control byte at the end of the array.

This function does not make any changes to the data parts of the table, or any changes to the the items or growth_left field of the table.

Safety

You must observe the following safety rules when calling this function:

• The RawTableInner has already been allocated;

• The index must not be greater than the RawTableInner.bucket_mask, i.e. index <= RawTableInner.bucket_mask or, in other words, (index + 1) must be no greater than the number returned by the function RawTableInner::buckets.

Calling this function on a table that has not been allocated results in undefined behavior.

See also Bucket::as_ptr method, for more information about of properly removing or saving data element from / into the RawTable / RawTableInner.

unsafe fn ctrl(&self, index: usize) -> *mut u8

Returns a pointer to a control byte.

Safety

For the allocated RawTableInner, the result is Undefined Behavior, if the index is greater than the self.bucket_mask + 1 + Group::WIDTH. In that case, calling this function with index == self.bucket_mask + 1 + Group::WIDTH will return a pointer to the end of the allocated table and it is useless on its own.

Calling this function with index >= self.bucket_mask + 1 + Group::WIDTH on a table that has not been allocated results in Undefined Behavior.

So to satisfy both requirements you should always follow the rule that index < self.bucket_mask + 1 + Group::WIDTH

Calling this function on RawTableInner that are not already allocated is safe for read-only purpose.

See also Bucket::as_ptr() method, for more information about of properly removing or saving data element from / into the RawTable / RawTableInner.

fn buckets(&self) -> usize

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.

fn num_ctrl_bytes(&self) -> usize

fn is_empty_singleton(&self) -> bool

unsafe fn prepare_resize( &self, table_layout: TableLayout, capacity: usize, fallibility: Fallibility ) -> Result<ScopeGuard<Self, impl FnMut(&mut Self)>, TryReserveError>

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>

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.

unsafe fn resize_inner( &mut self, capacity: usize, hasher: &dyn Fn(&mut Self, usize) -> u64, fallibility: Fallibility, layout: TableLayout ) -> Result<(), TryReserveError>

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.

unsafe fn rehash_in_place( &mut self, hasher: &dyn Fn(&mut Self, usize) -> u64, size_of: usize, drop: Option<fn(_: *mut u8)> )

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.

unsafe fn free_buckets(&mut self, table_layout: TableLayout)

fn allocation_info(&self, table_layout: TableLayout) -> (NonNull<u8>, Layout)

fn clear_no_drop(&mut self)

Marks all table buckets as empty without dropping their contents.

unsafe fn erase(&mut self, index: usize)

Erases the Bucket’s control byte at the given index so that it does not triggered as full, decreases the items of the table and, if it can be done, increases self.growth_left.

This function does not actually erase / drop the Bucket itself, i.e. it does not make any changes to the data parts of the table. The caller of this function must take care to properly drop the data, otherwise calling this function may result in a memory leak.

Safety

You must observe the following safety rules when calling this function:

• The RawTableInner has already been allocated;

• It must be the full control byte at the given position;

• The index must not be greater than the RawTableInner.bucket_mask, i.e. index <= RawTableInner.bucket_mask or, in other words, (index + 1) must be no greater than the number returned by the function RawTableInner::buckets.

Calling this function on a table that has not been allocated results in undefined behavior.

Calling this function on a table with no elements is unspecified, but calling subsequent functions is likely to result in undefined behavior due to overflow subtraction (self.items -= 1 cause overflow when self.items == 0).

See also Bucket::as_ptr method, for more information about of properly removing or saving data element from / into the RawTable / RawTableInner.