diff options
author | Jonathan Wakely <jwakely@redhat.com> | 2014-09-12 14:30:35 +0100 |
---|---|---|
committer | Jonathan Wakely <redi@gcc.gnu.org> | 2014-09-12 14:30:35 +0100 |
commit | bc5022d0114c306684f4f21c91716fb91c83fdc6 (patch) | |
tree | b6136e609c67d0b85b3b2a73e97b8141cf1d97c1 | |
parent | 139c9e3b9b08cdeedbf9191c792d220499638894 (diff) | |
download | gcc-bc5022d0114c306684f4f21c91716fb91c83fdc6.tar.gz |
re PR libstdc++/59603 (std::random_shuffle tries to swap element with itself)
PR libstdc++/59603
* include/bits/stl_algo.h (random_shuffle): Prevent self-swapping.
* testsuite/25_algorithms/random_shuffle/59603.cc: New.
From-SVN: r215219
-rw-r--r-- | libstdc++-v3/ChangeLog | 6 | ||||
-rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 14 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/random_shuffle/59603.cc | 34 |
3 files changed, 52 insertions, 2 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 29fdb5662f1..afcba385f21 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,9 @@ +2014-09-12 Jonathan Wakely <jwakely@redhat.com> + + PR libstdc++/59603 + * include/bits/stl_algo.h (random_shuffle): Prevent self-swapping. + * testsuite/25_algorithms/random_shuffle/59603.cc: New. + 2014-09-11 Jonathan Wakely <jwakely@redhat.com> PR libstdc++/63219 diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 4c6ca8a7268..f2dfc208ce5 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 00000000000..7b179ac19a0 --- /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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } +// { dg-require-debug-mode "" } + +// libstdc++/59603 + +#include <algorithm> +#include <vector> + +struct C { + std::vector<int> v; + C (int a) : v{a} {}; +}; + +int main () { + std::vector<C> cs { {1}, {2}, {3}, {4} }; + std::random_shuffle(cs.begin(), cs.end()); +} |