#include <hash-table.h>

Inheritance diagram for hash_table< Descriptor, Allocator >:

Collaboration diagram for hash_table< Descriptor, Allocator >:

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 >

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 <Value> 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 <Value> 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 <Value> when not freeing objects.
     Derive from typed_free_remove <Value> when doing a simple object free.

   Specify the template Allocator to allocate and free memory.
     The default is xcallocator.

Member Typedef Documentation

template<typename Descriptor, template< typename Type > class Allocator = xcallocator>

typedef Descriptor::compare_type hash_table< Descriptor, Allocator >::compare_type

template<typename Descriptor, template< typename Type > class Allocator = xcallocator>

typedef Descriptor::value_type hash_table< Descriptor, Allocator >::value_type

Constructor & Destructor Documentation

template<typename Descriptor , template< typename Type > class Allocator>

hash_table< Descriptor, Allocator >::hash_table ( )

inline

Construct the hash table.  The only useful operation next is create.

Member Function Documentation

template<typename Descriptor , template< typename Type > class Allocator>

hash_table< Descriptor, Allocator >::iterator hash_table< Descriptor, Allocator >::begin ( )

inline

Hash table iterator producers.

The beginning of a hash table iteration.

References hash_table< Descriptor, Allocator >::iterator::slide().

Referenced by vectorize_loops().

template<typename Descriptor , template< typename Type > class Allocator>

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 abort().

Referenced by copy_original_table_clear(), discard_useless_values(), disqualify_candidate(), emit_note_insn_var_location(), ggc_free_overhead(), ggc_prune_ptr(), haifa_htab_i1_traverse(), haifa_htab_i2_traverse(), lto_orig_address_remove(), preserve_constants_and_equivs(), remove_local_expressions_from_table(), remove_value_from_changed_variables(), and variable_was_changed().

template<typename Descriptor , template< typename Type > class Allocator>

double hash_table< Descriptor, Allocator >::collisions ( )

inline

Referenced by dump_hash_table(), htab_statistics(), and tail_merge_optimize().

template<typename Descriptor , template< typename Type > class Allocator>

void hash_table< Descriptor, Allocator >::create ( size_t size )

Create a hash table with at least the given number of INITIAL_SLOTS.

References hash_table_higher_prime_index(), prime_ent::prime, and prime_tab.

Referenced by addr_stridxptr(), alloc_mem(), allocate_pool_descriptor(), allocate_vn_table(), analyze_insns_in_loop(), assign_filter_values(), break_out_includes(), browse_tree(), build_gimple_cfg(), build_type_inheritance_graph(), coalesce_ssa_name(), compute_ld_motion_mems(), compute_store_table(), convert_to_eh_region_ranges(), copy_bb_and_scalar_dependences(), copy_decls_for_unworthy_types(), create_coalesce_list(), create_output_block(), create_pseudo_cfg(), cselib_init(), curr_statistics_hash(), dataflow_set_merge(), dead_debug_global_insert(), debug_fold_checksum(), dse_step0(), dwarf2out_finish(), eliminate_local_variables(), execute_strength_reduction(), find_or_create_vtbl_map_node(), fold_build1_stat_loc(), fold_build2_stat_loc(), fold_build3_stat_loc(), fold_build_call_array_loc(), get_bitmap_descriptor(), get_instantiated_value_entry(), get_mem_ref_hash_table(), get_named_event_id(), get_non_trapping(), ggc_record_overhead(), gloog(), graphite_transform_loops(), gt_pch_save(), init_alias_vars(), init_allocno_hard_regs(), init_pre(), init_scc_vn(), init_ssa_renamer(), init_worklist(), initialize_original_copy_tables(), initiate_regno_cost_classes(), insert_clobber_before_stack_restore(), ipa_profile_generate_summary(), ipa_profile_read_summary(), iv_analysis_loop_init(), lookup_tmp_var(), lower_eh_constructs(), lto_reader_init(), lto_streamer_init(), make_loc_descriptor(), merge_identical_invariants(), note_simd_array_uses_cb(), optimize_external_refs(), optimize_location_lists(), optimize_macinfo_range(), parallelize_loops(), perform_var_substitution(), possible_polymorphic_call_targets(), print_fold_checksum(), print_generated_program(), record_delay_slot_pair(), register_scoped_attributes(), separate_decls_in_region(), shared_hash_unshare(), sjlj_assign_call_site_values(), sra_initialize(), thread_block(), tm_log_init(), tree_lower_complex(), tree_ssa_dominator_optimize(), tree_ssa_iv_optimize_init(), tree_ssa_uncprop(), undistribute_ops_list(), update_ssa(), var_map_base_init(), vectorize_loops(), vt_emit_notes(), and vt_initialize().

