nobu	2014-06-14 10:55:25 +0900 (Sat, 14 Jun 2014)

  New Revision: 46428

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

  Log:
    array.c: non-recursive rcombinate0
    
    * array.c (rcombinate0): remove recursion, by looping with indexes
      stored in `p`.

  Modified files:
    trunk/ChangeLog
    trunk/array.c
    trunk/test/ruby/test_array.rb
Index: array.c
===================================================================
--- array.c	(revision 46427)
+++ array.c	(revision 46428)
@@ -5087,18 +5087,25 @@ rb_ary_repeated_permutation(VALUE ary, V https://github.com/ruby/ruby/blob/trunk/array.c#L5087
 }
 
 static void
-rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
+rcombinate0(const long n, const long r, long *const p, const long rest, const VALUE values)
 {
-    if (rest > 0) {
-	for (; index < n; ++index) {
-	    p[r-rest] = index;
-	    rcombinate0(n, r, p, index, rest-1, values);
+    long i = 0, index = 0;
+
+    p[index] = i;
+    for (;;) {
+	if (++index < r-1) {
+	    p[index] = i;
+	    continue;
 	}
-    }
-    else {
-	if (!yield_indexed_values(values, r, p)) {
-	    rb_raise(rb_eRuntimeError, "repeated combination reentered");
+	for (; i < n; ++i) {
+	    p[index] = i;
+	    if (!yield_indexed_values(values, r, p)) {
+		rb_raise(rb_eRuntimeError, "repeated combination reentered");
+	    }
 	}
+	do {
+	    if (index <= 0) return;
+	} while ((i = ++p[--index]) >= n);
     }
 }
 
@@ -5163,13 +5170,13 @@ rb_ary_repeated_combination(VALUE ary, V https://github.com/ruby/ruby/blob/trunk/array.c#L5170
 	/* yield nothing */
     }
     else {
-	volatile VALUE t0 = tmpbuf(n, sizeof(long));
-	long *p = (long*)RSTRING_PTR(t0);
+	volatile VALUE t0;
+	long *p = ALLOCV_N(long, t0, n);
 	VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
 	RBASIC_CLEAR_CLASS(ary0);
 
-	rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
-	tmpbuf_discard(t0);
+	rcombinate0(len, n, p, n, ary0); /* compute and yield repeated combinations */
+	ALLOCV_END(t0);
 	RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
     }
     return ary;
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 46427)
+++ ChangeLog	(revision 46428)
@@ -1,4 +1,7 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
-Sat Jun 14 10:53:49 2014  Nobuyoshi Nakada  <nobu@r...>
+Sat Jun 14 10:54:08 2014  Nobuyoshi Nakada  <nobu@r...>
+
+	* array.c (rcombinate0): remove recursion, by looping with indexes
+	  stored in `p`.
 
 	* array.c (rpermute0): remove recursion, by looping with indexes
 	  stored in `p`.
Index: test/ruby/test_array.rb
===================================================================
--- test/ruby/test_array.rb	(revision 46427)
+++ test/ruby/test_array.rb	(revision 46428)
@@ -1815,6 +1815,12 @@ class TestArray < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L1815
 
     a = @cls[0, 1, 2, 3, 4][1, 4].repeated_combination(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_combination(500_000) {break :ok})
+      end
+    end;
   end
 
   def test_take

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