Struct hashbrown::raw::inner::RawTableInner

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

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

Implementations

impl RawTableInner

const NEW: Self = _

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 accessed due to our load factor forcing us to always have at least 1 free bucket.

impl RawTableInner

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

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<A>( alloc: &A, table_layout: TableLayout, capacity: usize, fallibility: Fallibility ) -> Result<Self, TryReserveError>where A: Allocator,

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.

fn with_capacity<A>( alloc: &A, table_layout: TableLayout, capacity: usize ) -> Selfwhere A: Allocator,

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

Panics if the new capacity exceeds isize::MAX bytes and abort the program in case of allocation error. Use fallible_with_capacity instead if you want to handle memory allocation failure.

All the control bytes are initialized with the EMPTY bytes.

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

Fixes up an insertion slot returned by the RawTableInner::find_insert_slot_in_group method.

In tables smaller than the group width (self.buckets() < Group::WIDTH), trailing control bytes outside the range of the table are filled with EMPTY entries. These will unfortunately trigger a match of RawTableInner::find_insert_slot_in_group function. This is because the Some(bit) returned by group.match_empty_or_deleted().lowest_set_bit() after masking ((probe_seq.pos + bit) & self.bucket_mask) may point to a full bucket that is already occupied. We detect this situation here and 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 bytes).

If this function is called correctly, it is guaranteed to return InsertSlot with an index of an empty or deleted bucket in the range 0..self.buckets() (see Warning and Safety).

Warning

The table must have at least 1 empty or deleted bucket, otherwise if the table is less than the group width (self.buckets() < Group::WIDTH) this function returns an index outside of the table indices range 0..self.buckets() (0..=self.bucket_mask). Attempt to write data at that index will cause immediate undefined behavior.

Safety

The safety rules are directly derived from the safety rules for RawTableInner::ctrl method. Thus, in order to uphold those safety contracts, as well as for the correct logic of the work of this crate, the following rules are necessary and sufficient:

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

• This function must only be used on insertion slots found by RawTableInner::find_insert_slot_in_group (after the find_insert_slot_in_group function, but before insertion into the table).

• The index must not be greater than the self.bucket_mask, i.e. (index + 1) <= self.buckets() (this one is provided by the RawTableInner::find_insert_slot_in_group function).

Calling this function with an index not provided by RawTableInner::find_insert_slot_in_group may result in undefined behavior even if the index satisfies the safety rules of the RawTableInner::ctrl function (index < self.bucket_mask + 1 + Group::WIDTH).

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.

The function is guaranteed to return the index of an empty or deleted Bucket in the range 0..self.buckets() (0..=self.bucket_mask).

unsafe 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 (an empty or deleted Bucket index).

This uses dynamic dispatch to reduce the amount of code generated, but that 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 or deleted bucket, otherwise, if the eq: &mut dyn FnMut(usize) -> bool function does not return true, 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.

This function is guaranteed to provide the eq: &mut dyn FnMut(usize) -> bool function with only FULL buckets’ indices and return the index of the found element (as Ok(index)). If the element is not found and there is at least 1 empty or deleted Bucket in the table, the function is guaranteed to return InsertSlot with an index in the range 0..self.buckets(), but in any case, if this function returns InsertSlot, it will contain an index in the range 0..=self.buckets().

Safety

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

Attempt to write data at the InsertSlot returned by this function when the table is less than the group width and if there was not at least one empty or deleted 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.

unsafe fn prepare_insert_slot(&mut 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. Returns an index of that slot and the old control byte stored in the found index.

This function does not check if the given element exists in the table. Also, this function does not check if there is enough space in the table to insert a new element. Caller of the funtion must make ensure that the table has 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.

If there is at least 1 empty or deleted bucket in the table, the function is guaranteed to return an index in the range 0..self.buckets(), but in any case, if this function returns an index it will be in the range 0..=self.buckets().

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 the RawTableInner::set_ctrl_h2 and RawTableInner::find_insert_slot methods. Thus, in order to uphold the safety contracts for that methods, as well as for the correct logic of the work of this crate, you must observe the following rules when calling this function:

• The RawTableInner has already been allocated and has properly initialized control bytes otherwise calling this function results in undefined behavior.

• The caller of this function must ensure that the “data” parts of the table will have an entry in the returned index (matching the given hash) right after calling this function.

Attempt 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 or deleted 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.

The caller must independently increase the items field of the table, and also, if the old control byte was EMPTY, then decrease the table’s growth_left field, and do not change it if the old control byte was DELETED.

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

unsafe 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.

If there is at least 1 empty or deleted bucket in the table, the function is guaranteed to return InsertSlot with an index in the range 0..self.buckets(), but in any case, if this function returns InsertSlot, it will contain an index in the range 0..=self.buckets().

Safety

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

Attempt to write data at the InsertSlot returned by this function when the table is less than the group width and if there was not at least one empty or deleted 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.

unsafe 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).