template<typename Descriptor , template< typename Type > class Allocator>

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.

References hash_table< Descriptor, Allocator >::size().

Referenced by assign_filter_values(), break_out_includes(), browse_tree(), build_gimple_cfg(), coalesce_ssa_name(), convert_to_eh_region_ranges(), copy_bb_and_scalar_dependences(), copy_decls_for_unworthy_types(), cselib_finish(), dead_debug_global_finish(), delete_coalesce_list(), delete_points_to_sets(), delete_worklist(), destroy_output_block(), dse_step7(), dwarf2out_finish(), eliminate_local_variables(), execute_dwarf2_frame(), execute_strength_reduction(), fini_pre(), fini_ssa_renamer(), finish_allocno_hard_regs(), finish_regno_cost_classes(), free_ld_motion_mems(), free_mem(), free_mem_ref_resources(), free_opt_info(), free_original_copy_tables(), free_polymorphic_call_targets_hash(), free_scc_vn(), free_store_motion_mems(), free_var_substitution_info(), free_vn_table(), get_named_event_id(), get_non_trapping(), gloog(), graphite_transform_loops(), gt_pch_save(), insert_clobbers_for_var(), ipa_profile_generate_summary(), ipa_profile_read_summary(), iv_analysis_done(), lower_eh_constructs(), merge_identical_invariants(), one_store_motion_pass(), optimize_location_lists(), output_comdat_type_unit(), output_comp_unit(), output_macinfo(), parallelize_loops(), pop_gimplify_context(), print_fold_checksum(), separate_decls_in_region(), shared_hash_destroy(), sjlj_assign_call_site_values(), sra_deinitialize(), thread_block(), tm_log_delete(), tree_lower_complex(), tree_ssa_dominator_optimize(), tree_ssa_iv_optimize_finalize(), tree_ssa_strlen(), tree_ssa_uncprop(), undistribute_ops_list(), vectorize_loops(), vt_emit_notes(), vt_finalize(), and instantiate_cache_type::~instantiate_cache_type().

template<typename Descriptor , template< typename Type > class Allocator>

size_t hash_table< Descriptor, Allocator >::elements ( )

inline

Return the current number of elements in this hash table.

Referenced by cselib_process_insn(), dataflow_set_different(), dataflow_set_merge(), dump_hash_table(), dump_vars(), emit_notes_for_changes(), gcse_after_reload_main(), gen_parallel_loop(), htab_statistics(), insert_phi_nodes(), num_coalesce_pairs(), optimize_macinfo_range(), reduction_phi(), separate_decls_in_region(), shared_hash_unshare(), transform_to_exit_first_loop(), try_create_reduction_list(), vt_emit_notes(), and vt_find_locations().

template<typename Descriptor , template< typename Type > class Allocator>

size_t hash_table< Descriptor, Allocator >::elements_with_deleted ( )

inline

Return the current number of elements in this hash table.

Referenced by dump_ggc_loc_statistics().

template<typename Descriptor , template< typename Type > class Allocator>

void hash_table< Descriptor, Allocator >::empty ( )

This function clears all entries in the given hash table.

References hash_table_higher_prime_index(), memset(), prime_ent::prime, prime_tab, and hash_table< Descriptor, Allocator >::size().

Referenced by clear_iv_info(), cselib_reset_table(), dse_step1(), empty_mem_ref_hash_table(), free_delay_pairs(), free_loop_data(), parallelize_loops(), and process_scc().

template<typename Descriptor , template< typename Type > class Allocator>

hash_table< Descriptor, Allocator >::iterator hash_table< Descriptor, Allocator >::end ( )

inline

The end of a hash table iteration.

Referenced by vectorize_loops().

template<typename Descriptor , template< typename Type > class Allocator>

void hash_table< Descriptor, Allocator >::expand ( )

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.

References hash_table_higher_prime_index(), prime_ent::prime, prime_tab, and hash_table< Descriptor, Allocator >::size().

template<typename Descriptor , template< typename Type > class Allocator>

Descriptor::value_type * hash_table< Descriptor, Allocator >::find ( const value_type * value )

inline

Like find_with_hash, but compute the hash value from the element.

Referenced by adjust_simduid_builtins(), apply_opt_in_copies(), dead_debug_global_find(), find_basis_for_base_expr(), find_hard_regs(), get_bb_copy(), get_bb_original(), get_loop_copy(), outside_finally_tree(), reduction_phi(), TB_up_expr(), and vectorize_loops().

template<typename Descriptor , template< typename Type > class Allocator>

