GCC Middle and Back End API Reference
hash_table< Descriptor, Lazy, Allocator > Class Template Reference

#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_typefind_with_hash (const compare_type &, hashval_t)
 
value_typefind (const value_type &value)
 
value_typefind_slot (const value_type &value, insert_option insert)
 
value_typefind_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_tablecreate_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_typealloc_entries (size_t n CXX_MEM_STAT_INFO) const
 
value_typefind_empty_slot_for_expand (hashval_t)
 
void verify (const compare_type &comparable, hashval_t hash)
 
bool too_empty_p (unsigned int)
 
void expand ()
 
value_typecheck_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_typem_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>
typedef 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>
typedef 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

◆ 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

◆ ~hash_table()

template<typename Descriptor, bool Lazy, template< typename Type > class Allocator>
hash_table< Descriptor, Lazy, Allocator >::~hash_table ( )

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

◆ begin()

template<typename Descriptor, bool Lazy = false, template< typename Type > class Allocator = xcallocator>
iterator hash_table< Descriptor, Lazy, Allocator >::begin ( ) const
inline

◆ 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

◆ 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

Referenced by find_slot_with_hash().

◆ 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 check_complete_insertion(), gcc_checking_assert, is_deleted(), is_empty(), m_entries, m_n_deleted, mark_deleted(), and size().

Referenced by gt_cleare_cache(), ipa_merge_profiles(), lto_free_function_in_decl_state_for_node(), move_sese_region_to_fn(), 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

Referenced by htab_statistics(), and htab_statistics().

◆ create_ggc()

◆ elements()

◆ 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

◆ empty()

template<typename Descriptor, bool Lazy = false, template< typename Type > class Allocator = xcallocator>
void hash_table< Descriptor, Lazy, Allocator >::empty ( )
inline

◆ empty_slow()

template<typename Descriptor, bool Lazy, template< typename Type > class Allocator>
void hash_table< Descriptor, Lazy, Allocator >::empty_slow ( )
private

◆ end()

template<typename Descriptor, bool Lazy = false, template< typename Type > class Allocator = xcallocator>
iterator hash_table< Descriptor, Lazy, Allocator >::end ( ) const
inline

◆ 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 alloc_entries(), check_complete_insertion(), elements(), find_empty_slot_for_expand(), gcc_checking_assert, ggc_free(), hash_table_higher_prime_index(), hash_table_usage(), is_deleted(), is_empty(), m_entries, m_gather_mem_stats, m_ggc, m_n_deleted, m_n_elements, m_size, m_size_prime_index, prime_tab, size(), and too_empty_p().

Referenced by find_slot_with_hash(), and traverse().

◆ 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

◆ 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 find_empty_slot_for_expand(), gcc_checking_assert, hash_table_mod1(), hash_table_mod2(), is_deleted(), is_empty(), m_entries, m_size, m_size_prime_index, and size().

Referenced by expand(), and find_empty_slot_for_expand().

◆ find_slot()

◆ 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 alloc_entries(), check_complete_insertion(), check_insert_slot(), expand(), hash_table_mod1(), hash_table_mod2(), insert(), is_deleted(), is_empty(), m_collisions, m_entries, m_n_deleted, m_n_elements, m_sanitize_eq_and_hash, m_searches, m_size, m_size_prime_index, mark_empty(), NULL, size(), and verify().

Referenced by add_ttypes_entry(), cgraph_add_edge_to_call_site_hash(), cgraph_update_edge_in_call_site_hash(), find_coalesce_pair(), find_or_insert_inv(), hash_table< decl_table_entry_hasher >::find_slot(), force_const_mem(), move_sese_region_to_fn(), notify_dependents_of_changed_value(), optimize_constant_pool(), register_scoped_attribute(), remove_elt_with_hash(), separate_decls_in_region_debug(), separate_decls_in_region_name(), shared_hash_find_slot_1(), shared_hash_find_slot_noinsert_1(), shared_hash_find_slot_unshare_1(), and vars_copy().

◆ 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 )

◆ 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

◆ is_empty() [1/2]

◆ 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

Referenced by clear_slot(), and remove_elt_with_hash().

◆ 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

◆ 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 check_complete_insertion(), find_slot_with_hash(), m_n_deleted, mark_deleted(), and NULL.

Referenced by hash_table< decl_table_entry_hasher >::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

◆ 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.   

References m_size.

Referenced by empty_slow(), expand(), and traverse().

◆ 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)

◆ 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 check_complete_insertion(), is_deleted(), is_empty(), m_entries, NULL, size(), and traverse_noresize().

Referenced by statistics_fini_pass(), and traverse_noresize().

◆ 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_deleted(), is_empty(), m_entries, m_n_deleted, m_n_elements, m_size, and MIN.

Referenced by find_slot_with_hash(), and find_with_hash().

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

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

◆ m_entries

template<typename Descriptor, bool Lazy = false, template< typename Type > class Allocator = xcallocator>
value_type* hash_table< Descriptor, Lazy, Allocator >::m_entries
private

◆ 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

◆ 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

◆ 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

◆ 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

◆ m_size

template<typename Descriptor, bool Lazy = false, template< typename Type > class Allocator = xcallocator>
size_t hash_table< Descriptor, Lazy, Allocator >::m_size
private

◆ 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

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