#include <hash-table.h>

Data Structures
class	iterator

Public Member Functions
	hash_table (size_t, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS, mem_alloc_origin origin=HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO)

	hash_table (const hash_table &, bool ggc=false, bool sanitize_eq_and_hash=true, bool gather_mem_stats=GATHER_STATISTICS, mem_alloc_origin origin=HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO)

	~hash_table ()

size_t	size () const

size_t	elements () const

size_t	elements_with_deleted () const

void	empty ()

bool	is_empty () const

void	clear_slot (value_type *)

value_type &	find_with_hash (const compare_type &, hashval_t)

value_type &	find (const value_type &value)

value_type *	find_slot (const value_type &value, insert_option insert)

value_type *	find_slot_with_hash (const compare_type &comparable, hashval_t hash, enum insert_option insert)

void	remove_elt_with_hash (const compare_type &, hashval_t)

void	remove_elt (const value_type &value)

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 () const

iterator	end () const

double	collisions () const

void	check_complete_insertion () const

Static Public Member Functions
static hash_table *	create_ggc (size_t n, bool sanitize_eq_and_hash=true CXX_MEM_STAT_INFO)

Private Types
typedef Descriptor::value_type	value_type

typedef Descriptor::compare_type	compare_type

Private Member Functions
void	operator= (hash_table &)

void	empty_slow ()

value_type *	alloc_entries (size_t n CXX_MEM_STAT_INFO) const

value_type *	find_empty_slot_for_expand (hashval_t)

void	verify (const compare_type &comparable, hashval_t hash)

bool	too_empty_p (unsigned int)

void	expand ()

value_type *	check_insert_slot (value_type *ret)

Static Private Member Functions
static bool	is_deleted (value_type &v)

static bool	is_empty (value_type &v)

static void	mark_deleted (value_type &v)

static void	mark_empty (value_type &v)

Private Attributes
value_type *	m_entries

size_t	m_size

size_t	m_n_elements

size_t	m_n_deleted

unsigned int	m_searches

unsigned int	m_collisions

unsigned int	m_size_prime_index

bool	m_ggc

bool	m_sanitize_eq_and_hash

Static Private Attributes
static const bool	m_gather_mem_stats = false

Friends
template<typename T >
void	gt_ggc_mx (hash_table< T > *)

template<typename T >
void	gt_pch_nx (hash_table< T > *)

template<typename T >
void	hashtab_entry_note_pointers (void obj, void h, gt_pointer_operator op, void *cookie)

template<typename T , typename U , typename V >
void	gt_pch_nx (hash_map< T, U, V > , gt_pointer_operator, void )

template<typename T , typename U >
void	gt_pch_nx (hash_set< T, false, U > , gt_pointer_operator, void )

template<typename T >
void	gt_pch_nx (hash_table< T > , gt_pointer_operator, void )

template<typename T >
void	gt_cleare_cache (hash_table< T > *)

Detailed Description

template<typename Descriptor, bool Lazy = false, template< typename Type > class Allocator = xcallocator>
class hash_table< Descriptor, Lazy, Allocator >

User-facing hash table type.

  The table stores elements of type Descriptor::value_type and uses
  the static descriptor functions described at the top of the file
  to hash, compare and remove elements.

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

    Storage is an implementation detail and should not be used outside the
    hash table code.

Member Typedef Documentation

◆ compare_type

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

private

◆ value_type

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

private

Constructor & Destructor Documentation

◆ hash_table() [1/2]

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

hash_table< Descriptor, Lazy, Allocator >::hash_table	(	size_t	size,
		bool	ggc = false,
		bool	sanitize_eq_and_hash = true,
		bool	gather_mem_stats = GATHER_STATISTICS,
		mem_alloc_origin origin	MEM_STAT_DECL = HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO )

explicit

