Merge C++ conversion into trunk (4/6 - hash table rewrite)
Richard Guenther
rguenther@suse.de
Wed Aug 15 10:59:00 GMT 2012
On Sun, 12 Aug 2012, Diego Novillo wrote:
> This implements a new C++ hash table.
>
> See http://gcc.gnu.org/ml/gcc-patches/2012-08/msg00711.html for
> details.
>
> Diego.
Btw, a new common allocator in hash-table.h should be one using
an obstack. That's useful at least for short-lived hashtables or
those which never shrink (which is quite common). The of course
the GGC variant.
Richard.
> 2012-08-12 Lawrence Crowl <crowl@google.com>
>
> * hash-table.h: New. Implementation borrowed from libiberty/hashtab.c.
> * hash-table.c: Likewise.
> * tree-ssa-tail-merge.c: Include hash-table.h instead of hashtab.h.
> (static htab_t same_succ_htab): Change type to hash_table;
> move specification of helper functions from create call to declaration.
> Change users to invoke member functions.
> (same_succ_print_traverse): Make extern ssa_.... Change callers.
> Remove void* casting.
> (same_succ_hash): Likewise.
> (same_succ_equal): Likewise.
> (same_succ_delete): Likewise.
> * tree-ssa-threadupdate.c: Include hash-table.h.
> (struct local_info): Rename to ssa_local_info_t to avoid overloading
> the type name local_info with the variable name local_info.
> (static htab_t redirection_data): Change type to hash_table.
> Move specification of helper functions from create call to declaration.
> Change users to invoke member functions.
> (redirection_data_hash): Make extern ssa_.... Change callers.
> Remove void* casting.
> (redirection_data_eq): Likewise.
> (fix_duplicate_block_edges): Likewise.
> (create_duplicates): Likewise.
> (fixup_template_block): Likewise.
> (redirect_edges): Likewise.
> (lookup_redirection_data): Change types associated with the hash table
> from void* to their actual type. Remove unnecessary casts.
> * tree-ssa-ccp.c: Include hash-table.h.
> (typedef gimple_htab): New. Uses hash_table. Replace specific uses
> of htab_t with gimple_htab. Change users to invoke member functions.
> Move specification of helper functions from create call to declaration.
> * tree-ssa-coalesce.c: Include hash-table.h instead of hashtab.h.
> (hash_ssa_name_by_var): Make extern. Remove void* casting.
> (eq_ssa_name_by_var): Likewise.
> (coalesce_ssa_name): Change type of local static htab_t ssa_name_hash
> to hash_table. Change users to invoke member functions.
> Move specification of helper functions from create call to declaration.
> * coverage.c: Include hash-table.h instead of hashtab.h.
> (static htab_t counts_hash): Change type to hash_table;
> move specification of helper functions from create call to declaration.
> Change users to invoke member functions.
> (htab_counts_entry_hash): Make extern. Rename with coverage_... instead
> of htab_... Remove void* casting.
> (htab_counts_entry_eq): Likewise.
> (htab_counts_entry_del): Likewise.
> * tree-ssa-pre.c: Include hash-table.h instead of hashtab.h.
> (static htab_t expression_to_id): Change type to hash_table.
> Move specification of helper functions from create call to declaration.
> Change users to invoke member functions.
> (static htab_t phi_translate_table): Likewise.
> (pre_expr_eq): Make extern ssa_.... Change callers.
> Remove void* casting.
> (pre_expr_hash): Likewise.
> (expr_pred_trans_hash): Likewise.
> (expr_pred_trans_eq): Likewise.
> (alloc_expression_id): Change types associated with the hash table
> from void* to their actual type. Remove unnecessary casts.
> (lookup_expression_id): Likewise.
> (phi_trans_lookup): Likewise.
> (phi_trans_add): Likewise.
> * stringpool.c: Rename uses of libcpp typedef hash_table to
> cpp_hash_table.
> * Makefile.in: Add hash-table.o to OBJS-libcommon-target.
> Add $(HASH_TABLE_H). Add new dependences on $(HASH_TABLE_H).
>
> diff --git a/gcc/coverage.c b/gcc/coverage.c
> index af52289..3fea525 100644
> --- a/gcc/coverage.c
> +++ b/gcc/coverage.c
> @@ -43,7 +43,7 @@ along with GCC; see the file COPYING3. If not see
> #include "ggc.h"
> #include "coverage.h"
> #include "langhooks.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
> #include "tree-iterator.h"
> #include "cgraph.h"
> #include "dumpfile.h"
> @@ -109,17 +109,11 @@ static unsigned bbg_file_stamp;
> /* Name of the count data (gcda) file. */
> static char *da_file_name;
>
> -/* Hash table of count data. */
> -static htab_t counts_hash = NULL;
> -
> /* The names of merge functions for counters. */
> static const char *const ctr_merge_functions[GCOV_COUNTERS] = GCOV_MERGE_FUNCTIONS;
> static const char *const ctr_names[GCOV_COUNTERS] = GCOV_COUNTER_NAMES;
>
> /* Forward declarations. */
> -static hashval_t htab_counts_entry_hash (const void *);
> -static int htab_counts_entry_eq (const void *, const void *);
> -static void htab_counts_entry_del (void *);
> static void read_counts_file (void);
> static tree build_var (tree, tree, int);
> static void build_fn_info_type (tree, unsigned, tree);
> @@ -149,32 +143,31 @@ get_gcov_unsigned_t (void)
> return lang_hooks.types.type_for_mode (mode, true);
> }
>
> -static hashval_t
> -htab_counts_entry_hash (const void *of)
> +inline hashval_t
> +coverage_counts_entry_hash (const counts_entry_t *entry)
> {
> - const counts_entry_t *const entry = (const counts_entry_t *) of;
> -
> return entry->ident * GCOV_COUNTERS + entry->ctr;
> }
>
> -static int
> -htab_counts_entry_eq (const void *of1, const void *of2)
> +inline int
> +coverage_counts_entry_eq (const counts_entry_t *entry1,
> + const counts_entry_t *entry2)
> {
> - const counts_entry_t *const entry1 = (const counts_entry_t *) of1;
> - const counts_entry_t *const entry2 = (const counts_entry_t *) of2;
> -
> return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
> }
>
> -static void
> -htab_counts_entry_del (void *of)
> +inline void
> +coverage_counts_entry_del (counts_entry_t *entry)
> {
> - counts_entry_t *const entry = (counts_entry_t *) of;
> -
> free (entry->counts);
> free (entry);
> }
>
> +/* Hash table of count data. */
> +static hash_table <counts_entry_t, coverage_counts_entry_hash,
> + coverage_counts_entry_eq, coverage_counts_entry_del>
> + counts_hash;
> +
> /* Read in the counts file, if available. */
>
> static void
> @@ -214,9 +207,7 @@ read_counts_file (void)
> tag = gcov_read_unsigned ();
> bbg_file_stamp = crc32_unsigned (bbg_file_stamp, tag);
>
> - counts_hash = htab_create (10,
> - htab_counts_entry_hash, htab_counts_entry_eq,
> - htab_counts_entry_del);
> + counts_hash.create (10);
> while ((tag = gcov_read_unsigned ()))
> {
> gcov_unsigned_t length;
> @@ -264,8 +255,7 @@ read_counts_file (void)
> elt.ident = fn_ident;
> elt.ctr = GCOV_COUNTER_FOR_TAG (tag);
>
> - slot = (counts_entry_t **) htab_find_slot
> - (counts_hash, &elt, INSERT);
> + slot = counts_hash.find_slot (&elt, INSERT);
> entry = *slot;
> if (!entry)
> {
> @@ -285,14 +275,14 @@ read_counts_file (void)
> error ("checksum is (%x,%x) instead of (%x,%x)",
> entry->lineno_checksum, entry->cfg_checksum,
> lineno_checksum, cfg_checksum);
> - htab_delete (counts_hash);
> + counts_hash.dispose ();
> break;
> }
> else if (entry->summary.num != n_counts)
> {
> error ("Profile data for function %u is corrupted", fn_ident);
> error ("number of counters is %d instead of %d", entry->summary.num, n_counts);
> - htab_delete (counts_hash);
> + counts_hash.dispose ();
> break;
> }
> else if (elt.ctr >= GCOV_COUNTERS_SUMMABLE)
> @@ -318,7 +308,7 @@ read_counts_file (void)
> {
> error (is_error < 0 ? "%qs has overflowed" : "%qs is corrupted",
> da_file_name);
> - htab_delete (counts_hash);
> + counts_hash.dispose ();
> break;
> }
> }
> @@ -336,7 +326,7 @@ get_coverage_counts (unsigned counter, unsigned expected,
> counts_entry_t *entry, elt;
>
> /* No hash table, no counts. */
> - if (!counts_hash)
> + if (!counts_hash.is_created ())
> {
> static int warned = 0;
>
> @@ -350,7 +340,7 @@ get_coverage_counts (unsigned counter, unsigned expected,
>
> elt.ident = current_function_funcdef_no + 1;
> elt.ctr = counter;
> - entry = (counts_entry_t *) htab_find (counts_hash, &elt);
> + entry = counts_hash.find (&elt);
> if (!entry || !entry->summary.num)
> /* The function was not emitted, or is weak and not chosen in the
> final executable. Silently fail, because there's nothing we
> diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
> index 9b186dd..9f602e9 100644
> --- a/gcc/tree-ssa-pre.c
> +++ b/gcc/tree-ssa-pre.c
> @@ -30,7 +30,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-inline.h"
> #include "tree-flow.h"
> #include "gimple.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
> #include "tree-iterator.h"
> #include "alloc-pool.h"
> #include "obstack.h"
> @@ -177,12 +177,11 @@ typedef struct pre_expr_d
> #define PRE_EXPR_REFERENCE(e) (e)->u.reference
> #define PRE_EXPR_CONSTANT(e) (e)->u.constant
>
> -static int
> -pre_expr_eq (const void *p1, const void *p2)
> -{
> - const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
> - const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
> +/* Compare E1 and E1 for equality. */
>
> +inline int
> +ssa_pre_expr_eq (const struct pre_expr_d *e1, const struct pre_expr_d *e2)
> +{
> if (e1->kind != e2->kind)
> return false;
>
> @@ -203,10 +202,11 @@ pre_expr_eq (const void *p1, const void *p2)
> }
> }
>
> -static hashval_t
> -pre_expr_hash (const void *p1)
> +/* Hash E. */
> +
> +inline hashval_t
> +ssa_pre_expr_hash (const struct pre_expr_d *e)
> {
> - const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
> switch (e->kind)
> {
> case CONSTANT:
> @@ -222,7 +222,6 @@ pre_expr_hash (const void *p1)
> }
> }
>
> -
> /* Next global expression id number. */
> static unsigned int next_expression_id;
>
> @@ -230,7 +229,9 @@ static unsigned int next_expression_id;
> DEF_VEC_P (pre_expr);
> DEF_VEC_ALLOC_P (pre_expr, heap);
> static VEC(pre_expr, heap) *expressions;
> -static htab_t expression_to_id;
> +static hash_table <pre_expr_d, ssa_pre_expr_hash, ssa_pre_expr_eq,
> + typed_null_remove <pre_expr_d> >
> + expression_to_id;
> static VEC(unsigned, heap) *name_to_id;
>
> /* Allocate an expression id for EXPR. */
> @@ -238,7 +239,7 @@ static VEC(unsigned, heap) *name_to_id;
> static inline unsigned int
> alloc_expression_id (pre_expr expr)
> {
> - void **slot;
> + struct pre_expr_d **slot;
> /* Make sure we won't overflow. */
> gcc_assert (next_expression_id + 1 > next_expression_id);
> expr->id = next_expression_id++;
> @@ -257,7 +258,7 @@ alloc_expression_id (pre_expr expr)
> }
> else
> {
> - slot = htab_find_slot (expression_to_id, expr, INSERT);
> + slot = expression_to_id.find_slot (expr, INSERT);
> gcc_assert (!*slot);
> *slot = expr;
> }
> @@ -275,7 +276,7 @@ get_expression_id (const pre_expr expr)
> static inline unsigned int
> lookup_expression_id (const pre_expr expr)
> {
> - void **slot;
> + struct pre_expr_d **slot;
>
> if (expr->kind == NAME)
> {
> @@ -286,7 +287,7 @@ lookup_expression_id (const pre_expr expr)
> }
> else
> {
> - slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
> + slot = expression_to_id.find_slot (expr, NO_INSERT);
> if (!slot)
> return 0;
> return ((pre_expr)*slot)->id;
> @@ -479,11 +480,6 @@ static bitmap need_eh_cleanup;
> /* Set of blocks with statements that have had their AB properties changed. */
> static bitmap need_ab_cleanup;
>
> -/* The phi_translate_table caches phi translations for a given
> - expression and predecessor. */
> -
> -static htab_t phi_translate_table;
> -
> /* A three tuple {e, pred, v} used to cache phi translations in the
> phi_translate_table. */
>
> @@ -506,21 +502,19 @@ typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
>
> /* Return the hash value for a phi translation table entry. */
>
> -static hashval_t
> -expr_pred_trans_hash (const void *p)
> +inline hashval_t
> +ssa_expr_pred_trans_hash (const expr_pred_trans_d *ve)
> {
> - const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
> return ve->hashcode;
> }
>
> /* Return true if two phi translation table entries are the same.
> P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
>
> -static int
> -expr_pred_trans_eq (const void *p1, const void *p2)
> +inline int
> +ssa_expr_pred_trans_eq (const expr_pred_trans_d *ve1,
> + const expr_pred_trans_d *ve2)
> {
> - const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
> - const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
> basic_block b1 = ve1->pred;
> basic_block b2 = ve2->pred;
>
> @@ -528,9 +522,17 @@ expr_pred_trans_eq (const void *p1, const void *p2)
> be equal. */
> if (b1 != b2)
> return false;
> - return pre_expr_eq (ve1->e, ve2->e);
> + return ssa_pre_expr_eq (ve1->e, ve2->e);
> }
>
> +/* The phi_translate_table caches phi translations for a given
> + expression and predecessor. */
> +
> +static hash_table <expr_pred_trans_d, ssa_expr_pred_trans_hash,
> + ssa_expr_pred_trans_eq,
> + typed_free_remove <expr_pred_trans_d> >
> + phi_translate_table;
> +
> /* Search in the phi translation table for the translation of
> expression E in basic block PRED.
> Return the translated value, if found, NULL otherwise. */
> @@ -538,18 +540,18 @@ expr_pred_trans_eq (const void *p1, const void *p2)
> static inline pre_expr
> phi_trans_lookup (pre_expr e, basic_block pred)
> {
> - void **slot;
> + expr_pred_trans_t *slot;
> struct expr_pred_trans_d ept;
>
> ept.e = e;
> ept.pred = pred;
> - ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
> - slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
> + ept.hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e), pred->index);
> + slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode,
> NO_INSERT);
> if (!slot)
> return NULL;
> else
> - return ((expr_pred_trans_t) *slot)->v;
> + return (*slot)->v;
> }
>
>
> @@ -559,18 +561,18 @@ phi_trans_lookup (pre_expr e, basic_block pred)
> static inline void
> phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
> {
> - void **slot;
> + expr_pred_trans_t *slot;
> expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
> new_pair->e = e;
> new_pair->pred = pred;
> new_pair->v = v;
> - new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
> + new_pair->hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
> pred->index);
>
> - slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
> + slot = phi_translate_table.find_slot_with_hash (new_pair,
> new_pair->hashcode, INSERT);
> free (*slot);
> - *slot = (void *) new_pair;
> + *slot = new_pair;
> }
>
>
> @@ -1607,12 +1609,12 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
> if (double_int_fits_in_shwi_p (off))
> newop.off = off.low;
> }
> - VEC_replace (vn_reference_op_s, newoperands, j, &newop);
> + VEC_replace (vn_reference_op_s, newoperands, j, newop);
> /* If it transforms from an SSA_NAME to an address, fold with
> a preceding indirect reference. */
> if (j > 0 && op[0] && TREE_CODE (op[0]) == ADDR_EXPR
> && VEC_index (vn_reference_op_s,
> - newoperands, j - 1)->opcode == MEM_REF)
> + newoperands, j - 1).opcode == MEM_REF)
> vn_reference_fold_indirect (&newoperands, &j);
> }
> if (i != VEC_length (vn_reference_op_s, operands))
> @@ -2596,8 +2598,8 @@ create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
> unsigned int *operand, gimple_seq *stmts,
> gimple domstmt)
> {
> - vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
> - *operand);
> + vn_reference_op_t currop = &VEC_index (vn_reference_op_s, ref->operands,
> + *operand);
> tree genop;
> ++*operand;
> switch (currop->opcode)
> @@ -2674,8 +2676,8 @@ create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
> {
> pre_expr op0expr, op1expr;
> tree genop0 = NULL_TREE, genop1 = NULL_TREE;
> - vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
> - ++*operand);
> + vn_reference_op_t nextop = &VEC_index (vn_reference_op_s, ref->operands,
> + ++*operand);
> tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
> stmts, domstmt);
> if (!baseop)
> @@ -3488,7 +3490,7 @@ do_regular_insertion (basic_block block, basic_block dom)
> do_insertion = true;
> if (first_s == NULL)
> first_s = edoubleprime;
> - else if (!pre_expr_eq (first_s, edoubleprime))
> + else if (!ssa_pre_expr_eq (first_s, edoubleprime))
> all_same = false;
> }
> }
> @@ -4767,7 +4769,7 @@ init_pre (bool do_fre)
>
> next_expression_id = 1;
> expressions = NULL;
> - VEC_safe_push (pre_expr, heap, expressions, NULL);
> + VEC_safe_push (pre_expr, heap, expressions, (pre_expr)NULL);
> value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
> VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
> get_max_value_id() + 1);
> @@ -4790,11 +4792,8 @@ init_pre (bool do_fre)
> calculate_dominance_info (CDI_DOMINATORS);
>
> bitmap_obstack_initialize (&grand_bitmap_obstack);
> - phi_translate_table = htab_create (5110, expr_pred_trans_hash,
> - expr_pred_trans_eq, free);
> - expression_to_id = htab_create (num_ssa_names * 3,
> - pre_expr_hash,
> - pre_expr_eq, NULL);
> + phi_translate_table.create (5110);
> + expression_to_id.create (num_ssa_names * 3);
> bitmap_set_pool = create_alloc_pool ("Bitmap sets",
> sizeof (struct bitmap_set), 30);
> pre_expr_pool = create_alloc_pool ("pre_expr nodes",
> @@ -4826,8 +4825,8 @@ fini_pre (bool do_fre)
> bitmap_obstack_release (&grand_bitmap_obstack);
> free_alloc_pool (bitmap_set_pool);
> free_alloc_pool (pre_expr_pool);
> - htab_delete (phi_translate_table);
> - htab_delete (expression_to_id);
> + phi_translate_table.dispose ();
> + expression_to_id.dispose ();
> VEC_free (unsigned, heap, name_to_id);
>
> free_aux_for_blocks ();
> diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
> index a2d4633..57d9f99 100644
> --- a/gcc/tree-ssa-tail-merge.c
> +++ b/gcc/tree-ssa-tail-merge.c
> @@ -193,7 +193,7 @@ along with GCC; see the file COPYING3. If not see
> #include "bitmap.h"
> #include "tree-ssa-alias.h"
> #include "params.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
> #include "gimple-pretty-print.h"
> #include "tree-ssa-sccvn.h"
> #include "tree-dump.h"
> @@ -368,11 +368,10 @@ same_succ_print (FILE *file, const same_succ e)
>
> /* Prints same_succ VE to VFILE. */
>
> -static int
> -same_succ_print_traverse (void **ve, void *vfile)
> +inline int
> +ssa_same_succ_print_traverse (same_succ *pe, FILE *file)
> {
> - const same_succ e = *((const same_succ *)ve);
> - FILE *file = ((FILE*)vfile);
> + const same_succ e = *pe;
> same_succ_print (file, e);
> return 1;
> }
> @@ -416,10 +415,9 @@ stmt_update_dep_bb (gimple stmt)
>
> /* Calculates hash value for same_succ VE. */
>
> -static hashval_t
> -same_succ_hash (const void *ve)
> +hashval_t
> +ssa_same_succ_hash (const_same_succ e)
> {
> - const_same_succ e = (const_same_succ)ve;
> hashval_t hashval = bitmap_hash (e->succs);
> int flags;
> unsigned int i;
> @@ -515,11 +513,9 @@ inverse_flags (const_same_succ e1, const_same_succ e2)
>
> /* Compares SAME_SUCCs VE1 and VE2. */
>
> -static int
> -same_succ_equal (const void *ve1, const void *ve2)
> +int
> +ssa_same_succ_equal (const_same_succ e1, const_same_succ e2)
> {
> - const_same_succ e1 = (const_same_succ)ve1;
> - const_same_succ e2 = (const_same_succ)ve2;
> unsigned int i, first1, first2;
> gimple_stmt_iterator gsi1, gsi2;
> gimple s1, s2;
> @@ -590,17 +586,15 @@ same_succ_alloc (void)
>
> /* Delete same_succ VE. */
>
> -static void
> -same_succ_delete (void *ve)
> +inline void
> +ssa_same_succ_delete (same_succ e)
> {
> - same_succ e = (same_succ)ve;
> -
> BITMAP_FREE (e->bbs);
> BITMAP_FREE (e->succs);
> BITMAP_FREE (e->inverse);
> VEC_free (int, heap, e->succ_flags);
>
> - XDELETE (ve);
> + XDELETE (e);
> }
>
> /* Reset same_succ SAME. */
> @@ -616,7 +610,9 @@ same_succ_reset (same_succ same)
>
> /* Hash table with all same_succ entries. */
>
> -static htab_t same_succ_htab;
> +static hash_table <struct same_succ_def, ssa_same_succ_hash,
> + ssa_same_succ_equal, ssa_same_succ_delete>
> + same_succ_htab;
>
> /* Array that is used to store the edge flags for a successor. */
>
> @@ -637,7 +633,7 @@ extern void debug_same_succ (void);
> DEBUG_FUNCTION void
> debug_same_succ ( void)
> {
> - htab_traverse (same_succ_htab, same_succ_print_traverse, stderr);
> + same_succ_htab.traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
> }
>
> DEF_VEC_P (same_succ);
> @@ -696,10 +692,9 @@ find_same_succ_bb (basic_block bb, same_succ *same_p)
> EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
> VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
>
> - same->hashval = same_succ_hash (same);
> + same->hashval = ssa_same_succ_hash (same);
>
> - slot = (same_succ *) htab_find_slot_with_hash (same_succ_htab, same,
> - same->hashval, INSERT);
> + slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
> if (*slot == NULL)
> {
> *slot = same;
> @@ -733,7 +728,7 @@ find_same_succ (void)
> same = same_succ_alloc ();
> }
>
> - same_succ_delete (same);
> + ssa_same_succ_delete (same);
> }
>
> /* Initializes worklist administration. */
> @@ -742,9 +737,7 @@ static void
> init_worklist (void)
> {
> alloc_aux_for_blocks (sizeof (struct aux_bb_info));
> - same_succ_htab
> - = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
> - same_succ_delete);
> + same_succ_htab.create (n_basic_blocks);
> same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
> deleted_bbs = BITMAP_ALLOC (NULL);
> deleted_bb_preds = BITMAP_ALLOC (NULL);
> @@ -764,8 +757,7 @@ static void
> delete_worklist (void)
> {
> free_aux_for_blocks ();
> - htab_delete (same_succ_htab);
> - same_succ_htab = NULL;
> + same_succ_htab.dispose ();
> XDELETEVEC (same_succ_edge_flags);
> same_succ_edge_flags = NULL;
> BITMAP_FREE (deleted_bbs);
> @@ -795,7 +787,7 @@ same_succ_flush_bb (basic_block bb)
> same_succ same = BB_SAME_SUCC (bb);
> BB_SAME_SUCC (bb) = NULL;
> if (bitmap_single_bit_set_p (same->bbs))
> - htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
> + same_succ_htab.remove_elt_with_hash (same, same->hashval);
> else
> bitmap_clear_bit (same->bbs, bb->index);
> }
> @@ -868,7 +860,7 @@ update_worklist (void)
> if (same == NULL)
> same = same_succ_alloc ();
> }
> - same_succ_delete (same);
> + ssa_same_succ_delete (same);
> bitmap_clear (deleted_bb_preds);
> }
>
> @@ -1637,7 +1629,7 @@ tail_merge_optimize (unsigned int todo)
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> fprintf (dump_file, "htab collision / search: %f\n",
> - htab_collisions (same_succ_htab));
> + same_succ_htab.collisions ());
>
> if (nr_bbs_removed_total > 0)
> {
> diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
> index a0536db..3ecb303 100644
> --- a/gcc/tree-ssa-threadupdate.c
> +++ b/gcc/tree-ssa-threadupdate.c
> @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-flow.h"
> #include "dumpfile.h"
> #include "cfgloop.h"
> +#include "hash-table.h"
>
> /* Given a block B, update the CFG and SSA graph to reflect redirecting
> one or more in-edges to B to instead reach the destination of an
> @@ -126,11 +127,8 @@ struct redirection_data
> struct el *incoming_edges;
> };
>
> -/* Main data structure to hold information for duplicates of BB. */
> -static htab_t redirection_data;
> -
> /* Data structure of information to pass to hash table traversal routines. */
> -struct local_info
> +struct ssa_local_info_t
> {
> /* The current block we are working on. */
> basic_block bb;
> @@ -220,24 +218,32 @@ create_block_for_threading (basic_block bb, struct redirection_data *rd)
> }
>
> /* Hashing and equality routines for our hash table. */
> -static hashval_t
> -redirection_data_hash (const void *p)
> +inline hashval_t
> +ssa_redirection_data_hash (const struct redirection_data *p)
> {
> - edge e = ((const struct redirection_data *)p)->outgoing_edge;
> + edge e = p->outgoing_edge;
> return e->dest->index;
> }
>
> -static int
> -redirection_data_eq (const void *p1, const void *p2)
> +inline int
> +ssa_redirection_data_eq (const struct redirection_data *p1,
> + const struct redirection_data *p2)
> {
> - edge e1 = ((const struct redirection_data *)p1)->outgoing_edge;
> - edge e2 = ((const struct redirection_data *)p2)->outgoing_edge;
> - edge e3 = ((const struct redirection_data *)p1)->intermediate_edge;
> - edge e4 = ((const struct redirection_data *)p2)->intermediate_edge;
> + edge e1 = p1->outgoing_edge;
> + edge e2 = p2->outgoing_edge;
> + edge e3 = p1->intermediate_edge;
> + edge e4 = p2->intermediate_edge;
>
> return e1 == e2 && e3 == e4;
> }
>
> +/* Main data structure to hold information for duplicates of BB. */
> +
> +static hash_table <struct redirection_data, ssa_redirection_data_hash,
> + ssa_redirection_data_eq,
> + typed_free_remove<struct redirection_data> >
> + redirection_data;
> +
> /* Given an outgoing edge E lookup and return its entry in our hash table.
>
> If INSERT is true, then we insert the entry into the hash table if
> @@ -247,7 +253,7 @@ redirection_data_eq (const void *p1, const void *p2)
> static struct redirection_data *
> lookup_redirection_data (edge e, enum insert_option insert)
> {
> - void **slot;
> + struct redirection_data **slot;
> struct redirection_data *elt;
>
> /* Build a hash table element so we can see if E is already
> @@ -259,7 +265,7 @@ lookup_redirection_data (edge e, enum insert_option insert)
> elt->dup_block = NULL;
> elt->incoming_edges = NULL;
>
> - slot = htab_find_slot (redirection_data, elt, insert);
> + slot = redirection_data.find_slot (elt, insert);
>
> /* This will only happen if INSERT is false and the entry is not
> in the hash table. */
> @@ -273,7 +279,7 @@ lookup_redirection_data (edge e, enum insert_option insert)
> INSERT is true. */
> if (*slot == NULL)
> {
> - *slot = (void *)elt;
> + *slot = elt;
> elt->incoming_edges = XNEW (struct el);
> elt->incoming_edges->e = e;
> elt->incoming_edges->next = NULL;
> @@ -287,7 +293,7 @@ lookup_redirection_data (edge e, enum insert_option insert)
> free (elt);
>
> /* Get the entry stored in the hash table. */
> - elt = (struct redirection_data *) *slot;
> + elt = *slot;
>
> /* If insertion was requested, then we need to add INCOMING_EDGE
> to the list of incoming edges associated with E. */
> @@ -375,9 +381,9 @@ create_edge_and_update_destination_phis (struct redirection_data *rd,
>
> /* Wire up the outgoing edges from the duplicate block and
> update any PHIs as needed. */
> -static void
> -fix_duplicate_block_edges (struct redirection_data *rd,
> - struct local_info *local_info)
> +void
> +ssa_fix_duplicate_block_edges (struct redirection_data *rd,
> + ssa_local_info_t *local_info)
> {
> /* If we were threading through an joiner block, then we want
> to keep its control statement and redirect an outgoing edge.
> @@ -412,11 +418,11 @@ fix_duplicate_block_edges (struct redirection_data *rd,
> }
> /* Hash table traversal callback routine to create duplicate blocks. */
>
> -static int
> -create_duplicates (void **slot, void *data)
> +int
> +ssa_create_duplicates (struct redirection_data **slot,
> + ssa_local_info_t *local_info)
> {
> - struct redirection_data *rd = (struct redirection_data *) *slot;
> - struct local_info *local_info = (struct local_info *)data;
> + struct redirection_data *rd = *slot;
>
> /* Create a template block if we have not done so already. Otherwise
> use the template to create a new block. */
> @@ -435,7 +441,7 @@ create_duplicates (void **slot, void *data)
>
> /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
> block. */
> - fix_duplicate_block_edges (rd, local_info);
> + ssa_fix_duplicate_block_edges (rd, local_info);
> }
>
> /* Keep walking the hash table. */
> @@ -446,11 +452,11 @@ create_duplicates (void **slot, void *data)
> block creation. This hash table traversal callback creates the
> outgoing edge for the template block. */
>
> -static int
> -fixup_template_block (void **slot, void *data)
> +inline int
> +ssa_fixup_template_block (struct redirection_data **slot,
> + ssa_local_info_t *local_info)
> {
> - struct redirection_data *rd = (struct redirection_data *) *slot;
> - struct local_info *local_info = (struct local_info *)data;
> + struct redirection_data *rd = *slot;
>
> /* If this is the template block halt the traversal after updating
> it appropriately.
> @@ -461,7 +467,7 @@ fixup_template_block (void **slot, void *data)
> a new outgoing edge. In both cases we may need to update PHIs. */
> if (rd->dup_block && rd->dup_block == local_info->template_block)
> {
> - fix_duplicate_block_edges (rd, local_info);
> + ssa_fix_duplicate_block_edges (rd, local_info);
> return 0;
> }
>
> @@ -471,11 +477,11 @@ fixup_template_block (void **slot, void *data)
> /* Hash table traversal callback to redirect each incoming edge
> associated with this hash table element to its new destination. */
>
> -static int
> -redirect_edges (void **slot, void *data)
> +int
> +ssa_redirect_edges (struct redirection_data **slot,
> + ssa_local_info_t *local_info)
> {
> - struct redirection_data *rd = (struct redirection_data *) *slot;
> - struct local_info *local_info = (struct local_info *)data;
> + struct redirection_data *rd = *slot;
> struct el *next, *el;
>
> /* Walk over all the incoming edges associated associated with this
> @@ -594,17 +600,14 @@ thread_block (basic_block bb, bool noloop_only)
> redirect to a duplicate of BB. */
> edge e, e2;
> edge_iterator ei;
> - struct local_info local_info;
> + ssa_local_info_t local_info;
> struct loop *loop = bb->loop_father;
>
> /* To avoid scanning a linear array for the element we need we instead
> use a hash table. For normal code there should be no noticeable
> difference. However, if we have a block with a large number of
> incoming and outgoing edges such linear searches can get expensive. */
> - redirection_data = htab_create (EDGE_COUNT (bb->succs),
> - redirection_data_hash,
> - redirection_data_eq,
> - free);
> + redirection_data.create (EDGE_COUNT (bb->succs));
>
> /* If we thread the latch of the loop to its exit, the loop ceases to
> exist. Make sure we do not restrict ourselves in order to preserve
> @@ -678,24 +681,26 @@ thread_block (basic_block bb, bool noloop_only)
> local_info.template_block = NULL;
> local_info.bb = bb;
> local_info.jumps_threaded = false;
> - htab_traverse (redirection_data, create_duplicates, &local_info);
> + redirection_data.traverse <ssa_local_info_t *, ssa_create_duplicates>
> + (&local_info);
>
> /* The template does not have an outgoing edge. Create that outgoing
> edge and update PHI nodes as the edge's target as necessary.
>
> We do this after creating all the duplicates to avoid creating
> unnecessary edges. */
> - htab_traverse (redirection_data, fixup_template_block, &local_info);
> + redirection_data.traverse <ssa_local_info_t *, ssa_fixup_template_block>
> + (&local_info);
>
> /* The hash table traversals above created the duplicate blocks (and the
> statements within the duplicate blocks). This loop creates PHI nodes for
> the duplicated blocks and redirects the incoming edges into BB to reach
> the duplicates of BB. */
> - htab_traverse (redirection_data, redirect_edges, &local_info);
> + redirection_data.traverse <ssa_local_info_t *, ssa_redirect_edges>
> + (&local_info);
>
> /* Done with this block. Clear REDIRECTION_DATA. */
> - htab_delete (redirection_data);
> - redirection_data = NULL;
> + redirection_data.dispose ();
>
> if (noloop_only
> && bb == bb->loop_father->header)
> diff --git a/libcpp/identifiers.c b/libcpp/identifiers.c
> index 8244f0c..d0973f4 100644
> --- a/libcpp/identifiers.c
> +++ b/libcpp/identifiers.c
> @@ -28,12 +28,12 @@ along with this program; see the file COPYING3. If not see
> #include "cpplib.h"
> #include "internal.h"
>
> -static hashnode alloc_node (hash_table *);
> +static hashnode alloc_node (cpp_hash_table *);
>
> /* Return an identifier node for hashtable.c. Used by cpplib except
> when integrated with the C front ends. */
> static hashnode
> -alloc_node (hash_table *table)
> +alloc_node (cpp_hash_table *table)
> {
> cpp_hashnode *node;
>
> @@ -45,7 +45,7 @@ alloc_node (hash_table *table)
> /* Set up the identifier hash table. Use TABLE if non-null, otherwise
> create our own. */
> void
> -_cpp_init_hashtable (cpp_reader *pfile, hash_table *table)
> +_cpp_init_hashtable (cpp_reader *pfile, cpp_hash_table *table)
> {
> struct spec_nodes *s;
>
> diff --git a/libcpp/include/symtab.h b/libcpp/include/symtab.h
> index 4107a6f..30d7645 100644
> --- a/libcpp/include/symtab.h
> +++ b/libcpp/include/symtab.h
> @@ -38,7 +38,7 @@ struct GTY(()) ht_identifier {
> #define HT_LEN(NODE) ((NODE)->len)
> #define HT_STR(NODE) ((NODE)->str)
>
> -typedef struct ht hash_table;
> +typedef struct ht cpp_hash_table;
> typedef struct ht_identifier *hashnode;
>
> enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC};
> @@ -51,7 +51,7 @@ struct ht
>
> hashnode *entries;
> /* Call back, allocate a node. */
> - hashnode (*alloc_node) (hash_table *);
> + hashnode (*alloc_node) (cpp_hash_table *);
> /* Call back, allocate something that hangs off a node like a cpp_macro.
> NULL means use the usual allocator. */
> void * (*alloc_subobject) (size_t);
> @@ -71,14 +71,14 @@ struct ht
> };
>
> /* Initialize the hashtable with 2 ^ order entries. */
> -extern hash_table *ht_create (unsigned int order);
> +extern cpp_hash_table *ht_create (unsigned int order);
>
> /* Frees all memory associated with a hash table. */
> -extern void ht_destroy (hash_table *);
> +extern void ht_destroy (cpp_hash_table *);
>
> -extern hashnode ht_lookup (hash_table *, const unsigned char *,
> +extern hashnode ht_lookup (cpp_hash_table *, const unsigned char *,
> size_t, enum ht_lookup_option);
> -extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *,
> +extern hashnode ht_lookup_with_hash (cpp_hash_table *, const unsigned char *,
> size_t, unsigned int,
> enum ht_lookup_option);
> #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
> @@ -88,17 +88,17 @@ extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *,
> TABLE->PFILE, the node, and a PTR, and the callback sequence stops
> if the callback returns zero. */
> typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *);
> -extern void ht_forall (hash_table *, ht_cb, const void *);
> +extern void ht_forall (cpp_hash_table *, ht_cb, const void *);
>
> /* For all nodes in TABLE, call the callback. If the callback returns
> a nonzero value, the node is removed from the table. */
> -extern void ht_purge (hash_table *, ht_cb, const void *);
> +extern void ht_purge (cpp_hash_table *, ht_cb, const void *);
>
> /* Restore the hash table. */
> -extern void ht_load (hash_table *ht, hashnode *entries,
> +extern void ht_load (cpp_hash_table *ht, hashnode *entries,
> unsigned int nslots, unsigned int nelements, bool own);
>
> /* Dump allocation statistics to stderr. */
> -extern void ht_dump_statistics (hash_table *);
> +extern void ht_dump_statistics (cpp_hash_table *);
>
> #endif /* LIBCPP_SYMTAB_H */
> diff --git a/libcpp/init.c b/libcpp/init.c
> index 7752fea..040ab34 100644
> --- a/libcpp/init.c
> +++ b/libcpp/init.c
> @@ -149,7 +149,7 @@ init_library (void)
>
> /* Initialize a cpp_reader structure. */
> cpp_reader *
> -cpp_create_reader (enum c_lang lang, hash_table *table,
> +cpp_create_reader (enum c_lang lang, cpp_hash_table *table,
> struct line_maps *line_table)
> {
> cpp_reader *pfile;
> diff --git a/libcpp/internal.h b/libcpp/internal.h
> index 37aac82..79dd54f 100644
> --- a/libcpp/internal.h
> +++ b/libcpp/internal.h
> @@ -619,7 +619,7 @@ extern void _cpp_push_token_context (cpp_reader *, cpp_hashnode *,
> extern void _cpp_backup_tokens_direct (cpp_reader *, unsigned int);
>
> /* In identifiers.c */
> -extern void _cpp_init_hashtable (cpp_reader *, hash_table *);
> +extern void _cpp_init_hashtable (cpp_reader *, cpp_hash_table *);
> extern void _cpp_destroy_hashtable (cpp_reader *);
>
> /* In files.c */
> diff --git a/libcpp/symtab.c b/libcpp/symtab.c
> index 48a5338..a3537a0 100644
> --- a/libcpp/symtab.c
> +++ b/libcpp/symtab.c
> @@ -31,7 +31,7 @@ along with this program; see the file COPYING3. If not see
> existing entry with a potential new one. */
>
> static unsigned int calc_hash (const unsigned char *, size_t);
> -static void ht_expand (hash_table *);
> +static void ht_expand (cpp_hash_table *);
> static double approx_sqrt (double);
>
> /* A deleted entry. */
> @@ -53,13 +53,13 @@ calc_hash (const unsigned char *str, size_t len)
>
> /* Initialize an identifier hashtable. */
>
> -hash_table *
> +cpp_hash_table *
> ht_create (unsigned int order)
> {
> unsigned int nslots = 1 << order;
> - hash_table *table;
> + cpp_hash_table *table;
>
> - table = XCNEW (hash_table);
> + table = XCNEW (cpp_hash_table);
>
> /* Strings need no alignment. */
> _obstack_begin (&table->stack, 0, 0,
> @@ -77,7 +77,7 @@ ht_create (unsigned int order)
> /* Frees all memory associated with a hash table. */
>
> void
> -ht_destroy (hash_table *table)
> +ht_destroy (cpp_hash_table *table)
> {
> obstack_free (&table->stack, NULL);
> if (table->entries_owned)
> @@ -91,7 +91,7 @@ ht_destroy (hash_table *table)
> returns NULL. Otherwise insert and returns a new entry. A new
> string is allocated. */
> hashnode
> -ht_lookup (hash_table *table, const unsigned char *str, size_t len,
> +ht_lookup (cpp_hash_table *table, const unsigned char *str, size_t len,
> enum ht_lookup_option insert)
> {
> return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
> @@ -99,7 +99,7 @@ ht_lookup (hash_table *table, const unsigned char *str, size_t len,
> }
>
> hashnode
> -ht_lookup_with_hash (hash_table *table, const unsigned char *str,
> +ht_lookup_with_hash (cpp_hash_table *table, const unsigned char *str,
> size_t len, unsigned int hash,
> enum ht_lookup_option insert)
> {
> @@ -182,7 +182,7 @@ ht_lookup_with_hash (hash_table *table, const unsigned char *str,
> /* Double the size of a hash table, re-hashing existing entries. */
>
> static void
> -ht_expand (hash_table *table)
> +ht_expand (cpp_hash_table *table)
> {
> hashnode *nentries, *p, *limit;
> unsigned int size, sizemask;
> @@ -224,7 +224,7 @@ ht_expand (hash_table *table)
> /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
> the node, and V. */
> void
> -ht_forall (hash_table *table, ht_cb cb, const void *v)
> +ht_forall (cpp_hash_table *table, ht_cb cb, const void *v)
> {
> hashnode *p, *limit;
>
> @@ -242,7 +242,7 @@ ht_forall (hash_table *table, ht_cb cb, const void *v)
> /* Like ht_forall, but a nonzero return from the callback means that
> the entry should be removed from the table. */
> void
> -ht_purge (hash_table *table, ht_cb cb, const void *v)
> +ht_purge (cpp_hash_table *table, ht_cb cb, const void *v)
> {
> hashnode *p, *limit;
>
> @@ -259,7 +259,7 @@ ht_purge (hash_table *table, ht_cb cb, const void *v)
>
> /* Restore the hash table. */
> void
> -ht_load (hash_table *ht, hashnode *entries,
> +ht_load (cpp_hash_table *ht, hashnode *entries,
> unsigned int nslots, unsigned int nelements,
> bool own)
> {
> @@ -274,7 +274,7 @@ ht_load (hash_table *ht, hashnode *entries,
> /* Dump allocation statistics to stderr. */
>
> void
> -ht_dump_statistics (hash_table *table)
> +ht_dump_statistics (cpp_hash_table *table)
> {
> size_t nelts, nids, overhead, headers;
> size_t total_bytes, longest, deleted = 0;
> diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
> index 83ed653..4332398 100644
> --- a/gcc/tree-ssa-ccp.c
> +++ b/gcc/tree-ssa-ccp.c
> @@ -130,6 +130,7 @@ along with GCC; see the file COPYING3. If not see
> #include "dbgcnt.h"
> #include "gimple-fold.h"
> #include "params.h"
> +#include "hash-table.h"
>
>
> /* Possible lattice values. */
> @@ -1688,11 +1689,17 @@ evaluate_stmt (gimple stmt)
> return val;
> }
>
> +typedef hash_table <gimple_statement_d, typed_pointer_hash<gimple_statement_d>,
> + typed_pointer_equal<gimple_statement_d>,
> + typed_null_remove<gimple_statement_d> >
> + gimple_htab;
> +
> /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
> each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
>
> static void
> -insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t *visited)
> +insert_clobber_before_stack_restore (tree saved_val, tree var,
> + gimple_htab *visited)
> {
> gimple stmt, clobber_stmt;
> tree clobber;
> @@ -1712,10 +1719,10 @@ insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t *visited)
> }
> else if (gimple_code (stmt) == GIMPLE_PHI)
> {
> - if (*visited == NULL)
> - *visited = htab_create (10, htab_hash_pointer, htab_eq_pointer, NULL);
> + if (!visited->is_created ())
> + visited->create (10);
>
> - slot = (gimple *)htab_find_slot (*visited, stmt, INSERT);
> + slot = visited->find_slot (stmt, INSERT);
> if (*slot != NULL)
> continue;
>
> @@ -1758,7 +1765,7 @@ insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
> {
> gimple stmt;
> tree saved_val;
> - htab_t visited = NULL;
> + gimple_htab visited;
>
> for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
> {
> @@ -1775,8 +1782,8 @@ insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
> break;
> }
>
> - if (visited != NULL)
> - htab_delete (visited);
> + if (visited.is_created ())
> + visited.dispose ();
> }
>
> /* Detects a __builtin_alloca_with_align with constant size argument. Declares
> diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
> index b8b1a51..399e7fc 100644
> --- a/gcc/tree-ssa-coalesce.c
> +++ b/gcc/tree-ssa-coalesce.c
> @@ -29,7 +29,7 @@ along with GCC; see the file COPYING3. If not see
> #include "bitmap.h"
> #include "dumpfile.h"
> #include "tree-flow.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
> #include "tree-ssa-live.h"
> #include "diagnostic-core.h"
>
> @@ -1258,22 +1258,19 @@ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
> }
> }
>
> -/* Returns a hash code for P. */
> +/* Returns a hash code for N. */
>
> -static hashval_t
> -hash_ssa_name_by_var (const void *p)
> +inline hashval_t
> +hash_ssa_name_by_var (const_tree n)
> {
> - const_tree n = (const_tree) p;
> return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
> }
>
> -/* Returns nonzero if P1 and P2 are equal. */
> +/* Returns nonzero if N1 and N2 are equal. */
>
> -static int
> -eq_ssa_name_by_var (const void *p1, const void *p2)
> +inline int
> +eq_ssa_name_by_var (const_tree n1, const_tree n2)
> {
> - const_tree n1 = (const_tree) p1;
> - const_tree n2 = (const_tree) p2;
> return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
> }
>
> @@ -1289,7 +1286,9 @@ coalesce_ssa_name (void)
> bitmap used_in_copies = BITMAP_ALLOC (NULL);
> var_map map;
> unsigned int i;
> - static htab_t ssa_name_hash;
> + static hash_table <tree_node, hash_ssa_name_by_var, eq_ssa_name_by_var,
> + typed_null_remove<tree_node> >
> + ssa_name_hash;
>
> cl = create_coalesce_list ();
> map = create_outofssa_var_map (cl, used_in_copies);
> @@ -1298,8 +1297,7 @@ coalesce_ssa_name (void)
> so debug info remains undisturbed. */
> if (!optimize)
> {
> - ssa_name_hash = htab_create (10, hash_ssa_name_by_var,
> - eq_ssa_name_by_var, NULL);
> + ssa_name_hash.create (10);
> for (i = 1; i < num_ssa_names; i++)
> {
> tree a = ssa_name (i);
> @@ -1309,7 +1307,7 @@ coalesce_ssa_name (void)
> && !DECL_IGNORED_P (SSA_NAME_VAR (a))
> && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)))
> {
> - tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
> + tree *slot = ssa_name_hash.find_slot (a, INSERT);
>
> if (!*slot)
> *slot = a;
> @@ -1322,7 +1320,7 @@ coalesce_ssa_name (void)
> }
> }
> }
> - htab_delete (ssa_name_hash);
> + ssa_name_hash.dispose ();
> }
> if (dump_file && (dump_flags & TDF_DETAILS))
> dump_var_map (dump_file, map);
> diff --git a/gcc/hash-table.c
> ===================================================================
> --- gcc/hash-table.c (revision 0)
> +++ gcc/hash-table.c (revision 0)
> @@ -0,0 +1,190 @@
> +/* A type-safe hash table template.
> + Copyright (C) 2012
> + 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. */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "hash-table.h"
> +
> +
> +/* 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. */
> +
> +#if 0
> +unsigned int
> +ceil_log2 (unsigned int x)
> +{
> + int i;
> + for (i = 31; i >= 0 ; --i)
> + if (x > (1u << i))
> + return i+1;
> + abort ();
> +}
> +
> +unsigned int
> +choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
> +{
> + unsigned long long mhigh;
> + double nx;
> + int lgup, post_shift;
> + int pow, pow2;
> + int n = 32, precision = 32;
> +
> + lgup = ceil_log2 (d);
> + pow = n + lgup;
> + pow2 = n + lgup - precision;
> +
> + nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
> + mhigh = nx / d;
> +
> + *shiftp = lgup - 1;
> + *mlp = mhigh;
> + return mhigh >> 32;
> +}
> +#endif
> +
> +struct prime_ent const prime_tab[] = {
> + { 7, 0x24924925, 0x9999999b, 2 },
> + { 13, 0x3b13b13c, 0x745d1747, 3 },
> + { 31, 0x08421085, 0x1a7b9612, 4 },
> + { 61, 0x0c9714fc, 0x15b1e5f8, 5 },
> + { 127, 0x02040811, 0x0624dd30, 6 },
> + { 251, 0x05197f7e, 0x073260a5, 7 },
> + { 509, 0x01824366, 0x02864fc8, 8 },
> + { 1021, 0x00c0906d, 0x014191f7, 9 },
> + { 2039, 0x0121456f, 0x0161e69e, 10 },
> + { 4093, 0x00300902, 0x00501908, 11 },
> + { 8191, 0x00080041, 0x00180241, 12 },
> + { 16381, 0x000c0091, 0x00140191, 13 },
> + { 32749, 0x002605a5, 0x002a06e6, 14 },
> + { 65521, 0x000f00e2, 0x00110122, 15 },
> + { 131071, 0x00008001, 0x00018003, 16 },
> + { 262139, 0x00014002, 0x0001c004, 17 },
> + { 524287, 0x00002001, 0x00006001, 18 },
> + { 1048573, 0x00003001, 0x00005001, 19 },
> + { 2097143, 0x00004801, 0x00005801, 20 },
> + { 4194301, 0x00000c01, 0x00001401, 21 },
> + { 8388593, 0x00001e01, 0x00002201, 22 },
> + { 16777213, 0x00000301, 0x00000501, 23 },
> + { 33554393, 0x00001381, 0x00001481, 24 },
> + { 67108859, 0x00000141, 0x000001c1, 25 },
> + { 134217689, 0x000004e1, 0x00000521, 26 },
> + { 268435399, 0x00000391, 0x000003b1, 27 },
> + { 536870909, 0x00000019, 0x00000029, 28 },
> + { 1073741789, 0x0000008d, 0x00000095, 29 },
> + { 2147483647, 0x00000003, 0x00000007, 30 },
> + /* Avoid "decimal constant so large it is unsigned" for 4294967291. */
> + { 0xfffffffb, 0x00000006, 0x00000008, 31 }
> +};
> +
> +/* The following function returns an index into the above table of the
> + nearest prime number which is greater than N, and near a power of two. */
> +
> +unsigned int
> +hash_table_higher_prime_index (unsigned long n)
> +{
> + unsigned int low = 0;
> + unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
> +
> + while (low != high)
> + {
> + unsigned int mid = low + (high - low) / 2;
> + if (n > prime_tab[mid].prime)
> + low = mid + 1;
> + else
> + high = mid;
> + }
> +
> + /* If we've run out of primes, abort. */
> + if (n > prime_tab[low].prime)
> + {
> + fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
> + abort ();
> + }
> +
> + return low;
> +}
> +
> +/* 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. */
> +
> +#ifdef UNSIGNED_64BIT_TYPE
> +static inline hashval_t
> +mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
> +{
> + __extension__ typedef UNSIGNED_64BIT_TYPE ull;
> + hashval_t t1, t2, t3, t4, q, r;
> +
> + t1 = ((ull)x * inv) >> 32;
> + t2 = x - t1;
> + t3 = t2 >> 1;
> + t4 = t1 + t3;
> + q = t4 >> shift;
> + r = x - (q * y);
> +
> + return r;
> +}
> +#endif
> +
> +/* Compute the primary table index for HASH given current prime index. */
> +
> +hashval_t
> +hash_table_mod1 (hashval_t hash, unsigned int index)
> +{
> + const struct prime_ent *p = &prime_tab[index];
> +#ifdef UNSIGNED_64BIT_TYPE
> + if (sizeof (hashval_t) * CHAR_BIT <= 32)
> + return mul_mod (hash, p->prime, p->inv, p->shift);
> +#endif
> + return hash % p->prime;
> +}
> +
> +
> +/* Compute the secondary table index for HASH given current prime index. */
> +
> +hashval_t
> +hash_table_mod2 (hashval_t hash, unsigned int index)
> +{
> + const struct prime_ent *p = &prime_tab[index];
> +#ifdef UNSIGNED_64BIT_TYPE
> + if (sizeof (hashval_t) * CHAR_BIT <= 32)
> + return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
> +#endif
> + return 1 + hash % (p->prime - 2);
> +}
> diff --git a/gcc/hash-table.h
> ===================================================================
> --- gcc/hash-table.h (revision 0)
> +++ gcc/hash-table.h (revision 0)
> @@ -0,0 +1,783 @@
> +/* A type-safe hash table template.
> + Copyright (C) 2012
> + 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. */
> +
> +
> +#ifndef TYPED_HASHTAB_H
> +#define TYPED_HASHTAB_H
> +
> +#include "hashtab.h"
> +
> +
> +/* The ordinary memory allocator. */
> +/* FIXME (crowl): This allocator may be extracted for wider sharing later. */
> +
> +template <typename Type>
> +struct xcallocator
> +{
> + static Type *control_alloc (size_t count);
> + static Type *data_alloc (size_t count);
> + static void control_free (Type *memory);
> + static void data_free (Type *memory);
> +};
> +
> +
> +/* Allocate memory for COUNT control blocks. */
> +
> +template <typename Type>
> +inline Type *
> +xcallocator <Type>::control_alloc (size_t count)
> +{
> + return static_cast <Type *> (xcalloc (count, sizeof (Type)));
> +}
> +
> +
> +/* Allocate memory for COUNT data blocks. */
> +
> +template <typename Type>
> +inline Type *
> +xcallocator <Type>::data_alloc (size_t count)
> +{
> + return static_cast <Type *> (xcalloc (count, sizeof (Type)));
> +}
> +
> +
> +/* Free memory for control blocks. */
> +
> +template <typename Type>
> +inline void
> +xcallocator <Type>::control_free (Type *memory)
> +{
> + return ::free (memory);
> +}
> +
> +
> +/* Free memory for data blocks. */
> +
> +template <typename Type>
> +inline void
> +xcallocator <Type>::data_free (Type *memory)
> +{
> + return ::free (memory);
> +}
> +
> +
> +/* A common function for hashing a CANDIDATE typed pointer. */
> +
> +template <typename Element>
> +inline hashval_t
> +typed_pointer_hash (const Element *candidate)
> +{
> + /* This is a really poor hash function, but it is what the current code uses,
> + so I am reusing it to avoid an additional axis in testing. */
> + return (hashval_t) ((intptr_t)candidate >> 3);
> +}
> +
> +
> +/* A common function for comparing an EXISTING and CANDIDATE typed pointers
> + for equality. */
> +
> +template <typename Element>
> +inline int
> +typed_pointer_equal (const Element *existing, const Element * candidate)
> +{
> + return existing == candidate;
> +}
> +
> +
> +/* A common function for doing nothing on removing a RETIRED slot. */
> +
> +template <typename Element>
> +inline void
> +typed_null_remove (Element *retired ATTRIBUTE_UNUSED)
> +{
> +}
> +
> +
> +/* A common function for using free on removing a RETIRED slot. */
> +
> +template <typename Element>
> +inline void
> +typed_free_remove (Element *retired)
> +{
> + free (retired);
> +}
> +
> +
> +/* Table of primes and their inversion information. */
> +
> +struct prime_ent
> +{
> + hashval_t prime;
> + hashval_t inv;
> + hashval_t inv_m2; /* inverse of prime-2 */
> + hashval_t shift;
> +};
> +
> +extern struct prime_ent const prime_tab[];
> +
> +
> +/* Functions for computing hash table indexes. */
> +
> +extern unsigned int hash_table_higher_prime_index (unsigned long n);
> +extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
> +extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
> +
> +
> +/* Internal implementation type. */
> +
> +template <typename Element>
> +struct hash_table_control
> +{
> + /* Table itself. */
> + Element **entries;
> +
> + /* Current size (in entries) of the hash table. */
> + size_t size;
> +
> + /* Current number of elements including also deleted elements. */
> + size_t n_elements;
> +
> + /* Current number of deleted elements in the table. */
> + size_t n_deleted;
> +
> + /* The following member is used for debugging. Its value is number
> + of all calls of `htab_find_slot' for the hash table. */
> + unsigned int searches;
> +
> + /* The following member is used for debugging. Its value is number
> + of collisions fixed for time of work with the hash table. */
> + unsigned int collisions;
> +
> + /* Current size (in entries) of the hash table, as an index into the
> + table of primes. */
> + unsigned int size_prime_index;
> +};
> +
> +
> +/* User-facing hash table type.
> +
> + The table stores elements of type Element.
> +
> + It hashes elements with the Hash function.
> + The table currently works with relatively weak hash functions.
> + Use typed_pointer_hash <Element> when hashing pointers instead of objects.
> +
> + It compares elements with the Equal function.
> + Two elements with the same hash may not be equal.
> + Use typed_pointer_equal <Element> when hashing pointers instead of objects.
> +
> + It removes elements with the Remove function.
> + This feature is useful for freeing memory.
> + Use typed_null_remove <Element> when not freeing objects.
> + Use typed_free_remove <Element> when doing a simple object free.
> +
> + Use the Allocator template to allocate and free memory.
> + The default is xcallocator.
> +
> +*/
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator = xcallocator>
> +class hash_table
> +{
> +
> +private:
> +
> + hash_table_control <Element> *htab;
> +
> + Element **find_empty_slot_for_expand (hashval_t hash);
> + void expand ();
> +
> +public:
> +
> + hash_table ();
> + void create (size_t initial_slots);
> + bool is_created ();
> + void dispose ();
> + Element *find (Element *comparable);
> + Element *find_with_hash (Element *comparable, hashval_t hash);
> + Element **find_slot (Element *comparable, enum insert_option insert);
> + Element **find_slot_with_hash (Element *comparable, hashval_t hash,
> + enum insert_option insert);
> + void empty ();
> + void clear_slot (Element **slot);
> + void remove_elt (Element *comparable);
> + void remove_elt_with_hash (Element *comparable, hashval_t hash);
> + size_t size();
> + size_t elements();
> + double collisions();
> +
> + template <typename Argument,
> + int (*Callback) (Element **slot, Argument argument)>
> + void traverse_noresize (Argument argument);
> +
> + template <typename Argument,
> + int (*Callback) (Element **slot, Argument argument)>
> + void traverse (Argument argument);
> +};
> +
> +
> +/* Construct the hash table. The only useful operation next is create. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline
> +hash_table <Element, Hash, Equal, Remove, Allocator>::hash_table ()
> +: htab (NULL)
> +{
> +}
> +
> +
> +/* See if the table has been created, as opposed to constructed. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline bool
> +hash_table <Element, Hash, Equal, Remove, Allocator>::is_created ()
> +{
> + return htab != NULL;
> +}
> +
> +
> +/* Like find_with_hash, but compute the hash value from the element. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline Element *
> +hash_table <Element, Hash, Equal, Remove, Allocator>::find (Element *comparable)
> +{
> + return find_with_hash (comparable, Hash (comparable));
> +}
> +
> +
> +/* Like find_slot_with_hash, but compute the hash value from the element. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline Element **
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::find_slot (Element *comparable, enum insert_option insert)
> +{
> + return find_slot_with_hash (comparable, Hash (comparable), insert);
> +}
> +
> +
> +/* Like remove_elt_with_hash, but compute the hash value from the element. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline void
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::remove_elt (Element *comparable)
> +{
> + remove_elt_with_hash (comparable, Hash (comparable));
> +}
> +
> +
> +/* Return the current size of this hash table. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline size_t
> +hash_table <Element, Hash, Equal, Remove, Allocator>::size()
> +{
> + return htab->size;
> +}
> +
> +
> +/* Return the current number of elements in this hash table. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline size_t
> +hash_table <Element, Hash, Equal, Remove, Allocator>::elements()
> +{
> + return htab->n_elements - htab->n_deleted;
> +}
> +
> +
> + /* Return the fraction of fixed collisions during all work with given
> + hash table. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +inline double
> +hash_table <Element, Hash, Equal, Remove, Allocator>::collisions()
> +{
> + if (htab->searches == 0)
> + return 0.0;
> +
> + return static_cast <double> (htab->collisions) / htab->searches;
> +}
> +
> +
> +/* Create a hash table with at least the given number of INITIAL_SLOTS. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>::create (size_t size)
> +{
> + unsigned int size_prime_index;
> +
> + size_prime_index = hash_table_higher_prime_index (size);
> + size = prime_tab[size_prime_index].prime;
> +
> + htab = Allocator <hash_table_control <Element> > ::control_alloc (1);
> + gcc_assert (htab != NULL);
> + htab->entries = Allocator <Element*> ::data_alloc (size);
> + gcc_assert (htab->entries != NULL);
> + htab->size = size;
> + htab->size_prime_index = size_prime_index;
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>::dispose ()
> +{
> + size_t size = htab->size;
> + Element **entries = htab->entries;
> +
> + for (int i = size - 1; i >= 0; i--)
> + if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
> + Remove (entries[i]);
> +
> + Allocator <Element *> ::data_free (entries);
> + Allocator <hash_table_control <Element> > ::control_free (htab);
> + htab = NULL;
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +Element **
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::find_empty_slot_for_expand (hashval_t hash)
> +{
> + hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
> + size_t size = htab->size;
> + Element **slot = htab->entries + index;
> + hashval_t hash2;
> +
> + if (*slot == HTAB_EMPTY_ENTRY)
> + return slot;
> + else if (*slot == HTAB_DELETED_ENTRY)
> + abort ();
> +
> + hash2 = hash_table_mod2 (hash, htab->size_prime_index);
> + for (;;)
> + {
> + index += hash2;
> + if (index >= size)
> + index -= size;
> +
> + slot = htab->entries + index;
> + if (*slot == HTAB_EMPTY_ENTRY)
> + return slot;
> + else if (*slot == HTAB_DELETED_ENTRY)
> + abort ();
> + }
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>::expand ()
> +{
> + Element **oentries;
> + Element **olimit;
> + Element **p;
> + Element **nentries;
> + size_t nsize, osize, elts;
> + unsigned int oindex, nindex;
> +
> + oentries = htab->entries;
> + oindex = htab->size_prime_index;
> + osize = htab->size;
> + olimit = oentries + osize;
> + elts = elements ();
> +
> + /* Resize only when table after removal of unused elements is either
> + too full or too empty. */
> + if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
> + {
> + nindex = hash_table_higher_prime_index (elts * 2);
> + nsize = prime_tab[nindex].prime;
> + }
> + else
> + {
> + nindex = oindex;
> + nsize = osize;
> + }
> +
> + nentries = Allocator <Element *> ::data_alloc (nsize);
> + gcc_assert (nentries != NULL);
> + htab->entries = nentries;
> + htab->size = nsize;
> + htab->size_prime_index = nindex;
> + htab->n_elements -= htab->n_deleted;
> + htab->n_deleted = 0;
> +
> + p = oentries;
> + do
> + {
> + Element *x = *p;
> +
> + if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
> + {
> + Element **q = find_empty_slot_for_expand (Hash (x));
> +
> + *q = x;
> + }
> +
> + p++;
> + }
> + while (p < olimit);
> +
> + Allocator <Element *> ::data_free (oentries);
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +Element *
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::find_with_hash (Element *comparable, hashval_t hash)
> +{
> + hashval_t index, hash2;
> + size_t size;
> + Element *entry;
> +
> + htab->searches++;
> + size = htab->size;
> + index = hash_table_mod1 (hash, htab->size_prime_index);
> +
> + entry = htab->entries[index];
> + if (entry == HTAB_EMPTY_ENTRY
> + || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
> + return entry;
> +
> + hash2 = hash_table_mod2 (hash, htab->size_prime_index);
> + for (;;)
> + {
> + htab->collisions++;
> + index += hash2;
> + if (index >= size)
> + index -= size;
> +
> + entry = htab->entries[index];
> + if (entry == HTAB_EMPTY_ENTRY
> + || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
> + return entry;
> + }
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +Element **
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::find_slot_with_hash (Element *comparable, hashval_t hash,
> + enum insert_option insert)
> +{
> + Element **first_deleted_slot;
> + hashval_t index, hash2;
> + size_t size;
> + Element *entry;
> +
> + size = htab->size;
> + if (insert == INSERT && size * 3 <= htab->n_elements * 4)
> + {
> + expand ();
> + size = htab->size;
> + }
> +
> + index = hash_table_mod1 (hash, htab->size_prime_index);
> +
> + htab->searches++;
> + first_deleted_slot = NULL;
> +
> + entry = htab->entries[index];
> + if (entry == HTAB_EMPTY_ENTRY)
> + goto empty_entry;
> + else if (entry == HTAB_DELETED_ENTRY)
> + first_deleted_slot = &htab->entries[index];
> + else if (Equal (entry, comparable))
> + return &htab->entries[index];
> +
> + hash2 = hash_table_mod2 (hash, htab->size_prime_index);
> + for (;;)
> + {
> + htab->collisions++;
> + index += hash2;
> + if (index >= size)
> + index -= size;
> +
> + entry = htab->entries[index];
> + if (entry == HTAB_EMPTY_ENTRY)
> + goto empty_entry;
> + else if (entry == HTAB_DELETED_ENTRY)
> + {
> + if (!first_deleted_slot)
> + first_deleted_slot = &htab->entries[index];
> + }
> + else if (Equal (entry, comparable))
> + return &htab->entries[index];
> + }
> +
> + empty_entry:
> + if (insert == NO_INSERT)
> + return NULL;
> +
> + if (first_deleted_slot)
> + {
> + htab->n_deleted--;
> + *first_deleted_slot = static_cast <Element *> (HTAB_EMPTY_ENTRY);
> + return first_deleted_slot;
> + }
> +
> + htab->n_elements++;
> + return &htab->entries[index];
> +}
> +
> +
> +/* This function clears all entries in the given hash table. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>::empty ()
> +{
> + size_t size = htab_size (htab);
> + Element **entries = htab->entries;
> + int i;
> +
> + for (i = size - 1; i >= 0; i--)
> + if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
> + Remove (entries[i]);
> +
> + /* Instead of clearing megabyte, downsize the table. */
> + if (size > 1024*1024 / sizeof (PTR))
> + {
> + int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
> + int nsize = prime_tab[nindex].prime;
> +
> + Allocator <Element *> ::data_free (htab->entries);
> + htab->entries = Allocator <Element *> ::data_alloc (nsize);
> + htab->size = nsize;
> + htab->size_prime_index = nindex;
> + }
> + else
> + memset (entries, 0, size * sizeof (Element *));
> + htab->n_deleted = 0;
> + htab->n_elements = 0;
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::clear_slot (Element **slot)
> +{
> + if (slot < htab->entries || slot >= htab->entries + htab->size
> + || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
> + abort ();
> +
> + Remove (*slot);
> +
> + *slot = HTAB_DELETED_ENTRY;
> + htab->n_deleted++;
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::remove_elt_with_hash (Element *comparable, hashval_t hash)
> +{
> + Element **slot;
> +
> + slot = find_slot_with_hash (comparable, hash, NO_INSERT);
> + if (*slot == HTAB_EMPTY_ENTRY)
> + return;
> +
> + Remove (*slot);
> +
> + *slot = static_cast <Element *> (HTAB_DELETED_ENTRY);
> + htab->n_deleted++;
> +}
> +
> +
> +/* 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. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +template <typename Argument,
> + int (*Callback) (Element **slot, Argument argument)>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::traverse_noresize (Argument argument)
> +{
> + Element **slot;
> + Element **limit;
> +
> + slot = htab->entries;
> + limit = slot + htab->size;
> +
> + do
> + {
> + Element *x = *slot;
> +
> + if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
> + if (! Callback (slot, argument))
> + break;
> + }
> + while (++slot < limit);
> +}
> +
> +
> +/* Like traverse_noresize, but does resize the table when it is too empty
> + to improve effectivity of subsequent calls. */
> +
> +template <typename Element,
> + hashval_t (*Hash) (const Element *candidate),
> + int (*Equal) (const Element *existing, const Element * candidate),
> + void (*Remove) (Element *retired),
> + template <typename Type> class Allocator>
> +template <typename Argument,
> + int (*Callback) (Element **slot, Argument argument)>
> +void
> +hash_table <Element, Hash, Equal, Remove, Allocator>
> +::traverse (Argument argument)
> +{
> + size_t size = htab->size;
> + if (elements () * 8 < size && size > 32)
> + expand ();
> +
> + traverse_noresize <Argument, Callback> (argument);
> +}
> +
> +#endif /* TYPED_HASHTAB_H */
>
>
--
Richard Guenther <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend
More information about the Gcc-patches
mailing list