[Bug libstdc++/61217] New: pop_heap can't guarantee At most 2 * log(last - first) comparisons

[Bug libstdc++/61217] New: pop_heap can't guarantee At most 2 * log(last - first) comparisons

[kan.liu.229 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61217

            Bug ID: 61217
           Summary: pop_heap can't guarantee At most 2 * log(last - first)
                    comparisons
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kan.liu.229 at gmail dot com

pop_heap uses __adjust_heap to percolate down the hole. 

Inside __adjust_heap, it uses __value stores the value where was in position
__result(__last). After percolating down the hole, it uses __push_heap to push
back the __value. Process of percolatiing down takes 2 * logN comparasion, and
__push_heap takes another 2 * logN, 4 * logN in total, which excceed the
requirement "2 * log(last - first) comparisons" of standard.

[Bug libstdc++/61217] pop_heap can't guarantee At most 2 * log(last - first) comparisons

[fdumont at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61217

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fdumont at gcc dot gnu.org

--- Comment #1 from François Dumont <fdumont at gcc dot gnu.org> ---
Rather than analysing the code I just add tests to the testsuite validating
number of comparisons done for heap algos. See

https://gcc.gnu.org/ml/libstdc++/2014-10/msg00058.html

and there is no problem with pop_heap.
>From gcc-bugs-return-463603-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Oct 08 20:42:41 2014
Return-Path: <gcc-bugs-return-463603-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 12754 invoked by alias); 8 Oct 2014 20:42:41 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 12708 invoked by uid 48); 8 Oct 2014 20:42:38 -0000
From: "jason at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/63485] [5 Regression] ICE: canonical types differ for identical types A<const wchar_t [3]>::type and const char_type [3]
Date: Wed, 08 Oct 2014 20:42:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: jason at gcc dot gnu.org
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: jason at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 5.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status resolution assigned_to target_milestone
Message-ID: <bug-63485-4-aQURttfex7@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-63485-4@http.gcc.gnu.org/bugzilla/>
References: <bug-63485-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-10/txt/msg00624.txt.bz2
Content-length: 556

https://gcc.gnu.org/bugzilla/show_bug.cgi?idc485

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED
           Assignee|unassigned at gcc dot gnu.org      |jason at gcc dot gnu.org
   Target Milestone|---                         |5.0

--- Comment #3 from Jason Merrill <jason at gcc dot gnu.org> ---
Fixed.

[Bug libstdc++/61217] pop_heap can't guarantee At most 2 * log(last - first) comparisons

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61217

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
If you think there's a bug here please provide a testcase to demonstrate it.