References hash_table< Descriptor, Lazy, Allocator >::alloc_entries(), FINAL_PASS_MEM_STAT, hash_table_higher_prime_index(), hash_table_usage(), hash_table< Descriptor, Lazy, Allocator >::m_entries, hash_table< Descriptor, Lazy, Allocator >::m_gather_mem_stats, hash_table< Descriptor, Lazy, Allocator >::m_size, hash_table< Descriptor, Lazy, Allocator >::m_size_prime_index, NULL, PASS_MEM_STAT, prime_ent::prime, prime_tab, and hash_table< Descriptor, Lazy, Allocator >::size().

◆ hash_table() [2/2]

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

hash_table< Descriptor, Lazy, Allocator >::hash_table	(	const hash_table< Descriptor, Lazy, Allocator > &	h,
		bool	ggc = false,
		bool	sanitize_eq_and_hash = true,
		bool	gather_mem_stats = GATHER_STATISTICS,
		mem_alloc_origin origin	MEM_STAT_DECL = HASH_TABLE_ORIGIN CXX_MEM_STAT_INFO )

explicit

References hash_table< Descriptor, Lazy, Allocator >::check_complete_insertion(), FINAL_PASS_MEM_STAT, hash_table_usage(), hash_table< Descriptor, Lazy, Allocator >::m_entries, hash_table< Descriptor, Lazy, Allocator >::m_gather_mem_stats, hash_table< Descriptor, Lazy, Allocator >::m_size, NULL, and hash_table< Descriptor, Lazy, Allocator >::size().

◆ ~hash_table()

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

hash_table< Descriptor, Lazy, Allocator >::~hash_table ( )

References ggc_free(), hash_table_usage(), i, and is_empty().

Member Function Documentation

◆ alloc_entries()

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

hash_table< Descriptor, Lazy, Allocator >::value_type * hash_table< Descriptor, Lazy, Allocator >::alloc_entries ( size_t n MEM_STAT_DECL ) const

inlineprivate

This function returns an array of empty hash table elements.

References gcc_assert, ggc_cleared_vec_alloc(), hash_table_usage(), i, NULL, and PASS_MEM_STAT.

Referenced by hash_table< Descriptor, Lazy, Allocator >::hash_table().

◆ begin()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::check_complete_insertion(), hash_table< Descriptor, Lazy, Allocator >::m_entries, hash_table< Descriptor, Lazy, Allocator >::m_size, NULL, and hash_table< Descriptor, Lazy, Allocator >::iterator::slide().

Referenced by hash_set< KeyId, Lazy, Traits >::begin(), loop_distribution::distribute_loop(), gt_cleare_cache(), shrink_simd_arrays(), and hash_set< KeyId, Lazy, Traits >::traverse().

◆ check_complete_insertion()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

void hash_table< Descriptor, Lazy, Allocator >::check_complete_insertion ( ) const

inline

References gcc_checking_assert, gcc_unreachable, hash_table< Descriptor, Lazy, Allocator >::is_empty(), hash_table< Descriptor, Lazy, Allocator >::m_entries, hash_table< Descriptor, Lazy, Allocator >::m_size, and NULL.

Referenced by hash_table< Descriptor, Lazy, Allocator >::begin(), gt_pch_nx(), and hash_table< Descriptor, Lazy, Allocator >::hash_table().

◆ check_insert_slot()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

value_type * hash_table< Descriptor, Lazy, Allocator >::check_insert_slot ( value_type * ret )

inlineprivate

References gcc_checking_assert, and hash_table< Descriptor, Lazy, Allocator >::is_empty().

◆ clear_slot()

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

void hash_table< Descriptor, Lazy, 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 gcc_checking_assert, and is_empty().

Referenced by do_unwind(), emit_note_insn_var_location(), gt_cleare_cache(), ipa_merge_profiles(), lto_free_function_in_decl_state_for_node(), move_sese_region_to_fn(), avail_exprs_stack::pop_to_marker(), release_section_hash_entry(), remove_value_from_changed_variables(), symbol_table::unlink_from_assembler_name_hash(), and variable_was_changed().

