diff options
| author | Benjamin Kosnik <bkoz@redhat.com> | 2006-09-28 13:40:07 +0000 |
|---|---|---|
| committer | Benjamin Kosnik <bkoz@gcc.gnu.org> | 2006-09-28 13:40:07 +0000 |
| commit | 1b24692f652301d0105b94286a41120d67d4f8e8 (patch) | |
| tree | cddfeb37a2382b40bf6d02b0205a862fad221555 | |
| parent | 4553813629f226082846477bd9e484c681d9b4ec (diff) | |
| download | gcc-1b24692f652301d0105b94286a41120d67d4f8e8.zip gcc-1b24692f652301d0105b94286a41120d67d4f8e8.tar.gz gcc-1b24692f652301d0105b94286a41120d67d4f8e8.tar.bz2 | |
erase_store_hash_fn_imps.hpp: Formatting fixes.
2006-09-28 Benjamin Kosnik <bkoz@redhat.com>
* include/ext/pb_ds/detail/cc_hash_table_map_/
erase_store_hash_fn_imps.hpp: Formatting fixes.
* include/ext/pb_ds/detail/cc_hash_table_map_/
constructor_destructor_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
insert_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
resize_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
constructor_destructor_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
insert_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
entry_list_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
find_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
debug_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
cond_key_dtor_entry_dealtor.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
debug_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
erase_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/cc_hash_table_map_/
resize_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/head.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/leaf.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/node_base.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp: Same.
* include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
erase_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
constructor_destructor_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
insert_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
resize_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
constructor_destructor_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
insert_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
iterator_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
find_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
find_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
debug_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
constructor_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
erase_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/gp_hash_table_map_/
resize_no_store_hash_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/
policy_access_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/node.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
* include/ext/pb_ds/detail/splay_tree_/traits.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/
entry_metadata_base.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/list_update_map_/
iterators_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/
constructors_destructor_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp: Same.
* include/ext/pb_ds/detail/rb_tree_map_/traits.hpp: Same.
From-SVN: r117281
94 files changed, 1251 insertions, 2539 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 7db967b..26c5ee0 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,135 @@ +2006-09-28 Benjamin Kosnik <bkoz@redhat.com> + + * include/ext/pb_ds/detail/cc_hash_table_map_/ + erase_store_hash_fn_imps.hpp: Formatting fixes. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + constructor_destructor_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + insert_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + policy_access_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + resize_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + constructor_destructor_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + insert_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + entry_list_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + find_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + debug_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + constructor_destructor_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + cond_key_dtor_entry_dealtor.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + debug_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + erase_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + iterators_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/cc_hash_table_map_/ + resize_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/head.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/leaf.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/node_base.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp: Same. + * include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + erase_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + constructor_destructor_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + insert_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + policy_access_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + resize_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + constructor_destructor_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + insert_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + iterator_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + info_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + find_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + find_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + debug_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + constructor_destructor_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + erase_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/gp_hash_table_map_/ + resize_no_store_hash_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/ + policy_access_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/ + constructors_destructor_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/node.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same. + * include/ext/pb_ds/detail/splay_tree_/traits.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/ + entry_metadata_base.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/list_update_map_/ + iterators_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/ + constructors_destructor_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp: Same. + * include/ext/pb_ds/detail/rb_tree_map_/traits.hpp: Same. + 2006-09-28 Paolo Carlini <pcarlini@suse.de> * include/tr1/boost_shared_ptr.h: Use __atomic_add_dispatch and diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp index 8fdc97d..c6f361d 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp @@ -75,44 +75,26 @@ namespace pb_ds template<typename Value_Type, class Cmp_Fn, class Allocator> class binomial_heap_ : public PB_DS_BASE_C_DEC { - private: typedef PB_DS_BASE_C_DEC base_type; - typedef typename base_type::node_pointer node_pointer; - typedef typename base_type::const_node_pointer const_node_pointer; public: - + typedef Value_Type value_type; typedef typename Allocator::size_type size_type; - typedef typename Allocator::difference_type difference_type; - - typedef Value_Type value_type; - typedef typename base_type::pointer pointer; - typedef typename base_type::const_pointer const_pointer; - typedef typename base_type::reference reference; - typedef typename base_type::const_reference const_reference; - typedef typename base_type::const_point_iterator const_point_iterator; - typedef typename base_type::point_iterator point_iterator; - typedef typename base_type::const_iterator const_iterator; - typedef typename base_type::iterator iterator; - typedef typename base_type::cmp_fn cmp_fn; - typedef typename base_type::allocator allocator; - public: - binomial_heap_(); binomial_heap_(const Cmp_Fn& r_cmp_fn); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp index 94c1fc6..9223da5 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp @@ -50,9 +50,7 @@ template<typename Other_HT_Map_Type> bool PB_DS_CLASS_C_DEC:: operator==(const Other_HT_Map_Type& other) const -{ - return (cmp_with_other(other)); -} +{ return cmp_with_other(other); } PB_DS_CLASS_T_DEC template<typename Other_Map_Type> @@ -61,27 +59,26 @@ PB_DS_CLASS_C_DEC:: cmp_with_other(const Other_Map_Type& other) const { if (size() != other.size()) - return (false); + return false; for (typename Other_Map_Type::const_iterator it = other.begin(); it != other.end(); ++it) { - const_key_reference r_key =(const_key_reference)PB_DS_V2F(*it); + const_key_reference r_key = const_key_reference(PB_DS_V2F(*it)); const_mapped_pointer p_mapped_value = const_cast<PB_DS_CLASS_C_DEC& >(*this). find_key_pointer(r_key, traits_base::m_store_hash_indicator); if (p_mapped_value == NULL) - return (false); + return false; #ifdef PB_DS_DATA_TRUE_INDICATOR if (p_mapped_value->second != it->second) - return (false); + return false; #endif } - - return (true); + return true; } PB_DS_CLASS_T_DEC @@ -89,6 +86,4 @@ template<typename Other_HT_Map_Type> bool PB_DS_CLASS_C_DEC:: operator!=(const Other_HT_Map_Type& other) const -{ - return (!operator==(other)); -} +{ return !operator==(other); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp index 54859e8..bf5e0bd 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp @@ -49,12 +49,8 @@ namespace pb_ds namespace detail { -#define PB_DS_CLASS_T_DEC \ - template<typename HT_Map> - -#define PB_DS_CLASS_C_DEC \ - PB_DS_CKDED_CLASS_NAME< \ - HT_Map> +#define PB_DS_CLASS_T_DEC template<typename HT_Map> +#define PB_DS_CLASS_C_DEC PB_DS_CKDED_CLASS_NAME<HT_Map> /** * A conditional key destructor, used for exception handling. @@ -64,12 +60,9 @@ namespace pb_ds { public: typedef typename HT_Map::entry entry; - typedef typename HT_Map::entry_allocator entry_allocator; - typedef typename HT_Map::key_type key_type; - public: inline PB_DS_CKDED_CLASS_NAME(entry_allocator* p_a, entry* p_e); @@ -93,10 +86,8 @@ namespace pb_ds PB_DS_CLASS_T_DEC inline PB_DS_CLASS_C_DEC:: - PB_DS_CKDED_CLASS_NAME(entry_allocator* p_a, entry* p_e) : - m_p_a(p_a), - m_p_e(p_e), - m_key_destruct(false), + PB_DS_CKDED_CLASS_NAME(entry_allocator* p_a, entry* p_e) + : m_p_a(p_a), m_p_e(p_e), m_key_destruct(false), m_no_action_destructor(false) { } @@ -104,17 +95,13 @@ namespace pb_ds inline void PB_DS_CLASS_C_DEC:: set_key_destruct() - { - m_key_destruct = true; - } + { m_key_destruct = true; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: set_no_action_destructor() - { - m_no_action_destructor = true; - } + { m_no_action_destructor = true; } PB_DS_CLASS_T_DEC inline @@ -123,10 +110,8 @@ namespace pb_ds { if (m_no_action_destructor) return; - if (m_key_destruct) m_p_e->m_value.first.~key_type(); - m_p_a->deallocate(m_p_e, 1); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp index 7273b0f..4bb1e12 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp @@ -143,7 +143,7 @@ PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : { copy_from_range(other.begin(), other.end()); } - catch (...) + catch(...) { deallocate_all(); throw; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp index 7c38d10..6aac379 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp @@ -51,11 +51,10 @@ PB_DS_CLASS_C_DEC:: constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, integral_constant<int,false>) { // Following lines might throw an exception. - entry_pointer p_e = get_entry(r_val, traits_base::s_no_throw_copies_indicator); + entry_pointer p = get_entry(r_val, traits_base::s_no_throw_copies_indicator); // At this point no exceptions can be thrown. - - p_e->m_p_next = m_entries[pos]; - m_entries[pos] = p_e; + p->m_p_next = m_entries[pos]; + m_entries[pos] = p; _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(r_key);) } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp index 6ebd1f7..08a0b7b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp @@ -51,13 +51,12 @@ PB_DS_CLASS_C_DEC:: constructor_insert_new_imp(const_reference r_val, size_type pos, true_type) { // Following lines might throw an exception. - entry_pointer p_e = get_entry(r_val, - traits_base::s_no_throw_copies_indicator); + entry_pointer p = get_entry(r_val, traits_base::s_no_throw_copies_indicator); // At this point no exceptions can be thrown. - p_e->m_p_next = m_entries[pos]; - p_e->m_hash = ranged_hash_fn_base::operator()((const_key_reference)(PB_DS_V2F(p_e->m_value))).second; + p->m_p_next = m_entries[pos]; + p->m_hash = ranged_hash_fn_base::operator()((const_key_reference)(PB_DS_V2F(p->m_value))).second; - m_entries[pos] = p_e; + m_entries[pos] = p; _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(r_key);) } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp index 42503ed..509008b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp @@ -49,8 +49,7 @@ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: -assert_entry_pointer_valid(const entry_pointer p_e, - store_hash_false_type) const -{ map_debug_base::check_key_exists(PB_DS_V2F(p_e->m_value)); } +assert_entry_pointer_valid(const entry_pointer p, store_hash_false_type) const +{ map_debug_base::check_key_exists(PB_DS_V2F(p->m_value)); } #endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp index cfa2af6..984a7ec 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp @@ -49,11 +49,10 @@ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: -assert_entry_pointer_valid(const entry_pointer p_e, store_hash_true_type) const +assert_entry_pointer_valid(const entry_pointer p_e, store_hash_true_type) const { map_debug_base::check_key_exists(PB_DS_V2F(p_e->m_value)); comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value)); - _GLIBCXX_DEBUG_ASSERT(p_e->m_hash == pos_hash_pair.second); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp index 458ed36..1dd2a16 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp @@ -52,9 +52,7 @@ deallocate_links_in_list(entry_pointer p_e) while (p_e != NULL) { entry_pointer p_dealloc_e = p_e; - p_e = p_e->m_p_next; - s_entry_allocator.deallocate(p_dealloc_e, 1); } } @@ -65,14 +63,11 @@ PB_DS_CLASS_C_DEC:: get_entry(const_reference r_val, no_throw_copies_true_type) { // Following line might throw an exception. - entry_pointer p_e = s_entry_allocator.allocate(1); // Following lines* cannot* throw an exception. - new (&p_e->m_value) value_type(r_val); - - return (p_e); + return p_e; } PB_DS_CLASS_T_DEC @@ -81,18 +76,13 @@ PB_DS_CLASS_C_DEC:: get_entry(const_reference r_val, no_throw_copies_false_type) { // Following line might throw an exception. - entry_pointer p_e = s_entry_allocator.allocate(1); - cond_dealtor_t cond(p_e); // Following lines might throw an exception. - new (&p_e->m_value) value_type(r_val); - cond.set_no_action(); - - return (p_e); + return p_e; } PB_DS_CLASS_T_DEC @@ -100,11 +90,8 @@ inline void PB_DS_CLASS_C_DEC:: rels_entry(entry_pointer p_e) { - /* The following lines cannot throw exceptions - * (unless if key-data dtors do). */ - + // The following lines cannot throw exceptions (unless if key-data dtors do). p_e->m_value.~value_type(); - s_entry_allocator.deallocate(p_e, 1); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp index 3a82138..80e06e9 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp @@ -49,15 +49,11 @@ inline void PB_DS_CLASS_C_DEC:: erase_entry_pointer(entry_pointer& r_p_e) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing( - PB_DS_V2F(r_p_e->m_value))); + _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing(PB_DS_V2F(r_p_e->m_value))); entry_pointer p_e = r_p_e; - r_p_e = r_p_e->m_p_next; - rels_entry(p_e); - _GLIBCXX_DEBUG_ASSERT(m_num_used_e > 0); resize_base::notify_erased(--m_num_used_e); } @@ -68,34 +64,24 @@ inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { + typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_reference const_reference; size_type num_ersd = 0; - for (size_type pos = 0; pos < m_num_e; ++pos) { - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_reference - const_reference; - - while (m_entries[pos] != NULL&& - pred(m_entries[pos]->m_value)) + while (m_entries[pos] != NULL && pred(m_entries[pos]->m_value)) { ++num_ersd; - entry_pointer p_next_e = m_entries[pos]->m_p_next; - erase_entry_pointer(m_entries[pos]); - m_entries[pos] = p_next_e; } entry_pointer p_e = m_entries[pos]; - - while (p_e != NULL&& p_e->m_p_next != NULL) + while (p_e != NULL && p_e->m_p_next != NULL) { if (pred(p_e->m_p_next->m_value)) { ++num_ersd; - erase_entry_pointer(p_e->m_p_next); } else @@ -104,8 +90,7 @@ erase_if(Pred pred) } do_resize_if_needed_no_throw(); - - return (num_ersd); + return num_ersd; } PB_DS_CLASS_T_DEC @@ -116,9 +101,7 @@ clear() for (size_type pos = 0; pos < m_num_e; ++pos) while (m_entries[pos] != NULL) erase_entry_pointer(m_entries[pos]); - do_resize_if_needed_no_throw(); - resize_base::notify_cleared(); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp index 298c580..13a3a6d 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp @@ -41,8 +41,8 @@ /** * @file erase_no_store_hash_fn_imps.hpp - * Contains implementations of cc_ht_map_'s erase related functions, when the hash - * value is not stored. + * Contains implementations of cc_ht_map_'s erase related functions, + * when the hash value is not stored. */ PB_DS_CLASS_T_DEC @@ -51,9 +51,7 @@ PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (erase_in_pos_imp(r_key, - ranged_hash_fn_base::operator()(r_key))); + return erase_in_pos_imp(r_key, ranged_hash_fn_base::operator()(r_key)); } PB_DS_CLASS_T_DEC @@ -62,77 +60,47 @@ PB_DS_CLASS_C_DEC:: erase_in_pos_imp(const_key_reference r_key, size_type pos) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - entry_pointer p_e = m_entries[pos]; - + entry_pointer p_e = m_entries[pos]; resize_base::notify_erase_search_start(); - if (p_e == NULL) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist( - r_key);) - - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (false); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return false; } - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_e->m_value), - r_key)) + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - check_key_exists(r_key);) - - erase_entry_pointer(m_entries[pos]); - + _GLIBCXX_DEBUG_ONLY(map_debug_base:: check_key_exists(r_key);) + erase_entry_pointer(m_entries[pos]); do_resize_if_needed_no_throw(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (true); + return true; } while (true) { entry_pointer p_next_e = p_e->m_p_next; - if (p_next_e == NULL) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - check_key_does_not_exist(r_key);) - - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (false); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return false; } - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_next_e->m_value), - r_key)) + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_next_e->m_value), r_key)) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - check_key_exists(r_key);) - - erase_entry_pointer(p_e->m_p_next); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) + erase_entry_pointer(p_e->m_p_next); do_resize_if_needed_no_throw(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (true); + return true; } - resize_base::notify_erase_search_collision(); - p_e = p_next_e; } } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp index ddd898b..7eb821e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp @@ -41,8 +41,8 @@ /** * @file erase_store_hash_fn_imps.hpp - * Contains implementations of cc_ht_map_'s erase related functions, when the hash - * value is stored. + * Contains implementations of cc_ht_map_'s erase related functions, + * when the hash value is stored. */ PB_DS_CLASS_T_DEC @@ -51,83 +51,50 @@ PB_DS_CLASS_C_DEC:: erase_in_pos_imp(const_key_reference r_key, const comp_hash& r_pos_hash_pair) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - entry_pointer p_e = m_entries[r_pos_hash_pair.first]; - + entry_pointer p_e = m_entries[r_pos_hash_pair.first]; resize_base::notify_erase_search_start(); - if (p_e == NULL) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - check_key_does_not_exist( - r_key);) - - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (false); + _GLIBCXX_DEBUG_ONLY(map_debug_base:: check_key_does_not_exist(r_key);) + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return false; } - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_e->m_value), - p_e->m_hash, - r_key, - r_pos_hash_pair.second)) + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, + r_key, r_pos_hash_pair.second)) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists( - r_key);) - - erase_entry_pointer(m_entries[r_pos_hash_pair.first]); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) + erase_entry_pointer(m_entries[r_pos_hash_pair.first]); do_resize_if_needed_no_throw(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (true); + return true; } while (true) { entry_pointer p_next_e = p_e->m_p_next; - if (p_next_e == NULL) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - check_key_does_not_exist(r_key);) - - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (false); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return false; } - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_next_e->m_value), - p_next_e->m_hash, - r_key, + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_next_e->m_value), + p_next_e->m_hash, r_key, r_pos_hash_pair.second)) { resize_base::notify_erase_search_end(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - check_key_exists( - r_key);) - - erase_entry_pointer(p_e->m_p_next); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) + erase_entry_pointer(p_e->m_p_next); do_resize_if_needed_no_throw(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (true); + return true; } - resize_base::notify_erase_search_collision(); - p_e = p_next_e; } } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp index 942879f..1a72664 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp @@ -50,8 +50,7 @@ PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (find_key_pointer(r_key, traits_base::m_store_extra_indicator)); + return find_key_pointer(r_key, traits_base::m_store_extra_indicator); } PB_DS_CLASS_T_DEC @@ -60,23 +59,19 @@ PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (const_cast<PB_DS_CLASS_C_DEC& >(*this).find_key_pointer( r_key, traits_base::m_store_extra_indicator)); + return const_cast<PB_DS_CLASS_C_DEC& >(*this).find_key_pointer(r_key, + traits_base::m_store_extra_indicator); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: find_end() -{ - return (NULL); -} +{ return NULL; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: find_end() const -{ - return (NULL); -} +{ return NULL; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp index b44f674..423a59a 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp @@ -41,7 +41,7 @@ /** * @file find_store_hash_fn_imps.hpp - * Contains implementations of cc_ht_map_'s find related functions, when the hash - * value is stored. + * Contains implementations of cc_ht_map_'s find related functions, + * when the hash value is stored. */ diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp index dde1d35..519072a 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp @@ -42,41 +42,33 @@ /** * @file info_fn_imps.hpp * Contains implementations of cc_ht_map_'s entire container info related - * functions. + * functions. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const -{ - return (m_num_used_e); -} +{ return m_num_used_e; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const -{ - return (m_entry_allocator.max_size()); -} +{ return m_entry_allocator.max_size(); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const -{ - return (size() == 0); -} +{ return (size() == 0); } PB_DS_CLASS_T_DEC template<typename Other_HT_Map_Type> bool PB_DS_CLASS_C_DEC:: operator==(const Other_HT_Map_Type& other) const -{ - return (cmp_with_other(other)); -} +{ return cmp_with_other(other); } PB_DS_CLASS_T_DEC template<typename Other_Map_Type> @@ -85,27 +77,25 @@ PB_DS_CLASS_C_DEC:: cmp_with_other(const Other_Map_Type& other) const { if (size() != other.size()) - return (false); + return false; for (typename Other_Map_Type::const_iterator it = other.begin(); it != other.end(); ++it) { const_key_reference r_key =(const_key_reference)PB_DS_V2F(*it); - const_mapped_pointer p_mapped_value = const_cast<PB_DS_CLASS_C_DEC& >(*this). find_key_pointer(r_key, traits_base::m_store_hash_indicator); if (p_mapped_value == NULL) - return (false); + return false; #ifdef PB_DS_DATA_TRUE_INDICATOR if (p_mapped_value->second != it->second) - return (false); -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR + return false; +#endif } - - return (true); + return true; } PB_DS_CLASS_T_DEC @@ -113,6 +103,4 @@ template<typename Other_HT_Map_Type> bool PB_DS_CLASS_C_DEC:: operator!=(const Other_HT_Map_Type& other) const -{ - return (!operator==(other)); -} +{ return !operator==(other); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp index 41815c8..799dc37 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp @@ -41,49 +41,36 @@ /** * @file insert_no_store_hash_fn_imps.hpp - * Contains implementations of cc_ht_map_'s insert related functions, when the hash - * value is not stored. + * Contains implementations of cc_ht_map_'s insert related functions, + * when the hash value is not stored. */ PB_DS_CLASS_T_DEC -inline std::pair< - typename PB_DS_CLASS_C_DEC::point_iterator, - bool> +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> PB_DS_CLASS_C_DEC:: insert_imp(const_reference r_val, store_hash_false_type) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - const_key_reference r_key = PB_DS_V2F(r_val); - + const_key_reference r_key = PB_DS_V2F(r_val); const size_type pos = ranged_hash_fn_base::operator()(r_key); - entry_pointer p_e = m_entries[pos]; - resize_base::notify_insert_search_start(); - while (p_e != NULL&& - !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) + while (p_e != NULL && !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), + r_key)) { resize_base::notify_insert_search_collision(); - p_e = p_e->m_p_next; } resize_base::notify_insert_search_end(); - if (p_e != NULL) { _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) - - return ( - std::make_pair( & p_e->m_value, false)); + return std::make_pair(&p_e->m_value, false); } _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return (std::make_pair( - insert_new_imp(r_val, pos), - true)); + return std::make_pair(insert_new_imp(r_val, pos), true); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp index 73a0aa9..b39c764 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp @@ -41,51 +41,37 @@ /** * @file insert_store_hash_fn_imps.hpp - * Contains implementations of cc_ht_map_'s insert related functions, when the hash - * value is stored. + * Contains implementations of cc_ht_map_'s insert related functions, + * when the hash value is stored. */ PB_DS_CLASS_T_DEC -inline std::pair< - typename PB_DS_CLASS_C_DEC::point_iterator, - bool> +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> PB_DS_CLASS_C_DEC:: insert_imp(const_reference r_val, store_hash_true_type) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - const_key_reference r_key = PB_DS_V2F(r_val); - - comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); - + const_key_reference key = PB_DS_V2F(r_val); + comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(key); entry_pointer p_e = m_entries[pos_hash_pair.first]; - resize_base::notify_insert_search_start(); - while (p_e != NULL&& - !hash_eq_fn_base::operator()( - PB_DS_V2F(p_e->m_value), - p_e->m_hash, - r_key, pos_hash_pair.second)) + while (p_e != NULL && !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), + p_e->m_hash, + key, pos_hash_pair.second)) { resize_base::notify_insert_search_collision(); - p_e = p_e->m_p_next; } resize_base::notify_insert_search_end(); - if (p_e != NULL) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) - - return (std::make_pair( & p_e->m_value, false)); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);) + return std::make_pair(&p_e->m_value, false); } - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return (std::make_pair( - insert_new_imp(r_val, pos_hash_pair), - true)); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);) + return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp index eca3791..2c4f6ae 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp @@ -42,7 +42,7 @@ /** * @file iterators_fn_imps.hpp * Contains implementations of cc_ht_map_'s iterators related functions, e.g., - * begin(). + * begin(). */ PB_DS_CLASS_T_DEC @@ -60,19 +60,15 @@ begin() { pointer p_value; std::pair<entry_pointer, size_type> pos; - get_start_it_state(p_value, pos); - - return (iterator(p_value, pos, this)); + return iterator(p_value, pos, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() -{ - return (s_end_it); -} +{ return s_end_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator @@ -81,17 +77,13 @@ begin() const { pointer p_value; std::pair<entry_pointer, size_type> pos; - get_start_it_state(p_value, pos); - - return (const_iterator(p_value, pos, this)); + return const_iterator(p_value, pos, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const -{ - return (s_const_end_it); -} +{ return s_const_end_it; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp index 5ed175f..6c03d45 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp @@ -49,62 +49,46 @@ PB_DS_CLASS_T_DEC Hash_Fn& PB_DS_CLASS_C_DEC:: get_hash_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Hash_Fn& PB_DS_CLASS_C_DEC:: get_hash_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Eq_Fn& PB_DS_CLASS_C_DEC:: get_eq_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Eq_Fn& PB_DS_CLASS_C_DEC:: get_eq_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Comb_Hash_Fn& PB_DS_CLASS_C_DEC:: get_comb_hash_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Comb_Hash_Fn& PB_DS_CLASS_C_DEC:: get_comb_hash_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Resize_Policy& PB_DS_CLASS_C_DEC:: get_resize_policy() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Resize_Policy& PB_DS_CLASS_C_DEC:: get_resize_policy() const -{ - return (*this); -} +{ return *this; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp index fb692b5..ea30fe7 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp @@ -50,21 +50,16 @@ PB_DS_CLASS_C_DEC:: do_resize_if_needed() { if (!resize_base::is_resize_needed()) - return (false); - - resize_imp(resize_base::get_new_size( m_num_e, m_num_used_e)); - - return (true); + return false; + resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); + return true; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: do_resize(size_type size) -{ - resize_imp(resize_base::get_nearest_larger_size( - size)); -} +{ resize_imp(resize_base::get_nearest_larger_size(size)); } PB_DS_CLASS_T_DEC inline void @@ -76,13 +71,13 @@ do_resize_if_needed_no_throw() try { - resize_imp(resize_base::get_new_size( m_num_e, m_num_used_e)); + resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); } catch(...) { } _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC void @@ -90,67 +85,54 @@ PB_DS_CLASS_C_DEC:: resize_imp(size_type new_size) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - if (new_size == m_num_e) - return; + if (new_size == m_num_e) + return; const size_type old_size = m_num_e; - entry_pointer_array a_p_entries_resized; // Following line might throw an exception. - ranged_hash_fn_base::notify_resized(new_size); try { // Following line might throw an exception. - a_p_entries_resized = s_entry_pointer_allocator.allocate(new_size); - m_num_e = new_size; } catch(...) { ranged_hash_fn_base::notify_resized(old_size); - throw; } // At this point no exceptions can be thrown. - resize_imp_no_exceptions(new_size, a_p_entries_resized, old_size); - Resize_Policy::notify_resized(new_size); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: resize_imp_no_exceptions(size_type new_size, entry_pointer_array a_p_entries_resized, size_type old_size) { - std::fill(a_p_entries_resized, a_p_entries_resized + m_num_e,(entry_pointer)NULL); + std::fill(a_p_entries_resized, a_p_entries_resized + m_num_e, + entry_pointer(NULL)); for (size_type pos = 0; pos < old_size; ++pos) { entry_pointer p_e = m_entries[pos]; - while (p_e != NULL) - p_e = resize_imp_no_exceptions_reassign_pointer(p_e, a_p_entries_resized, traits_base::m_store_extra_indicator); + p_e = resize_imp_no_exceptions_reassign_pointer(p_e, a_p_entries_resized, traits_base::m_store_extra_indicator); } m_num_e = new_size; - _GLIBCXX_DEBUG_ONLY(assert_entry_pointer_array_valid(a_p_entries_resized);) - - s_entry_pointer_allocator.deallocate(m_entries, old_size); - + s_entry_pointer_allocator.deallocate(m_entries, old_size); m_entries = a_p_entries_resized; - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} #include <ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp> #include <ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp index 474ac00..18b7a40 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp @@ -54,10 +54,7 @@ resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value)); entry_pointer const p_next_e = p_e->m_p_next; - p_e->m_p_next = a_p_entries_resized[hash_pos]; - a_p_entries_resized[hash_pos] = p_e; - - return (p_next_e); + return p_next_e; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp index d90d578..a61088a 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp @@ -51,15 +51,10 @@ PB_DS_CLASS_C_DEC:: resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, store_hash_true_type) { const comp_hash pos_hash_pair = - ranged_hash_fn_base::operator()( - PB_DS_V2F(p_e->m_value), - p_e->m_hash); + ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash); entry_pointer const p_next_e = p_e->m_p_next; - p_e->m_p_next = a_p_entries_resized[pos_hash_pair.first]; - a_p_entries_resized[pos_hash_pair.first] = p_e; - - return (p_next_e); + return p_next_e; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp index 010834d..8fee010 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp @@ -49,23 +49,17 @@ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const -{ - return (m_num_used_e); -} +{ return m_num_used_e; } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const -{ - return (size() == 0); -} +{ return (size() == 0); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const -{ - return (s_entry_allocator.max_size()); -} +{ return s_entry_allocator.max_size(); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp index e40a45c..21097de 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp @@ -51,15 +51,13 @@ void PB_DS_CLASS_C_DEC:: trace() const { - std::cerr << static_cast<unsigned long>(m_num_e) << " " << - static_cast<unsigned long>(m_num_used_e) << std::endl; + std::cerr << static_cast<unsigned long>(m_num_e) << " " + << static_cast<unsigned long>(m_num_used_e) << std::endl; for (size_type i = 0; i < m_num_e; ++i) { std::cerr << static_cast<unsigned long>(i) << " "; - trace_list(m_entries[i]); - std::cerr << std::endl; } } @@ -70,13 +68,11 @@ PB_DS_CLASS_C_DEC:: trace_list(const_entry_pointer p_l) const { size_type iterated_num_used_e = 0; - while (p_l != NULL) { std::cerr << PB_DS_V2F(p_l->m_value) << " "; - p_l = p_l->m_p_next; } } -#endif // #ifdef PB_DS_HT_MAP_TRACE_ +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp index fa1d9b2..fea4177 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp @@ -161,7 +161,7 @@ PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : new (m_entries + i) entry(other.m_entries[i]); } } - catch (...) + catch(...) { deallocate_all(); throw; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp index 72d2a19..df4af95 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp @@ -48,16 +48,12 @@ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, integral_constant<int,false>) +constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, + false_type) { - _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); - + _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status)k; entry* const p_e = m_entries + pos; - new (&p_e->m_value) mapped_value_type(r_val); - p_e->m_stat = valid_entry_status; - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - insert_new(p_e->m_value.first);) - } + _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(p_e->m_value.first);) +} diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp index d532b84..0e17e36 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp @@ -42,25 +42,19 @@ /** * @file constructor_destructor_store_hash_fn_imps.hpp * Contains implementations of gp_ht_map_'s constructors, destructor, - * and related functions. + * and related functions. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, true_type) +constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, + true_type) { _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); - entry* const p_e = m_entries + pos; - new (&p_e->m_value) mapped_value_type(r_val); - - p_e->m_hash = ranged_probe_fn_base::operator()( - PB_DS_V2F(r_val)).second; - + p_e->m_hash = ranged_probe_fn_base::operator()(PB_DS_V2F(r_val)).second; p_e->m_stat = valid_entry_status; - - _GLIBCXX_DEBUG_ONLY(map_debug_base:: - insert_new(p_e->m_value.first);) - } + _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(p_e->m_value.first);) +} diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp index 5669f60..62afc19 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp @@ -52,11 +52,9 @@ PB_DS_CLASS_C_DEC:: assert_entry_array_valid(const entry_array a_entries, store_hash_false_type) const { size_type iterated_num_used_e = 0; - for (size_type pos = 0; pos < m_num_e; ++pos) { - const_entry_pointer p_e =& a_entries[pos]; - + const_entry_pointer p_e = &a_entries[pos]; switch(p_e->m_stat) { case empty_entry_status: @@ -64,20 +62,15 @@ assert_entry_array_valid(const entry_array a_entries, store_hash_false_type) con break; case valid_entry_status: { - const_key_reference r_key = - PB_DS_V2F(p_e->m_value); - + const_key_reference r_key = PB_DS_V2F(p_e->m_value); map_debug_base::check_key_exists(r_key); - ++iterated_num_used_e; - break; } default: _GLIBCXX_DEBUG_ASSERT(0); }; } - _GLIBCXX_DEBUG_ASSERT(iterated_num_used_e == m_num_used_e); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp index 94d1f87..51acec9 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp @@ -41,8 +41,8 @@ /** * @file erase_no_store_hash_fn_imps.hpp - * Contains implementations of gp_ht_map_'s erase related functions, when the hash - * value is not stored. + * Contains implementations of gp_ht_map_'s erase related functions, + * when the hash value is not stored. */ PB_DS_CLASS_T_DEC @@ -51,44 +51,31 @@ PB_DS_CLASS_C_DEC:: erase_imp(const_key_reference r_key, false_type) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) - - size_type hash = ranged_probe_fn_base::operator()(r_key); - + size_type hash = ranged_probe_fn_base::operator()(r_key); size_type i; - resize_base::notify_erase_search_start(); for (i = 0; i < m_num_e; ++i) { - const size_type pos = - ranged_probe_fn_base::operator()( r_key, hash, i); - + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); entry* const p_e = m_entries + pos; - switch(p_e->m_stat) { case empty_entry_status: { resize_base::notify_erase_search_end(); - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist( r_key)); - - return (false); + return false; } break; case valid_entry_status: - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_e->m_value), - r_key)) + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) { resize_base::notify_erase_search_end(); - erase_entry(p_e); - do_resize_if_needed_no_throw(); - - return (true); + return true; } break; case erased_entry_status: @@ -96,12 +83,9 @@ erase_imp(const_key_reference r_key, false_type) default: _GLIBCXX_DEBUG_ASSERT(0); }; - resize_base::notify_erase_search_collision(); } - resize_base::notify_erase_search_end(); - - return (false); + return false; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp index 77f1aa3..71c498b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp @@ -41,54 +41,41 @@ /** * @file erase_store_hash_fn_imps.hpp - * Contains implementations of gp_ht_map_'s erase related functions, when the hash - * value is stored. + * Contains implementations of gp_ht_map_'s erase related functions, + * when the hash value is stored. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: -erase_imp(const_key_reference r_key, true_type) +erase_imp(const_key_reference r_key, true_type) { - const comp_hash pos_hash_pair = - ranged_probe_fn_base::operator()(r_key); - + const comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); size_type i; - resize_base::notify_erase_search_start(); - for (i = 0; i < m_num_e; ++i) { - const size_type pos = ranged_probe_fn_base::operator()( r_key, pos_hash_pair.second, i); + const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i); entry* const p_e = m_entries + pos; - switch(p_e->m_stat) { case empty_entry_status: { resize_base::notify_erase_search_end(); - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist( r_key)); - - return (false); + return false; } break; case valid_entry_status: - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_e->m_value), - p_e->m_hash, - r_key, - pos_hash_pair.second)) + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, + r_key, pos_hash_pair.second)) { resize_base::notify_erase_search_end(); - erase_entry(p_e); - do_resize_if_needed_no_throw(); - - return (true); + return true; } break; case erased_entry_status: @@ -99,9 +86,7 @@ erase_imp(const_key_reference r_key, true_type) resize_base::notify_erase_search_collision(); } - resize_base::notify_erase_search_end(); - - return (false); + return false; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp index f203850..ec67b5f 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp @@ -41,8 +41,8 @@ /** * @file find_no_store_hash_fn_imps.hpp - * Contains implementations of gp_ht_map_'s find related functions, when the hash - * value is not stored. + * Contains implementations of gp_ht_map_'s find related functions, + * when the hash value is not stored. */ PB_DS_CLASS_T_DEC diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp index 8982607..e43c129 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp @@ -41,6 +41,6 @@ /** * @file find_store_hash_fn_imps.hpp - * Contains implementations of gp_ht_map_'s insert related functions, when the hash - * value is stored. + * Contains implementations of gp_ht_map_'s insert related functions, + * when the hash value is stored. */ diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp index 4d527ba..bd6c186 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp @@ -457,8 +457,7 @@ namespace pb_ds const size_type pos = find_ins_pos(key, traits_base::m_store_extra_indicator); - entry_pointer p_e =& m_entries[pos]; - + entry_pointer p_e = &m_entries[pos]; if (p_e->m_stat != valid_entry_status) return insert_new_imp(value_type(key, mapped_type()), pos)->second; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp index 071399d..f24fa8e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp @@ -49,22 +49,16 @@ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const -{ - return (m_num_used_e); -} +{ return m_num_used_e; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const -{ - return (s_entry_allocator.max_size()); -} +{ return s_entry_allocator.max_size(); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const -{ - return (size() == 0); -} +{ return (size() == 0); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp index dcb712e..49d71e1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp @@ -41,8 +41,8 @@ /** * @file insert_no_store_hash_fn_imps.hpp - * Contains implementations of gp_ht_map_'s insert related functions, when the hash - * value is not stored. + * Contains implementations of gp_ht_map_'s insert related functions, + * when the hash value is not stored. */ PB_DS_CLASS_T_DEC @@ -51,35 +51,25 @@ PB_DS_CLASS_C_DEC:: find_ins_pos(const_key_reference r_key, store_hash_false_type) { size_type hash = ranged_probe_fn_base::operator()(r_key); - size_type i; /* The insertion position is initted to a non-legal value to indicate * that it has not been initted yet. */ size_type ins_pos = m_num_e; - resize_base::notify_insert_search_start(); - for (i = 0; i < m_num_e; ++i) { - const size_type pos = - ranged_probe_fn_base::operator()(r_key, hash, i); - + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); _GLIBCXX_DEBUG_ASSERT(pos < m_num_e); - entry* const p_e = m_entries + pos; - switch(p_e->m_stat) { case empty_entry_status: { resize_base::notify_insert_search_end(); - - _GLIBCXX_DEBUG_ONLY( - map_debug_base::check_key_does_not_exist(r_key);) - - return ((ins_pos == m_num_e)? pos : ins_pos); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) + return (ins_pos == m_num_e) ? pos : ins_pos; } break; case erased_entry_status: @@ -87,14 +77,11 @@ find_ins_pos(const_key_reference r_key, store_hash_false_type) ins_pos = pos; break; case valid_entry_status: - if (hash_eq_fn_base::operator()( - PB_DS_V2F(p_e->m_value), r_key)) + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) { resize_base::notify_insert_search_end(); - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) - - return (pos); + return pos; } break; default: @@ -103,13 +90,10 @@ find_ins_pos(const_key_reference r_key, store_hash_false_type) resize_base::notify_insert_search_collision(); } - resize_base::notify_insert_search_end(); - if (ins_pos == m_num_e) throw insert_error(); - - return (ins_pos); + return ins_pos; } PB_DS_CLASS_T_DEC @@ -118,23 +102,16 @@ PB_DS_CLASS_C_DEC:: insert_imp(const_reference r_val, store_hash_false_type) { const_key_reference r_key = PB_DS_V2F(r_val); - - const size_type pos = - find_ins_pos(r_key, traits_base::m_store_extra_indicator); + const size_type pos = find_ins_pos(r_key, + traits_base::m_store_extra_indicator); if (m_entries[pos].m_stat == valid_entry_status) { _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) - - return (std::make_pair( - & (m_entries + pos)->m_value, - false)); + return std::make_pair(&(m_entries + pos)->m_value, false); } _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); - - return (std::make_pair( - insert_new_imp(r_val, pos), - true)); + return std::make_pair(insert_new_imp(r_val, pos), true); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp index 4ef9b20..8f6861c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp @@ -41,8 +41,8 @@ /** * @file insert_store_hash_fn_imps.hpp - * Contains implementations of gp_ht_map_'s find related functions, when the hash - * value is stored. + * Contains implementations of gp_ht_map_'s find related functions, + * when the hash value is stored. */ PB_DS_CLASS_T_DEC @@ -70,12 +70,11 @@ find_ins_pos(const_key_reference r_key, store_hash_true_type) case empty_entry_status: { resize_base::notify_insert_search_end(); - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - return ((ins_pos == m_num_e) ? - std::make_pair(pos, pos_hash_pair.second) : - std::make_pair(ins_pos, pos_hash_pair.second)); + return ((ins_pos == m_num_e) ? + std::make_pair(pos, pos_hash_pair.second) : + std::make_pair(ins_pos, pos_hash_pair.second)); } break; case erased_entry_status: diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp index a73109c..0f5e835 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp @@ -60,19 +60,15 @@ begin() { pointer_ p_value; size_type pos; - get_start_it_state(p_value, pos); - - return (iterator(p_value, pos, this)); + return iterator(p_value, pos, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() -{ - return (s_end_it); -} +{ return s_end_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator @@ -81,17 +77,13 @@ begin() const { const_pointer_ p_value; size_type pos; - get_start_it_state(p_value, pos); - - return (const_iterator( p_value, pos, this)); + return const_iterator(p_value, pos, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const -{ - return (s_const_end_it); -} +{ return s_const_end_it; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp index 593c8fd..903fc34 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp @@ -49,78 +49,58 @@ PB_DS_CLASS_T_DEC Hash_Fn& PB_DS_CLASS_C_DEC:: get_hash_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Hash_Fn& PB_DS_CLASS_C_DEC:: get_hash_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Eq_Fn& PB_DS_CLASS_C_DEC:: get_eq_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Eq_Fn& PB_DS_CLASS_C_DEC:: get_eq_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Probe_Fn& PB_DS_CLASS_C_DEC:: get_probe_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Probe_Fn& PB_DS_CLASS_C_DEC:: get_probe_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Comb_Probe_Fn& PB_DS_CLASS_C_DEC:: get_comb_probe_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Comb_Probe_Fn& PB_DS_CLASS_C_DEC:: get_comb_probe_fn() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC Resize_Policy& PB_DS_CLASS_C_DEC:: get_resize_policy() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Resize_Policy& PB_DS_CLASS_C_DEC:: get_resize_policy() const -{ - return (*this); -} +{ return *this; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp index d799804..05c9e8c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp @@ -73,7 +73,7 @@ do_resize_if_needed_no_throw() { resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); } - catch (...) + catch(...) { } _GLIBCXX_DEBUG_ONLY(assert_valid();) @@ -108,7 +108,7 @@ resize_imp(size_type new_size) { resize_imp(a_entries_resized, old_size); } - catch (...) + catch(...) { erase_all_valid_entries(a_entries_resized, new_size); m_num_e = old_size; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp index 32e1b11..14a913d 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp @@ -48,29 +48,21 @@ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash_false_type) +resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, + store_hash_false_type) { const_key_reference r_key = PB_DS_V2F(p_e->m_value); - size_type hash = ranged_probe_fn_base::operator()(r_key); - size_type i; - for (i = 0; i < m_num_e; ++i) { - const size_type pos = - ranged_probe_fn_base::operator()(r_key, hash, i); - + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); entry_pointer p_new_e = a_entries_resized + pos; - switch(p_new_e->m_stat) { case empty_entry_status: - new (&p_new_e->m_value) value_type(p_e->m_value); - p_new_e->m_stat = valid_entry_status; - return; case erased_entry_status: _GLIBCXX_DEBUG_ASSERT(0); @@ -81,7 +73,6 @@ resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash _GLIBCXX_DEBUG_ASSERT(0); }; } - throw insert_error(); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp index e3dd24c..f471ed3 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp @@ -48,32 +48,23 @@ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash_true_type) +resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, + store_hash_true_type) { const_key_reference r_key = PB_DS_V2F(p_e->m_value); - - size_type hash = - ranged_probe_fn_base::operator()(r_key, p_e->m_hash); + size_type hash = ranged_probe_fn_base::operator()(r_key, p_e->m_hash); size_type i; - for (i = 0; i < m_num_e; ++i) { - const size_type pos = - ranged_probe_fn_base::operator()(r_key, hash, i); - + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); entry_pointer p_new_e = a_entries_resized + pos; - switch(p_new_e->m_stat) { case empty_entry_status: - new (&p_new_e->m_value) value_type(p_e->m_value); - p_new_e->m_hash = hash; - p_new_e->m_stat = valid_entry_status; - return; case erased_entry_status: _GLIBCXX_DEBUG_ASSERT(0); @@ -84,7 +75,6 @@ resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash _GLIBCXX_DEBUG_ASSERT(0); }; } - throw insert_error(); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp index 41a493d..7d711a2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp @@ -63,4 +63,4 @@ namespace pb_ds } // namespace detail } // namespace pb_ds -#endif // #ifndef PB_DS_LU_MAP_ENTRY_METADATA_BASE_HPP +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp index d23c76b..85ac02d 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp @@ -50,33 +50,26 @@ PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) - - if (m_p_l == NULL) - return false; + if (m_p_l == NULL) + return false; if (s_eq_fn(r_key, PB_DS_V2F(m_p_l->m_value))) { entry_pointer p_next = m_p_l->m_p_next; - actual_erase_entry(m_p_l); - m_p_l = p_next; - return true; } entry_pointer p_l = m_p_l; - while (p_l->m_p_next != NULL) if (s_eq_fn(r_key, PB_DS_V2F(p_l->m_p_next->m_value))) { erase_next(p_l); - return true; } else p_l = p_l->m_p_next; - return false; } @@ -95,17 +88,12 @@ PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) - - size_type num_ersd = 0; - - while (m_p_l != NULL&& pred(m_p_l->m_value)) + size_type num_ersd = 0; + while (m_p_l != NULL && pred(m_p_l->m_value)) { entry_pointer p_next = m_p_l->m_p_next; - ++num_ersd; - actual_erase_entry(m_p_l); - m_p_l = p_next; } @@ -113,13 +101,11 @@ erase_if(Pred pred) return num_ersd; entry_pointer p_l = m_p_l; - while (p_l->m_p_next != NULL) { if (pred(p_l->m_p_next->m_value)) { ++num_ersd; - erase_next(p_l); } else @@ -127,8 +113,7 @@ erase_if(Pred pred) } _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) - - return (num_ersd); + return num_ersd; } PB_DS_CLASS_T_DEC @@ -139,11 +124,8 @@ erase_next(entry_pointer p_l) _GLIBCXX_DEBUG_ASSERT(p_l != NULL); _GLIBCXX_DEBUG_ASSERT(p_l != m_p_l); _GLIBCXX_DEBUG_ASSERT(p_l->m_p_next != NULL); - entry_pointer p_next_l = p_l->m_p_next->m_p_next; - actual_erase_entry(p_l->m_p_next); - p_l->m_p_next = p_next_l; } @@ -152,11 +134,8 @@ void PB_DS_CLASS_C_DEC:: actual_erase_entry(entry_pointer p_l) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing( - PB_DS_V2F(p_l->m_value));) - - p_l->~entry(); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing(PB_DS_V2F(p_l->m_value));) + p_l->~entry(); s_entry_allocator.deallocate(p_l, 1); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp index dd43185..37c173d 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp @@ -51,35 +51,26 @@ find_imp(const_key_reference r_key) const { if (m_p_l == NULL) return NULL; - if (s_eq_fn(r_key, PB_DS_V2F(m_p_l->m_value))) { apply_update(m_p_l, s_metadata_type_indicator); - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) - - return m_p_l; + return m_p_l; } entry_pointer p_l = m_p_l; - while (p_l->m_p_next != NULL) { entry_pointer p_next = p_l->m_p_next; - if (s_eq_fn(r_key, PB_DS_V2F(p_next->m_value))) { if (apply_update(p_next, s_metadata_type_indicator)) { p_l->m_p_next = p_next->m_p_next; - p_next->m_p_next = m_p_l; - m_p_l = p_next; - return m_p_l; } - return p_next; } else @@ -87,8 +78,7 @@ find_imp(const_key_reference r_key) const } _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return NULL; + return NULL; } PB_DS_CLASS_T_DEC @@ -96,15 +86,11 @@ template<typename Metadata> inline bool PB_DS_CLASS_C_DEC:: apply_update(entry_pointer p_l, type_to_type<Metadata>) -{ - return s_update_policy(p_l->m_update_metadata); -} +{ return s_update_policy(p_l->m_update_metadata); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: apply_update(entry_pointer, type_to_type<null_lu_metadata>) -{ - return s_update_policy(s_null_lu_metadata); -} +{ return s_update_policy(s_null_lu_metadata); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp index 56bc9be..a7fe8c4 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp @@ -48,22 +48,16 @@ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const -{ - return (std::distance(begin(), end())); -} +{ return std::distance(begin(), end()); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const -{ - return (s_entry_allocator.max_size()); -} +{ return s_entry_allocator.max_size(); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const -{ - return (m_p_l == NULL); -} +{ return (m_p_l == NULL); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp index a9b94ea..af60c07 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp @@ -52,29 +52,21 @@ PB_DS_CLASS_C_DEC:: insert(const_reference r_val) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - entry_pointer p_l = find_imp(PB_DS_V2F(r_val)); + entry_pointer p_l = find_imp(PB_DS_V2F(r_val)); if (p_l != NULL) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists( - PB_DS_V2F(r_val));) - - return std::make_pair(point_iterator(&p_l->m_value), false); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(PB_DS_V2F(r_val));) + return std::make_pair(point_iterator(&p_l->m_value), false); } - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist( - PB_DS_V2F(r_val));) - - p_l = allocate_new_entry(r_val, PB_DS_TYPES_TRAITS_C_DEC::m_no_throw_copies_indicator); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(PB_DS_V2F(r_val));) + p_l = allocate_new_entry(r_val, traits_base::m_no_throw_copies_indicator); p_l->m_p_next = m_p_l; - m_p_l = p_l; - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return std::make_pair(point_iterator(&p_l->m_value), true); + return std::make_pair(point_iterator(&p_l->m_value), true); } PB_DS_CLASS_T_DEC @@ -83,20 +75,13 @@ PB_DS_CLASS_C_DEC:: allocate_new_entry(const_reference r_val, false_type) { entry_pointer p_l = s_entry_allocator.allocate(1); - cond_dealtor_t cond(p_l); - - new (const_cast<void* >( - static_cast<const void* >(&p_l->m_value))) + new (const_cast<void* >(static_cast<const void* >(&p_l->m_value))) value_type(r_val); cond.set_no_action(); - - _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new( - PB_DS_V2F(r_val));) - - init_entry_metadata(p_l, s_metadata_type_indicator); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));) + init_entry_metadata(p_l, s_metadata_type_indicator); return p_l; } @@ -106,14 +91,9 @@ PB_DS_CLASS_C_DEC:: allocate_new_entry(const_reference r_val, true_type) { entry_pointer p_l = s_entry_allocator.allocate(1); - new (&p_l->m_value) value_type(r_val); - - _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new( - PB_DS_V2F(r_val));) - - init_entry_metadata(p_l, s_metadata_type_indicator); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));) + init_entry_metadata(p_l, s_metadata_type_indicator); return p_l; } @@ -122,9 +102,7 @@ template<typename Metadata> inline void PB_DS_CLASS_C_DEC:: init_entry_metadata(entry_pointer p_l, type_to_type<Metadata>) -{ - new (&p_l->m_update_metadata) Metadata(s_update_policy()); -} +{ new (&p_l->m_update_metadata) Metadata(s_update_policy()); } PB_DS_CLASS_T_DEC inline void diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp index 4fd7207..e962032 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp @@ -52,11 +52,9 @@ begin() if (m_p_l == NULL) { _GLIBCXX_DEBUG_ASSERT(empty()); - - return (end()); + return end(); } - - return (iterator(&m_p_l->m_value, m_p_l, this)); + return iterator(&m_p_l->m_value, m_p_l, this); } PB_DS_CLASS_T_DEC @@ -67,28 +65,22 @@ begin() const if (m_p_l == NULL) { _GLIBCXX_DEBUG_ASSERT(empty()); - - return (end()); + return end(); } - - return (iterator(&m_p_l->m_value, m_p_l, - const_cast<PB_DS_CLASS_C_DEC* >(this))); + return iterator(&m_p_l->m_value, m_p_l, const_cast<PB_DS_CLASS_C_DEC* >(this)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() -{ - return (iterator(NULL, NULL, this)); -} +{ return iterator(NULL, NULL, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const { - return (const_iterator(NULL, NULL, - const_cast<PB_DS_CLASS_C_DEC* const>(this))); + return const_iterator(NULL, NULL, const_cast<PB_DS_CLASS_C_DEC* const>(this)); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp index 6eaa370..9014fd8 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp @@ -113,47 +113,30 @@ namespace pb_ds #endif public PB_DS_TYPES_TRAITS_C_DEC { - private: + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; - struct entry : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type> + struct entry + : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type> { - typename PB_DS_TYPES_TRAITS_C_DEC::value_type m_value; - + typename traits_base::value_type m_value; typename Allocator::template rebind<entry>::other::pointer m_p_next; }; - typedef - typename Allocator::template rebind<entry>::other - entry_allocator; - + typedef typename Allocator::template rebind<entry>::other entry_allocator; typedef typename entry_allocator::pointer entry_pointer; - typedef typename entry_allocator::const_pointer const_entry_pointer; - typedef typename entry_allocator::reference entry_reference; - typedef typename entry_allocator::const_reference const_entry_reference; - typedef - typename Allocator::template rebind<entry_pointer>::other - entry_pointer_allocator; - + typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator; typedef typename entry_pointer_allocator::pointer entry_pointer_array; - typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type_; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer_; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer - const_pointer_; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference_; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_reference - const_reference_; + typedef typename traits_base::value_type value_type_; + typedef typename traits_base::pointer pointer_; + typedef typename traits_base::const_pointer const_pointer_; + typedef typename traits_base::reference reference_; + typedef typename traits_base::const_reference const_reference_; #define PB_DS_GEN_POS entry_pointer @@ -164,63 +147,39 @@ namespace pb_ds #undef PB_DS_GEN_POS - public: - typedef typename Allocator::size_type size_type; +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; +#endif - typedef typename Allocator::difference_type difference_type; + typedef typename traits_base:: no_throw_copies_false_type no_throw_copies_false_type; - typedef Eq_Fn eq_fn; + typedef typename traits_base:: no_throw_copies_true_type no_throw_copies_true_type; - typedef Allocator allocator; + typedef cond_dealtor<entry, Allocator> cond_dealtor_t; + public: + typedef Allocator allocator; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::difference_type difference_type; + typedef Eq_Fn eq_fn; typedef Update_Policy update_policy; - typedef typename Update_Policy::metadata_type update_metadata; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer - const_key_pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference - const_key_reference; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer - mapped_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer - const_mapped_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference - mapped_reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference - const_mapped_reference; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_reference - const_reference; + typedef typename traits_base::key_type key_type; + typedef typename traits_base::key_pointer key_pointer; + typedef typename traits_base::const_key_pointer const_key_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::const_key_reference const_key_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::const_mapped_pointer const_mapped_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::const_mapped_reference const_mapped_reference; + typedef typename traits_base::value_type value_type; + typedef typename traits_base::pointer pointer; + typedef typename traits_base::const_pointer const_pointer; + typedef typename traits_base::reference reference; + typedef typename traits_base::const_reference const_reference; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef point_iterator_ point_iterator; @@ -243,10 +202,9 @@ namespace pb_ds typedef const_iterator_ const_iterator; public: - PB_DS_CLASS_NAME(); - PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); virtual ~PB_DS_CLASS_NAME(); @@ -255,7 +213,7 @@ namespace pb_ds PB_DS_CLASS_NAME(It first_it, It last_it); void - swap(PB_DS_CLASS_C_DEC& other); + swap(PB_DS_CLASS_C_DEC&); inline size_type size() const; @@ -279,7 +237,7 @@ namespace pb_ds } inline std::pair<point_iterator, bool> - insert(const_reference r_val); + insert(const_reference); inline point_iterator find(const_key_reference r_key) @@ -298,11 +256,11 @@ namespace pb_ds } inline bool - erase(const_key_reference r_key); + erase(const_key_reference); template<typename Pred> inline size_type - erase_if(Pred pred); + erase_if(Pred); void clear(); @@ -329,90 +287,65 @@ namespace pb_ds trace() const; #endif - private: - typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; - -#ifdef _GLIBCXX_DEBUG - typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; -#endif - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC:: - no_throw_copies_false_type - no_throw_copies_false_type; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC:: - no_throw_copies_true_type - no_throw_copies_true_type; - protected: template<typename It> void - copy_from_range(It first_it, It last_it); + copy_from_range(It, It); private: +#ifdef PB_DS_DATA_TRUE_INDICATOR + friend class iterator_; +#endif + + friend class const_iterator_; inline entry_pointer - allocate_new_entry(const_reference r_val, false_type); + allocate_new_entry(const_reference, false_type); inline entry_pointer - allocate_new_entry(const_reference r_val, true_type); + allocate_new_entry(const_reference, true_type); template<typename Metadata> inline static void - init_entry_metadata(entry_pointer p_l, type_to_type<Metadata>); + init_entry_metadata(entry_pointer, type_to_type<Metadata>); inline static void - init_entry_metadata(entry_pointer p_l, type_to_type<null_lu_metadata>); + init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>); void deallocate_all(); void - erase_next(entry_pointer p_l); + erase_next(entry_pointer); void - actual_erase_entry(entry_pointer p_l); + actual_erase_entry(entry_pointer); void inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const { r_pos = r_pos->m_p_next; - r_p_value = (r_pos == NULL)? NULL :& r_pos->m_value; + r_p_value = (r_pos == NULL) ? NULL : &r_pos->m_value; } template<typename Metadata> inline static bool - apply_update(entry_pointer p_l, type_to_type<Metadata>); + apply_update(entry_pointer, type_to_type<Metadata>); inline static bool - apply_update(entry_pointer p_l, type_to_type<null_lu_metadata>); + apply_update(entry_pointer, type_to_type<null_lu_metadata>); inline entry_pointer - find_imp(const_key_reference r_key) const; - - private: - mutable entry_pointer m_p_l; - - typedef cond_dealtor< entry, Allocator> cond_dealtor_t; - -#ifdef PB_DS_DATA_TRUE_INDICATOR - friend class iterator_; -#endif - - friend class const_iterator_; + find_imp(const_key_reference) const; static entry_allocator s_entry_allocator; - static Eq_Fn s_eq_fn; - static Update_Policy s_update_policy; - static type_to_type<update_metadata> s_metadata_type_indicator; - static null_lu_metadata s_null_lu_metadata; + + mutable entry_pointer m_p_l; }; #include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp> @@ -426,10 +359,9 @@ namespace pb_ds #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC -#undef PB_DS_TYPES_TRAITS_C_DEC +#undef PB_DS_TYPES_TRAITS_C_DEC #undef PB_DS_MAP_DEBUG_BASE_C_DEC #undef PB_DS_CLASS_NAME - #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp index f406bd8..28bd7c4 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp @@ -52,18 +52,14 @@ PB_DS_CLASS_C_DEC:: trace() const { std::cerr << m_p_l << std::endl << std::endl; - const_entry_pointer p_l = m_p_l; - while (p_l != NULL) { std::cerr << PB_DS_V2F(p_l->m_value) << std::endl; - p_l = p_l->m_p_next; } - std::cerr << std::endl; } -#endif // #ifdef PB_DS_LU_MAP_TRACE_ +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp index e8b418d..b1a3655 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp @@ -54,7 +54,7 @@ assert_valid() const std::cout << "av1" << std::endl; if (m_a_values == NULL || m_end_it == NULL || m_size == 0) - _GLIBCXX_DEBUG_ASSERT(m_a_values == NULL&& m_end_it == NULL && m_size == 0); + _GLIBCXX_DEBUG_ASSERT(m_a_values == NULL && m_end_it == NULL && m_size == 0); std::cout << "av2" << std::endl; assert_iterators(); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp index c6ff353..936d5492 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp @@ -50,30 +50,23 @@ PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - if (m_size == 0) - { - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return; - } - else - { - reallocate_metadata((node_update* )this, 0); - - cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); - } + if (m_size == 0) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return; + } + else + { + reallocate_metadata((node_update* )this, 0); + cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); + } _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();) - - m_a_values = NULL; - + m_a_values = NULL; m_size = 0; - m_end_it = m_a_values; - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC template<typename Pred> @@ -85,14 +78,11 @@ erase_if(Pred pred) #ifdef PB_DS_REGRESSION typename Allocator::group_throw_prob_adjustor adjust(m_size); -#endif // #ifdef PB_DS_REGRESSION +#endif size_type new_size = 0; - size_type num_val_ersd = 0; - iterator source_it = m_a_values; - for (source_it = begin(); source_it != m_end_it; ++source_it) if (!pred(*source_it)) ++new_size; @@ -102,35 +92,26 @@ erase_if(Pred pred) if (new_size == 0) { clear(); - - return (num_val_ersd); + return num_val_ersd; } value_vector a_new_values = s_value_alloc.allocate(new_size); - iterator target_it = a_new_values; - cond_dtor<size_type> cd(a_new_values, target_it, new_size); - _GLIBCXX_DEBUG_ONLY(map_debug_base::clear()); - for (source_it = begin(); source_it != m_end_it; ++source_it) { if (!pred(*source_it)) { - new (const_cast<void* >( - static_cast<const void* >(target_it))) + new (const_cast<void*>(static_cast<const void* >(target_it))) value_type(*source_it); - _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new( - PB_DS_V2F(*source_it))); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(*source_it))); ++target_it; } } reallocate_metadata((node_update* )this, new_size); - cd.set_no_action(); { @@ -138,16 +119,11 @@ erase_if(Pred pred) } m_a_values = a_new_values; - m_size = new_size; - m_end_it = target_it; - update(node_begin(), (node_update* )this); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (num_val_ersd); + return num_val_ersd; } PB_DS_CLASS_T_DEC @@ -157,21 +133,17 @@ PB_DS_CLASS_C_DEC:: erase_imp(It it) { _GLIBCXX_DEBUG_ONLY(assert_valid();) + if (it == end()) + return end(); - if (it == end()) - return end(); - - _GLIBCXX_DEBUG_ONLY( - PB_DS_CLASS_C_DEC::check_key_exists(PB_DS_V2F(*it));) + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::check_key_exists(PB_DS_V2F(*it));) #ifdef PB_DS_REGRESSION typename Allocator::group_throw_prob_adjustor adjust(m_size); -#endif // #ifdef PB_DS_REGRESSION +#endif _GLIBCXX_DEBUG_ASSERT(m_size > 0); - value_vector a_values = s_value_alloc.allocate(m_size - 1); - iterator source_it = begin(); iterator source_end_it = end(); iterator target_it = a_values; @@ -181,48 +153,36 @@ erase_imp(It it) _GLIBCXX_DEBUG_ONLY(size_type cnt = 0;) - while (source_it != source_end_it) - { - if (source_it != it) - { - _GLIBCXX_DEBUG_ONLY(++cnt;) - _GLIBCXX_DEBUG_ASSERT(cnt != m_size); - - new (const_cast<void* >( - static_cast<const void* >(target_it))) + while (source_it != source_end_it) + { + if (source_it != it) + { + _GLIBCXX_DEBUG_ONLY(++cnt;) + _GLIBCXX_DEBUG_ASSERT(cnt != m_size); + new (const_cast<void* >(static_cast<const void* >(target_it))) value_type(*source_it); - ++target_it; - } - else - ret_it = target_it; - - ++source_it; - } + ++target_it; + } + else + ret_it = target_it; + ++source_it; + } _GLIBCXX_DEBUG_ASSERT(m_size > 0); - reallocate_metadata((node_update* )this, m_size - 1); - cd.set_no_action(); - - _GLIBCXX_DEBUG_ONLY( - PB_DS_CLASS_C_DEC::erase_existing(PB_DS_V2F(*it));) - { - cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); - } + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::erase_existing(PB_DS_V2F(*it));) + { + cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); + } m_a_values = a_values; - --m_size; - m_end_it = m_a_values + m_size; - update(node_begin(), (node_update* )this); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (It(ret_it)); + return It(ret_it); } PB_DS_CLASS_T_DEC @@ -231,12 +191,9 @@ PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { point_iterator it = find(r_key); - if (it == end()) - return (false); - + return false; erase(it); - - return (true); + return true; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp index bb7c4dc..05161cb 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp @@ -50,22 +50,17 @@ PB_DS_CLASS_C_DEC:: size() const { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (m_size); + return m_size; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const -{ - return (s_value_alloc.max_size()); -} +{ return s_value_alloc.max_size(); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const -{ - return (size() == 0); -} +{ return size() == 0; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp index 4f0481d..16d6f04 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp @@ -56,16 +56,14 @@ void PB_DS_CLASS_C_DEC:: reallocate_metadata(Node_Update_* , size_type new_size) { - metadata_pointer a_new_metadata_vec =(new_size == 0)? NULL : s_metadata_alloc.allocate(new_size); + metadata_pointer a_new_metadata_vec =(new_size == 0) ? NULL : s_metadata_alloc.allocate(new_size); if (m_a_metadata != NULL) { for (size_type i = 0; i < m_size; ++i) m_a_metadata[i].~metadata_type(); - s_metadata_alloc.deallocate(m_a_metadata, m_size); } - std::swap(m_a_metadata, a_new_metadata_vec); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp index f982c91..38d4cee 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp @@ -48,45 +48,36 @@ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_begin() const -{ - return (PB_DS_node_begin_imp()); -} +{ return PB_DS_node_begin_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_end() const -{ - return (PB_DS_node_end_imp()); -} +{ return PB_DS_node_end_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_begin() -{ - return (PB_DS_node_begin_imp()); -} +{ return PB_DS_node_begin_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_end() -{ - return (PB_DS_node_end_imp()); -} +{ return PB_DS_node_end_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_begin_imp() const { - return (const_node_iterator( - const_cast<pointer>(mid_pointer(begin(), end())), + return const_node_iterator(const_cast<pointer>(mid_pointer(begin(), end())), const_cast<pointer>(begin()), const_cast<pointer>(end()),(m_a_metadata == NULL)? NULL : - mid_pointer(m_a_metadata, m_a_metadata + m_size))); + mid_pointer(m_a_metadata, m_a_metadata + m_size)); } PB_DS_CLASS_T_DEC @@ -94,12 +85,8 @@ inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_end_imp() const { - return (const_node_iterator( - end(), - end(), - end(),(m_a_metadata == NULL)? - NULL : - m_a_metadata + m_size)); + return const_node_iterator(end(), end(), end(), + (m_a_metadata == NULL) ? NULL : m_a_metadata + m_size); } PB_DS_CLASS_T_DEC @@ -107,12 +94,8 @@ inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_begin_imp() { - return (node_iterator( - mid_pointer(begin(), end()), - begin(), - end(),(m_a_metadata == NULL)? - NULL : - mid_pointer(m_a_metadata, m_a_metadata + m_size))); + return node_iterator(mid_pointer(begin(), end()), begin(), end(), + (m_a_metadata == NULL) ? NULL : mid_pointer(m_a_metadata, m_a_metadata + m_size)); } PB_DS_CLASS_T_DEC @@ -120,11 +103,7 @@ inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_end_imp() { - return (node_iterator( - end(), - end(), - end(),(m_a_metadata == NULL)? - NULL : - m_a_metadata + m_size)); + return node_iterator(end(), end(), + end(),(m_a_metadata == NULL) ? NULL : m_a_metadata + m_size); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp index 719a824..d64ad20 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp @@ -55,7 +55,6 @@ namespace pb_ds { namespace detail { - #define PB_DS_STATIC_ASSERT(UNIQUE, E) \ typedef \ static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \ diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp index b385431..f9e2714 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp @@ -64,7 +64,6 @@ namespace pb_ds { namespace detail { - #define PB_DS_CLASS_T_DEC \ template<typename Key, typename Mapped, class Cmp_Fn, \ class Node_And_It_Traits, class Allocator> @@ -128,21 +127,14 @@ namespace pb_ds public Node_And_It_Traits::node_update, public PB_DS_TYPES_TRAITS_C_DEC { - private: - typedef - typename remove_const< - typename PB_DS_TYPES_TRAITS_C_DEC::value_type>::type - non_const_value_type; + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; - typedef - typename Allocator::template rebind< - non_const_value_type>::other - value_allocator; + typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type; + typedef typename Allocator::template rebind<non_const_value_type>::other value_allocator; typedef typename value_allocator::pointer value_vector; - typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; typedef Cmp_Fn cmp_fn_base; @@ -150,25 +142,14 @@ namespace pb_ds typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; #endif - typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer mapped_pointer_; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer - const_mapped_pointer_; + typedef typename traits_base::pointer mapped_pointer_; + typedef typename traits_base::const_pointer const_mapped_pointer_; typedef typename Node_And_It_Traits::metadata_type metadata_type; - typedef - typename Allocator::template rebind< - metadata_type>::other - metadata_allocator; - + typedef typename Allocator::template rebind<metadata_type>::other metadata_allocator; typedef typename metadata_allocator::pointer metadata_pointer; - - typedef - typename metadata_allocator::const_reference - const_metadata_reference; - + typedef typename metadata_allocator::const_reference const_metadata_reference; typedef typename metadata_allocator::reference metadata_reference; typedef @@ -177,59 +158,29 @@ namespace pb_ds public: + typedef Allocator allocator; typedef typename Allocator::size_type size_type; - typedef typename Allocator::difference_type difference_type; typedef Cmp_Fn cmp_fn; typedef typename Node_And_It_Traits::node_update node_update; - typedef Allocator allocator; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer - const_key_pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference - const_key_reference; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer - mapped_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer - const_mapped_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference - mapped_reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference - const_mapped_reference; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_reference - const_reference; + typedef typename traits_base::key_type key_type; + typedef typename traits_base::key_pointer key_pointer; + typedef typename traits_base::const_key_pointer const_key_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::const_key_reference const_key_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::const_mapped_pointer const_mapped_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::const_mapped_reference const_mapped_reference; + typedef typename traits_base::value_type value_type; + typedef typename traits_base::pointer pointer; + typedef typename traits_base::const_pointer const_pointer; + typedef typename traits_base::reference reference; + typedef typename traits_base::const_reference const_reference; typedef const_pointer const_point_iterator; @@ -255,20 +206,20 @@ namespace pb_ds PB_DS_OV_TREE_CLASS_NAME(); - PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn); + PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&); - PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update); + PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&, const node_update&); - PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); + PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC&); ~PB_DS_OV_TREE_CLASS_NAME(); void - swap(PB_DS_CLASS_C_DEC& other); + swap(PB_DS_CLASS_C_DEC&); template<typename It> void - copy_from_range(It first_it, It last_it); + copy_from_range(It, It); inline size_type max_size() const; @@ -342,9 +293,7 @@ namespace pb_ds inline const_point_iterator lower_bound(const_key_reference r_key) const - { - return (const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key)); - } + { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); } inline point_iterator upper_bound(const_key_reference r_key) @@ -384,11 +333,11 @@ namespace pb_ds { return (const_cast<PB_DS_CLASS_C_DEC& >(*this).find(r_key)); } bool - erase(const_key_reference r_key); + erase(const_key_reference); template<typename Pred> inline size_type - erase_if(Pred pred); + erase_if(Pred); inline iterator erase(iterator it) @@ -398,10 +347,10 @@ namespace pb_ds clear(); void - join(PB_DS_CLASS_C_DEC& other); + join(PB_DS_CLASS_C_DEC&); void - split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); + split(const_key_reference, PB_DS_CLASS_C_DEC&); inline iterator begin() @@ -438,25 +387,25 @@ namespace pb_ds template<typename Node_Update> void - update(node_iterator it, Node_Update* p_update); + update(node_iterator, Node_Update*); void reallocate_metadata(null_node_update_pointer, size_type); template<typename Node_Update_> void - reallocate_metadata(Node_Update_* p_update, size_type new_size); + reallocate_metadata(Node_Update_*, size_type); template<typename It> void - copy_from_ordered_range(It first_it, It last_it); + copy_from_ordered_range(It, It); void - value_swap(PB_DS_CLASS_C_DEC& other); + value_swap(PB_DS_CLASS_C_DEC&); template<typename It> void - copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it); + copy_from_ordered_range(It, It, It, It); template<typename Ptr> inline static Ptr @@ -543,16 +492,12 @@ namespace pb_ds PB_DS_node_end_imp(); private: - value_vector m_a_values; - static value_allocator s_value_alloc; - - metadata_pointer m_a_metadata; - static metadata_allocator s_metadata_alloc; + value_vector m_a_values; + metadata_pointer m_a_metadata; iterator m_end_it; - size_type m_size; }; @@ -577,7 +522,6 @@ namespace pb_ds #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S - #undef PB_DS_CONST_NODE_ITERATOR_NAME } // namespace detail diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp index adb08a8..8ed19f1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/policy_access_fn_imps.hpp @@ -48,14 +48,10 @@ PB_DS_CLASS_T_DEC Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() const -{ - return (*this); -} +{ return *this; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp index e20086b..7f6e5d4 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp @@ -50,77 +50,55 @@ PB_DS_CLASS_C_DEC:: split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - if (m_size == 0) - { - other.clear(); - - _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - return; - } + if (m_size == 0) + { + other.clear(); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; + } if (Cmp_Fn::operator()(r_key, PB_DS_V2F(*begin()))) { value_swap(other); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - return; + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; } - if (!Cmp_Fn::operator()( - r_key, - PB_DS_V2F(*(end() - 1)))) + if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(*(end() - 1)))) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - return; + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; } if (m_size == 1) { value_swap(other); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - return; + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; } _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);) - - iterator it = upper_bound(r_key); - + iterator it = upper_bound(r_key); PB_DS_CLASS_C_DEC new_other(other, other); - new_other.copy_from_ordered_range(it, end()); - PB_DS_CLASS_C_DEC new_this(*this, * this); - new_this.copy_from_ordered_range(begin(), it); // No exceptions from this point. - - _GLIBCXX_DEBUG_ONLY(map_debug_base::split( - r_key,(Cmp_Fn& )(*this), - other);) - - other.update(other.node_begin(), (node_update* )(&other)); - + _GLIBCXX_DEBUG_ONLY(map_debug_base::split(r_key,(Cmp_Fn& )(*this), other);) + other.update(other.node_begin(), (node_update* )(&other)); update(node_begin(), (node_update* )this); - other.value_swap(new_other); - value_swap(new_this); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} PB_DS_CLASS_T_DEC void @@ -128,52 +106,38 @@ PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - if (other.m_size == 0) - return; + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + if (other.m_size == 0) + return; if (m_size == 0) { value_swap(other); - return; } - const bool greater = Cmp_Fn::operator()( - PB_DS_V2F(*(end() - 1)), + const bool greater = Cmp_Fn::operator()(PB_DS_V2F(*(end() - 1)), PB_DS_V2F(*other.begin())); - const bool lesser = Cmp_Fn::operator()( - PB_DS_V2F(*(other.end() - 1)), + const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(*(other.end() - 1)), PB_DS_V2F(*begin())); if (!greater&& !lesser) throw join_error(); - PB_DS_CLASS_C_DEC new_this(*this, * this); + PB_DS_CLASS_C_DEC new_this(*this, *this); if (greater) - new_this.copy_from_ordered_range( - begin(), - end(), - other.begin(), - other.end()); + new_this.copy_from_ordered_range(begin(), end(), + other.begin(), other.end()); else - new_this.copy_from_ordered_range( - other.begin(), - other.end(), - begin(), - end()); + new_this.copy_from_ordered_range(other.begin(), other.end(), + begin(), end()); // No exceptions from this point. - _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);) - - value_swap(new_this); - + value_swap(new_this); other.clear(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp index 79dc307..82c3fbd 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp @@ -48,64 +48,52 @@ struct iterator : public const_iterator { public: typedef std::forward_iterator_tag iterator_category; - typedef typename Allocator::difference_type difference_type; - typedef node_pointer value_type; - typedef node_pointer_pointer pointer; - typedef node_pointer_reference reference; -public: inline - iterator(node_pointer_pointer p_p_cur = NULL, node_pointer_pointer p_p_end = NULL) : const_iterator(p_p_cur, p_p_end) + iterator(node_pointer_pointer p_p_cur = NULL, + node_pointer_pointer p_p_end = NULL) + : const_iterator(p_p_cur, p_p_end) { } inline bool operator==(const iterator& other) const - { - return (const_iterator::m_p_p_cur == other.m_p_p_cur); - } + { return const_iterator::m_p_p_cur == other.m_p_p_cur; } inline bool operator!=(const iterator& other) const - { - return (const_iterator::m_p_p_cur != other.m_p_p_cur); - } + { return const_iterator::m_p_p_cur != other.m_p_p_cur; } inline iterator& operator++() { const_iterator::operator++(); - - return (*this); + return *this; } inline iterator operator++(int) { iterator ret_it(*this); - operator++(); - - return (ret_it); + return ret_it; } node_pointer_pointer operator->() { _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) - - return (const_iterator::m_p_p_cur); + return const_iterator::m_p_p_cur; } node_pointer operator*() { _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) - - return (*const_iterator::m_p_p_cur); + return *const_iterator::m_p_p_cur; } }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp index 17de4e0..64c16b1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp @@ -79,9 +79,7 @@ public: protected: leaf_pointer m_p_nd; - bool m_no_action_dtor; - bool m_call_destructor; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp index 29c76ea..0fba3a4 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp @@ -50,34 +50,23 @@ PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { node_pointer p_nd = find_imp(r_key); - if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist( - r_key)); - - return (false); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); + return false; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); - - if (!synth_e_access_traits::equal_keys( - PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), - r_key)) + if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist( - r_key)); - - return (false); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); + return false; } _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); - erase_leaf(static_cast<leaf_pointer>(p_nd)); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (true); + return true; } PB_DS_CLASS_T_DEC @@ -86,19 +75,15 @@ PB_DS_CLASS_C_DEC:: erase_fixup(internal_node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); - if (std::distance(p_nd->begin(), p_nd->end()) == 1) { node_pointer p_parent = p_nd->m_p_parent; - if (p_parent == m_p_head) m_p_head->m_p_parent =* p_nd->begin(); else { _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); - node_pointer p_new_child =* p_nd->begin(); - static_cast<internal_node_pointer>(p_parent)->replace_child( p_new_child, pref_begin(p_new_child), @@ -106,31 +91,24 @@ erase_fixup(internal_node_pointer p_nd) this); } (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; - p_nd->~internal_node(); - s_internal_node_allocator.deallocate(p_nd, 1); if (p_parent == m_p_head) return; _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); - p_nd = static_cast<internal_node_pointer>(p_parent); } while (true) { _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); - p_nd->update_prefixes(this); - apply_update(p_nd, (node_update* )this); - _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);) - - if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) - return; + if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) + return; _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == pat_trie_internal_node_type); @@ -146,11 +124,8 @@ actual_erase_leaf(leaf_pointer p_l) { _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; - _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value()))); - p_l->~leaf(); - s_leaf_allocator.deallocate(p_l, 1); } @@ -160,20 +135,15 @@ PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - if (empty()) - return; + if (empty()) + return; clear_imp(m_p_head->m_p_parent); - m_size = 0; - initialize(); - _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();) - - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} PB_DS_CLASS_T_DEC void @@ -183,29 +153,21 @@ clear_imp(node_pointer p_nd) if (p_nd->m_type == pat_trie_internal_node_type) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); - for (typename internal_node::iterator it = static_cast<internal_node_pointer>(p_nd)->begin(); it != static_cast<internal_node_pointer>(p_nd)->end(); ++it) { node_pointer p_child =* it; - clear_imp(p_child); } - - s_internal_node_allocator.deallocate( - static_cast<internal_node_pointer>(p_nd), 1); - + s_internal_node_allocator.deallocate(static_cast<internal_node_pointer>(p_nd), 1); return; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); - static_cast<leaf_pointer>(p_nd)->~leaf(); - - s_leaf_allocator.deallocate( - static_cast<leaf_pointer>(p_nd), 1); + s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1); } PB_DS_CLASS_T_DEC @@ -216,19 +178,14 @@ erase(const_iterator it) _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it == end()) - return (it); + return it; const_iterator ret_it = it; - ++ret_it; - _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); - erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } #ifdef PB_DS_DATA_TRUE_INDICATOR @@ -240,19 +197,13 @@ erase(iterator it) _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it == end()) - return (it); - + return it; iterator ret_it = it; - ++ret_it; - _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); - erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR @@ -264,19 +215,14 @@ erase(const_reverse_iterator it) _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it.m_p_nd == m_p_head) - return (it); - + return it; const_reverse_iterator ret_it = it; - ++ret_it; _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); - erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } #ifdef PB_DS_DATA_TRUE_INDICATOR @@ -288,19 +234,14 @@ erase(reverse_iterator it) _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it.m_p_nd == m_p_head) - return (it); - + return it; reverse_iterator ret_it = it; - ++ret_it; _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); - erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR @@ -311,19 +252,15 @@ PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { size_type num_ersd = 0; - _GLIBCXX_DEBUG_ONLY(assert_valid();) - iterator it = begin(); - + iterator it = begin(); while (it != end()) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - if (pred(*it)) { ++num_ersd; - it = erase(it); } else @@ -331,8 +268,7 @@ erase_if(Pred pred) } _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (num_ersd); + return num_ersd; } PB_DS_CLASS_T_DEC @@ -341,18 +277,14 @@ PB_DS_CLASS_C_DEC:: erase_leaf(leaf_pointer p_l) { update_min_max_for_erased_leaf(p_l); - if (p_l->m_p_parent->m_type == pat_trie_head_node_type) { _GLIBCXX_DEBUG_ASSERT(size() == 1); - clear(); - return; } _GLIBCXX_DEBUG_ASSERT(size() > 1); - _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == pat_trie_internal_node_type); @@ -360,9 +292,7 @@ erase_leaf(leaf_pointer p_l) static_cast<internal_node_pointer>(p_l->m_p_parent); p_parent->remove_child(p_l); - erase_fixup(p_parent); - actual_erase_leaf(p_l); } @@ -375,27 +305,21 @@ update_min_max_for_erased_leaf(leaf_pointer p_l) { m_p_head->m_p_min = m_p_head; m_p_head->m_p_max = m_p_head; - return; } if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min)) { iterator it(p_l); - ++it; - m_p_head->m_p_min = it.m_p_nd; - return; } if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max)) { iterator it(p_l); - --it; - m_p_head->m_p_max = it.m_p_nd; } } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp index f76bc30..d9b3c4a 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp @@ -50,28 +50,22 @@ PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - node_pointer p_nd = find_imp(r_key); + node_pointer p_nd = find_imp(r_key); if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return (end()); + return end(); } - if (synth_e_access_traits::equal_keys( - PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), - r_key)) + if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) { _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); - - return (iterator(p_nd)); + return iterator(p_nd); } _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return (end()); + return end(); } PB_DS_CLASS_T_DEC @@ -81,29 +75,22 @@ find(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) - const_node_pointer p_nd = - const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); + const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return (end()); + return end(); } - if (synth_e_access_traits::equal_keys( - PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), - r_key)) + if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) { - _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists( - r_key)); - - return (const_iterator(const_cast<node_pointer>(p_nd))); + _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); + return const_iterator(const_cast<node_pointer>(p_nd)); } _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) - - return (end()); + return end(); } PB_DS_CLASS_T_DEC @@ -125,17 +112,13 @@ find_imp(const_key_reference r_key) while (p_nd->m_type != pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); - - node_pointer p_next_nd = - static_cast<internal_node_pointer>(p_nd)->get_child_node( b_it, e_it, this); + node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it, e_it, this); if (p_next_nd == NULL) - return (p_nd); - + return p_nd; p_nd = p_next_nd; } - - return (p_nd); + return p_nd; } PB_DS_CLASS_T_DEC @@ -156,31 +139,23 @@ lower_bound_imp(const_key_reference r_key) synth_e_access_traits::end(r_key); size_type checked_ind = 0; - while (true) { if (p_nd->m_type == pat_trie_leaf_node_type) { - if (!synth_e_access_traits::cmp_keys( - PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), - r_key)) - return (p_nd); - + if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) + return p_nd; iterator it(p_nd); - ++it; - - return (it.m_p_nd); + return it.m_p_nd; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); - const size_type new_checked_ind = static_cast<internal_node_pointer>(p_nd)->get_e_ind(); p_nd = static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); - checked_ind = new_checked_ind; } } @@ -189,17 +164,14 @@ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: lower_bound(const_key_reference r_key) -{ - return (point_iterator(lower_bound_imp(r_key))); -} +{ return point_iterator(lower_bound_imp(r_key)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: lower_bound(const_key_reference r_key) const { - return (const_point_iterator( - const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key))); + return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); } PB_DS_CLASS_T_DEC @@ -210,17 +182,14 @@ upper_bound(const_key_reference r_key) point_iterator l_bound_it = lower_bound(r_key); _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || - !synth_e_access_traits::cmp_keys( - PB_DS_V2F(*l_bound_it), + !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), r_key)); if (l_bound_it == end() || - synth_e_access_traits::cmp_keys( - r_key, - PB_DS_V2F(*l_bound_it))) - return (l_bound_it); + synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) + return l_bound_it; - return (++l_bound_it); + return ++l_bound_it; } PB_DS_CLASS_T_DEC @@ -231,17 +200,13 @@ upper_bound(const_key_reference r_key) const const_point_iterator l_bound_it = lower_bound(r_key); _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || - !synth_e_access_traits::cmp_keys( - PB_DS_V2F(*l_bound_it), + !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), r_key)); if (l_bound_it == end() || - synth_e_access_traits::cmp_keys( - r_key, - PB_DS_V2F(*l_bound_it))) - return (l_bound_it); - - return (++l_bound_it); + synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) + return l_bound_it; + return ++l_bound_it; } PB_DS_CLASS_T_DEC @@ -250,12 +215,10 @@ PB_DS_CLASS_C_DEC:: pref_begin(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (synth_e_access_traits::begin( - PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); + return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); - - return (static_cast<const_internal_node_pointer>(p_nd)->pref_b_it()); + return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it(); } PB_DS_CLASS_T_DEC @@ -264,12 +227,10 @@ PB_DS_CLASS_C_DEC:: pref_end(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (synth_e_access_traits::end( - PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); + return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); - - return (static_cast<const_internal_node_pointer>(p_nd)->pref_e_it()); + return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it(); } PB_DS_CLASS_T_DEC @@ -278,9 +239,8 @@ PB_DS_CLASS_C_DEC:: leftmost_descendant(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (static_cast<const_leaf_pointer>(p_nd)); - - return (static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant()); + return static_cast<const_leaf_pointer>(p_nd); + return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant(); } PB_DS_CLASS_T_DEC @@ -289,9 +249,8 @@ PB_DS_CLASS_C_DEC:: leftmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (static_cast<leaf_pointer>(p_nd)); - - return (static_cast<internal_node_pointer>(p_nd)->leftmost_descendant()); + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); } PB_DS_CLASS_T_DEC @@ -300,9 +259,8 @@ PB_DS_CLASS_C_DEC:: rightmost_descendant(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (static_cast<const_leaf_pointer>(p_nd)); - - return (static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant()); + return static_cast<const_leaf_pointer>(p_nd); + return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant(); } PB_DS_CLASS_T_DEC @@ -311,8 +269,7 @@ PB_DS_CLASS_C_DEC:: rightmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (static_cast<leaf_pointer>(p_nd)); - - return (static_cast<internal_node_pointer>(p_nd)->rightmost_descendant()); + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp index 14f8057..e8bee52 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp @@ -54,32 +54,20 @@ namespace pb_ds { namespace detail { +#define PB_DS_CLASS_T_DEC \ + template<typename Type_Traits, typename E_Access_Traits, \ + typename Metadata, typename Allocator> -#define PB_DS_CLASS_T_DEC \ - template< \ - class Type_Traits, \ - class E_Access_Traits, \ - class Metadata, \ - class Allocator> - -#define PB_DS_CLASS_C_DEC \ - pat_trie_head< \ - Type_Traits, \ - E_Access_Traits, \ - Metadata, \ - Allocator> - -#define PB_DS_BASE_C_DEC \ - pat_trie_node_base< \ - Type_Traits, \ - E_Access_Traits, \ - Metadata, \ - Allocator> +#define PB_DS_CLASS_C_DEC \ + pat_trie_head<Type_Traits, E_Access_Traits, Metadata, Allocator> + +#define PB_DS_BASE_C_DEC \ + pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> template<typename Type_Traits, - class E_Access_Traits, - class Metadata, - class Allocator> + typename E_Access_Traits, + typename Metadata, + typename Allocator> struct pat_trie_head : public PB_DS_BASE_C_DEC { private: diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp index dcaf1bf..7e20cd1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp @@ -48,23 +48,17 @@ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const -{ - return (m_size == 0); -} +{ return (m_size == 0); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const -{ - return (m_size); -} +{ return m_size; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const -{ - return (s_internal_node_allocator.max_size()); -} +{ return s_internal_node_allocator.max_size(); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp index 0f36585..ff117c5 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp @@ -48,33 +48,25 @@ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: begin() -{ - return (iterator(m_p_head->m_p_min)); -} +{ return iterator(m_p_head->m_p_min); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin() const -{ - return (const_iterator(m_p_head->m_p_min)); -} +{ return const_iterator(m_p_head->m_p_min); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() -{ - return (iterator(m_p_head)); -} +{ return iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const -{ - return (const_iterator(m_p_head)); -} +{ return const_iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator @@ -82,9 +74,8 @@ PB_DS_CLASS_C_DEC:: rbegin() const { if (empty()) - return (rend()); - - return (--end()); + return rend(); + return --end(); } PB_DS_CLASS_T_DEC @@ -93,56 +84,43 @@ PB_DS_CLASS_C_DEC:: rbegin() { if (empty()) - return (rend()); - - return (--end()); + return rend(); + return --end(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: rend() -{ - return (reverse_iterator(m_p_head)); -} +{ return reverse_iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator PB_DS_CLASS_C_DEC:: rend() const -{ - return (const_reverse_iterator(m_p_head)); -} +{ return const_reverse_iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_begin() const -{ - return (const_node_iterator(m_p_head->m_p_parent, this)); -} +{ return const_node_iterator(m_p_head->m_p_parent, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_begin() -{ - return (node_iterator(m_p_head->m_p_parent, this)); -} +{ return node_iterator(m_p_head->m_p_parent, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_end() const -{ - return (const_node_iterator(NULL, this)); -} +{ return const_node_iterator(NULL, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_end() -{ - return (node_iterator(NULL, this)); -} +{ return node_iterator(NULL, this); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp index db990b1..08f3761 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp @@ -127,7 +127,6 @@ namespace pb_ds private: pat_trie_leaf(const PB_DS_CLASS_C_DEC& other); - private: value_type m_value; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp index de995fb..753e66b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp @@ -53,26 +53,15 @@ namespace pb_ds { namespace detail { +#define PB_DS_CLASS_T_DEC \ + template<typename Type_Traits, typename E_Access_Traits, \ + typename Metadata, typename Allocator> -#define PB_DS_CLASS_T_DEC \ - template< \ - class Type_Traits, \ - class E_Access_Traits, \ - class Metadata, \ - class Allocator> - -#define PB_DS_CLASS_C_DEC \ - pat_trie_node_base< \ - Type_Traits, \ - E_Access_Traits, \ - Metadata, \ - Allocator> - -#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC \ - pat_trie_subtree_debug_info< \ - Type_Traits, \ - E_Access_Traits, \ - Allocator> +#define PB_DS_CLASS_C_DEC \ + pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> + +#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC \ + pat_trie_subtree_debug_info<Type_Traits, E_Access_Traits, Allocator> enum pat_trie_node_type { @@ -82,9 +71,9 @@ namespace pb_ds }; template<typename Type_Traits, - class E_Access_Traits, - class Metadata, - class Allocator> + typename E_Access_Traits, + typename Metadata, + typename Allocator> struct pat_trie_node_base : public pat_trie_node_metadata_base< Metadata, Allocator> @@ -108,7 +97,6 @@ namespace pb_ds subtree_debug_info; #endif - public: pat_trie_node_base(pat_trie_node_type type); #ifdef _GLIBCXX_DEBUG @@ -119,9 +107,7 @@ namespace pb_ds assert_valid_imp(const_e_access_traits_pointer p_traits) const = 0; #endif - public: node_pointer m_p_parent; - const pat_trie_node_type m_type; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp index ec6eaaf..9c8a40c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp @@ -87,7 +87,6 @@ namespace pb_ds class Allocator> class pat_trie_const_node_it_ { - protected: typedef typename Allocator::template rebind< @@ -181,14 +180,11 @@ namespace pb_ds metadata_type>::other::const_reference const_metadata_reference; - public: - // Default constructor. /* inline pat_trie_const_node_it_() */ - inline pat_trie_const_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) @@ -219,7 +215,7 @@ namespace pb_ds num_children() const { if (m_p_nd->m_type == pat_trie_leaf_node_type) - return (0); + return 0; _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(), static_cast<internal_node_pointer>(m_p_nd)->end()); } @@ -270,7 +266,6 @@ namespace pb_ds public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC { - private: typedef typename Allocator::template rebind< @@ -303,8 +298,6 @@ namespace pb_ds // __Iterator's __const reference type. typedef value_type const_reference; - public: - // Default constructor. /* inline @@ -328,8 +321,7 @@ namespace pb_ds PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC get_child(size_type i) const { - _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == - pat_trie_internal_node_type); + _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type); typename Internal_Node::iterator it = static_cast<internal_node_pointer>(base_type::m_p_nd)->begin(); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp index 8fbc224..cb0a032 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp @@ -75,37 +75,26 @@ namespace pb_ds { namespace detail { - -#define PB_DS_CLASS_T_DEC \ - template<typename Key, typename Mapped, class Node_And_It_Traits, \ - class Allocator> +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Node_And_It_Traits, \ + typename Allocator> #ifdef PB_DS_DATA_TRUE_INDICATOR -#define PB_DS_CLASS_NAME \ - pat_trie_data_ +#define PB_DS_CLASS_NAME pat_trie_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR -#define PB_DS_CLASS_NAME \ - pat_trie_no_data_ +#define PB_DS_CLASS_NAME pat_trie_no_data_ #endif -#define PB_DS_CLASS_C_DEC \ - PB_DS_CLASS_NAME< \ - Key, \ - Mapped, \ - Node_And_It_Traits, \ - Allocator> +#define PB_DS_CLASS_C_DEC \ + PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator> -#define PB_DS_TYPES_TRAITS_C_DEC \ - types_traits< \ - Key, \ - Mapped, \ - Allocator, \ - false> +#define PB_DS_TYPES_TRAITS_C_DEC \ + types_traits<Key, Mapped, Allocator, false> #ifdef _GLIBCXX_DEBUG -#define PB_DS_MAP_DEBUG_BASE_C_DEC \ +#define PB_DS_MAP_DEBUG_BASE_C_DEC \ map_debug_base<Key, eq_by_less<Key, \ std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference> #endif @@ -122,10 +111,8 @@ namespace pb_ds #define PB_DS_EP2VP(X)& ((X)->m_value.first) #endif -#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ - typedef \ - static_assert_dumclass< \ - sizeof(static_assert<(bool)(E)>)> \ +#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ + typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \ UNIQUE##static_assert_type /** @@ -133,8 +120,8 @@ namespace pb_ds **/ template<typename Key, typename Mapped, - class Node_And_It_Traits, - class Allocator> + typename Node_And_It_Traits, + typename Allocator> class PB_DS_CLASS_NAME : #ifdef _GLIBCXX_DEBUG public PB_DS_MAP_DEBUG_BASE_C_DEC, @@ -143,70 +130,31 @@ namespace pb_ds public Node_And_It_Traits::node_update, public PB_DS_TYPES_TRAITS_C_DEC { - private: + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; - typedef - typename Node_And_It_Traits::synth_e_access_traits - synth_e_access_traits; - - typedef - typename Allocator::template rebind< - synth_e_access_traits>::other::const_pointer - const_e_access_traits_pointer; - - typedef - typename synth_e_access_traits::const_iterator - const_e_iterator; + typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits; + typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer; + typedef typename synth_e_access_traits::const_iterator const_e_iterator; typedef typename Node_And_It_Traits::node node; + typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer; - typedef - typename Allocator::template rebind< - node>::other::const_pointer - const_node_pointer; - - typedef - typename Allocator::template rebind< - node>::other::pointer - node_pointer; + typedef typename Allocator::template rebind<node>::other::pointer node_pointer; typedef typename Node_And_It_Traits::head head; - - typedef - typename Allocator::template rebind< - head>::other - head_allocator; - + typedef typename Allocator::template rebind<head>::other head_allocator; typedef typename head_allocator::pointer head_pointer; typedef typename Node_And_It_Traits::leaf leaf; - - typedef - typename Allocator::template rebind< - leaf>::other - leaf_allocator; - + typedef typename Allocator::template rebind<leaf>::other leaf_allocator; typedef typename leaf_allocator::const_pointer const_leaf_pointer; - typedef typename leaf_allocator::pointer leaf_pointer; typedef typename Node_And_It_Traits::internal_node internal_node; - - typedef - typename Allocator::template rebind< - internal_node>::other - internal_node_allocator; - - typedef - typename internal_node_allocator::const_pointer - const_internal_node_pointer; - - typedef - typename internal_node_allocator::pointer - internal_node_pointer; - - typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; + typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator; + typedef typename internal_node_allocator::const_pointer const_internal_node_pointer; + typedef typename internal_node_allocator::pointer internal_node_pointer; #include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp> @@ -216,99 +164,50 @@ namespace pb_ds #include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp> - typedef - typename Node_And_It_Traits::null_node_update_pointer - null_node_update_pointer; + typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; public: typedef pat_trie_tag container_category; - + typedef Allocator allocator; typedef typename Allocator::size_type size_type; - typedef typename Allocator::difference_type difference_type; - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer - const_key_pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference - const_key_reference; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer - mapped_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer - const_mapped_pointer; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference - mapped_reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference - const_mapped_reference; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; - - typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; - - typedef - typename PB_DS_TYPES_TRAITS_C_DEC::const_reference - const_reference; - - typedef - typename Node_And_It_Traits::const_iterator - const_point_iterator; - + typedef typename traits_base::key_type key_type; + typedef typename traits_base::key_pointer key_pointer; + typedef typename traits_base::const_key_pointer const_key_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::const_key_reference const_key_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::const_mapped_pointer const_mapped_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::const_mapped_reference const_mapped_reference; + typedef typename traits_base::value_type value_type; + typedef typename traits_base::pointer pointer; + typedef typename traits_base::const_pointer const_pointer; + typedef typename traits_base::reference reference; + typedef typename traits_base::const_reference const_reference; + + typedef typename Node_And_It_Traits::const_iterator const_point_iterator; typedef typename Node_And_It_Traits::iterator point_iterator; - typedef const_point_iterator const_iterator; - typedef point_iterator iterator; - typedef - typename Node_And_It_Traits::const_reverse_iterator - const_reverse_iterator; - + typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator; typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; - - typedef - typename Node_And_It_Traits::const_node_iterator - const_node_iterator; - + typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator; typedef typename Node_And_It_Traits::node_iterator node_iterator; - typedef typename Node_And_It_Traits::e_access_traits e_access_traits; - typedef typename Node_And_It_Traits::node_update node_update; - typedef Allocator allocator; - - public: - PB_DS_CLASS_NAME(); - PB_DS_CLASS_NAME(const e_access_traits& r_e_access_traits); + PB_DS_CLASS_NAME(const e_access_traits&); - PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); void - swap(PB_DS_CLASS_C_DEC& other); + swap(PB_DS_CLASS_C_DEC&); ~PB_DS_CLASS_NAME(); @@ -333,74 +232,69 @@ namespace pb_ds const node_update& get_node_update() const; - inline std::pair< - point_iterator, - bool> - insert(const_reference r_val); + inline std::pair<point_iterator, bool> + insert(const_reference); inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR - return (insert(std::make_pair( - r_key, - mapped_type())).first->second); -#else // #ifdef PB_DS_DATA_TRUE_INDICATOR + return insert(std::make_pair(r_key, mapped_type())).first->second; +#else insert(r_key); - - return (traits_base::s_null_mapped); -#endif // #ifdef PB_DS_DATA_TRUE + return traits_base::s_null_mapped; +#endif } inline point_iterator - find(const_key_reference r_key); + find(const_key_reference); inline const_point_iterator - find(const_key_reference r_key) const; + find(const_key_reference) const; inline point_iterator - lower_bound(const_key_reference r_key); + lower_bound(const_key_reference); inline const_point_iterator - lower_bound(const_key_reference r_key) const; + lower_bound(const_key_reference) const; inline point_iterator - upper_bound(const_key_reference r_key); + upper_bound(const_key_reference); inline const_point_iterator - upper_bound(const_key_reference r_key) const; + upper_bound(const_key_reference) const; void clear(); inline bool - erase(const_key_reference r_key); + erase(const_key_reference); inline const_iterator - erase(const_iterator it); + erase(const_iterator); #ifdef PB_DS_DATA_TRUE_INDICATOR inline iterator - erase(iterator it); -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR + erase(iterator); +#endif inline const_reverse_iterator - erase(const_reverse_iterator it); + erase(const_reverse_iterator); #ifdef PB_DS_DATA_TRUE_INDICATOR inline reverse_iterator - erase(reverse_iterator it); -#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR + erase(reverse_iterator); +#endif template<typename Pred> inline size_type - erase_if(Pred pred); + erase_if(Pred); void - join(PB_DS_CLASS_C_DEC& other); + join(PB_DS_CLASS_C_DEC&); void - split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); + split(const_key_reference, PB_DS_CLASS_C_DEC&); inline iterator begin(); @@ -439,23 +333,21 @@ namespace pb_ds node_end(); #ifdef PB_DS_PAT_TRIE_TRACE_ - void trace() const; - -#endif // #ifdef PB_DS_PAT_TRIE_TRACE_ +#endif protected: template<typename It> void - copy_from_range(It first_it, It last_it); + copy_from_range(It, It); void - value_swap(PB_DS_CLASS_C_DEC& other); + value_swap(PB_DS_CLASS_C_DEC&); node_pointer - recursive_copy_node(const_node_pointer p_other_nd); + recursive_copy_node(const_node_pointer); private: @@ -463,95 +355,103 @@ namespace pb_ds initialize(); inline void - apply_update(node_pointer p_nd, null_node_update_pointer); + apply_update(node_pointer, null_node_update_pointer); template<typename Node_Update_> inline void - apply_update(node_pointer p_nd, Node_Update_* p_update); + apply_update(node_pointer, Node_Update_*); bool - join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag); + join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&); void - rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag); + rec_join_prep(const_node_pointer, const_node_pointer, + split_join_branch_bag&); void - rec_join_prep(const_leaf_pointer p_l, const_leaf_pointer p_r, split_join_branch_bag& r_bag); + rec_join_prep(const_leaf_pointer, const_leaf_pointer, + split_join_branch_bag&); void - rec_join_prep(const_leaf_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag); + rec_join_prep(const_leaf_pointer, const_internal_node_pointer, + split_join_branch_bag&); void - rec_join_prep(const_internal_node_pointer p_l, const_leaf_pointer p_r, split_join_branch_bag& r_bag); + rec_join_prep(const_internal_node_pointer, const_leaf_pointer, + split_join_branch_bag&); void - rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag); + rec_join_prep(const_internal_node_pointer, const_internal_node_pointer, + split_join_branch_bag&); node_pointer - rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag); + rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&); node_pointer - rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag); + rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&); node_pointer - rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag); + rec_join(leaf_pointer, internal_node_pointer, size_type, + split_join_branch_bag&); node_pointer - rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag); + rec_join(internal_node_pointer, leaf_pointer, size_type, + split_join_branch_bag&); node_pointer - rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag); + rec_join(internal_node_pointer, internal_node_pointer, + split_join_branch_bag&); size_type - keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r); + keys_diff_ind(typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator); internal_node_pointer - insert_branch(node_pointer p_left_nd, node_pointer p_right_nd, split_join_branch_bag& r_bag); + insert_branch(node_pointer, node_pointer, split_join_branch_bag&); void - update_min_max_for_inserted_leaf(leaf_pointer p_l); + update_min_max_for_inserted_leaf(leaf_pointer); void - erase_leaf(leaf_pointer p_l); + erase_leaf(leaf_pointer); inline void - actual_erase_leaf(leaf_pointer p_lf); + actual_erase_leaf(leaf_pointer); void - clear_imp(node_pointer p_nd); + clear_imp(node_pointer); void - erase_fixup(internal_node_pointer p_nd); + erase_fixup(internal_node_pointer); void - update_min_max_for_erased_leaf(leaf_pointer p_l); + update_min_max_for_erased_leaf(leaf_pointer); static inline const_e_iterator - pref_begin(const_node_pointer p_nd); + pref_begin(const_node_pointer); static inline const_e_iterator - pref_end(const_node_pointer p_nd); + pref_end(const_node_pointer); inline node_pointer - find_imp(const_key_reference r_key); + find_imp(const_key_reference); inline node_pointer - lower_bound_imp(const_key_reference r_key); + lower_bound_imp(const_key_reference); inline node_pointer - upper_bound_imp(const_key_reference r_key); + upper_bound_imp(const_key_reference); inline static const_leaf_pointer - leftmost_descendant(const_node_pointer p_nd); + leftmost_descendant(const_node_pointer); inline static leaf_pointer - leftmost_descendant(node_pointer p_nd); + leftmost_descendant(node_pointer); inline static const_leaf_pointer - rightmost_descendant(const_node_pointer p_nd); + rightmost_descendant(const_node_pointer); inline static leaf_pointer - rightmost_descendant(node_pointer p_nd); + rightmost_descendant(node_pointer); #ifdef _GLIBCXX_DEBUG void @@ -564,45 +464,39 @@ namespace pb_ds assert_reverse_iterators() const; static size_type - recursive_count_leafs(const_node_pointer p_nd); + recursive_count_leafs(const_node_pointer); #endif #ifdef PB_DS_PAT_TRIE_TRACE_ static void - trace_node(const_node_pointer p_nd, size_type level); + trace_node(const_node_pointer, size_type); template<typename Metadata_> static void - trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>); + trace_node_metadata(const_node_pointer, type_to_type<Metadata_>); static void - trace_node_metadata(const_node_pointer, - type_to_type<null_node_metadata>); + trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>); #endif leaf_pointer - split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other, - split_join_branch_bag& r_bag); + split_prep(const_key_reference, PB_DS_CLASS_C_DEC&, + split_join_branch_bag&); node_pointer - rec_split(node_pointer p_nd, const_e_iterator b_it, - const_e_iterator e_it, PB_DS_CLASS_C_DEC& other, - split_join_branch_bag& r_bag); + rec_split(node_pointer, const_e_iterator, const_e_iterator, + PB_DS_CLASS_C_DEC&, split_join_branch_bag&); void - split_insert_branch(size_type e_ind, const_e_iterator b_it, - typename internal_node::iterator child_b_it, - size_type num_children, split_join_branch_bag&); + split_insert_branch(size_type, const_e_iterator, + typename internal_node::iterator, + size_type, split_join_branch_bag&); - private: static head_allocator s_head_allocator; - static internal_node_allocator s_internal_node_allocator; - static leaf_allocator s_leaf_allocator; head_pointer m_p_head; - size_type m_size; }; @@ -623,11 +517,9 @@ namespace pb_ds #undef PB_DS_CLASS_NAME #undef PB_DS_TYPES_TRAITS_C_DEC #undef PB_DS_MAP_DEBUG_BASE_C_DEC - #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S - #undef PB_DS_STATIC_ASSERT } // namespace detail diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp index b26ad6e..1a42dc5 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp @@ -164,7 +164,7 @@ namespace pb_ds operator=(const PB_DS_CONST_IT_C_DEC& other) { m_p_nd = other.m_p_nd; - return (*this); + return *this; } inline @@ -172,52 +172,44 @@ namespace pb_ds operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) { m_p_nd = other.m_p_nd; - return (*this); + return *this; } inline const_pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); - return (&static_cast<leaf_pointer>(m_p_nd)->value()); + return &static_cast<leaf_pointer>(m_p_nd)->value(); } inline const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); - return (static_cast<leaf_pointer>(m_p_nd)->value()); + return static_cast<leaf_pointer>(m_p_nd)->value(); } inline bool operator==(const PB_DS_CONST_IT_C_DEC& other) const - { - return (m_p_nd == other.m_p_nd); - } + { return (m_p_nd == other.m_p_nd); } inline bool operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const - { - return (m_p_nd == other.m_p_nd); - } + { return (m_p_nd == other.m_p_nd); } inline bool operator!=(const PB_DS_CONST_IT_C_DEC& other) const - { - return (m_p_nd != other.m_p_nd); - } + { return (m_p_nd != other.m_p_nd); } inline bool operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const - { - return (m_p_nd != other.m_p_nd); - } + { return (m_p_nd != other.m_p_nd); } inline PB_DS_CONST_IT_C_DEC& operator++() { inc(integral_constant<int,Is_Forward_Iterator>()); - return (*this); + return *this; } inline PB_DS_CONST_IT_C_DEC @@ -225,14 +217,14 @@ namespace pb_ds { PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); operator++(); - return (ret_it); + return ret_it; } inline PB_DS_CONST_IT_C_DEC& operator--() { dec(integral_constant<int,Is_Forward_Iterator>()); - return (*this); + return *this; } inline PB_DS_CONST_IT_C_DEC @@ -240,7 +232,7 @@ namespace pb_ds { PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); operator--(); - return (ret_it); + return ret_it; } protected: @@ -345,17 +337,16 @@ namespace pb_ds leftmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (static_cast<leaf_pointer>(p_nd)); - - return (static_cast<internal_node_pointer>(p_nd)->leftmost_descendant()); + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); } inline static leaf_pointer rightmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) - return (static_cast<leaf_pointer>(p_nd)); - return (static_cast<internal_node_pointer>(p_nd)->rightmost_descendant()); + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); } public: @@ -374,7 +365,6 @@ namespace pb_ds public PB_DS_CONST_IT_C_DEC { - private: typedef typename Allocator::template rebind< @@ -412,8 +402,6 @@ namespace pb_ds typedef typename Type_Traits::reference reference; - public: - inline pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd) { } @@ -427,7 +415,7 @@ namespace pb_ds operator=(const PB_DS_IT_C_DEC& other) { base_it_type::m_p_nd = other.m_p_nd; - return (*this); + return *this; } inline @@ -435,23 +423,22 @@ namespace pb_ds operator=(const PB_DS_ODIR_IT_C_DEC& other) { base_it_type::m_p_nd = other.m_p_nd; - return (*this); + return *this; } inline pointer operator->() const { - _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == - pat_trie_leaf_node_type); + _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); - return (&static_cast<leaf_pointer>(base_it_type::m_p_nd)->value()); + return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value(); } inline reference operator*() const { _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); - return (static_cast<leaf_pointer>(base_it_type::m_p_nd)->value()); + return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value(); } inline PB_DS_IT_C_DEC& @@ -459,7 +446,7 @@ namespace pb_ds { PB_DS_CONST_IT_C_DEC:: operator++(); - return (*this); + return *this; } inline PB_DS_IT_C_DEC @@ -467,14 +454,14 @@ namespace pb_ds { PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); operator++(); - return (ret_it); + return ret_it; } inline PB_DS_IT_C_DEC& operator--() { PB_DS_CONST_IT_C_DEC::operator--(); - return (*this); + return *this; } inline PB_DS_IT_C_DEC @@ -482,7 +469,7 @@ namespace pb_ds { PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); operator--(); - return (ret_it); + return ret_it; } protected: diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp index a054e27..7c6eb0f 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp @@ -48,30 +48,22 @@ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::e_access_traits& PB_DS_CLASS_C_DEC:: get_e_access_traits() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const typename PB_DS_CLASS_C_DEC::e_access_traits& PB_DS_CLASS_C_DEC:: get_e_access_traits() const -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_update& PB_DS_CLASS_C_DEC:: get_node_update() -{ - return (*this); -} +{ return *this; } PB_DS_CLASS_T_DEC const typename PB_DS_CLASS_C_DEC::node_update& PB_DS_CLASS_C_DEC:: get_node_update() const -{ - return (*this); -} +{ return *this; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp index 436e03a..6b20fe6 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp @@ -60,7 +60,6 @@ public: add_branch() { internal_node_pointer p_nd = s_internal_node_allocator.allocate(1); - try { m_bag.push_back(p_nd); @@ -68,7 +67,6 @@ public: catch(...) { s_internal_node_allocator.deallocate(p_nd, 1); - throw; } } @@ -77,12 +75,9 @@ public: get_branch() { _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); - internal_node_pointer p_nd =* m_bag.begin(); - m_bag.pop_front(); - - return (p_nd); + return p_nd; } ~split_join_branch_bag() @@ -90,18 +85,14 @@ public: while (!m_bag.empty()) { internal_node_pointer p_nd =* m_bag.begin(); - s_internal_node_allocator.deallocate(p_nd, 1); - m_bag.pop_front(); } } inline bool empty() const - { - return (m_bag.empty()); - } + { return m_bag.empty(); } private: bag_t m_bag; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp index 7623a88..cab28ca77 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp @@ -52,12 +52,9 @@ PB_DS_CLASS_C_DEC:: trace() const { std::cerr << std::endl; - if (m_p_head->m_p_parent == NULL) return; - trace_node(m_p_head->m_p_parent, 0); - std::cerr << std::endl; } @@ -68,29 +65,20 @@ trace_node(const_node_pointer p_nd, size_type level) { for (size_type i = 0; i < level; ++i) std::cerr << ' '; - std::cerr << p_nd << " "; - - std::cerr << ((p_nd->m_type == pat_trie_leaf_node_type)? - "l " : - "i "); + std::cerr << ((p_nd->m_type == pat_trie_leaf_node_type) ? "l " : "i "); trace_node_metadata(p_nd, type_to_type<typename node::metadata_type>()); - - typename e_access_traits::const_iterator el_it = - pref_begin(p_nd); - + typename e_access_traits::const_iterator el_it = pref_begin(p_nd); while (el_it != pref_end(p_nd)) { std::cerr <<* el_it; - ++el_it; } if (p_nd->m_type == pat_trie_leaf_node_type) { std::cerr << std::endl; - return; } @@ -100,8 +88,7 @@ trace_node(const_node_pointer p_nd, size_type level) std::cerr << " " << static_cast<unsigned long>(p_internal->get_e_ind()) << std::endl; - const size_type num_children = std::distance( - p_internal->begin(), + const size_type num_children = std::distance(p_internal->begin(), p_internal->end()); for (size_type child_i = 0; child_i < num_children; ++child_i) @@ -109,7 +96,6 @@ trace_node(const_node_pointer p_nd, size_type level) typename internal_node::const_iterator child_it = p_internal->begin(); std::advance(child_it, num_children - child_i - 1); - trace_node(*child_it, level + 1); } } @@ -120,8 +106,7 @@ void PB_DS_CLASS_C_DEC:: trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>) { - std::cerr << "(" << - static_cast<unsigned long>(p_nd->get_metadata()) << ") "; + std::cerr << "(" << static_cast<unsigned long>(p_nd->get_metadata()) << ") "; } PB_DS_CLASS_T_DEC @@ -130,5 +115,5 @@ PB_DS_CLASS_C_DEC:: trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>) { } -#endif // #ifdef PB_DS_PAT_TRIE_TRACE_ +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp index d27acf9..445376e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp @@ -56,7 +56,6 @@ inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer p_nd, Node_Update_* /*p_update*/) { - Node_Update_::operator()( - node_iterator(p_nd, this), - const_node_iterator(NULL, this)); + Node_Update_::operator()(node_iterator(p_nd, this), + const_node_iterator(NULL, this)); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp index de220d9..c4a1bb8 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp @@ -59,39 +59,35 @@ PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME() { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : - PB_DS_BASE_C_DEC(r_cmp_fn) + base_type(r_cmp_fn) { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : - PB_DS_BASE_C_DEC(r_cmp_fn, r_node_update) + base_type(r_cmp_fn, r_node_update) { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : - PB_DS_BASE_C_DEC(other) + base_type(other) { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC void @@ -99,16 +95,12 @@ PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - PB_DS_BASE_C_DEC::swap(other); - + base_type::swap(other); _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() -{ - PB_DS_BASE_C_DEC::m_p_head->m_red = true; -} +{ base_type::m_p_head->m_red = true; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp index 3a4049e..08107ec 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp @@ -52,7 +52,7 @@ PB_DS_CLASS_C_DEC:: assert_node_consistent(const node_pointer p_nd) const { if (p_nd == NULL) - return (1); + return 1; const size_type l_height = assert_node_consistent(p_nd->m_p_left); const size_type r_height = assert_node_consistent(p_nd->m_p_right); @@ -62,7 +62,7 @@ assert_node_consistent(const node_pointer p_nd) const _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_right)); } _GLIBCXX_DEBUG_ASSERT(l_height == r_height); - return ((p_nd->m_red? 0 : 1) + l_height); + return (p_nd->m_red ? 0 : 1) + l_height; } PB_DS_CLASS_T_DEC @@ -70,8 +70,8 @@ void PB_DS_CLASS_C_DEC:: assert_valid() const { - PB_DS_BASE_C_DEC::assert_valid(); - const node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; + base_type::assert_valid(); + const node_pointer p_head = base_type::m_p_head; _GLIBCXX_DEBUG_ASSERT(p_head->m_red); if (p_head->m_p_parent != NULL) { diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp index cfe2125..77b4990 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp @@ -50,13 +50,10 @@ PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { point_iterator it = find(r_key); - - if (it == PB_DS_BASE_C_DEC::end()) - return (false); - + if (it == base_type::end()) + return false; erase(it); - - return (true); + return true; } PB_DS_CLASS_T_DEC @@ -65,19 +62,14 @@ PB_DS_CLASS_C_DEC:: erase(iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); - - if (it == PB_DS_BASE_C_DEC::end()) - return (it); + if (it == base_type::end()) + return it; iterator ret_it = it; - ++ret_it; - erase_node(it.m_p_nd); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } PB_DS_CLASS_T_DEC @@ -86,19 +78,14 @@ PB_DS_CLASS_C_DEC:: erase(reverse_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); - - if (it.m_p_nd == PB_DS_BASE_C_DEC::m_p_head) - return (it); + if (it.m_p_nd == base_type::m_p_head) + return it; reverse_iterator ret_it = it; - ++ret_it; - erase_node(it.m_p_nd); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } PB_DS_CLASS_T_DEC @@ -108,17 +95,13 @@ PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - size_type num_ersd = 0; - - iterator it = PB_DS_BASE_C_DEC::begin(); - - while (it != PB_DS_BASE_C_DEC::end()) + size_type num_ersd = 0; + iterator it = base_type::begin(); + while (it != base_type::end()) { if (pred(*it)) { ++num_ersd; - it = erase(it); } else @@ -126,8 +109,7 @@ erase_if(Pred pred) } _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (num_ersd); + return num_ersd; } PB_DS_CLASS_T_DEC @@ -136,9 +118,7 @@ PB_DS_CLASS_C_DEC:: erase_node(node_pointer p_nd) { remove_node(p_nd); - - PB_DS_BASE_C_DEC::actual_erase_node(p_nd); - + base_type::actual_erase_node(p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid()); } @@ -148,11 +128,8 @@ PB_DS_CLASS_C_DEC:: remove_node(node_pointer p_z) { update_min_max_for_erased_node(p_z); - node_pointer p_y = p_z; - node_pointer p_x = NULL; - node_pointer p_new_x_parent = NULL; if (p_y->m_p_left == NULL) @@ -162,68 +139,55 @@ remove_node(node_pointer p_z) else { p_y = p_y->m_p_right; - while (p_y->m_p_left != NULL) p_y = p_y->m_p_left; - p_x = p_y->m_p_right; } if (p_y == p_z) { p_new_x_parent = p_y->m_p_parent; - if (p_x != NULL) p_x->m_p_parent = p_y->m_p_parent; - if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == p_z) - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_x; + if (base_type::m_p_head->m_p_parent == p_z) + base_type::m_p_head->m_p_parent = p_x; else if (p_z->m_p_parent->m_p_left == p_z) { p_y->m_p_left = p_z->m_p_parent; - p_z->m_p_parent->m_p_left = p_x; } else { p_y->m_p_left = NULL; - p_z->m_p_parent->m_p_right = p_x; } } else { p_z->m_p_left->m_p_parent = p_y; - p_y->m_p_left = p_z->m_p_left; - if (p_y != p_z->m_p_right) { p_new_x_parent = p_y->m_p_parent; - if (p_x != NULL) p_x->m_p_parent = p_y->m_p_parent; - p_y->m_p_parent->m_p_left = p_x; - p_y->m_p_right = p_z->m_p_right; - p_z->m_p_right->m_p_parent = p_y; } else p_new_x_parent = p_y; - if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == p_z) - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_y; + if (base_type::m_p_head->m_p_parent == p_z) + base_type::m_p_head->m_p_parent = p_y; else if (p_z->m_p_parent->m_p_left == p_z) p_z->m_p_parent->m_p_left = p_y; else p_z->m_p_parent->m_p_right = p_y; p_y->m_p_parent = p_z->m_p_parent; - std::swap(p_y->m_red, p_z->m_red); - p_y = p_z; } @@ -242,30 +206,23 @@ remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) { _GLIBCXX_DEBUG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent); - while (p_x != PB_DS_BASE_C_DEC::m_p_head->m_p_parent&& - is_effectively_black(p_x)) + while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x)) if (p_x == p_new_x_parent->m_p_left) { node_pointer p_w = p_new_x_parent->m_p_right; - if (p_w->m_red) { p_w->m_red = false; - p_new_x_parent->m_red = true; - - PB_DS_BASE_C_DEC::rotate_left(p_new_x_parent); - + base_type::rotate_left(p_new_x_parent); p_w = p_new_x_parent->m_p_right; } - if (is_effectively_black(p_w->m_p_left)&& - is_effectively_black(p_w->m_p_right)) + if (is_effectively_black(p_w->m_p_left) + && is_effectively_black(p_w->m_p_right)) { p_w->m_red = true; - p_x = p_new_x_parent; - p_new_x_parent = p_new_x_parent->m_p_parent; } else @@ -276,48 +233,37 @@ remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) p_w->m_p_left->m_red = false; p_w->m_red = true; - - PB_DS_BASE_C_DEC::rotate_right(p_w); - + base_type::rotate_right(p_w); p_w = p_new_x_parent->m_p_right; } p_w->m_red = p_new_x_parent->m_red; - p_new_x_parent->m_red = false; if (p_w->m_p_right != NULL) p_w->m_p_right->m_red = false; - PB_DS_BASE_C_DEC::rotate_left(p_new_x_parent); - + base_type::rotate_left(p_new_x_parent); update_to_top(p_new_x_parent, (node_update* )this); - break; } } else { node_pointer p_w = p_new_x_parent->m_p_left; - if (p_w->m_red == true) { p_w->m_red = false; - p_new_x_parent->m_red = true; - - PB_DS_BASE_C_DEC::rotate_right(p_new_x_parent); - + base_type::rotate_right(p_new_x_parent); p_w = p_new_x_parent->m_p_left; } - if (is_effectively_black(p_w->m_p_right)&& - is_effectively_black(p_w->m_p_left)) + if (is_effectively_black(p_w->m_p_right) + && is_effectively_black(p_w->m_p_left)) { p_w->m_red = true; - p_x = p_new_x_parent; - p_new_x_parent = p_new_x_parent->m_p_parent; } else @@ -328,23 +274,18 @@ remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) p_w->m_p_right->m_red = false; p_w->m_red = true; - - PB_DS_BASE_C_DEC::rotate_left(p_w); - + base_type::rotate_left(p_w); p_w = p_new_x_parent->m_p_left; } p_w->m_red = p_new_x_parent->m_red; - p_new_x_parent->m_red = false; if (p_w->m_p_left != NULL) p_w->m_p_left->m_red = false; - PB_DS_BASE_C_DEC::rotate_right(p_new_x_parent); - + base_type::rotate_right(p_new_x_parent); update_to_top(p_new_x_parent, (node_update* )this); - break; } } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp index ca00830..7b65baa 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp @@ -48,7 +48,5 @@ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: is_effectively_black(const node_pointer p_nd) -{ - return (p_nd == NULL || !p_nd->m_red); -} +{ return (p_nd == NULL || !p_nd->m_red); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp index d0e5e10..3bc7ce1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp @@ -50,22 +50,16 @@ PB_DS_CLASS_C_DEC:: insert(const_reference r_value) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - std::pair<point_iterator, bool> ins_pair = - PB_DS_BASE_C_DEC::insert_leaf(r_value); - + std::pair<point_iterator, bool> ins_pair = base_type::insert_leaf(r_value); if (ins_pair.second == true) { ins_pair.first.m_p_nd->m_red = true; - _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();) - - insert_fixup(ins_pair.first.m_p_nd); + insert_fixup(ins_pair.first.m_p_nd); } _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (ins_pair); + return ins_pair; } PB_DS_CLASS_T_DEC @@ -74,22 +68,16 @@ PB_DS_CLASS_C_DEC:: insert_fixup(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_red == true); - - while (p_nd != PB_DS_BASE_C_DEC::m_p_head->m_p_parent&& - p_nd->m_p_parent->m_red) + while (p_nd != base_type::m_p_head->m_p_parent && p_nd->m_p_parent->m_red) { if (p_nd->m_p_parent == p_nd->m_p_parent->m_p_parent->m_p_left) { node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_right; - - if (p_y != NULL&& p_y->m_red) + if (p_y != NULL && p_y->m_red) { p_nd->m_p_parent->m_red = false; - p_y->m_red = false; - p_nd->m_p_parent->m_p_parent->m_red = true; - p_nd = p_nd->m_p_parent->m_p_parent; } else @@ -97,30 +85,21 @@ insert_fixup(node_pointer p_nd) if (p_nd == p_nd->m_p_parent->m_p_right) { p_nd = p_nd->m_p_parent; - - PB_DS_BASE_C_DEC::rotate_left(p_nd); + base_type::rotate_left(p_nd); } - p_nd->m_p_parent->m_red = false; - p_nd->m_p_parent->m_p_parent->m_red = true; - - PB_DS_BASE_C_DEC::rotate_right( - p_nd->m_p_parent->m_p_parent); + base_type::rotate_right(p_nd->m_p_parent->m_p_parent); } } else { node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_left; - - if (p_y != NULL&& p_y->m_red) + if (p_y != NULL && p_y->m_red) { p_nd->m_p_parent->m_red = false; - p_y->m_red = false; - p_nd->m_p_parent->m_p_parent->m_red = true; - p_nd = p_nd->m_p_parent->m_p_parent; } else @@ -128,21 +107,15 @@ insert_fixup(node_pointer p_nd) if (p_nd == p_nd->m_p_parent->m_p_left) { p_nd = p_nd->m_p_parent; - - PB_DS_BASE_C_DEC::rotate_right(p_nd); + base_type::rotate_right(p_nd); } - p_nd->m_p_parent->m_red = false; - p_nd->m_p_parent->m_p_parent->m_red = true; - - PB_DS_BASE_C_DEC::rotate_left( - p_nd->m_p_parent->m_p_parent); + base_type::rotate_left(p_nd->m_p_parent->m_p_parent); } } } - PB_DS_BASE_C_DEC::update_to_top(p_nd, (node_update* )this); - - PB_DS_BASE_C_DEC::m_p_head->m_p_parent->m_red = false; + base_type::update_to_top(p_nd, (node_update* )this); + base_type::m_p_head->m_p_parent->m_red = false; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp index 179e80e..164f965 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp @@ -53,11 +53,13 @@ namespace pb_ds { namespace detail { - template<typename Value_Type, class Metadata, class Allocator> struct rb_tree_node_ { public: + typedef Value_Type value_type; + typedef Metadata metadata_type; + typedef typename Allocator::template rebind< rb_tree_node_< @@ -66,10 +68,6 @@ namespace pb_ds Allocator> >::other::pointer node_pointer; - typedef Value_Type value_type; - - typedef Metadata metadata_type; - typedef typename Allocator::template rebind< metadata_type>::other::reference @@ -80,55 +78,42 @@ namespace pb_ds metadata_type>::other::const_reference const_metadata_reference; - public: inline bool special() const - { - return (m_red); - } + { return m_red; } inline const_metadata_reference get_metadata() const - { - return (m_metadata); - } + { return m_metadata; } inline metadata_reference get_metadata() - { - return (m_metadata); - } + { return m_metadata; } #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ void trace() const { - std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> ") << - "(" << m_metadata << ")"; - + std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> ") + << "(" << m_metadata << ")"; } -#endif // #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ +#endif - public: node_pointer m_p_left; node_pointer m_p_right; - node_pointer m_p_parent; - value_type m_value; - bool m_red; - metadata_type m_metadata; }; template<typename Value_Type, class Allocator> - struct rb_tree_node_< - Value_Type, - null_node_metadata, - Allocator> + struct rb_tree_node_<Value_Type, null_node_metadata, Allocator> { public: + typedef Value_Type value_type; + typedef null_node_metadata metadata_type; + typedef typename Allocator::template rebind< rb_tree_node_< @@ -137,38 +122,23 @@ namespace pb_ds Allocator> >::other::pointer node_pointer; - typedef Value_Type value_type; - - typedef null_node_metadata metadata_type; - - public: inline bool special() const - { - return (m_red); - } + { return m_red; } #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ void trace() const - { - std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> "); - - } -#endif // #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ + { std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> "); } +#endif - public: node_pointer m_p_left; node_pointer m_p_right; - node_pointer m_p_parent; - value_type m_value; - bool m_red; }; - } // namespace detail } // namespace pb_ds -#endif // #ifndef PB_DS_RB_TREE_NODE_HPP +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp index 7942480..d08b2db 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp @@ -73,50 +73,31 @@ namespace pb_ds { namespace detail { - -#define PB_DS_CLASS_T_DEC \ - template< \ - typename Key, \ - typename Mapped, \ - class Cmp_Fn, \ - class Node_And_It_Traits, \ - class Allocator> +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Cmp_Fn, \ + typename Node_And_It_Traits, typename Allocator> #ifdef PB_DS_DATA_TRUE_INDICATOR -#define PB_DS_CLASS_NAME \ - rb_tree_data_ +#define PB_DS_CLASS_NAME rb_tree_data_ #endif #ifdef PB_DS_DATA_TRUE_INDICATOR -#define PB_DS_BASE_CLASS_NAME \ - bin_search_tree_data_ +#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR -#define PB_DS_CLASS_NAME \ - rb_tree_no_data_ +#define PB_DS_CLASS_NAME rb_tree_no_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR -#define PB_DS_BASE_CLASS_NAME \ - bin_search_tree_no_data_ +#define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_ #endif -#define PB_DS_CLASS_C_DEC \ - PB_DS_CLASS_NAME< \ - Key, \ - Mapped, \ - Cmp_Fn, \ - Node_And_It_Traits, \ - Allocator> - -#define PB_DS_BASE_C_DEC \ - PB_DS_BASE_CLASS_NAME< \ - Key, \ - Mapped, \ - Cmp_Fn, \ - Node_And_It_Traits, \ - Allocator> +#define PB_DS_CLASS_C_DEC \ + PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> + +#define PB_DS_BASE_C_DEC \ + PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_V2F(X) (X).first @@ -132,96 +113,61 @@ namespace pb_ds template<typename Key, typename Mapped, - class Cmp_Fn, - class Node_And_It_Traits, - class Allocator> + typename Cmp_Fn, + typename Node_And_It_Traits, + typename Allocator> class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC { - private: - typedef typename PB_DS_BASE_C_DEC::node_pointer node_pointer; + typedef PB_DS_BASE_C_DEC base_type; + typedef typename base_type::node_pointer node_pointer; public: - - typedef typename Allocator::size_type size_type; - - typedef typename Allocator::difference_type difference_type; - - typedef typename PB_DS_BASE_C_DEC::key_type key_type; - - typedef typename PB_DS_BASE_C_DEC::key_pointer key_pointer; - - typedef typename PB_DS_BASE_C_DEC::const_key_pointer const_key_pointer; - - typedef typename PB_DS_BASE_C_DEC::key_reference key_reference; - - typedef - typename PB_DS_BASE_C_DEC::const_key_reference - const_key_reference; - - typedef typename PB_DS_BASE_C_DEC::mapped_type mapped_type; - - typedef typename PB_DS_BASE_C_DEC::mapped_pointer mapped_pointer; - - typedef - typename PB_DS_BASE_C_DEC::const_mapped_pointer - const_mapped_pointer; - - typedef typename PB_DS_BASE_C_DEC::mapped_reference mapped_reference; - - typedef - typename PB_DS_BASE_C_DEC::const_mapped_reference - const_mapped_reference; - - typedef typename PB_DS_BASE_C_DEC::value_type value_type; - - typedef typename PB_DS_BASE_C_DEC::pointer pointer; - - typedef typename PB_DS_BASE_C_DEC::const_pointer const_pointer; - - typedef typename PB_DS_BASE_C_DEC::reference reference; - - typedef typename PB_DS_BASE_C_DEC::const_reference const_reference; - - typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator; - - typedef typename PB_DS_BASE_C_DEC::const_iterator const_point_iterator; - - typedef typename PB_DS_BASE_C_DEC::iterator iterator; - - typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator; - - typedef typename PB_DS_BASE_C_DEC::reverse_iterator reverse_iterator; - - typedef - typename PB_DS_BASE_C_DEC::const_reverse_iterator - const_reverse_iterator; - typedef Cmp_Fn cmp_fn; - typedef Allocator allocator; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::difference_type difference_type; + typedef typename base_type::key_type key_type; + typedef typename base_type::key_pointer key_pointer; + typedef typename base_type::const_key_pointer const_key_pointer; + typedef typename base_type::key_reference key_reference; + typedef typename base_type::const_key_reference const_key_reference; + typedef typename base_type::mapped_type mapped_type; + typedef typename base_type::mapped_pointer mapped_pointer; + typedef typename base_type::const_mapped_pointer const_mapped_pointer; + typedef typename base_type::mapped_reference mapped_reference; + typedef typename base_type::const_mapped_reference const_mapped_reference; + typedef typename base_type::value_type value_type; + typedef typename base_type::pointer pointer; + typedef typename base_type::const_pointer const_pointer; + typedef typename base_type::reference reference; + typedef typename base_type::const_reference const_reference; + typedef typename base_type::point_iterator point_iterator; + typedef typename base_type::const_iterator const_point_iterator; + typedef typename base_type::iterator iterator; + typedef typename base_type::const_iterator const_iterator; + typedef typename base_type::reverse_iterator reverse_iterator; + typedef typename base_type::const_reverse_iterator const_reverse_iterator; + typedef typename base_type::node_update node_update; - typedef typename PB_DS_BASE_C_DEC::node_update node_update; - - public: PB_DS_CLASS_NAME(); - PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); + PB_DS_CLASS_NAME(const Cmp_Fn&); - PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update); + PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&); - PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); void - swap(PB_DS_CLASS_C_DEC& other); + swap(PB_DS_CLASS_C_DEC&); template<typename It> void - copy_from_range(It first_it, It last_it); + copy_from_range(It, It); inline std::pair<point_iterator, bool> - insert(const_reference r_value); + insert(const_reference); inline mapped_reference operator[](const_key_reference r_key) @@ -229,7 +175,7 @@ namespace pb_ds #ifdef PB_DS_DATA_TRUE_INDICATOR _GLIBCXX_DEBUG_ONLY(assert_valid();) std::pair<point_iterator, bool> ins_pair = - PB_DS_BASE_C_DEC::insert_leaf(value_type(r_key, mapped_type())); + base_type::insert_leaf(value_type(r_key, mapped_type())); if (ins_pair.second == true) { @@ -238,32 +184,31 @@ namespace pb_ds insert_fixup(ins_pair.first.m_p_nd); } _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (ins_pair.first.m_p_nd->m_value.second); + return ins_pair.first.m_p_nd->m_value.second; #else insert(r_key); - return (PB_DS_BASE_C_DEC::s_null_mapped); + return base_type::s_null_mapped; #endif } inline bool - erase(const_key_reference r_key); + erase(const_key_reference); inline iterator - erase(iterator it); + erase(iterator); inline reverse_iterator - erase(reverse_iterator it); + erase(reverse_iterator); template<typename Pred> inline size_type - erase_if(Pred pred); + erase_if(Pred); void - join(PB_DS_CLASS_C_DEC& other); + join(PB_DS_CLASS_C_DEC&); void - split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); + split(const_key_reference, PB_DS_CLASS_C_DEC&); protected: @@ -274,29 +219,29 @@ namespace pb_ds assert_valid() const; size_type - assert_node_consistent(const node_pointer p_nd) const; + assert_node_consistent(const node_pointer) const; #endif inline static bool - is_effectively_black(const node_pointer p_nd); + is_effectively_black(const node_pointer); void initialize(); void - insert_fixup(node_pointer p_nd); + insert_fixup(node_pointer); void - erase_node(node_pointer p_nd); + erase_node(node_pointer); void - remove_node(node_pointer p_nd); + remove_node(node_pointer); void - remove_fixup(node_pointer p_x, node_pointer p_new_x_parent); + remove_fixup(node_pointer, node_pointer); void - split_imp(node_pointer p_nd, PB_DS_CLASS_C_DEC& other); + split_imp(node_pointer, PB_DS_CLASS_C_DEC&); inline node_pointer split_min(); @@ -305,20 +250,19 @@ namespace pb_ds split_min_imp(); void - join_imp(node_pointer p_x, node_pointer p_r); + join_imp(node_pointer, node_pointer); std::pair<node_pointer, node_pointer> - find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r); + find_join_pos_right(node_pointer, size_type, size_type); std::pair<node_pointer, node_pointer> - find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r); + find_join_pos_left(node_pointer, size_type, size_type); inline size_type - black_height(node_pointer p_nd); + black_height(node_pointer); void - split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other); - + split_at_node(node_pointer, PB_DS_CLASS_C_DEC&); }; #include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp> @@ -333,7 +277,6 @@ namespace pb_ds #undef PB_DS_CLASS_NAME #undef PB_DS_BASE_CLASS_NAME #undef PB_DS_BASE_C_DEC - #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp index 8cb5750..94b5ac3 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp @@ -51,8 +51,8 @@ join(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) - if (PB_DS_BASE_C_DEC::join_prep(other) == false) + _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) + if (base_type::join_prep(other) == false) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) @@ -61,11 +61,11 @@ join(PB_DS_CLASS_C_DEC& other) const node_pointer p_x = other.split_min(); join_imp(p_x, other.m_p_head->m_p_parent); - PB_DS_BASE_C_DEC::join_finish(other); + base_type::join_finish(other); _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) } PB_DS_CLASS_T_DEC @@ -77,7 +77,7 @@ join_imp(node_pointer p_x, node_pointer p_r) if (p_r != NULL) p_r->m_red = false; - const size_type h = black_height(PB_DS_BASE_C_DEC::m_p_head->m_p_parent); + const size_type h = black_height(base_type::m_p_head->m_p_parent); const size_type other_h = black_height(p_r); node_pointer p_x_l; node_pointer p_x_r; @@ -85,28 +85,28 @@ join_imp(node_pointer p_x, node_pointer p_r) const bool right_join = h >= other_h; if (right_join) { - join_pos = find_join_pos_right(PB_DS_BASE_C_DEC::m_p_head->m_p_parent, + join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, h, other_h); p_x_l = join_pos.first; p_x_r = p_r; } else { - p_x_l = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_r; + p_x_l = base_type::m_p_head->m_p_parent; + base_type::m_p_head->m_p_parent = p_r; if (p_r != NULL) - p_r->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; + p_r->m_p_parent = base_type::m_p_head; - join_pos = find_join_pos_left(PB_DS_BASE_C_DEC::m_p_head->m_p_parent, + join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, h, other_h); p_x_r = join_pos.first; } node_pointer p_parent = join_pos.second; - if (p_parent == PB_DS_BASE_C_DEC::m_p_head) + if (p_parent == base_type::m_p_head) { - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_x; - p_x->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; + base_type::m_p_head->m_p_parent = p_x; + p_x->m_p_parent = base_type::m_p_head; } else { @@ -127,11 +127,11 @@ join_imp(node_pointer p_x, node_pointer p_r) p_x->m_red = true; - PB_DS_BASE_C_DEC::initialize_min_max(); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - PB_DS_BASE_C_DEC::update_to_top(p_x, (node_update* )this); + base_type::initialize_min_max(); + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) + base_type::update_to_top(p_x, (node_update* )this); insert_fixup(p_x); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); } PB_DS_CLASS_T_DEC @@ -139,15 +139,15 @@ inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: split_min() { - node_pointer p_min = PB_DS_BASE_C_DEC::m_p_head->m_p_left; + node_pointer p_min = base_type::m_p_head->m_p_left; #ifdef _GLIBCXX_DEBUG - const node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; + const node_pointer p_head = base_type::m_p_head; _GLIBCXX_DEBUG_ASSERT(p_min != p_head); #endif remove_node(p_min); - return (p_min); + return p_min; } PB_DS_CLASS_T_DEC @@ -159,10 +159,10 @@ find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) { _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); - if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == NULL) - return (std::make_pair((node_pointer)NULL, PB_DS_BASE_C_DEC::m_p_head)); + if (base_type::m_p_head->m_p_parent == NULL) + return (std::make_pair((node_pointer)NULL, base_type::m_p_head)); - node_pointer p_l_parent = PB_DS_BASE_C_DEC::m_p_head; + node_pointer p_l_parent = base_type::m_p_head; while (h_l > h_r) { if (p_l->m_red == false) @@ -195,10 +195,10 @@ PB_DS_CLASS_C_DEC:: find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) { _GLIBCXX_DEBUG_ASSERT(h_r > h_l); - if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == NULL) + if (base_type::m_p_head->m_p_parent == NULL) return (std::make_pair((node_pointer)NULL, - PB_DS_BASE_C_DEC::m_p_head)); - node_pointer p_r_parent = PB_DS_BASE_C_DEC::m_p_head; + base_type::m_p_head)); + node_pointer p_r_parent = base_type::m_p_head; while (h_r > h_l) { if (p_r->m_red == false) @@ -244,20 +244,20 @@ PB_DS_CLASS_C_DEC:: split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid()); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid()); - _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) - if (PB_DS_BASE_C_DEC::split_prep(r_key, other) == false) + if (base_type::split_prep(r_key, other) == false) { _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); return; } - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) node_pointer p_nd = upper_bound(r_key).m_p_nd; do { @@ -265,13 +265,13 @@ split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) split_at_node(p_nd, other); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) p_nd = p_next_nd; } - while (p_nd != PB_DS_BASE_C_DEC::m_p_head); + while (p_nd != base_type::m_p_head); - PB_DS_BASE_C_DEC::split_finish(other); + base_type::split_finish(other); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(assert_valid();) } @@ -286,12 +286,12 @@ split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) node_pointer p_l = p_nd->m_p_left; node_pointer p_r = p_nd->m_p_right; node_pointer p_parent = p_nd->m_p_parent; - if (p_parent == PB_DS_BASE_C_DEC::m_p_head) + if (p_parent == base_type::m_p_head) { - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_l; + base_type::m_p_head->m_p_parent = p_l; if (p_l != NULL) { - p_l->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; + p_l->m_p_parent = base_type::m_p_head; p_l->m_red = false; } } @@ -311,9 +311,9 @@ split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) remove_fixup(p_l, p_parent); } - PB_DS_BASE_C_DEC::initialize_min_max(); + base_type::initialize_min_max(); other.join_imp(p_nd, p_r); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); - _GLIBCXX_DEBUG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid()); + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); + _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid()); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp index 77db8dd..67570d8 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp @@ -53,16 +53,15 @@ namespace pb_ds { namespace detail { - template<typename Key, typename Mapped, - class Cmp_Fn, + typename Cmp_Fn, template<typename Const_Node_Iterator, class Node_Iterator, class Cmp_Fn_, class Allocator_> class Node_Update, - class Allocator> + typename Allocator> struct tree_traits< Key, Mapped, @@ -128,4 +127,4 @@ namespace pb_ds } // namespace detail } // namespace pb_ds -#endif // #ifndef PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp index 459fdc1..b05a672 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp @@ -59,39 +59,35 @@ PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME() { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : - PB_DS_BASE_C_DEC(r_cmp_fn) + base_type(r_cmp_fn) { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : - PB_DS_BASE_C_DEC(r_cmp_fn, r_node_update) + base_type(r_cmp_fn, r_node_update) { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : - PB_DS_BASE_C_DEC(other) + base_type(other) { initialize(); - _GLIBCXX_DEBUG_ONLY(assert_valid();) - } +} PB_DS_CLASS_T_DEC void @@ -99,18 +95,14 @@ PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - PB_DS_BASE_C_DEC::swap(other); - + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + base_type::swap(other); _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() -{ - PB_DS_BASE_C_DEC::m_p_head->m_special = true; -} +{ base_type::m_p_head->m_special = true; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp index 6f78bf2..cf7aaa8 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp @@ -51,8 +51,8 @@ void PB_DS_CLASS_C_DEC:: assert_valid() const { - PB_DS_BASE_C_DEC::assert_valid(); - const node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; + base_type::assert_valid(); + const node_pointer p_head = base_type::m_p_head; assert_special_imp(p_head); } @@ -64,7 +64,7 @@ assert_special_imp(const node_pointer p_nd) const if (p_nd == NULL) return; - if (p_nd == PB_DS_BASE_C_DEC::m_p_head) + if (p_nd == base_type::m_p_head) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_special); assert_special_imp(p_nd->m_p_parent); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp index 272bd36..26288fb 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp @@ -50,13 +50,10 @@ PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { point_iterator it = find(r_key); - - if (it == PB_DS_BASE_C_DEC::end()) - return (false); - + if (it == base_type::end()) + return false; erase(it); - - return (true); + return true; } PB_DS_CLASS_T_DEC @@ -65,19 +62,13 @@ PB_DS_CLASS_C_DEC:: erase(iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); - - if (it == PB_DS_BASE_C_DEC::end()) - return (it); - + if (it == base_type::end()) + return it; iterator ret_it = it; - ++ret_it; - erase_node(it.m_p_nd); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } PB_DS_CLASS_T_DEC @@ -86,19 +77,13 @@ PB_DS_CLASS_C_DEC:: erase(reverse_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); - - if (it.m_p_nd == PB_DS_BASE_C_DEC::m_p_head) + if (it.m_p_nd == base_type::m_p_head) return (it); - reverse_iterator ret_it = it; - ++ret_it; - erase_node(it.m_p_nd); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ret_it); + return ret_it; } PB_DS_CLASS_T_DEC @@ -108,26 +93,20 @@ PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - size_type num_ersd = 0; - - iterator it = PB_DS_BASE_C_DEC::begin(); - - while (it != PB_DS_BASE_C_DEC::end()) + size_type num_ersd = 0; + iterator it = base_type::begin(); + while (it != base_type::end()) { if (pred(*it)) { ++num_ersd; - it = erase(it); } else ++it; } - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return (num_ersd); + return num_ersd; } PB_DS_CLASS_T_DEC @@ -136,56 +115,40 @@ PB_DS_CLASS_C_DEC:: erase_node(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); - splay(p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); + _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); node_pointer p_l = p_nd->m_p_left; node_pointer p_r = p_nd->m_p_right; - PB_DS_BASE_C_DEC::update_min_max_for_erased_node(p_nd); - - PB_DS_BASE_C_DEC::actual_erase_node(p_nd); - + base_type::update_min_max_for_erased_node(p_nd); + base_type::actual_erase_node(p_nd); if (p_r == NULL) { - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_l; - + base_type::m_p_head->m_p_parent = p_l; if (p_l != NULL) - p_l->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; - + p_l->m_p_parent = base_type::m_p_head; _GLIBCXX_DEBUG_ONLY(assert_valid();) - - return; + return; } node_pointer p_target_r = leftmost(p_r); - _GLIBCXX_DEBUG_ASSERT(p_target_r != NULL); - - p_r->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; - - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_r; - + p_r->m_p_parent = base_type::m_p_head; + base_type::m_p_head->m_p_parent = p_r; splay(p_target_r); _GLIBCXX_DEBUG_ONLY(p_target_r->m_p_left = NULL); - _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_parent == this->m_p_head); - - _GLIBCXX_DEBUG_ASSERT(this->m_p_head->m_p_parent == - p_target_r); + _GLIBCXX_DEBUG_ASSERT(this->m_p_head->m_p_parent == p_target_r); p_target_r->m_p_left = p_l; - if (p_l != NULL) p_l->m_p_parent = p_target_r; - _GLIBCXX_DEBUG_ONLY(assert_valid();) - - apply_update(p_target_r, (node_update* )this); + apply_update(p_target_r, (node_update* )this); } PB_DS_CLASS_T_DEC @@ -194,9 +157,7 @@ PB_DS_CLASS_C_DEC:: leftmost(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); - while (p_nd->m_p_left != NULL) p_nd = p_nd->m_p_left; - - return (p_nd); + return p_nd; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp index 6be38e2..6fdb8f5 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp @@ -50,11 +50,9 @@ PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) { node_pointer p_found = find_imp(r_key); - - if (p_found != PB_DS_BASE_C_DEC::m_p_head) + if (p_found != base_type::m_p_head) splay(p_found); - - return (point_iterator(p_found)); + return point_iterator(p_found); } PB_DS_CLASS_T_DEC @@ -63,11 +61,9 @@ PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) const { const node_pointer p_found = find_imp(r_key); - - if (p_found != PB_DS_BASE_C_DEC::m_p_head) + if (p_found != base_type::m_p_head) const_cast<PB_DS_CLASS_C_DEC* >(this)->splay(p_found); - - return (point_iterator(p_found)); + return point_iterator(p_found); } PB_DS_CLASS_T_DEC @@ -75,22 +71,18 @@ inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: find_imp(const_key_reference r_key) { - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - - node_pointer p_nd = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; - + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) + node_pointer p_nd = base_type::m_p_head->m_p_parent; while (p_nd != NULL) if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) { if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) - return (p_nd); - + return p_nd; p_nd = p_nd->m_p_left; } else p_nd = p_nd->m_p_right; - - return PB_DS_BASE_C_DEC::m_p_head; + return base_type::m_p_head; } PB_DS_CLASS_T_DEC @@ -99,19 +91,15 @@ PB_DS_CLASS_C_DEC:: find_imp(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - node_pointer p_nd = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; - + node_pointer p_nd = base_type::m_p_head->m_p_parent; while (p_nd != NULL) if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) { if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) - return (p_nd); - + return p_nd; p_nd = p_nd->m_p_left; } else p_nd = p_nd->m_p_right; - - return PB_DS_BASE_C_DEC::m_p_head; + return base_type::m_p_head; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp index c9f3768..f4b9f95 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp @@ -50,19 +50,12 @@ PB_DS_CLASS_C_DEC:: insert(const_reference r_value) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - - std::pair<point_iterator, bool> ins_pair = - insert_leaf_imp(r_value); - + std::pair<point_iterator, bool> ins_pair = insert_leaf_imp(r_value); ins_pair.first.m_p_nd->m_special = false; - _GLIBCXX_DEBUG_ONLY(assert_valid()); - splay(ins_pair.first.m_p_nd); - _GLIBCXX_DEBUG_ONLY(assert_valid()); - - return (ins_pair); + return ins_pair; } PB_DS_CLASS_T_DEC @@ -70,55 +63,37 @@ inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> PB_DS_CLASS_C_DEC:: insert_leaf_imp(const_reference r_value) { - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) - - if (PB_DS_BASE_C_DEC::m_size == 0) - return (std::make_pair( - PB_DS_BASE_C_DEC::insert_imp_empty(r_value), - true)); + _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) + if (base_type::m_size == 0) + return std::make_pair(base_type::insert_imp_empty(r_value), true); - node_pointer p_nd = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; - node_pointer p_pot = PB_DS_BASE_C_DEC::m_p_head; + node_pointer p_nd = base_type::m_p_head->m_p_parent; + node_pointer p_pot = base_type::m_p_head; while (p_nd != NULL) - if (!Cmp_Fn::operator()( - PB_DS_V2F(p_nd->m_value), - PB_DS_V2F(r_value))) + if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), PB_DS_V2F(r_value))) { - if (!Cmp_Fn::operator()( - PB_DS_V2F(r_value), - PB_DS_V2F(p_nd->m_value))) + if (!Cmp_Fn::operator()(PB_DS_V2F(r_value), PB_DS_V2F(p_nd->m_value))) { - return std::make_pair( - point_iterator(p_nd), - false); + return std::make_pair(point_iterator(p_nd), false); } - p_pot = p_nd; - p_nd = p_nd->m_p_left; } else p_nd = p_nd->m_p_right; - if (p_pot == PB_DS_BASE_C_DEC::m_p_head) - return (std::make_pair( - PB_DS_BASE_C_DEC::insert_leaf_new(r_value, PB_DS_BASE_C_DEC::m_p_head->m_p_right, false), - true)); + if (p_pot == base_type::m_p_head) + return std::make_pair(base_type::insert_leaf_new(r_value, base_type::m_p_head->m_p_right, false), true); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::check_key_does_not_exist( - PB_DS_V2F(r_value))); + _GLIBCXX_DEBUG_ONLY(base_type::check_key_does_not_exist(PB_DS_V2F(r_value))); p_nd = p_pot->m_p_left; if (p_nd == NULL) - return (std::make_pair( - PB_DS_BASE_C_DEC::insert_leaf_new( r_value, p_pot, true), - true)); + return (std::make_pair(base_type::insert_leaf_new(r_value, p_pot, true), true)); while (p_nd->m_p_right != NULL) p_nd = p_nd->m_p_right; - return (std::make_pair( - insert_leaf_new(r_value, p_nd, false), - true)); + return std::make_pair(insert_leaf_new(r_value, p_nd, false), true); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp index 2e3bb30..d23e931 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp @@ -51,121 +51,81 @@ namespace pb_ds { namespace detail { - template<typename Value_Type, class Metadata, class Allocator> struct splay_tree_node_ { public: + typedef Value_Type value_type; + typedef Metadata metadata_type; + typedef typename Allocator::template rebind< - splay_tree_node_< - Value_Type, - Metadata, - Allocator> >::other::pointer + splay_tree_node_<Value_Type, Metadata, Allocator> >::other::pointer node_pointer; - typedef Metadata metadata_type; - typedef - typename Allocator::template rebind< - metadata_type>::other::reference + typename Allocator::template rebind<metadata_type>::other::reference metadata_reference; typedef - typename Allocator::template rebind< - metadata_type>::other::const_reference + typename Allocator::template rebind<metadata_type>::other::const_reference const_metadata_reference; #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ void trace() const - { - std::cout << PB_DS_V2F(m_value) << - "(" << m_metadata << ")"; - } -#endif // #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ + { std::cout << PB_DS_V2F(m_value) << "(" << m_metadata << ")"; } +#endif - public: inline bool special() const - { - return (m_special); - } + { return m_special; } inline const_metadata_reference get_metadata() const - { - return (m_metadata); - } + { return m_metadata; } inline metadata_reference get_metadata() - { - return (m_metadata); - } - - public: - typedef Value_Type value_type; + { return m_metadata; } value_type m_value; - bool m_special; - node_pointer m_p_left; node_pointer m_p_right; - node_pointer m_p_parent; - metadata_type m_metadata; }; - template<typename Value_Type, class Allocator> - struct splay_tree_node_< - Value_Type, - null_node_metadata, - Allocator> + template<typename Value_Type, typename Allocator> + struct splay_tree_node_<Value_Type, null_node_metadata, Allocator> { public: + typedef Value_Type value_type; + typedef null_node_metadata metadata_type; + typedef typename Allocator::template rebind< - splay_tree_node_< - Value_Type, - null_node_metadata, - Allocator> >::other::pointer + splay_tree_node_<Value_Type, null_node_metadata, Allocator> >::other::pointer node_pointer; - typedef Value_Type value_type; - - typedef null_node_metadata metadata_type; - - public: inline bool special() const - { - return (m_special); - } + { return m_special; } #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ void trace() const - { - std::cout << PB_DS_V2F(m_value); - - } -#endif // #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ + { std::cout << PB_DS_V2F(m_value); } +#endif - public: node_pointer m_p_left; node_pointer m_p_right; - node_pointer m_p_parent; - value_type m_value; - bool m_special; }; - } // namespace detail } // namespace pb_ds -#endif // #ifndef PB_DS_SPLAY_TREE_NODE_HPP +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp index 1525b5c..62def3c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp @@ -49,20 +49,20 @@ void PB_DS_CLASS_C_DEC:: splay(node_pointer p_nd) { - while (p_nd->m_p_parent != PB_DS_BASE_C_DEC::m_p_head) + while (p_nd->m_p_parent != base_type::m_p_head) { #ifdef _GLIBCXX_DEBUG { - node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; + node_pointer p_head = base_type::m_p_head; assert_special_imp(p_head); } #endif - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_nd);) + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);) - if (p_nd->m_p_parent->m_p_parent == PB_DS_BASE_C_DEC::m_p_head) + if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head) { - PB_DS_BASE_C_DEC::rotate_parent(p_nd); + base_type::rotate_parent(p_nd); _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); } else @@ -72,7 +72,7 @@ splay(node_pointer p_nd) #ifdef _GLIBCXX_DEBUG const size_type total = - PB_DS_BASE_C_DEC::recursive_count(p_grandparent); + base_type::recursive_count(p_grandparent); _GLIBCXX_DEBUG_ASSERT(total >= 3); #endif @@ -90,19 +90,20 @@ splay(node_pointer p_nd) _GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd)); } - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_nd);) + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);) } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent) +splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, + node_pointer p_grandparent) { _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);) + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd && p_grandparent->m_p_right == p_parent); @@ -132,12 +133,13 @@ splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_gran PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent) +splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, + node_pointer p_grandparent) { _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);) + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd && p_grandparent->m_p_left == p_parent); @@ -167,12 +169,13 @@ splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_gra PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent) +splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, + node_pointer p_grandparent) { _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);) + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd && p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent); @@ -202,15 +205,14 @@ splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_gran PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent) +splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, + node_pointer p_grandparent) { _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); - - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);) - - _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd&& - p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent); + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) + _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd && + p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent); splay_zz_start(p_nd, p_parent, p_grandparent); @@ -231,7 +233,7 @@ splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_gra if (p_c != NULL) p_c->m_p_parent = p_grandparent; - PB_DS_BASE_C_DEC::update_to_top(p_grandparent, (node_update* )this); + base_type::update_to_top(p_grandparent, (node_update* )this); splay_zz_end(p_nd, p_parent, p_grandparent); } @@ -250,15 +252,12 @@ splay_zz_start(node_pointer p_nd, _GLIBCXX_DEBUG_ASSERT(p_parent != NULL); _GLIBCXX_DEBUG_ASSERT(p_grandparent != NULL); - const bool grandparent_head = - p_grandparent->m_p_parent == PB_DS_BASE_C_DEC::m_p_head; + const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head; if (grandparent_head) { - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = - PB_DS_BASE_C_DEC::m_p_head->m_p_parent; - - p_nd->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; + base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent; + p_nd->m_p_parent = base_type::m_p_head; return; } @@ -275,15 +274,16 @@ splay_zz_start(node_pointer p_nd, PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent) +splay_zz_end(node_pointer p_nd, node_pointer p_parent, + node_pointer p_grandparent) { - if (p_nd->m_p_parent == PB_DS_BASE_C_DEC::m_p_head) - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_nd; + if (p_nd->m_p_parent == base_type::m_p_head) + base_type::m_p_head->m_p_parent = p_nd; apply_update(p_grandparent, (node_update* )this); apply_update(p_parent, (node_update* )this); apply_update(p_nd, (node_update* )this); - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_nd);) + _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);) } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp index 281b47d..bf90525 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp @@ -97,50 +97,31 @@ namespace pb_ds { namespace detail { - -#define PB_DS_CLASS_T_DEC \ - template< \ - typename Key, \ - typename Mapped, \ - class Cmp_Fn, \ - class Node_And_It_Traits, \ - class Allocator> +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Cmp_Fn, \ + typename Node_And_It_Traits, typename Allocator> #ifdef PB_DS_DATA_TRUE_INDICATOR -#define PB_DS_CLASS_NAME \ - splay_tree_data_ +#define PB_DS_CLASS_NAME splay_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR -#define PB_DS_CLASS_NAME \ - splay_tree_no_data_ +#define PB_DS_CLASS_NAME splay_tree_no_data_ #endif #ifdef PB_DS_DATA_TRUE_INDICATOR -#define PB_DS_BASE_CLASS_NAME \ - bin_search_tree_data_ +#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR -#define PB_DS_BASE_CLASS_NAME \ - bin_search_tree_no_data_ +#define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_ #endif -#define PB_DS_CLASS_C_DEC \ - PB_DS_CLASS_NAME< \ - Key, \ - Mapped, \ - Cmp_Fn, \ - Node_And_It_Traits, \ - Allocator> - -#define PB_DS_BASE_C_DEC \ - PB_DS_BASE_CLASS_NAME< \ - Key, \ - Mapped, \ - Cmp_Fn, \ - Node_And_It_Traits, \ - Allocator> +#define PB_DS_CLASS_C_DEC \ + PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> + +#define PB_DS_BASE_C_DEC \ + PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_V2F(X) (X).first @@ -155,102 +136,61 @@ namespace pb_ds #endif // $p14y 7r33 7481. - template<typename Key, - typename Mapped, - class Cmp_Fn, - class Node_And_It_Traits, - class Allocator> + template<typename Key, typename Mapped, typename Cmp_Fn, + typename Node_And_It_Traits, typename Allocator> class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC { - private: - typedef typename PB_DS_BASE_C_DEC::node_pointer node_pointer; + typedef PB_DS_BASE_C_DEC base_type; + typedef typename base_type::node_pointer node_pointer; public: - + typedef Allocator allocator; typedef typename Allocator::size_type size_type; - typedef typename Allocator::difference_type difference_type; - - typedef typename PB_DS_BASE_C_DEC::key_type key_type; - - typedef typename PB_DS_BASE_C_DEC::key_pointer key_pointer; - - typedef typename PB_DS_BASE_C_DEC::const_key_pointer const_key_pointer; - - typedef typename PB_DS_BASE_C_DEC::key_reference key_reference; - - typedef - typename PB_DS_BASE_C_DEC::const_key_reference - const_key_reference; - - typedef typename PB_DS_BASE_C_DEC::mapped_type mapped_type; - - typedef typename PB_DS_BASE_C_DEC::mapped_pointer mapped_pointer; - - typedef - typename PB_DS_BASE_C_DEC::const_mapped_pointer - const_mapped_pointer; - - typedef typename PB_DS_BASE_C_DEC::mapped_reference mapped_reference; - - typedef - typename PB_DS_BASE_C_DEC::const_mapped_reference - const_mapped_reference; - - typedef typename PB_DS_BASE_C_DEC::value_type value_type; - - typedef typename PB_DS_BASE_C_DEC::pointer pointer; - - typedef typename PB_DS_BASE_C_DEC::const_pointer const_pointer; - - typedef typename PB_DS_BASE_C_DEC::reference reference; - - typedef typename PB_DS_BASE_C_DEC::const_reference const_reference; - - typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator; - - typedef typename PB_DS_BASE_C_DEC::const_iterator const_point_iterator; - - typedef typename PB_DS_BASE_C_DEC::iterator iterator; - - typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator; - - typedef typename PB_DS_BASE_C_DEC::reverse_iterator reverse_iterator; - - typedef - typename PB_DS_BASE_C_DEC::const_reverse_iterator - const_reverse_iterator; - typedef Cmp_Fn cmp_fn; - - typedef Allocator allocator; - - typedef typename PB_DS_BASE_C_DEC::node_update node_update; - - public: + typedef typename base_type::key_type key_type; + typedef typename base_type::key_pointer key_pointer; + typedef typename base_type::const_key_pointer const_key_pointer; + typedef typename base_type::key_reference key_reference; + typedef typename base_type::const_key_reference const_key_reference; + typedef typename base_type::mapped_type mapped_type; + typedef typename base_type::mapped_pointer mapped_pointer; + typedef typename base_type::const_mapped_pointer const_mapped_pointer; + typedef typename base_type::mapped_reference mapped_reference; + typedef typename base_type::const_mapped_reference const_mapped_reference; + typedef typename base_type::value_type value_type; + typedef typename base_type::pointer pointer; + typedef typename base_type::const_pointer const_pointer; + typedef typename base_type::reference reference; + typedef typename base_type::const_reference const_reference; + typedef typename base_type::point_iterator point_iterator; + typedef typename base_type::const_iterator const_point_iterator; + typedef typename base_type::iterator iterator; + typedef typename base_type::const_iterator const_iterator; + typedef typename base_type::reverse_iterator reverse_iterator; + typedef typename base_type::const_reverse_iterator const_reverse_iterator; + typedef typename base_type::node_update node_update; PB_DS_CLASS_NAME(); - PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); + PB_DS_CLASS_NAME(const Cmp_Fn&); - PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update); + PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&); - PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); void - swap(PB_DS_CLASS_C_DEC& other); + swap(PB_DS_CLASS_C_DEC&); template<typename It> void - copy_from_range(It first_it, It last_it); + copy_from_range(It, It); void initialize(); - inline std::pair< - point_iterator, - bool> + inline std::pair<point_iterator, bool> insert(const_reference r_value); inline mapped_reference @@ -262,87 +202,85 @@ namespace pb_ds insert_leaf_imp(value_type(r_key, mapped_type())); ins_pair.first.m_p_nd->m_special = false; - _GLIBCXX_DEBUG_ONLY(PB_DS_BASE_C_DEC::assert_valid()); + _GLIBCXX_DEBUG_ONLY(base_type::assert_valid()); splay(ins_pair.first.m_p_nd); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) return ins_pair.first.m_p_nd->m_value.second; #else insert(r_key); - return PB_DS_BASE_C_DEC::s_null_mapped; + return base_type::s_null_mapped; #endif } inline point_iterator - find(const_key_reference r_key); + find(const_key_reference); inline const_point_iterator - find(const_key_reference r_key) const; + find(const_key_reference) const; inline bool - erase(const_key_reference r_key); + erase(const_key_reference); inline iterator erase(iterator it); inline reverse_iterator - erase(reverse_iterator it); + erase(reverse_iterator); template<typename Pred> inline size_type - erase_if(Pred pred); + erase_if(Pred); void - join(PB_DS_CLASS_C_DEC& other); + join(PB_DS_CLASS_C_DEC&); void - split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); + split(const_key_reference, PB_DS_CLASS_C_DEC&); private: - inline std::pair<point_iterator, bool> - insert_leaf_imp(const_reference r_mapped_value); + insert_leaf_imp(const_reference); inline node_pointer - find_imp(const_key_reference r_key); + find_imp(const_key_reference); inline const node_pointer - find_imp(const_key_reference r_key) const; + find_imp(const_key_reference) const; #ifdef _GLIBCXX_DEBUG void assert_valid() const; void - assert_special_imp(const node_pointer p_nd) const; + assert_special_imp(const node_pointer) const; #endif void - splay(node_pointer p_nd); + splay(node_pointer); inline void - splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent); + splay_zig_zag_left(node_pointer, node_pointer, node_pointer); inline void - splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent); + splay_zig_zag_right(node_pointer, node_pointer, node_pointer); inline void - splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent); + splay_zig_zig_left(node_pointer, node_pointer, node_pointer); inline void - splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent); + splay_zig_zig_right(node_pointer, node_pointer, node_pointer); inline void - splay_zz_start(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent); + splay_zz_start(node_pointer, node_pointer, node_pointer); inline void - splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent); + splay_zz_end(node_pointer, node_pointer, node_pointer); inline node_pointer - leftmost(node_pointer p_nd); + leftmost(node_pointer); void - erase_node(node_pointer p_nd); - + erase_node(node_pointer); }; #include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp> @@ -358,7 +296,6 @@ namespace pb_ds #undef PB_DS_CLASS_NAME #undef PB_DS_BASE_CLASS_NAME #undef PB_DS_BASE_C_DEC - #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp index f8f73df..c752f71 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp @@ -50,40 +50,35 @@ PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - if (PB_DS_BASE_C_DEC::join_prep(other) == false) - { - _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - - return; - } + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + if (base_type::join_prep(other) == false) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; + } node_pointer p_target_r = other.leftmost(other.m_p_head); - _GLIBCXX_DEBUG_ASSERT(p_target_r != NULL); - other.splay(p_target_r); _GLIBCXX_DEBUG_ASSERT(p_target_r == other.m_p_head->m_p_parent); _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_left == NULL); - p_target_r->m_p_left = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; + p_target_r->m_p_left = base_type::m_p_head->m_p_parent; _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_left != NULL); p_target_r->m_p_left->m_p_parent = p_target_r; - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_target_r; - p_target_r->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; - + base_type::m_p_head->m_p_parent = p_target_r; + p_target_r->m_p_parent = base_type::m_p_head; apply_update(p_target_r, (node_update* )this); - PB_DS_BASE_C_DEC::join_finish(other); + base_type::join_finish(other); _GLIBCXX_DEBUG_ONLY(assert_valid();) - _GLIBCXX_DEBUG_ONLY(other.assert_valid();) - } + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} PB_DS_CLASS_T_DEC void @@ -93,11 +88,10 @@ split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); - if (PB_DS_BASE_C_DEC::split_prep(r_key, other) == false) + if (base_type::split_prep(r_key, other) == false) { _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); - return; } @@ -110,16 +104,13 @@ split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) node_pointer p_new_root = p_upper_bound->m_p_left; _GLIBCXX_DEBUG_ASSERT(p_new_root != NULL); - PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_new_root; - p_new_root->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; - + base_type::m_p_head->m_p_parent = p_new_root; + p_new_root->m_p_parent = base_type::m_p_head; other.m_p_head->m_p_parent = p_upper_bound; p_upper_bound->m_p_parent = other.m_p_head; p_upper_bound->m_p_left = NULL; - apply_update(p_upper_bound, (node_update* )this); - - PB_DS_BASE_C_DEC::split_finish(other); + base_type::split_finish(other); _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp index 2cdb733..a758ef9 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp @@ -96,26 +96,14 @@ namespace pb_ds class Node_Iterator, class Cmp_Fn_, class Allocator_> - class Node_Update, + class Node_Update, class Allocator> - struct tree_traits< - Key, - null_mapped_type, - Cmp_Fn, - Node_Update, - splay_tree_tag, - Allocator> : public bin_search_tree_traits< - Key, - null_mapped_type, - Cmp_Fn, - Node_Update, - splay_tree_node_< - typename types_traits< - Key, - null_mapped_type, - Allocator, - false>::value_type, - typename tree_node_metadata_selector< + struct tree_traits<Key, null_mapped_type, Cmp_Fn, Node_Update, + splay_tree_tag, Allocator> + : public bin_search_tree_traits<Key, null_mapped_type, Cmp_Fn, + Node_Update, + splay_tree_node_<typename types_traits<Key, null_mapped_type, Allocator, false>::value_type, + typename tree_node_metadata_selector< Key, null_mapped_type, Cmp_Fn, |