nobu	2014-06-14 10:54:45 +0900 (Sat, 14 Jun 2014)

  New Revision: 46426

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=46426

  Log:
    array.c: non-recursive permute0
    
    * array.c (permute0): remove recursion, by looping with indexes
      stored in `p`.  [ruby-core:63103] [Bug #9932]

  Modified files:
    trunk/ChangeLog
    trunk/array.c
    trunk/test/ruby/test_array.rb
Index: array.c
===================================================================
--- array.c	(revision 46425)
+++ array.c	(revision 46426)
@@ -4742,8 +4742,7 @@ yield_indexed_values(const VALUE values, https://github.com/ruby/ruby/blob/trunk/array.c#L4742
 }
 
 /*
- * Recursively compute permutations of +r+ elements of the set
- * <code>[0..n-1]</code>.
+ * Compute permutations of +r+ elements of the set <code>[0..n-1]</code>.
  *
  * When we have a complete permutation of array indexes, copy the values
  * at those indexes into a new array and yield that array.
@@ -4751,28 +4750,40 @@ yield_indexed_values(const VALUE values, https://github.com/ruby/ruby/blob/trunk/array.c#L4750
  * 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
  * used: an array of booleans: whether a given index is already used
  * values: the Ruby array that holds the actual values to permute
  */
 static void
-permute0(long n, long r, long *p, long index, char *used, VALUE values)
+permute0(const long n, const long r, long *const p, char *const used, const VALUE values)
 {
-    long i;
-    for (i = 0; i < n; i++) {
-	if (used[i] == 0) {
+    long i = 0, index = 0;
+
+    for (;;) {
+	const char *const unused = memchr(&used[i], 0, n-i);
+	if (!unused) {
+	    if (!index) break;
+	    i = p[--index];                /* pop index */
+	    used[i++] = 0;                 /* index unused */
+	}
+	else {
+	    i = unused - used;
 	    p[index] = i;
+	    used[i] = 1;                   /* mark index used */
+	    ++index;
 	    if (index < r-1) {             /* if not done yet */
-		used[i] = 1;               /* mark index used */
-		permute0(n, r, p, index+1, /* recurse */
-			 used, values);
-		used[i] = 0;               /* index unused */
+		p[index] = i = 0;
+		continue;
 	    }
-	    else {
+	    for (i = 0; i < n; ++i) {
+		if (used[i]) continue;
+		p[index] = i;
 		if (!yield_indexed_values(values, r, p)) {
 		    rb_raise(rb_eRuntimeError, "permute reentered");
 		}
 	    }
+	    i = p[--index];                /* pop index */
+	    used[i] = 0;                   /* index unused */
+	    p[index] = ++i;
 	}
     }
 }
@@ -4867,18 +4878,16 @@ rb_ary_permutation(int argc, VALUE *argv https://github.com/ruby/ruby/blob/trunk/array.c#L4878
 	}
     }
     else {             /* this is the general case */
-	volatile VALUE t0 = tmpbuf(r,sizeof(long));
-	long *p = (long*)RSTRING_PTR(t0);
-	volatile VALUE t1 = tmpbuf(n,sizeof(char));
-	char *used = (char*)RSTRING_PTR(t1);
+	volatile VALUE t0;
+	long *p = (long*)ALLOCV(t0, r*sizeof(long)+n*sizeof(char));
+	char *used = (char*)(p + r);
 	VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
 	RBASIC_CLEAR_CLASS(ary0);
 
 	MEMZERO(used, char, n); /* initialize array */
 
-	permute0(n, r, p, 0, used, ary0); /* compute and yield permutations */
-	tmpbuf_discard(t0);
-	tmpbuf_discard(t1);
+	permute0(n, r, p, used, ary0); /* compute and yield permutations */
+	ALLOCV_END(t0);
 	RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
     }
     return ary;
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 46425)
+++ ChangeLog	(revision 46426)
@@ -1,3 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Sat Jun 14 10:53:28 2014  Nobuyoshi Nakada  <nobu@r...>
+
+	* array.c (permute0): remove recursion, by looping with indexes
+	  stored in `p`.  [ruby-core:63103] [Bug #9932]
+
 Sat Jun 14 10:52:15 2014  Nobuyoshi Nakada  <nobu@r...>
 
 	* string.c (rb_str_resize): update capa only when buffer get
Index: test/ruby/test_array.rb
===================================================================
--- test/ruby/test_array.rb	(revision 46425)
+++ test/ruby/test_array.rb	(revision 46426)
@@ -1748,6 +1748,13 @@ class TestArray < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L1748
 
     bug3708 = '[ruby-dev:42067]'
     assert_equal(b, @cls[0, 1, 2, 3, 4][1, 4].permutation.to_a, bug3708)
+
+    bug9932 = '[ruby-core:63103] [Bug #9932]'
+    assert_separately([], <<-"end;") #    do
+      assert_nothing_raised(SystemStackError, "#{bug9932}") do
+        assert_equal(:ok, Array.new(100_000, nil).permutation {break :ok})
+      end
+    end;
   end
 
   def test_repeated_permutation

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/