2011-05-23 Benjamin Kosnik <bkoz@redhat.com>

	PR libstdc++/37144
	PR libstdc++/28457
	Interface changes for ext/pb_ds.
	PB_DS_BASE_C_DEC to unique PB_DS_*_BASE macros.
	* include/ext/pb_ds/assoc_container.hpp (container_base): Remove.
	(basic_hash_table, basic_branch, list_update): Derive from
	container_base_dispatch.
	* include/ext/pb_ds/list_update_policy.hpp (null_lu_metadata): Remove.
	(move_to_front_lu_policy): To lu_move_to_front_policy.
	(counter_lu_policy): To lu_counter_policy.
	* include/ext/pb_ds/tree_policy.hpp (null_tree_node_update): Remove.
	* include/ext/pb_ds/tag_and_trait.hpp (container_base_dispatch): Adjust
	template parameters, declare here.
	(null_mapped_type) Remove.
	(null_type): Just use this for template tricks everywhere.
	* include/ext/pb_ds/hash_policy.hpp (null_hash_fn, null_probe_fn):
	Remove.
	* include/ext/pb_ds/trie_policy.hpp (null_trie_node_update): Remove.
	(string_trie_e_access_traits): To trie_string_access_traits.
	* include/ext/pb_ds/priority_queue.hpp: Use container_base_dispatch.

	File changes.
	* include/Makefile.am (pb_headers): Removed and changed file names.
	* include/Makefile.in: Regenerated.
	* include/ext/pb_ds/detail/basic_types.hpp: Remove.
	* include/ext/pb_ds/detail/bin_search_tree_/
	  cond_dtor_entry_dealtor.hpp: Remove.
	* include/ext/pb_ds/detail/bin_search_tree_/
	  cond_key_dtor_entry_dealtor.hpp: Remove.
	* include/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp: Move..
	* include/ext/pb_ds/detail/binary_heap_/
	  point_const_iterator.hpp: ..here.
	* include/ext/pb_ds/detail/basic_tree_policy: Move to...
	* include/ext/pb_ds/detail/branch_policy: This.
	* include/ext/pb_ds/detail/branch_policy/
	  basic_tree_policy_base.hpp: Move...
	* include/ext/pb_ds/detail/branch_policy/branch_policy.hpp: ...here.
	* include/ext/pb_ds/detail/branch_policy/null_node_metadata.hpp: Add.
	* include/ext/pb_ds/detail/branch_policy/traits.hpp: Add.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	null_metadata.hpp: Remove.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	const_point_iterator.hpp: Move...
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	point_const_iterator.hpp: ...here.
	* include/ext/pb_ds/detail/list_update_policy/
	counter_lu_metadata.hpp: Move..
	* include/ext/pb_ds/detail/list_update_policy/
	lu_counter_metadata.hpp: ...here.
	* include/ext/pb_ds/detail/list_update_policy/
	counter_lu_policy_imp.hpp: Remove.
	* include/ext/pb_ds/detail/list_update_policy/
	mtf_lu_policy_imp.hpp: Remove.
	* include/ext/pb_ds/detail/trie_policy/
	string_trie_e_access_traits_imp.hpp: Move...
	* include/ext/pb_ds/detail/trie_policy/
	sample_trie_access_traits.hpp: ...here.
	* include/ext/pb_ds/detail/trie_policy/
	sample_trie_e_access_traits.hpp: Move...
	* include/ext/pb_ds/detail/trie_policy/
	trie_string_access_traits_imp.hpp: ...here.
	* include/ext/pb_ds/detail/trie_policy/null_node_update_imp.hpp: Remove.
	* include/ext/pb_ds/detail/tree_policy/null_node_update_imp.hpp: Remove.
	* include/ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp: Remove.
	* include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp: New, fold all
	types found in the following files into pat_trie_base.
	* include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/
	  cond_dtor_entry_dealtor.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/head.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/leaf.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/node_base.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/internal_node.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp: Folded.
	* include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp: Move...
	* include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp: ...here.
	* include/ext/pb_ds/detail/unordered_iterator/
	const_point_iterator.hpp: Move...
	* include/ext/pb_ds/detail/unordered_iterator/
	point_const_iterator.hpp: ...here.


	Adjust for above changes.
	* include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp: Same.
	* include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp: Same.
	* include/ext/pb_ds/detail/resize_policy/
	  sample_resize_trigger.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/
	  binomial_heap_base_.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_base_/
	  split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/container_base_dispatch.hpp: Same. Adjust
	  for template parameter ordering change.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  erase_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  constructor_destructor_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  insert_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  resize_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  constructor_destructor_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  insert_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  entry_list_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  find_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  debug_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  constructor_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  cond_key_dtor_entry_dealtor.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  debug_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  erase_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  resize_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/
	  standard_policies.hpp: Same.
	* include/ext/pb_ds/detail/tree_trace_base.hpp: Same.
	* include/ext/pb_ds/detail/unordered_iterator/iterator.hpp: Same.
	* include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp: Same.
	* include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/traits.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/
	  policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/traits.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/
	  split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_policy/
	  sample_update_policy.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  erase_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  constructor_destructor_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  insert_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  resize_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  constructor_destructor_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  insert_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  iterator_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  find_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  find_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  debug_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  constructor_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  debug_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  erase_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  resize_no_store_hash_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/
	  standard_policies.hpp: Same.
	* include/ext/pb_ds/detail/standard_policies.hpp: Same.
	* include/ext/pb_ds/detail/types_traits.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp: Same.
	* include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp: Same.
	* include/ext/pb_ds/detail/tree_policy/
	  sample_tree_node_update.hpp: Same.
	* include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp: Same.
	* include/ext/pb_ds/detail/trie_policy/
	  sample_trie_node_update.hpp: Same.
	* include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp: Same.
	* include/ext/pb_ds/detail/trie_policy/
	  prefix_search_node_update_imp.hpp: Same.
	* include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp: Same.
	* include/ext/pb_ds/detail/cond_dealtor.hpp: Same.
	* include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp: Same.
	  Adjust for template parameter change, fold into
	  container_base_dispatch.
	* include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
	* include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/type_utils.hpp: Same.
	* include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp: Same.
	* include/ext/pb_ds/detail/eq_fn/eq_by_less.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  left_child_next_sibling_heap_.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  const_iterator.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  node.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	  iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/traits.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/debug_map_base.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp: Same.
	* include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/node.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/traits.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/
	  entry_metadata_base.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/
	  constructor_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/
	  rc_binomial_heap_.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/
	  split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/
	  constructors_destructor_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/traits.hpp: Same.


	Documentation changes.
	* include/ext/pb_ds/*: Add doxygen markup.
	* doc/doxygen/user.cfg.in: Add details for extracting comments
	from pb_ds.
	* scripts/run_doxygen: Fixup __gnu_pb_ds::detail.
	* scripts/make_graph.py: Move to svg output. Re-format generated tables.

	* doc/Makefile.am (stamp-html-copy): New rule.
	(stamp-html): Use it to copy non-generated files into html docs.
	* doc/Makefile.in: Regenerated.

	* doc/html/ext/pb_ds/sample_trie_e_access_traits.html: Move...
	* doc/html/ext/pb_ds/trie_string_access_traits.html: ...here.
	* doc/html/ext/pb_ds/string_trie_e_access_traits.html: Move..
	* doc/html/ext/pb_ds/sample_trie_access_traits.html: ...here.

	* doc/html/ext/pb_ds/tree_text_lor_find_timing_test_local.png,
	hash_random_int_erase_mem_usage_test_local.png,
	multimap_text_insert_mem_usage_test_small_s2p_hash_local.png,
	tree_text_insert_timing_test_pat_trie_local.png ,
	multimap_text_insert_mem_usage_test_small_s2p_tree_local.png ,
	priority_queue_text_modify_down_timing_test_local.png,
	gp_hash_random_int_subscript_timing_test_find_local.png,
	text_find_timing_test_hash_local.png,
	multimap_text_insert_timing_test_small_s2p_hash_local.png,
	multimap_text_insert_timing_test_small_s2p_tree_local.png,
	multimap_text_insert_mem_usage_test_large_s2p_hash_local.png,
	multimap_text_insert_mem_usage_test_large_s2p_tree_local.png,
	multimap_text_insert_timing_test_large_s2p_hash_local.png,
	hash_zlob_random_int_find_timing_test_local.png,
	multimap_text_insert_timing_test_large_s2p_tree_local.png,
	binary_priority_queue_random_int_push_timing_test_local.png,
	priority_queue_text_pop_mem_usage_test_local.png,
	priority_queue_text_modify_down_timing_test_pairing_thin_local.png,
	tree_split_join_timing_test_local.png,
	multimap_text_find_timing_test_small_s2p_hash_local.png,
	ccgp_hash_random_int_subscript_timing_test_insert_local.png,
	priority_queue_random_int_push_pop_timing_test_local.png,
	multimap_text_find_timing_test_small_s2p_tree_local.png,
	gp_hash_random_int_subscript_timing_test_insert_local.png,
	priority_queue_text_push_timing_test_local.png,
	cc_hash_random_int_subscript_timing_test_find_local.png,
	tree_text_insert_timing_test_vector_tree_local.png,
	multimap_text_find_timing_test_large_s2p_hash_local.png,
	pairing_priority_queue_text_push_timing_test_local.png,
	tree_order_statistics_timing_test_local.png,
	priority_queue_text_push_pop_timing_test_local.png,
	text_find_timing_test_tree_like_local.png,
	multimap_text_find_timing_test_large_s2p_tree_local.png,
	priority_queue_text_modify_up_timing_test_pairing_thin_local.png,
	cc_hash_random_int_subscript_timing_test_insert_local.png,
	priority_queue_text_modify_up_timing_test_local.png,
	random_int_find_find_timing_test_tree_local.png,
	priority_queue_random_int_push_timing_test_local.png,
	tree_text_insert_timing_test_node_tree_local.png,
	pairing_priority_queue_text_push_pop_timing_test_local.png,
	gp_hash_random_int_find_timing_test_local.png,
	cc_hash_random_int_find_timing_test_local.png,
	priority_queue_text_join_timing_test_local.png: Update local pngs.


	Testsuite changes.
	* testsuite/ext/pb_ds/regression/tree_no_data_map_rand_debug.cc: New.
	* testsuite/ext/pb_ds/regression/tree_data_map_rand_debug.cc: New.
	* testsuite/ext/pb_ds/regression/priority_queue_rand_debug.cc: New.
	* testsuite/ext/pb_ds/regression/trie_no_data_map_rand_debug.cc: New.
	* testsuite/ext/pb_ds/regression/trie_data_map_rand_debug.cc: New.
	* testsuite/ext/pb_ds/regression/list_update_no_data_map_rand_debug.cc:
	New.
	* testsuite/ext/pb_ds/regression/list_update_data_map_rand_debug.cc:
	New.
	* testsuite/ext/pb_ds/regression/hash_no_data_map_rand_debug.cc: New.
	* testsuite/ext/pb_ds/regression/hash_data_map_rand_debug.cc: New.

	* testsuite/ext/pb_ds/regression/list_update_data_map_rand.cc: Fix typo.

	* testsuite/ext/pb_ds/example/basic_set.cc: Update.
	* testsuite/ext/pb_ds/example/ranged_hash.cc: Same.
	* testsuite/ext/pb_ds/example/tree_order_statistics.cc: Same.
	* testsuite/ext/pb_ds/example/trie_prefix_search.cc: Same.
	* testsuite/ext/pb_ds/example/trie_dna.cc: Same.
	* testsuite/ext/pb_ds/example/tree_intervals.cc: Same.
	* testsuite/ext/pb_ds/example/basic_multimap.cc: Same.
	* testsuite/performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc:
	  Same.
	* testsuite/performance/ext/pb_ds/tree_split_join_timing.cc: Same.
	* testsuite/performance/ext/pb_ds/tree_order_statistics_timing.cc: Same.
	* testsuite/data/make_graph_test_infos.xml: Same.
	* testsuite/util/regression/common_type.hpp: Same.
	* testsuite/util/regression/trait/assoc/native_type_trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
	* testsuite/util/regression/rand/priority_queue/
	  rand_regression_test.hpp: Same.
	* testsuite/util/regression/rand/priority_queue/
	  container_rand_regression_test.tcc: Same.
	* testsuite/util/regression/rand/assoc/rand_regression_test.hpp: Same.
	* testsuite/util/regression/rand/assoc/container_rand_regression_test.h
	* testsuite/util/regression/rand/assoc/
	  container_rand_regression_test.tcc: Same.
	* testsuite/util/native_type/native_priority_queue.hpp: Same.
	* testsuite/util/native_type/native_multimap.hpp: Same.
	* testsuite/util/native_type/native_hash_multimap.hpp: Same.
	* testsuite/util/native_type/native_set.hpp: Same.
	* testsuite/util/native_type/native_map.hpp: Same.
	* testsuite/util/native_type/native_hash_set.hpp: Same.
	* testsuite/util/native_type/native_hash_map.hpp: Same.
	* testsuite/util/testsuite_containers.h
	* testsuite/util/common_type/priority_queue/common_type.hpp: Same.
	* testsuite/util/common_type/assoc/common_type.hpp: Same.
	* testsuite/util/common_type/assoc/string_form.hpp: Same.
	* testsuite/util/common_type/assoc/template_policy.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  trigger_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/ds_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  size_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  probe_fn_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  tree_supports_order_statistics.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  trie_supports_prefix_search.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  list_update_policy_string_form.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	  trie_supports_order_statistics.hpp: Same.
	* testsuite/util/common_type/assoc/native_set.hpp: Same.
	* testsuite/util/performance/assoc/timing/common_type.hpp: Same.
	* testsuite/util/performance/assoc/timing/multimap_find_test.hpp: Same.
	* testsuite/util/performance/assoc/multimap_common_type.hpp: Same.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@174100 138bc75d-0d04-0410-961f-82ee72b054a4

7 files changed, 177 insertions, 189 deletions

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp
index 970cfc1e553..19855ac1e8b 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp
@@ -47,7 +47,7 @@ namespace __gnu_pbds
 {
   namespace detail
   {
-    template<typename Allocator>
+    template<typename _Alloc>
     class probe_fn_base
     {
     protected:
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
index 24899272f8f..8567851f798 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the terms
@@ -42,7 +42,6 @@
 #ifndef PB_DS_RANGED_HASH_FN_HPP
 #define PB_DS_RANGED_HASH_FN_HPP
 
-#include <ext/pb_ds/detail/basic_types.hpp>
 #include <utility>
 #include <debug/debug.h>
 
@@ -50,33 +49,33 @@ namespace __gnu_pbds
 {
   namespace detail
   {
-    template<typename Key, typename Hash_Fn, typename Allocator, 
+    template<typename Key, typename Hash_Fn, typename _Alloc, 
 	     typename Comb_Hash_Fn, bool Store_Hash>
     class ranged_hash_fn;
 
 #define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Hash_Fn, typename Allocator, \
+    template<typename Key, typename Hash_Fn, typename _Alloc, \
 	     typename Comb_Hash_Fn>
 
 #define PB_DS_CLASS_C_DEC \
-    ranged_hash_fn<Key,	Hash_Fn, Allocator, Comb_Hash_Fn, false>
+    ranged_hash_fn<Key,	Hash_Fn, _Alloc, Comb_Hash_Fn, false>
 
     /**
      * Specialization 1
      * The client supplies a hash function and a ranged hash function,
      * and requests that hash values not be stored.
      **/
