From 4802149e44ac616ac50cd7a4315b5933f4a89b19 Mon Sep 17 00:00:00 2001 From: nobu Date: Sat, 14 Jun 2014 01:55:07 +0000 Subject: 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 --- ChangeLog | 5 ++++- array.c | 31 ++++++++++++++++++------------- test/ruby/test_array.rb | 6 ++++++ 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 +Sat Jun 14 10:53:49 2014 Nobuyoshi Nakada + + * 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 * [0..n-1]. * * 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 -- cgit v1.2.3