Struct hashbrown::raw::Bucket

pub struct Bucket<T> {
    ptr: NonNull<T>,
}

A reference to a hash table bucket containing a T.

This is usually just a pointer to the element itself. However if the element is a ZST, then we instead track the index of the element in the table so that erase works properly.

Fields

ptr: NonNull<T>

Implementations

impl<T> Bucket<T>

const IS_ZERO_SIZED_TYPE: bool = _

unsafe fn from_base_index(base: NonNull<T>, index: usize) -> Self

Creates a Bucket that contain pointer to the data. The pointer calculation is performed by calculating the offset from given base pointer (convenience for base.as_ptr().sub(index)).

index is in units of T; e.g., an index of 3 represents a pointer offset of 3 * size_of::<T>() bytes.

If the T is a ZST, then we instead track the index of the element in the table so that erase works properly (return NonNull::new_unchecked((index + 1) as *mut T))

Safety

If mem::size_of::<T>() != 0, then the safety rules are directly derived from the safety rules for <*mut T>::sub method of *mut T and the safety rules of NonNull::new_unchecked function.

Thus, in order to uphold the safety contracts for the <*mut T>::sub method and NonNull::new_unchecked function, as well as for the correct logic of the work of this crate, the following rules are necessary and sufficient:

• the base pointer must not be dangling and must points to the end of the first value element from the data part of the table, i.e. must be the pointer that returned by RawTable::data_end or by RawTableInner::data_end<T>;

• index must not be greater than 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 RawTable::buckets or RawTableInner::buckets.

If mem::size_of::<T>() == 0, then the only requirement is that the index must not be greater than 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 RawTable::buckets or RawTableInner::buckets.

unsafe fn to_base_index(&self, base: NonNull<T>) -> usize

Calculates the index of a Bucket as distance between two pointers (convenience for base.as_ptr().offset_from(self.ptr.as_ptr()) as usize). The returned value is in units of T: the distance in bytes divided by core::mem::size_of::<T>().

If the T is a ZST, then we return the index of the element in the table so that erase works properly (return self.ptr.as_ptr() as usize - 1).

This function is the inverse of from_base_index.

Safety

If mem::size_of::<T>() != 0, then the safety rules are directly derived from the safety rules for <*const T>::offset_from method of *const T.

Thus, in order to uphold the safety contracts for <*const T>::offset_from method, as well as for the correct logic of the work of this crate, the following rules are necessary and sufficient:

• base contained pointer must not be dangling and must point to the end of the first element from the data part of the table, i.e. must be a pointer that returns by RawTable::data_end or by RawTableInner::data_end<T>;

• self also must not contain dangling pointer;

• both self and base must be created from the same RawTable (or RawTableInner).

If mem::size_of::<T>() == 0, this function is always safe.

pub fn as_ptr(&self) -> *mut T

Acquires the underlying raw pointer *mut T to data.

Note

If T is not Copy, do not use *mut T methods that can cause calling the destructor of T (for example the <*mut T>::drop_in_place method), because for properly dropping the data we also need to clear data control bytes. If we drop data, but do not clear data control byte it leads to double drop when RawTable goes out of scope.

If you modify an already initialized value, so Hash and Eq on the new T value and its borrowed form must match those for the old T value, as the map will not re-evaluate where the new value should go, meaning the value may become “lost” if their location does not reflect their state.

Examples

use core::hash::{BuildHasher, Hash};
use hashbrown::raw::{Bucket, RawTable};

type NewHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;

fn make_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
    use core::hash::Hasher;
    let mut state = hash_builder.build_hasher();
    key.hash(&mut state);
    state.finish()
}

let hash_builder = NewHashBuilder::default();
let mut table = RawTable::new();

let value = ("a", 100);
let hash = make_hash(&hash_builder, &value.0);

table.insert(hash, value.clone(), |val| make_hash(&hash_builder, &val.0));

let bucket: Bucket<(&str, i32)> = table.find(hash, |(k1, _)| k1 == &value.0).unwrap();

assert_eq!(unsafe { &*bucket.as_ptr() }, &("a", 100));

unsafe fn next_n(&self, offset: usize) -> Self

Create a new Bucket that is offset from the self by the given offset. The pointer calculation is performed by calculating the offset from self pointer (convenience for self.ptr.as_ptr().sub(offset)). This function is used for iterators.