-    template<typename Key, typename Hash_Fn, typename Allocator, 
+    template<typename Key, typename Hash_Fn, typename _Alloc, 
 	     typename Comb_Hash_Fn>
-    class ranged_hash_fn< Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> 
+    class ranged_hash_fn< Key, Hash_Fn, _Alloc, Comb_Hash_Fn, false> 
     : public Hash_Fn, public Comb_Hash_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef Hash_Fn hash_fn_base;
       typedef Comb_Hash_Fn comb_hash_fn_base;
-      typedef typename Allocator::template rebind< Key>::other key_allocator;
-      typedef typename key_allocator::const_reference const_key_reference;
+      typedef typename _Alloc::template rebind< Key>::other key_allocator;
+      typedef typename key_allocator::const_reference key_const_reference;
 
       ranged_hash_fn(size_type);
 
@@ -91,7 +90,7 @@ namespace __gnu_pbds
       notify_resized(size_type);
 
       inline size_type
-      operator()(const_key_reference) const;
+      operator()(key_const_reference) const;
     };
 
     PB_DS_CLASS_T_DEC
@@ -130,36 +129,36 @@ namespace __gnu_pbds
     PB_DS_CLASS_T_DEC
     inline typename PB_DS_CLASS_C_DEC::size_type
     PB_DS_CLASS_C_DEC::
