Struct HashTable 

pub struct HashTable<K, P, B = SinglyLinkedList<P>, H = DefaultHashTraits>
where
    P: PtrTraits,
    P::Target: HashTableKeyable<K>,
    B: HashTableBucket<P>,
    K: Eq,
    H: HashTraits<K>,
{ /* private fields */ }

An intrusive, unordered, associative hash table container.

Bookkeeping & Memory Storage

Objects are stored in an array of buckets, each of which is an intrusive linked list (see “Buckets” below). The bookkeeping storage required to link an object into its bucket (a list node) lives on the object itself, so adding or removing members to/from the container never requires allocation. The only allocation performed by the hash table is the one-time allocation of its bucket array, which is fallible.

The hash table stores pointers to the objects, not the objects themselves, and is parameterized based on the specific pointer wrapper to be stored (P). Supported pointer wrappers are:

• *mut T : Raw unmanaged pointers.
• UniquePtr<T> : Unique managed pointers.
• RefPtr<T> : Shared managed pointers to reference-counted objects.

Buckets

The type of the buckets is selected by the B parameter (see HashTableBucket):

• SinglyLinkedList<P, Tag> (the default): Objects need a SinglyLinkedListNode, which is a single pointer. Erasing an element by reference searches its bucket.
• DoublyLinkedList<P, Tag>: Objects need a DoublyLinkedListNode, which is two pointers. Erasing an element by reference runs in constant time.

The Tag of the bucket type selects the node used by the hash table, which allows an object to be in a hash table and in other containers at the same time.

Keys & Hashing

Objects expose their key of type K through HashTableKeyable<K>, and keys are compared using K: Eq. Duplicate keys are not allowed. The bucket an object belongs to is the hash of its key, as computed by the hash traits H (see HashTraits, which default to DefaultHashTraits), modulo the bucket count of the hash table.

The key of an object must not change while the object is in the hash table.

Bucket Storage & Initialization

The bucket count of a HashTable is chosen at runtime. A hash table may be created with its bucket storage in a single step using try_new, or created in an “invalid” (uninitialized) state using the infallible const fn new and later initialized exactly once using try_init (the analog of C++’s HashTableOption::DelayedInit followed by Init). An uninitialized hash table is empty and may be cleared, iterated, or dropped, but it must be initialized before any keyed operation (insert, find, erase, …) is performed on it.

The bucket storage is heap allocated and its buckets never move, so unlike the other intrusive containers in this crate, a HashTable itself does not need to be pinned (even with DoublyLinkedList buckets) and may be freely moved.

Bucket storage with a bucket count fixed at compile time is not currently supported.

Lifecycle Management

• Managed Pointers (UniquePtr/RefPtr): The hash table holds ownership references of elements. Clearing the hash table or dropping it automatically releases references, which may destruct the elements if it was their last reference.

• Unmanaged Pointers (*mut T): The hash table performs no lifecycle management. It is up to the caller to ensure elements outlive the hash table and are freed correctly. As a safety check, a hash table of unmanaged pointers will debug-assert if it is dropped with elements still inside.

Complexity

Insert, find and erase-by-key run in time proportional to the length of the bucket the key hashes to. Direct erase operations (where a reference to the element to be erased is already known, e.g. erase_element and HashTableCursorMut::erase) run in constant time with DoublyLinkedList buckets, and in time proportional to the length of the bucket with SinglyLinkedList buckets. len and is_empty run in constant time.

---

Example: Hash table of unique managed pointers

use fbl::{
    DoublyLinkedList, DoublyLinkedListContainable, DoublyLinkedListNode, HashTable,
    HashTableKeyable, Recyclable, SinglyLinkedListContainable, SinglyLinkedListNode, UniquePtr,
};

#[derive(SinglyLinkedListContainable, DoublyLinkedListContainable, Recyclable)]
struct Foo {
    id: u64,
    #[sll_node]
    sll_node: SinglyLinkedListNode<Foo>,
    #[dll_node]
    dll_node: DoublyLinkedListNode<Foo>,
}

impl Foo {
    fn new(id: u64) -> UniquePtr<Foo> {
        let sll_node = SinglyLinkedListNode::new();
        let dll_node = DoublyLinkedListNode::new();
        UniquePtr::try_new(Foo { id, sll_node, dll_node }).unwrap()
    }
}

impl HashTableKeyable<u64> for Foo {
    type Key<'a> = u64;
    fn get_key(&self) -> u64 {
        self.id
    }
}