◆ collisions()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::m_collisions, and hash_table< Descriptor, Lazy, Allocator >::m_searches.

Referenced by htab_statistics(), and htab_statistics().

◆ create_ggc()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

static hash_table * hash_table< Descriptor, Lazy, Allocator >::create_ggc	(	size_t	n,
		bool	sanitize_eq_and_hash = true CXX_MEM_STAT_INFO )

inlinestatic

References ggc_alloc(), HASH_TABLE_ORIGIN, PASS_MEM_STAT, and table.

Referenced by add_addr_table_entry(), add_filepath_AT_string(), add_skeleton_AT_string(), create_constant_pool(), decl_debug_args_insert(), decl_for_type_lookup(), expand_block_edges(), find_AT_string(), cgraph_node::get_edge(), init_emit_once(), init_one_libfunc_visibility(), init_optabs(), init_temp_slots(), init_tree_ssa(), init_ttree(), init_varasm_once(), cgraph_node::insert_new_function_version(), ipa_check_create_edge_args(), ipa_record_return_value_range(), ipcp_transformation_initialize(), new_ctf_container(), omp_lto_input_declare_variant_alt(), omp_resolve_declare_variant(), output_line_string(), record_insns(), record_loop_exits(), record_tm_clone_pair(), record_tm_replacement(), scev_initialize(), symtab_node::set_section_for_node(), split_bb_make_tm_edge(), symbol_table::symtab_initialize_asm_name_hash(), and types_used_by_var_decl_insert().

◆ elements()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

◆ elements_with_deleted()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::m_n_elements.

◆ empty()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::elements(), and hash_table< Descriptor, Lazy, Allocator >::empty_slow().

Referenced by ctfc_delete_container(), delete_tree_ssa(), hash_set< KeyId, Lazy, Traits >::empty(), parallelize_loops(), release_recorded_exits(), cgraph_node::remove(), and cgraph_node::remove_callees().

◆ empty_slow()

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

void hash_table< Descriptor, Lazy, Allocator >::empty_slow ( )

private

Implements empty() in cases where it isn't a no-op.

References ggc_free(), hash_table_higher_prime_index(), i, is_empty(), prime_ent::prime, and prime_tab.

Referenced by hash_table< Descriptor, Lazy, Allocator >::empty().

◆ end()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

Referenced by loop_distribution::distribute_loop(), hash_set< KeyId, Lazy, Traits >::end(), gt_cleare_cache(), shrink_simd_arrays(), and hash_set< KeyId, Lazy, Traits >::traverse().

◆ expand()

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

void hash_table< Descriptor, Lazy, 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 gcc_checking_assert, ggc_free(), hash_table_higher_prime_index(), hash_table_usage(), is_empty(), prime_ent::prime, and prime_tab.

◆ find()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::find_with_hash().

Referenced by adjust_simduid_builtins(), apply_opt_in_copies(), contains(), dead_debug_global_find(), maybe_copy_prologue_epilogue_insn(), prune_predictions_for_bb(), reduction_phi(), shrink_simd_arrays(), and vect_peeling_hash_insert().

◆ find_empty_slot_for_expand()

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

hash_table< Descriptor, Lazy, Allocator >::value_type * hash_table< Descriptor, Lazy, 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 gcc_checking_assert, hash_table_mod1(), hash_table_mod2(), and is_empty().

◆ find_slot()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::find_slot_with_hash(), and insert().

