From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libstdc++-v3/include/ext/algorithm | 605 ++++ libstdc++-v3/include/ext/array_allocator.h | 157 ++ libstdc++-v3/include/ext/atomicity.h | 116 + libstdc++-v3/include/ext/bitmap_allocator.h | 1112 ++++++++ libstdc++-v3/include/ext/cast.h | 121 + libstdc++-v3/include/ext/codecvt_specializations.h | 514 ++++ libstdc++-v3/include/ext/concurrence.h | 401 +++ libstdc++-v3/include/ext/debug_allocator.h | 127 + libstdc++-v3/include/ext/enc_filebuf.h | 65 + libstdc++-v3/include/ext/extptr_allocator.h | 181 ++ libstdc++-v3/include/ext/functional | 427 +++ libstdc++-v3/include/ext/iterator | 116 + libstdc++-v3/include/ext/malloc_allocator.h | 137 + libstdc++-v3/include/ext/memory | 198 ++ libstdc++-v3/include/ext/mt_allocator.h | 754 +++++ libstdc++-v3/include/ext/new_allocator.h | 134 + libstdc++-v3/include/ext/numeric | 152 + libstdc++-v3/include/ext/numeric_traits.h | 138 + libstdc++-v3/include/ext/pb_ds/assoc_container.hpp | 700 +++++ .../basic_tree_policy/basic_tree_policy_base.hpp | 173 ++ .../basic_tree_policy/null_node_metadata.hpp | 67 + .../ext/pb_ds/detail/basic_tree_policy/traits.hpp | 85 + .../include/ext/pb_ds/detail/basic_types.hpp | 211 ++ .../detail/bin_search_tree_/bin_search_tree_.hpp | 497 ++++ .../bin_search_tree_/cond_dtor_entry_dealtor.hpp | 70 + .../cond_key_dtor_entry_dealtor.hpp | 81 + .../constructors_destructor_fn_imps.hpp | 219 ++ .../detail/bin_search_tree_/debug_fn_imps.hpp | 272 ++ .../detail/bin_search_tree_/erase_fn_imps.hpp | 120 + .../pb_ds/detail/bin_search_tree_/find_fn_imps.hpp | 182 ++ .../pb_ds/detail/bin_search_tree_/info_fn_imps.hpp | 64 + .../detail/bin_search_tree_/insert_fn_imps.hpp | 211 ++ .../detail/bin_search_tree_/iterators_fn_imps.hpp | 136 + .../detail/bin_search_tree_/node_iterators.hpp | 237 ++ .../detail/bin_search_tree_/point_iterators.hpp | 381 +++ .../bin_search_tree_/policy_access_fn_imps.hpp | 56 + .../detail/bin_search_tree_/r_erase_fn_imps.hpp | 120 + .../detail/bin_search_tree_/rotate_fn_imps.hpp | 156 + .../detail/bin_search_tree_/split_join_fn_imps.hpp | 146 + .../ext/pb_ds/detail/bin_search_tree_/traits.hpp | 250 ++ .../ext/pb_ds/detail/binary_heap_/binary_heap_.hpp | 357 +++ .../pb_ds/detail/binary_heap_/const_iterator.hpp | 152 + .../detail/binary_heap_/const_point_iterator.hpp | 144 + .../constructors_destructor_fn_imps.hpp | 159 ++ .../pb_ds/detail/binary_heap_/debug_fn_imps.hpp | 72 + .../ext/pb_ds/detail/binary_heap_/entry_cmp.hpp | 93 + .../ext/pb_ds/detail/binary_heap_/entry_pred.hpp | 93 + .../pb_ds/detail/binary_heap_/erase_fn_imps.hpp | 242 ++ .../ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp | 91 + .../ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp | 64 + .../pb_ds/detail/binary_heap_/insert_fn_imps.hpp | 183 ++ .../detail/binary_heap_/iterators_fn_imps.hpp | 72 + .../detail/binary_heap_/policy_access_fn_imps.hpp | 56 + .../pb_ds/detail/binary_heap_/resize_policy.hpp | 253 ++ .../detail/binary_heap_/split_join_fn_imps.hpp | 173 ++ .../pb_ds/detail/binary_heap_/trace_fn_imps.hpp | 78 + .../pb_ds/detail/binomial_heap_/binomial_heap_.hpp | 116 + .../constructors_destructor_fn_imps.hpp | 61 + .../pb_ds/detail/binomial_heap_/debug_fn_imps.hpp | 49 + .../binomial_heap_base_/binomial_heap_base_.hpp | 234 ++ .../constructors_destructor_fn_imps.hpp | 97 + .../detail/binomial_heap_base_/debug_fn_imps.hpp | 99 + .../detail/binomial_heap_base_/erase_fn_imps.hpp | 192 ++ .../detail/binomial_heap_base_/find_fn_imps.hpp | 73 + .../detail/binomial_heap_base_/insert_fn_imps.hpp | 216 ++ .../binomial_heap_base_/split_join_fn_imps.hpp | 232 ++ .../pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp | 636 +++++ .../detail/cc_hash_table_map_/cmp_fn_imps.hpp | 83 + .../cond_key_dtor_entry_dealtor.hpp | 117 + .../constructor_destructor_fn_imps.hpp | 192 ++ ...onstructor_destructor_no_store_hash_fn_imps.hpp | 55 + .../constructor_destructor_store_hash_fn_imps.hpp | 56 + .../detail/cc_hash_table_map_/debug_fn_imps.hpp | 74 + .../debug_no_store_hash_fn_imps.hpp | 49 + .../debug_store_hash_fn_imps.hpp | 53 + .../cc_hash_table_map_/entry_list_fn_imps.hpp | 91 + .../detail/cc_hash_table_map_/erase_fn_imps.hpp | 103 + .../erase_no_store_hash_fn_imps.hpp | 101 + .../erase_store_hash_fn_imps.hpp | 95 + .../detail/cc_hash_table_map_/find_fn_imps.hpp | 71 + .../cc_hash_table_map_/find_store_hash_fn_imps.hpp | 41 + .../detail/cc_hash_table_map_/info_fn_imps.hpp | 100 + .../detail/cc_hash_table_map_/insert_fn_imps.hpp | 43 + .../insert_no_store_hash_fn_imps.hpp | 70 + .../insert_store_hash_fn_imps.hpp | 71 + .../cc_hash_table_map_/iterators_fn_imps.hpp | 83 + .../cc_hash_table_map_/policy_access_fn_imps.hpp | 88 + .../detail/cc_hash_table_map_/resize_fn_imps.hpp | 134 + .../resize_no_store_hash_fn_imps.hpp | 54 + .../resize_store_hash_fn_imps.hpp | 54 + .../detail/cc_hash_table_map_/size_fn_imps.hpp | 59 + .../cc_hash_table_map_/standard_policies.hpp | 46 + .../detail/cc_hash_table_map_/trace_fn_imps.hpp | 72 + .../include/ext/pb_ds/detail/cond_dealtor.hpp | 125 + .../detail/constructors_destructor_fn_imps.hpp | 103 + .../ext/pb_ds/detail/container_base_dispatch.hpp | 332 +++ .../include/ext/pb_ds/detail/debug_map_base.hpp | 346 +++ .../include/ext/pb_ds/detail/eq_fn/eq_by_less.hpp | 68 + .../include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp | 179 ++ .../constructor_destructor_fn_imps.hpp | 223 ++ ...onstructor_destructor_no_store_hash_fn_imps.hpp | 53 + .../constructor_destructor_store_hash_fn_imps.hpp | 54 + .../detail/gp_hash_table_map_/debug_fn_imps.hpp | 55 + .../debug_no_store_hash_fn_imps.hpp | 71 + .../debug_store_hash_fn_imps.hpp | 77 + .../detail/gp_hash_table_map_/erase_fn_imps.hpp | 100 + .../erase_no_store_hash_fn_imps.hpp | 85 + .../erase_store_hash_fn_imps.hpp | 86 + .../detail/gp_hash_table_map_/find_fn_imps.hpp | 70 + .../find_no_store_hash_fn_imps.hpp | 46 + .../gp_hash_table_map_/find_store_hash_fn_imps.hpp | 40 + .../pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp | 677 +++++ .../detail/gp_hash_table_map_/info_fn_imps.hpp | 58 + .../detail/gp_hash_table_map_/insert_fn_imps.hpp | 43 + .../insert_no_store_hash_fn_imps.hpp | 111 + .../insert_store_hash_fn_imps.hpp | 118 + .../detail/gp_hash_table_map_/iterator_fn_imps.hpp | 83 + .../gp_hash_table_map_/policy_access_fn_imps.hpp | 100 + .../detail/gp_hash_table_map_/resize_fn_imps.hpp | 138 + .../resize_no_store_hash_fn_imps.hpp | 72 + .../resize_store_hash_fn_imps.hpp | 74 + .../gp_hash_table_map_/standard_policies.hpp | 74 + .../detail/gp_hash_table_map_/trace_fn_imps.hpp | 74 + .../hash_fn/direct_mask_range_hashing_imp.hpp | 58 + .../hash_fn/direct_mod_range_hashing_imp.hpp | 58 + .../pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp | 53 + .../detail/hash_fn/mask_based_range_hashing.hpp | 107 + .../detail/hash_fn/mod_based_range_hashing.hpp | 108 + .../ext/pb_ds/detail/hash_fn/probe_fn_base.hpp | 59 + .../detail/hash_fn/quadratic_probe_fn_imp.hpp | 53 + .../ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp | 359 +++ .../ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp | 327 +++ .../ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp | 73 + .../pb_ds/detail/hash_fn/sample_range_hashing.hpp | 77 + .../pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp | 77 + .../detail/hash_fn/sample_ranged_probe_fn.hpp | 77 + .../const_iterator.hpp | 162 ++ .../const_point_iterator.hpp | 154 + .../constructors_destructor_fn_imps.hpp | 153 + .../debug_fn_imps.hpp | 141 + .../erase_fn_imps.hpp | 150 + .../left_child_next_sibling_heap_/info_fn_imps.hpp | 64 + .../insert_fn_imps.hpp | 175 ++ .../iterators_fn_imps.hpp | 88 + .../left_child_next_sibling_heap_.hpp | 349 +++ .../detail/left_child_next_sibling_heap_/node.hpp | 123 + .../null_metadata.hpp | 55 + .../policy_access_fn_imps.hpp | 52 + .../trace_fn_imps.hpp | 95 + .../constructor_destructor_fn_imps.hpp | 142 + .../detail/list_update_map_/debug_fn_imps.hpp | 57 + .../list_update_map_/entry_metadata_base.hpp | 60 + .../detail/list_update_map_/erase_fn_imps.hpp | 135 + .../pb_ds/detail/list_update_map_/find_fn_imps.hpp | 90 + .../pb_ds/detail/list_update_map_/info_fn_imps.hpp | 57 + .../detail/list_update_map_/insert_fn_imps.hpp | 106 + .../detail/list_update_map_/iterators_fn_imps.hpp | 80 + .../ext/pb_ds/detail/list_update_map_/lu_map_.hpp | 359 +++ .../detail/list_update_map_/trace_fn_imps.hpp | 59 + .../list_update_policy/counter_lu_metadata.hpp | 86 + .../list_update_policy/counter_lu_policy_imp.hpp | 51 + .../list_update_policy/mtf_lu_policy_imp.hpp | 55 + .../list_update_policy/sample_update_policy.hpp | 74 + .../ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp | 74 + .../constructors_destructor_fn_imps.hpp | 273 ++ .../pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp | 83 + .../pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp | 193 ++ .../ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp | 60 + .../pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp | 63 + .../detail/ov_tree_map_/iterators_fn_imps.hpp | 103 + .../pb_ds/detail/ov_tree_map_/node_iterators.hpp | 292 ++ .../ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp | 522 ++++ .../detail/ov_tree_map_/policy_access_fn_imps.hpp | 51 + .../detail/ov_tree_map_/split_join_fn_imps.hpp | 137 + .../ext/pb_ds/detail/ov_tree_map_/traits.hpp | 183 ++ .../constructors_destructor_fn_imps.hpp | 91 + .../pb_ds/detail/pairing_heap_/debug_fn_imps.hpp | 53 + .../pb_ds/detail/pairing_heap_/erase_fn_imps.hpp | 236 ++ .../pb_ds/detail/pairing_heap_/find_fn_imps.hpp | 50 + .../pb_ds/detail/pairing_heap_/insert_fn_imps.hpp | 101 + .../pb_ds/detail/pairing_heap_/pairing_heap_.hpp | 216 ++ .../detail/pairing_heap_/split_join_fn_imps.hpp | 140 + .../ext/pb_ds/detail/pat_trie_/child_iterator.hpp | 93 + .../detail/pat_trie_/cond_dtor_entry_dealtor.hpp | 79 + .../detail/pat_trie_/const_child_iterator.hpp | 111 + .../pat_trie_/constructors_destructor_fn_imps.hpp | 215 ++ .../ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp | 117 + .../ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp | 319 +++ .../ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp | 269 ++ .../include/ext/pb_ds/detail/pat_trie_/head.hpp | 124 + .../ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp | 58 + .../pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp | 465 +++ .../ext/pb_ds/detail/pat_trie_/internal_node.hpp | 599 ++++ .../pb_ds/detail/pat_trie_/iterators_fn_imps.hpp | 120 + .../include/ext/pb_ds/detail/pat_trie_/leaf.hpp | 171 ++ .../ext/pb_ds/detail/pat_trie_/node_base.hpp | 128 + .../ext/pb_ds/detail/pat_trie_/node_iterators.hpp | 338 +++ .../pb_ds/detail/pat_trie_/node_metadata_base.hpp | 86 + .../ext/pb_ds/detail/pat_trie_/pat_trie_.hpp | 515 ++++ .../ext/pb_ds/detail/pat_trie_/point_iterators.hpp | 484 ++++ .../detail/pat_trie_/policy_access_fn_imps.hpp | 63 + .../ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp | 103 + .../ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp | 150 + .../ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp | 254 ++ .../detail/pat_trie_/split_join_branch_bag.hpp | 93 + .../detail/pat_trie_/synth_e_access_traits.hpp | 229 ++ .../ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp | 113 + .../include/ext/pb_ds/detail/pat_trie_/traits.hpp | 350 +++ .../ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp | 55 + .../pb_ds/detail/priority_queue_base_dispatch.hpp | 91 + .../constructors_destructor_fn_imps.hpp | 100 + .../pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp | 78 + .../pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp | 289 ++ .../ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp | 39 + .../ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp | 46 + .../pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp | 115 + .../include/ext/pb_ds/detail/rb_tree_map_/node.hpp | 138 + .../ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp | 280 ++ .../detail/rb_tree_map_/split_join_fn_imps.hpp | 313 ++ .../ext/pb_ds/detail/rb_tree_map_/traits.hpp | 124 + .../constructors_destructor_fn_imps.hpp | 88 + .../detail/rc_binomial_heap_/debug_fn_imps.hpp | 121 + .../detail/rc_binomial_heap_/erase_fn_imps.hpp | 107 + .../detail/rc_binomial_heap_/insert_fn_imps.hpp | 154 + .../ext/pb_ds/detail/rc_binomial_heap_/rc.hpp | 262 ++ .../detail/rc_binomial_heap_/rc_binomial_heap_.hpp | 198 ++ .../rc_binomial_heap_/split_join_fn_imps.hpp | 81 + .../detail/rc_binomial_heap_/trace_fn_imps.hpp | 53 + ...hash_max_collision_check_resize_trigger_imp.hpp | 211 ++ .../hash_exponential_size_policy_imp.hpp | 90 + .../hash_load_check_resize_trigger_imp.hpp | 283 ++ .../hash_load_check_resize_trigger_size_base.hpp | 94 + .../resize_policy/hash_prime_size_policy_imp.hpp | 161 ++ .../hash_standard_resize_policy_imp.hpp | 249 ++ .../detail/resize_policy/sample_resize_policy.hpp | 125 + .../detail/resize_policy/sample_resize_trigger.hpp | 138 + .../detail/resize_policy/sample_size_policy.hpp | 73 + .../constructors_destructor_fn_imps.hpp | 102 + .../ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp | 74 + .../ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp | 157 ++ .../ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp | 99 + .../ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp | 39 + .../pb_ds/detail/splay_tree_/insert_fn_imps.hpp | 93 + .../include/ext/pb_ds/detail/splay_tree_/node.hpp | 125 + .../ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp | 283 ++ .../ext/pb_ds/detail/splay_tree_/splay_tree_.hpp | 298 ++ .../detail/splay_tree_/split_join_fn_imps.hpp | 112 + .../ext/pb_ds/detail/splay_tree_/traits.hpp | 113 + .../include/ext/pb_ds/detail/standard_policies.hpp | 136 + .../thin_heap_/constructors_destructor_fn_imps.hpp | 106 + .../ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp | 112 + .../ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp | 296 ++ .../ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp | 51 + .../ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp | 326 +++ .../pb_ds/detail/thin_heap_/split_join_fn_imps.hpp | 126 + .../ext/pb_ds/detail/thin_heap_/thin_heap_.hpp | 351 +++ .../ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp | 55 + .../detail/tree_policy/node_metadata_selector.hpp | 116 + .../detail/tree_policy/null_node_update_imp.hpp | 50 + .../detail/tree_policy/order_statistics_imp.hpp | 141 + .../detail/tree_policy/sample_tree_node_update.hpp | 72 + .../include/ext/pb_ds/detail/tree_trace_base.hpp | 209 ++ .../detail/trie_policy/node_metadata_selector.hpp | 116 + .../detail/trie_policy/null_node_update_imp.hpp | 50 + .../detail/trie_policy/order_statistics_imp.hpp | 181 ++ .../trie_policy/prefix_search_node_update_imp.hpp | 151 + .../trie_policy/sample_trie_e_access_traits.hpp | 89 + .../detail/trie_policy/sample_trie_node_update.hpp | 72 + .../string_trie_e_access_traits_imp.hpp | 99 + .../pb_ds/detail/trie_policy/trie_policy_base.hpp | 249 ++ .../include/ext/pb_ds/detail/type_utils.hpp | 167 ++ .../include/ext/pb_ds/detail/types_traits.hpp | 82 + .../detail/unordered_iterator/const_iterator.hpp | 129 + .../unordered_iterator/const_point_iterator.hpp | 151 + .../pb_ds/detail/unordered_iterator/iterator.hpp | 150 + .../detail/unordered_iterator/point_iterator.hpp | 143 + libstdc++-v3/include/ext/pb_ds/exception.hpp | 105 + libstdc++-v3/include/ext/pb_ds/hash_policy.hpp | 605 ++++ .../include/ext/pb_ds/list_update_policy.hpp | 139 + libstdc++-v3/include/ext/pb_ds/priority_queue.hpp | 129 + libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp | 364 +++ libstdc++-v3/include/ext/pb_ds/tree_policy.hpp | 163 ++ libstdc++-v3/include/ext/pb_ds/trie_policy.hpp | 356 +++ libstdc++-v3/include/ext/pod_char_traits.h | 188 ++ libstdc++-v3/include/ext/pointer.h | 570 ++++ libstdc++-v3/include/ext/pool_allocator.h | 266 ++ libstdc++-v3/include/ext/rb_tree | 96 + libstdc++-v3/include/ext/rc_string_base.h | 733 +++++ libstdc++-v3/include/ext/rope | 2976 ++++++++++++++++++++ libstdc++-v3/include/ext/ropeimpl.h | 1704 +++++++++++ libstdc++-v3/include/ext/slist | 1083 +++++++ libstdc++-v3/include/ext/sso_string_base.h | 577 ++++ libstdc++-v3/include/ext/stdio_filebuf.h | 162 ++ libstdc++-v3/include/ext/stdio_sync_filebuf.h | 290 ++ libstdc++-v3/include/ext/string_conversions.h | 101 + libstdc++-v3/include/ext/throw_allocator.h | 765 +++++ libstdc++-v3/include/ext/type_traits.h | 214 ++ libstdc++-v3/include/ext/typelist.h | 554 ++++ libstdc++-v3/include/ext/vstring.h | 2796 ++++++++++++++++++ libstdc++-v3/include/ext/vstring.tcc | 702 +++++ libstdc++-v3/include/ext/vstring_fwd.h | 90 + libstdc++-v3/include/ext/vstring_util.h | 184 ++ 302 files changed, 58730 insertions(+) create mode 100644 libstdc++-v3/include/ext/algorithm create mode 100644 libstdc++-v3/include/ext/array_allocator.h create mode 100644 libstdc++-v3/include/ext/atomicity.h create mode 100644 libstdc++-v3/include/ext/bitmap_allocator.h create mode 100644 libstdc++-v3/include/ext/cast.h create mode 100644 libstdc++-v3/include/ext/codecvt_specializations.h create mode 100644 libstdc++-v3/include/ext/concurrence.h create mode 100644 libstdc++-v3/include/ext/debug_allocator.h create mode 100644 libstdc++-v3/include/ext/enc_filebuf.h create mode 100644 libstdc++-v3/include/ext/extptr_allocator.h create mode 100644 libstdc++-v3/include/ext/functional create mode 100644 libstdc++-v3/include/ext/iterator create mode 100644 libstdc++-v3/include/ext/malloc_allocator.h create mode 100644 libstdc++-v3/include/ext/memory create mode 100644 libstdc++-v3/include/ext/mt_allocator.h create mode 100644 libstdc++-v3/include/ext/new_allocator.h create mode 100644 libstdc++-v3/include/ext/numeric create mode 100644 libstdc++-v3/include/ext/numeric_traits.h create mode 100644 libstdc++-v3/include/ext/pb_ds/assoc_container.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/basic_types.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/standard_policies.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/cond_dealtor.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/container_base_dispatch.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/eq_fn/eq_by_less.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/standard_policies.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_probe_fn.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/counter_lu_metadata.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/counter_lu_policy_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/mtf_lu_policy_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/sample_update_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/tree_policy/null_node_update_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/tree_policy/sample_tree_node_update.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/tree_trace_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/null_node_update_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_e_access_traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/type_utils.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/exception.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/hash_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/priority_queue.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/tree_policy.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/trie_policy.hpp create mode 100644 libstdc++-v3/include/ext/pod_char_traits.h create mode 100644 libstdc++-v3/include/ext/pointer.h create mode 100644 libstdc++-v3/include/ext/pool_allocator.h create mode 100644 libstdc++-v3/include/ext/rb_tree create mode 100644 libstdc++-v3/include/ext/rc_string_base.h create mode 100644 libstdc++-v3/include/ext/rope create mode 100644 libstdc++-v3/include/ext/ropeimpl.h create mode 100644 libstdc++-v3/include/ext/slist create mode 100644 libstdc++-v3/include/ext/sso_string_base.h create mode 100644 libstdc++-v3/include/ext/stdio_filebuf.h create mode 100644 libstdc++-v3/include/ext/stdio_sync_filebuf.h create mode 100644 libstdc++-v3/include/ext/string_conversions.h create mode 100644 libstdc++-v3/include/ext/throw_allocator.h create mode 100644 libstdc++-v3/include/ext/type_traits.h create mode 100644 libstdc++-v3/include/ext/typelist.h create mode 100644 libstdc++-v3/include/ext/vstring.h create mode 100644 libstdc++-v3/include/ext/vstring.tcc create mode 100644 libstdc++-v3/include/ext/vstring_fwd.h create mode 100644 libstdc++-v3/include/ext/vstring_util.h (limited to 'libstdc++-v3/include/ext') diff --git a/libstdc++-v3/include/ext/algorithm b/libstdc++-v3/include/ext/algorithm new file mode 100644 index 000000000..417a03ab9 --- /dev/null +++ b/libstdc++-v3/include/ext/algorithm @@ -0,0 +1,605 @@ +// Algorithm extensions -*- C++ -*- + +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, +// 2009, 2010, 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1996 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +/** @file ext/algorithm + * This file is a GNU extension to the Standard C++ Library (possibly + * containing extensions from the HP/SGI STL subset). + */ + +#ifndef _EXT_ALGORITHM +#define _EXT_ALGORITHM 1 + +#pragma GCC system_header + +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::ptrdiff_t; + using std::min; + using std::pair; + using std::input_iterator_tag; + using std::random_access_iterator_tag; + using std::iterator_traits; + + //-------------------------------------------------- + // copy_n (not part of the C++ standard) + + template + pair<_InputIterator, _OutputIterator> + __copy_n(_InputIterator __first, _Size __count, + _OutputIterator __result, + input_iterator_tag) + { + for ( ; __count > 0; --__count) + { + *__result = *__first; + ++__first; + ++__result; + } + return pair<_InputIterator, _OutputIterator>(__first, __result); + } + + template + inline pair<_RAIterator, _OutputIterator> + __copy_n(_RAIterator __first, _Size __count, + _OutputIterator __result, + random_access_iterator_tag) + { + _RAIterator __last = __first + __count; + return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, + __last, + __result)); + } + + /** + * @brief Copies the range [first,first+count) into [result,result+count). + * @param first An input iterator. + * @param count The number of elements to copy. + * @param result An output iterator. + * @return A std::pair composed of first+count and result+count. + * + * This is an SGI extension. + * This inline function will boil down to a call to @c memmove whenever + * possible. Failing that, if random access iterators are passed, then the + * loop count will be known (and therefore a candidate for compiler + * optimizations such as unrolling). + * @ingroup SGIextensions + */ + template + inline pair<_InputIterator, _OutputIterator> + copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_InputIterator>::value_type>) + + return __gnu_cxx::__copy_n(__first, __count, __result, + std::__iterator_category(__first)); + } + + template + int + __lexicographical_compare_3way(_InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2) + { + while (__first1 != __last1 && __first2 != __last2) + { + if (*__first1 < *__first2) + return -1; + if (*__first2 < *__first1) + return 1; + ++__first1; + ++__first2; + } + if (__first2 == __last2) + return !(__first1 == __last1); + else + return -1; + } + + inline int + __lexicographical_compare_3way(const unsigned char* __first1, + const unsigned char* __last1, + const unsigned char* __first2, + const unsigned char* __last2) + { + const ptrdiff_t __len1 = __last1 - __first1; + const ptrdiff_t __len2 = __last2 - __first2; + const int __result = __builtin_memcmp(__first1, __first2, + min(__len1, __len2)); + return __result != 0 ? __result + : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); + } + + inline int + __lexicographical_compare_3way(const char* __first1, const char* __last1, + const char* __first2, const char* __last2) + { +#if CHAR_MAX == SCHAR_MAX + return __lexicographical_compare_3way((const signed char*) __first1, + (const signed char*) __last1, + (const signed char*) __first2, + (const signed char*) __last2); +#else + return __lexicographical_compare_3way((const unsigned char*) __first1, + (const unsigned char*) __last1, + (const unsigned char*) __first2, + (const unsigned char*) __last2); +#endif + } + + /** + * @brief @c memcmp on steroids. + * @param first1 An input iterator. + * @param last1 An input iterator. + * @param first2 An input iterator. + * @param last2 An input iterator. + * @return An int, as with @c memcmp. + * + * The return value will be less than zero if the first range is + * lexigraphically less than the second, greater than zero + * if the second range is lexigraphically less than the + * first, and zero otherwise. + * This is an SGI extension. + * @ingroup SGIextensions + */ + template + int + lexicographical_compare_3way(_InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_InputIterator1>::value_type>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_InputIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + return __lexicographical_compare_3way(__first1, __last1, __first2, + __last2); + } + + // count and count_if: this version, whose return type is void, was present + // in the HP STL, and is retained as an extension for backward compatibility. + template + void + count(_InputIterator __first, _InputIterator __last, + const _Tp& __value, + _Size& __n) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_EqualityComparableConcept< + typename iterator_traits<_InputIterator>::value_type >) + __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_requires_valid_range(__first, __last); + + for ( ; __first != __last; ++__first) + if (*__first == __value) + ++__n; + } + + template + void + count_if(_InputIterator __first, _InputIterator __last, + _Predicate __pred, + _Size& __n) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + for ( ; __first != __last; ++__first) + if (__pred(*__first)) + ++__n; + } + + // random_sample and random_sample_n (extensions, not part of the standard). + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + _OutputIterator + random_sample_n(_ForwardIterator __first, _ForwardIterator __last, + _OutputIterator __out, const _Distance __n) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + _Distance __remaining = std::distance(__first, __last); + _Distance __m = min(__n, __remaining); + + while (__m > 0) + { + if ((std::rand() % __remaining) < __m) + { + *__out = *__first; + ++__out; + --__m; + } + --__remaining; + ++__first; + } + return __out; + } + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + _OutputIterator + random_sample_n(_ForwardIterator __first, _ForwardIterator __last, + _OutputIterator __out, const _Distance __n, + _RandomNumberGenerator& __rand) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_function_requires(_UnaryFunctionConcept< + _RandomNumberGenerator, _Distance, _Distance>) + __glibcxx_requires_valid_range(__first, __last); + + _Distance __remaining = std::distance(__first, __last); + _Distance __m = min(__n, __remaining); + + while (__m > 0) + { + if (__rand(__remaining) < __m) + { + *__out = *__first; + ++__out; + --__m; + } + --__remaining; + ++__first; + } + return __out; + } + + template + _RandomAccessIterator + __random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out, + const _Distance __n) + { + _Distance __m = 0; + _Distance __t = __n; + for ( ; __first != __last && __m < __n; ++__m, ++__first) + __out[__m] = *__first; + + while (__first != __last) + { + ++__t; + _Distance __M = std::rand() % (__t); + if (__M < __n) + __out[__M] = *__first; + ++__first; + } + return __out + __m; + } + + template + _RandomAccessIterator + __random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out, + _RandomNumberGenerator& __rand, + const _Distance __n) + { + // concept requirements + __glibcxx_function_requires(_UnaryFunctionConcept< + _RandomNumberGenerator, _Distance, _Distance>) + + _Distance __m = 0; + _Distance __t = __n; + for ( ; __first != __last && __m < __n; ++__m, ++__first) + __out[__m] = *__first; + + while (__first != __last) + { + ++__t; + _Distance __M = __rand(__t); + if (__M < __n) + __out[__M] = *__first; + ++__first; + } + return __out + __m; + } + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + inline _RandomAccessIterator + random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out_first, + _RandomAccessIterator __out_last) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_valid_range(__out_first, __out_last); + + return __random_sample(__first, __last, + __out_first, __out_last - __out_first); + } + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + inline _RandomAccessIterator + random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out_first, + _RandomAccessIterator __out_last, + _RandomNumberGenerator& __rand) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_valid_range(__out_first, __out_last); + + return __random_sample(__first, __last, + __out_first, __rand, + __out_last - __out_first); + } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + using std::is_heap; +#else + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + inline bool + is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) + { + // concept requirements + __glibcxx_function_requires(_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_RandomAccessIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + return std::__is_heap(__first, __last - __first); + } + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + inline bool + is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, + _StrictWeakOrdering __comp) + { + // concept requirements + __glibcxx_function_requires(_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_RandomAccessIterator>::value_type, + typename iterator_traits<_RandomAccessIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + return std::__is_heap(__first, __comp, __last - __first); + } +#endif + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + using std::is_sorted; +#else + // is_sorted, a predicated testing whether a range is sorted in + // nondescending order. This is an extension, not part of the C++ + // standard. + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + bool + is_sorted(_ForwardIterator __first, _ForwardIterator __last) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return true; + + _ForwardIterator __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) + if (*__next < *__first) + return false; + return true; + } + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + bool + is_sorted(_ForwardIterator __first, _ForwardIterator __last, + _StrictWeakOrdering __comp) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return true; + + _ForwardIterator __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) + if (__comp(*__next, *__first)) + return false; + return true; + } +#endif // __GXX_EXPERIMENTAL_CXX0X__ + + /** + * @brief Find the median of three values. + * @param a A value. + * @param b A value. + * @param c A value. + * @return One of @p a, @p b or @p c. + * + * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n + * then the value returned will be @c m. + * This is an SGI extension. + * @ingroup SGIextensions + */ + template + const _Tp& + __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) + { + // concept requirements + __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + if (__a < __b) + if (__b < __c) + return __b; + else if (__a < __c) + return __c; + else + return __a; + else if (__a < __c) + return __a; + else if (__b < __c) + return __c; + else + return __b; + } + + /** + * @brief Find the median of three values using a predicate for comparison. + * @param a A value. + * @param b A value. + * @param c A value. + * @param comp A binary predicate. + * @return One of @p a, @p b or @p c. + * + * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) + * and @p comp(m,n) are both true then the value returned will be @c m. + * This is an SGI extension. + * @ingroup SGIextensions + */ + template + const _Tp& + __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, + _Tp, _Tp>) + if (__comp(__a, __b)) + if (__comp(__b, __c)) + return __b; + else if (__comp(__a, __c)) + return __c; + else + return __a; + else if (__comp(__a, __c)) + return __a; + else if (__comp(__b, __c)) + return __c; + else + return __b; + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif /* _EXT_ALGORITHM */ diff --git a/libstdc++-v3/include/ext/array_allocator.h b/libstdc++-v3/include/ext/array_allocator.h new file mode 100644 index 000000000..9c61d7431 --- /dev/null +++ b/libstdc++-v3/include/ext/array_allocator.h @@ -0,0 +1,157 @@ +// array allocator -*- C++ -*- + +// Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/array_allocator.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _ARRAY_ALLOCATOR_H +#define _ARRAY_ALLOCATOR_H 1 + +#include +#include +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::size_t; + using std::ptrdiff_t; + + /// Base class. + template + class array_allocator_base + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef const _Tp* const_pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + + pointer + address(reference __x) const { return std::__addressof(__x); } + + const_pointer + address(const_reference __x) const { return std::__addressof(__x); } + + void + deallocate(pointer, size_type) + { + // Does nothing. + } + + size_type + max_size() const throw() + { return size_t(-1) / sizeof(_Tp); } + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 402. wrong new expression in [some_] allocator::construct + void + construct(pointer __p, const _Tp& __val) + { ::new((void *)__p) value_type(__val); } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + void + construct(pointer __p, _Args&&... __args) + { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); } +#endif + + void + destroy(pointer __p) { __p->~_Tp(); } + }; + + /** + * @brief An allocator that uses previously allocated memory. + * This memory can be externally, globally, or otherwise allocated. + * @ingroup allocators + */ + template > + class array_allocator : public array_allocator_base<_Tp> + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef const _Tp* const_pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + typedef _Array array_type; + + private: + array_type* _M_array; + size_type _M_used; + + public: + template + struct rebind + { typedef array_allocator<_Tp1, _Array1> other; }; + + array_allocator(array_type* __array = 0) throw() + : _M_array(__array), _M_used(size_type()) { } + + array_allocator(const array_allocator& __o) throw() + : _M_array(__o._M_array), _M_used(__o._M_used) { } + + template + array_allocator(const array_allocator<_Tp1, _Array1>&) throw() + : _M_array(0), _M_used(size_type()) { } + + ~array_allocator() throw() { } + + pointer + allocate(size_type __n, const void* = 0) + { + if (_M_array == 0 || _M_used + __n > _M_array->size()) + std::__throw_bad_alloc(); + pointer __ret = _M_array->begin() + _M_used; + _M_used += __n; + return __ret; + } + }; + + template + inline bool + operator==(const array_allocator<_Tp, _Array>&, + const array_allocator<_Tp, _Array>&) + { return true; } + + template + inline bool + operator!=(const array_allocator<_Tp, _Array>&, + const array_allocator<_Tp, _Array>&) + { return false; } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif diff --git a/libstdc++-v3/include/ext/atomicity.h b/libstdc++-v3/include/ext/atomicity.h new file mode 100644 index 000000000..f0c775216 --- /dev/null +++ b/libstdc++-v3/include/ext/atomicity.h @@ -0,0 +1,116 @@ +// Support for atomic operations -*- C++ -*- + +// Copyright (C) 2004, 2005, 2006, 2008, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/atomicity.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _GLIBCXX_ATOMICITY_H +#define _GLIBCXX_ATOMICITY_H 1 + +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // Functions for portable atomic access. + // To abstract locking primitives across all thread policies, use: + // __exchange_and_add_dispatch + // __atomic_add_dispatch +#ifdef _GLIBCXX_ATOMIC_BUILTINS_4 + static inline _Atomic_word + __exchange_and_add(volatile _Atomic_word* __mem, int __val) + { return __sync_fetch_and_add(__mem, __val); } + + static inline void + __atomic_add(volatile _Atomic_word* __mem, int __val) + { __sync_fetch_and_add(__mem, __val); } +#else + _Atomic_word + __attribute__ ((__unused__)) + __exchange_and_add(volatile _Atomic_word*, int) throw (); + + void + __attribute__ ((__unused__)) + __atomic_add(volatile _Atomic_word*, int) throw (); +#endif + + static inline _Atomic_word + __exchange_and_add_single(_Atomic_word* __mem, int __val) + { + _Atomic_word __result = *__mem; + *__mem += __val; + return __result; + } + + static inline void + __atomic_add_single(_Atomic_word* __mem, int __val) + { *__mem += __val; } + + static inline _Atomic_word + __attribute__ ((__unused__)) + __exchange_and_add_dispatch(_Atomic_word* __mem, int __val) + { +#ifdef __GTHREADS + if (__gthread_active_p()) + return __exchange_and_add(__mem, __val); + else + return __exchange_and_add_single(__mem, __val); +#else + return __exchange_and_add_single(__mem, __val); +#endif + } + + static inline void + __attribute__ ((__unused__)) + __atomic_add_dispatch(_Atomic_word* __mem, int __val) + { +#ifdef __GTHREADS + if (__gthread_active_p()) + __atomic_add(__mem, __val); + else + __atomic_add_single(__mem, __val); +#else + __atomic_add_single(__mem, __val); +#endif + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +// Even if the CPU doesn't need a memory barrier, we need to ensure +// that the compiler doesn't reorder memory accesses across the +// barriers. +#ifndef _GLIBCXX_READ_MEM_BARRIER +#define _GLIBCXX_READ_MEM_BARRIER __asm __volatile ("":::"memory") +#endif +#ifndef _GLIBCXX_WRITE_MEM_BARRIER +#define _GLIBCXX_WRITE_MEM_BARRIER __asm __volatile ("":::"memory") +#endif + +#endif diff --git a/libstdc++-v3/include/ext/bitmap_allocator.h b/libstdc++-v3/include/ext/bitmap_allocator.h new file mode 100644 index 000000000..4993c2c57 --- /dev/null +++ b/libstdc++-v3/include/ext/bitmap_allocator.h @@ -0,0 +1,1112 @@ +// Bitmap Allocator. -*- C++ -*- + +// Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/bitmap_allocator.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _BITMAP_ALLOCATOR_H +#define _BITMAP_ALLOCATOR_H 1 + +#include // For std::pair. +#include // For __throw_bad_alloc(). +#include // For greater_equal, and less_equal. +#include // For operator new. +#include // _GLIBCXX_DEBUG_ASSERT +#include +#include + +/** @brief The constant in the expression below is the alignment + * required in bytes. + */ +#define _BALLOC_ALIGN_BYTES 8 + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ + using std::size_t; + using std::ptrdiff_t; + + namespace __detail + { + _GLIBCXX_BEGIN_NAMESPACE_VERSION + /** @class __mini_vector bitmap_allocator.h bitmap_allocator.h + * + * @brief __mini_vector<> is a stripped down version of the + * full-fledged std::vector<>. + * + * It is to be used only for built-in types or PODs. Notable + * differences are: + * + * @detail + * 1. Not all accessor functions are present. + * 2. Used ONLY for PODs. + * 3. No Allocator template argument. Uses ::operator new() to get + * memory, and ::operator delete() to free it. + * Caveat: The dtor does NOT free the memory allocated, so this a + * memory-leaking vector! + */ + template + class __mini_vector + { + __mini_vector(const __mini_vector&); + __mini_vector& operator=(const __mini_vector&); + + public: + typedef _Tp value_type; + typedef _Tp* pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef pointer iterator; + + private: + pointer _M_start; + pointer _M_finish; + pointer _M_end_of_storage; + + size_type + _M_space_left() const throw() + { return _M_end_of_storage - _M_finish; } + + pointer + allocate(size_type __n) + { return static_cast(::operator new(__n * sizeof(_Tp))); } + + void + deallocate(pointer __p, size_type) + { ::operator delete(__p); } + + public: + // Members used: size(), push_back(), pop_back(), + // insert(iterator, const_reference), erase(iterator), + // begin(), end(), back(), operator[]. + + __mini_vector() + : _M_start(0), _M_finish(0), _M_end_of_storage(0) { } + + size_type + size() const throw() + { return _M_finish - _M_start; } + + iterator + begin() const throw() + { return this->_M_start; } + + iterator + end() const throw() + { return this->_M_finish; } + + reference + back() const throw() + { return *(this->end() - 1); } + + reference + operator[](const size_type __pos) const throw() + { return this->_M_start[__pos]; } + + void + insert(iterator __pos, const_reference __x); + + void + push_back(const_reference __x) + { + if (this->_M_space_left()) + { + *this->end() = __x; + ++this->_M_finish; + } + else + this->insert(this->end(), __x); + } + + void + pop_back() throw() + { --this->_M_finish; } + + void + erase(iterator __pos) throw(); + + void + clear() throw() + { this->_M_finish = this->_M_start; } + }; + + // Out of line function definitions. + template + void __mini_vector<_Tp>:: + insert(iterator __pos, const_reference __x) + { + if (this->_M_space_left()) + { + size_type __to_move = this->_M_finish - __pos; + iterator __dest = this->end(); + iterator __src = this->end() - 1; + + ++this->_M_finish; + while (__to_move) + { + *__dest = *__src; + --__dest; --__src; --__to_move; + } + *__pos = __x; + } + else + { + size_type __new_size = this->size() ? this->size() * 2 : 1; + iterator __new_start = this->allocate(__new_size); + iterator __first = this->begin(); + iterator __start = __new_start; + while (__first != __pos) + { + *__start = *__first; + ++__start; ++__first; + } + *__start = __x; + ++__start; + while (__first != this->end()) + { + *__start = *__first; + ++__start; ++__first; + } + if (this->_M_start) + this->deallocate(this->_M_start, this->size()); + + this->_M_start = __new_start; + this->_M_finish = __start; + this->_M_end_of_storage = this->_M_start + __new_size; + } + } + + template + void __mini_vector<_Tp>:: + erase(iterator __pos) throw() + { + while (__pos + 1 != this->end()) + { + *__pos = __pos[1]; + ++__pos; + } + --this->_M_finish; + } + + + template + struct __mv_iter_traits + { + typedef typename _Tp::value_type value_type; + typedef typename _Tp::difference_type difference_type; + }; + + template + struct __mv_iter_traits<_Tp*> + { + typedef _Tp value_type; + typedef ptrdiff_t difference_type; + }; + + enum + { + bits_per_byte = 8, + bits_per_block = sizeof(size_t) * size_t(bits_per_byte) + }; + + template + _ForwardIterator + __lower_bound(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val, _Compare __comp) + { + typedef typename __mv_iter_traits<_ForwardIterator>::value_type + _ValueType; + typedef typename __mv_iter_traits<_ForwardIterator>::difference_type + _DistanceType; + + _DistanceType __len = __last - __first; + _DistanceType __half; + _ForwardIterator __middle; + + while (__len > 0) + { + __half = __len >> 1; + __middle = __first; + __middle += __half; + if (__comp(*__middle, __val)) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + + /** @brief The number of Blocks pointed to by the address pair + * passed to the function. + */ + template + inline size_t + __num_blocks(_AddrPair __ap) + { return (__ap.second - __ap.first) + 1; } + + /** @brief The number of Bit-maps pointed to by the address pair + * passed to the function. + */ + template + inline size_t + __num_bitmaps(_AddrPair __ap) + { return __num_blocks(__ap) / size_t(bits_per_block); } + + // _Tp should be a pointer type. + template + class _Inclusive_between + : public std::unary_function, bool> + { + typedef _Tp pointer; + pointer _M_ptr_value; + typedef typename std::pair<_Tp, _Tp> _Block_pair; + + public: + _Inclusive_between(pointer __ptr) : _M_ptr_value(__ptr) + { } + + bool + operator()(_Block_pair __bp) const throw() + { + if (std::less_equal()(_M_ptr_value, __bp.second) + && std::greater_equal()(_M_ptr_value, __bp.first)) + return true; + else + return false; + } + }; + + // Used to pass a Functor to functions by reference. + template + class _Functor_Ref + : public std::unary_function + { + _Functor& _M_fref; + + public: + typedef typename _Functor::argument_type argument_type; + typedef typename _Functor::result_type result_type; + + _Functor_Ref(_Functor& __fref) : _M_fref(__fref) + { } + + result_type + operator()(argument_type __arg) + { return _M_fref(__arg); } + }; + + /** @class _Ffit_finder bitmap_allocator.h bitmap_allocator.h + * + * @brief The class which acts as a predicate for applying the + * first-fit memory allocation policy for the bitmap allocator. + */ + // _Tp should be a pointer type, and _Alloc is the Allocator for + // the vector. + template + class _Ffit_finder + : public std::unary_function, bool> + { + typedef typename std::pair<_Tp, _Tp> _Block_pair; + typedef typename __detail::__mini_vector<_Block_pair> _BPVector; + typedef typename _BPVector::difference_type _Counter_type; + + size_t* _M_pbitmap; + _Counter_type _M_data_offset; + + public: + _Ffit_finder() : _M_pbitmap(0), _M_data_offset(0) + { } + + bool + operator()(_Block_pair __bp) throw() + { + // Set the _rover to the last physical location bitmap, + // which is the bitmap which belongs to the first free + // block. Thus, the bitmaps are in exact reverse order of + // the actual memory layout. So, we count down the bitmaps, + // which is the same as moving up the memory. + + // If the used count stored at the start of the Bit Map headers + // is equal to the number of Objects that the current Block can + // store, then there is definitely no space for another single + // object, so just return false. + _Counter_type __diff = __detail::__num_bitmaps(__bp); + + if (*(reinterpret_cast + (__bp.first) - (__diff + 1)) == __detail::__num_blocks(__bp)) + return false; + + size_t* __rover = reinterpret_cast(__bp.first) - 1; + + for (_Counter_type __i = 0; __i < __diff; ++__i) + { + _M_data_offset = __i; + if (*__rover) + { + _M_pbitmap = __rover; + return true; + } + --__rover; + } + return false; + } + + size_t* + _M_get() const throw() + { return _M_pbitmap; } + + _Counter_type + _M_offset() const throw() + { return _M_data_offset * size_t(bits_per_block); } + }; + + /** @class _Bitmap_counter bitmap_allocator.h bitmap_allocator.h + * + * @brief The bitmap counter which acts as the bitmap + * manipulator, and manages the bit-manipulation functions and + * the searching and identification functions on the bit-map. + */ + // _Tp should be a pointer type. + template + class _Bitmap_counter + { + typedef typename + __detail::__mini_vector > _BPVector; + typedef typename _BPVector::size_type _Index_type; + typedef _Tp pointer; + + _BPVector& _M_vbp; + size_t* _M_curr_bmap; + size_t* _M_last_bmap_in_block; + _Index_type _M_curr_index; + + public: + // Use the 2nd parameter with care. Make sure that such an + // entry exists in the vector before passing that particular + // index to this ctor. + _Bitmap_counter(_BPVector& Rvbp, long __index = -1) : _M_vbp(Rvbp) + { this->_M_reset(__index); } + + void + _M_reset(long __index = -1) throw() + { + if (__index == -1) + { + _M_curr_bmap = 0; + _M_curr_index = static_cast<_Index_type>(-1); + return; + } + + _M_curr_index = __index; + _M_curr_bmap = reinterpret_cast + (_M_vbp[_M_curr_index].first) - 1; + + _GLIBCXX_DEBUG_ASSERT(__index <= (long)_M_vbp.size() - 1); + + _M_last_bmap_in_block = _M_curr_bmap + - ((_M_vbp[_M_curr_index].second + - _M_vbp[_M_curr_index].first + 1) + / size_t(bits_per_block) - 1); + } + + // Dangerous Function! Use with extreme care. Pass to this + // function ONLY those values that are known to be correct, + // otherwise this will mess up big time. + void + _M_set_internal_bitmap(size_t* __new_internal_marker) throw() + { _M_curr_bmap = __new_internal_marker; } + + bool + _M_finished() const throw() + { return(_M_curr_bmap == 0); } + + _Bitmap_counter& + operator++() throw() + { + if (_M_curr_bmap == _M_last_bmap_in_block) + { + if (++_M_curr_index == _M_vbp.size()) + _M_curr_bmap = 0; + else + this->_M_reset(_M_curr_index); + } + else + --_M_curr_bmap; + return *this; + } + + size_t* + _M_get() const throw() + { return _M_curr_bmap; } + + pointer + _M_base() const throw() + { return _M_vbp[_M_curr_index].first; } + + _Index_type + _M_offset() const throw() + { + return size_t(bits_per_block) + * ((reinterpret_cast(this->_M_base()) + - _M_curr_bmap) - 1); + } + + _Index_type + _M_where() const throw() + { return _M_curr_index; } + }; + + /** @brief Mark a memory address as allocated by re-setting the + * corresponding bit in the bit-map. + */ + inline void + __bit_allocate(size_t* __pbmap, size_t __pos) throw() + { + size_t __mask = 1 << __pos; + __mask = ~__mask; + *__pbmap &= __mask; + } + + /** @brief Mark a memory address as free by setting the + * corresponding bit in the bit-map. + */ + inline void + __bit_free(size_t* __pbmap, size_t __pos) throw() + { + size_t __mask = 1 << __pos; + *__pbmap |= __mask; + } + + _GLIBCXX_END_NAMESPACE_VERSION + } // namespace __detail + +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /** @brief Generic Version of the bsf instruction. + */ + inline size_t + _Bit_scan_forward(size_t __num) + { return static_cast(__builtin_ctzl(__num)); } + + /** @class free_list bitmap_allocator.h bitmap_allocator.h + * + * @brief The free list class for managing chunks of memory to be + * given to and returned by the bitmap_allocator. + */ + class free_list + { + public: + typedef size_t* value_type; + typedef __detail::__mini_vector vector_type; + typedef vector_type::iterator iterator; + typedef __mutex __mutex_type; + + private: + struct _LT_pointer_compare + { + bool + operator()(const size_t* __pui, + const size_t __cui) const throw() + { return *__pui < __cui; } + }; + +#if defined __GTHREADS + __mutex_type& + _M_get_mutex() + { + static __mutex_type _S_mutex; + return _S_mutex; + } +#endif + + vector_type& + _M_get_free_list() + { + static vector_type _S_free_list; + return _S_free_list; + } + + /** @brief Performs validation of memory based on their size. + * + * @param __addr The pointer to the memory block to be + * validated. + * + * @detail Validates the memory block passed to this function and + * appropriately performs the action of managing the free list of + * blocks by adding this block to the free list or deleting this + * or larger blocks from the free list. + */ + void + _M_validate(size_t* __addr) throw() + { + vector_type& __free_list = _M_get_free_list(); + const vector_type::size_type __max_size = 64; + if (__free_list.size() >= __max_size) + { + // Ok, the threshold value has been reached. We determine + // which block to remove from the list of free blocks. + if (*__addr >= *__free_list.back()) + { + // Ok, the new block is greater than or equal to the + // last block in the list of free blocks. We just free + // the new block. + ::operator delete(static_cast(__addr)); + return; + } + else + { + // Deallocate the last block in the list of free lists, + // and insert the new one in its correct position. + ::operator delete(static_cast(__free_list.back())); + __free_list.pop_back(); + } + } + + // Just add the block to the list of free lists unconditionally. + iterator __temp = __detail::__lower_bound + (__free_list.begin(), __free_list.end(), + *__addr, _LT_pointer_compare()); + + // We may insert the new free list before _temp; + __free_list.insert(__temp, __addr); + } + + /** @brief Decides whether the wastage of memory is acceptable for + * the current memory request and returns accordingly. + * + * @param __block_size The size of the block available in the free + * list. + * + * @param __required_size The required size of the memory block. + * + * @return true if the wastage incurred is acceptable, else returns + * false. + */ + bool + _M_should_i_give(size_t __block_size, + size_t __required_size) throw() + { + const size_t __max_wastage_percentage = 36; + if (__block_size >= __required_size && + (((__block_size - __required_size) * 100 / __block_size) + < __max_wastage_percentage)) + return true; + else + return false; + } + + public: + /** @brief This function returns the block of memory to the + * internal free list. + * + * @param __addr The pointer to the memory block that was given + * by a call to the _M_get function. + */ + inline void + _M_insert(size_t* __addr) throw() + { +#if defined __GTHREADS + __scoped_lock __bfl_lock(_M_get_mutex()); +#endif + // Call _M_validate to decide what should be done with + // this particular free list. + this->_M_validate(reinterpret_cast(__addr) - 1); + // See discussion as to why this is 1! + } + + /** @brief This function gets a block of memory of the specified + * size from the free list. + * + * @param __sz The size in bytes of the memory required. + * + * @return A pointer to the new memory block of size at least + * equal to that requested. + */ + size_t* + _M_get(size_t __sz) throw(std::bad_alloc); + + /** @brief This function just clears the internal Free List, and + * gives back all the memory to the OS. + */ + void + _M_clear(); + }; + + + // Forward declare the class. + template + class bitmap_allocator; + + // Specialize for void: + template<> + class bitmap_allocator + { + public: + typedef void* pointer; + typedef const void* const_pointer; + + // Reference-to-void members are impossible. + typedef void value_type; + template + struct rebind + { + typedef bitmap_allocator<_Tp1> other; + }; + }; + + /** + * @brief Bitmap Allocator, primary template. + * @ingroup allocators + */ + template + class bitmap_allocator : private free_list + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef const _Tp* const_pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + typedef free_list::__mutex_type __mutex_type; + + template + struct rebind + { + typedef bitmap_allocator<_Tp1> other; + }; + + private: + template + struct aligned_size + { + enum + { + modulus = _BSize % _AlignSize, + value = _BSize + (modulus ? _AlignSize - (modulus) : 0) + }; + }; + + struct _Alloc_block + { + char __M_unused[aligned_size::value]; + }; + + + typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair; + + typedef typename __detail::__mini_vector<_Block_pair> _BPVector; + typedef typename _BPVector::iterator _BPiter; + + template + static _BPiter + _S_find(_Predicate __p) + { + _BPiter __first = _S_mem_blocks.begin(); + while (__first != _S_mem_blocks.end() && !__p(*__first)) + ++__first; + return __first; + } + +#if defined _GLIBCXX_DEBUG + // Complexity: O(lg(N)). Where, N is the number of block of size + // sizeof(value_type). + void + _S_check_for_free_blocks() throw() + { + typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; + _BPiter __bpi = _S_find(_FFF()); + + _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end()); + } +#endif + + /** @brief Responsible for exponentially growing the internal + * memory pool. + * + * @throw std::bad_alloc. If memory can not be allocated. + * + * @detail Complexity: O(1), but internally depends upon the + * complexity of the function free_list::_M_get. The part where + * the bitmap headers are written has complexity: O(X),where X + * is the number of blocks of size sizeof(value_type) within + * the newly acquired block. Having a tight bound. + */ + void + _S_refill_pool() throw(std::bad_alloc) + { +#if defined _GLIBCXX_DEBUG + _S_check_for_free_blocks(); +#endif + + const size_t __num_bitmaps = (_S_block_size + / size_t(__detail::bits_per_block)); + const size_t __size_to_allocate = sizeof(size_t) + + _S_block_size * sizeof(_Alloc_block) + + __num_bitmaps * sizeof(size_t); + + size_t* __temp = + reinterpret_cast(this->_M_get(__size_to_allocate)); + *__temp = 0; + ++__temp; + + // The Header information goes at the Beginning of the Block. + _Block_pair __bp = + std::make_pair(reinterpret_cast<_Alloc_block*> + (__temp + __num_bitmaps), + reinterpret_cast<_Alloc_block*> + (__temp + __num_bitmaps) + + _S_block_size - 1); + + // Fill the Vector with this information. + _S_mem_blocks.push_back(__bp); + + for (size_t __i = 0; __i < __num_bitmaps; ++__i) + __temp[__i] = ~static_cast(0); // 1 Indicates all Free. + + _S_block_size *= 2; + } + + static _BPVector _S_mem_blocks; + static size_t _S_block_size; + static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request; + static typename _BPVector::size_type _S_last_dealloc_index; +#if defined __GTHREADS + static __mutex_type _S_mut; +#endif + + public: + + /** @brief Allocates memory for a single object of size + * sizeof(_Tp). + * + * @throw std::bad_alloc. If memory can not be allocated. + * + * @detail Complexity: Worst case complexity is O(N), but that + * is hardly ever hit. If and when this particular case is + * encountered, the next few cases are guaranteed to have a + * worst case complexity of O(1)! That's why this function + * performs very well on average. You can consider this + * function to have a complexity referred to commonly as: + * Amortized Constant time. + */ + pointer + _M_allocate_single_object() throw(std::bad_alloc) + { +#if defined __GTHREADS + __scoped_lock __bit_lock(_S_mut); +#endif + + // The algorithm is something like this: The last_request + // variable points to the last accessed Bit Map. When such a + // condition occurs, we try to find a free block in the + // current bitmap, or succeeding bitmaps until the last bitmap + // is reached. If no free block turns up, we resort to First + // Fit method. + + // WARNING: Do not re-order the condition in the while + // statement below, because it relies on C++'s short-circuit + // evaluation. The return from _S_last_request->_M_get() will + // NOT be dereference able if _S_last_request->_M_finished() + // returns true. This would inevitably lead to a NULL pointer + // dereference if tinkered with. + while (_S_last_request._M_finished() == false + && (*(_S_last_request._M_get()) == 0)) + _S_last_request.operator++(); + + if (__builtin_expect(_S_last_request._M_finished() == true, false)) + { + // Fall Back to First Fit algorithm. + typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; + _FFF __fff; + _BPiter __bpi = _S_find(__detail::_Functor_Ref<_FFF>(__fff)); + + if (__bpi != _S_mem_blocks.end()) + { + // Search was successful. Ok, now mark the first bit from + // the right as 0, meaning Allocated. This bit is obtained + // by calling _M_get() on __fff. + size_t __nz_bit = _Bit_scan_forward(*__fff._M_get()); + __detail::__bit_allocate(__fff._M_get(), __nz_bit); + + _S_last_request._M_reset(__bpi - _S_mem_blocks.begin()); + + // Now, get the address of the bit we marked as allocated. + pointer __ret = reinterpret_cast + (__bpi->first + __fff._M_offset() + __nz_bit); + size_t* __puse_count = + reinterpret_cast + (__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1); + + ++(*__puse_count); + return __ret; + } + else + { + // Search was unsuccessful. We Add more memory to the + // pool by calling _S_refill_pool(). + _S_refill_pool(); + + // _M_Reset the _S_last_request structure to the first + // free block's bit map. + _S_last_request._M_reset(_S_mem_blocks.size() - 1); + + // Now, mark that bit as allocated. + } + } + + // _S_last_request holds a pointer to a valid bit map, that + // points to a free block in memory. + size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get()); + __detail::__bit_allocate(_S_last_request._M_get(), __nz_bit); + + pointer __ret = reinterpret_cast + (_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit); + + size_t* __puse_count = reinterpret_cast + (_S_mem_blocks[_S_last_request._M_where()].first) + - (__detail:: + __num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1); + + ++(*__puse_count); + return __ret; + } + + /** @brief Deallocates memory that belongs to a single object of + * size sizeof(_Tp). + * + * @detail Complexity: O(lg(N)), but the worst case is not hit + * often! This is because containers usually deallocate memory + * close to each other and this case is handled in O(1) time by + * the deallocate function. + */ + void + _M_deallocate_single_object(pointer __p) throw() + { +#if defined __GTHREADS + __scoped_lock __bit_lock(_S_mut); +#endif + _Alloc_block* __real_p = reinterpret_cast<_Alloc_block*>(__p); + + typedef typename _BPVector::iterator _Iterator; + typedef typename _BPVector::difference_type _Difference_type; + + _Difference_type __diff; + long __displacement; + + _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); + + __detail::_Inclusive_between<_Alloc_block*> __ibt(__real_p); + if (__ibt(_S_mem_blocks[_S_last_dealloc_index])) + { + _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index + <= _S_mem_blocks.size() - 1); + + // Initial Assumption was correct! + __diff = _S_last_dealloc_index; + __displacement = __real_p - _S_mem_blocks[__diff].first; + } + else + { + _Iterator _iter = _S_find(__ibt); + + _GLIBCXX_DEBUG_ASSERT(_iter != _S_mem_blocks.end()); + + __diff = _iter - _S_mem_blocks.begin(); + __displacement = __real_p - _S_mem_blocks[__diff].first; + _S_last_dealloc_index = __diff; + } + + // Get the position of the iterator that has been found. + const size_t __rotate = (__displacement + % size_t(__detail::bits_per_block)); + size_t* __bitmapC = + reinterpret_cast + (_S_mem_blocks[__diff].first) - 1; + __bitmapC -= (__displacement / size_t(__detail::bits_per_block)); + + __detail::__bit_free(__bitmapC, __rotate); + size_t* __puse_count = reinterpret_cast + (_S_mem_blocks[__diff].first) + - (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1); + + _GLIBCXX_DEBUG_ASSERT(*__puse_count != 0); + + --(*__puse_count); + + if (__builtin_expect(*__puse_count == 0, false)) + { + _S_block_size /= 2; + + // We can safely remove this block. + // _Block_pair __bp = _S_mem_blocks[__diff]; + this->_M_insert(__puse_count); + _S_mem_blocks.erase(_S_mem_blocks.begin() + __diff); + + // Reset the _S_last_request variable to reflect the + // erased block. We do this to protect future requests + // after the last block has been removed from a particular + // memory Chunk, which in turn has been returned to the + // free list, and hence had been erased from the vector, + // so the size of the vector gets reduced by 1. + if ((_Difference_type)_S_last_request._M_where() >= __diff--) + _S_last_request._M_reset(__diff); + + // If the Index into the vector of the region of memory + // that might hold the next address that will be passed to + // deallocated may have been invalidated due to the above + // erase procedure being called on the vector, hence we + // try to restore this invariant too. + if (_S_last_dealloc_index >= _S_mem_blocks.size()) + { + _S_last_dealloc_index =(__diff != -1 ? __diff : 0); + _GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0); + } + } + } + + public: + bitmap_allocator() throw() + { } + + bitmap_allocator(const bitmap_allocator&) + { } + + template + bitmap_allocator(const bitmap_allocator<_Tp1>&) throw() + { } + + ~bitmap_allocator() throw() + { } + + pointer + allocate(size_type __n) + { + if (__n > this->max_size()) + std::__throw_bad_alloc(); + + if (__builtin_expect(__n == 1, true)) + return this->_M_allocate_single_object(); + else + { + const size_type __b = __n * sizeof(value_type); + return reinterpret_cast(::operator new(__b)); + } + } + + pointer + allocate(size_type __n, typename bitmap_allocator::const_pointer) + { return allocate(__n); } + + void + deallocate(pointer __p, size_type __n) throw() + { + if (__builtin_expect(__p != 0, true)) + { + if (__builtin_expect(__n == 1, true)) + this->_M_deallocate_single_object(__p); + else + ::operator delete(__p); + } + } + + pointer + address(reference __r) const + { return std::__addressof(__r); } + + const_pointer + address(const_reference __r) const + { return std::__addressof(__r); } + + size_type + max_size() const throw() + { return size_type(-1) / sizeof(value_type); } + + void + construct(pointer __p, const_reference __data) + { ::new((void *)__p) value_type(__data); } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + void + construct(pointer __p, _Args&&... __args) + { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); } +#endif + + void + destroy(pointer __p) + { __p->~value_type(); } + }; + + template + bool + operator==(const bitmap_allocator<_Tp1>&, + const bitmap_allocator<_Tp2>&) throw() + { return true; } + + template + bool + operator!=(const bitmap_allocator<_Tp1>&, + const bitmap_allocator<_Tp2>&) throw() + { return false; } + + // Static member definitions. + template + typename bitmap_allocator<_Tp>::_BPVector + bitmap_allocator<_Tp>::_S_mem_blocks; + + template + size_t bitmap_allocator<_Tp>::_S_block_size = + 2 * size_t(__detail::bits_per_block); + + template + typename bitmap_allocator<_Tp>::_BPVector::size_type + bitmap_allocator<_Tp>::_S_last_dealloc_index = 0; + + template + __detail::_Bitmap_counter + ::_Alloc_block*> + bitmap_allocator<_Tp>::_S_last_request(_S_mem_blocks); + +#if defined __GTHREADS + template + typename bitmap_allocator<_Tp>::__mutex_type + bitmap_allocator<_Tp>::_S_mut; +#endif + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace __gnu_cxx + +#endif + diff --git a/libstdc++-v3/include/ext/cast.h b/libstdc++-v3/include/ext/cast.h new file mode 100644 index 000000000..f3384f9a5 --- /dev/null +++ b/libstdc++-v3/include/ext/cast.h @@ -0,0 +1,121 @@ +// -*- C++ -*- + +// Copyright (C) 2008, 2009, 2010 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/cast.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{ext/pointer.h} + */ + +#ifndef _GLIBCXX_CAST_H +#define _GLIBCXX_CAST_H 1 + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /** + * These functions are here to allow containers to support non standard + * pointer types. For normal pointers, these resolve to the use of the + * standard cast operation. For other types the functions will perform + * the apprpriate cast to/from the custom pointer class so long as that + * class meets the following conditions: + * 1) has a typedef element_type which names tehe type it points to. + * 2) has a get() const method which returns element_type*. + * 3) has a constructor which can take one element_type* argument. + */ + + /** + * This type supports the semantics of the pointer cast operators (below.) + */ + template + struct _Caster + { typedef typename _ToType::element_type* type; }; + + template + struct _Caster<_ToType*> + { typedef _ToType* type; }; + + /** + * Casting operations for cases where _FromType is not a standard pointer. + * _ToType can be a standard or non-standard pointer. Given that _FromType + * is not a pointer, it must have a get() method that returns the standard + * pointer equivalent of the address it points to, and must have an + * element_type typedef which names the type it points to. + */ + template + inline _ToType + __static_pointer_cast(const _FromType& __arg) + { return _ToType(static_cast:: + type>(__arg.get())); } + + template + inline _ToType + __dynamic_pointer_cast(const _FromType& __arg) + { return _ToType(dynamic_cast:: + type>(__arg.get())); } + + template + inline _ToType + __const_pointer_cast(const _FromType& __arg) + { return _ToType(const_cast:: + type>(__arg.get())); } + + template + inline _ToType + __reinterpret_pointer_cast(const _FromType& __arg) + { return _ToType(reinterpret_cast:: + type>(__arg.get())); } + + /** + * Casting operations for cases where _FromType is a standard pointer. + * _ToType can be a standard or non-standard pointer. + */ + template + inline _ToType + __static_pointer_cast(_FromType* __arg) + { return _ToType(static_cast:: + type>(__arg)); } + + template + inline _ToType + __dynamic_pointer_cast(_FromType* __arg) + { return _ToType(dynamic_cast:: + type>(__arg)); } + + template + inline _ToType + __const_pointer_cast(_FromType* __arg) + { return _ToType(const_cast:: + type>(__arg)); } + + template + inline _ToType + __reinterpret_pointer_cast(_FromType* __arg) + { return _ToType(reinterpret_cast:: + type>(__arg)); } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // __GLIBCXX_CAST_H diff --git a/libstdc++-v3/include/ext/codecvt_specializations.h b/libstdc++-v3/include/ext/codecvt_specializations.h new file mode 100644 index 000000000..38b95efc1 --- /dev/null +++ b/libstdc++-v3/include/ext/codecvt_specializations.h @@ -0,0 +1,514 @@ +// Locale support (codecvt) -*- C++ -*- + +// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, +// 2008, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +// +// ISO C++ 14882: 22.2.1.5 Template class codecvt +// + +// Written by Benjamin Kosnik + +/** @file ext/codecvt_specializations.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _EXT_CODECVT_SPECIALIZATIONS_H +#define _EXT_CODECVT_SPECIALIZATIONS_H 1 + +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /// Extension to use iconv for dealing with character encodings. + // This includes conversions and comparisons between various character + // sets. This object encapsulates data that may need to be shared between + // char_traits, codecvt and ctype. + class encoding_state + { + public: + // Types: + // NB: A conversion descriptor subsumes and enhances the + // functionality of a simple state type such as mbstate_t. + typedef iconv_t descriptor_type; + + protected: + // Name of internal character set encoding. + std::string _M_int_enc; + + // Name of external character set encoding. + std::string _M_ext_enc; + + // Conversion descriptor between external encoding to internal encoding. + descriptor_type _M_in_desc; + + // Conversion descriptor between internal encoding to external encoding. + descriptor_type _M_out_desc; + + // The byte-order marker for the external encoding, if necessary. + int _M_ext_bom; + + // The byte-order marker for the internal encoding, if necessary. + int _M_int_bom; + + // Number of external bytes needed to construct one complete + // character in the internal encoding. + // NB: -1 indicates variable, or stateful, encodings. + int _M_bytes; + + public: + explicit + encoding_state() + : _M_in_desc(0), _M_out_desc(0), _M_ext_bom(0), _M_int_bom(0), _M_bytes(0) + { } + + explicit + encoding_state(const char* __int, const char* __ext, + int __ibom = 0, int __ebom = 0, int __bytes = 1) + : _M_int_enc(__int), _M_ext_enc(__ext), _M_in_desc(0), _M_out_desc(0), + _M_ext_bom(__ebom), _M_int_bom(__ibom), _M_bytes(__bytes) + { init(); } + + // 21.1.2 traits typedefs + // p4 + // typedef STATE_T state_type + // requires: state_type shall meet the requirements of + // CopyConstructible types (20.1.3) + // NB: This does not preserve the actual state of the conversion + // descriptor member, but it does duplicate the encoding + // information. + encoding_state(const encoding_state& __obj) : _M_in_desc(0), _M_out_desc(0) + { construct(__obj); } + + // Need assignment operator as well. + encoding_state& + operator=(const encoding_state& __obj) + { + construct(__obj); + return *this; + } + + ~encoding_state() + { destroy(); } + + bool + good() const throw() + { + const descriptor_type __err = (iconv_t)(-1); + bool __test = _M_in_desc && _M_in_desc != __err; + __test &= _M_out_desc && _M_out_desc != __err; + return __test; + } + + int + character_ratio() const + { return _M_bytes; } + + const std::string + internal_encoding() const + { return _M_int_enc; } + + int + internal_bom() const + { return _M_int_bom; } + + const std::string + external_encoding() const + { return _M_ext_enc; } + + int + external_bom() const + { return _M_ext_bom; } + + const descriptor_type& + in_descriptor() const + { return _M_in_desc; } + + const descriptor_type& + out_descriptor() const + { return _M_out_desc; } + + protected: + void + init() + { + const descriptor_type __err = (iconv_t)(-1); + const bool __have_encodings = _M_int_enc.size() && _M_ext_enc.size(); + if (!_M_in_desc && __have_encodings) + { + _M_in_desc = iconv_open(_M_int_enc.c_str(), _M_ext_enc.c_str()); + if (_M_in_desc == __err) + std::__throw_runtime_error(__N("encoding_state::_M_init " + "creating iconv input descriptor failed")); + } + if (!_M_out_desc && __have_encodings) + { + _M_out_desc = iconv_open(_M_ext_enc.c_str(), _M_int_enc.c_str()); + if (_M_out_desc == __err) + std::__throw_runtime_error(__N("encoding_state::_M_init " + "creating iconv output descriptor failed")); + } + } + + void + construct(const encoding_state& __obj) + { + destroy(); + _M_int_enc = __obj._M_int_enc; + _M_ext_enc = __obj._M_ext_enc; + _M_ext_bom = __obj._M_ext_bom; + _M_int_bom = __obj._M_int_bom; + _M_bytes = __obj._M_bytes; + init(); + } + + void + destroy() throw() + { + const descriptor_type __err = (iconv_t)(-1); + if (_M_in_desc && _M_in_desc != __err) + { + iconv_close(_M_in_desc); + _M_in_desc = 0; + } + if (_M_out_desc && _M_out_desc != __err) + { + iconv_close(_M_out_desc); + _M_out_desc = 0; + } + } + }; + + /// encoding_char_traits + // Custom traits type with encoding_state for the state type, and the + // associated fpos for the position type, all other + // bits equivalent to the required char_traits instantiations. + template + struct encoding_char_traits : public std::char_traits<_CharT> + { + typedef encoding_state state_type; + typedef typename std::fpos pos_type; + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using __gnu_cxx::encoding_state; + + /// codecvt specialization. + // This partial specialization takes advantage of iconv to provide + // code conversions between a large number of character encodings. + template + class codecvt<_InternT, _ExternT, encoding_state> + : public __codecvt_abstract_base<_InternT, _ExternT, encoding_state> + { + public: + // Types: + typedef codecvt_base::result result; + typedef _InternT intern_type; + typedef _ExternT extern_type; + typedef __gnu_cxx::encoding_state state_type; + typedef state_type::descriptor_type descriptor_type; + + // Data Members: + static locale::id id; + + explicit + codecvt(size_t __refs = 0) + : __codecvt_abstract_base(__refs) + { } + + explicit + codecvt(state_type& __enc, size_t __refs = 0) + : __codecvt_abstract_base(__refs) + { } + + protected: + virtual + ~codecvt() { } + + virtual result + do_out(state_type& __state, const intern_type* __from, + const intern_type* __from_end, const intern_type*& __from_next, + extern_type* __to, extern_type* __to_end, + extern_type*& __to_next) const; + + virtual result + do_unshift(state_type& __state, extern_type* __to, + extern_type* __to_end, extern_type*& __to_next) const; + + virtual result + do_in(state_type& __state, const extern_type* __from, + const extern_type* __from_end, const extern_type*& __from_next, + intern_type* __to, intern_type* __to_end, + intern_type*& __to_next) const; + + virtual int + do_encoding() const throw(); + + virtual bool + do_always_noconv() const throw(); + + virtual int + do_length(state_type&, const extern_type* __from, + const extern_type* __end, size_t __max) const; + + virtual int + do_max_length() const throw(); + }; + + template + locale::id + codecvt<_InternT, _ExternT, encoding_state>::id; + + // This adaptor works around the signature problems of the second + // argument to iconv(): SUSv2 and others use 'const char**', but glibc 2.2 + // uses 'char**', which matches the POSIX 1003.1-2001 standard. + // Using this adaptor, g++ will do the work for us. + template + inline size_t + __iconv_adaptor(size_t(*__func)(iconv_t, _Tp, size_t*, char**, size_t*), + iconv_t __cd, char** __inbuf, size_t* __inbytes, + char** __outbuf, size_t* __outbytes) + { return __func(__cd, (_Tp)__inbuf, __inbytes, __outbuf, __outbytes); } + + template + codecvt_base::result + codecvt<_InternT, _ExternT, encoding_state>:: + do_out(state_type& __state, const intern_type* __from, + const intern_type* __from_end, const intern_type*& __from_next, + extern_type* __to, extern_type* __to_end, + extern_type*& __to_next) const + { + result __ret = codecvt_base::error; + if (__state.good()) + { + const descriptor_type& __desc = __state.out_descriptor(); + const size_t __fmultiple = sizeof(intern_type); + size_t __fbytes = __fmultiple * (__from_end - __from); + const size_t __tmultiple = sizeof(extern_type); + size_t __tbytes = __tmultiple * (__to_end - __to); + + // Argument list for iconv specifies a byte sequence. Thus, + // all to/from arrays must be brutally casted to char*. + char* __cto = reinterpret_cast(__to); + char* __cfrom; + size_t __conv; + + // Some encodings need a byte order marker as the first item + // in the byte stream, to designate endian-ness. The default + // value for the byte order marker is NULL, so if this is + // the case, it's not necessary and we can just go on our + // merry way. + int __int_bom = __state.internal_bom(); + if (__int_bom) + { + size_t __size = __from_end - __from; + intern_type* __cfixed = static_cast + (__builtin_alloca(sizeof(intern_type) * (__size + 1))); + __cfixed[0] = static_cast(__int_bom); + char_traits::copy(__cfixed + 1, __from, __size); + __cfrom = reinterpret_cast(__cfixed); + __conv = __iconv_adaptor(iconv, __desc, &__cfrom, + &__fbytes, &__cto, &__tbytes); + } + else + { + intern_type* __cfixed = const_cast(__from); + __cfrom = reinterpret_cast(__cfixed); + __conv = __iconv_adaptor(iconv, __desc, &__cfrom, &__fbytes, + &__cto, &__tbytes); + } + + if (__conv != size_t(-1)) + { + __from_next = reinterpret_cast(__cfrom); + __to_next = reinterpret_cast(__cto); + __ret = codecvt_base::ok; + } + else + { + if (__fbytes < __fmultiple * (__from_end - __from)) + { + __from_next = reinterpret_cast(__cfrom); + __to_next = reinterpret_cast(__cto); + __ret = codecvt_base::partial; + } + else + __ret = codecvt_base::error; + } + } + return __ret; + } + + template + codecvt_base::result + codecvt<_InternT, _ExternT, encoding_state>:: + do_unshift(state_type& __state, extern_type* __to, + extern_type* __to_end, extern_type*& __to_next) const + { + result __ret = codecvt_base::error; + if (__state.good()) + { + const descriptor_type& __desc = __state.in_descriptor(); + const size_t __tmultiple = sizeof(intern_type); + size_t __tlen = __tmultiple * (__to_end - __to); + + // Argument list for iconv specifies a byte sequence. Thus, + // all to/from arrays must be brutally casted to char*. + char* __cto = reinterpret_cast(__to); + size_t __conv = __iconv_adaptor(iconv,__desc, 0, 0, + &__cto, &__tlen); + + if (__conv != size_t(-1)) + { + __to_next = reinterpret_cast(__cto); + if (__tlen == __tmultiple * (__to_end - __to)) + __ret = codecvt_base::noconv; + else if (__tlen == 0) + __ret = codecvt_base::ok; + else + __ret = codecvt_base::partial; + } + else + __ret = codecvt_base::error; + } + return __ret; + } + + template + codecvt_base::result + codecvt<_InternT, _ExternT, encoding_state>:: + do_in(state_type& __state, const extern_type* __from, + const extern_type* __from_end, const extern_type*& __from_next, + intern_type* __to, intern_type* __to_end, + intern_type*& __to_next) const + { + result __ret = codecvt_base::error; + if (__state.good()) + { + const descriptor_type& __desc = __state.in_descriptor(); + const size_t __fmultiple = sizeof(extern_type); + size_t __flen = __fmultiple * (__from_end - __from); + const size_t __tmultiple = sizeof(intern_type); + size_t __tlen = __tmultiple * (__to_end - __to); + + // Argument list for iconv specifies a byte sequence. Thus, + // all to/from arrays must be brutally casted to char*. + char* __cto = reinterpret_cast(__to); + char* __cfrom; + size_t __conv; + + // Some encodings need a byte order marker as the first item + // in the byte stream, to designate endian-ness. The default + // value for the byte order marker is NULL, so if this is + // the case, it's not necessary and we can just go on our + // merry way. + int __ext_bom = __state.external_bom(); + if (__ext_bom) + { + size_t __size = __from_end - __from; + extern_type* __cfixed = static_cast + (__builtin_alloca(sizeof(extern_type) * (__size + 1))); + __cfixed[0] = static_cast(__ext_bom); + char_traits::copy(__cfixed + 1, __from, __size); + __cfrom = reinterpret_cast(__cfixed); + __conv = __iconv_adaptor(iconv, __desc, &__cfrom, + &__flen, &__cto, &__tlen); + } + else + { + extern_type* __cfixed = const_cast(__from); + __cfrom = reinterpret_cast(__cfixed); + __conv = __iconv_adaptor(iconv, __desc, &__cfrom, + &__flen, &__cto, &__tlen); + } + + + if (__conv != size_t(-1)) + { + __from_next = reinterpret_cast(__cfrom); + __to_next = reinterpret_cast(__cto); + __ret = codecvt_base::ok; + } + else + { + if (__flen < static_cast(__from_end - __from)) + { + __from_next = reinterpret_cast(__cfrom); + __to_next = reinterpret_cast(__cto); + __ret = codecvt_base::partial; + } + else + __ret = codecvt_base::error; + } + } + return __ret; + } + + template + int + codecvt<_InternT, _ExternT, encoding_state>:: + do_encoding() const throw() + { + int __ret = 0; + if (sizeof(_ExternT) <= sizeof(_InternT)) + __ret = sizeof(_InternT) / sizeof(_ExternT); + return __ret; + } + + template + bool + codecvt<_InternT, _ExternT, encoding_state>:: + do_always_noconv() const throw() + { return false; } + + template + int + codecvt<_InternT, _ExternT, encoding_state>:: + do_length(state_type&, const extern_type* __from, + const extern_type* __end, size_t __max) const + { return std::min(__max, static_cast(__end - __from)); } + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 74. Garbled text for codecvt::do_max_length + template + int + codecvt<_InternT, _ExternT, encoding_state>:: + do_max_length() const throw() + { return 1; } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif diff --git a/libstdc++-v3/include/ext/concurrence.h b/libstdc++-v3/include/ext/concurrence.h new file mode 100644 index 000000000..ce999e5e3 --- /dev/null +++ b/libstdc++-v3/include/ext/concurrence.h @@ -0,0 +1,401 @@ +// Support for concurrent programing -*- C++ -*- + +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/concurrence.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _CONCURRENCE_H +#define _CONCURRENCE_H 1 + +#pragma GCC system_header + +#include +#include +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // Available locking policies: + // _S_single single-threaded code that doesn't need to be locked. + // _S_mutex multi-threaded code that requires additional support + // from gthr.h or abstraction layers in concurrence.h. + // _S_atomic multi-threaded code using atomic operations. + enum _Lock_policy { _S_single, _S_mutex, _S_atomic }; + + // Compile time constant that indicates prefered locking policy in + // the current configuration. + static const _Lock_policy __default_lock_policy = +#ifdef __GTHREADS +#if (defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_2) \ + && defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_4)) + _S_atomic; +#else + _S_mutex; +#endif +#else + _S_single; +#endif + + // NB: As this is used in libsupc++, need to only depend on + // exception. No stdexception classes, no use of std::string. + class __concurrence_lock_error : public std::exception + { + public: + virtual char const* + what() const throw() + { return "__gnu_cxx::__concurrence_lock_error"; } + }; + + class __concurrence_unlock_error : public std::exception + { + public: + virtual char const* + what() const throw() + { return "__gnu_cxx::__concurrence_unlock_error"; } + }; + + class __concurrence_broadcast_error : public std::exception + { + public: + virtual char const* + what() const throw() + { return "__gnu_cxx::__concurrence_broadcast_error"; } + }; + + class __concurrence_wait_error : public std::exception + { + public: + virtual char const* + what() const throw() + { return "__gnu_cxx::__concurrence_wait_error"; } + }; + + // Substitute for concurrence_error object in the case of -fno-exceptions. + inline void + __throw_concurrence_lock_error() + { +#if __EXCEPTIONS + throw __concurrence_lock_error(); +#else + __builtin_abort(); +#endif + } + + inline void + __throw_concurrence_unlock_error() + { +#if __EXCEPTIONS + throw __concurrence_unlock_error(); +#else + __builtin_abort(); +#endif + } + +#ifdef __GTHREAD_HAS_COND + inline void + __throw_concurrence_broadcast_error() + { +#if __EXCEPTIONS + throw __concurrence_broadcast_error(); +#else + __builtin_abort(); +#endif + } + + inline void + __throw_concurrence_wait_error() + { +#if __EXCEPTIONS + throw __concurrence_wait_error(); +#else + __builtin_abort(); +#endif + } +#endif + + template + static inline void + __copy_gthr_type(_Tp& __to, const _Tp& __from) + { +#if defined __GXX_EXPERIMENTAL_CXX0X__ \ + && defined _GLIBCXX_GTHREADS_NO_COPY_ASSIGN_IN_CXX11 + __builtin_memcpy(&__to, &__from, sizeof(__to)); +#else + __to = __from; +#endif + } + + class __mutex + { + private: + __gthread_mutex_t _M_mutex; + + __mutex(const __mutex&); + __mutex& operator=(const __mutex&); + + public: + __mutex() + { +#if __GTHREADS + if (__gthread_active_p()) + { +#if defined __GTHREAD_MUTEX_INIT + __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT; + __copy_gthr_type(_M_mutex, __tmp); +#else + __GTHREAD_MUTEX_INIT_FUNCTION(&_M_mutex); +#endif + } +#endif + } + +#if __GTHREADS && ! defined __GTHREAD_MUTEX_INIT + ~__mutex() + { + if (__gthread_active_p()) + __gthread_mutex_destroy(&_M_mutex); + } +#endif + + void lock() + { +#if __GTHREADS + if (__gthread_active_p()) + { + if (__gthread_mutex_lock(&_M_mutex) != 0) + __throw_concurrence_lock_error(); + } +#endif + } + + void unlock() + { +#if __GTHREADS + if (__gthread_active_p()) + { + if (__gthread_mutex_unlock(&_M_mutex) != 0) + __throw_concurrence_unlock_error(); + } +#endif + } + + __gthread_mutex_t* gthread_mutex(void) + { return &_M_mutex; } + }; + + class __recursive_mutex + { + private: + __gthread_recursive_mutex_t _M_mutex; + + __recursive_mutex(const __recursive_mutex&); + __recursive_mutex& operator=(const __recursive_mutex&); + + public: + __recursive_mutex() + { +#if __GTHREADS + if (__gthread_active_p()) + { +#if defined __GTHREAD_RECURSIVE_MUTEX_INIT + __gthread_recursive_mutex_t __tmp = __GTHREAD_RECURSIVE_MUTEX_INIT; + __copy_gthr_type(_M_mutex, __tmp); +#else + __GTHREAD_RECURSIVE_MUTEX_INIT_FUNCTION(&_M_mutex); +#endif + } +#endif + } + +#if __GTHREADS && ! defined __GTHREAD_RECURSIVE_MUTEX_INIT + ~__recursive_mutex() + { + if (__gthread_active_p()) + _S_destroy(&_M_mutex); + } +#endif + + void lock() + { +#if __GTHREADS + if (__gthread_active_p()) + { + if (__gthread_recursive_mutex_lock(&_M_mutex) != 0) + __throw_concurrence_lock_error(); + } +#endif + } + + void unlock() + { +#if __GTHREADS + if (__gthread_active_p()) + { + if (__gthread_recursive_mutex_unlock(&_M_mutex) != 0) + __throw_concurrence_unlock_error(); + } +#endif + } + + __gthread_recursive_mutex_t* gthread_recursive_mutex(void) + { return &_M_mutex; } + +#if __GTHREADS && ! defined __GTHREAD_RECURSIVE_MUTEX_INIT + // FIXME: gthreads doesn't define __gthread_recursive_mutex_destroy + // so we need to obtain a __gthread_mutex_t to destroy + private: + template + static void + _S_destroy_win32(_Mx* __mx, _Rm const* __rmx) + { + __mx->counter = __rmx->counter; + __mx->sema = __rmx->sema; + __gthread_mutex_destroy(__mx); + } + + // matches a gthr-win32.h recursive mutex + template + static typename __enable_if<(bool)sizeof(&_Rm::sema), void>::__type + _S_destroy(_Rm* __mx) + { + __gthread_mutex_t __tmp; + _S_destroy_win32(&__tmp, __mx); + } + + // matches a recursive mutex with a member 'actual' + template + static typename __enable_if<(bool)sizeof(&_Rm::actual), void>::__type + _S_destroy(_Rm* __mx) + { __gthread_mutex_destroy(&__mx->actual); } + + // matches when there's only one mutex type + template + static typename + __enable_if::__value, + void>::__type + _S_destroy(_Rm* __mx) + { __gthread_mutex_destroy(__mx); } +#endif + }; + + /// Scoped lock idiom. + // Acquire the mutex here with a constructor call, then release with + // the destructor call in accordance with RAII style. + class __scoped_lock + { + public: + typedef __mutex __mutex_type; + + private: + __mutex_type& _M_device; + + __scoped_lock(const __scoped_lock&); + __scoped_lock& operator=(const __scoped_lock&); + + public: + explicit __scoped_lock(__mutex_type& __name) : _M_device(__name) + { _M_device.lock(); } + + ~__scoped_lock() throw() + { _M_device.unlock(); } + }; + +#ifdef __GTHREAD_HAS_COND + class __cond + { + private: + __gthread_cond_t _M_cond; + + __cond(const __cond&); + __cond& operator=(const __cond&); + + public: + __cond() + { +#if __GTHREADS + if (__gthread_active_p()) + { +#if defined __GTHREAD_COND_INIT + __gthread_cond_t __tmp = __GTHREAD_COND_INIT; + __copy_gthr_type(_M_cond, __tmp); +#else + __GTHREAD_COND_INIT_FUNCTION(&_M_cond); +#endif + } +#endif + } + +#if __GTHREADS && ! defined __GTHREAD_COND_INIT + ~__cond() + { + if (__gthread_active_p()) + __gthread_cond_destroy(&_M_cond); + } +#endif + + void broadcast() + { +#if __GTHREADS + if (__gthread_active_p()) + { + if (__gthread_cond_broadcast(&_M_cond) != 0) + __throw_concurrence_broadcast_error(); + } +#endif + } + + void wait(__mutex *mutex) + { +#if __GTHREADS + { + if (__gthread_cond_wait(&_M_cond, mutex->gthread_mutex()) != 0) + __throw_concurrence_wait_error(); + } +#endif + } + + void wait_recursive(__recursive_mutex *mutex) + { +#if __GTHREADS + { + if (__gthread_cond_wait_recursive(&_M_cond, + mutex->gthread_recursive_mutex()) + != 0) + __throw_concurrence_wait_error(); + } +#endif + } + }; +#endif + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif diff --git a/libstdc++-v3/include/ext/debug_allocator.h b/libstdc++-v3/include/ext/debug_allocator.h new file mode 100644 index 000000000..12a5ea6ba --- /dev/null +++ b/libstdc++-v3/include/ext/debug_allocator.h @@ -0,0 +1,127 @@ +// Allocators -*- C++ -*- + +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/* + * Copyright (c) 1996-1997 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +/** @file ext/debug_allocator.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _DEBUG_ALLOCATOR_H +#define _DEBUG_ALLOCATOR_H 1 + +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::size_t; + + /** + * @brief A meta-allocator with debugging bits, as per [20.4]. + * @ingroup allocators + * + * This is precisely the allocator defined in the C++ Standard. + * - all allocation calls operator new + * - all deallocation calls operator delete + */ + template + class debug_allocator + { + public: + typedef typename _Alloc::size_type size_type; + typedef typename _Alloc::difference_type difference_type; + typedef typename _Alloc::pointer pointer; + typedef typename _Alloc::const_pointer const_pointer; + typedef typename _Alloc::reference reference; + typedef typename _Alloc::const_reference const_reference; + typedef typename _Alloc::value_type value_type; + + private: + // _M_extra is the number of objects that correspond to the + // extra space where debug information is stored. + size_type _M_extra; + + _Alloc _M_allocator; + + public: + debug_allocator() + { + const size_t __obj_size = sizeof(value_type); + _M_extra = (sizeof(size_type) + __obj_size - 1) / __obj_size; + } + + pointer + allocate(size_type __n) + { + pointer __res = _M_allocator.allocate(__n + _M_extra); + size_type* __ps = reinterpret_cast(__res); + *__ps = __n; + return __res + _M_extra; + } + + pointer + allocate(size_type __n, const void* __hint) + { + pointer __res = _M_allocator.allocate(__n + _M_extra, __hint); + size_type* __ps = reinterpret_cast(__res); + *__ps = __n; + return __res + _M_extra; + } + + void + deallocate(pointer __p, size_type __n) + { + if (__p) + { + pointer __real_p = __p - _M_extra; + if (*reinterpret_cast(__real_p) != __n) + { + throw std::runtime_error("debug_allocator::deallocate" + " wrong size"); + } + _M_allocator.deallocate(__real_p, __n + _M_extra); + } + else + throw std::runtime_error("debug_allocator::deallocate null pointer"); + } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif diff --git a/libstdc++-v3/include/ext/enc_filebuf.h b/libstdc++-v3/include/ext/enc_filebuf.h new file mode 100644 index 000000000..058d330c1 --- /dev/null +++ b/libstdc++-v3/include/ext/enc_filebuf.h @@ -0,0 +1,65 @@ +// filebuf with encoding state type -*- C++ -*- + +// Copyright (C) 2002, 2003, 2004, 2007, 2009 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/enc_filebuf.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _EXT_ENC_FILEBUF_H +#define _EXT_ENC_FILEBUF_H 1 + +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /// class enc_filebuf. + template + class enc_filebuf + : public std::basic_filebuf<_CharT, encoding_char_traits<_CharT> > + { + public: + typedef encoding_char_traits<_CharT> traits_type; + typedef typename traits_type::state_type state_type; + typedef typename traits_type::pos_type pos_type; + + enc_filebuf(state_type& __state) + : std::basic_filebuf<_CharT, encoding_char_traits<_CharT> >() + { this->_M_state_beg = __state; } + + private: + // concept requirements: + // Set state type to something useful. + // Something more than copyconstructible is needed here, so + // require default and copy constructible + assignment operator. + __glibcxx_class_requires(state_type, _SGIAssignableConcept) + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif diff --git a/libstdc++-v3/include/ext/extptr_allocator.h b/libstdc++-v3/include/ext/extptr_allocator.h new file mode 100644 index 000000000..dfb76ac09 --- /dev/null +++ b/libstdc++-v3/include/ext/extptr_allocator.h @@ -0,0 +1,181 @@ +// -*- C++ -*- + +// Copyright (C) 2008, 2009, 2010 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** + * @file ext/extptr_allocator.h + * This file is a GNU extension to the Standard C++ Library. + * + * @author Bob Walters + * + * An example allocator which uses an alternative pointer type from + * bits/pointer.h. Supports test cases which confirm container support + * for alternative pointers. + */ + +#ifndef _EXTPTR_ALLOCATOR_H +#define _EXTPTR_ALLOCATOR_H 1 + +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /** + * @brief An example allocator which uses a non-standard pointer type. + * @ingroup allocators + * + * This allocator specifies that containers use a 'relative pointer' as it's + * pointer type. (See ext/pointer.h) Memory allocation in this example + * is still performed using std::allocator. + */ + template + class _ExtPtr_allocator + { + public: + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + + // Note the non-standard pointer types. + typedef _Pointer_adapter<_Relative_pointer_impl<_Tp> > pointer; + typedef _Pointer_adapter<_Relative_pointer_impl > + const_pointer; + + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + + template + struct rebind + { typedef _ExtPtr_allocator<_Up> other; }; + + _ExtPtr_allocator() throw() + : _M_real_alloc() { } + + _ExtPtr_allocator(const _ExtPtr_allocator &__rarg) throw() + : _M_real_alloc(__rarg._M_real_alloc) { } + + template + _ExtPtr_allocator(const _ExtPtr_allocator<_Up>& __rarg) throw() + : _M_real_alloc(__rarg._M_getUnderlyingImp()) { } + + ~_ExtPtr_allocator() throw() + { } + + pointer address(reference __x) const + { return std::__addressof(__x); } + + const_pointer address(const_reference __x) const + { return std::__addressof(__x); } + + pointer allocate(size_type __n, void* __hint = 0) + { return _M_real_alloc.allocate(__n,__hint); } + + void deallocate(pointer __p, size_type __n) + { _M_real_alloc.deallocate(__p.get(), __n); } + + size_type max_size() const throw() + { return std::numeric_limits::max() / sizeof(_Tp); } + + void construct(pointer __p, const _Tp& __val) + { ::new(__p.get()) _Tp(__val); } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + void + construct(pointer __p, _Args&&... __args) + { ::new(__p.get()) _Tp(std::forward<_Args>(__args)...); } +#endif + + void destroy(pointer __p) + { __p->~_Tp(); } + + template + inline bool + operator==(const _ExtPtr_allocator<_Up>& __rarg) + { return _M_real_alloc == __rarg._M_getUnderlyingImp(); } + + inline bool + operator==(const _ExtPtr_allocator& __rarg) + { return _M_real_alloc == __rarg._M_real_alloc; } + + template + inline bool + operator!=(const _ExtPtr_allocator<_Up>& __rarg) + { return _M_real_alloc != __rarg._M_getUnderlyingImp(); } + + inline bool + operator!=(const _ExtPtr_allocator& __rarg) + { return _M_real_alloc != __rarg._M_real_alloc; } + + template + inline friend void + swap(_ExtPtr_allocator<_Up>&, _ExtPtr_allocator<_Up>&); + + // A method specific to this implementation. + const std::allocator<_Tp>& + _M_getUnderlyingImp() const + { return _M_real_alloc; } + + private: + std::allocator<_Tp> _M_real_alloc; + }; + + // _ExtPtr_allocator specialization. + template<> + class _ExtPtr_allocator + { + public: + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + typedef void value_type; + + // Note the non-standard pointer types + typedef _Pointer_adapter<_Relative_pointer_impl > pointer; + typedef _Pointer_adapter<_Relative_pointer_impl > + const_pointer; + + template + struct rebind + { typedef _ExtPtr_allocator<_Up> other; }; + + private: + std::allocator _M_real_alloc; + }; + + template + inline void + swap(_ExtPtr_allocator<_Tp>& __larg, _ExtPtr_allocator<_Tp>& __rarg) + { + std::allocator<_Tp> __tmp( __rarg._M_real_alloc ); + __rarg._M_real_alloc = __larg._M_real_alloc; + __larg._M_real_alloc = __tmp; + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif /* _EXTPTR_ALLOCATOR_H */ diff --git a/libstdc++-v3/include/ext/functional b/libstdc++-v3/include/ext/functional new file mode 100644 index 000000000..7e8acdfb4 --- /dev/null +++ b/libstdc++-v3/include/ext/functional @@ -0,0 +1,427 @@ +// Functional extensions -*- C++ -*- + +// Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1996 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +/** @file ext/functional + * This file is a GNU extension to the Standard C++ Library (possibly + * containing extensions from the HP/SGI STL subset). + */ + +#ifndef _EXT_FUNCTIONAL +#define _EXT_FUNCTIONAL 1 + +#pragma GCC system_header + +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::size_t; + using std::unary_function; + using std::binary_function; + using std::mem_fun1_t; + using std::const_mem_fun1_t; + using std::mem_fun1_ref_t; + using std::const_mem_fun1_ref_t; + + /** The @c identity_element functions are not part of the C++ + * standard; SGI provided them as an extension. Its argument is an + * operation, and its return value is the identity element for that + * operation. It is overloaded for addition and multiplication, + * and you can overload it for your own nefarious operations. + * + * @addtogroup SGIextensions + * @{ + */ + /// An \link SGIextensions SGI extension \endlink. + template + inline _Tp + identity_element(std::plus<_Tp>) + { return _Tp(0); } + + /// An \link SGIextensions SGI extension \endlink. + template + inline _Tp + identity_element(std::multiplies<_Tp>) + { return _Tp(1); } + /** @} */ + + /** As an extension to the binders, SGI provided composition functors and + * wrapper functions to aid in their creation. The @c unary_compose + * functor is constructed from two functions/functors, @c f and @c g. + * Calling @c operator() with a single argument @c x returns @c f(g(x)). + * The function @c compose1 takes the two functions and constructs a + * @c unary_compose variable for you. + * + * @c binary_compose is constructed from three functors, @c f, @c g1, + * and @c g2. Its @c operator() returns @c f(g1(x),g2(x)). The function + * @compose2 takes f, g1, and g2, and constructs the @c binary_compose + * instance for you. For example, if @c f returns an int, then + * \code + * int answer = (compose2(f,g1,g2))(x); + * \endcode + * is equivalent to + * \code + * int temp1 = g1(x); + * int temp2 = g2(x); + * int answer = f(temp1,temp2); + * \endcode + * But the first form is more compact, and can be passed around as a + * functor to other algorithms. + * + * @addtogroup SGIextensions + * @{ + */ + /// An \link SGIextensions SGI extension \endlink. + template + class unary_compose + : public unary_function + { + protected: + _Operation1 _M_fn1; + _Operation2 _M_fn2; + + public: + unary_compose(const _Operation1& __x, const _Operation2& __y) + : _M_fn1(__x), _M_fn2(__y) {} + + typename _Operation1::result_type + operator()(const typename _Operation2::argument_type& __x) const + { return _M_fn1(_M_fn2(__x)); } + }; + + /// An \link SGIextensions SGI extension \endlink. + template + inline unary_compose<_Operation1, _Operation2> + compose1(const _Operation1& __fn1, const _Operation2& __fn2) + { return unary_compose<_Operation1,_Operation2>(__fn1, __fn2); } + + /// An \link SGIextensions SGI extension \endlink. + template + class binary_compose + : public unary_function + { + protected: + _Operation1 _M_fn1; + _Operation2 _M_fn2; + _Operation3 _M_fn3; + + public: + binary_compose(const _Operation1& __x, const _Operation2& __y, + const _Operation3& __z) + : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { } + + typename _Operation1::result_type + operator()(const typename _Operation2::argument_type& __x) const + { return _M_fn1(_M_fn2(__x), _M_fn3(__x)); } + }; + + /// An \link SGIextensions SGI extension \endlink. + template + inline binary_compose<_Operation1, _Operation2, _Operation3> + compose2(const _Operation1& __fn1, const _Operation2& __fn2, + const _Operation3& __fn3) + { return binary_compose<_Operation1, _Operation2, _Operation3> + (__fn1, __fn2, __fn3); } + /** @} */ + + /** As an extension, SGI provided a functor called @c identity. When a + * functor is required but no operations are desired, this can be used as a + * pass-through. Its @c operator() returns its argument unchanged. + * + * @addtogroup SGIextensions + */ + template + struct identity : public std::_Identity<_Tp> {}; + + /** @c select1st and @c select2nd are extensions provided by SGI. Their + * @c operator()s + * take a @c std::pair as an argument, and return either the first member + * or the second member, respectively. They can be used (especially with + * the composition functors) to @a strip data from a sequence before + * performing the remainder of an algorithm. + * + * @addtogroup SGIextensions + * @{ + */ + /// An \link SGIextensions SGI extension \endlink. + template + struct select1st : public std::_Select1st<_Pair> {}; + + /// An \link SGIextensions SGI extension \endlink. + template + struct select2nd : public std::_Select2nd<_Pair> {}; + /** @} */ + + // extension documented next + template + struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1> + { + _Arg1 + operator()(const _Arg1& __x, const _Arg2&) const + { return __x; } + }; + + template + struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> + { + _Arg2 + operator()(const _Arg1&, const _Arg2& __y) const + { return __y; } + }; + + /** The @c operator() of the @c project1st functor takes two arbitrary + * arguments and returns the first one, while @c project2nd returns the + * second one. They are extensions provided by SGI. + * + * @addtogroup SGIextensions + * @{ + */ + + /// An \link SGIextensions SGI extension \endlink. + template + struct project1st : public _Project1st<_Arg1, _Arg2> {}; + + /// An \link SGIextensions SGI extension \endlink. + template + struct project2nd : public _Project2nd<_Arg1, _Arg2> {}; + /** @} */ + + // extension documented next + template + struct _Constant_void_fun + { + typedef _Result result_type; + result_type _M_val; + + _Constant_void_fun(const result_type& __v) : _M_val(__v) {} + + const result_type& + operator()() const + { return _M_val; } + }; + + template + struct _Constant_unary_fun + { + typedef _Argument argument_type; + typedef _Result result_type; + result_type _M_val; + + _Constant_unary_fun(const result_type& __v) : _M_val(__v) {} + + const result_type& + operator()(const _Argument&) const + { return _M_val; } + }; + + template + struct _Constant_binary_fun + { + typedef _Arg1 first_argument_type; + typedef _Arg2 second_argument_type; + typedef _Result result_type; + _Result _M_val; + + _Constant_binary_fun(const _Result& __v) : _M_val(__v) {} + + const result_type& + operator()(const _Arg1&, const _Arg2&) const + { return _M_val; } + }; + + /** These three functors are each constructed from a single arbitrary + * variable/value. Later, their @c operator()s completely ignore any + * arguments passed, and return the stored value. + * - @c constant_void_fun's @c operator() takes no arguments + * - @c constant_unary_fun's @c operator() takes one argument (ignored) + * - @c constant_binary_fun's @c operator() takes two arguments (ignored) + * + * The helper creator functions @c constant0, @c constant1, and + * @c constant2 each take a @a result argument and construct variables of + * the appropriate functor type. + * + * @addtogroup SGIextensions + * @{ + */ + /// An \link SGIextensions SGI extension \endlink. + template + struct constant_void_fun + : public _Constant_void_fun<_Result> + { + constant_void_fun(const _Result& __v) + : _Constant_void_fun<_Result>(__v) {} + }; + + /// An \link SGIextensions SGI extension \endlink. + template + struct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument> + { + constant_unary_fun(const _Result& __v) + : _Constant_unary_fun<_Result, _Argument>(__v) {} + }; + + /// An \link SGIextensions SGI extension \endlink. + template + struct constant_binary_fun + : public _Constant_binary_fun<_Result, _Arg1, _Arg2> + { + constant_binary_fun(const _Result& __v) + : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {} + }; + + /// An \link SGIextensions SGI extension \endlink. + template + inline constant_void_fun<_Result> + constant0(const _Result& __val) + { return constant_void_fun<_Result>(__val); } + + /// An \link SGIextensions SGI extension \endlink. + template + inline constant_unary_fun<_Result, _Result> + constant1(const _Result& __val) + { return constant_unary_fun<_Result, _Result>(__val); } + + /// An \link SGIextensions SGI extension \endlink. + template + inline constant_binary_fun<_Result,_Result,_Result> + constant2(const _Result& __val) + { return constant_binary_fun<_Result, _Result, _Result>(__val); } + /** @} */ + + /** The @c subtractive_rng class is documented on + * SGI's site. + * Note that this code assumes that @c int is 32 bits. + * + * @ingroup SGIextensions + */ + class subtractive_rng + : public unary_function + { + private: + unsigned int _M_table[55]; + size_t _M_index1; + size_t _M_index2; + + public: + /// Returns a number less than the argument. + unsigned int + operator()(unsigned int __limit) + { + _M_index1 = (_M_index1 + 1) % 55; + _M_index2 = (_M_index2 + 1) % 55; + _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2]; + return _M_table[_M_index1] % __limit; + } + + void + _M_initialize(unsigned int __seed) + { + unsigned int __k = 1; + _M_table[54] = __seed; + size_t __i; + for (__i = 0; __i < 54; __i++) + { + size_t __ii = (21 * (__i + 1) % 55) - 1; + _M_table[__ii] = __k; + __k = __seed - __k; + __seed = _M_table[__ii]; + } + for (int __loop = 0; __loop < 4; __loop++) + { + for (__i = 0; __i < 55; __i++) + _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55]; + } + _M_index1 = 0; + _M_index2 = 31; + } + + /// Ctor allowing you to initialize the seed. + subtractive_rng(unsigned int __seed) + { _M_initialize(__seed); } + + /// Default ctor; initializes its state with some number you don't see. + subtractive_rng() + { _M_initialize(161803398u); } + }; + + // Mem_fun adaptor helper functions mem_fun1 and mem_fun1_ref, + // provided for backward compatibility, they are no longer part of + // the C++ standard. + + template + inline mem_fun1_t<_Ret, _Tp, _Arg> + mem_fun1(_Ret (_Tp::*__f)(_Arg)) + { return mem_fun1_t<_Ret, _Tp, _Arg>(__f); } + + template + inline const_mem_fun1_t<_Ret, _Tp, _Arg> + mem_fun1(_Ret (_Tp::*__f)(_Arg) const) + { return const_mem_fun1_t<_Ret, _Tp, _Arg>(__f); } + + template + inline mem_fun1_ref_t<_Ret, _Tp, _Arg> + mem_fun1_ref(_Ret (_Tp::*__f)(_Arg)) + { return mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); } + + template + inline const_mem_fun1_ref_t<_Ret, _Tp, _Arg> + mem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const) + { return const_mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif + diff --git a/libstdc++-v3/include/ext/iterator b/libstdc++-v3/include/ext/iterator new file mode 100644 index 000000000..3e8f438ad --- /dev/null +++ b/libstdc++-v3/include/ext/iterator @@ -0,0 +1,116 @@ +// HP/SGI iterator extensions -*- C++ -*- + +// Copyright (C) 2001, 2002, 2004, 2005, 2009 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1996-1998 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +/** @file ext/iterator + * This file is a GNU extension to the Standard C++ Library (possibly + * containing extensions from the HP/SGI STL subset). + */ + +#ifndef _EXT_ITERATOR +#define _EXT_ITERATOR 1 + +#pragma GCC system_header + +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // There are two signatures for distance. In addition to the one + // taking two iterators and returning a result, there is another + // taking two iterators and a reference-to-result variable, and + // returning nothing. The latter seems to be an SGI extension. + // -- pedwards + template + inline void + __distance(_InputIterator __first, _InputIterator __last, + _Distance& __n, std::input_iterator_tag) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + while (__first != __last) + { + ++__first; + ++__n; + } + } + + template + inline void + __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, + _Distance& __n, std::random_access_iterator_tag) + { + // concept requirements + __glibcxx_function_requires(_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __n += __last - __first; + } + + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + inline void + distance(_InputIterator __first, _InputIterator __last, + _Distance& __n) + { + // concept requirements -- taken care of in __distance + __distance(__first, __last, __n, std::__iterator_category(__first)); + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif + diff --git a/libstdc++-v3/include/ext/malloc_allocator.h b/libstdc++-v3/include/ext/malloc_allocator.h new file mode 100644 index 000000000..3aa994d9f --- /dev/null +++ b/libstdc++-v3/include/ext/malloc_allocator.h @@ -0,0 +1,137 @@ +// Allocator that wraps "C" malloc -*- C++ -*- + +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/malloc_allocator.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _MALLOC_ALLOCATOR_H +#define _MALLOC_ALLOCATOR_H 1 + +#include +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::size_t; + using std::ptrdiff_t; + + /** + * @brief An allocator that uses malloc. + * @ingroup allocators + * + * This is precisely the allocator defined in the C++ Standard. + * - all allocation calls malloc + * - all deallocation calls free + */ + template + class malloc_allocator + { + public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef _Tp* pointer; + typedef const _Tp* const_pointer; + typedef _Tp& reference; + typedef const _Tp& const_reference; + typedef _Tp value_type; + + template + struct rebind + { typedef malloc_allocator<_Tp1> other; }; + + malloc_allocator() throw() { } + + malloc_allocator(const malloc_allocator&) throw() { } + + template + malloc_allocator(const malloc_allocator<_Tp1>&) throw() { } + + ~malloc_allocator() throw() { } + + pointer + address(reference __x) const { return std::__addressof(__x); } + + const_pointer + address(const_reference __x) const { return std::__addressof(__x); } + + // NB: __n is permitted to be 0. The C++ standard says nothing + // about what the return value is when __n == 0. + pointer + allocate(size_type __n, const void* = 0) + { + if (__n > this->max_size()) + std::__throw_bad_alloc(); + + pointer __ret = static_cast<_Tp*>(std::malloc(__n * sizeof(_Tp))); + if (!__ret) + std::__throw_bad_alloc(); + return __ret; + } + + // __p is not permitted to be a null pointer. + void + deallocate(pointer __p, size_type) + { std::free(static_cast(__p)); } + + size_type + max_size() const throw() + { return size_t(-1) / sizeof(_Tp); } + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 402. wrong new expression in [some_] allocator::construct + void + construct(pointer __p, const _Tp& __val) + { ::new((void *)__p) value_type(__val); } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template + void + construct(pointer __p, _Args&&... __args) + { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); } +#endif + + void + destroy(pointer __p) { __p->~_Tp(); } + }; + + template + inline bool + operator==(const malloc_allocator<_Tp>&, const malloc_allocator<_Tp>&) + { return true; } + + template + inline bool + operator!=(const malloc_allocator<_Tp>&, const malloc_allocator<_Tp>&) + { return false; } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif diff --git a/libstdc++-v3/include/ext/memory b/libstdc++-v3/include/ext/memory new file mode 100644 index 000000000..ddcfe22b5 --- /dev/null +++ b/libstdc++-v3/include/ext/memory @@ -0,0 +1,198 @@ +// Memory extensions -*- C++ -*- + +// Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1996 + * Silicon Graphics Computer Systems, Inc. + * + * Permission to use, copy, modify, distribute and sell this software + * and its documentation for any purpose is hereby granted without fee, + * provided that the above copyright notice appear in all copies and + * that both that copyright notice and this permission notice appear + * in supporting documentation. Silicon Graphics makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + */ + +/** @file ext/memory + * This file is a GNU extension to the Standard C++ Library (possibly + * containing extensions from the HP/SGI STL subset). + */ + +#ifndef _EXT_MEMORY +#define _EXT_MEMORY 1 + +#pragma GCC system_header + +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::ptrdiff_t; + using std::pair; + using std::__iterator_category; + using std::_Temporary_buffer; + + template + pair<_InputIter, _ForwardIter> + __uninitialized_copy_n(_InputIter __first, _Size __count, + _ForwardIter __result, std::input_iterator_tag) + { + _ForwardIter __cur = __result; + __try + { + for (; __count > 0 ; --__count, ++__first, ++__cur) + std::_Construct(&*__cur, *__first); + return pair<_InputIter, _ForwardIter>(__first, __cur); + } + __catch(...) + { + std::_Destroy(__result, __cur); + __throw_exception_again; + } + } + + template + inline pair<_RandomAccessIter, _ForwardIter> + __uninitialized_copy_n(_RandomAccessIter __first, _Size __count, + _ForwardIter __result, + std::random_access_iterator_tag) + { + _RandomAccessIter __last = __first + __count; + return (pair<_RandomAccessIter, _ForwardIter> + (__last, std::uninitialized_copy(__first, __last, __result))); + } + + template + inline pair<_InputIter, _ForwardIter> + __uninitialized_copy_n(_InputIter __first, _Size __count, + _ForwardIter __result) + { return __gnu_cxx::__uninitialized_copy_n(__first, __count, __result, + __iterator_category(__first)); } + + /** + * @brief Copies the range [first,last) into result. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @return result + (first - last) + * @ingroup SGIextensions + * + * Like copy(), but does not require an initialized output range. + */ + template + inline pair<_InputIter, _ForwardIter> + uninitialized_copy_n(_InputIter __first, _Size __count, + _ForwardIter __result) + { return __gnu_cxx::__uninitialized_copy_n(__first, __count, __result, + __iterator_category(__first)); } + + + // An alternative version of uninitialized_copy_n that constructs + // and destroys objects with a user-provided allocator. + template + pair<_InputIter, _ForwardIter> + __uninitialized_copy_n_a(_InputIter __first, _Size __count, + _ForwardIter __result, + _Allocator __alloc) + { + _ForwardIter __cur = __result; + __try + { + for (; __count > 0 ; --__count, ++__first, ++__cur) + __alloc.construct(&*__cur, *__first); + return pair<_InputIter, _ForwardIter>(__first, __cur); + } + __catch(...) + { + std::_Destroy(__result, __cur, __alloc); + __throw_exception_again; + } + } + + template + inline pair<_InputIter, _ForwardIter> + __uninitialized_copy_n_a(_InputIter __first, _Size __count, + _ForwardIter __result, + std::allocator<_Tp>) + { + return __gnu_cxx::uninitialized_copy_n(__first, __count, __result); + } + + /** + * This class provides similar behavior and semantics of the standard + * functions get_temporary_buffer() and return_temporary_buffer(), but + * encapsulated in a type vaguely resembling a standard container. + * + * By default, a temporary_buffer stores space for objects of + * whatever type the Iter iterator points to. It is constructed from a + * typical [first,last) range, and provides the begin(), end(), size() + * functions, as well as requested_size(). For non-trivial types, copies + * of *first will be used to initialize the storage. + * + * @c malloc is used to obtain underlying storage. + * + * Like get_temporary_buffer(), not all the requested memory may be + * available. Ideally, the created buffer will be large enough to hold a + * copy of [first,last), but if size() is less than requested_size(), + * then this didn't happen. + * + * @ingroup SGIextensions + */ + template ::value_type > + struct temporary_buffer : public _Temporary_buffer<_ForwardIterator, _Tp> + { + /// Requests storage large enough to hold a copy of [first,last). + temporary_buffer(_ForwardIterator __first, _ForwardIterator __last) + : _Temporary_buffer<_ForwardIterator, _Tp>(__first, __last) { } + + /// Destroys objects and frees storage. + ~temporary_buffer() { } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif + diff --git a/libstdc++-v3/include/ext/mt_allocator.h b/libstdc++-v3/include/ext/mt_allocator.h new file mode 100644 index 000000000..91eac24f2 --- /dev/null +++ b/libstdc++-v3/include/ext/mt_allocator.h @@ -0,0 +1,754 @@ +// MT-optimized allocator -*- C++ -*- + +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// 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 of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file ext/mt_allocator.h + * This file is a GNU extension to the Standard C++ Library. + */ + +#ifndef _MT_ALLOCATOR_H +#define _MT_ALLOCATOR_H 1 + +#include +#include +#include +#include +#include + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + using std::size_t; + using std::ptrdiff_t; + + typedef void (*__destroy_handler)(void*); + + /// Base class for pool object. + struct __pool_base + { + // Using short int as type for the binmap implies we are never + // caching blocks larger than 32768 with this allocator. + typedef unsigned short int _Binmap_type; + + // Variables used to configure the behavior of the allocator, + // assigned and explained in detail below. + struct _Tune + { + // Compile time constants for the default _Tune values. + enum { _S_align = 8 }; + enum { _S_max_bytes = 128 }; + enum { _S_min_bin = 8 }; + enum { _S_chunk_size = 4096 - 4 * sizeof(void*) }; + enum { _S_max_threads = 4096 }; + enum { _S_freelist_headroom = 10 }; + + // Alignment needed. + // NB: In any case must be >= sizeof(_Block_record), that + // is 4 on 32 bit machines and 8 on 64 bit machines. + size_t _M_align; + + // Allocation requests (after round-up to power of 2) below + // this value will be handled by the allocator. A raw new/ + // call will be used for requests larger than this value. + // NB: Must be much smaller than _M_chunk_size and in any + // case <= 32768. + size_t _M_max_bytes; + + // Size in bytes of the smallest bin. + // NB: Must be a power of 2 and >= _M_align (and of course + // much smaller than _M_max_bytes). + size_t _M_min_bin; + + // In order to avoid fragmenting and minimize the number of + // new() calls we always request new memory using this + // value. Based on previous discussions on the libstdc++ + // mailing list we have chosen the value below. + // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html + // NB: At least one order of magnitude > _M_max_bytes. + size_t _M_chunk_size; + + // The maximum number of supported threads. For + // single-threaded operation, use one. Maximum values will + // vary depending on details of the underlying system. (For + // instance, Linux 2.4.18 reports 4070 in + // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports + // 65534) + size_t _M_max_threads; + + // Each time a deallocation occurs in a threaded application + // we make sure that there are no more than + // _M_freelist_headroom % of used memory on the freelist. If + // the number of additional records is more than + // _M_freelist_headroom % of the freelist, we move these + // records back to the global pool. + size_t _M_freelist_headroom; + + // Set to true forces all allocations to use new(). + bool _M_force_new; + + explicit + _Tune() + : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin), + _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads), + _M_freelist_headroom(_S_freelist_headroom), + _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false) + { } + + explicit + _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk, + size_t __maxthreads, size_t __headroom, bool __force) + : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin), + _M_chunk_size(__chunk), _M_max_threads(__maxthreads), + _M_freelist_headroom(__headroom), _M_force_new(__force) + { } + }; + + struct _Block_address + { + void* _M_initial; + _Block_address* _M_next; + }; + + const _Tune& + _M_get_options() const + { return _M_options; } + + void + _M_set_options(_Tune __t) + { + if (!_M_init) + _M_options = __t; + } + + bool + _M_check_threshold(size_t __bytes) + { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; } + + size_t + _M_get_binmap(size_t __bytes) + { return _M_binmap[__bytes]; } + + size_t + _M_get_align() + { return _M_options._M_align; } + + explicit + __pool_base() + : _M_options(_Tune()), _M_binmap(0), _M_init(false) { } + + explicit + __pool_base(const _Tune& __options) + : _M_options(__options), _M_binmap(0), _M_init(false) { } + + private: + explicit + __pool_base(const __pool_base&); + + __pool_base& + operator=(const __pool_base&); + + protected: + // Configuration options. + _Tune _M_options; + + _Binmap_type* _M_binmap; + + // Configuration of the pool object via _M_options can happen + // after construction but before initialization. After + // initialization is complete, this variable is set to true. + bool _M_init; + }; + + + /** + * @brief Data describing the underlying memory pool, parameterized on + * threading support. + */ + template + class __pool; + + /// Specialization for single thread. + template<> + class __pool : public __pool_base + { + public: + union _Block_record + { + // Points to the block_record of the next free block. + _Block_record* _M_next; + }; + + struct _Bin_record + { + // An "array" of pointers to the first free block. + _Block_record** _M_first; + + // A list of the initial addresses of all allocated blocks. + _Block_address* _M_address; + }; + + void + _M_initialize_once() + { + if (__builtin_expect(_M_init == false, false)) + _M_initialize(); + } + + void + _M_destroy() throw(); + + char* + _M_reserve_block(size_t __bytes, const size_t __thread_id); + + void + _M_reclaim_block(char* __p, size_t __bytes) throw (); + + size_t + _M_get_thread_id() { return 0; } + + const _Bin_record& + _M_get_bin(size_t __which) + { return _M_bin[__which]; } + + void + _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t) + { } + + explicit __pool() + : _M_bin(0), _M_bin_size(1) { } + + explicit __pool(const __pool_base::_Tune& __tune) + : __pool_base(__tune), _M_bin(0), _M_bin_size(1) { } + + private: + // An "array" of bin_records each of which represents a specific + // power of 2 size. Memory to this "array" is allocated in + // _M_initialize(). + _Bin_record* _M_bin; + + // Actual value calculated in _M_initialize(). + size_t _M_bin_size; + + void + _M_initialize(); + }; + +#ifdef __GTHREADS + /// Specialization for thread enabled, via gthreads.h. + template<> + class __pool : public __pool_base + { + public: + // Each requesting thread is assigned an id ranging from 1 to + // _S_max_threads. Thread id 0 is used as a global memory pool. + // In order to get constant performance on the thread assignment + // routine, we keep a list of free ids. When a thread first + // requests memory we remove the first record in this list and + // stores the address in a __gthread_key. When initializing the + // __gthread_key we specify a destructor. When this destructor + // (i.e. the thread dies) is called, we return the thread id to + // the front of this list. + struct _Thread_record + { + // Points to next free thread id record. NULL if last record in list. + _Thread_record* _M_next; + + // Thread id ranging from 1 to _S_max_threads. + size_t _M_id; + }; + + union _Block_record + { + // Points to the block_record of the next free block. + _Block_record* _M_next; + + // The thread id of the thread which has requested this block. + size_t _M_thread_id; + }; + + struct _Bin_record + { + // An "array" of pointers to the first free block for each + // thread id. Memory to this "array" is allocated in + // _S_initialize() for _S_max_threads + global pool 0. + _Block_record** _M_first; + + // A list of the initial addresses of all allocated blocks. + _Block_address* _M_address; + + // An "array" of counters used to keep track of the amount of + // blocks that are on the freelist/used for each thread id. + // - Note that the second part of the allocated _M_used "array" + // actually hosts (atomic) counters of reclaimed blocks: in + // _M_reserve_block and in _M_reclaim_block those numbers are + // subtracted from the first ones to obtain the actual size + // of the "working set" of the given thread. + // - Memory to these "arrays" is allocated in _S_initialize() + // for _S_max_threads + global pool 0. + size_t* _M_free; + size_t* _M_used; + + // Each bin has its own mutex which is used to ensure data + // integrity while changing "ownership" on a block. The mutex + // is initialized in _S_initialize(). + __gthread_mutex_t* _M_mutex; + }; + + // XXX GLIBCXX_ABI Deprecated + void + _M_initialize(__destroy_handler); + + void + _M_initialize_once() + { + if (__builtin_expect(_M_init == false, false)) + _M_initialize(); + } + + void + _M_destroy() throw(); + + char* + _M_reserve_block(size_t __bytes, const size_t __thread_id); + + void + _M_reclaim_block(char* __p, size_t __bytes) throw (); + + const _Bin_record& + _M_get_bin(size_t __which) + { return _M_bin[__which]; } + + void + _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block, + size_t __thread_id) + { + if (__gthread_active_p()) + { + __block->_M_thread_id = __thread_id; + --__bin._M_free[__thread_id]; + ++__bin._M_used[__thread_id]; + } + } + + // XXX GLIBCXX_ABI Deprecated + _GLIBCXX_CONST void + _M_destroy_thread_key(void*) throw (); + + size_t + _M_get_thread_id(); + + explicit __pool() + : _M_bin(0), _M_bin_size(1), _M_thread_freelist(0) + { } + + explicit __pool(const __pool_base::_Tune& __tune) + : __pool_base(__tune), _M_bin(0), _M_bin_size(1), + _M_thread_freelist(0) + { } + + private: + // An "array" of bin_records each of which represents a specific + // power of 2 size. Memory to this "array" is allocated in + // _M_initialize(). + _Bin_record* _M_bin; + + // Actual value calculated in _M_initialize(). + size_t _M_bin_size; + + _Thread_record* _M_thread_freelist; + void* _M_thread_freelist_initial; + + void + _M_initialize(); + }; +#endif + + template