From patchwork Thu Feb 14 14:10:31 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1042215 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-496133-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="WbpO/jwo"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 440db85wXFz9sML for ; Fri, 15 Feb 2019 01:10:44 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=USB/9FS2zRHYyeyRK6gc67wfAlvBMWB5hgn5LYp/Vp3jzpkvFRSEX 3OGQtfduGtSpGZ9O3Nd+8n9jQ/I3wKc0Q1XGVBXktTF0jOubZgWEHRsJpdh5x1tq No1jdWYzWOd76CAi2nD9fwhWj3GGi7QH3slXKO8Su+lgZLcnfbWJTY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=xGbXlLU9obd1z6xIOuH690Qhf9s=; b=WbpO/jwo68WYH2pS8Lna wx5bRRrg11hIqWdvzDDQqZ9yRQt2myjPhu43ReDgvSTLXQY+c6tbOoTt+nJLArz+ IAqi5GXf+htlayySOUuP9ehG+8blhhvVhMACyVHcJ7ZJl9XhgiMx2RCVbpBqXIsa irSJVy3gxi4benocHSl4ZeI= Received: (qmail 7734 invoked by alias); 14 Feb 2019 14:10:37 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 7620 invoked by uid 89); 14 Feb 2019 14:10:36 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_LAZY_DOMAIN_SECURITY, KAM_SHORT, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=heap X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 14 Feb 2019 14:10:34 +0000 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id CA2E481F25; Thu, 14 Feb 2019 14:10:32 +0000 (UTC) Received: from localhost (unknown [10.33.36.88]) by smtp.corp.redhat.com (Postfix) with ESMTP id 372455F702; Thu, 14 Feb 2019 14:10:32 +0000 (UTC) Date: Thu, 14 Feb 2019 14:10:31 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] LWG 2537 fix priority_queue constructors to establish invariant Message-ID: <20190214141031.GA25529@redhat.com> MIME-Version: 1.0 Content-Disposition: inline X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.10.1 (2018-07-13) This change is safe to make now (in stage 4), because the constructors are currently incorrect and unusable (unless the supplied container already contains a heap, in which case the new make_heap calls are redundant but harmless). * doc/xml/manual/intro.xml: Document LWG 2537 status. * include/bits/stl_queue.h (priority_queue(const Compare&, const Container&, const Alloc&)) (priority_queue(const Compare&, Container&&, const Alloc&)): Call make_heap. * testsuite/23_containers/priority_queue/dr2537.cc: New test. Tested powerpc64le-linux, committed to trunk. commit 00eb831064ca6c6cfff48b2f3f8b1217b0c5d527 Author: Jonathan Wakely Date: Thu Feb 14 10:52:56 2019 +0000 LWG 2537 fix priority_queue constructors to establish invariant This change is safe to make now (in stage 4), because the constructors are currently incorrect and unusable (unless the supplied container already contains a heap, in which case the new make_heap calls are redundant but harmless). * doc/xml/manual/intro.xml: Document LWG 2537 status. * include/bits/stl_queue.h (priority_queue(const Compare&, const Container&, const Alloc&)) (priority_queue(const Compare&, Container&&, const Alloc&)): Call make_heap. * testsuite/23_containers/priority_queue/dr2537.cc: New test. diff --git a/libstdc++-v3/doc/xml/manual/intro.xml b/libstdc++-v3/doc/xml/manual/intro.xml index 2a3231f4eb4..656e32b00aa 100644 --- a/libstdc++-v3/doc/xml/manual/intro.xml +++ b/libstdc++-v3/doc/xml/manual/intro.xml @@ -1127,6 +1127,14 @@ requirements of the license of GCC. Add static assertions to enforce the requirement. + 2566: + Constructors for priority_queue taking allocators + should call make_heap + + + Call make_heap. + + 2583: There is no way to supply an allocator for basic_string(str, pos) diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h index 1eb56810edc..dd1d5d9727a 100644 --- a/libstdc++-v3/include/bits/stl_queue.h +++ b/libstdc++-v3/include/bits/stl_queue.h @@ -520,14 +520,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION priority_queue(const _Compare& __x, const _Alloc& __a) : c(__a), comp(__x) { } + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 2537. Constructors [...] taking allocators should call make_heap template> priority_queue(const _Compare& __x, const _Sequence& __c, const _Alloc& __a) - : c(__c, __a), comp(__x) { } + : c(__c, __a), comp(__x) + { std::make_heap(c.begin(), c.end(), comp); } template> priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) - : c(std::move(__c), __a), comp(__x) { } + : c(std::move(__c), __a), comp(__x) + { std::make_heap(c.begin(), c.end(), comp); } template> priority_queue(const priority_queue& __q, const _Alloc& __a) diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc new file mode 100644 index 00000000000..ecb51780ee5 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc @@ -0,0 +1,50 @@ +// Copyright (C) 2019 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 { target c++11 } } + +#include +#include + +struct Q : std::priority_queue +{ + using priority_queue::priority_queue; + + bool is_heap() const + { return std::is_heap(c.begin(), c.end()); } +}; + +void +test01() +{ + const Q::value_compare cmp; + const Q::container_type c{ 2, 3, 5, 7, 11, 13, 17, 19, 23 }; + const Q::container_type::allocator_type a; + + Q q1(cmp, c, a); + VERIFY( q1.is_heap() ); + + auto c2 = c; + Q q2(cmp, std::move(c2), a); + VERIFY( q2.is_heap() ); +} + +int +main() +{ + test01(); +}