This function is guaranteed to provide the eq: &mut dyn FnMut(usize) -> bool function with only FULL buckets’ indices and return the index of the found element as Some(index), so the index will always be in the range 0..self.buckets().

Safety

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

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.

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

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 iter<T>(&self) -> RawIter<T>

Returns an iterator over every element in the table.

Safety

If any of the following conditions are violated, the result is undefined behavior:

• The caller has to ensure that the RawTableInner outlives the RawIter. Because we cannot make the next method unsafe on the RawIter struct, we have to make the iter method unsafe.

• The RawTableInner must have properly initialized control bytes.

The type T must be the actual type of the elements stored in the table, otherwise using the returned RawIter results in undefined behavior.

unsafe fn drop_elements<T>(&mut self)

Executes the destructors (if any) of the values stored in the table.

Note

This function does not erase the control bytes of the table and does not make any changes to the items or growth_left fields of the table. If necessary, the caller of this function must manually set up these table fields, for example using the clear_no_drop function.

Be careful during calling this function, because drop function of the elements can panic, and this can leave table in an inconsistent state.

Safety

The type T must be the actual type of the elements stored in the table, otherwise calling this function may result in undefined behavior.

If T is a type that should be dropped and the table is not empty, calling this function more than once results in undefined behavior.

If T is not Copy, attempting to use values stored in the table after calling this function may result in undefined behavior.

It is safe to call this function on a table that has not been allocated, on a table with uninitialized control bytes, and on a table with no actual data but with Full control bytes if self.items == 0.

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

unsafe fn drop_inner_table<T, A: Allocator>( &mut self, alloc: &A, table_layout: TableLayout )

Executes the destructors (if any) of the values stored in the table and than deallocates the table.

Note

Calling this function automatically makes invalid (dangling) all instances of buckets (Bucket) and makes invalid (dangling) the ctrl field of the table.

This function does not make any changes to the bucket_mask, items or growth_left fields of the table. If necessary, the caller of this function must manually set up these table fields.

Safety

If any of the following conditions are violated, the result is undefined behavior:

• Calling this function more than once;

• The type T must be the actual type of the elements stored in the table.

• The alloc must be the same Allocator as the Allocator that was used to allocate this table.

• The table_layout must be the same TableLayout as the TableLayout that was used to allocate this table.

The caller of this function should pay attention to the possibility of the elements’ drop function panicking, because this:

• May leave the table in an inconsistent state;

• Memory is never deallocated, so a memory leak may occur.

Attempt to use the ctrl field of the table (dereference) after calling this function results in undefined behavior.

It is safe to call this function on a table that has not been allocated, on a table with uninitialized control bytes, and on a table with no actual data but with Full control bytes if self.items == 0.

See also RawTableInner::drop_elements or RawTableInner::free_buckets for more information.

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

Returns a pointer to an element in the table (convenience for Bucket::from_base_index(self.data_end::<T>(), index)).

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

Safety

If mem::size_of::<T>() != 0, then the safety rules are directly derived from the safety rules of the Bucket::from_base_index function. Therefore, when calling this function, the following safety rules must be observed:

• The table must already be allocated;

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

• The type T must be the actual type of the elements stored in the table, otherwise using the returned Bucket may result in undefined behavior.

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::buckets function, i.e. (index + 1) <= self.buckets().

If mem::size_of::<T>() != 0 then return a pointer to the `element` in the `data part` of the table
(we start counting from "0", so that in the expression T[n], the "n" index actually one less than
the "buckets" number of our `RawTableInner`, i.e. "n = RawTableInner::buckets() - 1"):

          `table.bucket(3).as_ptr()` returns a pointer that points here in the `data`
          part of the `RawTableInner`, i.e. to the start of T3 (see [`Bucket::as_ptr`])
                 |
                 |               `base = table.data_end::<T>()` points here
                 |               (to the start of CT0 or to the end of T0)
                 v                 v