// A hash table with the default `SinglyLinkedList` buckets.
let mut table = HashTable::<u64, UniquePtr<Foo>>::try_new(37).unwrap();
table.insert(Foo::new(1));
table.insert(Foo::new(2));

assert_eq!(table.len(), 2);
assert_eq!(table.find(&1).map(|foo| foo.id), Some(1));

let foo = table.erase(&2).unwrap();
assert_eq!(foo.id, 2);

// A hash table with `DoublyLinkedList` buckets, which can erase an element by reference in
// constant time.
type DllBuckets = DoublyLinkedList<UniquePtr<Foo>>;
let mut dll_table = HashTable::<u64, UniquePtr<Foo>, DllBuckets>::try_new(37).unwrap();
dll_table.insert(foo);
let foo: *const Foo = dll_table.find(&2).unwrap();
// SAFETY: `foo` is in `dll_table` and its key has not changed.
assert!(unsafe { dll_table.erase_element(&*foo) }.is_some());

// Dropping the tables automatically drops the remaining unique pointers.

Implementations

impl<K, P, B, H> HashTable<K, P, B, H>

where P: PtrTraits, P::Target: HashTableKeyable<K>, B: HashTableBucket<P>, K: Eq, H: HashTraits<K>,

pub const fn new() -> Self

Creates a new, uninitialized hash table without any bucket storage.

The hash table must be initialized with try_init before any keyed operation is performed on it. This is the analog of constructing a C++ fbl::HashTable with HashTableOption::DelayedInit.

pub fn try_new(bucket_count: usize) -> Result<Self, AllocError>

Creates a new, empty hash table with bucket_count buckets.

Returns an error if the bucket storage could not be allocated.

Panics

Panics if bucket_count is zero.

pub fn try_init(&mut self, bucket_count: usize) -> Result<(), AllocError>

Initializes a hash table created with new with bucket_count buckets.

Initialization is not idempotent and must be performed exactly once before use. Returns an error if the bucket storage could not be allocated, in which case the hash table remains uninitialized.

Panics

Panics if bucket_count is zero, or if the hash table has already been initialized.

pub fn is_initialized(&self) -> bool

Returns true if the hash table has been given its bucket storage.

pub fn bucket_count(&self) -> usize

Returns the number of buckets in the hash table, or zero if it has not been initialized.

pub fn len(&self) -> usize

Returns the number of elements in the hash table.

pub fn is_empty(&self) -> bool

Returns true if the hash table contains no elements.

pub fn insert(&mut self, ptr: P)

where P: ManagedPtr,

Inserts an element into the hash table.

Duplicate keys are disallowed. If there might already be an element with the same key in the hash table, use insert_or_find or insert_or_replace instead.

For raw pointers, use insert_raw instead.

Panics

Panics if the hash table has not been initialized. Panics in debug builds if the object is already in a container, or if an element with the same key is already in the hash table.

pub unsafe fn insert_raw(&mut self, ptr: P)

Inserts an element into the hash table.

Duplicate keys are disallowed. If there might already be an element with the same key in the hash table, use insert_or_find_raw or insert_or_replace_raw instead.

Panics

Panics if the hash table has not been initialized. Panics in debug builds if the object is already in a container, or if an element with the same key is already in the hash table.

Safety

The caller must ensure that ptr is a valid pointer to an object that is not currently in any container, and that the object outlives the reference from the hash table.

pub fn insert_or_find( &mut self, ptr: P, ) -> HashTableInsertOrFindResult<'_, K, P, B, H>

where P: ManagedPtr,

Inserts the element pointed to by ptr if no element with the same key is already in the hash table, or finds the element that ptr collided with instead.

For raw pointers, use insert_or_find_raw instead.

Returns

• Ok(()) if there was no collision and the element was successfully inserted. In this case, the hash table takes ownership of ptr.
• Err((ptr, cursor)) if there was a collision. In this case, ptr is not consumed and is returned to the caller, along with a cursor positioned at the colliding element already in the hash table.

Panics

Panics if the hash table has not been initialized. Panics in debug builds if the object is already in a container.

pub unsafe fn insert_or_find_raw( &mut self, ptr: P, ) -> HashTableInsertOrFindResult<'_, K, P, B, H>

Inserts the element pointed to by ptr if no element with the same key is already in the hash table, or finds the element that ptr collided with instead.

