#include <hash_table.h>
Collaboration diagram for hash_table< key_type, contents >:
Public Types | |
| enum | outcomes { IS_NEW = common::IS_NEW, EXISTING = 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. | |
Public Member Functions | |
| hash_table (const hashing_algorithm &hasher, int max_table_bits) | |
| Creates a table using the "hasher" and having 2^max_table_bits slots. | |
| ~hash_table () | |
| destroys any objects left in the hash_table. | |
| int | max_bits () const |
| void | rehash (int max_bits) |
| resizes the underlying hashing structures to use a new "max_bits". | |
| int | elements () const |
| the number of valid items we found by traversing the hash table. | |
| outcome | add (const key_type &key, contents *to_store) |
| Stores "to_store" into the table given its "key" for hashing. | |
| outcome | fast_dangerous_add (const key_type &key, contents *to_store) |
| Like the add method above, but doesn't check for duplicates. | |
| bool | find (const key_type &key, contents *&item_found) const |
| locates the item specified by the "key", if possible. | |
| contents * | find (const key_type &key) const |
| simplified form of above find() method. | |
| contents * | acquire (const key_type &key) |
| retrieves the contents held for "key" out of the table. | |
| bool | zap (const key_type &key) |
| removes the entry with the "key" specified. | |
| void | reset () |
| removes all entries in the table and returns it to a pristine state. | |
| void | apply (apply_function *to_apply, void *data_link) |
| Invokes the function "to_apply" on every entry in the table. | |
| outcome | add (key_type *key, contents *to_store, bool check_dupes=true) |
| specialized add for a pre-existing pointer "key". | |
| bool | verify () const |
| returns true if the hash table is internally consistent. | |
| internal_hash_array< key_type, contents > & | table_access () const |
| special accessor for the copy_hash_table method only. | |
Static Public Member Functions | |
| static const char * | class_name () |
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 (hmmm).
Definition at line 65 of file hash_table.h.
| typedef bool 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.
Reimplemented in int_hash< contents >, pointer_hash< contents >, int_hash< connection >, int_hash< queued_zings >, int_hash< data_shuttle >, int_hash< value_record >, int_hash< living_item >, int_hash< sequence_record >, int_hash< ml_memory_record >, int_hash< mail_cabinet >, and pointer_hash< internal_pointer_hider< contents > >.
Definition at line 142 of file hash_table.h.
| enum hash_table::outcomes |
| hash_table< key_type, contents >::hash_table | ( | const hashing_algorithm & | hasher, | |
| int | max_table_bits | |||
| ) |
Creates a table using the "hasher" and having 2^max_table_bits slots.
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. the "max_table_bits" specifies how many of the bits in the integer hash values are meaningful. the rest of the bits are chopped. note that using a "max_table_bits" greater than thirty-two or less than one is meaningless. "max_table_bits" is consequently also used to compute the size of the hash table; the table will have (2 ^ max_table_bits) elements in it. note that using values greater than 16 for "max_table_ bits" start to use a very large amount of memory, but they will also provide faster lookups. choose the number of bits wisely.
Definition at line 85 of file hash_table.cpp.
| hash_table< key_type, contents >::~hash_table | ( | ) |
destroys any objects left in the hash_table.
Definition at line 94 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, hash_table< key_type, contents >::reset(), hash_table< key_type, contents >::verify(), and WHACK().
| static const char* hash_table< key_type, contents >::class_name | ( | ) | [inline, static] |
Definition at line 87 of file hash_table.h.
Referenced by hash_table< key_type, contents >::acquire(), hash_table< key_type, contents >::add(), hash_table< key_type, contents >::apply(), hash_table< key_type, contents >::elements(), hash_table< key_type, contents >::find(), hash_table< key_type, contents >::rehash(), hash_table< key_type, contents >::reset(), hash_table< key_type, contents >::zap(), and hash_table< key_type, contents >::~hash_table().
| int hash_table< key_type, contents >::max_bits | ( | ) | const [inline] |
Definition at line 89 of file hash_table.h.
| void hash_table< key_type, contents >::rehash | ( | int | max_bits | ) |
resizes the underlying hashing structures to use a new "max_bits".
this is a potentially expensive operation.
Definition at line 183 of file hash_table.cpp.
References hash_table< key_type, contents >::_max_bits, hash_table< key_type, contents >::_table, hash_table< key_type, contents >::add(), hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, and hash_table< key_type, contents >::verify().
| int hash_table< key_type, contents >::elements | ( | ) | const |
the number of valid items we found by traversing the hash table.
this is a very costly method.
Definition at line 392 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, and hash_table< key_type, contents >::verify().
| outcome 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 221 of file hash_table.cpp.
Referenced by pointer_hash< contents >::add(), int_hash< contents >::add(), copy_hash_table(), and hash_table< key_type, contents >::rehash().
| outcome 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 272 of file hash_table.cpp.
| bool 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 276 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, hashing_algorithm::hash(), negative(), NIL, and hash_table< key_type, contents >::verify().
Referenced by pointer_hash< contents >::apply(), int_hash< contents >::apply(), and hash_table< void *, live_object_info >::find().
| contents* hash_table< key_type, contents >::find | ( | const key_type & | key | ) | const [inline] |
| contents * 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 NIL is returned.
Definition at line 299 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, hashing_algorithm::hash(), negative(), NIL, hash_table< key_type, contents >::verify(), and WHACK().
Referenced by pointer_hash< contents >::acquire(), and int_hash< contents >::acquire().
| bool 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 325 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, hashing_algorithm::hash(), negative(), hash_table< key_type, contents >::verify(), and WHACK().
Referenced by pointer_hash< contents >::zap(), and int_hash< contents >::zap().
| void hash_table< key_type, contents >::reset | ( | ) |
removes all entries in the table and returns it to a pristine state.
Reimplemented in int_hash< contents >, pointer_hash< contents >, int_hash< connection >, int_hash< queued_zings >, int_hash< data_shuttle >, int_hash< value_record >, int_hash< living_item >, int_hash< sequence_record >, int_hash< ml_memory_record >, int_hash< mail_cabinet >, and pointer_hash< internal_pointer_hider< contents > >.
Definition at line 132 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, hash_table< key_type, contents >::verify(), and WHACK().
Referenced by copy_hash_table(), pointer_hash< contents >::reset(), int_hash< contents >::reset(), and hash_table< key_type, contents >::~hash_table().
| void 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.
Reimplemented in int_hash< contents >, pointer_hash< contents >, int_hash< connection >, int_hash< queued_zings >, int_hash< data_shuttle >, int_hash< value_record >, int_hash< living_item >, int_hash< sequence_record >, int_hash< ml_memory_record >, int_hash< mail_cabinet >, and pointer_hash< internal_pointer_hider< contents > >.
Definition at line 359 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, FUNCDEF, and hash_table< key_type, contents >::verify().
| outcome 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 226 of file hash_table.cpp.
References hash_table< key_type, contents >::class_name(), deadly_error, hash_table< key_type, contents >::EXISTING, FUNCDEF, hashing_algorithm::hash(), hash_table< key_type, contents >::IS_NEW, negative(), hash_table< key_type, contents >::verify(), and WHACK().
| bool hash_table< key_type, contents >::verify | ( | ) | const |
returns true if the hash table is internally consistent.
this is mainly for debugging.
Definition at line 157 of file hash_table.cpp.
Referenced by hash_table< key_type, contents >::acquire(), hash_table< key_type, contents >::add(), hash_table< key_type, contents >::apply(), copy_hash_table(), hash_table< key_type, contents >::elements(), hash_table< key_type, contents >::find(), hash_table< key_type, contents >::rehash(), hash_table< key_type, contents >::reset(), hash_table< key_type, contents >::zap(), and hash_table< key_type, contents >::~hash_table().
| internal_hash_array< key_type, contents > & hash_table< key_type, contents >::table_access | ( | ) | const |
special accessor for the copy_hash_table method only.
Definition at line 179 of file hash_table.cpp.
Referenced by copy_hash_table().
1.5.1