Descriptor::value_type ** hash_table< Descriptor, Allocator >::find_empty_slot_for_expand ( hashval_t hash )

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 abort(), hash_table_mod1(), and hash_table_mod2().

template<typename Descriptor , template< typename Type > class Allocator>

Descriptor::value_type ** hash_table< Descriptor, Allocator >::find_slot	(	const value_type *	value,
		enum insert_option	insert
	)

inline

Like find_slot_with_hash, but compute the hash value from the element.

Referenced by account_time_size(), add_action_record(), add_ehspec_entry(), add_or_mark_expr(), alloc_expression_id(), analyze_insns_in_loop(), build_new_reduction(), canon_file_name(), clast_name_to_index(), clast_name_to_lb_ub(), clast_name_to_level(), coalesce_ssa_name(), copy_original_table_clear(), copy_original_table_set(), dead_debug_global_insert(), dwarf2out_finish(), find_or_create_vtbl_map_node(), find_pbb_via_hash(), find_rtx_in_ldst(), fold_checksum_tree(), get_expr_id(), get_group_info(), get_named_event_id(), get_rename(), insert_clobber_before_stack_restore(), insert_hard_regs(), lookup_expression_id(), lookup_external_ref(), lookup_or_add_counter(), lookup_redirection_data(), lookup_tmp_var(), lto_orig_address_get(), lto_orig_address_map(), lto_orig_address_remove(), make_loc_descriptor(), mark_bb_with_pbb(), note_simd_array_uses_cb(), optimize_macinfo_range(), possible_polymorphic_call_targets(), record_equiv(), record_in_finally_tree(), record_potential_basis(), remove_equivalence(), save_clast_name_index(), set_rename(), setup_regno_cost_classes_by_aclass(), setup_regno_cost_classes_by_mode(), store_child_info(), streamer_string_index(), thread_private_new_memory(), tm_log_add(), tm_log_emit_restores(), tm_log_emit_saves(), uncprop_into_successor_phis(), undistribute_ops_list(), update_mem_ref_hash_table(), var_map_base_init(), vectorize_loops(), vtbl_map_get_node(), and vtbl_map_node_registration_insert().

template<typename Descriptor , template< typename Type > class Allocator>

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.

References hash_table_mod1(), hash_table_mod2(), and hash_table< Descriptor, Allocator >::size().

Referenced by add_ttypes_entry(), addr_stridxptr(), allocate_pool_descriptor(), check_duplicate_cu(), clone_tree_hash(), copy_ancestor_tree(), copy_decls_walk(), copy_phi(), copy_reference(), create_pseudo_cfg(), cselib_find_slot(), cvc_insert(), disqualify_candidate(), equiv_class_lookup_or_add(), find_coalesce_pair(), find_or_insert_inv(), find_param_candidates(), find_same_succ_bb(), get_bitmap_descriptor(), get_constant_value_id(), get_instantiated_value_entry(), get_odr_type(), get_or_alloc_constant_value_id(), get_var_info(), ggc_free_overhead(), ggc_record_overhead(), gt_pch_note_object(), insert_expr_in_table(), ldst_entry(), lookup_avail_expr(), lookup_expr_in_table(), maybe_add_sra_candidate(), next_discriminator_for_locus(), notify_dependents_of_changed_value(), optimize_location_lists_1(), phi_trans_add(), phi_trans_lookup(), record_biv(), record_comdat_symbol_number(), record_cond(), record_delay_slot_pair(), register_scoped_attribute(), remove_local_expressions_from_table(), remove_value_from_changed_variables(), separate_decls_in_region_debug(), separate_decls_in_region_name(), shared_bitmap_add(), shared_bitmap_lookup(), shared_hash_find_slot_1(), shared_hash_find_slot_noinsert_1(), shared_hash_find_slot_unshare_1(), st_expr_entry(), take_address_of(), unshare_variable(), variable_from_dropped(), variable_was_changed(), vars_copy(), visit_reference_op_call(), vn_nary_op_insert_into(), vn_nary_op_lookup_1(), vn_phi_insert(), vn_phi_lookup(), vn_reference_insert(), vn_reference_insert_pieces(), vn_reference_lookup_1(), and vn_reference_lookup_2().

template<typename Descriptor , template< typename Type > class Allocator>

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 add_delay_dependencies(), analyzed_for_bivness_p(), candidate(), cvc_lookup(), dataflow_set_different(), dep_cost_1(), emit_notes_for_differences_1(), emit_notes_for_differences_2(), find_loc_in_1pdv(), find_mem_expr_in_1pdv(), get_addr_stridx(), get_trace_info(), gt_pch_note_reorder(), loc_exp_insert_dep(), notify_dependents_of_changed_value(), notify_dependents_of_resolved_value(), prune_ready_list(), real_insn_for_shadow(), relocate_ptrs(), schedule_block(), shared_hash_find_1(), vt_expand_loc_callback(), and write_pch_globals().

