re PR libstdc++/37144 (A bug in include/ext/pb_ds/detail/pat_trie_/constructors_destr...

[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / detail / binary_heap_ / insert_fn_imps.hpp

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
index c6c41e572645d8d1e8ba0d3adb6f23ade3b83475..1e1ed969e723dbf1e32bc0623d552998cb3ab8be 100644 (file)
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
@@ -34,7 +34,7 @@
 // warranty.
 
 /**
- * @file insert_fn_imps.hpp
+ * @file binary_heap_/insert_fn_imps.hpp
  * Contains an implementation class for a binary_heap.
  */
 
@@ -45,8 +45,7 @@ push(const_reference r_val)
 {
   PB_DS_ASSERT_VALID((*this))
   insert_value(r_val, s_no_throw_copies_ind);
-  std::push_heap(m_a_entries, m_a_entries + m_size, 
-                static_cast<entry_cmp&>(*this));
+  push_heap();
   PB_DS_ASSERT_VALID((*this))
   return point_iterator(m_a_entries);
 }
@@ -57,7 +56,6 @@ PB_DS_CLASS_C_DEC::
 insert_value(value_type val, true_type)
 {
   resize_for_insert_if_needed();
-
   m_a_entries[m_size++] = val;
 }
 
@@ -74,15 +72,6 @@ insert_value(const_reference r_val, false_type)
   m_a_entries[m_size++] = p_new;
 }
 
-PB_DS_CLASS_T_DEC
-inline void
-PB_DS_CLASS_C_DEC::
-insert_entry(entry e)
-{
-  resize_for_insert_if_needed();
-  m_a_entries[m_size++] = e;
-}
-
 PB_DS_CLASS_T_DEC
 inline void
 PB_DS_CLASS_C_DEC::
@@ -94,13 +83,15 @@ resize_for_insert_if_needed()
       return;
     }
 
-  const size_type new_actual_size = resize_policy::get_new_size_for_grow();
-  entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size);
+  const size_type new_size = resize_policy::get_new_size_for_grow();
+  entry_pointer new_entries = s_entry_allocator.allocate(new_size);
   resize_policy::notify_grow_resize();
-  std::copy(m_a_entries, m_a_entries + m_size, a_new_entries);
+
+  std::copy(m_a_entries, m_a_entries + m_size, new_entries);
   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
-  m_actual_size = new_actual_size;
-  m_a_entries = a_new_entries;
+  m_actual_size = new_size;
+  m_a_entries = new_entries;
+  make_heap();
 }
 
 PB_DS_CLASS_T_DEC
@@ -112,6 +103,7 @@ modify(point_iterator it, const_reference r_new_val)
   swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind);
   fix(it.m_p_e);
   PB_DS_ASSERT_VALID((*this))
+  _GLIBCXX_DEBUG_ASSERT(is_heap());
 }
 
 PB_DS_CLASS_T_DEC
@@ -123,13 +115,13 @@ fix(entry_pointer p_e)
   if (i > 0 && entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i]))
     {
       size_type parent_i = parent(i);
-      while (i > 0 
+      while (i > 0
             && entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i]))
-        {
+       {
          std::swap(m_a_entries[i], m_a_entries[parent_i]);
          i = parent_i;
          parent_i = parent(i);
-        }
+       }
 
       PB_DS_ASSERT_VALID((*this))
       return;
@@ -137,29 +129,30 @@ fix(entry_pointer p_e)
 
   while (i < m_size)
     {
-      const size_type left_child_i = left_child(i);
-      const size_type right_child_i = right_child(i);
-      _GLIBCXX_DEBUG_ASSERT(right_child_i > left_child_i);
-      const bool smaller_than_left_child = left_child_i < m_size && 
-       entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child_i]);
-
-      const bool smaller_than_right_child = right_child_i < m_size && 
-       entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child_i]);
-
-      const bool swap_with_r_child = smaller_than_right_child && (!smaller_than_left_child || entry_cmp::operator()(m_a_entries[left_child_i], m_a_entries[right_child_i]));
-
-      const bool swap_with_l_child = !swap_with_r_child && smaller_than_left_child;
-
-      if (swap_with_l_child)
-        {
-         std::swap(m_a_entries[i], m_a_entries[left_child_i]);
-         i = left_child_i;
-        }
-      else if (swap_with_r_child)
-        {
-         std::swap(m_a_entries[i], m_a_entries[right_child_i]);
-         i = right_child_i;
-        }
+      const size_type lchild_i = left_child(i);
+      const size_type rchild_i = right_child(i);
+      _GLIBCXX_DEBUG_ASSERT(rchild_i > lchild_i);
+
+      const bool smaller_than_lchild = lchild_i < m_size &&
+       entry_cmp::operator()(m_a_entries[i], m_a_entries[lchild_i]);
+
+      const bool smaller_than_rchild = rchild_i < m_size &&
+       entry_cmp::operator()(m_a_entries[i], m_a_entries[rchild_i]);
+
+      const bool swap_with_rchild = smaller_than_rchild && (!smaller_than_lchild || entry_cmp::operator()(m_a_entries[lchild_i], m_a_entries[rchild_i]));
+
+      const bool swap_with_lchild = !swap_with_rchild && smaller_than_lchild;
+
+      if (swap_with_lchild)
+       {
+         std::swap(m_a_entries[i], m_a_entries[lchild_i]);
+         i = lchild_i;
+       }
+      else if (swap_with_rchild)
+       {
+         std::swap(m_a_entries[i], m_a_entries[rchild_i]);
+         i = rchild_i;
+       }
       else
        i = m_size;
     }
@@ -169,9 +162,7 @@ PB_DS_CLASS_T_DEC
 inline void
 PB_DS_CLASS_C_DEC::
 swap_value_imp(entry_pointer p_e, value_type new_val, true_type)
-{
-  * p_e = new_val;
-}
+{ *p_e = new_val; }
 
 PB_DS_CLASS_T_DEC
 inline void