From patchwork Fri Sep 12 13:34:52 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 388646 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 6E20B1400A0 for ; Fri, 12 Sep 2014 23:35:06 +1000 (EST) 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=T9qqFecIWeW7z9882e8g42vJocf1d4/mt5Lce7lAAgs71fsheMUla v3HJEGe25hYmHXADoUUAvkQ6eWzVU/Z/z3dArwxWGtvrp8tmYBr25LK/YLiFhBtO KmP8s8R8Rg4iFzKqe3OB5EWGjPqBkkqMQ+NG5Q7cpTSEThPNJQjgxY= 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=kHYgI4FUY+oQtQU7h7PBr/jBkbs=; b=IRMTQ4J1T8KU/77yk+IJ N+4NcTxmKkxGiC3+X4+yTLxf1r7DUL7m+tUwu0Nb/0nECaOcK5F7G58Uocp/9lax uIshTqcYL98zzFJzjwkDaQ7jheHe7+c3iNMh/IvCvRDawO4Nx8e/eAJzT4JMrlpm 0LR8wiqfVGDXbsRKtntM+Vo= Received: (qmail 3797 invoked by alias); 12 Sep 2014 13:34:59 -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 3778 invoked by uid 89); 12 Sep 2014 13:34:58 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.2 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 12 Sep 2014 13:34:57 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s8CDYs6K031059 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Fri, 12 Sep 2014 09:34:55 -0400 Received: from localhost (ovpn-116-77.ams2.redhat.com [10.36.116.77]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s8CDYr6U021664; Fri, 12 Sep 2014 09:34:53 -0400 Date: Fri, 12 Sep 2014 14:34:52 +0100 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [patch] libstdc++/59603 Prevent self-swapping in random_shuffle Message-ID: <20140912133452.GN22778@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) Swapping an object with itself is pointless, and asserts in debug mode (but we should probably remove that check from debug mode, since it can happen in reasonable code). Tested x86_64-linux, committed to trunk. I think this makes sense for the branches too, so will backport it soon. commit 0a25b348c511172bd53c5fbca35942cc6c362e8b Author: redi Date: Fri Sep 12 13:30:35 2014 +0000 PR libstdc++/59603 * include/bits/stl_algo.h (random_shuffle): Prevent self-swapping. * testsuite/25_algorithms/random_shuffle/59603.cc: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@215219 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 4c6ca8a..f2dfc20 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -4430,7 +4430,13 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO if (__first != __last) for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) - std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1))); + { + // XXX rand() % N is not uniformly distributed + _RandomAccessIterator __j = __first + + std::rand() % ((__i - __first) + 1); + if (__i != __j) + std::iter_swap(__i, __j); + } } /** @@ -4464,7 +4470,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO if (__first == __last) return; for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) - std::iter_swap(__i, __first + __rand((__i - __first) + 1)); + { + _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); + if (__i != __j) + std::iter_swap(__i, __j); + } } diff --git a/libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc b/libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc new file mode 100644 index 0000000..7b179ac --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc @@ -0,0 +1,34 @@ +// Copyright (C) 2014 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-options "-std=gnu++11" } +// { dg-require-debug-mode "" } + +// libstdc++/59603 + +#include +#include + +struct C { + std::vector v; + C (int a) : v{a} {}; +}; + +int main () { + std::vector cs { {1}, {2}, {3}, {4} }; + std::random_shuffle(cs.begin(), cs.end()); +}