Struct hashbrown::raw::RawTable

source ·
pub struct RawTable<T, A: Allocator + Clone = Global> {
    table: RawTableInner<A>,
    marker: PhantomData<T>,
}
Expand description

A raw hash table with an unsafe API.

Fields§

§table: RawTableInner<A>§marker: PhantomData<T>

Implementations§

source§

impl<T> RawTable<T, Global>

source

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

source

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

source§

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

source

const TABLE_LAYOUT: TableLayout = _

source

const DATA_NEEDS_DROP: bool = _

source

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

source

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.

source

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

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

source

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

source

pub fn allocator(&self) -> &A

Returns a reference to the underlying allocator.

source

unsafe fn free_buckets(&mut self)

Deallocates the table without dropping any entries.

source

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

Returns pointer to one past last element of data table.

source

pub unsafe fn data_start(&self) -> NonNull<T>

Returns pointer to start of data table.

source

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

Returns the index of a bucket from a Bucket.

source

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

Returns a pointer to an element in the table.

source

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

Erases an element from the table without dropping it.

source

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

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

source

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

Removes an element from the table, returning it.

This also returns an InsertSlot pointing to the newly free bucket.

source

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

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

source

pub fn clear_no_drop(&mut self)

Marks all table buckets as empty without dropping their contents.

source

pub fn clear(&mut self)

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

source

unsafe fn drop_elements(&mut self)

source

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

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

source

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

source

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

source

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.

source

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.

source

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

source

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

source

pub unsafe fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T>

Inserts a new element into the table, without growing the table.

There must be enough space in the table to insert the new element.

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

source

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

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

Returns true if the bucket still contains an element

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

source

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

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.

source

pub unsafe fn insert_in_slot( &mut self, hash: u64, slot: InsertSlot, value: T ) -> Bucket<T>

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

Safety

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

source

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

Searches for an element in the table.

source

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

Gets a reference to an element in the table.

source

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

source

pub fn get_many_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.

source

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]>

source

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

source

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

source

pub fn len(&self) -> usize

Returns the number of elements in the table.

source

pub fn is_empty(&self) -> bool

Returns true if the table contains no elements.

source

pub fn buckets(&self) -> usize

Returns the number of buckets in the table.

source

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

source

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

source

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

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

source

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

source

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

source

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

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

source§

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

source

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

Common code for clone and clone_from. Assumes:

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

Trait Implementations§

source§

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

source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
source§

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

Performs copy-assignment from source. Read more
source§

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

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

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

source§

fn drop(&mut self)

Executes the destructor for this type. Read more
source§

impl<T, A: Allocator + Clone> 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?
source§

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

Creates an iterator from a value. Read more
source§

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

source§

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

source§

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

source§

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

source§

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

source§

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

Auto Trait Implementations§

§

impl<T, A> RefUnwindSafe for RawTable<T, A>where A: RefUnwindSafe, T: RefUnwindSafe,

§

impl<T, A> Unpin for RawTable<T, A>where A: Unpin, T: Unpin,

§

impl<T, A> UnwindSafe for RawTable<T, A>where A: UnwindSafe, T: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.