diff options
author | bkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4> | 2011-05-24 02:38:19 +0000 |
---|---|---|
committer | bkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4> | 2011-05-24 02:38:19 +0000 |
commit | 4f4a327e5b45f8ece94996e6c5f6f29ce1b3d43e (patch) | |
tree | 3a3e2385c96d7603cc7578228f954bd4d03d73a4 /libstdc++-v3/include/ext/pb_ds/detail/hash_fn | |
parent | 10c3b4fd04a0b42e09228dba893c4bb11c5f2d77 (diff) | |
download | gcc-4f4a327e5b45f8ece94996e6c5f6f29ce1b3d43e.tar.gz |
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
Diffstat (limited to 'libstdc++-v3/include/ext/pb_ds/detail/hash_fn')
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 |