Referenced by account_time_size(), add_action_record(), add_ehspec_entry(), nontrapping_dom_walker::add_or_mark_expr(), analyze_insns_in_loop(), build_new_reduction(), canon_file_name(), ctf_dtd_insert(), ctf_dtd_lookup(), ctf_dvd_ignore_insert(), ctf_dvd_ignore_lookup(), ctf_dvd_insert(), ctf_dvd_lookup(), dead_debug_global_insert(), find_or_create_vtbl_map_node(), loop_distribution::get_data_dependence(), ipa_merge_profiles(), avail_exprs_stack::lookup_avail_expr(), lookup_or_add_counter(), fwd_jt_path_registry::lookup_redirection_data(), lookup_tmp_var(), lto_free_function_in_decl_state_for_node(), lto_get_function_in_decl_state(), maybe_copy_prologue_epilogue_insn(), avail_exprs_stack::pop_to_marker(), populate_coalesce_list_for_outofssa(), possible_polymorphic_call_targets(), prune_predictions_for_bb(), record_insns(), fwd_jt_path_registry::remove_jump_threads_including(), avail_exprs_stack::simplify_binary_operation(), split_out_patterns(), streamer_string_index(), take_address_of(), undistribute_ops_list(), fwd_jt_path_registry::update_cfg(), update_mem_ref_hash_table(), vect_peeling_hash_insert(), vect_transform_loops(), vtbl_map_get_node(), and vtbl_map_node_registration_insert().

◆ find_slot_with_hash()

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

hash_table< Descriptor, Lazy, Allocator >::value_type * hash_table< Descriptor, Lazy, 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(), insert(), is_empty(), and NULL.

Referenced by hash_set< KeyId, Lazy, Traits >::add(), add_ttypes_entry(), cgraph_add_edge_to_call_site_hash(), cgraph_update_edge_in_call_site_hash(), hash_set< KeyId, Lazy, Traits >::contains(), cvc_insert(), do_unwind(), find_coalesce_pair(), find_or_insert_inv(), hash_table< Descriptor, Lazy, Allocator >::find_slot(), force_const_mem(), symtab_node::get_for_asmname(), get_odr_type(), symbol_table::insert_to_assembler_name_hash(), move_sese_region_to_fn(), notify_dependents_of_changed_value(), optimize_constant_pool(), avail_exprs_stack::record_cond(), register_scoped_attribute(), release_section_hash_entry(), remove_value_from_changed_variables(), separate_decls_in_region_debug(), separate_decls_in_region_name(), symtab_node::set_section_for_node(), shared_hash_find_slot_1(), shared_hash_find_slot_noinsert_1(), shared_hash_find_slot_unshare_1(), symbol_table::unlink_from_assembler_name_hash(), unshare_variable(), variable_from_dropped(), variable_was_changed(), vars_copy(), visit_reference_op_call(), 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().

◆ find_with_hash()

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

hash_table< Descriptor, Lazy, Allocator >::value_type & hash_table< Descriptor, Lazy, 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(), is_empty(), and NULL.

Referenced by candidate(), hash_set< KeyId, Lazy, Traits >::contains(), cvc_lookup(), dataflow_set_different(), emit_notes_for_differences_1(), emit_notes_for_differences_2(), hash_table< Descriptor, Lazy, Allocator >::find(), find_loc_in_1pdv(), find_mem_expr_in_1pdv(), cgraph_node::get_edge(), loc_exp_insert_dep(), notify_dependents_of_changed_value(), notify_dependents_of_resolved_value(), shared_hash_find_1(), and vt_expand_loc_callback().

◆ is_deleted()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

static bool hash_table< Descriptor, Lazy, Allocator >::is_deleted ( value_type & v )

inlinestaticprivate

References gcc_checking_assert.

Referenced by hash_table< Descriptor, Lazy, Allocator >::iterator::slide().

◆ is_empty() [1/2]

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

bool hash_table< Descriptor, Lazy, Allocator >::is_empty ( ) const

inline

References hash_table< Descriptor, Lazy, Allocator >::elements().

Referenced by hash_table< Descriptor, Lazy, Allocator >::check_complete_insertion(), hash_table< Descriptor, Lazy, Allocator >::check_insert_slot(), dump_vars(), emit_notes_for_changes(), gather_scalar_reductions(), gen_parallel_loop(), hash_set< KeyId, Lazy, Traits >::is_empty(), reduction_phi(), separate_decls_in_region(), hash_table< Descriptor, Lazy, Allocator >::iterator::slide(), transform_to_exit_first_loop(), try_create_reduction_list(), and vt_emit_notes().

