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

#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_typefind (const value_type *value)
value_typefind_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

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

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.

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

Referenced by invariant_or_equiv_p(), and vt_find_locations().

template<typename Descriptor , template< typename Type > class Allocator>
double hash_table< Descriptor, Allocator >::collisions ( )
inline

Return the fraction of fixed collisions during all work with given hash table.

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

template<typename Descriptor , template< typename Type > class Allocator>
void hash_table< Descriptor, Allocator >::create ( size_t  size)
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.

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

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.

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

Referenced by compare_pairs(), and find_src_set_src().

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.

template<typename Descriptor , template< typename Type > class Allocator>
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().

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.

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.

Resize only when table after removal of unused elements is either too full or too empty.

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.

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

Referenced by adjust_simduid_builtins(), free_original_copy_tables(), and insert_var_expansion_initialization().

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 gcc_assert, hash_table_higher_prime_index(), NULL, 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_slot ( const value_type value,
enum insert_option  insert 
)
inline
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.

Referenced by assign_symbol_names(), attrs_list_member(), clone_tree(), connect_traces(), do_complex_constraint(), get_biv_step(), 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().

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(), NULL, and hash_table< Descriptor, Allocator >::size().

Referenced by attrs_list_union(), and gt_pch_note_object().

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 adjust_simduid_builtins(), dead_debug_global_find(), asan_mem_ref_hasher::equal(), and insert_var_expansion_initialization().

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.

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

template<typename Descriptor , template< typename Type > class Allocator>
size_t hash_table< Descriptor, Allocator >::size ( )
inline
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 NULL.

Referenced by create_call_for_reduction(), create_call_for_reduction_1(), discard_useless_locs(), ptr_hash_hasher::equal(), and generate_skeleton().

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.


Field Documentation

template<typename Descriptor, template< typename Type > class Allocator = xcallocator>
hash_table_control<value_type>* hash_table< Descriptor, Allocator >::htab
private

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