Implements hashing into buckets for quick object access. More...
#include <hash_table.h>
Public Types | |
| enum | outcomes { IS_NEW = basis::common::IS_NEW , EXISTING = basis::common::EXISTING } |
| typedef bool | apply_function(const key_type &key, contents ¤t, void *data_link) |
| the "apply_function" is what a user of the "apply" method must supply. More... | |
Public Member Functions | |
| hash_table (const hashing_algorithm &hasher, int estimated_elements) | |
| Creates a table using the "hasher" that is ready to store "estimated_elements". More... | |
| virtual | ~hash_table () |
| destroys any objects left in the hash_table. More... | |
| DEFINE_CLASS_NAME ("hash_table") | |
| void | rehash (int estimated_elements) |
| resizes the hashing structures to optimise for a new size of "estimated_elements". More... | |
| int | elements () const |
| the number of valid items we found by traversing the hash table. More... | |
| int | estimated_elements () const |
| returns the size of table we're optimized for. More... | |
| basis::outcome | add (const key_type &key, contents *to_store) |
| Stores "to_store" into the table given its "key" for hashing. More... | |
| basis::outcome | fast_dangerous_add (const key_type &key, contents *to_store) |
| Like the add method above, but doesn't check for duplicates. More... | |
| bool | find (const key_type &key, contents *&item_found) const |
| locates the item specified by the "key", if possible. More... | |
| contents * | find (const key_type &key) const |
| simplified form of above find() method. More... | |
| contents * | acquire (const key_type &key) |
| retrieves the contents held for "key" out of the table. More... | |
| bool | zap (const key_type &key) |
| removes the entry with the "key" specified. More... | |
| void | reset () |
| removes all entries in the table and returns it to a pristine state. More... | |
| void | apply (apply_function *to_apply, void *data_link) |
| Invokes the function "to_apply" on every entry in the table. More... | |
| basis::outcome | add (key_type *key, contents *to_store, bool check_dupes=true) |
| specialized add for a pre-existing pointer "key". More... | |
| bool | verify () const |
| returns true if the hash table is internally consistent. More... | |
| internal_hash_array< key_type, contents > & | table_access () const |
| special accessor for the copy_hash_table method only. More... | |
 Public Member Functions inherited from basis::nameable | |