◆ is_empty() [2/2]

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

static bool hash_table< Descriptor, Lazy, Allocator >::is_empty ( value_type & v )

inlinestaticprivate

◆ mark_deleted()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

static void hash_table< Descriptor, Lazy, Allocator >::mark_deleted ( value_type & v )

inlinestaticprivate

References gcc_checking_assert.

◆ mark_empty()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

static void hash_table< Descriptor, Lazy, Allocator >::mark_empty ( value_type & v )

inlinestaticprivate

◆ operator=()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

void hash_table< Descriptor, Lazy, Allocator >::operator= ( hash_table< Descriptor, Lazy, Allocator > & )

private

◆ remove_elt()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::remove_elt_with_hash().

◆ remove_elt_with_hash()

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

void hash_table< Descriptor, Lazy, 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 NULL.

Referenced by hash_set< KeyId, Lazy, Traits >::remove(), cgraph_edge::remove_caller(), hash_table< Descriptor, Lazy, Allocator >::remove_elt(), and cgraph_edge::set_call_stmt().

◆ size()

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

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

inline

References hash_table< Descriptor, Lazy, Allocator >::m_size.

Referenced by hash_table< Descriptor, Lazy, Allocator >::hash_table(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), htab_statistics(), htab_statistics(), and vt_find_locations().

◆ too_empty_p()

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

bool hash_table< Descriptor, Lazy, Allocator >::too_empty_p ( unsigned int elts )

inlineprivate

Return true if the current table is excessively big for ELTS elements.

◆ traverse()

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

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

void hash_table< Descriptor, Lazy, 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 btf_collect_translated_types(), clobber_overlapping_mems(), compute_bb_dataflow(), create_call_for_reduction(), create_final_loads_for_reduction(), ctf_preprocess(), dataflow_post_merge_adjust(), dataflow_set_clear_at_call(), dump_vars(), emit_notes_for_changes(), emit_notes_for_differences(), gather_scalar_reductions(), gen_parallel_loop(), process_changed_values(), separate_decls_in_region(), fwd_jt_path_registry::thread_block_1(), vt_emit_notes(), and vt_find_locations().

◆ traverse_noresize()

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

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

void hash_table< Descriptor, Lazy, 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 is_empty(), and NULL.

Referenced by statistics_fini(), and statistics_fini_pass().

◆ verify()

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

void hash_table< Descriptor, Lazy, Allocator >::verify	(	const compare_type &	comparable,
		hashval_t	hash )

private

Verify that all existing elements in the hash table which are
equal to COMPARABLE have an equal HASH value provided as argument.
Also check that the hash table element counts are correct.

References gcc_checking_assert, hash_table_sanitize_eq_limit, hashtab_chk_error(), i, is_empty(), and MIN.

Friends And Related Symbol Documentation

◆ gt_cleare_cache

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T >

void gt_cleare_cache ( hash_table< T > * )

friend

◆ gt_ggc_mx

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T >

void gt_ggc_mx ( hash_table< T > * )

friend

◆ gt_pch_nx [1/4]

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T , typename U , typename V >

void gt_pch_nx	(	hash_map< T, U, V > *	,
		gt_pointer_operator	,
		void *	)

friend

◆ gt_pch_nx [2/4]

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T , typename U >

void gt_pch_nx	(	hash_set< T, false, U > *	,
		gt_pointer_operator	,
		void *	)

friend

◆ gt_pch_nx [3/4]

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T >

void gt_pch_nx ( hash_table< T > * )

friend

◆ gt_pch_nx [4/4]

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T >

void gt_pch_nx	(	hash_table< T > *	,
		gt_pointer_operator	,
		void *	)

friend

◆ hashtab_entry_note_pointers

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

template<typename T >

void hashtab_entry_note_pointers	(	void *	obj,
		void *	h,
		gt_pointer_operator	op,
		void *	cookie )

