backport: As described in http://gcc.gnu.org/ml/gcc/2012-08/msg00015.html...

Merge from cxx-conversion branch (http://gcc.gnu.org/wiki/cxx-conversion).

As described in http://gcc.gnu.org/ml/gcc/2012-08/msg00015.html, this patch
changes the default bootstrap process so that stage 1 always builds with a C++
compiler.

Other than the bootstrap change, the patch makes no functional changes to the
compiler.  Everything should build as it does now in trunk.  The main
changes in this patch are:

1- Configuration changes.
2- Re-write of VEC.
3- Re-write of gengtype to support C++ templates and
   user-provided marking functions.
4- New hash table class.
5- Re-write double_int.
6- Implement tree macros as inline functions so they can be
   called from gdb.

As discussed before, several of these changes do not fully change
the call sites to use the new APIs.

The bootstrap changes have already been tested on a wide range of
targets (http://gcc.gnu.org/wiki/CppBuildStatus).  Additionally,
I have tested the merged trunk on: x86_64-unknown-linux-gnu,
mips64el-unknown-linux-gnu, powerpc64-unknown-linux-gnu,
i686-pc-linux-gnu, and ia64-unknown-linux-gnu.

ChangeLog
2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.

	* Makefile.tpl (STAGE[+id+]_CXXFLAGS): Remove
	POSTSTAGE1_CONFIGURE_FLAGS.
	* Makefile.in: Regenerate.
	* configure.ac (ENABLE_BUILD_WITH_CXX): Remove.  Update all users.
	Force C++ when bootstrapping.
	* configure: Regenerate.


libcpp/ChangeLog
2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.  Configury.

	* Makefile.in: Remove all handlers of ENABLE_BUILD_WITH_CXX.
	* configure.ac: Likewise.
	* configure: Regenerate.

2012-08-14   Lawrence Crowl  <crowl@google.com>

	Merge from cxx-conversion branch.  New C++ hash table.

	* include/symtab.h (typedef struct ht hash_table): Change the typedef
	name to cpp_hash_table.  Update all users of the typedef.

gcc/ChangeLog
2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.  Configury.

	* configure.ac (CXX_FOR_BUILD): Define and substitute.
	(BUILD_CXXFLAGS): Define.
	Remove all handlers of ENABLE_BUILD_WITH_CXX.
	Force all build to be with C++.
	* Makefile.in (BUILD_CXXFLAGS): Use it.
	Remove all handlers of ENABLE_BUILD_WITH_CXX.
	* configure: Regenerate.
	* config.in: Regenerate.
	* doc/install.texi: Remove documentation for --enable-build-with-cxx
	and --enable-build-poststage1-with-cxx.

2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.  Re-implement VEC in C++.

	* vec.c (vec_heap_free): Convert into a template function.
	(vec_gc_o_reserve_1): Make extern.
	(vec_gc_p_reserve): Remove.
	(vec_gc_p_reserve_exact): Remove.
	(vec_gc_o_reserve): Remove.
	(vec_gc_o_reserve_exact): Remove.
	(vec_heap_o_reserve_1): Make extern.
	(vec_heap_p_reserve): Remove.
	(vec_heap_p_reserve_exact): Remove.
	(vec_heap_o_reserve): Remove.
	(vec_heap_o_reserve_exact): Remove.
	(vec_stack_p_reserve): Remove.
	(vec_stack_p_reserve_exact): Remove.
	* vec.h (VEC_CHECK_INFO, VEC_CHECK_DECL, VEC_CHECK_PASS,
	VEC_ASSERT, VEC_ASSERT_FAIL, vec_assert_fail): Move earlier
	in the file.
	(VEC): Define to vec_t<T>.
	(vec_allocation_t): Define.
	(struct vec_prefix): Move earlier in the file.
	(vec_t<T>): New template.
	(DEF_VEC_I, DEF_VECL_ALLOC_I, DEF_VEC_P, DEF_VEC_ALLOC_P,
	DEF_VEC_O, DEF_VEC_ALLOC_P, DEF_VEC_O, DEF_VEC_ALLOC_O,
	DEF_VEC_ALLOC_P_STACK, DEF_VEC_ALLOC_O_STACK,
	DEF_VEC_ALLOC_I_STACK): Expand to 'struct vec_swallow_trailing_semi'.
	(DEF_VEC_A): Provide template instantiations for
	GC/PCH markers that do not traverse the vector.
	(vec_stack_p_reserve): Remove.
	(vec_stack_p_reserve_exact): Remove.
	(vec_stack_p_reserve_exact_1): Remove.
	(vec_stack_o_reserve): Remove.
	(vec_stack_o_reserve_exact): Remove.
	(vec_stack_free): Re-write as a template function.
	(vec_reserve): New template function.
	(vec_reserve_exact): New template function.
	(vec_heap_free): New template function if GATHER_STATISTICS is
	defined.  Otherwise, macro that expands to free().
	(VEC_length_1): New template function.
	(VEC_length): Call it.
	(VEC_empty_1): New template function.
	(VEC_empty): Call it.
	(VEC_address_1): New template function.
	(VEC_address): Call it.
	(VEC_last_1): New template function.
	(VEC_last): Call it.  Change return type to T&.
	Change all users that used VEC_Os.
	(VEC_index_1): New template function.
	(VEC_index): Call it.  Return a T& instead of a T*.
	Update all callers that were using VEC_O before.
	(VEC_iterate_1): New template function.
	(VEC_iterate): Call it.
	(VEC_embedded_size_1): New template function.
	(VEC_embedded_size): Call it.
	(VEC_embedded_init_1): New template function.
	(VEC_embedded_init): Call it.
	(VEC_alloc_1): New template function.
	(VEC_alloc): Call it.  If A is 'stack', call XALLOCAVAR to
	do the allocation.
	(VEC_free_1): New template function.
	(VEC_free): Call it.
	(VEC_copy_1): New template function.
	(VEC_copy): Call it.
	(VEC_space_1): New template function
	(VEC_space): Call it.
	(VEC_reserve_1): New template function.
	(VEC_reserve): Call it.
	(VEC_reserve_exact_1): New template function.
	(VEC_reserve_exact): Call it.
	(VEC_splice_1): New template function.
	(VEC_splice): Call it.
	(VEC_safe_splice_1): New template function.
	(VEC_safe_splice): Call it.
	(VEC_quick_push_1): New template function.  Create two overloads, one
	accepting T, the other accepting T *.  Update all callers
	where T and T * are ambiguous.
	(VEC_quick_push): Call it.
	(VEC_safe_push_1): New template function. Create two overloads, one
	accepting T, the other accepting T *.  Update all callers
	where T and T * are ambiguous.
	(VEC_safe_push): Call it.
	(VEC_pop_1): New template function.
	(VEC_pop): Call it.
	(VEC_truncate_1): New template function.
	(VEC_truncate): Call it.
	(VEC_safe_grow_1): New template function.
	(VEC_safe_grow): Call it.
	(VEC_safe_grow_cleared_1): New template function.
	(VEC_safe_grow_cleared): Call it.
	(VEC_replace_1): New template function.
	(VEC_replace): Call it.  Always accept T instead of T*.
	Update all callers that used VEC_Os.
	(VEC_quick_insert_1): New template function.
	(VEC_quick_insert): Call it.
	(VEC_safe_insert_1): New template function.
	(VEC_safe_insert): Call it.
	(VEC_ordered_remove_1): New template function.
	(VEC_ordered_remove): Call it.
	(VEC_unordered_remove_1): New template function.
	(VEC_unordered_remove): Call it.
	(VEC_block_remove_1): New template function.
	(VEC_block_remove): Call it.
	(VEC_lower_bound_1): New template function.
	(VEC_lower_bound): Call it.
	(VEC_OP): Remove.
	(DEF_VEC_FUNC_P): Remove.
	(DEF_VEC_ALLOC_FUNC_P): Remove.
	(DEF_VEC_NONALLOC_FUNCS_P): Remove.
	(DEF_VEC_FUNC_O): Remove.
	(DEF_VEC_ALLOC_FUNC_O): Remove.
	(DEF_VEC_NONALLOC_FUNCS_O): Remove.
	(DEF_VEC_ALLOC_FUNC_I): Remove.
	(DEF_VEC_NONALLOC_FUNCS_I): Remove.
	(DEF_VEC_ALLOC_FUNC_P_STACK): Remove.
	(DEF_VEC_ALLOC_FUNC_O_STACK): Remove.
	(DEF_VEC_ALLOC_FUNC_I_STACK): Remove.
	(vec_reserve_exact): New template function.

	* gengtype-lex.l (DEF_VEC_ALLOC_[IOP]/{EOID}): Remove.
	* gengtype-parse.c (token_names): Remove DEF_VEC_ALLOC_[IOP].
	(typedef_name): Emit vec_t<C1> instead of VEC_C1_C2.
	(def_vec_alloc): Remove.  Update all callers.
	* gengtype.c (filter_type_name): New.
	(output_mangled_typename): Call it.
	(write_func_for_structure): Likewise.
	(write_types): Likewise.
	(write_root): Likewise.
	(write_typed_alloc_def): Likewise.
	(note_def_vec): Emit vec_t<TYPE_NAME> instead of VEC_TYPE_NAME_base.
	(note_def_vec_alloc): Remove.
	* gengtype.h (note_def_vec_alloc): Remove.
	(DEFVEC_ALLOC): Remove token code.

	* df-scan.c (df_bb_verify): Remove call to df_free_collection_rec
	inside the insn traversal loop.
	* gimplify.c (gimplify_compound_lval): Rename STACK to EXPR_STACK.
	* ipa-inline.c (inline_small_functions): Rename HEAP to EDGE_HEAP.
	* reg-stack.c (stack): Rename to STACK_PTR.  Update all users.
	* tree-vrp.c (stack): Rename to EQUIV_STACK.  Update all users.

	* config/bfin/bfin.c (hwloop_optimize): Update some calls to
	VEC_* for vectors of non-pointers.
	* config/c6x/c6x.c (try_rename_operands): Likewise.
	(reshuffle_units): Likewise.
	* config/mips/mips.c (mips_multi_start): Likewise.
	(mips_multi_add): Likewise.
	(mips_multi_copy_insn): Likewise.
	(mips_multi_set_operand): Likewise.
	* hw-doloop.c (discover_loop): Likewise.
	(discover_loops): Likewise.
	(reorg_loops): Likewise.

2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.  C++ support in gengtype.

	* coretypes.h (gt_pointer_operator): Move from ...
	* ggc.h: ... here.
	* doc/gty.texi: Document support for C++ templates and
	user-provided markers.
	* gcc/gengtype-lex.l: Update copyright year.
	Remove support for recognizing DEF_VEC_O, DEF_VEC_P and
	DEFVEC_I.
	* gengtype-parse.c: Update copyright year.
	(token_names): Remove DEF_VEC_O, DEF_VEC_P and DEF_VEC_I.
	(require_template_declaration): New.
	(typedef_name): Call it.
	(type): Replace IS_UNION with KIND. Replace all users.
	(def_vec): Remove.  Update all users.
	* gengtype-state.c (type_lineloc): Handle TYPE_USER_STRUCT.
	(write_state_user_struct_type): New.
	(write_state_type): Call it.
	(read_state_user_struct_type): New.
	(read_state_type): Call it.
	* gengtype.c: Update copyright year.
	(dump_pair): Move declaration to the top.
	(dump_type): Likewise.
	(dump_type_list): Likewise.
	(dbgprint_count_type_at): Handle TYPE_USER_STRUCT.
	(create_user_defined_type): New.
	(resolve_typedef): Call it.
	(new_structure): Replace argument ISUNION with KIND.
	Change users to refer to KIND directly.
	Update all callers.
	(find_structure): Likewise.
	(set_gc_used_type): Handle TYPE_USER_STRUCT.
	(create_file): Update HDR to include new copyright year.
	(struct walk_type_data): Add field IN_PTR_FIELD.
	(output_mangled_typename): Handle TYPE_USER_STRUCT.
	(walk_type): Set D->IN_PTR_FIELD when walking a TYPE_POINTER.
	Clear it afterwards.
	Handle TYPE_USER_STRUCT.
	(write_types_process_field): Handle TYPE_USER_STRUCT.
	(get_type_specifier): Move earlier in the file.
	(write_type_decl): New.
	(write_marker_function_name): New.
	(write_user_func_for_structure_ptr): New.
	(write_user_func_for_structure_body): New.
	(write_user_marking_functions): New.
	(write_func_for_structure): Call write_marker_function_name
	and write_type_decl.
	Do not call walk_type for TYPE_USER_STRUCT. Emit a call to the user
	function directly.
	Call write_user_marking_functions on TYPE_USER_STRUCTs.
	(write_types_local_user_process_field): New.
	(write_pch_user_walking_for_structure_body): New.
	(write_pch_user_walking_functions): New.
	(write_types_local_process_field): Handle TYPE_USER_STRUCT.
	(write_local_func_for_structure): Do not call walk_type for
	TYPE_USER_STRUCT. Instead, emit the call to gt_pch_nx directly.
	Call write_pch_user_walking_functions for TYPE_USER_STRUCTs.
	(write_root): Handle TYPE_USER_STRUCT.
	(vec_prefix_type): Remove.  Update all users.
	(note_def_vec): Remove.  Update all users.
	(dump_typekind): Handle TYPE_USER_STRUCT.
	(dump_type): Initialize SEEN_TYPES, if needed.
	Handle TYPE_USER_STRUCT.
	(dump_everything): Do not initialize SEEN_TYPES.
	* gengtype.h: Update copyright year.
	(enum typekind): Add TYPE_USER_STRUCT.
	(union_or_struct_p): Rename from UNION_OR_STRUCT_P.
	Convert into function.
	Add an overload taking const_type_p.
	Update all callers.
	(new_structure): Change second field to type enum typekind.
	Update all users.
	(find_structure): Likewise.
	(note_def_vec): Remove.
	(DEFVEC_OP): Remove.
	(DEFVEC_I): Remove.
	* ggc-page.c (gt_ggc_mx): Add entry points for marking
	'const char *&', 'unsigned char *&' and 'unsigned char&'.
	* ggc-zone.c (gt_ggc_mx): Add entry points for marking
	'const char *&' and 'unsigned char *&'.
	* stringpool.c (gt_pch_nx): Add entry points for marking
	'const char *&', 'unsigned char *&' and 'unsigned char&'.
	Add an entry point for the overload taking arguments 'unsigned char
	*', 'gt_pointer_operator' and 'void *'.
	* vec.h (struct vec_prefix): Remove GTY marker.
	(struct vec_t): Remove GTY((length)) attribute from field 'vec'.
	(gt_ggc_mx (vec_t<T> *)): New template function.
	(gt_pch_nx (vec_t<T> *)): New template function.
	(gt_pch_nx (vec_t<T *> *, gt_pointer_operator, void *)): New template
	function.
	(gt_pch_nx (vec_t<T> *, gt_pointer_operator, void *)): New template
	function.

	* basic-block.h (struct edge_def): Mark GTY((user)).
	Remove all GTY markers from fields.
	(gt_ggc_mx): Declare.
	(gt_pch_nx): Declare.
	* tree-cfg.c (gt_ggc_mx): New.
	(gt_pch_nx): New.

	* gengtype-lex.l (USER_GTY): Add pattern for "user".
	* gengtype-parse.c (option): Handle USER_GTY.
	(opts_have): New.
	(type): Call it.
	If the keyword 'user' is used, do not walk the fields
	of the structure.
	* gengtype.h (USER_GTY): Add.
	* doc/gty.texi: Update.

2012-08-14   Lawrence Crowl  <crowl@google.com>

	Merge cxx-conversion branch.  Implement C++ hash table.

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

2012-08-14   Lawrence Crowl  <crowl@google.com>

	Merge from cxx-conversion branch.  Re-write double_int in C++.

	* hash-table.h
	(typedef double_int): Change to struct (POD).
	(double_int::make): New overloads for int to double-int conversion.
	(double_int::mask): New.
	(double_int::max_value): New.
	(double_int::min_value): New.
	(double_int::operator ++): New.
	(double_int::operator --): New.
	(double_int::operator *=): New.
	(double_int::operator +=): New.
	(double_int::operator -=): New.
	(double_int::to_signed): New.
	(double_int::to_unsigned): New.
	(double_int::fits_unsigned): New.
	(double_int::fits_signed): New.
	(double_int::fits): New.
	(double_int::trailing_zeros): New.
	(double_int::popcount): New.
	(double_int::multiple_of): New.
	(double_int::set_bit): New.
	(double_int::mul_with_sign): New.
	(double_int::operator * (binary)): New.
	(double_int::operator + (binary)): New.
	(double_int::operator - (binary)): New.
	(double_int::operator - (unary)): New.
	(double_int::operator ~ (unary)): New.
	(double_int::operator & (binary)): New.
	(double_int::operator | (binary)): New.
	(double_int::operator ^ (binary)): New.
	(double_int::and_not): New.
	(double_int::lshift): New.
	(double_int::rshift): New.
	(double_int::alshift): New.
	(double_int::arshift): New.
	(double_int::llshift): New.
	(double_int::lrshift): New.
	(double_int::lrotate): New.
	(double_int::rrotate): New.
	(double_int::div): New.
	(double_int::sdiv): New.
	(double_int::udiv): New.
	(double_int::mod): New.
	(double_int::smod): New.
	(double_int::umod): New.
	(double_int::divmod): New.
	(double_int::sdivmod): New.
	(double_int::udivmod): New.
	(double_int::ext): New.
	(double_int::zext): New.
	(double_int::sext): New.
	(double_int::is_zero): New.
	(double_int::is_one): New.
	(double_int::is_minus_one): New.
	(double_int::is_negative): New.
	(double_int::cmp): New.
	(double_int::ucmp): New.
	(double_int::scmp): New.
	(double_int::ult): New.
	(double_int::ugt): New.
	(double_int::slt): New.
	(double_int::sgt): New.
	(double_int::max): New.
	(double_int::smax): New.
	(double_int::umax): New.
	(double_int::min): New.
	(double_int::smin): New.
	(double_int::umin): New.
	(double_int::operator ==): New.
	(double_int::operator !=): New.
	(shwi_to_double_int): Change implementation to use member function.
	(double_int_minus_one): Likewise.
	(double_int_zero): Likewise.
	(double_int_one): Likewise.
	(double_int_two): Likewise.
	(double_int_ten): Likewise.
	(uhwi_to_double_int): Likewise.
	(double_int_to_shwi): Likewise.
	(double_int_to_uhwi): Likewise.
	(double_int_fits_in_uhwi_p): Likewise.
	(double_int_fits_in_shwi_p): Likewise.
	(double_int_fits_in_hwi_p): Likewise.
	(double_int_mul): Likewise.
	(double_int_mul_with_sign): Likewise.
	(double_int_add): Likewise.
	(double_int_sub): Likewise.
	(double_int_neg): Likewise.
	(double_int_div): Likewise.
	(double_int_sdiv): Likewise.
	(double_int_udiv): Likewise.
	(double_int_mod): Likewise.
	(double_int_smod): Likewise.
	(double_int_umod): Likewise.
	(double_int_divmod): Likewise.
	(double_int_sdivmod): Likewise.
	(double_int_udivmod): Likewise.
	(double_int_multiple_of): Likewise.
	(double_int_setbit): Likewise.
	(double_int_ctz): Likewise.
	(double_int_not): Likewise.
	(double_int_ior): Likewise.
	(double_int_and): Likewise.
	(double_int_and_not): Likewise.
	(double_int_xor): Likewise.
	(double_int_lshift): Likewise.
	(double_int_rshift): Likewise.
	(double_int_lrotate): Likewise.
	(double_int_rrotate): Likewise.
	(double_int_cmp): Likewise.
	(double_int_scmp): Likewise.
	(double_int_ucmp): Likewise.
	(double_int_max): Likewise.
	(double_int_smax): Likewise.
	(double_int_umax): Likewise.
	(double_int_min): Likewise.
	(double_int_smin): Likewise.
	(double_int_umin): Likewise.
	(double_int_ext): Likewise.
	(double_int_sext): Likewise.
	(double_int_zext): Likewise.
	(double_int_mask): Likewise.
	(double_int_max_value): Likewise.
	(double_int_min_value): Likewise.
	(double_int_zero_p): Likewise.
	(double_int_one_p): Likewise.
	(double_int_minus_one_p): Likewise.
	(double_int_equal_p): Likewise.
	(double_int_popcount): Likewise.
	* hash-table.c
	(double_int_mask): Reuse implementation for double_int::mask.
	(double_int_max_value): Likewise.
	(double_int_min_value): Likewise.
	(double_int_ext): Likewise.
	(double_int_zext): Likewise.
	(double_int_sext): Likewise.
	(double_int_mul_with_sign): Likewise.
	(double_int_divmod): Likewise.
	(double_int_sdivmod): Likewise.
	(double_int_udivmod): Likewise.
	(double_int_div): Likewise.
	(double_int_sdiv): Likewise.
	(double_int_udiv): Likewise.
	(double_int_mod): Likewise.
	(double_int_smod): Likewise.
	(double_int_umod): Likewise.
	(double_int_multiple_of): Likewise.
	(double_int_lshift): Likewise.
	(double_int_rshift): Likewise.
	(double_int_lrotate): Likewise.
	(double_int_rrotate): Likewise.
	(double_int_cmp): Likewise.
	(double_int_ucmp): Likewise.
	(double_int_scmp): Likewise.
	(double_int_max): Likewise.
	(double_int_smax): Likewise.
	(double_int_umax): Likewise.
	(double_int_min): Likewise.
	(double_int_smin): Likewise.
	(double_int_umin): Likewise.
	(double_int_min): Likewise.
	(double_int_min): Likewise.
	(double_int_min): Likewise.
	(double_int_min): Likewise.
	(double_int_min): Likewise.
	(double_int_min): Likewise.
	(double_int::alshift): New.
	(double_int::arshift): New.
	(double_int::llshift): New.
	(double_int::lrshift): New.
	(double_int::ult): New.
	(double_int::ugt): New.
	(double_int::slt): New.
	(double_int::sgt): New.
	(double_int_setbit): Reuse implementation for double_int::set_bit,
	which avoids a name conflict with a macro.
	(double_int_double_int_ctz): Reuse implementation for
	double_int::trailing_zeros.
	(double_int_fits_in_shwi_p): Reuse implementation for
	double_int::fits_signed.
	(double_int_fits_in_hwi_p): Reuse implementation for double_int::fits.
	(double_int_mul): Reuse implementation for binary
	double_int::operator *.
	(double_int_add): Likewise.
	(double_int_sub): Likewise.
	(double_int_neg): Reuse implementation for unary
	double_int::operator -.
	(double_int_max_value): Likewise.
	* fixed-value.c: Change to use member functions introduced above.

2012-08-14   Lawrence Crowl  <crowl@google.com>

	Merge cxx-conversion branch.  Support tree macro calling
	from gdb.

	* tree.h (tree_check): New.
	(TREE_CHECK): Use inline function above instead of __extension__.
	(tree_not_check): New.
	(TREE_NOT_CHECK): Use inline function above instead of __extension__.
	(tree_check2): New.
	(TREE_CHECK2): Use inline function above instead of __extension__.
	(tree_not_check2): New.
	(TREE_NOT_CHECK2): Use inline function above instead of __extension__.
	(tree_check3): New.
	(TREE_CHECK3): Use inline function above instead of __extension__.
	(tree_not_check3): New.
	(TREE_NOT_CHECK3): Use inline function above instead of __extension__.
	(tree_check4): New.
	(TREE_CHECK4): Use inline function above instead of __extension__.
	(tree_not_check4): New.
	(TREE_NOT_CHECK4): Use inline function above instead of __extension__.
	(tree_check5): New.
	(TREE_CHECK5): Use inline function above instead of __extension__.
	(tree_not_check5): New.
	(TREE_NOT_CHECK5): Use inline function above instead of __extension__.
	(contains_struct_check): New.
	(CONTAINS_STRUCT_CHECK): Use inline function above instead of
	__extension__.
	(tree_class_check): New.
	(TREE_CLASS_CHECK): Use inline function above instead of __extension__.
	(tree_range_check): New.
	(TREE_RANGE_CHECK): Use inline function above instead of __extension__.
	(omp_clause_subcode_check): New.
	(OMP_CLAUSE_SUBCODE_CHECK): Use inline function above instead of
	__extension__.
	(omp_clause_range_check): New.
	(OMP_CLAUSE_RANGE_CHECK): Use inline function above instead of
	__extension__.
	(expr_check): New.
	(EXPR_CHECK): Use inline function above instead of __extension__.
	(non_type_check): New.
	(NON_TYPE_CHECK): Use inline function above instead of __extension__.
	(tree_vec_elt_check): New.
	(TREE_VEC_ELT_CHECK): Use inline function above instead of
	__extension__.
	(omp_clause_elt_check): New.
	(OMP_CLAUSE_ELT_CHECK): Use inline function above instead of
	__extension__.
	(tree_operand_check): New.
	(TREE_OPERAND_CHECK): Use inline function above instead of
	__extension__.
	(tree_operand_check_code): New.
	(TREE_OPERAND_CHECK_CODE): Use inline function above instead of
	__extension__.
	(TREE_CHAIN): Simplify implementation.
	(TREE_TYPE): Simplify implementation.
	(tree_operand_length): Move for compilation dependences.
	* gdbinit.in: (macro define __FILE__): New.
	(macro define __LINE__): New.
	(skip "tree.h"): New.

gcc/cp/ChangeLog
2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.  Re-write VEC in C++.

	* call.c (add_function_candidate): Remove const qualifier
	from call to VEC_index.

2012-08-14   Diego Novillo  <dnovillo@google.com>

	Merge from cxx-conversion branch.  Configury.

	* go-c.h: Remove all handlers of ENABLE_BUILD_WITH_CXX.
	* go-gcc.cc: Likewise.
	* go-system.h: Likewise.

From-SVN: r190402

1 files changed, 783 insertions, 0 deletions

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
new file mode 100644
index 0000000..2c483e2
--- /dev/null
+++ b/gcc/hash-table.h
@@ -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 */