[Pad], T_n, ..., |T3|, T2, T1, T0, |CT0, CT1, CT2, CT3, ..., CT_n, CTa_0, CTa_1, ..., CTa_m
                    ^                                              \__________  __________/
       `table.bucket(3)` returns a pointer that points                        \/
        here in the `data` part of the `RawTableInner`             additional control bytes
        (to the end of T3)                                          `m = Group::WIDTH - 1`

where: T0...T_n  - our stored data;
       CT0...CT_n - control bytes or metadata for `data`;
       CTa_0...CTa_m - additional control bytes (so that the search with loading `Group` bytes from
                       the heap works properly, even if the result of `h1(hash) & self.bucket_mask`
                       is equal to `self.bucket_mask`). See also `RawTableInner::set_ctrl` function.

P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.

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

Returns a raw *mut u8 pointer to the start of the data element in the table (convenience for self.data_end::<u8>().as_ptr().sub((index + 1) * size_of)).

The caller must ensure that the RawTableInner outlives the returned *mut u8, otherwise using it may result in undefined behavior.

Safety

If any of the following conditions are violated, the result is undefined behavior:

• The table must already be allocated;

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

• The size_of must be equal to the size of the elements stored in the table;

If mem::size_of::<T>() != 0 then return a pointer to the `element` in the `data part` of the table
(we start counting from "0", so that in the expression T[n], the "n" index actually one less than
the "buckets" number of our `RawTableInner`, i.e. "n = RawTableInner::buckets() - 1"):

          `table.bucket_ptr(3, mem::size_of::<T>())` returns a pointer that points here in the
          `data` part of the `RawTableInner`, i.e. to the start of T3
                 |
                 |               `base = table.data_end::<u8>()` points here
                 |               (to the start of CT0 or to the end of T0)
                 v                 v
[Pad], T_n, ..., |T3|, T2, T1, T0, |CT0, CT1, CT2, CT3, ..., CT_n, CTa_0, CTa_1, ..., CTa_m
                                                                   \__________  __________/
                                                                              \/
                                                                   additional control bytes
                                                                    `m = Group::WIDTH - 1`

where: T0...T_n  - our stored data;
       CT0...CT_n - control bytes or metadata for `data`;
       CTa_0...CTa_m - additional control bytes (so that the search with loading `Group` bytes from
                       the heap works properly, even if the result of `h1(hash) & self.bucket_mask`
                       is equal to `self.bucket_mask`). See also `RawTableInner::set_ctrl` function.

P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.

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

Returns pointer to one past last data element in the the table as viewed from the start point of the allocation (convenience for self.ctrl.cast()).

This function actually returns a pointer to the end of the data element at index “0” (zero).

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

Note

The type T must be the actual type of the elements stored in the table, otherwise using the returned NonNull<T> may result in undefined behavior.

                       `table.data_end::<T>()` returns pointer that points here
                       (to the end of `T0`)
                         ∨
[Pad], T_n, ..., T1, T0, |CT0, CT1, ..., CT_n|, CTa_0, CTa_1, ..., CTa_m
                          \________  ________/
                                   \/
      `n = buckets - 1`, i.e. `RawTableInner::buckets() - 1`

where: T0...T_n  - our stored data;
       CT0...CT_n - control bytes or metadata for `data`.
       CTa_0...CTa_m - additional control bytes, where `m = Group::WIDTH - 1` (so that the search
                       with loading `Group` bytes from the heap works properly, even if the result
                       of `h1(hash) & self.bucket_mask` is equal to `self.bucket_mask`). See also
                       `RawTableInner::set_ctrl` function.

P.S. `h1(hash) & self.bucket_mask` is the same as `hash as usize % self.buckets()` because the number
of buckets is a power of two, and `self.bucket_mask = self.buckets() - 1`.

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 prepare_insert_no_grow(&mut self, hash: u64) -> Result<usize, ()>

