Patchwork Convert more non-GTY htab_t to hash_table.

login
register
mail settings
Submitter Lawrence Crowl
Date Oct. 3, 2012, 10:46 p.m.
Message ID <CAGqM8fZVfjCXY1iqA68jmVmo26ALV5js7-u-JHzhYYZAMh4Tsw@mail.gmail.com>
Download mbox | patch
Permalink /patch/188952/
State New
Headers show

Comments

Lawrence Crowl - Oct. 3, 2012, 10:46 p.m.
Sorry, one more time with the right file contents.

On 10/2/12, Richard Guenther <rguenther@suse.de> wrote:
> You are changing a hashtable used by fold checking, did you test
> with fold checking enabled?

One small thinko fixed.  Patch passes tests.

> The cfg.c, dse.c and hash-table.h parts are ok for trunk, I'll
> leave the rest to respective maintainers of the pieces of the
> compiler.

+cc
java: tromey@redhat.com
c: rth@redhat.com
objc: mikestump@comcast.net
cp: jason@redhat.com

    $(DF_H) alloc-pool.h $(TREE_PASS_H) $(TARGET_H) \
@@ -3058,7 +3058,7 @@ auto-inc-dec.o : auto-inc-dec.c $(CONFIG
    $(REGS_H) $(FLAGS_H) $(FUNCTION_H) $(EXCEPT_H)
$(DIAGNOSTIC_CORE_H) $(RECOG_H) \
    $(EXPR_H) $(TREE_PASS_H) $(DF_H) $(DBGCNT_H) $(TARGET_H)
 cfg.o : cfg.c $(CONFIG_H) $(SYSTEM_H) coretypes.h dumpfile.h
$(DIAGNOSTIC_CORE_H) \
-   $(GGC_H) $(OBSTACK_H) alloc-pool.h $(HASHTAB_H) $(CFGLOOP_H) $(TREE_H) \
+   $(GGC_H) $(OBSTACK_H) alloc-pool.h $(HASH_TABLE_H) $(CFGLOOP_H) $(TREE_H) \
    $(BASIC_BLOCK_H)
 cfghooks.o: cfghooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(TREE_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) $(TIMEVAR_H) toplev.h
$(DIAGNOSTIC_CORE_H) $(CFGLOOP_H)
Lawrence Crowl - Oct. 5, 2012, 9:03 p.m.
Could you please review the patch at
http://www.mail-archive.com/gcc-patches@gcc.gnu.org/msg40961.html?

On 10/3/12, Lawrence Crowl <crowl@googlers.com> wrote:
> Sorry, one more time with the right file contents.
>
> On 10/2/12, Richard Guenther <rguenther@suse.de> wrote:
>> You are changing a hashtable used by fold checking, did you test
>> with fold checking enabled?
>
> One small thinko fixed.  Patch passes tests.
>
>> The cfg.c, dse.c and hash-table.h parts are ok for trunk, I'll
>> leave the rest to respective maintainers of the pieces of the
>> compiler.
>
> +cc
> java: tromey@redhat.com
> c: rth@redhat.com
> objc: mikestump@comcast.net
> cp: jason@redhat.com
>
> ====
>
> Change more non-GTY hash tables to use the new type-safe template hash
> table.
> Constify member function parameters that can be const.
> Correct a couple of expressions in formerly uninstantiated templates.
>
> The new code is 0.362% faster in bootstrap, with a 99.5% confidence of
> being faster.
>
> Tested on x86-64.
>
> Okay for trunk?
>
>
> Index: gcc/java/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
> 	* Make-lang.in (JAVA_OBJS): Add dependence on hash-table.o.
> 	(JCFDUMP_OBJS): Add dependence on hash-table.o.
> 	(jcf-io.o): Add dependence on hash-table.h.
> 	* jcf-io.c (memoized_class_lookups): Change to use type-safe hash table.
>
> Index: gcc/c/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
> 	* Make-lang.in (c-decl.o): Add dependence on hash-table.h.
> 	* c-decl.c (detect_field_duplicates_hash): Change to new type-safe
> 	hash table.
>
> Index: gcc/objc/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
> 	* Make-lang.in (OBJC_OBJS): Add dependence on hash-table.o.
> 	(objc-act.o): Add dependence on hash-table.h.
> 	* objc-act.c (objc_detect_field_duplicates): Change to new type-safe
> 	hash table.
>
> Index: gcc/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
> 	* Makefile.in (fold-const.o): Add depencence on hash-table.h.
> 	(dse.o): Likewise.
> 	(cfg.o): Likewise.
> 	* fold-const.c (fold_checksum_tree): Change to new type-safe hash table.
> 	* (print_fold_checksum): Likewise.
> 	* cfg.c (var bb_original): Likewise.
> 	* (var bb_copy): Likewise.
> 	* (var loop_copy): Likewise.
> 	* hash-table.h (template hash_table): Constify parameters for find...
> 	and remove_elt... member functions.
>         (hash_table::empty) Correct size expression.
>         (hash_table::clear_slot) Correct deleted entry assignment.
> 	* dse.c (var rtx_group_table): Change to new type-safe hash table.
>
> Index: gcc/cp/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
> 	* Make-lang.in (class.o): Add dependence on hash-table.h.
> 	(tree.o): Likewise.
> 	(semantics.o): Likewise.
> 	* class.c (fixed_type_or_null): Change to new type-safe hash table.
> 	* tree.c (verify_stmt_tree): Likewise.
> 	(verify_stmt_tree_r): Likewise.
> 	* semantics.c (struct nrv_data): Likewise.
>
>
> Index: gcc/java/Make-lang.in
> ===================================================================
> --- gcc/java/Make-lang.in	(revision 191941)
> +++ gcc/java/Make-lang.in	(working copy)
> @@ -83,10 +83,10 @@ JAVA_OBJS = java/class.o java/decl.o jav
>    java/zextract.o java/jcf-io.o java/win32-host.o java/jcf-parse.o
> java/mangle.o \
>    java/mangle_name.o java/builtins.o java/resource.o \
>    java/jcf-depend.o \
> -  java/jcf-path.o java/boehm.o java/java-gimplify.o
> +  java/jcf-path.o java/boehm.o java/java-gimplify.o hash-table.o
>
>  JCFDUMP_OBJS = java/jcf-dump.o java/jcf-io.o java/jcf-depend.o
> java/jcf-path.o \
> -		java/win32-host.o java/zextract.o ggc-none.o
> +		java/win32-host.o java/zextract.o ggc-none.o hash-table.o
>
>  JVGENMAIN_OBJS = java/jvgenmain.o java/mangle_name.o
>
> @@ -326,7 +326,7 @@ java/java-gimplify.o: java/java-gimplify
>  # jcf-io.o needs $(ZLIBINC) added to cflags.
>  CFLAGS-java/jcf-io.o += $(ZLIBINC)
>  java/jcf-io.o: java/jcf-io.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
> -  $(JAVA_TREE_H) java/zipfile.h
> +  $(JAVA_TREE_H) java/zipfile.h $(HASH_TABLE_H)
>
>  # jcf-path.o needs a -D.
>  CFLAGS-java/jcf-path.o += \
> Index: gcc/java/jcf-io.c
> ===================================================================
> --- gcc/java/jcf-io.c	(revision 191941)
> +++ gcc/java/jcf-io.c	(working copy)
> @@ -31,7 +31,7 @@ The Free Software Foundation is independ
>  #include "jcf.h"
>  #include "tree.h"
>  #include "java-tree.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
>  #include <dirent.h>
>
>  #include "zlib.h"
> @@ -271,20 +271,34 @@ find_classfile (char *filename, JCF *jcf
>    return open_class (filename, jcf, fd, dep_name);
>  }
>
> -/* Returns 1 if the CLASSNAME (really a char *) matches the name
> -   stored in TABLE_ENTRY (also a char *).  */
>
> -static int
> -memoized_class_lookup_eq (const void *table_entry, const void *classname)
> +/* Hash table helper.  */
> +
> +struct charstar_hash : typed_noop_remove <char>
>  {
> -  return strcmp ((const char *)classname, (const char *)table_entry) == 0;
> +  typedef const char T;
> +  static inline hashval_t hash (const T *candidate);
> +  static inline bool equal (const T *existing, const T *candidate);
> +};
> +
> +inline hashval_t
> +charstar_hash::hash (const T *candidate)
> +{
> +  return htab_hash_string (candidate);
>  }
>
> +inline bool
> +charstar_hash::equal (const T *existing, const T *candidate)
> +{
> +  return strcmp (existing, candidate) == 0;
> +}
> +
> +
>  /* A hash table keeping track of class names that were not found
>     during class lookup.  (There is no need to cache the values
>     associated with names that were found; they are saved in
>     IDENTIFIER_CLASS_VALUE.)  */
> -static htab_t memoized_class_lookups;
> +static hash_table <charstar_hash> memoized_class_lookups;
>
>  /* Returns a freshly malloc'd string with the fully qualified pathname
>     of the .class file for the class CLASSNAME.  CLASSNAME must be
> @@ -306,16 +320,13 @@ find_class (const char *classname, int c
>    hashval_t hash;
>
>    /* Create the hash table, if it does not already exist.  */
> -  if (!memoized_class_lookups)
> -    memoized_class_lookups = htab_create (37,
> -					  htab_hash_string,
> -					  memoized_class_lookup_eq,
> -					  NULL);
> +  if (!memoized_class_lookups.is_created ())
> +    memoized_class_lookups.create (37);
>
>    /* Loop for this class in the hashtable.  If it is present, we've
>       already looked for this class and failed to find it.  */
> -  hash = htab_hash_string (classname);
> -  if (htab_find_with_hash (memoized_class_lookups, classname, hash))
> +  hash = charstar_hash::hash (classname);
> +  if (memoized_class_lookups.find_with_hash (classname, hash))
>      return NULL;
>
>    /* Allocate and zero out the buffer, since we don't explicitly put a
> @@ -390,8 +401,8 @@ find_class (const char *classname, int c
>
>    /* Remember that this class could not be found so that we do not
>       have to look again.  */
> -  *htab_find_slot_with_hash (memoized_class_lookups, classname, hash,
> INSERT)
> -    = (void *) CONST_CAST (char *, classname);
> +  *memoized_class_lookups.find_slot_with_hash (classname, hash, INSERT)
> +    = classname;
>
>    return NULL;
>   found:
> Index: gcc/c/Make-lang.in
> ===================================================================
> --- gcc/c/Make-lang.in	(revision 191941)
> +++ gcc/c/Make-lang.in	(working copy)
> @@ -162,7 +162,7 @@ c/c-decl.o : c/c-decl.c c/c-lang.h $(CON
>  	$(TREE_H) $(C_TREE_H) $(GGC_H) $(TARGET_H) $(FLAGS_H) $(FUNCTION_H) \
>  	output.h debug.h toplev.h intl.h $(TM_P_H) $(TREE_INLINE_H) \
>  	$(TIMEVAR_H) $(OPTS_H) $(C_PRAGMA_H) gt-c-c-decl.h $(CGRAPH_H) \
> -	$(HASHTAB_H) $(LANGHOOKS_DEF_H) \
> +	$(HASH_TABLE_H) $(LANGHOOKS_DEF_H) \
>  	dumpfile.h $(C_COMMON_H) $(CPPLIB_H) $(DIAGNOSTIC_CORE_H) \
>  	$(INPUT_H) langhooks.h pointer-set.h tree-iterator.h \
>  	$(PLUGIN_H) c-family/c-ada-spec.h c-family/c-objc.h
> Index: gcc/c/c-decl.c
> ===================================================================
> --- gcc/c/c-decl.c	(revision 191941)
> +++ gcc/c/c-decl.c	(working copy)
> @@ -53,7 +53,7 @@ along with GCC; see the file COPYING3.
>  #include "diagnostic-core.h"
>  #include "dumpfile.h"
>  #include "cgraph.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
>  #include "langhooks-def.h"
>  #include "pointer-set.h"
>  #include "plugin.h"
> @@ -6895,15 +6895,16 @@ is_duplicate_field (tree x, tree y)
>     to HTAB, giving errors for any duplicates.  */
>
>  static void
> -detect_field_duplicates_hash (tree fieldlist, htab_t htab)
> +detect_field_duplicates_hash (tree fieldlist,
> +			      hash_table <pointer_hash <tree_node> > htab)
>  {
>    tree x, y;
> -  void **slot;
> +  tree_node **slot;
>
>    for (x = fieldlist; x ; x = DECL_CHAIN (x))
>      if ((y = DECL_NAME (x)) != 0)
>        {
> -	slot = htab_find_slot (htab, y, INSERT);
> +	slot = htab.find_slot (y, INSERT);
>  	if (*slot)
>  	  {
>  	    error ("duplicate member %q+D", x);
> @@ -6923,7 +6924,7 @@ detect_field_duplicates_hash (tree field
>  	    && TREE_CODE (TYPE_NAME (TREE_TYPE (x))) == TYPE_DECL)
>  	  {
>  	    tree xn = DECL_NAME (TYPE_NAME (TREE_TYPE (x)));
> -	    slot = htab_find_slot (htab, xn, INSERT);
> +	    slot = htab.find_slot (xn, INSERT);
>  	    if (*slot)
>  	      error ("duplicate member %q+D", TYPE_NAME (TREE_TYPE (x)));
>  	    *slot = xn;
> @@ -6995,10 +6996,11 @@ detect_field_duplicates (tree fieldlist)
>      }
>    else
>      {
> -      htab_t htab = htab_create (37, htab_hash_pointer, htab_eq_pointer,
> NULL);
> +      hash_table <pointer_hash <tree_node> > htab;
> +      htab.create (37);
>
>        detect_field_duplicates_hash (fieldlist, htab);
> -      htab_delete (htab);
> +      htab.dispose ();
>      }
>  }
>
> Index: gcc/fold-const.c
> ===================================================================
> --- gcc/fold-const.c	(revision 191941)
> +++ gcc/fold-const.c	(working copy)
> @@ -56,7 +56,7 @@ along with GCC; see the file COPYING3.
>  #include "diagnostic-core.h"
>  #include "intl.h"
>  #include "ggc.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
>  #include "langhooks.h"
>  #include "md5.h"
>  #include "gimple.h"
> @@ -14320,7 +14320,8 @@ fold (tree expr)
>  #ifdef ENABLE_FOLD_CHECKING
>  #undef fold
>
> -static void fold_checksum_tree (const_tree, struct md5_ctx *, htab_t);
> +static void fold_checksum_tree (const_tree, struct md5_ctx *,
> +				hash_table <pointer_hash <tree_node> >);
>  static void fold_check_failed (const_tree, const_tree);
>  void print_fold_checksum (const_tree);
>
> @@ -14334,20 +14335,20 @@ fold (tree expr)
>    tree ret;
>    struct md5_ctx ctx;
>    unsigned char checksum_before[16], checksum_after[16];
> -  htab_t ht;
> +  hash_table <pointer_hash <tree_node> > ht;
>
> -  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  ht.create (32);
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (expr, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    ret = fold_1 (expr);
>
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (expr, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after);
> -  htab_delete (ht);
> +  ht.dispose ();
>
>    if (memcmp (checksum_before, checksum_after, 16))
>      fold_check_failed (expr, ret);
> @@ -14360,13 +14361,13 @@ print_fold_checksum (const_tree expr)
>  {
>    struct md5_ctx ctx;
>    unsigned char checksum[16], cnt;
> -  htab_t ht;
> +  hash_table <pointer_hash <tree_node> > ht;
>
> -  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  ht.create (32);
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (expr, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum);
> -  htab_delete (ht);
> +  ht.dispose ();
>    for (cnt = 0; cnt < 16; ++cnt)
>      fprintf (stderr, "%02x", checksum[cnt]);
>    putc ('\n', stderr);
> @@ -14379,9 +14380,10 @@ fold_check_failed (const_tree expr ATTRI
>  }
>
>  static void
> -fold_checksum_tree (const_tree expr, struct md5_ctx *ctx, htab_t ht)
> +fold_checksum_tree (const_tree expr, struct md5_ctx *ctx,
> +		    hash_table <pointer_hash <tree_node> > ht)
>  {
> -  void **slot;
> +  tree_node **slot;
>    enum tree_code code;
>    union tree_node buf;
>    int i, len;
> @@ -14389,7 +14391,7 @@ fold_checksum_tree (const_tree expr, str
>   recursive_label:
>    if (expr == NULL)
>      return;
> -  slot = (void **) htab_find_slot (ht, expr, INSERT);
> +  slot = ht.find_slot (expr, INSERT);
>    if (*slot != NULL)
>      return;
>    *slot = CONST_CAST_TREE (expr);
> @@ -14538,12 +14540,13 @@ debug_fold_checksum (const_tree t)
>    int i;
>    unsigned char checksum[16];
>    struct md5_ctx ctx;
> -  htab_t ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  hash_table <pointer_hash <tree_node> > ht;
> +  ht.create (32);
>
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (t, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    for (i = 0; i < 16; i++)
>      fprintf (stderr, "%d ", checksum[i]);
> @@ -14566,13 +14569,13 @@ fold_build1_stat_loc (location_t loc,
>  #ifdef ENABLE_FOLD_CHECKING
>    unsigned char checksum_before[16], checksum_after[16];
>    struct md5_ctx ctx;
> -  htab_t ht;
> +  hash_table <pointer_hash <tree_node> > ht;
>
> -  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  ht.create (32);
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op0, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before);
> -  htab_empty (ht);
> +  ht.empty ();
>  #endif
>
>    tem = fold_unary_loc (loc, code, type, op0);
> @@ -14583,7 +14586,7 @@ fold_build1_stat_loc (location_t loc,
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op0, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after);
> -  htab_delete (ht);
> +  ht.dispose ();
>
>    if (memcmp (checksum_before, checksum_after, 16))
>      fold_check_failed (op0, tem);
> @@ -14609,18 +14612,18 @@ fold_build2_stat_loc (location_t loc,
>  		checksum_after_op0[16],
>  		checksum_after_op1[16];
>    struct md5_ctx ctx;
> -  htab_t ht;
> +  hash_table <pointer_hash <tree_node> > ht;
>
> -  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  ht.create (32);
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op0, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_op0);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op1, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_op1);
> -  htab_empty (ht);
> +  ht.empty ();
>  #endif
>
>    tem = fold_binary_loc (loc, code, type, op0, op1);
> @@ -14631,7 +14634,7 @@ fold_build2_stat_loc (location_t loc,
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op0, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_op0);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    if (memcmp (checksum_before_op0, checksum_after_op0, 16))
>      fold_check_failed (op0, tem);
> @@ -14639,7 +14642,7 @@ fold_build2_stat_loc (location_t loc,
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op1, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_op1);
> -  htab_delete (ht);
> +  ht.dispose ();
>
>    if (memcmp (checksum_before_op1, checksum_after_op1, 16))
>      fold_check_failed (op1, tem);
> @@ -14665,23 +14668,23 @@ fold_build3_stat_loc (location_t loc, en
>  		checksum_after_op1[16],
>  		checksum_after_op2[16];
>    struct md5_ctx ctx;
> -  htab_t ht;
> +  hash_table <pointer_hash <tree_node> > ht;
>
> -  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  ht.create (32);
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op0, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_op0);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op1, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_op1);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op2, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_op2);
> -  htab_empty (ht);
> +  ht.empty ();
>  #endif
>
>    gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
> @@ -14693,7 +14696,7 @@ fold_build3_stat_loc (location_t loc, en
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op0, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_op0);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    if (memcmp (checksum_before_op0, checksum_after_op0, 16))
>      fold_check_failed (op0, tem);
> @@ -14701,7 +14704,7 @@ fold_build3_stat_loc (location_t loc, en
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op1, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_op1);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    if (memcmp (checksum_before_op1, checksum_after_op1, 16))
>      fold_check_failed (op1, tem);
> @@ -14709,7 +14712,7 @@ fold_build3_stat_loc (location_t loc, en
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (op2, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_op2);
> -  htab_delete (ht);
> +  ht.dispose ();
>
>    if (memcmp (checksum_before_op2, checksum_after_op2, 16))
>      fold_check_failed (op2, tem);
> @@ -14733,20 +14736,20 @@ fold_build_call_array_loc (location_t lo
>  		checksum_after_fn[16],
>  		checksum_after_arglist[16];
>    struct md5_ctx ctx;
> -  htab_t ht;
> +  hash_table <pointer_hash <tree_node> > ht;
>    int i;
>
> -  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
> +  ht.create (32);
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (fn, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_fn);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    md5_init_ctx (&ctx);
>    for (i = 0; i < nargs; i++)
>      fold_checksum_tree (argarray[i], &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_before_arglist);
> -  htab_empty (ht);
> +  ht.empty ();
>  #endif
>
>    tem = fold_builtin_call_array (loc, type, fn, nargs, argarray);
> @@ -14755,7 +14758,7 @@ fold_build_call_array_loc (location_t lo
>    md5_init_ctx (&ctx);
>    fold_checksum_tree (fn, &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_fn);
> -  htab_empty (ht);
> +  ht.empty ();
>
>    if (memcmp (checksum_before_fn, checksum_after_fn, 16))
>      fold_check_failed (fn, tem);
> @@ -14764,7 +14767,7 @@ fold_build_call_array_loc (location_t lo
>    for (i = 0; i < nargs; i++)
>      fold_checksum_tree (argarray[i], &ctx, ht);
>    md5_finish_ctx (&ctx, checksum_after_arglist);
> -  htab_delete (ht);
> +  ht.dispose ();
>
>    if (memcmp (checksum_before_arglist, checksum_after_arglist, 16))
>      fold_check_failed (NULL_TREE, tem);
> Index: gcc/objc/Make-lang.in
> ===================================================================
> --- gcc/objc/Make-lang.in	(revision 191941)
> +++ gcc/objc/Make-lang.in	(working copy)
> @@ -50,7 +50,7 @@ START_HDRS = $(CONFIG_H) $(SYSTEM_H) cor
>  objc-warn = $(STRICT_WARN)
>
>  # Language-specific object files for Objective C.
> -OBJC_OBJS = objc/objc-lang.o objc/objc-act.o \
> +OBJC_OBJS = objc/objc-lang.o objc/objc-act.o hash-table.o \
>     objc/objc-runtime-shared-support.o \
>     objc/objc-gnu-runtime-abi-01.o \
>     objc/objc-next-runtime-abi-01.o \
> @@ -127,7 +127,7 @@ objc/objc-act.o : objc/objc-act.c \
>     $(START_HDRS) \
>     $(GGC_H) $(DIAGNOSTIC_CORE_H) $(FLAGS_H) input.h \
>     toplev.h $(FUNCTION_H) debug.h $(LANGHOOKS_DEF_H) \
> -   $(HASHTAB_H) $(GIMPLE_H) \
> +   $(HASH_TABLE_H) $(GIMPLE_H) \
>     $(C_PRAGMA_H) $(C_TARGET_H) \
>     objc/objc-encoding.h \
>     objc/objc-map.h \
> Index: gcc/objc/objc-act.c
> ===================================================================
> --- gcc/objc/objc-act.c	(revision 191941)
> +++ gcc/objc/objc-act.c	(working copy)
> @@ -51,7 +51,7 @@ along with GCC; see the file COPYING3.
>  #include "intl.h"
>  #include "cgraph.h"
>  #include "tree-iterator.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
>  #include "langhooks-def.h"
>  /* Different initialization, code gen and meta data generation for each
>     runtime.  */
> @@ -3824,18 +3824,23 @@ objc_get_class_ivars (tree class_name)
>     allows us to store keys in the hashtable, without values (it looks
>     more like a set).  So, we store the DECLs, but define equality as
>     DECLs having the same name, and hash as the hash of the name.  */
> -static hashval_t
> -hash_instance_variable (const PTR p)
> +
> +struct decl_name_hash : typed_noop_remove <tree_node>
> +{
> +  typedef tree_node T;
> +  static inline hashval_t hash (const T *);
> +  static inline bool equal (const T *, const T *);
> +};
> +
> +inline hashval_t
> +decl_name_hash::hash (const T *q)
>  {
> -  const_tree q = (const_tree)p;
>    return (hashval_t) ((intptr_t)(DECL_NAME (q)) >> 3);
>  }
>
> -static int
> -eq_instance_variable (const PTR p1, const PTR p2)
> +inline bool
> +decl_name_hash::equal (const T *a, const T *b)
>  {
> -  const_tree a = (const_tree)p1;
> -  const_tree b = (const_tree)p2;
>    return DECL_NAME (a) == DECL_NAME (b);
>  }
>
> @@ -3916,8 +3921,8 @@ objc_detect_field_duplicates (bool check
>  	  {
>  	    /* First, build the hashtable by putting all the instance
>  	       variables of superclasses in it.  */
> -	    htab_t htab = htab_create (37, hash_instance_variable,
> -				       eq_instance_variable, NULL);
> +	    hash_table <decl_name_hash> htab;
> +	    htab.create (37);
>  	    tree interface;
>  	    for (interface = lookup_interface (CLASS_SUPER_NAME
>  					       (objc_interface_context));
> @@ -3930,7 +3935,7 @@ objc_detect_field_duplicates (bool check
>  		  {
>  		    if (DECL_NAME (ivar) != NULL_TREE)
>  		      {
> -			void **slot = htab_find_slot (htab, ivar, INSERT);
> +			tree_node **slot = htab.find_slot (ivar, INSERT);
>  			/* Do not check for duplicate instance
>  			   variables in superclasses.  Errors have
>  			   already been generated.  */
> @@ -3950,7 +3955,7 @@ objc_detect_field_duplicates (bool check
>  		  {
>  		    if (DECL_NAME (ivar) != NULL_TREE)
>  		      {
> -			tree duplicate_ivar = (tree)(htab_find (htab, ivar));
> +			tree duplicate_ivar = htab.find (ivar);
>  			if (duplicate_ivar != HTAB_EMPTY_ENTRY)
>  			  {
>  			    error_at (DECL_SOURCE_LOCATION (ivar),
> @@ -3977,7 +3982,7 @@ objc_detect_field_duplicates (bool check
>  		  {
>  		    if (DECL_NAME (ivar) != NULL_TREE)
>  		      {
> -			void **slot = htab_find_slot (htab, ivar, INSERT);
> +			tree_node **slot = htab.find_slot (ivar, INSERT);
>  			if (*slot)
>  			  {
>  			    tree duplicate_ivar = (tree)(*slot);
> @@ -3994,7 +3999,7 @@ objc_detect_field_duplicates (bool check
>  		      }
>  		  }
>  	      }
> -	    htab_delete (htab);
> +	    htab.dispose ();
>  	    return true;
>  	  }
>        }
> Index: gcc/cfg.c
> ===================================================================
> --- gcc/cfg.c	(revision 191941)
> +++ gcc/cfg.c	(working copy)
> @@ -53,7 +53,7 @@ along with GCC; see the file COPYING3.
>  #include "coretypes.h"
>  #include "obstack.h"
>  #include "ggc.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
>  #include "alloc-pool.h"
>  #include "tree.h"
>  #include "basic-block.h"
> @@ -976,14 +976,7 @@ scale_bbs_frequencies_gcov_type (basic_b
>        }
>  }
>
> -/* Data structures used to maintain mapping between basic blocks and
> -   copies.  */
> -static htab_t bb_original;
> -static htab_t bb_copy;
> -
> -/* And between loops and copies.  */
> -static htab_t loop_copy;
> -static alloc_pool original_copy_bb_pool;
> +/* Helper types for hash tables.  */
>
>  struct htab_bb_copy_original_entry
>  {
> @@ -993,25 +986,35 @@ struct htab_bb_copy_original_entry
>    int index2;
>  };
>
> -static hashval_t
> -bb_copy_original_hash (const void *p)
> +struct bb_copy_hasher : typed_noop_remove <htab_bb_copy_original_entry>
>  {
> -  const struct htab_bb_copy_original_entry *data
> -    = ((const struct htab_bb_copy_original_entry *)p);
> +  typedef htab_bb_copy_original_entry T;
> +  static inline hashval_t hash (const T *);
> +  static inline bool equal (const T *existing, const T * candidate);
> +};
>
> +inline hashval_t
> +bb_copy_hasher::hash (const T *data)
> +{
>    return data->index1;
>  }
> -static int
> -bb_copy_original_eq (const void *p, const void *q)
> -{
> -  const struct htab_bb_copy_original_entry *data
> -    = ((const struct htab_bb_copy_original_entry *)p);
> -  const struct htab_bb_copy_original_entry *data2
> -    = ((const struct htab_bb_copy_original_entry *)q);
>
> +inline bool
> +bb_copy_hasher::equal (const T *data, const T *data2)
> +{
>    return data->index1 == data2->index1;
>  }
>
> +/* Data structures used to maintain mapping between basic blocks and
> +   copies.  */
> +static hash_table <bb_copy_hasher> bb_original;
> +static hash_table <bb_copy_hasher> bb_copy;
> +
> +/* And between loops and copies.  */
> +static hash_table <bb_copy_hasher> loop_copy;
> +static alloc_pool original_copy_bb_pool;
> +
> +
>  /* Initialize the data structures to maintain mapping between blocks
>     and its copies.  */
>  void
> @@ -1021,10 +1024,9 @@ initialize_original_copy_tables (void)
>    original_copy_bb_pool
>      = create_alloc_pool ("original_copy",
>  			 sizeof (struct htab_bb_copy_original_entry), 10);
> -  bb_original = htab_create (10, bb_copy_original_hash,
> -			     bb_copy_original_eq, NULL);
> -  bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq,
> NULL);
> -  loop_copy = htab_create (10, bb_copy_original_hash,
> bb_copy_original_eq, NULL);
> +  bb_original.create (10);
> +  bb_copy.create (10);
> +  loop_copy.create (10);
>  }
>
>  /* Free the data structures to maintain mapping between blocks and
> @@ -1033,34 +1035,31 @@ void
>  free_original_copy_tables (void)
>  {
>    gcc_assert (original_copy_bb_pool);
> -  htab_delete (bb_copy);
> -  htab_delete (bb_original);
> -  htab_delete (loop_copy);
> +  bb_copy.dispose ();
> +  bb_original.dispose ();
> +  loop_copy.dispose ();
>    free_alloc_pool (original_copy_bb_pool);
> -  bb_copy = NULL;
> -  bb_original = NULL;
> -  loop_copy = NULL;
>    original_copy_bb_pool = NULL;
>  }
>
>  /* Removes the value associated with OBJ from table TAB.  */
>
>  static void
> -copy_original_table_clear (htab_t tab, unsigned obj)
> +copy_original_table_clear (hash_table <bb_copy_hasher> tab, unsigned obj)
>  {
> -  void **slot;
> +  htab_bb_copy_original_entry **slot;
>    struct htab_bb_copy_original_entry key, *elt;
>
>    if (!original_copy_bb_pool)
>      return;
>
>    key.index1 = obj;
> -  slot = htab_find_slot (tab, &key, NO_INSERT);
> +  slot = tab.find_slot (&key, NO_INSERT);
>    if (!slot)
>      return;
>
> -  elt = (struct htab_bb_copy_original_entry *) *slot;
> -  htab_clear_slot (tab, slot);
> +  elt = *slot;
> +  tab.clear_slot (slot);
>    pool_free (original_copy_bb_pool, elt);
>  }
>
> @@ -1068,7 +1067,8 @@ copy_original_table_clear (htab_t tab, u
>     Do nothing when data structures are not initialized.  */
>
>  static void
> -copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
> +copy_original_table_set (hash_table <bb_copy_hasher> tab,
> +			 unsigned obj, unsigned val)
>  {
>    struct htab_bb_copy_original_entry **slot;
>    struct htab_bb_copy_original_entry key;
> @@ -1077,8 +1077,7 @@ copy_original_table_set (htab_t tab, uns
>      return;
>
>    key.index1 = obj;
> -  slot = (struct htab_bb_copy_original_entry **)
> -		htab_find_slot (tab, &key, INSERT);
> +  slot = tab.find_slot (&key, INSERT);
>    if (!*slot)
>      {
>        *slot = (struct htab_bb_copy_original_entry *)
> @@ -1106,7 +1105,7 @@ get_bb_original (basic_block bb)
>    gcc_assert (original_copy_bb_pool);
>
>    key.index1 = bb->index;
> -  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original,
> &key);
> +  entry = bb_original.find (&key);
>    if (entry)
>      return BASIC_BLOCK (entry->index2);
>    else
> @@ -1131,7 +1130,7 @@ get_bb_copy (basic_block bb)
>    gcc_assert (original_copy_bb_pool);
>
>    key.index1 = bb->index;
> -  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy,
> &key);
> +  entry = bb_copy.find (&key);
>    if (entry)
>      return BASIC_BLOCK (entry->index2);
>    else
> @@ -1161,7 +1160,7 @@ get_loop_copy (struct loop *loop)
>    gcc_assert (original_copy_bb_pool);
>
>    key.index1 = loop->num;
> -  entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy,
> &key);
> +  entry = loop_copy.find (&key);
>    if (entry)
>      return get_loop (entry->index2);
>    else
> Index: gcc/cp/class.c
> ===================================================================
> --- gcc/cp/class.c	(revision 191941)
> +++ gcc/cp/class.c	(working copy)
> @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.
>  #include "dumpfile.h"
>  #include "splay-tree.h"
>  #include "pointer-set.h"
> +#include "hash-table.h"
>
>  /* The number of nested classes being processed.  If we are not in the
>     scope of any class, this is zero.  */
> @@ -6465,12 +6466,9 @@ fixed_type_or_null (tree instance, int *
>        else if (TREE_CODE (TREE_TYPE (instance)) == REFERENCE_TYPE)
>  	{
>  	  /* We only need one hash table because it is always left empty.  */
> -	  static htab_t ht;
> -	  if (!ht)
> -	    ht = htab_create (37,
> -			      htab_hash_pointer,
> -			      htab_eq_pointer,
> -			      /*htab_del=*/NULL);
> +	  static hash_table <pointer_hash <tree_node> > ht;
> +	  if (!ht.is_created ())
> +	    ht.create (37);
>
>  	  /* Reference variables should be references to objects.  */
>  	  if (nonnull)
> @@ -6482,15 +6480,15 @@ fixed_type_or_null (tree instance, int *
>  	  if (TREE_CODE (instance) == VAR_DECL
>  	      && DECL_INITIAL (instance)
>  	      && !type_dependent_expression_p_push (DECL_INITIAL (instance))
> -	      && !htab_find (ht, instance))
> +	      && !ht.find (instance))
>  	    {
>  	      tree type;
> -	      void **slot;
> +	      tree_node **slot;
>
> -	      slot = htab_find_slot (ht, instance, INSERT);
> +	      slot = ht.find_slot (instance, INSERT);
>  	      *slot = instance;
>  	      type = RECUR (DECL_INITIAL (instance));
> -	      htab_remove_elt (ht, instance);
> +	      ht.remove_elt (instance);
>
>  	      return type;
>  	    }
> Index: gcc/cp/Make-lang.in
> ===================================================================
> --- gcc/cp/Make-lang.in	(revision 191941)
> +++ gcc/cp/Make-lang.in	(working copy)
> @@ -293,7 +293,7 @@ cp/typeck.o: cp/typeck.c $(CXX_TREE_H) $
>    c-family/c-objc.h
>  cp/class.o: cp/class.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
>    $(TARGET_H) convert.h $(CGRAPH_H) dumpfile.h gt-cp-class.h \
> -  $(SPLAY_TREE_H) pointer-set.h
> +  $(SPLAY_TREE_H) pointer-set.h $(HASH_TABLE_H)
>  cp/call.o: cp/call.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
>    $(DIAGNOSTIC_CORE_H) intl.h gt-cp-call.h convert.h $(TARGET_H)
> langhooks.h \
>    $(TIMEVAR_H) c-family/c-objc.h
> @@ -309,7 +309,7 @@ cp/search.o: cp/search.c $(CXX_TREE_H) $
>    intl.h
>  cp/tree.o: cp/tree.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) \
>    $(TREE_INLINE_H) $(REAL_H) gt-cp-tree.h \
> -  $(TARGET_H) debug.h $(CGRAPH_H) $(SPLAY_TREE_H) $(GIMPLE_H)
> +  $(TARGET_H) debug.h $(CGRAPH_H) $(SPLAY_TREE_H) $(GIMPLE_H)
> $(HASH_TABLE_H)
>  cp/ptree.o: cp/ptree.c $(CXX_TREE_H) $(TM_H)
>  cp/rtti.o: cp/rtti.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) convert.h \
>    $(TARGET_H) $(C_PRAGMA_H) gt-cp-rtti.h intl.h
> @@ -327,7 +327,7 @@ cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_
>  cp/semantics.o: cp/semantics.c $(CXX_TREE_H) $(TM_H) toplev.h \
>    $(FLAGS_H) $(RTL_H) $(TIMEVAR_H) \
>    $(TREE_INLINE_H) $(CGRAPH_H) $(TARGET_H) $(C_COMMON_H) $(GIMPLE_H) \
> -  bitmap.h gt-cp-semantics.h c-family/c-objc.h
> +  bitmap.h gt-cp-semantics.h c-family/c-objc.h $(HASH_TABLE_H)
>  cp/dump.o: cp/dump.c $(CXX_TREE_H) $(TM_H) $(TREE_DUMP_H)
>  cp/optimize.o: cp/optimize.c $(CXX_TREE_H) $(TM_H) \
>    input.h $(PARAMS_H) debug.h $(TREE_INLINE_H) $(GIMPLE_H) \
> Index: gcc/cp/tree.c
> ===================================================================
> --- gcc/cp/tree.c	(revision 191941)
> +++ gcc/cp/tree.c	(working copy)
> @@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.
>  #include "cgraph.h"
>  #include "splay-tree.h"
>  #include "gimple.h" /* gimple_has_body_p */
> +#include "hash-table.h"
>
>  static tree bot_manip (tree *, int *, void *);
>  static tree bot_replace (tree *, int *, void *);
> @@ -1918,17 +1919,18 @@ static tree
>  verify_stmt_tree_r (tree* tp, int * /*walk_subtrees*/, void* data)
>  {
>    tree t = *tp;
> -  htab_t *statements = (htab_t *) data;
> -  void **slot;
> +  hash_table <pointer_hash <tree_node> > *statements
> +      = static_cast <hash_table <pointer_hash <tree_node> > *> (data);
> +  tree_node **slot;
>
>    if (!STATEMENT_CODE_P (TREE_CODE (t)))
>      return NULL_TREE;
>
>    /* If this statement is already present in the hash table, then
>       there is a circularity in the statement tree.  */
> -  gcc_assert (!htab_find (*statements, t));
> +  gcc_assert (!statements->find (t));
>
> -  slot = htab_find_slot (*statements, t, INSERT);
> +  slot = statements->find_slot (t, INSERT);
>    *slot = t;
>
>    return NULL_TREE;
> @@ -1941,10 +1943,10 @@ verify_stmt_tree_r (tree* tp, int * /*wa
>  void
>  verify_stmt_tree (tree t)
>  {
> -  htab_t statements;
> -  statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
> +  hash_table <pointer_hash <tree_node> > statements;
> +  statements.create (37);
>    cp_walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
> -  htab_delete (statements);
> +  statements.dispose ();
>  }
>
>  /* Check if the type T depends on a type with no linkage and if so, return
> Index: gcc/cp/semantics.c
> ===================================================================
> --- gcc/cp/semantics.c	(revision 191941)
> +++ gcc/cp/semantics.c	(working copy)
> @@ -44,6 +44,7 @@ along with GCC; see the file COPYING3.
>  #include "target.h"
>  #include "gimple.h"
>  #include "bitmap.h"
> +#include "hash-table.h"
>
>  /* There routines provide a modular interface to perform many parsing
>     operations.  They may therefore be used during actual parsing, or
> @@ -3811,7 +3812,7 @@ struct nrv_data
>  {
>    tree var;
>    tree result;
> -  htab_t visited;
> +  hash_table <pointer_hash <tree_node> > visited;
>  };
>
>  /* Helper function for walk_tree, used by finalize_nrv below.  */
> @@ -3820,7 +3821,7 @@ static tree
>  finalize_nrv_r (tree* tp, int* walk_subtrees, void* data)
>  {
>    struct nrv_data *dp = (struct nrv_data *)data;
> -  void **slot;
> +  tree_node **slot;
>
>    /* No need to walk into types.  There wouldn't be any need to walk into
>       non-statements, except that we have to consider STMT_EXPRs.  */
> @@ -3859,7 +3860,7 @@ finalize_nrv_r (tree* tp, int* walk_subt
>    /* Avoid walking into the same tree more than once.  Unfortunately, we
>       can't just use walk_tree_without duplicates because it would only
> call
>       us for the first occurrence of dp->var in the function body.  */
> -  slot = htab_find_slot (dp->visited, *tp, INSERT);
> +  slot = dp->visited.find_slot (*tp, INSERT);
>    if (*slot)
>      *walk_subtrees = 0;
>    else
> @@ -3891,9 +3892,9 @@ finalize_nrv (tree *tp, tree var, tree r
>
>    data.var = var;
>    data.result = result;
> -  data.visited = htab_create (37, htab_hash_pointer, htab_eq_pointer,
> NULL);
> +  data.visited.create (37);
>    cp_walk_tree (tp, finalize_nrv_r, &data, 0);
> -  htab_delete (data.visited);
> +  data.visited.dispose ();
>  }
>  
>  /* Create CP_OMP_CLAUSE_INFO for clause C.  Returns true if it is invalid.
> */
> Index: gcc/hash-table.h
> ===================================================================
> --- gcc/hash-table.h	(revision 191941)
> +++ gcc/hash-table.h	(working copy)
> @@ -223,15 +223,15 @@ public:
>    void create (size_t initial_slots);
>    bool is_created ();
>    void dispose ();
> -  T *find (T *comparable);
> -  T *find_with_hash (T *comparable, hashval_t hash);
> -  T **find_slot (T *comparable, enum insert_option insert);
> -  T **find_slot_with_hash (T *comparable, hashval_t hash,
> +  T *find (const T *comparable);
> +  T *find_with_hash (const T *comparable, hashval_t hash);
> +  T **find_slot (const T *comparable, enum insert_option insert);
> +  T **find_slot_with_hash (const T *comparable, hashval_t hash,
>  				   enum insert_option insert);
>    void empty ();
>    void clear_slot (T **slot);
> -  void remove_elt (T *comparable);
> -  void remove_elt_with_hash (T *comparable, hashval_t hash);
> +  void remove_elt (const T *comparable);
> +  void remove_elt_with_hash (const T *comparable, hashval_t hash);
>    size_t size();
>    size_t elements();
>    double collisions();
> @@ -273,7 +273,7 @@ hash_table <Descr, Allocator>::is_create
>  template <typename Descr,
>  	  template <typename Type> class Allocator>
>  inline typename Descr::T *
> -hash_table <Descr, Allocator>::find (T *comparable)
> +hash_table <Descr, Allocator>::find (const T *comparable)
>  {
>    return find_with_hash (comparable, Descr::hash (comparable));
>  }
> @@ -285,7 +285,7 @@ template <typename Descr,
>  	  template <typename Type> class Allocator>
>  inline typename Descr::T **
>  hash_table <Descr, Allocator>
> -::find_slot (T *comparable, enum insert_option insert)
> +::find_slot (const T *comparable, enum insert_option insert)
>  {
>    return find_slot_with_hash (comparable, Descr::hash (comparable),
> insert);
>  }
> @@ -297,7 +297,7 @@ template <typename Descr,
>  	  template <typename Type> class Allocator>
>  inline void
>  hash_table <Descr, Allocator>
> -::remove_elt (T *comparable)
> +::remove_elt (const T *comparable)
>  {
>    remove_elt_with_hash (comparable, Descr::hash (comparable));
>  }
> @@ -495,7 +495,7 @@ template <typename Descr,
>  	  template <typename Type> class Allocator>
>  typename Descr::T *
>  hash_table <Descr, Allocator>
> -::find_with_hash (T *comparable, hashval_t hash)
> +::find_with_hash (const T *comparable, hashval_t hash)
>  {
>    hashval_t index, hash2;
>    size_t size;
> @@ -538,7 +538,7 @@ template <typename Descr,
>  	  template <typename Type> class Allocator>
>  typename Descr::T **
>  hash_table <Descr, Allocator>
> -::find_slot_with_hash (T *comparable, hashval_t hash,
> +::find_slot_with_hash (const T *comparable, hashval_t hash,
>  		       enum insert_option insert)
>  {
>    T **first_deleted_slot;
> @@ -609,7 +609,7 @@ template <typename Descr,
>  void
>  hash_table <Descr, Allocator>::empty ()
>  {
> -  size_t size = htab_size (htab);
> +  size_t size = htab->size;
>    T **entries = htab->entries;
>    int i;
>
> @@ -651,7 +651,7 @@ hash_table <Descr, Allocator>
>
>    Descr::remove (*slot);
>
> -  *slot = HTAB_DELETED_ENTRY;
> +  *slot = static_cast <T *> (HTAB_DELETED_ENTRY);
>    htab->n_deleted++;
>  }
>
> @@ -664,7 +664,7 @@ template <typename Descr,
>  	  template <typename Type> class Allocator>
>  void
>  hash_table <Descr, Allocator>
> -::remove_elt_with_hash (T *comparable, hashval_t hash)
> +::remove_elt_with_hash (const T *comparable, hashval_t hash)
>  {
>    T **slot;
>
> Index: gcc/dse.c
> ===================================================================
> --- gcc/dse.c	(revision 191941)
> +++ gcc/dse.c	(working copy)
> @@ -26,7 +26,7 @@ along with GCC; see the file COPYING3.
>  #include "config.h"
>  #include "system.h"
>  #include "coretypes.h"
> -#include "hashtab.h"
> +#include "hash-table.h"
>  #include "tm.h"
>  #include "rtl.h"
>  #include "tree.h"
> @@ -547,9 +547,6 @@ typedef struct group_info *group_info_t;
>  typedef const struct group_info *const_group_info_t;
>  static alloc_pool rtx_group_info_pool;
>
> -/* Tables of group_info structures, hashed by base value.  */
> -static htab_t rtx_group_table;
> -
>  /* Index into the rtx_group_vec.  */
>  static int rtx_group_next_id;
>
> @@ -655,23 +652,29 @@ clear_alias_set_lookup (alias_set_type a
>  /* Hashtable callbacks for maintaining the "bases" field of
>     store_group_info, given that the addresses are function invariants.  */
>
> -static int
> -invariant_group_base_eq (const void *p1, const void *p2)
> +struct invariant_group_base_hasher : typed_noop_remove <group_info>
> +{
> +  typedef group_info T;
> +  static inline hashval_t hash (const T *);
> +  static inline bool equal (const T *, const T *);
> +};
> +
> +inline bool
> +invariant_group_base_hasher::equal (const T *gi1, const T *gi2)
>  {
> -  const_group_info_t gi1 = (const_group_info_t) p1;
> -  const_group_info_t gi2 = (const_group_info_t) p2;
>    return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
>  }
>
> -
> -static hashval_t
> -invariant_group_base_hash (const void *p)
> +inline hashval_t
> +invariant_group_base_hasher::hash (const T *gi)
>  {
> -  const_group_info_t gi = (const_group_info_t) p;
>    int do_not_record;
>    return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
>  }
>
> +/* Tables of group_info structures, hashed by base value.  */
> +static hash_table <invariant_group_base_hasher> rtx_group_table;
> +
>
>  /* Get the GROUP for BASE.  Add a new group if it is not there.  */
>
> @@ -680,14 +683,14 @@ get_group_info (rtx base)
>  {
>    struct group_info tmp_gi;
>    group_info_t gi;
> -  void **slot;
> +  group_info **slot;
>
>    if (base)
>      {
>        /* Find the store_base_info structure for BASE, creating a new one
>  	 if necessary.  */
>        tmp_gi.rtx_base = base;
> -      slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
> +      slot = rtx_group_table.find_slot (&tmp_gi, INSERT);
>        gi = (group_info_t) *slot;
>      }
>    else
> @@ -777,8 +780,7 @@ dse_step0 (void)
>      = create_alloc_pool ("deferred_change_pool",
>  			 sizeof (struct deferred_change), 10);
>
> -  rtx_group_table = htab_create (11, invariant_group_base_hash,
> -				 invariant_group_base_eq, NULL);
> +  rtx_group_table.create (11);
>
>    bb_table = XNEWVEC (bb_info_t, last_basic_block);
>    rtx_group_next_id = 0;
> @@ -2872,7 +2874,7 @@ dse_step1 (void)
>
>    BITMAP_FREE (regs_live);
>    cselib_finish ();
> -  htab_empty (rtx_group_table);
> +  rtx_group_table.empty ();
>  }
>
>  
> @@ -3812,7 +3814,7 @@ dse_step7 (void)
>
>    end_alias_analysis ();
>    free (bb_table);
> -  htab_delete (rtx_group_table);
> +  rtx_group_table.dispose ();
>    VEC_free (group_info_t, heap, rtx_group_vec);
>    BITMAP_FREE (all_blocks);
>    BITMAP_FREE (scratch);
> Index: gcc/Makefile.in
> ===================================================================
> --- gcc/Makefile.in	(revision 191941)
> +++ gcc/Makefile.in	(working copy)
> @@ -2616,8 +2616,8 @@ tree-diagnostic.o : tree-diagnostic.c $(
>     $(TREE_H) $(DIAGNOSTIC_H) tree-diagnostic.h langhooks.h
> $(LANGHOOKS_DEF_H) \
>     $(VEC_H) $(TREE_PRETTY_PRINT_H)
>  fold-const.o : fold-const.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
> -   $(TREE_H) $(FLAGS_H) $(DIAGNOSTIC_CORE_H) $(HASHTAB_H) $(EXPR_H)
> $(RTL_H) \
> -   $(GGC_H) $(TM_P_H) langhooks.h $(MD5_H) intl.h $(TARGET_H) \
> +   $(TREE_H) $(FLAGS_H) $(DIAGNOSTIC_CORE_H) $(HASH_TABLE_H) $(EXPR_H) \
> +   $(RTL_H) $(GGC_H) $(TM_P_H) langhooks.h $(MD5_H) intl.h $(TARGET_H) \
>     $(GIMPLE_H) realmpfr.h $(TREE_FLOW_H)
>  diagnostic.o : diagnostic.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
>     version.h $(DEMANGLE_H) $(INPUT_H) intl.h $(BACKTRACE_H) $(DIAGNOSTIC_H)
> \
> @@ -2929,7 +2929,7 @@ dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) co
>     $(TREE_H) $(TM_P_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
>     $(RECOG_H) $(EXPR_H) $(DF_H) cselib.h $(DBGCNT_H) \
>     $(TREE_PASS_H) alloc-pool.h $(ALIAS_H) $(OPTABS_H) $(TARGET_H) \
> -   $(BITMAP_H) $(PARAMS_H) $(TREE_FLOW_H)
> +   $(BITMAP_H) $(PARAMS_H) $(TREE_FLOW_H) $(HASH_TABLE_H)
>  fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
>     $(DIAGNOSTIC_CORE_H) insn-config.h $(RECOG_H) $(FLAGS_H)
> $(OBSTACK_H) $(BASIC_BLOCK_H) \
>     $(DF_H) alloc-pool.h $(TREE_PASS_H) $(TARGET_H) \
> @@ -3058,7 +3058,7 @@ auto-inc-dec.o : auto-inc-dec.c $(CONFIG
>     $(REGS_H) $(FLAGS_H) $(FUNCTION_H) $(EXCEPT_H)
> $(DIAGNOSTIC_CORE_H) $(RECOG_H) \
>     $(EXPR_H) $(TREE_PASS_H) $(DF_H) $(DBGCNT_H) $(TARGET_H)
>  cfg.o : cfg.c $(CONFIG_H) $(SYSTEM_H) coretypes.h dumpfile.h
> $(DIAGNOSTIC_CORE_H) \
> -   $(GGC_H) $(OBSTACK_H) alloc-pool.h $(HASHTAB_H) $(CFGLOOP_H) $(TREE_H)
> \
> +   $(GGC_H) $(OBSTACK_H) alloc-pool.h $(HASH_TABLE_H) $(CFGLOOP_H)
> $(TREE_H) \
>     $(BASIC_BLOCK_H)
>  cfghooks.o: cfghooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H)
> \
>     $(TREE_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) $(TIMEVAR_H) toplev.h
> $(DIAGNOSTIC_CORE_H) $(CFGLOOP_H)
>
> --
> Lawrence Crowl
>
Diego Novillo - Oct. 5, 2012, 10:52 p.m.
On Wed, Oct 3, 2012 at 6:46 PM, Lawrence Crowl <crowl@googlers.com> wrote:

> On 10/2/12, Richard Guenther <rguenther@suse.de> wrote:
>> You are changing a hashtable used by fold checking, did you test
>> with fold checking enabled?
>
> One small thinko fixed.  Patch passes tests.
>
>> The cfg.c, dse.c and hash-table.h parts are ok for trunk, I'll
>> leave the rest to respective maintainers of the pieces of the
>> compiler.
>
> +cc
> java: tromey@redhat.com
> c: rth@redhat.com
> objc: mikestump@comcast.net
> cp: jason@redhat.com
>
> ====
>
> Change more non-GTY hash tables to use the new type-safe template hash table.
> Constify member function parameters that can be const.
> Correct a couple of expressions in formerly uninstantiated templates.
>
> The new code is 0.362% faster in bootstrap, with a 99.5% confidence of
> being faster.
>
> Tested on x86-64.
>
> Okay for trunk?
>
>
> Index: gcc/java/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
>         * Make-lang.in (JAVA_OBJS): Add dependence on hash-table.o.
>         (JCFDUMP_OBJS): Add dependence on hash-table.o.
>         (jcf-io.o): Add dependence on hash-table.h.
>         * jcf-io.c (memoized_class_lookups): Change to use type-safe hash table.
>
> Index: gcc/c/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
>         * Make-lang.in (c-decl.o): Add dependence on hash-table.h.
>         * c-decl.c (detect_field_duplicates_hash): Change to new type-safe
>         hash table.
>
> Index: gcc/objc/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
>         * Make-lang.in (OBJC_OBJS): Add dependence on hash-table.o.
>         (objc-act.o): Add dependence on hash-table.h.
>         * objc-act.c (objc_detect_field_duplicates): Change to new type-safe
>         hash table.
>
> Index: gcc/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
>         * Makefile.in (fold-const.o): Add depencence on hash-table.h.
>         (dse.o): Likewise.
>         (cfg.o): Likewise.
>         * fold-const.c (fold_checksum_tree): Change to new type-safe hash table.
>         * (print_fold_checksum): Likewise.
>         * cfg.c (var bb_original): Likewise.
>         * (var bb_copy): Likewise.
>         * (var loop_copy): Likewise.
>         * hash-table.h (template hash_table): Constify parameters for find...
>         and remove_elt... member functions.
>         (hash_table::empty) Correct size expression.
>         (hash_table::clear_slot) Correct deleted entry assignment.
>         * dse.c (var rtx_group_table): Change to new type-safe hash table.
>
> Index: gcc/cp/ChangeLog
>
> 2012-10-01  Lawrence Crowl  <crowl@google.com>
>
>         * Make-lang.in (class.o): Add dependence on hash-table.h.
>         (tree.o): Likewise.
>         (semantics.o): Likewise.
>         * class.c (fixed_type_or_null): Change to new type-safe hash table.
>         * tree.c (verify_stmt_tree): Likewise.
>         (verify_stmt_tree_r): Likewise.
>         * semantics.c (struct nrv_data): Likewise.

Given that the changes to the front ends are mechanical and a
side-effect of the main hash table changes, I think they should be OK
without further review (provided tests pass of course).

The changes look fine to me.  To be extra safe, let's wait a couple
more days to give the FE maintainers a chance to look at the patch.


Diego.
Lawrence Crowl - Oct. 9, 2012, 9:21 p.m.
On 10/5/12, Diego Novillo <dnovillo@google.com> wrote:
> On Oct 3, 2012 Lawrence Crowl <crowl@googlers.com> wrote:
> > Change more non-GTY hash tables to use the new type-safe
> > template hash table.  Constify member function parameters that
> > can be const.  Correct a couple of expressions in formerly
> > uninstantiated templates.
> >
> > The new code is 0.362% faster in bootstrap, with a 99.5%
> > confidence of being faster.
> >
> > Tested on x86-64.
> >
> > Okay for trunk?
>
> Given that the changes to the front ends are mechanical and a
> side-effect of the main hash table changes, I think they should
> be OK without further review (provided tests pass of course).
>
> The changes look fine to me.  To be extra safe, let's wait a couple
> more days to give the FE maintainers a chance to look at the patch.

Committed.

Patch

====

Change more non-GTY hash tables to use the new type-safe template hash table.
Constify member function parameters that can be const.
Correct a couple of expressions in formerly uninstantiated templates.

The new code is 0.362% faster in bootstrap, with a 99.5% confidence of
being faster.

Tested on x86-64.

Okay for trunk?


Index: gcc/java/ChangeLog

2012-10-01  Lawrence Crowl  <crowl@google.com>

	* Make-lang.in (JAVA_OBJS): Add dependence on hash-table.o.
	(JCFDUMP_OBJS): Add dependence on hash-table.o.
	(jcf-io.o): Add dependence on hash-table.h.
	* jcf-io.c (memoized_class_lookups): Change to use type-safe hash table.

Index: gcc/c/ChangeLog

2012-10-01  Lawrence Crowl  <crowl@google.com>

	* Make-lang.in (c-decl.o): Add dependence on hash-table.h.
	* c-decl.c (detect_field_duplicates_hash): Change to new type-safe
	hash table.

Index: gcc/objc/ChangeLog

2012-10-01  Lawrence Crowl  <crowl@google.com>

	* Make-lang.in (OBJC_OBJS): Add dependence on hash-table.o.
	(objc-act.o): Add dependence on hash-table.h.
	* objc-act.c (objc_detect_field_duplicates): Change to new type-safe
	hash table.

Index: gcc/ChangeLog

2012-10-01  Lawrence Crowl  <crowl@google.com>

	* Makefile.in (fold-const.o): Add depencence on hash-table.h.
	(dse.o): Likewise.
	(cfg.o): Likewise.
	* fold-const.c (fold_checksum_tree): Change to new type-safe hash table.
	* (print_fold_checksum): Likewise.
	* cfg.c (var bb_original): Likewise.
	* (var bb_copy): Likewise.
	* (var loop_copy): Likewise.
	* hash-table.h (template hash_table): Constify parameters for find...
	and remove_elt... member functions.
        (hash_table::empty) Correct size expression.
        (hash_table::clear_slot) Correct deleted entry assignment.
	* dse.c (var rtx_group_table): Change to new type-safe hash table.

Index: gcc/cp/ChangeLog

2012-10-01  Lawrence Crowl  <crowl@google.com>

	* Make-lang.in (class.o): Add dependence on hash-table.h.
	(tree.o): Likewise.
	(semantics.o): Likewise.
	* class.c (fixed_type_or_null): Change to new type-safe hash table.
	* tree.c (verify_stmt_tree): Likewise.
	(verify_stmt_tree_r): Likewise.
	* semantics.c (struct nrv_data): Likewise.


Index: gcc/java/Make-lang.in
===================================================================
--- gcc/java/Make-lang.in	(revision 191941)
+++ gcc/java/Make-lang.in	(working copy)
@@ -83,10 +83,10 @@  JAVA_OBJS = java/class.o java/decl.o jav
   java/zextract.o java/jcf-io.o java/win32-host.o java/jcf-parse.o
java/mangle.o \
   java/mangle_name.o java/builtins.o java/resource.o \
   java/jcf-depend.o \
-  java/jcf-path.o java/boehm.o java/java-gimplify.o
+  java/jcf-path.o java/boehm.o java/java-gimplify.o hash-table.o

 JCFDUMP_OBJS = java/jcf-dump.o java/jcf-io.o java/jcf-depend.o
java/jcf-path.o \
-		java/win32-host.o java/zextract.o ggc-none.o
+		java/win32-host.o java/zextract.o ggc-none.o hash-table.o

 JVGENMAIN_OBJS = java/jvgenmain.o java/mangle_name.o

@@ -326,7 +326,7 @@  java/java-gimplify.o: java/java-gimplify
 # jcf-io.o needs $(ZLIBINC) added to cflags.
 CFLAGS-java/jcf-io.o += $(ZLIBINC)
 java/jcf-io.o: java/jcf-io.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
-  $(JAVA_TREE_H) java/zipfile.h
+  $(JAVA_TREE_H) java/zipfile.h $(HASH_TABLE_H)

 # jcf-path.o needs a -D.
 CFLAGS-java/jcf-path.o += \
Index: gcc/java/jcf-io.c
===================================================================
--- gcc/java/jcf-io.c	(revision 191941)
+++ gcc/java/jcf-io.c	(working copy)
@@ -31,7 +31,7 @@  The Free Software Foundation is independ
 #include "jcf.h"
 #include "tree.h"
 #include "java-tree.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include <dirent.h>

 #include "zlib.h"
@@ -271,20 +271,34 @@  find_classfile (char *filename, JCF *jcf
   return open_class (filename, jcf, fd, dep_name);
 }

-/* Returns 1 if the CLASSNAME (really a char *) matches the name
-   stored in TABLE_ENTRY (also a char *).  */

-static int
-memoized_class_lookup_eq (const void *table_entry, const void *classname)
+/* Hash table helper.  */
+
+struct charstar_hash : typed_noop_remove <char>
 {
-  return strcmp ((const char *)classname, (const char *)table_entry) == 0;
+  typedef const char T;
+  static inline hashval_t hash (const T *candidate);
+  static inline bool equal (const T *existing, const T *candidate);
+};
+
+inline hashval_t
+charstar_hash::hash (const T *candidate)
+{
+  return htab_hash_string (candidate);
 }

+inline bool
+charstar_hash::equal (const T *existing, const T *candidate)
+{
+  return strcmp (existing, candidate) == 0;
+}
+
+
 /* A hash table keeping track of class names that were not found
    during class lookup.  (There is no need to cache the values
    associated with names that were found; they are saved in
    IDENTIFIER_CLASS_VALUE.)  */
-static htab_t memoized_class_lookups;
+static hash_table <charstar_hash> memoized_class_lookups;

 /* Returns a freshly malloc'd string with the fully qualified pathname
    of the .class file for the class CLASSNAME.  CLASSNAME must be
@@ -306,16 +320,13 @@  find_class (const char *classname, int c
   hashval_t hash;

   /* Create the hash table, if it does not already exist.  */
-  if (!memoized_class_lookups)
-    memoized_class_lookups = htab_create (37,
-					  htab_hash_string,
-					  memoized_class_lookup_eq,
-					  NULL);
+  if (!memoized_class_lookups.is_created ())
+    memoized_class_lookups.create (37);

   /* Loop for this class in the hashtable.  If it is present, we've
      already looked for this class and failed to find it.  */
-  hash = htab_hash_string (classname);
-  if (htab_find_with_hash (memoized_class_lookups, classname, hash))
+  hash = charstar_hash::hash (classname);
+  if (memoized_class_lookups.find_with_hash (classname, hash))
     return NULL;

   /* Allocate and zero out the buffer, since we don't explicitly put a
@@ -390,8 +401,8 @@  find_class (const char *classname, int c

   /* Remember that this class could not be found so that we do not
      have to look again.  */
-  *htab_find_slot_with_hash (memoized_class_lookups, classname, hash, INSERT)
-    = (void *) CONST_CAST (char *, classname);
+  *memoized_class_lookups.find_slot_with_hash (classname, hash, INSERT)
+    = classname;

   return NULL;
  found:
Index: gcc/c/Make-lang.in
===================================================================
--- gcc/c/Make-lang.in	(revision 191941)
+++ gcc/c/Make-lang.in	(working copy)
@@ -162,7 +162,7 @@  c/c-decl.o : c/c-decl.c c/c-lang.h $(CON
 	$(TREE_H) $(C_TREE_H) $(GGC_H) $(TARGET_H) $(FLAGS_H) $(FUNCTION_H) \
 	output.h debug.h toplev.h intl.h $(TM_P_H) $(TREE_INLINE_H) \
 	$(TIMEVAR_H) $(OPTS_H) $(C_PRAGMA_H) gt-c-c-decl.h $(CGRAPH_H) \
-	$(HASHTAB_H) $(LANGHOOKS_DEF_H) \
+	$(HASH_TABLE_H) $(LANGHOOKS_DEF_H) \
 	dumpfile.h $(C_COMMON_H) $(CPPLIB_H) $(DIAGNOSTIC_CORE_H) \
 	$(INPUT_H) langhooks.h pointer-set.h tree-iterator.h \
 	$(PLUGIN_H) c-family/c-ada-spec.h c-family/c-objc.h
Index: gcc/c/c-decl.c
===================================================================
--- gcc/c/c-decl.c	(revision 191941)
+++ gcc/c/c-decl.c	(working copy)
@@ -53,7 +53,7 @@  along with GCC; see the file COPYING3.
 #include "diagnostic-core.h"
 #include "dumpfile.h"
 #include "cgraph.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "langhooks-def.h"
 #include "pointer-set.h"
 #include "plugin.h"
@@ -6895,15 +6895,16 @@  is_duplicate_field (tree x, tree y)
    to HTAB, giving errors for any duplicates.  */

 static void
-detect_field_duplicates_hash (tree fieldlist, htab_t htab)
+detect_field_duplicates_hash (tree fieldlist,
+			      hash_table <pointer_hash <tree_node> > htab)
 {
   tree x, y;
-  void **slot;
+  tree_node **slot;

   for (x = fieldlist; x ; x = DECL_CHAIN (x))
     if ((y = DECL_NAME (x)) != 0)
       {
-	slot = htab_find_slot (htab, y, INSERT);
+	slot = htab.find_slot (y, INSERT);
 	if (*slot)
 	  {
 	    error ("duplicate member %q+D", x);
@@ -6923,7 +6924,7 @@  detect_field_duplicates_hash (tree field
 	    && TREE_CODE (TYPE_NAME (TREE_TYPE (x))) == TYPE_DECL)
 	  {
 	    tree xn = DECL_NAME (TYPE_NAME (TREE_TYPE (x)));
-	    slot = htab_find_slot (htab, xn, INSERT);
+	    slot = htab.find_slot (xn, INSERT);
 	    if (*slot)
 	      error ("duplicate member %q+D", TYPE_NAME (TREE_TYPE (x)));
 	    *slot = xn;
@@ -6995,10 +6996,11 @@  detect_field_duplicates (tree fieldlist)
     }
   else
     {
-      htab_t htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+      hash_table <pointer_hash <tree_node> > htab;
+      htab.create (37);

       detect_field_duplicates_hash (fieldlist, htab);
-      htab_delete (htab);
+      htab.dispose ();
     }
 }

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c	(revision 191941)
+++ gcc/fold-const.c	(working copy)
@@ -56,7 +56,7 @@  along with GCC; see the file COPYING3.
 #include "diagnostic-core.h"
 #include "intl.h"
 #include "ggc.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "langhooks.h"
 #include "md5.h"
 #include "gimple.h"
@@ -14320,7 +14320,8 @@  fold (tree expr)
 #ifdef ENABLE_FOLD_CHECKING
 #undef fold

-static void fold_checksum_tree (const_tree, struct md5_ctx *, htab_t);
+static void fold_checksum_tree (const_tree, struct md5_ctx *,
+				hash_table <pointer_hash <tree_node> >);
 static void fold_check_failed (const_tree, const_tree);
 void print_fold_checksum (const_tree);

@@ -14334,20 +14335,20 @@  fold (tree expr)
   tree ret;
   struct md5_ctx ctx;
   unsigned char checksum_before[16], checksum_after[16];
-  htab_t ht;
+  hash_table <pointer_hash <tree_node> > ht;

-  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  ht.create (32);
   md5_init_ctx (&ctx);
   fold_checksum_tree (expr, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before);
-  htab_empty (ht);
+  ht.empty ();

   ret = fold_1 (expr);

   md5_init_ctx (&ctx);
   fold_checksum_tree (expr, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after);
-  htab_delete (ht);
+  ht.dispose ();

   if (memcmp (checksum_before, checksum_after, 16))
     fold_check_failed (expr, ret);
@@ -14360,13 +14361,13 @@  print_fold_checksum (const_tree expr)
 {
   struct md5_ctx ctx;
   unsigned char checksum[16], cnt;
-  htab_t ht;
+  hash_table <pointer_hash <tree_node> > ht;

-  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  ht.create (32);
   md5_init_ctx (&ctx);
   fold_checksum_tree (expr, &ctx, ht);
   md5_finish_ctx (&ctx, checksum);
-  htab_delete (ht);
+  ht.dispose ();
   for (cnt = 0; cnt < 16; ++cnt)
     fprintf (stderr, "%02x", checksum[cnt]);
   putc ('\n', stderr);
@@ -14379,9 +14380,10 @@  fold_check_failed (const_tree expr ATTRI
 }

 static void
-fold_checksum_tree (const_tree expr, struct md5_ctx *ctx, htab_t ht)
+fold_checksum_tree (const_tree expr, struct md5_ctx *ctx,
+		    hash_table <pointer_hash <tree_node> > ht)
 {
-  void **slot;
+  tree_node **slot;
   enum tree_code code;
   union tree_node buf;
   int i, len;
@@ -14389,7 +14391,7 @@  fold_checksum_tree (const_tree expr, str
  recursive_label:
   if (expr == NULL)
     return;
-  slot = (void **) htab_find_slot (ht, expr, INSERT);
+  slot = ht.find_slot (expr, INSERT);
   if (*slot != NULL)
     return;
   *slot = CONST_CAST_TREE (expr);
@@ -14538,12 +14540,13 @@  debug_fold_checksum (const_tree t)
   int i;
   unsigned char checksum[16];
   struct md5_ctx ctx;
-  htab_t ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  hash_table <pointer_hash <tree_node> > ht;
+  ht.create (32);

   md5_init_ctx (&ctx);
   fold_checksum_tree (t, &ctx, ht);
   md5_finish_ctx (&ctx, checksum);
-  htab_empty (ht);
+  ht.empty ();

   for (i = 0; i < 16; i++)
     fprintf (stderr, "%d ", checksum[i]);
@@ -14566,13 +14569,13 @@  fold_build1_stat_loc (location_t loc,
 #ifdef ENABLE_FOLD_CHECKING
   unsigned char checksum_before[16], checksum_after[16];
   struct md5_ctx ctx;
-  htab_t ht;
+  hash_table <pointer_hash <tree_node> > ht;

-  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  ht.create (32);
   md5_init_ctx (&ctx);
   fold_checksum_tree (op0, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before);
-  htab_empty (ht);
+  ht.empty ();
 #endif

   tem = fold_unary_loc (loc, code, type, op0);
@@ -14583,7 +14586,7 @@  fold_build1_stat_loc (location_t loc,
   md5_init_ctx (&ctx);
   fold_checksum_tree (op0, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after);
-  htab_delete (ht);
+  ht.dispose ();

   if (memcmp (checksum_before, checksum_after, 16))
     fold_check_failed (op0, tem);
@@ -14609,18 +14612,18 @@  fold_build2_stat_loc (location_t loc,
 		checksum_after_op0[16],
 		checksum_after_op1[16];
   struct md5_ctx ctx;
-  htab_t ht;
+  hash_table <pointer_hash <tree_node> > ht;

-  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  ht.create (32);
   md5_init_ctx (&ctx);
   fold_checksum_tree (op0, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_op0);
-  htab_empty (ht);
+  ht.empty ();

   md5_init_ctx (&ctx);
   fold_checksum_tree (op1, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_op1);
-  htab_empty (ht);
+  ht.empty ();
 #endif

   tem = fold_binary_loc (loc, code, type, op0, op1);
@@ -14631,7 +14634,7 @@  fold_build2_stat_loc (location_t loc,
   md5_init_ctx (&ctx);
   fold_checksum_tree (op0, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_op0);
-  htab_empty (ht);
+  ht.empty ();

   if (memcmp (checksum_before_op0, checksum_after_op0, 16))
     fold_check_failed (op0, tem);
@@ -14639,7 +14642,7 @@  fold_build2_stat_loc (location_t loc,
   md5_init_ctx (&ctx);
   fold_checksum_tree (op1, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_op1);
-  htab_delete (ht);
+  ht.dispose ();

   if (memcmp (checksum_before_op1, checksum_after_op1, 16))
     fold_check_failed (op1, tem);
@@ -14665,23 +14668,23 @@  fold_build3_stat_loc (location_t loc, en
 		checksum_after_op1[16],
 		checksum_after_op2[16];
   struct md5_ctx ctx;
-  htab_t ht;
+  hash_table <pointer_hash <tree_node> > ht;

-  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  ht.create (32);
   md5_init_ctx (&ctx);
   fold_checksum_tree (op0, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_op0);
-  htab_empty (ht);
+  ht.empty ();

   md5_init_ctx (&ctx);
   fold_checksum_tree (op1, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_op1);
-  htab_empty (ht);
+  ht.empty ();

   md5_init_ctx (&ctx);
   fold_checksum_tree (op2, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_op2);
-  htab_empty (ht);
+  ht.empty ();
 #endif

   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
@@ -14693,7 +14696,7 @@  fold_build3_stat_loc (location_t loc, en
   md5_init_ctx (&ctx);
   fold_checksum_tree (op0, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_op0);
-  htab_empty (ht);
+  ht.empty ();

   if (memcmp (checksum_before_op0, checksum_after_op0, 16))
     fold_check_failed (op0, tem);
@@ -14701,7 +14704,7 @@  fold_build3_stat_loc (location_t loc, en
   md5_init_ctx (&ctx);
   fold_checksum_tree (op1, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_op1);
-  htab_empty (ht);
+  ht.empty ();

   if (memcmp (checksum_before_op1, checksum_after_op1, 16))
     fold_check_failed (op1, tem);
@@ -14709,7 +14712,7 @@  fold_build3_stat_loc (location_t loc, en
   md5_init_ctx (&ctx);
   fold_checksum_tree (op2, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_op2);
-  htab_delete (ht);
+  ht.dispose ();

   if (memcmp (checksum_before_op2, checksum_after_op2, 16))
     fold_check_failed (op2, tem);
@@ -14733,20 +14736,20 @@  fold_build_call_array_loc (location_t lo
 		checksum_after_fn[16],
 		checksum_after_arglist[16];
   struct md5_ctx ctx;
-  htab_t ht;
+  hash_table <pointer_hash <tree_node> > ht;
   int i;

-  ht = htab_create (32, htab_hash_pointer, htab_eq_pointer, NULL);
+  ht.create (32);
   md5_init_ctx (&ctx);
   fold_checksum_tree (fn, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_fn);
-  htab_empty (ht);
+  ht.empty ();

   md5_init_ctx (&ctx);
   for (i = 0; i < nargs; i++)
     fold_checksum_tree (argarray[i], &ctx, ht);
   md5_finish_ctx (&ctx, checksum_before_arglist);
-  htab_empty (ht);
+  ht.empty ();
 #endif

   tem = fold_builtin_call_array (loc, type, fn, nargs, argarray);
@@ -14755,7 +14758,7 @@  fold_build_call_array_loc (location_t lo
   md5_init_ctx (&ctx);
   fold_checksum_tree (fn, &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_fn);
-  htab_empty (ht);
+  ht.empty ();

   if (memcmp (checksum_before_fn, checksum_after_fn, 16))
     fold_check_failed (fn, tem);
@@ -14764,7 +14767,7 @@  fold_build_call_array_loc (location_t lo
   for (i = 0; i < nargs; i++)
     fold_checksum_tree (argarray[i], &ctx, ht);
   md5_finish_ctx (&ctx, checksum_after_arglist);
-  htab_delete (ht);
+  ht.dispose ();

   if (memcmp (checksum_before_arglist, checksum_after_arglist, 16))
     fold_check_failed (NULL_TREE, tem);
Index: gcc/objc/Make-lang.in
===================================================================
--- gcc/objc/Make-lang.in	(revision 191941)
+++ gcc/objc/Make-lang.in	(working copy)
@@ -50,7 +50,7 @@  START_HDRS = $(CONFIG_H) $(SYSTEM_H) cor
 objc-warn = $(STRICT_WARN)

 # Language-specific object files for Objective C.
-OBJC_OBJS = objc/objc-lang.o objc/objc-act.o \
+OBJC_OBJS = objc/objc-lang.o objc/objc-act.o hash-table.o \
    objc/objc-runtime-shared-support.o \
    objc/objc-gnu-runtime-abi-01.o \
    objc/objc-next-runtime-abi-01.o \
@@ -127,7 +127,7 @@  objc/objc-act.o : objc/objc-act.c \
    $(START_HDRS) \
    $(GGC_H) $(DIAGNOSTIC_CORE_H) $(FLAGS_H) input.h \
    toplev.h $(FUNCTION_H) debug.h $(LANGHOOKS_DEF_H) \
-   $(HASHTAB_H) $(GIMPLE_H) \
+   $(HASH_TABLE_H) $(GIMPLE_H) \
    $(C_PRAGMA_H) $(C_TARGET_H) \
    objc/objc-encoding.h \
    objc/objc-map.h \
Index: gcc/objc/objc-act.c
===================================================================
--- gcc/objc/objc-act.c	(revision 191941)
+++ gcc/objc/objc-act.c	(working copy)
@@ -51,7 +51,7 @@  along with GCC; see the file COPYING3.
 #include "intl.h"
 #include "cgraph.h"
 #include "tree-iterator.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "langhooks-def.h"
 /* Different initialization, code gen and meta data generation for each
    runtime.  */
@@ -3824,18 +3824,23 @@  objc_get_class_ivars (tree class_name)
    allows us to store keys in the hashtable, without values (it looks
    more like a set).  So, we store the DECLs, but define equality as
    DECLs having the same name, and hash as the hash of the name.  */
-static hashval_t
-hash_instance_variable (const PTR p)
+
+struct decl_name_hash : typed_noop_remove <tree_node>
+{
+  typedef tree_node T;
+  static inline hashval_t hash (const T *);
+  static inline bool equal (const T *, const T *);
+};
+
+inline hashval_t
+decl_name_hash::hash (const T *q)
 {
-  const_tree q = (const_tree)p;
   return (hashval_t) ((intptr_t)(DECL_NAME (q)) >> 3);
 }

-static int
-eq_instance_variable (const PTR p1, const PTR p2)
+inline bool
+decl_name_hash::equal (const T *a, const T *b)
 {
-  const_tree a = (const_tree)p1;
-  const_tree b = (const_tree)p2;
   return DECL_NAME (a) == DECL_NAME (b);
 }

@@ -3916,8 +3921,8 @@  objc_detect_field_duplicates (bool check
 	  {
 	    /* First, build the hashtable by putting all the instance
 	       variables of superclasses in it.  */
-	    htab_t htab = htab_create (37, hash_instance_variable,
-				       eq_instance_variable, NULL);
+	    hash_table <decl_name_hash> htab;
+	    htab.create (37);
 	    tree interface;
 	    for (interface = lookup_interface (CLASS_SUPER_NAME
 					       (objc_interface_context));
@@ -3930,7 +3935,7 @@  objc_detect_field_duplicates (bool check
 		  {
 		    if (DECL_NAME (ivar) != NULL_TREE)
 		      {
-			void **slot = htab_find_slot (htab, ivar, INSERT);
+			tree_node **slot = htab.find_slot (ivar, INSERT);
 			/* Do not check for duplicate instance
 			   variables in superclasses.  Errors have
 			   already been generated.  */
@@ -3950,7 +3955,7 @@  objc_detect_field_duplicates (bool check
 		  {
 		    if (DECL_NAME (ivar) != NULL_TREE)
 		      {
-			tree duplicate_ivar = (tree)(htab_find (htab, ivar));
+			tree duplicate_ivar = htab.find (ivar);
 			if (duplicate_ivar != HTAB_EMPTY_ENTRY)
 			  {
 			    error_at (DECL_SOURCE_LOCATION (ivar),
@@ -3977,7 +3982,7 @@  objc_detect_field_duplicates (bool check
 		  {
 		    if (DECL_NAME (ivar) != NULL_TREE)
 		      {
-			void **slot = htab_find_slot (htab, ivar, INSERT);
+			tree_node **slot = htab.find_slot (ivar, INSERT);
 			if (*slot)
 			  {
 			    tree duplicate_ivar = (tree)(*slot);
@@ -3994,7 +3999,7 @@  objc_detect_field_duplicates (bool check
 		      }
 		  }
 	      }
-	    htab_delete (htab);
+	    htab.dispose ();
 	    return true;
 	  }
       }
Index: gcc/cfg.c
===================================================================
--- gcc/cfg.c	(revision 191941)
+++ gcc/cfg.c	(working copy)
@@ -53,7 +53,7 @@  along with GCC; see the file COPYING3.
 #include "coretypes.h"
 #include "obstack.h"
 #include "ggc.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "alloc-pool.h"
 #include "tree.h"
 #include "basic-block.h"
@@ -976,14 +976,7 @@  scale_bbs_frequencies_gcov_type (basic_b
       }
 }

-/* Data structures used to maintain mapping between basic blocks and
-   copies.  */
-static htab_t bb_original;
-static htab_t bb_copy;
-
-/* And between loops and copies.  */
-static htab_t loop_copy;
-static alloc_pool original_copy_bb_pool;
+/* Helper types for hash tables.  */

 struct htab_bb_copy_original_entry
 {
@@ -993,25 +986,35 @@  struct htab_bb_copy_original_entry
   int index2;
 };

-static hashval_t
-bb_copy_original_hash (const void *p)
+struct bb_copy_hasher : typed_noop_remove <htab_bb_copy_original_entry>
 {
-  const struct htab_bb_copy_original_entry *data
-    = ((const struct htab_bb_copy_original_entry *)p);
+  typedef htab_bb_copy_original_entry T;
+  static inline hashval_t hash (const T *);
+  static inline bool equal (const T *existing, const T * candidate);
+};

+inline hashval_t
+bb_copy_hasher::hash (const T *data)
+{
   return data->index1;
 }
-static int
-bb_copy_original_eq (const void *p, const void *q)
-{
-  const struct htab_bb_copy_original_entry *data
-    = ((const struct htab_bb_copy_original_entry *)p);
-  const struct htab_bb_copy_original_entry *data2
-    = ((const struct htab_bb_copy_original_entry *)q);

+inline bool
+bb_copy_hasher::equal (const T *data, const T *data2)
+{
   return data->index1 == data2->index1;
 }

+/* Data structures used to maintain mapping between basic blocks and
+   copies.  */
+static hash_table <bb_copy_hasher> bb_original;
+static hash_table <bb_copy_hasher> bb_copy;
+
+/* And between loops and copies.  */
+static hash_table <bb_copy_hasher> loop_copy;
+static alloc_pool original_copy_bb_pool;
+
+
 /* Initialize the data structures to maintain mapping between blocks
    and its copies.  */
 void
@@ -1021,10 +1024,9 @@  initialize_original_copy_tables (void)
   original_copy_bb_pool
     = create_alloc_pool ("original_copy",
 			 sizeof (struct htab_bb_copy_original_entry), 10);
-  bb_original = htab_create (10, bb_copy_original_hash,
-			     bb_copy_original_eq, NULL);
-  bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
-  loop_copy = htab_create (10, bb_copy_original_hash,
bb_copy_original_eq, NULL);
+  bb_original.create (10);
+  bb_copy.create (10);
+  loop_copy.create (10);
 }

 /* Free the data structures to maintain mapping between blocks and
@@ -1033,34 +1035,31 @@  void
 free_original_copy_tables (void)
 {
   gcc_assert (original_copy_bb_pool);
-  htab_delete (bb_copy);
-  htab_delete (bb_original);
-  htab_delete (loop_copy);
+  bb_copy.dispose ();
+  bb_original.dispose ();
+  loop_copy.dispose ();
   free_alloc_pool (original_copy_bb_pool);
-  bb_copy = NULL;
-  bb_original = NULL;
-  loop_copy = NULL;
   original_copy_bb_pool = NULL;
 }

 /* Removes the value associated with OBJ from table TAB.  */

 static void
-copy_original_table_clear (htab_t tab, unsigned obj)
+copy_original_table_clear (hash_table <bb_copy_hasher> tab, unsigned obj)
 {
-  void **slot;
+  htab_bb_copy_original_entry **slot;
   struct htab_bb_copy_original_entry key, *elt;

   if (!original_copy_bb_pool)
     return;

   key.index1 = obj;
-  slot = htab_find_slot (tab, &key, NO_INSERT);
+  slot = tab.find_slot (&key, NO_INSERT);
   if (!slot)
     return;

-  elt = (struct htab_bb_copy_original_entry *) *slot;
-  htab_clear_slot (tab, slot);
+  elt = *slot;
+  tab.clear_slot (slot);
   pool_free (original_copy_bb_pool, elt);
 }

@@ -1068,7 +1067,8 @@  copy_original_table_clear (htab_t tab, u
    Do nothing when data structures are not initialized.  */

 static void
-copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
+copy_original_table_set (hash_table <bb_copy_hasher> tab,
+			 unsigned obj, unsigned val)
 {
   struct htab_bb_copy_original_entry **slot;
   struct htab_bb_copy_original_entry key;
@@ -1077,8 +1077,7 @@  copy_original_table_set (htab_t tab, uns
     return;

   key.index1 = obj;
-  slot = (struct htab_bb_copy_original_entry **)
-		htab_find_slot (tab, &key, INSERT);
+  slot = tab.find_slot (&key, INSERT);
   if (!*slot)
     {
       *slot = (struct htab_bb_copy_original_entry *)
@@ -1106,7 +1105,7 @@  get_bb_original (basic_block bb)
   gcc_assert (original_copy_bb_pool);

   key.index1 = bb->index;
-  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
+  entry = bb_original.find (&key);
   if (entry)
     return BASIC_BLOCK (entry->index2);
   else
@@ -1131,7 +1130,7 @@  get_bb_copy (basic_block bb)
   gcc_assert (original_copy_bb_pool);

   key.index1 = bb->index;
-  entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
+  entry = bb_copy.find (&key);
   if (entry)
     return BASIC_BLOCK (entry->index2);
   else
@@ -1161,7 +1160,7 @@  get_loop_copy (struct loop *loop)
   gcc_assert (original_copy_bb_pool);

   key.index1 = loop->num;
-  entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
+  entry = loop_copy.find (&key);
   if (entry)
     return get_loop (entry->index2);
   else
Index: gcc/cp/class.c
===================================================================
--- gcc/cp/class.c	(revision 191941)
+++ gcc/cp/class.c	(working copy)
@@ -38,6 +38,7 @@  along with GCC; see the file COPYING3.
 #include "dumpfile.h"
 #include "splay-tree.h"
 #include "pointer-set.h"
+#include "hash-table.h"

 /* The number of nested classes being processed.  If we are not in the
    scope of any class, this is zero.  */
@@ -6465,12 +6466,9 @@  fixed_type_or_null (tree instance, int *
       else if (TREE_CODE (TREE_TYPE (instance)) == REFERENCE_TYPE)
 	{
 	  /* We only need one hash table because it is always left empty.  */
-	  static htab_t ht;
-	  if (!ht)
-	    ht = htab_create (37,
-			      htab_hash_pointer,
-			      htab_eq_pointer,
-			      /*htab_del=*/NULL);
+	  static hash_table <pointer_hash <tree_node> > ht;
+	  if (!ht.is_created ())
+	    ht.create (37);

 	  /* Reference variables should be references to objects.  */
 	  if (nonnull)
@@ -6482,15 +6480,15 @@  fixed_type_or_null (tree instance, int *
 	  if (TREE_CODE (instance) == VAR_DECL
 	      && DECL_INITIAL (instance)
 	      && !type_dependent_expression_p_push (DECL_INITIAL (instance))
-	      && !htab_find (ht, instance))
+	      && !ht.find (instance))
 	    {
 	      tree type;
-	      void **slot;
+	      tree_node **slot;

-	      slot = htab_find_slot (ht, instance, INSERT);
+	      slot = ht.find_slot (instance, INSERT);
 	      *slot = instance;
 	      type = RECUR (DECL_INITIAL (instance));
-	      htab_remove_elt (ht, instance);
+	      ht.remove_elt (instance);

 	      return type;
 	    }
Index: gcc/cp/Make-lang.in
===================================================================
--- gcc/cp/Make-lang.in	(revision 191941)
+++ gcc/cp/Make-lang.in	(working copy)
@@ -293,7 +293,7 @@  cp/typeck.o: cp/typeck.c $(CXX_TREE_H) $
   c-family/c-objc.h
 cp/class.o: cp/class.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
   $(TARGET_H) convert.h $(CGRAPH_H) dumpfile.h gt-cp-class.h \
-  $(SPLAY_TREE_H) pointer-set.h
+  $(SPLAY_TREE_H) pointer-set.h $(HASH_TABLE_H)
 cp/call.o: cp/call.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
   $(DIAGNOSTIC_CORE_H) intl.h gt-cp-call.h convert.h $(TARGET_H) langhooks.h \
   $(TIMEVAR_H) c-family/c-objc.h
@@ -309,7 +309,7 @@  cp/search.o: cp/search.c $(CXX_TREE_H) $
   intl.h
 cp/tree.o: cp/tree.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) \
   $(TREE_INLINE_H) $(REAL_H) gt-cp-tree.h \
-  $(TARGET_H) debug.h $(CGRAPH_H) $(SPLAY_TREE_H) $(GIMPLE_H)
+  $(TARGET_H) debug.h $(CGRAPH_H) $(SPLAY_TREE_H) $(GIMPLE_H) $(HASH_TABLE_H)
 cp/ptree.o: cp/ptree.c $(CXX_TREE_H) $(TM_H)
 cp/rtti.o: cp/rtti.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) convert.h \
   $(TARGET_H) $(C_PRAGMA_H) gt-cp-rtti.h intl.h
@@ -327,7 +327,7 @@  cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_
 cp/semantics.o: cp/semantics.c $(CXX_TREE_H) $(TM_H) toplev.h \
   $(FLAGS_H) $(RTL_H) $(TIMEVAR_H) \
   $(TREE_INLINE_H) $(CGRAPH_H) $(TARGET_H) $(C_COMMON_H) $(GIMPLE_H) \
-  bitmap.h gt-cp-semantics.h c-family/c-objc.h
+  bitmap.h gt-cp-semantics.h c-family/c-objc.h $(HASH_TABLE_H)
 cp/dump.o: cp/dump.c $(CXX_TREE_H) $(TM_H) $(TREE_DUMP_H)
 cp/optimize.o: cp/optimize.c $(CXX_TREE_H) $(TM_H) \
   input.h $(PARAMS_H) debug.h $(TREE_INLINE_H) $(GIMPLE_H) \
Index: gcc/cp/tree.c
===================================================================
--- gcc/cp/tree.c	(revision 191941)
+++ gcc/cp/tree.c	(working copy)
@@ -34,6 +34,7 @@  along with GCC; see the file COPYING3.
 #include "cgraph.h"
 #include "splay-tree.h"
 #include "gimple.h" /* gimple_has_body_p */
+#include "hash-table.h"

 static tree bot_manip (tree *, int *, void *);
 static tree bot_replace (tree *, int *, void *);
@@ -1918,17 +1919,18 @@  static tree
 verify_stmt_tree_r (tree* tp, int * /*walk_subtrees*/, void* data)
 {
   tree t = *tp;
-  htab_t *statements = (htab_t *) data;
-  void **slot;
+  hash_table <pointer_hash <tree_node> > *statements
+      = static_cast <hash_table <pointer_hash <tree_node> > *> (data);
+  tree_node **slot;

   if (!STATEMENT_CODE_P (TREE_CODE (t)))
     return NULL_TREE;

   /* If this statement is already present in the hash table, then
      there is a circularity in the statement tree.  */
-  gcc_assert (!htab_find (*statements, t));
+  gcc_assert (!statements->find (t));

-  slot = htab_find_slot (*statements, t, INSERT);
+  slot = statements->find_slot (t, INSERT);
   *slot = t;

   return NULL_TREE;
@@ -1941,10 +1943,10 @@  verify_stmt_tree_r (tree* tp, int * /*wa
 void
 verify_stmt_tree (tree t)
 {
-  htab_t statements;
-  statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+  hash_table <pointer_hash <tree_node> > statements;
+  statements.create (37);
   cp_walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
-  htab_delete (statements);
+  statements.dispose ();
 }

 /* Check if the type T depends on a type with no linkage and if so, return
Index: gcc/cp/semantics.c
===================================================================
--- gcc/cp/semantics.c	(revision 191941)
+++ gcc/cp/semantics.c	(working copy)
@@ -44,6 +44,7 @@  along with GCC; see the file COPYING3.
 #include "target.h"
 #include "gimple.h"
 #include "bitmap.h"
+#include "hash-table.h"

 /* There routines provide a modular interface to perform many parsing
    operations.  They may therefore be used during actual parsing, or
@@ -3811,7 +3812,7 @@  struct nrv_data
 {
   tree var;
   tree result;
-  htab_t visited;
+  hash_table <pointer_hash <tree_node> > visited;
 };

 /* Helper function for walk_tree, used by finalize_nrv below.  */
@@ -3820,7 +3821,7 @@  static tree
 finalize_nrv_r (tree* tp, int* walk_subtrees, void* data)
 {
   struct nrv_data *dp = (struct nrv_data *)data;
-  void **slot;
+  tree_node **slot;

   /* No need to walk into types.  There wouldn't be any need to walk into
      non-statements, except that we have to consider STMT_EXPRs.  */
@@ -3859,7 +3860,7 @@  finalize_nrv_r (tree* tp, int* walk_subt
   /* Avoid walking into the same tree more than once.  Unfortunately, we
      can't just use walk_tree_without duplicates because it would only call
      us for the first occurrence of dp->var in the function body.  */
-  slot = htab_find_slot (dp->visited, *tp, INSERT);
+  slot = dp->visited.find_slot (*tp, INSERT);
   if (*slot)
     *walk_subtrees = 0;
   else
@@ -3891,9 +3892,9 @@  finalize_nrv (tree *tp, tree var, tree r

   data.var = var;
   data.result = result;
-  data.visited = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+  data.visited.create (37);
   cp_walk_tree (tp, finalize_nrv_r, &data, 0);
-  htab_delete (data.visited);
+  data.visited.dispose ();
 }
 
 /* Create CP_OMP_CLAUSE_INFO for clause C.  Returns true if it is invalid.  */
Index: gcc/hash-table.h
===================================================================
--- gcc/hash-table.h	(revision 191941)
+++ gcc/hash-table.h	(working copy)
@@ -223,15 +223,15 @@  public:
   void create (size_t initial_slots);
   bool is_created ();
   void dispose ();
-  T *find (T *comparable);
-  T *find_with_hash (T *comparable, hashval_t hash);
-  T **find_slot (T *comparable, enum insert_option insert);
-  T **find_slot_with_hash (T *comparable, hashval_t hash,
+  T *find (const T *comparable);
+  T *find_with_hash (const T *comparable, hashval_t hash);
+  T **find_slot (const T *comparable, enum insert_option insert);
+  T **find_slot_with_hash (const T *comparable, hashval_t hash,
 				   enum insert_option insert);
   void empty ();
   void clear_slot (T **slot);
-  void remove_elt (T *comparable);
-  void remove_elt_with_hash (T *comparable, hashval_t hash);
+  void remove_elt (const T *comparable);
+  void remove_elt_with_hash (const T *comparable, hashval_t hash);
   size_t size();
   size_t elements();
   double collisions();
@@ -273,7 +273,7 @@  hash_table <Descr, Allocator>::is_create
 template <typename Descr,
 	  template <typename Type> class Allocator>
 inline typename Descr::T *
-hash_table <Descr, Allocator>::find (T *comparable)
+hash_table <Descr, Allocator>::find (const T *comparable)
 {
   return find_with_hash (comparable, Descr::hash (comparable));
 }
@@ -285,7 +285,7 @@  template <typename Descr,
 	  template <typename Type> class Allocator>
 inline typename Descr::T **
 hash_table <Descr, Allocator>
-::find_slot (T *comparable, enum insert_option insert)
+::find_slot (const T *comparable, enum insert_option insert)
 {
   return find_slot_with_hash (comparable, Descr::hash (comparable), insert);
 }
@@ -297,7 +297,7 @@  template <typename Descr,
 	  template <typename Type> class Allocator>
 inline void
 hash_table <Descr, Allocator>
-::remove_elt (T *comparable)
+::remove_elt (const T *comparable)
 {
   remove_elt_with_hash (comparable, Descr::hash (comparable));
 }
@@ -495,7 +495,7 @@  template <typename Descr,
 	  template <typename Type> class Allocator>
 typename Descr::T *
 hash_table <Descr, Allocator>
-::find_with_hash (T *comparable, hashval_t hash)
+::find_with_hash (const T *comparable, hashval_t hash)
 {
   hashval_t index, hash2;
   size_t size;
@@ -538,7 +538,7 @@  template <typename Descr,
 	  template <typename Type> class Allocator>
 typename Descr::T **
 hash_table <Descr, Allocator>
-::find_slot_with_hash (T *comparable, hashval_t hash,
+::find_slot_with_hash (const T *comparable, hashval_t hash,
 		       enum insert_option insert)
 {
   T **first_deleted_slot;
@@ -609,7 +609,7 @@  template <typename Descr,
 void
 hash_table <Descr, Allocator>::empty ()
 {
-  size_t size = htab_size (htab);
+  size_t size = htab->size;
   T **entries = htab->entries;
   int i;

@@ -651,7 +651,7 @@  hash_table <Descr, Allocator>

   Descr::remove (*slot);

-  *slot = HTAB_DELETED_ENTRY;
+  *slot = static_cast <T *> (HTAB_DELETED_ENTRY);
   htab->n_deleted++;
 }

@@ -664,7 +664,7 @@  template <typename Descr,
 	  template <typename Type> class Allocator>
 void
 hash_table <Descr, Allocator>
-::remove_elt_with_hash (T *comparable, hashval_t hash)
+::remove_elt_with_hash (const T *comparable, hashval_t hash)
 {
   T **slot;

Index: gcc/dse.c
===================================================================
--- gcc/dse.c	(revision 191941)
+++ gcc/dse.c	(working copy)
@@ -26,7 +26,7 @@  along with GCC; see the file COPYING3.
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "tm.h"
 #include "rtl.h"
 #include "tree.h"
@@ -547,9 +547,6 @@  typedef struct group_info *group_info_t;
 typedef const struct group_info *const_group_info_t;
 static alloc_pool rtx_group_info_pool;

-/* Tables of group_info structures, hashed by base value.  */
-static htab_t rtx_group_table;
-
 /* Index into the rtx_group_vec.  */
 static int rtx_group_next_id;

@@ -655,23 +652,29 @@  clear_alias_set_lookup (alias_set_type a
 /* Hashtable callbacks for maintaining the "bases" field of
    store_group_info, given that the addresses are function invariants.  */

-static int
-invariant_group_base_eq (const void *p1, const void *p2)
+struct invariant_group_base_hasher : typed_noop_remove <group_info>
+{
+  typedef group_info T;
+  static inline hashval_t hash (const T *);
+  static inline bool equal (const T *, const T *);
+};
+
+inline bool
+invariant_group_base_hasher::equal (const T *gi1, const T *gi2)
 {
-  const_group_info_t gi1 = (const_group_info_t) p1;
-  const_group_info_t gi2 = (const_group_info_t) p2;
   return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
 }

-
-static hashval_t
-invariant_group_base_hash (const void *p)
+inline hashval_t
+invariant_group_base_hasher::hash (const T *gi)
 {
-  const_group_info_t gi = (const_group_info_t) p;
   int do_not_record;
   return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
 }

+/* Tables of group_info structures, hashed by base value.  */
+static hash_table <invariant_group_base_hasher> rtx_group_table;
+

 /* Get the GROUP for BASE.  Add a new group if it is not there.  */

@@ -680,14 +683,14 @@  get_group_info (rtx base)
 {
   struct group_info tmp_gi;
   group_info_t gi;
-  void **slot;
+  group_info **slot;

   if (base)
     {
       /* Find the store_base_info structure for BASE, creating a new one
 	 if necessary.  */
       tmp_gi.rtx_base = base;
-      slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
+      slot = rtx_group_table.find_slot (&tmp_gi, INSERT);
       gi = (group_info_t) *slot;
     }
   else
@@ -777,8 +780,7 @@  dse_step0 (void)
     = create_alloc_pool ("deferred_change_pool",
 			 sizeof (struct deferred_change), 10);

-  rtx_group_table = htab_create (11, invariant_group_base_hash,
-				 invariant_group_base_eq, NULL);
+  rtx_group_table.create (11);

   bb_table = XNEWVEC (bb_info_t, last_basic_block);
   rtx_group_next_id = 0;
@@ -2872,7 +2874,7 @@  dse_step1 (void)

   BITMAP_FREE (regs_live);
   cselib_finish ();
-  htab_empty (rtx_group_table);
+  rtx_group_table.empty ();
 }

 
@@ -3812,7 +3814,7 @@  dse_step7 (void)

   end_alias_analysis ();
   free (bb_table);
-  htab_delete (rtx_group_table);
+  rtx_group_table.dispose ();
   VEC_free (group_info_t, heap, rtx_group_vec);
   BITMAP_FREE (all_blocks);
   BITMAP_FREE (scratch);
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 191941)
+++ gcc/Makefile.in	(working copy)
@@ -2616,8 +2616,8 @@  tree-diagnostic.o : tree-diagnostic.c $(
    $(TREE_H) $(DIAGNOSTIC_H) tree-diagnostic.h langhooks.h $(LANGHOOKS_DEF_H) \
    $(VEC_H) $(TREE_PRETTY_PRINT_H)
 fold-const.o : fold-const.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
-   $(TREE_H) $(FLAGS_H) $(DIAGNOSTIC_CORE_H) $(HASHTAB_H) $(EXPR_H) $(RTL_H) \
-   $(GGC_H) $(TM_P_H) langhooks.h $(MD5_H) intl.h $(TARGET_H) \
+   $(TREE_H) $(FLAGS_H) $(DIAGNOSTIC_CORE_H) $(HASH_TABLE_H) $(EXPR_H) \
+   $(RTL_H) $(GGC_H) $(TM_P_H) langhooks.h $(MD5_H) intl.h $(TARGET_H) \
    $(GIMPLE_H) realmpfr.h $(TREE_FLOW_H)
 diagnostic.o : diagnostic.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    version.h $(DEMANGLE_H) $(INPUT_H) intl.h $(BACKTRACE_H) $(DIAGNOSTIC_H) \
@@ -2929,7 +2929,7 @@  dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) co
    $(TREE_H) $(TM_P_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
    $(RECOG_H) $(EXPR_H) $(DF_H) cselib.h $(DBGCNT_H) \
    $(TREE_PASS_H) alloc-pool.h $(ALIAS_H) $(OPTABS_H) $(TARGET_H) \
-   $(BITMAP_H) $(PARAMS_H) $(TREE_FLOW_H)
+   $(BITMAP_H) $(PARAMS_H) $(TREE_FLOW_H) $(HASH_TABLE_H)
 fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(DIAGNOSTIC_CORE_H) insn-config.h $(RECOG_H) $(FLAGS_H)
$(OBSTACK_H) $(BASIC_BLOCK_H) \