-    operator()(const_key_reference r_key) const
+    operator()(key_const_reference r_key) const
     { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));}
 
 #undef PB_DS_CLASS_T_DEC
 #undef PB_DS_CLASS_C_DEC
 
 #define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Hash_Fn, typename Allocator, \
+    template<typename Key, typename Hash_Fn, typename _Alloc, \
 	     typename Comb_Hash_Fn>
 
 #define PB_DS_CLASS_C_DEC \
-    ranged_hash_fn<Key,Hash_Fn,	Allocator, Comb_Hash_Fn, true>
+    ranged_hash_fn<Key,Hash_Fn,	_Alloc, Comb_Hash_Fn, true>
 
     /**
      * Specialization 2
      * The client supplies a hash function and a ranged hash function,
      * and requests that hash values be stored.
      **/
-    template<typename Key, typename Hash_Fn, typename Allocator,
+    template<typename Key, typename Hash_Fn, typename _Alloc,
 	     typename Comb_Hash_Fn>
-    class ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, true> 
+    class ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, true> 
     : public Hash_Fn, public Comb_Hash_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef std::pair<size_type, size_type> comp_hash;
       typedef Hash_Fn hash_fn_base;
       typedef Comb_Hash_Fn comb_hash_fn_base;
-      typedef typename Allocator::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference const_key_reference;
+      typedef typename _Alloc::template rebind<Key>::other key_allocator;
+      typedef typename key_allocator::const_reference key_const_reference;
 
       ranged_hash_fn(size_type);
 
