On 10/03/17 11:54 +0000, Jonathan Wakely wrote:
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!
I've committed the patch, with a new test to verify that we don't do
too many comparisons on insertion. Thanks again.
Tested powerpc64le-linux, committed to trunk. Backports to follow.
commit e81a1a7754ec90d3ecd3478e397d554d69c81d04
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Wed Mar 15 19:01:42 2017 +0000
PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap
2017-03-15????Xi Ruoyao????<r...@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.
2017-03-15 Jonathan Wakely <jwak...@redhat.com>
PR libstdc++/62045
* testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc:
New test.
* testsuite/ext/pb_ds/regression/priority_queues.cc: Fix copy&paste
error in comment.
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..d21fe3c 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
@@ -103,7 +103,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
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc
new file mode 100644
index 0000000..a61d36f
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc
@@ -0,0 +1,51 @@
+// Copyright (C) 2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <ext/pb_ds/priority_queue.hpp>
+#include <testsuite_hooks.h>
+
+int count = 0;
+
+struct less
+{
+ bool operator()(int i, int j) const
+ {
+ ++count;
+ return i < j;
+ }
+};
+
+void
+test01()
+{
+ __gnu_pbds::priority_queue<int, less, __gnu_pbds::binary_heap_tag> c;
+ c.push(1);
+ c.push(2);
+ c.push(3);
+ c.push(4);
+ count = 0;
+ c.push(5);
+ VERIFY( count < c.size() );
+}
+
+int
+main()
+{
+ test01();
+}
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
index 4a1b34f..6b27ac4 100644
--- a/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
+++ b/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
@@ -108,7 +108,7 @@ priority_queue_link_regression_test_0()
{
/*
- * Perform operations on a binomial-heap queue.
+ * Perform operations on a binary-heap queue.
*/
cout << "Binary heap" << endl;
__gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c;
