diff mbox

Remove __gnu_pbds::detail::binary_heap::is_heap (PR libstdc++/62045) [resend]

Message ID 1489145808.1763.21.camel@stu.xidian.edu.cn
State New
Headers show

Commit Message

Xi Ruoyao March 10, 2017, 11:36 a.m. UTC 
Hi,

This was resent to be in both libstdc++ and gcc-patches list.

The ill-formed checking in binary_heap::push_heap has made it
O(n). Remove this checking.

Since assert_valid also checks if (*this) is a legal heap, we can
remove is_heap and the assertions using it completely.

Bootstrapped and tested on x86_64-linux-gnu.

2017-03-09  Xi Ruoyao  <ryxi@stu.xidian.edu.cn>

	PR libstdc++/62045:
	* include/ext/pb_ds/qdetail/binary_heap_/binary_heap_.hpp
	  (is_heap): Remove.
	  (push_heap): Remove the wrong checking using is_heap.
	  (make_heap): Remove the assertion using is_heap.
	* include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
	  (modify): Ditto.
	  (resize_for_insert_if_needed): Add PB_DS_ASSERT_VALID after
	  calling make_heap.
---
 .../ext/pb_ds/detail/binary_heap_/binary_heap_.hpp  | 21 +++------------------
 .../pb_ds/detail/binary_heap_/insert_fn_imps.hpp    |  2 +-
 2 files changed, 4 insertions(+), 19 deletions(-)

Comments

Jonathan Wakely March 10, 2017, 11:54 a.m. UTC | #1 
On 10/03/17 19:36 +0800, Xi Ruoyao wrote:
>Hi,
>
>This was resent to be in both libstdc++ and gcc-patches list.

Thanks.

>The ill-formed checking in binary_heap::push_heap has made it
>O(n). Remove this checking.

The checking certainly looks redundant, I wouldn't say ill-formed
though (that's a formal term in the C++ standard meaning the code
isn't valid C++).

>Since assert_valid also checks if (*this) is a legal heap, we can
>remove is_heap and the assertions using it completely.

The patch looks good, and since you're just removing code I don't
think we need a copyright assignment. I'll get this applied to the
active branches, thanks!
diff mbox

Patch

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/libstdc++-
v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
index 2755f06..f653a1e 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
@@ -266,20 +266,14 @@  namespace __gnu_pbds
 	const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
 	entry_pointer end = m_a_entries + m_size;
 	std::make_heap(m_a_entries, end, m_cmp);
-	_GLIBCXX_DEBUG_ASSERT(is_heap());
       }
 
       void
       push_heap()
       {
-	if (!is_heap())
-	  make_heap();
-	else
-	  {
-	    const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
-	    entry_pointer end = m_a_entries + m_size;
-	    std::push_heap(m_a_entries, end, m_cmp);
-	  }
+	const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
+	entry_pointer end = m_a_entries + m_size;
+	std::push_heap(m_a_entries, end, m_cmp);
       }
 
       void
@@ -290,15 +284,6 @@  namespace __gnu_pbds
 	std::pop_heap(m_a_entries, end, m_cmp);
       }
 
-      bool
-      is_heap()
-      {
-	const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this);
-	entry_pointer end = m_a_entries + m_size;
-	bool p = std::__is_heap(m_a_entries, end, m_cmp);
-	return p;
-      }
-
 #ifdef _GLIBCXX_DEBUG
       void
       assert_valid(const char*, int) const;
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 f82dd52..3b63515 100644
--- 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
@@ -92,6 +92,7 @@  resize_for_insert_if_needed()
   m_actual_size = new_size;
   m_a_entries = new_entries;
   make_heap();
+  PB_DS_ASSERT_VALID((*this))
 }
 
 PB_DS_CLASS_T_DEC
@@ -103,7 +104,6 @@  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