@@ -174,10 +173,10 @@ namespace __gnu_pbds
       notify_resized(size_type);
 
       inline comp_hash
-      operator()(const_key_reference) const;
+      operator()(key_const_reference) const;
 
       inline comp_hash
-      operator()(const_key_reference, size_type) const;
+      operator()(key_const_reference, size_type) const;
     };
 
     PB_DS_CLASS_T_DEC
@@ -216,7 +215,7 @@ namespace __gnu_pbds
     PB_DS_CLASS_T_DEC
     inline typename PB_DS_CLASS_C_DEC::comp_hash
     PB_DS_CLASS_C_DEC::
-    operator()(const_key_reference r_key) const
+    operator()(key_const_reference r_key) const
     {
       const size_type hash = hash_fn_base::operator()(r_key);
       return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
@@ -227,9 +226,9 @@ namespace __gnu_pbds
     PB_DS_CLASS_C_DEC::
     operator()
 #ifdef _GLIBCXX_DEBUG
-      (const_key_reference r_key, size_type hash) const
+      (key_const_reference r_key, size_type hash) const
 #else 
-      (const_key_reference /*r_key*/, size_type hash) const
+      (key_const_reference /*r_key*/, size_type hash) const
 #endif
     {
       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
@@ -240,30 +239,30 @@ namespace __gnu_pbds
 #undef PB_DS_CLASS_C_DEC
 
 #define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Allocator, typename Comb_Hash_Fn>
+    template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
 
 #define PB_DS_CLASS_C_DEC \
-    ranged_hash_fn<Key,	null_hash_fn, Allocator, Comb_Hash_Fn, false>
+    ranged_hash_fn<Key,	null_type, _Alloc, Comb_Hash_Fn, false>
 
     /**
      * Specialization 3
      * The client does not supply a hash function (by specifying
-     * null_hash_fn as the Hash_Fn parameter), and requests that hash
+     * null_type as the Hash_Fn parameter), and requests that hash
      * values not be stored.
      **/
-    template<typename Key, typename Allocator, typename Comb_Hash_Fn>
-    class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, false> 
-    : public null_hash_fn, public Comb_Hash_Fn
+    template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
+    class ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, false> 
+    : public Comb_Hash_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef Comb_Hash_Fn comb_hash_fn_base;
 
       ranged_hash_fn(size_type);
 
       ranged_hash_fn(size_type, const Comb_Hash_Fn&);
 
-      ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&);
+      ranged_hash_fn(size_type, const null_type&, const Comb_Hash_Fn&);
 
       void
       swap(PB_DS_CLASS_C_DEC&);
@@ -282,7 +281,7 @@ namespace __gnu_pbds
 
     PB_DS_CLASS_T_DEC
     PB_DS_CLASS_C_DEC::
-    ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, 
+    ranged_hash_fn(size_type size, const null_type& r_null_type, 
 		   const Comb_Hash_Fn& r_comb_hash_fn) 
     : Comb_Hash_Fn(r_comb_hash_fn)
     { }
@@ -297,30 +296,30 @@ namespace __gnu_pbds
 #undef PB_DS_CLASS_C_DEC
 
 #define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Allocator, typename Comb_Hash_Fn>
+    template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
 
 #define PB_DS_CLASS_C_DEC \
-    ranged_hash_fn<Key,	null_hash_fn, Allocator, Comb_Hash_Fn, true>
+    ranged_hash_fn<Key,	null_type, _Alloc, Comb_Hash_Fn, true>
 
     /**
      * Specialization 4
      * The client does not supply a hash function (by specifying
-     * null_hash_fn as the Hash_Fn parameter), and requests that hash
+     * null_type as the Hash_Fn parameter), and requests that hash
      * values be stored.
      **/
-    template<typename Key, typename Allocator, typename Comb_Hash_Fn>
-    class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, true> 
-    : public null_hash_fn, public Comb_Hash_Fn
+    template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
+    class ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, true> 
+    : public Comb_Hash_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef Comb_Hash_Fn comb_hash_fn_base;
 
       ranged_hash_fn(size_type);
 
       ranged_hash_fn(size_type, const Comb_Hash_Fn&);
 
-      ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&);
+      ranged_hash_fn(size_type, const null_type&, const Comb_Hash_Fn&);
 
       void
       swap(PB_DS_CLASS_C_DEC&);
