array.c: non-recursive rpermute0

* array.c (rpermute0): remove recursion, by looping with indexes
  stored in `p`.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46427 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

3 files changed, 28 insertions, 14 deletions

diff --git a/ChangeLog b/ChangeLog
index 4a6c9454c3..251bd357a0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,4 +1,7 @@
-Sat Jun 14 10:53:28 2014  Nobuyoshi Nakada  <nobu@ruby-lang.org>
+Sat Jun 14 10:53:49 2014  Nobuyoshi Nakada  <nobu@ruby-lang.org>
+
+	* array.c (rpermute0): remove recursion, by looping with indexes
+	  stored in `p`.
 
 	* array.c (permute0): remove recursion, by looping with indexes
 	  stored in `p`.  [ruby-core:63103] [Bug #9932]
diff --git a/array.c b/array.c
index 73aabb14f8..8322c294f2 100644
--- a/array.c
+++ b/array.c
@@ -4981,7 +4981,7 @@ rb_ary_combination(VALUE ary, VALUE num)
 }
 
 /*
- * Recursively compute repeated permutations of +r+ elements of the set
+ * Compute repeated permutations of +r+ elements of the set
  * <code>[0..n-1]</code>.
  *
  * When we have a complete repeated permutation of array indexes, copy the
@@ -4990,23 +4990,28 @@ rb_ary_combination(VALUE ary, VALUE num)
  * n: the size of the set
  * r: the number of elements in each permutation
  * p: the array (of size r) that we're filling in
- * index: what index we're filling in now
  * values: the Ruby array that holds the actual values to permute
  */
 static void
-rpermute0(long n, long r, long *p, long index, VALUE values)
+rpermute0(const long n, const long r, long *const p, const VALUE values)
 {
-    long i;
-    for (i = 0; i < n; i++) {
-	p[index] = i;
-	if (index < r-1) {              /* if not done yet */
-	    rpermute0(n, r, p, index+1, values); /* recurse */
+    long i = 0, index = 0;
+
+    p[index] = i;
+    for (;;) {
+	if (++index < r-1) {
+	    p[index] = i = 0;
+	    continue;
 	}
-	else {
+	for (i = 0; i < n; ++i) {
+	    p[index] = i;
 	    if (!yield_indexed_values(values, r, p)) {
 		rb_raise(rb_eRuntimeError, "repeated permute reentered");
 	    }
 	}
+	do {
+	    if (index <= 0) return;
+	} while ((i = ++p[--index]) >= n);
     }
 }
 
@@ -5069,13 +5074,13 @@ rb_ary_repeated_permutation(VALUE ary, VALUE num)
 	}
     }
     else {             /* this is the general case */
-	volatile VALUE t0 = tmpbuf(r, sizeof(long));
-	long *p = (long*)RSTRING_PTR(t0);
+	volatile VALUE t0;
+	long *p = ALLOCV_N(long, t0, r * sizeof(long));
 	VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
 	RBASIC_CLEAR_CLASS(ary0);
 
-	rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
-	tmpbuf_discard(t0);
+	rpermute0(n, r, p, ary0); /* compute and yield repeated permutations */
+	ALLOCV_END(t0);
 	RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
     }
     return ary;
diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb
index 732a8ba44e..b9b2d5f88b 100644
--- a/test/ruby/test_array.rb
+++ b/test/ruby/test_array.rb
@@ -1780,6 +1780,12 @@ class TestArray < Test::Unit::TestCase
 
     a = @cls[0, 1, 2, 3, 4][1, 4].repeated_permutation(2)
     assert_empty(a.reject {|x| !x.include?(0)})
+
+    assert_separately([], <<-"end;") #    do
+      assert_nothing_raised(SystemStackError) do
+        assert_equal(:ok, Array.new(100_000, nil).repeated_permutation(500_000) {break :ok})
+      end
+    end;
   end
 
   def test_repeated_combination