| virtual const char * | class_name () const =0 |
| Returns the bare name of this class as a constant character pointer. More... | |
Static Public Member Functions | |
| static int | calculate_num_slots (int estimated_elements) |
| a helper method that lets us know what n is for how many 2^n slots we should have. More... | |
Detailed Description
template<class key_type, class contents>
class structures::hash_table< key_type, contents >
Implements hashing into buckets for quick object access.
The buckets are currently simple lists, but if the hashing algorithm is well chosen, then that's not a major problem. This makes lookups a lot faster than a linear search, but no particular performance guarantees are made at this time.
Definition at line 69 of file hash_table.h.
Member Typedef Documentation
◆ apply_function
| typedef bool structures::hash_table< key_type, contents >::apply_function(const key_type &key, contents ¤t, void *data_link) |
the "apply_function" is what a user of the "apply" method must supply.
the function will be called on every item in the table unless one of the invocations returns false; this causes the apply process to stop. the "data_link" provides a way for the function to refer back to an parent class of some sort.
Definition at line 142 of file hash_table.h.
Member Enumeration Documentation
◆ outcomes
| enum structures::hash_table::outcomes |
| Enumerator | |
|---|---|
| IS_NEW | |
| EXISTING | |
Definition at line 89 of file hash_table.h.
Constructor & Destructor Documentation
◆ hash_table()
| structures::hash_table< key_type, contents >::hash_table | ( | const hashing_algorithm & | hasher, |
| int | estimated_elements | ||
| ) |
Creates a table using the "hasher" that is ready to store "estimated_elements".
the "hasher" must provide the hashing algorithm for the two types specified. if the implementation is thread safe, then one object can be constructed to use with all the same types of hash tables. note that "hasher" must exist longer than any classes based on it; do not let "hasher" go out of scope or the hash table will explode.
Definition at line 260 of file hash_table.h.
◆ ~hash_table()
|
virtual |
destroys any objects left in the hash_table.
Definition at line 268 of file hash_table.h.
References deadly_error, FUNCDEF, and basis::WHACK().
Member Function Documentation
◆ acquire()
| contents * structures::hash_table< key_type, contents >::acquire | ( | const key_type & | key | ) |
retrieves the contents held for "key" out of the table.
afterwards, the contents pointer is the caller's responsibility; it is no longer in the table and must be destroyed externally. if no item was found for the "key", then NULL_POINTER is returned.
Definition at line 483 of file hash_table.h.
References deadly_error, structures::bucket< key_type, contents >::find(), FUNCDEF, basis::negative(), NULL_POINTER, basis::WHACK(), and basis::array< contents >::zap().
Referenced by structures::int_hash< contents >::acquire(), and structures::pointer_hash< contents >::acquire().
◆ add() [1/2]
| basis::outcome structures::hash_table< key_type, contents >::add | ( | const key_type & | key, |
| contents * | to_store | ||
| ) |
Stores "to_store" into the table given its "key" for hashing.
This places an entry in the hash table with the contents "to_store", using the "key" structure to identify it. the return value reports whether the "key" was already in the list or not. if the "key" was already in use, then the contents for it get replaced with "to_store". note that the hash table assumes ownership of the "to_store" object but just makes a copy of the key. thus, if an item is replaced, the previous contents are destroyed.
Definition at line 405 of file hash_table.h.
Referenced by structures::int_hash< contents >::add(), structures::pointer_hash< contents >::add(), structures::copy_hash_table(), and structures::hash_table< key_type, contents >::rehash().
◆ add() [2/2]
| basis::outcome structures::hash_table< key_type, contents >::add | ( | key_type * | key, |
| contents * | to_store, | ||
| bool | check_dupes = true |
||
| ) |
specialized add for a pre-existing pointer "key".
responsibility for the "key" is taken over by the hash table, as of course it is for the "to_store" pointer. this just allows others to generate new keys and hand them over to us when it might otherwise be very costly to copy the key structure. if "check_dupes" is not true, then that asserts that you have independently verified that there's no need to check whether the key is already present.
Definition at line 410 of file hash_table.h.
References deadly_error, structures::bucket< key_type, contents >::find(), FUNCDEF, basis::negative(), basis::array< contents >::put(), and basis::WHACK().
◆ apply()
| void structures::hash_table< key_type, contents >::apply | ( | apply_function * | to_apply, |
| void * | data_link | ||
| ) |
Invokes the function "to_apply" on every entry in the table.
This calls the "to_apply" function on every item in the catalog until the function returns false. The "data_link" pointer is available to the applied method and can be used to communicate an object for use during the iteration. NOTE: it is NOT safe to rearrange or manipulate the table in any way from your "to_apply" function.
Definition at line 543 of file hash_table.h.
References deadly_error, FUNCDEF, and basis::array< contents >::use().
◆ calculate_num_slots()
|
static |
a helper method that lets us know what n is for how many 2^n slots we should have.
Definition at line 280 of file hash_table.h.
◆ DEFINE_CLASS_NAME()
| structures::hash_table< key_type, contents >::DEFINE_CLASS_NAME | ( | "hash_table< key_type, contents >" | ) |
◆ elements()
| int structures::hash_table< key_type, contents >::elements |
the number of valid items we found by traversing the hash table.
this is a very costly method.
Definition at line 576 of file hash_table.h.
References deadly_error, FUNCDEF, and basis::array< contents >::length().
◆ estimated_elements()
|
inline |
returns the size of table we're optimized for.
Definition at line 101 of file hash_table.h.
◆ fast_dangerous_add()
| basis::outcome structures::hash_table< key_type, contents >::fast_dangerous_add | ( | const key_type & | key, |
| contents * | to_store | ||
| ) |
Like the add method above, but doesn't check for duplicates.
This should only ever be used when one has already guaranteed that the table doesn't have a duplicate item for the "key" specified.
Definition at line 455 of file hash_table.h.
◆ find() [1/2]
|
inline |
simplified form of above find() method.
Definition at line 125 of file hash_table.h.
References structures::hash_table< key_type, contents >::find(), and NULL_POINTER.
◆ find() [2/2]
| bool structures::hash_table< key_type, contents >::find | ( | const key_type & | key, |
| contents *& | item_found | ||
| ) | const |
locates the item specified by the "key", if possible.
true is returned on success and the "item_found" is filled in. the "item_found" is a pointer to the actual data held in the table, so do not destroy or otherwise damage the "item_found".
Definition at line 460 of file hash_table.h.
References deadly_error, structures::bucket< key_type, contents >::find(), FUNCDEF, basis::negative(), and NULL_POINTER.
Referenced by structures::int_hash< contents >::apply(), structures::pointer_hash< contents >::apply(), and structures::hash_table< key_type, contents >::find().
◆ rehash()
| void structures::hash_table< key_type, contents >::rehash | ( | int | estimated_elements | ) |
resizes the hashing structures to optimise for a new size of "estimated_elements".
this is a potentially expensive operation.
Definition at line 367 of file hash_table.h.
References structures::hash_table< key_type, contents >::add(), deadly_error, and FUNCDEF.
◆ reset()
| void structures::hash_table< key_type, contents >::reset |
removes all entries in the table and returns it to a pristine state.
Definition at line 316 of file hash_table.h.
References deadly_error, FUNCDEF, basis::array< contents >::length(), basis::WHACK(), and basis::array< contents >::zap().
Referenced by structures::copy_hash_table(), structures::int_hash< contents >::reset(), and structures::pointer_hash< contents >::reset().
◆ table_access()
| internal_hash_array< key_type, contents > & structures::hash_table< key_type, contents >::table_access |
special accessor for the copy_hash_table method only.
Definition at line 363 of file hash_table.h.
Referenced by structures::copy_hash_table().
◆ verify()
| bool structures::hash_table< key_type, contents >::verify |
returns true if the hash table is internally consistent.
this is mainly for debugging.
Definition at line 341 of file hash_table.h.
References structures::hash_wrapper< key_type, contents >::_data, structures::hash_wrapper< key_type, contents >::_id, and basis::array< contents >::length().
Referenced by structures::copy_hash_table().
◆ zap()
| bool structures::hash_table< key_type, contents >::zap | ( | const key_type & | key | ) |
removes the entry with the "key" specified.
true is returned if the item was found and destroyed.
Definition at line 509 of file hash_table.h.
References deadly_error, structures::bucket< key_type, contents >::find(), FUNCDEF, basis::array< contents >::length(), basis::negative(), basis::WHACK(), and basis::array< contents >::zap().
Referenced by structures::int_hash< contents >::zap(), and structures::pointer_hash< contents >::zap().
The documentation for this class was generated from the following file:
- /opt/feistymeow.org/feisty_meow/nucleus/library/structures/hash_table.h
