|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
CRTP mixin providing common operations for open addressing hash tables. More...
#include <hashDry.H>
Classes | |
| class | Iterator |
| Bidirectional iterator for traversing hash table entries. More... | |
| struct | Stats |
| Statistics about hash table performance. More... | |
Public Member Functions | |
| constexpr float | get_lower_alpha () const noexcept |
| Returns the lower load factor threshold for automatic shrinking. | |
| constexpr float | get_upper_alpha () const noexcept |
| Returns the upper load factor threshold for automatic growing. | |
| void | copy_from_table (const HashTbl &other) |
| Copies all entries from another hash table. | |
| void | clean_table () |
| Removes all entries from the table without deallocating storage. | |
| void | check_resize_before_insert () |
| Checks if resize is needed before inserting and performs it. | |
| Key * | insert (const Key &key) |
| Inserts a key into the hash table (copy version). | |
| Key * | insert (Key &&key) |
| Inserts a key into the hash table (move version). | |
| Key * | search_or_insert (const Key &key) |
| Searches for a key, inserting it if not found (copy version). | |
| Key * | search_or_insert (Key &&key) |
| Searches for a key, inserting it if not found (move version). | |
| std::pair< Key *, bool > | contains_or_insert (const Key &key) |
| Searches for a key, inserting if not found, with existence flag (copy version). | |
| std::pair< Key *, bool > | contains_or_insert (Key &&key) |
| Searches for a key, inserting if not found, with existence flag (move version). | |
| Key * | append (const Key &key) |
| Alias for insert() (copy version). | |
| Key * | append (Key &&key) |
| Alias for insert() (move version). | |
| constexpr bool | has (const Key &key) const noexcept |
| Checks if a key exists in the table. | |
| constexpr bool | contains (const Key &key) const noexcept |
| Alias for has(). | |
| Key & | find (const Key &key) |
| Finds a key and returns a reference to it. | |
| const Key & | find (const Key &key) const |
| Finds a key and returns a const reference to it. | |
| const Key & | operator[] (const Key &key) const |
| Subscript operator for const access. | |
| const Key & | operator[] (const Key &key) |
| Subscript operator with insertion semantics. | |
| void | remove_ptr (Key *key) |
| Removes an entry by pointer. | |
| size_t | resize (size_t new_size) |
| Resizes the hash table to a new capacity. | |
| void | rehash () |
| Rebuilds the hash table with the same capacity. | |
| void | empty () |
| Clears all entries and resets to default capacity. | |
| constexpr size_t | size () const noexcept |
| Returns the number of entries in the table. | |
| constexpr bool | is_empty () const noexcept |
| Checks if the table is empty. | |
| constexpr size_t | capacity () const noexcept |
| Returns the current capacity of the table. | |
| DynList< Key > | keys () const |
| Returns a list containing all keys in the table. | |
| auto | items () const |
| Alias for keys(). | |
| void | print_stats (const Stats &stats) const |
| Prints statistics to standard output. | |
| constexpr float | current_alpha () const noexcept |
| Returns the current load factor (alpha). | |
Private Member Functions | |
| HashTbl * | me () |
| Returns a pointer to the derived class (CRTP pattern). | |
| const HashTbl * | const_me () const |
| Returns a const pointer to the derived class (CRTP pattern). | |
CRTP mixin providing common operations for open addressing hash tables.
This template class provides shared implementation for hash table operations that are common between ODhashTable (double hashing) and OLhashTable (linear probing). It uses CRTP to achieve static polymorphism, avoiding virtual function overhead while enabling code reuse.
| HashTbl | The derived hash table class (ODhashTable or OLhashTable). Must provide: allocate_bucket(), hard_allocate_bucket(), deallocate_bucket(), test_resize(), search(), table, len, N, lower_alpha, upper_alpha, with_resize, current_alpha(), Bucket. |
| Key | The type of keys stored in the table. |
with_resize is enabled in the derived class, the table automatically:lower_alpha threshold
|
inline |
Alias for insert() (copy version).
Provides STL-like naming for insert operations.
| key | The key to append/insert. |
Definition at line 389 of file hashDry.H.
References OhashCommon< HashTbl, Key >::insert().
|
inline |
Alias for insert() (move version).
Provides STL-like naming for insert operations.
| key | The key to append/insert (will be moved from). |
Definition at line 402 of file hashDry.H.
References OhashCommon< HashTbl, Key >::insert().
|
inlineconstexprnoexcept |
Returns the current capacity of the table.
Definition at line 622 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
Referenced by demo_odhash(), and OhashCommon< HashTbl, Key >::print_stats().
|
inline |
Checks if resize is needed before inserting and performs it.
Called before each insert operation to ensure there is at least one empty bucket available (required as a sentinel for probing). If automatic resizing is enabled and the table is nearly full, doubles the table capacity.
Definition at line 180 of file hashDry.H.
References Aleph::maps(), OhashCommon< HashTbl, Key >::me(), N, and Primes::next_prime().
Referenced by OhashCommon< HashTbl, Key >::contains_or_insert(), OhashCommon< HashTbl, Key >::contains_or_insert(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::search_or_insert(), and OhashCommon< HashTbl, Key >::search_or_insert().
Removes all entries from the table without deallocating storage.
Resets all buckets to their initial empty state and sets the entry count to zero. The table capacity remains unchanged.
Definition at line 166 of file hashDry.H.
References OhashCommon< HashTbl, Key >::me().
Referenced by Aleph::ODhashTable< Key, Cmp >::operator=(), and Aleph::OLhashTable< Key, Cmp >::operator=().
|
inlineprivate |
Returns a const pointer to the derived class (CRTP pattern).
Definition at line 110 of file hashDry.H.
References Aleph::maps().
Referenced by OhashCommon< HashTbl, Key >::capacity(), OhashCommon< HashTbl, Key >::current_alpha(), OhashCommon< HashTbl, Key >::get_lower_alpha(), OhashCommon< HashTbl, Key >::get_upper_alpha(), OhashCommon< HashTbl, Key >::has(), OhashCommon< HashTbl, Key >::is_empty(), OhashCommon< HashTbl, Key >::keys(), OhashCommon< HashTbl, Key >::print_stats(), and OhashCommon< HashTbl, Key >::size().
|
inlineconstexprnoexcept |
Alias for has().
| key | The key to search for. |
Definition at line 425 of file hashDry.H.
References OhashCommon< HashTbl, Key >::has().
|
inline |
Searches for a key, inserting if not found, with existence flag (copy version).
Similar to search_or_insert(), but also indicates whether the key was already present in the table.
| key | The key to search for or insert. |
Definition at line 332 of file hashDry.H.
References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().
|
inline |
Searches for a key, inserting if not found, with existence flag (move version).
Similar to search_or_insert(), but also indicates whether the key was already present in the table.
| key | The key to search for or insert (moved from on insert). |
Definition at line 365 of file hashDry.H.
References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().
|
inline |
Copies all entries from another hash table.
Copies all BUSY entries from the source table to this table. This table must be empty and have sufficient capacity.
| other | Source hash table to copy from. |
Definition at line 143 of file hashDry.H.
References Aleph::DynList< T >::insert(), Aleph::maps(), OhashCommon< HashTbl, Key >::me(), and N.
Referenced by Aleph::ODhashTable< Key, Cmp >::ODhashTable(), Aleph::OLhashTable< Key, Cmp >::OLhashTable(), Aleph::ODhashTable< Key, Cmp >::operator=(), and Aleph::OLhashTable< Key, Cmp >::operator=().
|
inlineconstexprnoexcept |
Returns the current load factor (alpha).
The load factor is the ratio of stored entries to table capacity. A higher load factor means more efficient memory usage but potentially longer probe sequences.
Definition at line 959 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
Referenced by OhashCommon< HashTbl, Key >::remove_ptr().
Clears all entries and resets to default capacity.
Removes all entries and resets the table to its default initial capacity (Primes::DefaultPrime).
Definition at line 601 of file hashDry.H.
References Primes::DefaultPrime, and OhashCommon< HashTbl, Key >::me().
|
inline |
Finds a key and returns a reference to it.
Searches for the key and returns a reference to it. If the key is not found, throws an exception.
| key | The key to find. |
| std::domain_error | If the key is not found. |
Definition at line 438 of file hashDry.H.
References ah_domain_error_if, and OhashCommon< HashTbl, Key >::me().
Referenced by OhashCommon< HashTbl, Key >::find(), and OhashCommon< HashTbl, Key >::operator[]().
|
inline |
Finds a key and returns a const reference to it.
Const version of find().
| key | The key to find. |
| std::domain_error | If the key is not found. |
Definition at line 456 of file hashDry.H.
References OhashCommon< HashTbl, Key >::find().
|
inlineconstexprnoexcept |
Returns the lower load factor threshold for automatic shrinking.
When automatic resizing is enabled and the load factor drops below this value after a removal, the table shrinks.
Definition at line 121 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
|
inlineconstexprnoexcept |
Returns the upper load factor threshold for automatic growing.
When automatic resizing is enabled and the load factor would exceed this value, the table grows before insertion.
Definition at line 130 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
|
inlineconstexprnoexcept |
Checks if a key exists in the table.
| key | The key to search for. |
Definition at line 414 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
Referenced by OhashCommon< HashTbl, Key >::contains().
|
inline |
Inserts a key into the hash table (copy version).
Attempts to insert a copy of the key. If the key already exists, the insertion fails and nullptr is returned.
| key | The key to insert. |
Definition at line 203 of file hashDry.H.
References OhashCommon< HashTbl, Key >::check_resize_before_insert(), and OhashCommon< HashTbl, Key >::me().
Referenced by OhashCommon< HashTbl, Key >::append(), OhashCommon< HashTbl, Key >::append(), demo_odhash(), demo_performance(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().
|
inline |
Inserts a key into the hash table (move version).
Attempts to insert a key using move semantics. If the key already exists, the insertion fails and nullptr is returned.
| key | The key to insert (will be moved from on success). |
Definition at line 231 of file hashDry.H.
References OhashCommon< HashTbl, Key >::check_resize_before_insert(), and OhashCommon< HashTbl, Key >::me().
|
inlineconstexprnoexcept |
Checks if the table is empty.
Definition at line 617 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
Alias for keys().
Definition at line 906 of file hashDry.H.
References OhashCommon< HashTbl, Key >::keys().
|
inline |
Returns a list containing all keys in the table.
Creates and returns a DynList containing copies of all keys stored in the hash table.
Definition at line 897 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me(), and Aleph::maps().
Referenced by OhashCommon< HashTbl, Key >::items().
Returns a pointer to the derived class (CRTP pattern).
Definition at line 105 of file hashDry.H.
References Aleph::maps().
Referenced by OhashCommon< HashTbl, Key >::check_resize_before_insert(), OhashCommon< HashTbl, Key >::clean_table(), OhashCommon< HashTbl, Key >::contains_or_insert(), OhashCommon< HashTbl, Key >::contains_or_insert(), OhashCommon< HashTbl, Key >::copy_from_table(), OhashCommon< HashTbl, Key >::empty(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::rehash(), OhashCommon< HashTbl, Key >::remove_ptr(), OhashCommon< HashTbl, Key >::resize(), OhashCommon< HashTbl, Key >::search_or_insert(), and OhashCommon< HashTbl, Key >::search_or_insert().
|
inline |
Subscript operator with insertion semantics.
Returns a reference to the key. If the key doesn't exist, it is inserted first.
| key | The key to access or insert. |
Definition at line 482 of file hashDry.H.
References OhashCommon< HashTbl, Key >::search_or_insert().
|
inline |
Subscript operator for const access.
Returns a const reference to the key. Equivalent to find().
| key | The key to access. |
| std::domain_error | If the key is not found. |
Definition at line 469 of file hashDry.H.
References OhashCommon< HashTbl, Key >::find().
|
inline |
Prints statistics to standard output.
Displays formatted statistics including capacity, size, bucket states, load factor, and probe length distribution.
| stats | Statistics object to print. |
Definition at line 938 of file hashDry.H.
References OhashCommon< HashTbl, Key >::capacity(), OhashCommon< HashTbl, Key >::const_me(), OhashCommon< HashTbl, Key >::Stats::lens, OhashCommon< HashTbl, Key >::Stats::max_len, OhashCommon< HashTbl, Key >::Stats::num_busy, OhashCommon< HashTbl, Key >::Stats::num_deleted, OhashCommon< HashTbl, Key >::Stats::num_empty, OhashCommon< HashTbl, Key >::size(), and Aleph::DynArray< T >::size().
Rebuilds the hash table with the same capacity.
Creates a new internal table with the same capacity and re-inserts all entries. This can help improve performance after many deletions by eliminating deleted bucket markers.
Definition at line 569 of file hashDry.H.
References Aleph::maps(), OhashCommon< HashTbl, Key >::me(), and N.
|
inline |
Removes an entry by pointer.
Removes the entry pointed to by the given pointer. The pointer must have been obtained from this table (via insert, search, etc.).
If automatic resizing is enabled and the load factor drops below the lower threshold, the table is shrunk.
| key | Pointer to the key to remove (must be in this table). |
Definition at line 502 of file hashDry.H.
References OhashCommon< HashTbl, Key >::current_alpha(), Aleph::maps(), OhashCommon< HashTbl, Key >::me(), Primes::next_prime(), and OhashCommon< HashTbl, Key >::resize().
|
inline |
Resizes the hash table to a new capacity.
Changes the table capacity to the specified size and rehashes all entries. The new size must be large enough to hold all current entries plus at least one empty sentinel bucket.
| new_size | The new capacity (should be a prime number). |
| std::overflow_error | If new_size is too small for current entries. |
Definition at line 524 of file hashDry.H.
References ah_overflow_error_if, Aleph::maps(), OhashCommon< HashTbl, Key >::me(), and N.
Referenced by OhashCommon< HashTbl, Key >::remove_ptr().
|
inline |
Searches for a key, inserting it if not found (copy version).
If the key exists, returns a pointer to it. Otherwise, inserts a copy of the key and returns a pointer to the newly inserted key.
| key | The key to search for or insert. |
Definition at line 259 of file hashDry.H.
References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().
Referenced by OhashCommon< HashTbl, Key >::operator[]().
|
inline |
Searches for a key, inserting it if not found (move version).
If the key exists, returns a pointer to it. Otherwise, inserts the key using move semantics and returns a pointer to the newly inserted key.
| key | The key to search for or insert (moved from on insert). |
Definition at line 291 of file hashDry.H.
References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().
|
inlineconstexprnoexcept |
Returns the number of entries in the table.
Definition at line 612 of file hashDry.H.
References OhashCommon< HashTbl, Key >::const_me().
Referenced by demo_odhash(), demo_performance(), OhashCommon< HashTbl, Key >::print_stats(), TEST(), TEST(), and TEST().