See insert_or_find for a description of the return value.

Panics

Panics if the hash table has not been initialized. Panics in debug builds if the object is already in a container.

Safety

The caller must ensure that ptr is a valid pointer to an object that is not currently in any container, and that the object outlives the reference from the hash table.

pub fn insert_or_replace(&mut self, ptr: P) -> Option<P>

where P: ManagedPtr,

Finds the element in the hash table with the same key as *ptr and replaces it with ptr, returning the element which was replaced.

If no element in the hash table shares a key with *ptr, simply adds ptr to the hash table and returns None. In both cases, ptr is consumed.

For raw pointers, use insert_or_replace_raw instead.

Panics

Panics if the hash table has not been initialized. Panics in debug builds if the object is already in a container.

pub unsafe fn insert_or_replace_raw(&mut self, ptr: P) -> Option<P>

Finds the element in the hash table with the same key as *ptr and replaces it with ptr, returning the element which was replaced.

If no element in the hash table shares a key with *ptr, simply adds ptr to the hash table and returns None. In both cases, ptr is consumed.

Panics

Panics if the hash table has not been initialized. Panics in debug builds if the object is already in a container.

Safety

The caller must ensure that ptr is a valid pointer to an object that is not currently in any container, and that the object outlives the reference from the hash table.

pub fn find(&self, key: &K) -> Option<&P::Target>

Finds the element in the hash table with the given key.

Panics

Panics if the hash table has not been initialized.

pub fn find_cursor(&mut self, key: &K) -> HashTableCursorMut<'_, K, P, B, H>

Finds the element in the hash table with the given key and returns a cursor positioned at it.

If the key is not found, the returned cursor is not positioned at any element (i.e. cursor.get() returns None).

Panics

Panics if the hash table has not been initialized.

pub fn erase(&mut self, key: &K) -> Option<P>

Erases the element with the given key from the hash table, returning it.

Returns None if no element in the hash table has the given key.

Panics

Panics if the hash table has not been initialized.

pub unsafe fn erase_element(&mut self, obj: &P::Target) -> Option<P>

Erases the given element from the hash table, returning it.

Returns None if obj is not in any container. This operation runs in constant time with DoublyLinkedList buckets, and in time proportional to the length of the bucket of obj with SinglyLinkedList buckets.

Panics

Panics if the hash table has not been initialized.

Safety

The caller must ensure that obj is either not in any container, or is currently in this hash table instance and its key has not changed since it was inserted.

pub fn erase_if<F>(&mut self, f: F) -> Option<P>

where F: FnMut(&P::Target) -> bool,

Finds the first element of the hash table which satisfies the predicate, erases it from the hash table, and returns it. Returns None if no element satisfies the predicate.

pub fn find_if<F>(&self, f: F) -> Option<&P::Target>

where F: FnMut(&P::Target) -> bool,

Finds the first element of the hash table which satisfies the predicate. Returns None if no element satisfies the predicate.

pub fn clear(&mut self)

Removes all elements from the hash table.

For managed pointer types, this releases all of the references held by the hash table to the objects which were in it. Clearing an uninitialized hash table is a no-op.

pub fn iter(&self) -> HashTableIter<'_, P, B>

Returns an iterator over the elements of the hash table, in an unspecified order.

Trait Implementations

impl<K, P, B, H> Debug for HashTable<K, P, B, H>

where P: PtrTraits, P::Target: HashTableKeyable<K> + Debug, B: HashTableBucket<P>, K: Eq, H: HashTraits<K>,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, P, B, H> Default for HashTable<K, P, B, H>

where P: PtrTraits, P::Target: HashTableKeyable<K>, B: HashTableBucket<P>, K: Eq, H: HashTraits<K>,

fn default() -> Self

Creates a new, uninitialized hash table. See HashTable::new.

impl<K, P, B, H> Drop for HashTable<K, P, B, H>

where P: PtrTraits, P::Target: HashTableKeyable<K>, B: HashTableBucket<P>, K: Eq, H: HashTraits<K>,

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<'a, K, P, B, H> IntoIterator for &'a HashTable<K, P, B, H>

where P: PtrTraits, P::Target: HashTableKeyable<K>, B: HashTableBucket<P>, K: Eq, H: HashTraits<K>,

type Item = &'a <P as PtrTraits>::Target

The type of the elements being iterated over.

type IntoIter = HashTableIter<'a, P, B>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.