diff options
author | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2014-06-14 01:54:45 +0000 |
---|---|---|
committer | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2014-06-14 01:54:45 +0000 |
commit | 9d6b7aede9c20ff46290d9d08027dc8a025f0e78 (patch) | |
tree | 32ed149a35735e670a0bf61e2fd7ba96d2cf7d15 | |
parent | 02725fb682c5653142d7e4b5fca86e12e9359ef5 (diff) | |
download | ruby-9d6b7aede9c20ff46290d9d08027dc8a025f0e78.tar.gz |
array.c: non-recursive permute0
* array.c (permute0): remove recursion, by looping with indexes
stored in `p`. [ruby-core:63103] [Bug #9932]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46426 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 5 | ||||
-rw-r--r-- | array.c | 47 | ||||
-rw-r--r-- | test/ruby/test_array.rb | 7 |
3 files changed, 40 insertions, 19 deletions
@@ -1,3 +1,8 @@ +Sat Jun 14 10:53:28 2014 Nobuyoshi Nakada <nobu@ruby-lang.org> + + * 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@ruby-lang.org> * string.c (rb_str_resize): update capa only when buffer get @@ -4742,8 +4742,7 @@ yield_indexed_values(const VALUE values, const long r, const long *const p) } /* - * 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, const long r, const long *const p) * 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, VALUE ary) } } 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; diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb index a3d7163605..732a8ba44e 100644 --- a/test/ruby/test_array.rb +++ b/test/ruby/test_array.rb @@ -1748,6 +1748,13 @@ class TestArray < Test::Unit::TestCase 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 |