@@ -339,7 +338,7 @@ namespace __gnu_pbds
 
     PB_DS_CLASS_T_DEC
     PB_DS_CLASS_C_DEC::
-    ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, 
+    ranged_hash_fn(size_type size, const null_type& r_null_type, 
 		   const Comb_Hash_Fn& r_comb_hash_fn) 
     : Comb_Hash_Fn(r_comb_hash_fn)
     { }
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
index ddfba9de1f2..b13de65555a 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
@@ -42,7 +42,6 @@
 #ifndef PB_DS_RANGED_PROBE_FN_HPP
 #define PB_DS_RANGED_PROBE_FN_HPP
 
-#include <ext/pb_ds/detail/basic_types.hpp>
 #include <utility>
 #include <debug/debug.h>
 
@@ -50,35 +49,35 @@ namespace __gnu_pbds
 {
   namespace detail
   {
-    template<typename Key, typename Hash_Fn, typename Allocator,
+    template<typename Key, typename Hash_Fn, typename _Alloc,
 	     typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
     class ranged_probe_fn;
 
 #define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Hash_Fn, typename Allocator, \
+    template<typename Key, typename Hash_Fn, typename _Alloc, \
 	     typename Comb_Probe_Fn, typename Probe_Fn>
 
 #define PB_DS_CLASS_C_DEC \
-    ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>
+    ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false>
 
     /**
      * Specialization 1     
      * The client supplies a probe function and a ranged probe
      * function, and requests that hash values not be stored.
      **/
-    template<typename Key, typename Hash_Fn, typename Allocator,
+    template<typename Key, typename Hash_Fn, typename _Alloc,
 	     typename Comb_Probe_Fn, typename Probe_Fn>
-    class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
+    class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn,
 			  Probe_Fn, false> 
     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef Comb_Probe_Fn comb_probe_fn_base;
       typedef Hash_Fn hash_fn_base;
       typedef Probe_Fn probe_fn_base;
-      typedef typename Allocator::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference const_key_reference;
+      typedef typename _Alloc::template rebind<Key>::other key_allocator;
+      typedef typename key_allocator::const_reference key_const_reference;
 
       ranged_probe_fn(size_type);
 
@@ -96,10 +95,10 @@ namespace __gnu_pbds
       notify_resized(size_type);
 
       inline size_type
-      operator()(const_key_reference) const;
+      operator()(key_const_reference) const;
 
       inline size_type
-      operator()(const_key_reference, size_type, size_type) const;
+      operator()(key_const_reference, size_type, size_type) const;
     };
 
     PB_DS_CLASS_T_DEC
@@ -146,13 +145,13 @@ namespace __gnu_pbds
     PB_DS_CLASS_T_DEC
     inline typename PB_DS_CLASS_C_DEC::size_type
     PB_DS_CLASS_C_DEC::
-    operator()(const_key_reference r_key) const
+    operator()(key_const_reference r_key) const
     { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
 
     PB_DS_CLASS_T_DEC
     inline typename PB_DS_CLASS_C_DEC::size_type
     PB_DS_CLASS_C_DEC::
-    operator()(const_key_reference, size_type hash, size_type i) const
+    operator()(key_const_reference, size_type hash, size_type i) const
     {
       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
     }
@@ -161,30 +160,30 @@ namespace __gnu_pbds
 #undef PB_DS_CLASS_C_DEC
 
 #define PB_DS_CLASS_T_DEC \
-    template<typename Key, typename Hash_Fn, typename Allocator, \
+    template<typename Key, typename Hash_Fn, typename _Alloc, \
 	     typename Comb_Probe_Fn, typename Probe_Fn>
 
 #define PB_DS_CLASS_C_DEC \
-    ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>
+    ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true>
 
     /**
      * Specialization 2- The client supplies a probe function and a ranged
      *    probe function, and requests that hash values not be stored.
      **/
-    template<typename Key, typename Hash_Fn, typename Allocator,
+    template<typename Key, typename Hash_Fn, typename _Alloc,
 	     typename Comb_Probe_Fn, typename Probe_Fn>
-    class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, 
+    class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 
 			  Probe_Fn, true> 
     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef std::pair<size_type, size_type> comp_hash;
       typedef Comb_Probe_Fn comb_probe_fn_base;
       typedef Hash_Fn hash_fn_base;
       typedef Probe_Fn probe_fn_base;
-      typedef typename Allocator::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference const_key_reference;
+      typedef typename _Alloc::template rebind<Key>::other key_allocator;
+      typedef typename key_allocator::const_reference key_const_reference;
 
       ranged_probe_fn(size_type);
 
@@ -203,13 +202,13 @@ namespace __gnu_pbds
       notify_resized(size_type);
 
       inline comp_hash
-      operator()(const_key_reference) const;
+      operator()(key_const_reference) const;
 
       inline size_type
-      operator()(const_key_reference, size_type, size_type) const;
+      operator()(key_const_reference, size_type, size_type) const;
 
       inline size_type
-      operator()(const_key_reference, size_type) const;
+      operator()(key_const_reference, size_type) const;
     };
 
     PB_DS_CLASS_T_DEC
@@ -256,7 +255,7 @@ namespace __gnu_pbds
     PB_DS_CLASS_T_DEC
     inline typename PB_DS_CLASS_C_DEC::comp_hash
     PB_DS_CLASS_C_DEC::
-    operator()(const_key_reference r_key) const
+    operator()(key_const_reference r_key) const
     {
       const size_type hash = hash_fn_base::operator()(r_key);
       return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
@@ -265,7 +264,7 @@ namespace __gnu_pbds
     PB_DS_CLASS_T_DEC
     inline typename PB_DS_CLASS_C_DEC::size_type
     PB_DS_CLASS_C_DEC::
-    operator()(const_key_reference, size_type hash, size_type i) const
+    operator()(key_const_reference, size_type hash, size_type i) const
     {
       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
     }
@@ -275,9 +274,9 @@ namespace __gnu_pbds
     PB_DS_CLASS_C_DEC::
     operator()
 #ifdef _GLIBCXX_DEBUG
-      (const_key_reference r_key, size_type hash) const
+      (key_const_reference r_key, size_type hash) const
 #else 
-      (const_key_reference /*r_key*/, size_type hash) const
+      (key_const_reference /*r_key*/, size_type hash) const
 #endif 
     {
       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
@@ -292,16 +291,16 @@ namespace __gnu_pbds
      * The client does not supply a hash function or probe function,
      * and requests that hash values not be stored.
      **/
-    template<typename Key, typename Allocator, typename Comb_Probe_Fn>
-    class ranged_probe_fn<Key, null_hash_fn, Allocator, Comb_Probe_Fn, 
-			  null_probe_fn, false> 
-    : public Comb_Probe_Fn, public null_hash_fn, public null_probe_fn
+    template<typename Key, typename _Alloc, typename Comb_Probe_Fn>
+    class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, 
+			  null_type, false> 
+    : public Comb_Probe_Fn
     {
     protected:
-      typedef typename Allocator::size_type size_type;
+      typedef typename _Alloc::size_type size_type;
       typedef Comb_Probe_Fn comb_probe_fn_base;
-      typedef typename Allocator::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference const_key_reference;
+      typedef typename _Alloc::template rebind<Key>::other key_allocator;
+      typedef typename key_allocator::const_reference key_const_reference;
 
       ranged_probe_fn(size_type size)
       { Comb_Probe_Fn::notify_resized(size); }
@@ -310,9 +309,9 @@ namespace __gnu_pbds
       : Comb_Probe_Fn(r_comb_probe_fn)
       { }
 
-      ranged_probe_fn(size_type, const null_hash_fn&, 
+      ranged_probe_fn(size_type, const null_type&, 
 		      const Comb_Probe_Fn& r_comb_probe_fn, 
-		      const null_probe_fn&)
+		      const null_type&)
       : Comb_Probe_Fn(r_comb_probe_fn)
       { }
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp
index 7dcd82588c1..3ca9001e025 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp
@@ -41,33 +41,28 @@
 #ifndef PB_DS_SAMPLE_PROBE_FN_HPP
 #define PB_DS_SAMPLE_PROBE_FN_HPP
 
-// A sample probe policy.
-class sample_probe_fn
+namespace __gnu_pbds
 {
-
-public:
-
-  // Size type.
-  typedef std::size_t size_type;
-
-public:
-
-  // Default constructor.
-  sample_probe_fn();
-
-  // Copy constructor.
-  sample_probe_fn(const sample_probe_fn& other);
-
-  // Swaps content.
-  inline void
-  swap(sample_probe_fn& other);
-
-protected:
-
-  // Returns the i-th offset from the hash value of some key r_key.
-  inline size_type
-  operator()(const_key_reference r_key, size_type i) const;
-
-};
-
+  /// A sample probe policy.
+  class sample_probe_fn
+  {
+  public:
+    typedef std::size_t size_type;
+
+    // Default constructor.
+    sample_probe_fn();
+
+    // Copy constructor.
+    sample_probe_fn(const sample_probe_fn&);
+
+    // Swaps content.
+    inline void
+    swap(sample_probe_fn&);
+
+  protected:
+    // Returns the i-th offset from the hash value of some key r_key.
+    inline size_type
+    operator()(key_const_reference r_key, size_type i) const;
+  };
+}
 #endif // #ifndef PB_DS_SAMPLE_PROBE_FN_HPP
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp
index 988f111ea20..3092376832c 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp
@@ -41,37 +41,34 @@
 #ifndef PB_DS_SAMPLE_RANGE_HASHING_HPP
 #define PB_DS_SAMPLE_RANGE_HASHING_HPP
 
-// A sample range-hashing functor.
-class sample_range_hashing
+namespace __gnu_pbds
 {
-
-public:
-
-  // Size type.
-  typedef std::size_t size_type;
-
-public:
-
-  // Default constructor.
-  sample_range_hashing();
-
-  // Copy constructor.
-  sample_range_hashing(const sample_range_hashing& other);
-
-  // Swaps content.
-  inline void
-  swap(sample_range_hashing& other);
-
-protected:
-
-  // Notifies the policy object that the container's __size has changed to size.
-  void
-  notify_resized(size_type size);
-
-  // Transforms the __hash value hash into a ranged-hash value.
-  inline size_type
-  operator()(size_type hash) const;
-
-};
-
+  /// A sample range-hashing functor.
+  class sample_range_hashing
+  {
+  public:
+    // Size type.
+    typedef std::size_t size_type;
+
+    // Default constructor.
+    sample_range_hashing();
+
+    // Copy constructor.
+    sample_range_hashing(const sample_range_hashing& other);
+
+    // Swaps content.
+    inline void
+    swap(sample_range_hashing& other);
+
+  protected:
+    // Notifies the policy object that the container's __size has
+    // changed to size.
+    void
+    notify_resized(size_type);
+
+    // Transforms the __hash value hash into a ranged-hash value.
+    inline size_type
+    operator()(size_type ) const;
+  };
+}
 #endif // #ifndef PB_DS_SAMPLE_RANGE_HASHING_HPP
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp
index 8fa04d140e5..cc9aaab9134 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp
@@ -41,37 +41,35 @@
 #ifndef PB_DS_SAMPLE_RANGED_HASH_FN_HPP
 #define PB_DS_SAMPLE_RANGED_HASH_FN_HPP
 
-// A sample ranged-hash functor.
-class sample_ranged_hash_fn
+namespace __gnu_pbds
 {
+  /// A sample ranged-hash functor.
+  class sample_ranged_hash_fn
+  {
+  public:
+    typedef std::size_t size_type;
 
-public:
+    // Default constructor.
+    sample_ranged_hash_fn();
 
-  // Size type.
-  typedef std::size_t size_type;
+    // Copy constructor.
+    sample_ranged_hash_fn(const sample_ranged_hash_fn&);
 
-public:
+    // Swaps content.
+    inline void
+    swap(sample_ranged_hash_fn&);
 
-  // Default constructor.
-  sample_ranged_hash_fn();
+  protected:
 
-  // Copy constructor.
-  sample_ranged_hash_fn(const sample_ranged_hash_fn& other);
+    // Notifies the policy object that the container's __size has
+    // changed to size.
+    void
+    notify_resized(size_type);
 
-  // Swaps content.
-  inline void
-  swap(sample_ranged_hash_fn& other);
-
-protected:
-
-  // Notifies the policy object that the container's __size has changed to size.
-  void
-  notify_resized(size_type size);
-
-  // Transforms r_key into a position within the table.
-  inline size_type
-  operator()(const_key_reference r_key) const;
-
-};
+    // Transforms key_const_reference into a position within the table.
+    inline size_type
+    operator()(key_const_reference) const;
 
+  };
+}
 #endif // #ifndef PB_DS_SAMPLE_RANGED_HASH_FN_HPP
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp
index 2bcfdf51a54..b362f3d354f 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp
@@ -41,37 +41,37 @@
 #ifndef PB_DS_SAMPLE_RANGED_PROBE_FN_HPP
 #define PB_DS_SAMPLE_RANGED_PROBE_FN_HPP
 
-// A sample ranged-probe functor.
-class sample_ranged_probe_fn
+namespace __gnu_pbds
 {
+  /// A sample ranged-probe functor.
+  class sample_ranged_probe_fn
+  {
+  public:
+    typedef std::size_t 	size_type;
 
-public:
+    // Default constructor.
+    sample_ranged_probe_fn();
 
-  // Size type.
-  typedef std::size_t size_type;
+    // Copy constructor.
+    sample_ranged_probe_fn(const sample_ranged_probe_fn&);
 
-public:
+    // Swaps content.
+    inline void
+    swap(sample_ranged_probe_fn&);
 
-  // Default constructor.
-  sample_ranged_probe_fn();
+  protected:
 
-  // Copy constructor.
-  sample_ranged_probe_fn(const sample_ranged_probe_fn& other);
+    // Notifies the policy object that the container's __size has
+    // changed to size.
+    void
+    notify_resized(size_type);
 
-  // Swaps content.
-  inline void
-  swap(sample_ranged_probe_fn& other);
-
-protected:
-
-  // Notifies the policy object that the container's __size has changed to size.
-  void
-  notify_resized(size_type size);
-
-  // Transforms the const key reference r_key into the i-th position within the table. This method is called for each collision within the probe sequence.
-  inline size_type
-  operator()(const_key_reference r_key, std::size_t hash, size_type i) const;
-
-};
+    // Transforms the const key reference r_key into the i-th position
+    // within the table. This method is called for each collision within
+    // the probe sequence.
+    inline size_type
+    operator()(key_const_reference, std::size_t, size_type) const;
 
+  };
+}
 #endif // #ifndef PB_DS_SAMPLE_RANGED_PROBE_FN_HPP