offset is in units of T; e.g., a offset of 3 represents a pointer offset of 3 * size_of::<T>() bytes.

Safety

If mem::size_of::<T>() != 0, then the safety rules are directly derived from the safety rules for <*mut T>::sub method of *mut T and safety rules of NonNull::new_unchecked function.

Thus, in order to uphold the safety contracts for <*mut T>::sub method and NonNull::new_unchecked function, as well as for the correct logic of the work of this crate, the following rules are necessary and sufficient:

• self contained pointer must not be dangling;

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

If mem::size_of::<T>() == 0, then the only requirement is that the self.to_base_index() + ofset must not be greater than RawTableInner.bucket_mask, i.e. (self.to_base_index() + ofset) <= RawTableInner.bucket_mask or, in other words, self.to_base_index() + ofset + 1 must be no greater than the number returned by the function RawTable::buckets or RawTableInner::buckets.

pub(crate) unsafe fn drop(&self)

Executes the destructor (if any) of the pointed-to data.

Safety

See ptr::drop_in_place for safety concerns.

You should use RawTable::erase instead of this function, or be careful with calling this function directly, because for properly dropping the data we need also clear data control bytes. If we drop data, but do not erase data control byte it leads to double drop when RawTable goes out of scope.

pub(crate) unsafe fn read(&self) -> T

Reads the value from self without moving it. This leaves the memory in self unchanged.

Safety

See ptr::read for safety concerns.

You should use RawTable::remove instead of this function, or be careful with calling this function directly, because compiler calls its destructor when readed value goes out of scope. It can cause double dropping when RawTable goes out of scope, because of not erased data control byte.

pub(crate) unsafe fn write(&self, val: T)

Overwrites a memory location with the given value without reading or dropping the old value (like ptr::write function).

Safety

See ptr::write for safety concerns.

Note

Hash and Eq on the new T value and its borrowed form must match those for the old T value, as the map will not re-evaluate where the new value should go, meaning the value may become “lost” if their location does not reflect their state.

pub unsafe fn as_ref<'a>(&self) -> &'a T

Returns a shared immutable reference to the value.

Safety

See NonNull::as_ref for safety concerns.

Examples

use core::hash::{BuildHasher, Hash};
use hashbrown::raw::{Bucket, RawTable};

type NewHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;

fn make_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
    use core::hash::Hasher;
    let mut state = hash_builder.build_hasher();
    key.hash(&mut state);
    state.finish()
}

let hash_builder = NewHashBuilder::default();
let mut table = RawTable::new();

let value: (&str, String) = ("A pony", "is a small horse".to_owned());
let hash = make_hash(&hash_builder, &value.0);

table.insert(hash, value.clone(), |val| make_hash(&hash_builder, &val.0));

let bucket: Bucket<(&str, String)> = table.find(hash, |(k, _)| k == &value.0).unwrap();

assert_eq!(
    unsafe { bucket.as_ref() },
    &("A pony", "is a small horse".to_owned())
);

pub unsafe fn as_mut<'a>(&self) -> &'a mut T

Returns a unique mutable reference to the value.

Safety

See NonNull::as_mut for safety concerns.

Note

Hash and Eq on the new T value and its borrowed form must match those for the old T value, as the map will not re-evaluate where the new value should go, meaning the value may become “lost” if their location does not reflect their state.

Examples

use core::hash::{BuildHasher, Hash};
use hashbrown::raw::{Bucket, RawTable};

type NewHashBuilder = core::hash::BuildHasherDefault<ahash::AHasher>;

fn make_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
    use core::hash::Hasher;
    let mut state = hash_builder.build_hasher();
    key.hash(&mut state);
    state.finish()
}

let hash_builder = NewHashBuilder::default();
let mut table = RawTable::new();

let value: (&str, String) = ("A pony", "is a small horse".to_owned());
let hash = make_hash(&hash_builder, &value.0);

table.insert(hash, value.clone(), |val| make_hash(&hash_builder, &val.0));

let bucket: Bucket<(&str, String)> = table.find(hash, |(k, _)| k == &value.0).unwrap();

unsafe {
    bucket
        .as_mut()
        .1
        .push_str(" less than 147 cm at the withers")
};
assert_eq!(
    unsafe { bucket.as_ref() },
    &(
        "A pony",
        "is a small horse less than 147 cm at the withers".to_owned()
    )
);

Trait Implementations

impl<T> Clone for Bucket<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Send for Bucket<T>