friend

Referenced by gt_pch_nx().

Field Documentation

◆ m_collisions

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

unsigned int hash_table< Descriptor, Lazy, Allocator >::m_collisions

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::collisions().

◆ m_entries

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

value_type* hash_table< Descriptor, Lazy, Allocator >::m_entries

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::begin(), hash_table< Descriptor, Lazy, Allocator >::check_complete_insertion(), gt_ggc_mx(), gt_pch_nx(), gt_pch_nx(), gt_pch_nx(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), and hash_table< Descriptor, Lazy, Allocator >::hash_table().

◆ m_gather_mem_stats

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

const bool hash_table< Descriptor, Lazy, Allocator >::m_gather_mem_stats = false

staticprivate

Referenced by hash_table< Descriptor, Lazy, Allocator >::hash_table(), and hash_table< Descriptor, Lazy, Allocator >::hash_table().

◆ m_ggc

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

bool hash_table< Descriptor, Lazy, Allocator >::m_ggc

private

◆ m_n_deleted

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

size_t hash_table< Descriptor, Lazy, Allocator >::m_n_deleted

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::elements().

◆ m_n_elements

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

size_t hash_table< Descriptor, Lazy, Allocator >::m_n_elements

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::elements(), and hash_table< Descriptor, Lazy, Allocator >::elements_with_deleted().

◆ m_sanitize_eq_and_hash

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

bool hash_table< Descriptor, Lazy, Allocator >::m_sanitize_eq_and_hash

private

◆ m_searches

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

unsigned int hash_table< Descriptor, Lazy, Allocator >::m_searches

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::collisions().

◆ m_size

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

size_t hash_table< Descriptor, Lazy, Allocator >::m_size

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::begin(), hash_table< Descriptor, Lazy, Allocator >::check_complete_insertion(), gt_ggc_mx(), gt_pch_nx(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), and hash_table< Descriptor, Lazy, Allocator >::size().

◆ m_size_prime_index

template<typename Descriptor , bool Lazy = false, template< typename Type > class Allocator = xcallocator>

unsigned int hash_table< Descriptor, Lazy, Allocator >::m_size_prime_index

private

Referenced by hash_table< Descriptor, Lazy, Allocator >::hash_table().

The documentation for this class was generated from the following file:

hash-table.h

Data Structures

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ compare_type

◆ value_type

Constructor & Destructor Documentation

◆ hash_table() [1/2]

◆ hash_table() [2/2]

◆ ~hash_table()

Member Function Documentation

◆ alloc_entries()

◆ begin()

◆ check_complete_insertion()

◆ check_insert_slot()

◆ clear_slot()

◆ collisions()

◆ create_ggc()

◆ elements()

◆ elements_with_deleted()

◆ empty()

◆ empty_slow()

◆ end()

◆ expand()

◆ find()

◆ find_empty_slot_for_expand()

◆ find_slot()

◆ find_slot_with_hash()

◆ find_with_hash()

◆ is_deleted()

◆ is_empty() [1/2]

◆ is_empty() [2/2]

◆ mark_deleted()

◆ mark_empty()

◆ operator=()

◆ remove_elt()

◆ remove_elt_with_hash()

◆ size()

◆ too_empty_p()

◆ traverse()

◆ traverse_noresize()

◆ verify()

Friends And Related Symbol Documentation

◆ gt_cleare_cache

◆ gt_ggc_mx

◆ gt_pch_nx [1/4]

◆ gt_pch_nx [2/4]

◆ gt_pch_nx [3/4]

◆ gt_pch_nx [4/4]

◆ hashtab_entry_note_pointers

Field Documentation

◆ m_collisions

◆ m_entries

◆ m_gather_mem_stats

◆ m_ggc

◆ m_n_deleted

◆ m_n_elements

◆ m_sanitize_eq_and_hash

◆ m_searches

◆ m_size

◆ m_size_prime_index