diff options
Diffstat (limited to 'libstdc++-v3/include/ext')
7 files changed, 51 insertions, 9 deletions
diff --git a/libstdc++-v3/include/ext/atomicity.h b/libstdc++-v3/include/ext/atomicity.h index 98f745c..650b786 100644 --- a/libstdc++-v3/include/ext/atomicity.h +++ b/libstdc++-v3/include/ext/atomicity.h @@ -61,7 +61,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // To abstract locking primitives across all thread policies, use: // __exchange_and_add_dispatch // __atomic_add_dispatch -#ifdef _GLIBCXX_ATOMIC_BUILTINS +#ifdef _GLIBCXX_ATOMIC_WORD_BUILTINS inline _Atomic_word __attribute__((__always_inline__)) __exchange_and_add(volatile _Atomic_word* __mem, int __val) @@ -71,7 +71,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __attribute__((__always_inline__)) __atomic_add(volatile _Atomic_word* __mem, int __val) { __atomic_fetch_add(__mem, __val, __ATOMIC_ACQ_REL); } -#else +#else // Defined in config/cpu/.../atomicity.h _Atomic_word __exchange_and_add(volatile _Atomic_word*, int) _GLIBCXX_NOTHROW; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp index 6088709..a8c73b5 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp @@ -305,6 +305,9 @@ namespace __gnu_pbds rotate_parent(node_pointer); inline void + update_subtree_size(node_pointer); + + inline void apply_update(node_pointer, null_node_update_pointer); template<typename Node_Update_> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp index e6e954d..b8f5014 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp @@ -122,7 +122,6 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd) } p_new_nd->m_p_parent = p_nd; - p_new_nd->m_p_left = p_new_nd->m_p_right = 0; PB_DS_ASSERT_NODE_CONSISTENT(p_nd) update_to_top(p_new_nd, (node_update* )this); @@ -142,7 +141,6 @@ insert_imp_empty(const_reference r_value) m_p_head->m_p_parent = p_new_node; p_new_node->m_p_parent = m_p_head; - p_new_node->m_p_left = p_new_node->m_p_right = 0; _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));) update_to_top(m_p_head->m_p_parent, (node_update*)this); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp index 069b17f..8cadce2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp @@ -122,8 +122,23 @@ rotate_parent(node_pointer p_nd) PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) -{ } +update_subtree_size(node_pointer p_nd) +{ + size_type size = 1; + if (p_nd->m_p_left) + size += p_nd->m_p_left->m_subtree_size; + if (p_nd->m_p_right) + size += p_nd->m_p_right->m_subtree_size; + p_nd->m_subtree_size = size; +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +apply_update(node_pointer p_nd, null_node_update_pointer /*p_update*/) +{ + update_subtree_size(p_nd); +} PB_DS_CLASS_T_DEC template<typename Node_Update_> @@ -131,6 +146,7 @@ inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer p_nd, Node_Update_* /*p_update*/) { + update_subtree_size(p_nd); node_update::operator()(node_iterator(p_nd), node_const_iterator(static_cast<node_pointer>(0))); } @@ -152,7 +168,14 @@ update_to_top(node_pointer p_nd, Node_Update_* p_update) PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: -update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) -{ } +update_to_top(node_pointer p_nd, null_node_update_pointer /*p_update */) +{ + while (p_nd != m_p_head) + { + update_subtree_size(p_nd); + + p_nd = p_nd->m_p_parent; + } +} #endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp index 0c1b26f..a2a5775 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp @@ -133,7 +133,9 @@ PB_DS_CLASS_C_DEC:: split_finish(PB_DS_CLASS_C_DEC& other) { other.initialize_min_max(); - other.m_size = std::distance(other.begin(), other.end()); + other.m_size = 0; + if (other.m_p_head->m_p_parent != 0) + other.m_size = other.m_p_head->m_p_parent->m_subtree_size; m_size -= other.m_size; initialize_min_max(); PB_DS_ASSERT_VALID((*this)) 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 f229be7..3803ddb 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 @@ -58,6 +58,9 @@ namespace __gnu_pbds typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer node_pointer; + typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type + size_type; + typedef typename rebind_traits<_Alloc, metadata_type>::reference metadata_reference; @@ -88,6 +91,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; value_type m_value; bool m_red; metadata_type m_metadata; @@ -100,6 +104,9 @@ namespace __gnu_pbds typedef Value_Type value_type; typedef null_type metadata_type; + typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type + size_type; + typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer node_pointer; @@ -116,6 +123,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; value_type m_value; bool m_red; }; 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 961afbe..b5fbb50 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 @@ -56,6 +56,9 @@ namespace __gnu_pbds typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer node_pointer; + typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type + size_type; + typedef typename rebind_traits<_Alloc, metadata_type>::reference metadata_reference; @@ -85,6 +88,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; metadata_type m_metadata; }; @@ -98,6 +102,9 @@ namespace __gnu_pbds typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer node_pointer; + typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type + size_type; + inline bool special() const { return m_special; } @@ -111,6 +118,7 @@ namespace __gnu_pbds node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; + size_type m_subtree_size; value_type m_value; bool m_special; }; |