pub struct RawTable<T, A: Allocator + Clone = Global> { /* private fields */ }Expand description
A raw hash table with an unsafe API.
Implementations§
source§impl<T> RawTable<T, Global>
impl<T> RawTable<T, Global>
sourcepub const fn new() -> Self
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.
sourcepub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError>
pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError>
Attempts to allocate a new hash table with at least enough capacity for inserting the given number of elements without reallocating.
sourcepub fn with_capacity(capacity: usize) -> Self
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>
impl<T, A: Allocator + Clone> RawTable<T, A>
sourcepub const fn new_in(alloc: A) -> Self
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.
sourcepub fn try_with_capacity_in(
capacity: usize,
alloc: A,
) -> Result<Self, TryReserveError>
pub fn try_with_capacity_in( capacity: usize, alloc: A, ) -> Result<Self, TryReserveError>
Attempts to allocate a new hash table using the given allocator, with at least enough capacity for inserting the given number of elements without reallocating.
sourcepub fn with_capacity_in(capacity: usize, alloc: A) -> Self
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.
sourcepub unsafe fn data_end(&self) -> NonNull<T>
pub unsafe fn data_end(&self) -> NonNull<T>
Returns pointer to one past last element of data table.
sourcepub unsafe fn data_start(&self) -> NonNull<T>
pub unsafe fn data_start(&self) -> NonNull<T>
Returns pointer to start of data table.
sourcepub fn allocation_info(&self) -> (NonNull<u8>, Layout)
pub fn allocation_info(&self) -> (NonNull<u8>, Layout)
Return the information about memory allocated by the table.
RawTable allocates single memory block to store both data and metadata.
This function returns allocation size and alignment and the beginning of the area.
These are the arguments which will be passed to dealloc when the table is dropped.
This function might be useful for memory profiling.
sourcepub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize
pub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize
Returns the index of a bucket from a Bucket.
sourcepub unsafe fn bucket(&self, index: usize) -> Bucket<T>
pub unsafe fn bucket(&self, index: usize) -> Bucket<T>
Returns a pointer to an element in the table.
sourcepub unsafe fn erase(&mut self, item: Bucket<T>)
pub unsafe fn erase(&mut self, item: Bucket<T>)
Erases an element from the table, dropping it in place.
sourcepub fn erase_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> bool
pub fn erase_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> bool
Finds and erases an element from the table, dropping it in place. Returns true if an element was found.
sourcepub unsafe fn remove(&mut self, item: Bucket<T>) -> (T, InsertSlot)
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.
sourcepub fn remove_entry(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
) -> Option<T>
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.
sourcepub fn clear_no_drop(&mut self)
pub fn clear_no_drop(&mut self)
Marks all table buckets as empty without dropping their contents.
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Removes all elements from the table without freeing the backing memory.
sourcepub fn shrink_to(&mut self, min_size: usize, hasher: impl Fn(&T) -> u64)
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.
sourcepub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64)
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.
sourcepub fn try_reserve(
&mut self,
additional: usize,
hasher: impl Fn(&T) -> u64,
) -> Result<(), TryReserveError>
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.
sourcepub fn insert(
&mut self,
hash: u64,
value: T,
hasher: impl Fn(&T) -> u64,
) -> Bucket<T>
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.
sourcepub fn try_insert_no_grow(
&mut self,
hash: u64,
value: T,
) -> Result<Bucket<T>, T>
pub fn try_insert_no_grow( &mut self, hash: u64, value: T, ) -> Result<Bucket<T>, T>
Attempts to insert a new element without growing the table and return its raw bucket.
Returns an Err containing the given element if inserting it would require growing the
table.
This does not check if the given element already exists in the table.
sourcepub fn insert_entry(
&mut self,
hash: u64,
value: T,
hasher: impl Fn(&T) -> u64,
) -> &mut T
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.
sourcepub unsafe fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T>
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.
sourcepub unsafe fn replace_bucket_with<F>(&mut self, bucket: Bucket<T>, f: F) -> bool
pub unsafe fn replace_bucket_with<F>(&mut self, bucket: Bucket<T>, f: F) -> bool
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.
sourcepub fn find_or_find_insert_slot(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
hasher: impl Fn(&T) -> u64,
) -> Result<Bucket<T>, InsertSlot>
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.
sourcepub unsafe fn insert_in_slot(
&mut self,
hash: u64,
slot: InsertSlot,
value: T,
) -> Bucket<T>
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.
sourcepub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>>
pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>>
Searches for an element in the table.
sourcepub fn get(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>
pub fn get(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>
Gets a reference to an element in the table.
sourcepub fn get_mut(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
) -> Option<&mut T>
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.
sourcepub fn get_many_mut<const N: usize>(
&mut self,
hashes: [u64; N],
eq: impl FnMut(usize, &T) -> bool,
) -> Option<[&mut T; N]>
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.
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]>
sourcepub fn capacity(&self) -> usize
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.
sourcepub unsafe fn is_bucket_full(&self, index: usize) -> bool
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.
sourcepub unsafe fn iter(&self) -> RawIter<T> ⓘ
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.
sourcepub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<T> ⓘ
pub 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.
sourcepub fn drain(&mut self) -> RawDrain<'_, T, A> ⓘ
pub fn drain(&mut self) -> RawDrain<'_, T, A> ⓘ
Returns an iterator which removes all elements from the table without freeing the memory.
sourcepub unsafe fn drain_iter_from(&mut self, iter: RawIter<T>) -> RawDrain<'_, T, A> ⓘ
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.
sourcepub unsafe fn into_iter_from(self, iter: RawIter<T>) -> RawIntoIter<T, A> ⓘ
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.