Returns the index of a bucket for which a value must be inserted if there is enough rooom in the table, otherwise returns error

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(&mut 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(&mut 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(&mut 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

fn prepare_resize<'a, A>( &self, alloc: &'a A, table_layout: TableLayout, capacity: usize, fallibility: Fallibility ) -> Result<ScopeGuard<Self, impl FnMut(&mut Self) + 'a>, TryReserveError>where A: Allocator,

Attempts to allocate a new hash table with at least enough capacity for inserting the given number of elements without reallocating, and return it inside ScopeGuard to protect against panic in the hash function.

Note

It is recommended (but not required):

• That the new table’s capacity be greater than or equal to self.items.

• The alloc is the same Allocator as the Allocator used to allocate this table.

• The table_layout is the same TableLayout as the TableLayout used to allocate this table.

If table_layout does not match the TableLayout that was used to allocate this table, then using mem::swap with the self and the new table returned by this function results in undefined behavior.

unsafe fn reserve_rehash_inner<A>( &mut self, alloc: &A, additional: usize, hasher: &dyn Fn(&mut Self, usize) -> u64, fallibility: Fallibility, layout: TableLayout, drop: Option<fn(_: *mut u8)> ) -> Result<(), TryReserveError>where A: Allocator,

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.

Safety

If any of the following conditions are violated, the result is undefined behavior:

• The alloc must be the same Allocator as the Allocator used to allocate this table.

• The layout must be the same TableLayout as the TableLayout used to allocate this table.

• The drop function (fn(*mut u8)) must be the actual drop function of the elements stored in the table.

• The RawTableInner must have properly initialized control bytes.

unsafe fn full_buckets_indices(&self) -> FullBucketsIndices

Returns an iterator over full buckets indices in the table.

Safety

Behavior is undefined if any of the following conditions are violated:

• The caller has to ensure that the RawTableInner outlives the FullBucketsIndices. Because we cannot make the next method unsafe on the FullBucketsIndices struct, we have to make the full_buckets_indices method unsafe.

• The RawTableInner must have properly initialized control bytes.

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

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.

Safety

If any of the following conditions are violated, the result is undefined behavior:

• The alloc must be the same Allocator as the Allocator used to allocate this table;

• The layout must be the same TableLayout as the TableLayout used to allocate this table;

• The RawTableInner must have properly initialized control bytes.

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

• If self.items != 0, calling of this function with capacity == 0 results in undefined behavior.

• If capacity_to_buckets(capacity) < Group::WIDTH and self.items > capacity_to_buckets(capacity) calling this function results in undefined behavior.

• If capacity_to_buckets(capacity) >= Group::WIDTH and self.items > capacity_to_buckets(capacity) calling this function are never return (will go into an infinite loop).

Note: It is recommended (but not required) that the new table’s capacity be greater than or equal to self.items. In case if capacity <= self.items this function can never return. See RawTableInner::find_insert_slot for more information.

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.

Safety

If any of the following conditions are violated, the result is undefined behavior:

• The size_of must be equal to the size of the elements stored in the table;

• The drop function (fn(*mut u8)) must be the actual drop function of the elements stored in the table.

• The RawTableInner has already been allocated;

• The RawTableInner must have properly initialized control bytes.

unsafe fn free_buckets<A>(&mut self, alloc: &A, table_layout: TableLayout)where A: Allocator,

Deallocates the table without dropping any entries.

Note

This function must be called only after drop_elements, else it can lead to leaking of memory. Also calling this function automatically makes invalid (dangling) all instances of buckets (Bucket) and makes invalid (dangling) the ctrl field of the table.

Safety

If any of the following conditions are violated, the result is Undefined Behavior:

• The RawTableInner has already been allocated;

• The alloc must be the same Allocator as the Allocator that was used to allocate this table.

• The table_layout must be the same TableLayout as the TableLayout that was used to allocate this table.

See also GlobalAlloc::dealloc or Allocator::deallocate for more information.

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

Returns a pointer to the allocated memory and the layout that was used to allocate the table.

Safety

Caller of this function must observe the following safety rules:

• The RawTableInner has already been allocated, otherwise calling this function results in undefined behavior

• The table_layout must be the same TableLayout as the TableLayout that was used to allocate this table. Failure to comply with this condition may result in undefined behavior.

See also GlobalAlloc::dealloc or Allocator::deallocate for more information.

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

Returns a pointer to the allocated memory and the layout that was used to allocate the table. If RawTableInner has not been allocated, this function return dangling pointer and () (unit) layout.

Safety

The table_layout must be the same TableLayout as the TableLayout that was used to allocate this table. Failure to comply with this condition may result in undefined behavior.

See also GlobalAlloc::dealloc or Allocator::deallocate for more information.

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.