[gcc r16-770] libstdc++: remove two redundant statements in pb_ds binary tree

[Xi Ruoyao via Libstdc++-cvs]

https://gcc.gnu.org/g:6740732a659f9bef523f872c633d5477e8dc349c

commit r16-770-g6740732a659f9bef523f872c633d5477e8dc349c
Author: Xℹ Ruoyao 
Date:   Fri Jul 10 20:10:52 2020 +0800

libstdc++: remove two redundant statements in pb_ds binary tree

libstdc++-v3/ChangeLog:

* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
(insert_leaf_new, insert_imp_empty): remove redundant statements.

Diff:
---
 .../include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp| 2 --
 1 file changed, 2 deletions(-)

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 e6e954dc29c8..b8f5014838c2 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);

[gcc r16-771] libstdc++: maintain subtree size in pb_ds binary search trees

[Xi Ruoyao via Libstdc++-cvs]

https://gcc.gnu.org/g:2e27df6cbd05a3ee742434b7f50dbff5f363b487

commit r16-771-g2e27df6cbd05a3ee742434b7f50dbff5f363b487
Author: Xℹ Ruoyao 
Date:   Fri Jul 10 20:58:04 2020 +0800

libstdc++: maintain subtree size in pb_ds binary search trees

libstdc++-v3/ChangeLog:

* include/ext/pb_ds/detail/rb_tree_map_/node.hpp
(rb_tree_node_::size_type): New typedef.
(rb_tree_node_::m_subtree_size): New field.
* include/ext/pb_ds/detail/splay_tree_/node.hpp
(splay_tree_node_::size_type): New typedef.
(splay_tree_node_::m_subtree_size): New field.
* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
(PB_DS_BIN_TREE_NAME::update_subtree_size): Declare new member
function.
* include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
(update_subtree_size): Define.
(apply_update, update_to_top): Call update_subtree_size.

Diff:
---
 .../detail/bin_search_tree_/bin_search_tree_.hpp   |  3 +++
 .../detail/bin_search_tree_/rotate_fn_imps.hpp | 31 +++---
 .../include/ext/pb_ds/detail/rb_tree_map_/node.hpp |  8 ++
 .../include/ext/pb_ds/detail/splay_tree_/node.hpp  |  8 ++
 4 files changed, 46 insertions(+), 4 deletions(-)

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 6088709998a3..a8c73b55b89d 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
@@ -304,6 +304,9 @@ namespace __gnu_pbds
   inline void
   rotate_parent(node_pointer);
 
+  inline void
+  update_subtree_size(node_pointer);
+
   inline void
   apply_update(node_pointer, null_node_update_pointer);
 
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 069b17f08de2..8cadce2349bd 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
@@ -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(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/rb_tree_map_/node.hpp 
b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
index f229be7342c6..3803ddb19c5d 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_typem_subtree_size;
   value_type   m_value;
   bool m_red;
   metadata_typem_metadata;
@@ -100,6 +104,9 @@ namespace __gnu_pbds
   typedef Value_Type   value_type;
   typedef null_typemetadata_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;
+ 

[gcc r16-772] libstdc++: use maintained size when split pb_ds binary search trees

[Xi Ruoyao via Libstdc++-cvs]

https://gcc.gnu.org/g:36c20fee22d40c6d25f52e929b42f5eab62cb1eb

commit r16-772-g36c20fee22d40c6d25f52e929b42f5eab62cb1eb
Author: Xℹ Ruoyao 
Date:   Fri Jul 10 21:38:09 2020 +0800

libstdc++: use maintained size when split pb_ds binary search trees

libstdc++-v3/ChangeLog:

PR libstdc++/81806
* include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
(split_finish): Use maintained size, instead of calling
std::distance.

Diff:
---
 .../include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp  | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

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 0c1b26fa9e2d..a2a57757a046 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))