diff mbox

libstdc++/59603 Prevent self-swapping in random_shuffle

Message ID 20140912133452.GN22778@redhat.com
State New
Headers show

Commit Message

Jonathan Wakely Sept. 12, 2014, 1:34 p.m. UTC 
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.

Comments

Jonathan Wakely Oct. 1, 2014, 12:35 p.m. UTC | #1 
On 12/09/14 14:34 +0100, Jonathan Wakely wrote:
>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.

Now committed to the 4.9 branch (without the comment Chris didn't
like).

>    	PR libstdc++/59603
>    	* include/bits/stl_algo.h (random_shuffle): Prevent self-swapping.
>    	* testsuite/25_algorithms/random_shuffle/59603.cc: New.
Jonathan Wakely Dec. 6, 2014, 10:04 p.m. UTC | #2 
On 1 October 2014 at 13:35, Jonathan Wakely <jwakely@redhat.com> wrote:
> On 12/09/14 14:34 +0100, Jonathan Wakely wrote:
>>
>> 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.
>
>
> Now committed to the 4.9 branch (without the comment Chris didn't
> like).
>
>>         PR libstdc++/59603
>>         * include/bits/stl_algo.h (random_shuffle): Prevent self-swapping.
>>         * testsuite/25_algorithms/random_shuffle/59603.cc: New.
>
>
>

And also to the 4.8 branch.
diff mbox

Patch

commit 0a25b348c511172bd53c5fbca35942cc6c362e8b
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
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
+// <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());
+}