From 75d359f75944354ab1e7fcbf9afafd46e868fb37 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 15 Mar 2017 20:11:48 +0000 Subject: [PATCH] PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2017-03-15  Xi Ruoyao   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 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. From-SVN: r246173 --- libstdc++-v3/ChangeLog | 20 ++++++++ .../detail/binary_heap_/binary_heap_.hpp | 21 ++------ .../detail/binary_heap_/insert_fn_imps.hpp | 1 - .../priority_queue_binary_heap-62045.cc | 51 +++++++++++++++++++ .../ext/pb_ds/regression/priority_queues.cc | 2 +- 5 files changed, 75 insertions(+), 20 deletions(-) create mode 100644 libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 2e6e52fa74a..59976bd4b74 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,23 @@ +2017-03-15  Xi Ruoyao   + + 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 + + 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. + 2017-03-15 Jonathan Wakely * acinclude.m4 (GLIBCXX_CHECK_S_ISREG_OR_S_IFREG): Fix typo in 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 2755f061406..f653a1e4b9e 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(*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(*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(*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(*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 f82dd52de3e..d21fe3c3070 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 00000000000..a61d36f67b3 --- /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 +// . + +// { dg-do run } + +#include +#include + +int count = 0; + +struct less +{ + bool operator()(int i, int j) const + { + ++count; + return i < j; + } +}; + +void +test01() +{ + __gnu_pbds::priority_queue 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 4a1b34fce80..6b27ac42fcc 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, binary_heap_tag> c; -- 2.30.2