template<typename Descriptor , template< typename Type > class Allocator>

bool hash_table< Descriptor, Allocator >::is_created ( )

inline

See if the table has been created, as opposed to constructed.

Referenced by add_delay_dependencies(), addr_stridxptr(), adjust_simduid_builtins(), allocate_pool_descriptor(), analyze_insns_in_loop(), apply_opt_in_copies(), build_type_inheritance_graph(), clast_name_to_gcc(), copy_ancestor_tree(), dead_debug_global_finish(), dead_debug_global_insert(), dep_cost_1(), dump_alloc_pool_statistics(), dump_bitmap_statistics(), dump_tree_ssa_stats(), dump_var_infos(), empty_mem_ref_hash_table(), find_or_create_vtbl_map_node(), find_rtx_in_ldst(), fini_ssa_renamer(), free_delay_pairs(), free_ld_motion_mems(), free_mem_ref_resources(), free_opt_info(), free_store_motion_mems(), get_addr_stridx(), get_bitmap_descriptor(), get_instantiated_value_entry(), get_mem_ref_hash_table(), get_named_event_id(), ggc_record_overhead(), init_ssa_renamer(), insert_clobber_before_stack_restore(), insert_clobbers_for_var(), lookup_tmp_var(), make_loc_descriptor(), note_simd_array_uses_cb(), optimize_macinfo_range(), output_macinfo(), pop_gimplify_context(), possible_polymorphic_call_target_p(), prune_ready_list(), real_insn_for_shadow(), record_delay_slot_pair(), register_scoped_attribute(), rewrite_blocks(), schedule_block(), separate_decls_in_region(), tree_ssa_strlen(), type_for_clast_name(), update_type_inheritance_graph(), vectorize_loops(), vtbl_map_get_node(), vtbl_map_node_registration_insert(), and instantiate_cache_type::~instantiate_cache_type().

template<typename Descriptor , template< typename Type > class Allocator>

void hash_table< Descriptor, Allocator >::remove_elt ( const value_type * value )

inline

Like remove_elt_with_hash, but compute the hash value from the element.

template<typename Descriptor , template< typename Type > class Allocator>

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.

Referenced by compute_store_table(), same_succ_flush_bb(), and trim_ld_motion_mems().

template<typename Descriptor , template< typename Type > class Allocator>

size_t hash_table< Descriptor, Allocator >::size ( )

inline

Return the current size of this hash table.

References hash_table< Descriptor, Allocator >::size().

Referenced by hash_table< Descriptor, Allocator >::dispose(), dump_hash_table(), hash_table< Descriptor, Allocator >::empty(), hash_table< Descriptor, Allocator >::expand(), hash_table< Descriptor, Allocator >::find_slot_with_hash(), hash_table< Descriptor, Allocator >::find_with_hash(), htab_statistics(), hash_table< Descriptor, Allocator >::size(), hash_table< Descriptor, Allocator >::traverse(), and vt_find_locations().

template<typename Descriptor , template< typename Type > class Allocator>

template<typename Argument , int(*)(typename Descriptor::value_type **slot, Argument argument) Callback>

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.

References hash_table< Descriptor, Allocator >::size().

Referenced by clobber_overlapping_mems(), compute_bb_dataflow(), create_call_for_reduction(), create_final_loads_for_reduction(), cselib_reset_table(), dataflow_post_merge_adjust(), dataflow_set_clear_at_call(), debug_rename_map(), debug_same_succ(), delete_redundant_insns(), discard_delay_pairs_above(), dump_alloc_pool_statistics(), dump_bitmap_statistics(), dump_cselib_table(), dump_ggc_loc_statistics(), dump_hash_table(), dump_var_infos(), dump_vars(), emit_notes_for_changes(), emit_notes_for_differences(), gather_scalar_reductions(), gen_parallel_loop(), ggc_prune_overhead_list(), gt_pch_save(), optimize_external_refs(), process_changed_values(), remove_useless_values(), separate_decls_in_region(), thread_block(), vt_emit_notes(), and vt_find_locations().

template<typename Descriptor , template< typename Type > class Allocator>

template<typename Argument , int(*)(typename Descriptor::value_type **slot, Argument argument) Callback>

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.

References limit.

Referenced by dump_cand_chains(), and statistics_fini_pass().