hash-table.h File Reference

#include "statistics.h"
#include "ggc.h"
#include "vec.h"
#include "hashtab.h"
#include "inchash.h"
#include "mem-stats-traits.h"
#include "hash-traits.h"
#include "hash-map-traits.h"
#include "mem-stats.h"
#include "hash-map.h"

Include dependency graph for hash-table.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	xcallocator< Type >
struct	prime_ent
class	hash_table< Descriptor, Lazy, Allocator >
class	hash_table< Descriptor, Lazy, Allocator >::iterator

Macros
#define	FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER)

Functions
unsigned int	hash_table_higher_prime_index (unsigned long n) ATTRIBUTE_PURE
ATTRIBUTE_NORETURN ATTRIBUTE_COLD void	hashtab_chk_error ()
hashval_t	mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
hashval_t	hash_table_mod1 (hashval_t hash, unsigned int index)
hashval_t	hash_table_mod2 (hashval_t hash, unsigned int index)
mem_alloc_description< mem_usage > &	hash_table_usage (void)
void	dump_hash_table_loc_statistics (void)
template<typename E >
void	gt_ggc_mx (hash_table< E > *h)
template<typename D >
void	hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op, void *cookie)
template<typename D >
void	gt_pch_nx (hash_table< D > *h)
template<typename D >
void	gt_pch_nx (hash_table< D > *h, gt_pointer_operator op, void *cookie)
template<typename H >
void	gt_cleare_cache (hash_table< H > *h)

Variables
struct prime_ent const	prime_tab []
unsigned int	hash_table_sanitize_eq_limit

Macro Definition Documentation

FOR_EACH_HASH_TABLE_ELEMENT

#define FOR_EACH_HASH_TABLE_ELEMENT	(		HTAB,
			RESULT,
			TYPE,
			ITER )

Value:

  for ((ITER) = (HTAB).begin (); \
       (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \
       ++(ITER))

Iterate through the elements of hash_table HTAB,
using hash_table <....>::iterator ITER,
storing each element in RESULT, which is of type TYPE.   

Referenced by dataflow_set_different(), dataflow_set_merge(), dataflow_set_union(), dump_tm_memopt_set(), finish_tm_clone_pairs(), free_rpo_vn(), free_vn_table(), gather_stats_on_scev_database(), insert_phi_nodes(), output_object_blocks(), set_hashtable_value_ids(), tm_log_emit(), and vars_copy().

Function Documentation

dump_hash_table_loc_statistics()

void dump_hash_table_loc_statistics ( void )

extern

Support function for statistics.   

References mem_alloc_description< T >::dump(), ggc_alloc(), HASH_SET_ORIGIN, HASH_TABLE_ORIGIN, hash_table_usage(), and i.

Referenced by dump_memory_report().

gt_cleare_cache()

template<typename H >

void gt_cleare_cache ( hash_table< H > * h )

inline

References ggc_alloc(), and table.

gt_ggc_mx()

template<typename E >

void gt_ggc_mx ( hash_table< E > * h )

inline

ggc walking routines.   

References ggc_alloc(), ggc_test_and_set_mark, i, and table.

gt_pch_nx() [1/2]

template<typename D >

void gt_pch_nx

(

hash_table< D > *

h

)

References gcc_checking_assert, ggc_alloc(), gt_pch_note_object(), and i.

gt_pch_nx() [2/2]

template<typename D >

void gt_pch_nx ( hash_table< D > * h, gt_pointer_operator op, void * cookie )

inline

References ggc_alloc(), and NULL.

hash_table_higher_prime_index()

unsigned int hash_table_higher_prime_index ( unsigned long n )

extern

Functions for computing hash table indexes.   

The following function returns an index into the above table of the
nearest prime number which is at least N, and near a power of two.  

References gcc_assert, ggc_alloc(), prime_ent::prime, and prime_tab.

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

hash_table_mod1()

hashval_t hash_table_mod1 ( hashval_t hash, unsigned int index )

inline

Compute the primary table index for HASH given current prime index.   

References CHAR_BIT, gcc_checking_assert, ggc_alloc(), prime_ent::inv, mul_mod(), prime_ent::prime, prime_tab, and prime_ent::shift.

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

hash_table_mod2()

hashval_t hash_table_mod2 ( hashval_t hash, unsigned int index )

inline

Compute the secondary table index for HASH given current prime index.   

References CHAR_BIT, gcc_checking_assert, ggc_alloc(), prime_ent::inv_m2, mul_mod(), prime_ent::prime, prime_tab, and prime_ent::shift.

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

hash_table_usage()

mem_alloc_description< mem_usage > & hash_table_usage ( void )

extern

As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
mem-stats.h after hash_table declaration.   

Return a reference to the lazily initialized hash-table usage description.
This needs to be a function rather than a simple global variable so that it
is reliably initialized before hash table variables in other files such as
sem_item::m_type_hash_cache.   

References usage().

Referenced by hash_table< Descriptor, Lazy, Allocator >::alloc_entries(), dump_hash_table_loc_statistics(), hash_table< Descriptor, Lazy, Allocator >::expand(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), and hash_table< Descriptor, Lazy, Allocator >::~hash_table().

hashtab_chk_error()

ATTRIBUTE_NORETURN ATTRIBUTE_COLD void hashtab_chk_error ( )

extern

Report a hash table checking error.   

References gcc_unreachable, and ggc_alloc().

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

hashtab_entry_note_pointers()

template<typename D >

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

inline

mul_mod()

hashval_t mul_mod ( hashval_t x, hashval_t y, hashval_t inv, int shift )

inline

Return X % Y using multiplicative inverse values INV and SHIFT.

The multiplicative inverses computed above are for 32-bit types,
and requires that we be able to compute a highpart multiply.

FIX: I am not at all convinced that
  3 loads, 2 multiplications, 3 shifts, and 3 additions
will be faster than
  1 load and 1 modulus
on modern systems running a compiler.   

References ggc_alloc(), prime_ent::inv, r, shift, and y.

Referenced by hash_table_mod1(), and hash_table_mod2().

Variable Documentation

hash_table_sanitize_eq_limit

unsigned int hash_table_sanitize_eq_limit

extern

Limit number of comparisons when calling hash_table<>::verify.   

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

prime_tab

struct prime_ent const prime_tab[]

extern

A type-safe hash table template.
   Copyright (C) 2012-2024 Free Software Foundation, Inc.
   Contributed by Lawrence Crowl <crowl@google.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.   

This file implements a typed hash table.
The implementation borrows from libiberty's hashtab.   

Table of primes and multiplicative inverses.

Note that these are not minimally reduced inverses.  Unlike when generating
code to divide by a constant, we want to be able to use the same algorithm
all the time.  All of these inverses (are implied to) have bit 32 set.

For the record, here's the function that computed the table; it's a 
vastly simplified version of the function of the same name from gcc.   

Referenced by hash_table< Descriptor, Lazy, Allocator >::empty_slow(), hash_table< Descriptor, Lazy, Allocator >::expand(), hash_table< Descriptor, Lazy, Allocator >::hash_table(), hash_table_higher_prime_index(), hash_table_mod1(), and hash_table_mod2().