PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap
authorJonathan Wakely <redi@gcc.gnu.org>
Wed, 15 Mar 2017 20:11:48 +0000 (20:11 +0000)
committerJonathan Wakely <redi@gcc.gnu.org>
Wed, 15 Mar 2017 20:11:48 +0000 (20:11 +0000)
commit75d359f75944354ab1e7fcbf9afafd46e868fb37
tree378a37f9de23aceafda17406a7f093e8bfdf74d5
parent7fb22ebe018682ebcddc069c0ba39d82c3e91eb8
PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap

2017-03-15  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.

2017-03-15  Jonathan Wakely  <jwakely@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.

From-SVN: r246173
libstdc++-v3/ChangeLog
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc [new file with mode: 0644]
libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc