#include <hash-table.h>
Data Structures | |
| class | iterator |
Public Types | |
| typedef Descriptor::value_type | value_type |
| typedef Descriptor::compare_type | compare_type |
Public Member Functions | |
| hash_table () | |
| void | create (size_t initial_slots) |
| bool | is_created () |
| void | dispose () |
| value_type * | find (const value_type *value) |
| value_type * | find_with_hash (const compare_type *comparable, hashval_t hash) |
| value_type ** | find_slot (const value_type *value, enum insert_option insert) |
| value_type ** | find_slot_with_hash (const compare_type *comparable, hashval_t hash, enum insert_option insert) |
| void | empty () |
| void | clear_slot (value_type **slot) |
| void | remove_elt (const value_type *value) |
| void | remove_elt_with_hash (const compare_type *comparable, hashval_t hash) |
| size_t | size () |
| size_t | elements () |
| size_t | elements_with_deleted () |
| double | collisions () |
| template<typename Argument , int(*)(value_type **slot, Argument argument) Callback> | |
| void | traverse_noresize (Argument argument) |
| template<typename Argument , int(*)(value_type **slot, Argument argument) Callback> | |
| void | traverse (Argument argument) |
| iterator | begin () |
| iterator | end () |
Private Member Functions | |
| value_type ** | find_empty_slot_for_expand (hashval_t hash) |
| void | expand () |
Private Attributes | |
| hash_table_control< value_type > * | htab |
Detailed Description
template<typename Descriptor, template< typename Type > class Allocator = xcallocator>
class hash_table< Descriptor, Allocator >
@verbatim
User-facing hash table type.
The table stores elements of type Descriptor::value_type.
It hashes values with the hash member function. The table currently works with relatively weak hash functions. Use typed_pointer_hash
when hashing pointers instead of objects.
It compares elements with the equal member function. Two elements with the same hash may not be equal. Use typed_pointer_equal
when hashing pointers instead of objects.
It removes elements with the remove member function. This feature is useful for freeing memory. Derive from typed_null_remove
when not freeing objects. Derive from typed_free_remove
when doing a simple object free.
Specify the template Allocator to allocate and free memory. The default is xcallocator.
Member Typedef Documentation
| typedef Descriptor::compare_type hash_table< Descriptor, Allocator >::compare_type |
| typedef Descriptor::value_type hash_table< Descriptor, Allocator >::value_type |
Constructor & Destructor Documentation
|
inline |
Construct the hash table. The only useful operation next is create.
Member Function Documentation
|
inline |
Hash table iterator producers.
The beginning of a hash table iteration.
| void hash_table< Descriptor, Allocator >::clear_slot | ( | value_type ** | slot | ) |
This function clears a specified SLOT in a hash table. It is useful when you've already done the lookup and don't want to do it again.
References limit.
Referenced by delay_i1_hasher::hash(), invariant_or_equiv_p(), and vt_find_locations().
|
inline |
Return the fraction of fixed collisions during all work with given
hash table.
References hash_table< Descriptor, Allocator >::size().
| void hash_table< Descriptor, Allocator >::create | ( | size_t | size | ) |
Create a hash table with at least the given number of INITIAL_SLOTS.
References abort(), and hash_table_mod1().
Referenced by build_and_add_sum(), clear_iv_info(), coalesce_partitions(), collect_one_action_chain(), copy_ancestor_tree(), copy_reference(), create_loads_and_stores_for_name(), dead_debug_global_find(), debug_clast_stmt(), devirt_node_removal_hook(), emit_notes_for_changes(), asan_mem_ref_hasher::equal(), free_all_edge_infos(), generate_skeleton(), haifa_htab_i2_traverse(), and unshare_strinfo_vec().
| void hash_table< Descriptor, Allocator >::dispose | ( | ) |
Dispose of a hash table. Free all memory and return this hash table to the non-created state. Naturally the hash table must already exist.
Referenced by attrs_list_clear(), biv_p(), coalesce_partitions(), copy_ancestor_tree(), create_coalesce_list(), fp_setter_insn(), process_scc(), and setup_regno_cost_classes_by_mode().
|
inline |
Return the current number of elements in this hash table.
References hash_table_higher_prime_index(), prime_ent::prime, and prime_tab.
Referenced by compare_pairs(), and find_src_set_src().
|
inline |
Return the current number of elements in this hash table.
| void hash_table< Descriptor, Allocator >::empty | ( | ) |
This function clears all entries in the given hash table.
Instead of clearing megabyte, downsize the table.
Referenced by preserve_constants_and_equivs().
|
inline |
The end of a hash table iteration.
|
private |
The following function changes size of memory allocated for the entries and repeatedly inserts the table elements. The occupancy of the table after the call will be about 50%. Naturally the hash table must already exist. Remember also that the place of the table entries is changed. If memory allocation fails, this function will abort.
Resize only when table after removal of unused elements is either
too full or too empty.
|
inline |
Like find_with_hash, but compute the hash value from the element.
References hash_table< Descriptor, Allocator >::size().
Referenced by adjust_simduid_builtins(), free_original_copy_tables(), and insert_var_expansion_initialization().
|
private |
Similar to find_slot, but without several unwanted side effects:
- Does not call equal when it finds an existing entry.
- Does not change the count of elements/searches/collisions in the
hash table.
This function also assumes there are no deleted entries in the table.
HASH is the hash value for the element to be inserted.
References hash_table_higher_prime_index(), prime_ent::prime, prime_tab, and hash_table< Descriptor, Allocator >::size().
|
inline |
Like find_slot_with_hash, but compute the hash value from the element.
Referenced by analyze_iv_to_split_insn(), build_iv_mapping(), clast_name_to_index(), coalesce_partitions(), dead_debug_global_find(), histogram_hash::equal(), gate_lto_out(), get_expression_id(), lto_orig_address_map(), setup_cost_classes(), streamer_string_index(), TB_current_chain_node(), tm_log_emit(), and tm_log_emit_saves().
| Descriptor::value_type ** hash_table< Descriptor, Allocator >::find_slot_with_hash | ( | const compare_type * | comparable, |
| hashval_t | hash, | ||
| enum insert_option | insert | ||
| ) |
This function searches for a hash table slot containing an entry equal to the given COMPARABLE element and starting with the given HASH. To delete an entry, call this with insert=NO_INSERT, then call clear_slot on the slot returned (possibly after doing some checks). To insert an entry, call this with insert=INSERT, then write the value you want into the returned slot. When inserting an entry, NULL may be returned if memory allocation fails.
Referenced by assign_symbol_names(), attrs_list_member(), clone_tree(), connect_traces(), do_complex_constraint(), get_biv_step(), haifa_htab_i2_traverse(), separate_decls_in_region_name(), separate_decls_in_region_stmt(), set_register_defs(), shared_hash_find_slot_unshare(), vn_nary_op_compute_hash(), and vt_find_locations().
| Descriptor::value_type * hash_table< Descriptor, Allocator >::find_with_hash | ( | const compare_type * | comparable, |
| hashval_t | hash | ||
| ) |
This function searches for a hash table entry equal to the given COMPARABLE element starting with the given HASH value. It cannot be used to insert or delete an element.
References hash_table_mod1(), hash_table_mod2(), and hash_table< Descriptor, Allocator >::size().
Referenced by attrs_list_union(), discard_delay_pairs_above(), gt_pch_note_object(), and max_issue().
|
inline |
See if the table has been created, as opposed to constructed.
Referenced by adjust_simduid_builtins(), dead_debug_global_find(), discard_delay_pairs_above(), asan_mem_ref_hasher::equal(), gen_internal_sym(), haifa_htab_i2_traverse(), insert_var_expansion_initialization(), and max_issue().
|
inline |
Like remove_elt_with_hash, but compute the hash value from the element.
| void hash_table< Descriptor, Allocator >::remove_elt_with_hash | ( | const compare_type * | comparable, |
| hashval_t | hash | ||
| ) |
This function deletes an element with the given COMPARABLE value from hash table starting with the given HASH. If there is no matching element in the hash table, this function does nothing.
References hash_table< Descriptor, Allocator >::size().
|
inline |
Return the current size of this hash table.
Referenced by hash_table< Descriptor, Allocator >::collisions(), hash_table< Descriptor, Allocator >::find(), hash_table< Descriptor, Allocator >::find_empty_slot_for_expand(), find_src_set_src(), hash_table< Descriptor, Allocator >::find_with_hash(), and hash_table< Descriptor, Allocator >::remove_elt_with_hash().
| void hash_table< Descriptor, Allocator >::traverse | ( | Argument | argument | ) |
Like traverse_noresize, but does resize the table when it is too empty to improve effectivity of subsequent calls.
Referenced by create_call_for_reduction(), create_call_for_reduction_1(), discard_useless_locs(), ptr_hash_hasher::equal(), generate_skeleton(), and delay_i2_hasher::hash().
| void hash_table< Descriptor, Allocator >::traverse_noresize | ( | Argument | argument | ) |
This function scans over the entire hash table calling CALLBACK for each live entry. If CALLBACK returns false, the iteration stops. ARGUMENT is passed as CALLBACK's second argument.
Field Documentation
|
private |
The documentation for this class was generated from the following file:
