pub struct RawTable<T, A = Global>where
A: Allocator,{ /* private fields */ }Expand description
A raw hash table with an unsafe API.
Implementations§
Source§impl<T> RawTable<T>
impl<T> RawTable<T>
Sourcepub const fn new() -> RawTable<T>
pub const fn new() -> RawTable<T>
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§impl<T, A> RawTable<T, A>where
A: Allocator,
impl<T, A> RawTable<T, A>where
A: Allocator,
Sourcepub const fn new_in(alloc: A) -> RawTable<T, A>
pub const fn new_in(alloc: A) -> RawTable<T, A>
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<RawTable<T, A>, Error>
pub fn try_with_capacity_in( capacity: usize, alloc: A, ) -> Result<RawTable<T, A>, Error>
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 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<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<bool, E>where
C: ?Sized,
pub fn erase_entry<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<bool, E>where
C: ?Sized,
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<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<T>, E>where
C: ?Sized,
pub fn remove_entry<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<T>, E>where
C: ?Sized,
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<C, E>(
&mut self,
cx: &mut C,
min_size: usize,
hasher: impl HasherFn<C, T, E>,
) -> Result<(), CustomError<E>>where
C: ?Sized,
pub fn shrink_to<C, E>(
&mut self,
cx: &mut C,
min_size: usize,
hasher: impl HasherFn<C, T, E>,
) -> Result<(), CustomError<E>>where
C: ?Sized,
Shrinks the table to fit max(self.len(), min_size) elements.
Sourcepub fn reserve<C, E>(
&mut self,
cx: &mut C,
additional: usize,
hasher: impl HasherFn<C, T, E>,
) -> Result<(), CustomError<E>>where
C: ?Sized,
pub fn reserve<C, E>(
&mut self,
cx: &mut C,
additional: usize,
hasher: impl HasherFn<C, T, E>,
) -> Result<(), CustomError<E>>where
C: ?Sized,
Ensures that at least additional items can be inserted into the table
without reallocation.
Sourcepub fn try_reserve<C, E>(
&mut self,
cx: &mut C,
additional: usize,
hasher: impl HasherFn<C, T, E>,
) -> Result<(), CustomError<E>>where
C: ?Sized,
pub fn try_reserve<C, E>(
&mut self,
cx: &mut C,
additional: usize,
hasher: impl HasherFn<C, T, E>,
) -> Result<(), CustomError<E>>where
C: ?Sized,
Tries to ensure that at least additional items can be inserted into
the table without reallocation.
Sourcepub fn insert<C, E>(
&mut self,
cx: &mut C,
hash: u64,
value: T,
hasher: impl HasherFn<C, T, E>,
) -> Result<Bucket<T>, CustomError<E>>where
C: ?Sized,
pub fn insert<C, E>(
&mut self,
cx: &mut C,
hash: u64,
value: T,
hasher: impl HasherFn<C, T, E>,
) -> Result<Bucket<T>, CustomError<E>>where
C: ?Sized,
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<C, E>(
&mut self,
cx: &mut C,
hash: u64,
value: T,
hasher: impl HasherFn<C, T, E>,
) -> Result<&mut T, CustomError<E>>where
C: ?Sized,
pub fn insert_entry<C, E>(
&mut self,
cx: &mut C,
hash: u64,
value: T,
hasher: impl HasherFn<C, T, E>,
) -> Result<&mut T, CustomError<E>>where
C: ?Sized,
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 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<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
hasher: impl HasherFn<C, T, E>,
) -> Result<Bucket<T>, ErrorOrInsertSlot<E>>where
C: ?Sized,
pub fn find_or_find_insert_slot<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
hasher: impl HasherFn<C, T, E>,
) -> Result<Bucket<T>, ErrorOrInsertSlot<E>>where
C: ?Sized,
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<C, E>(
&self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<Bucket<T>>, E>where
C: ?Sized,
pub fn find<C, E>(
&self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<Bucket<T>>, E>where
C: ?Sized,
Searches for an element in the table.
Sourcepub fn get<C, E>(
&self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<&T>, E>where
C: ?Sized,
pub fn get<C, E>(
&self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<&T>, E>where
C: ?Sized,
Gets a reference to an element in the table.
Sourcepub fn get_mut<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<&mut T>, E>where
C: ?Sized,
pub fn get_mut<C, E>(
&mut self,
cx: &mut C,
hash: u64,
eq: impl EqFn<C, T, E>,
) -> Result<Option<&mut T>, E>where
C: ?Sized,
Gets a mutable reference to an element in the table.
Sourcepub fn get_many_mut<C, E, const N: usize>(
&mut self,
cx: &mut C,
hashes: [u64; N],
eq: impl Fn(&mut C, usize, &T) -> Result<bool, E>,
) -> Result<Option<[&mut T; N]>, E>where
C: ?Sized,
pub fn get_many_mut<C, E, const N: usize>(
&mut self,
cx: &mut C,
hashes: [u64; N],
eq: impl Fn(&mut C, usize, &T) -> Result<bool, E>,
) -> Result<Option<[&mut T; N]>, E>where
C: ?Sized,
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<C, E, const N: usize>(
&mut self,
cx: &mut C,
hashes: [u64; N],
eq: impl Fn(&mut C, usize, &T) -> Result<bool, E>,
) -> Result<Option<[&mut T; N]>, E>where
C: ?Sized,
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.
§Safety
Caller must ensure that the raw iterator doesn’t outlive self.
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.