diff options
-rw-r--r-- | ChangeLog | 6 | ||||
-rw-r--r-- | ext/-test-/st/numhash/numhash.c | 4 | ||||
-rw-r--r-- | ext/tk/tkutil/tkutil.c | 9 | ||||
-rw-r--r-- | hash.c | 5 | ||||
-rw-r--r-- | include/ruby/st.h | 1 | ||||
-rw-r--r-- | st.c | 97 | ||||
-rw-r--r-- | test/-ext-/st/test_numhash.rb | 13 |
7 files changed, 112 insertions, 23 deletions
@@ -1,4 +1,8 @@ -Sat Mar 10 23:52:03 2012 Nobuyoshi Nakada <nobu@ruby-lang.org> +Sat Mar 10 23:52:16 2012 Nobuyoshi Nakada <nobu@ruby-lang.org> + + * st.c: add st_foreach_check for fixing iteration over packed table + and st_delete_safe. patched by Sokolov Yura at + https://github.com/ruby/ruby/pull/84 * st.c: fix packed num_entries on delete_safe. patched by Sokolov Yura at https://github.com/ruby/ruby/pull/84 diff --git a/ext/-test-/st/numhash/numhash.c b/ext/-test-/st/numhash/numhash.c index 9b7df3844e..599678dde1 100644 --- a/ext/-test-/st/numhash/numhash.c +++ b/ext/-test-/st/numhash/numhash.c @@ -54,7 +54,9 @@ numhash_i(st_data_t key, st_data_t value, st_data_t arg, int error) static VALUE numhash_each(VALUE self) { - return st_foreach((st_table *)DATA_PTR(self), numhash_i, self) ? Qtrue : Qfalse; + st_table *table = DATA_PTR(self); + st_data_t data = (st_data_t)self; + return st_foreach_check(table, numhash_i, data, data) ? Qtrue : Qfalse; } static int diff --git a/ext/tk/tkutil/tkutil.c b/ext/tk/tkutil/tkutil.c index 09ad7ce143..956c6737c9 100644 --- a/ext/tk/tkutil/tkutil.c +++ b/ext/tk/tkutil/tkutil.c @@ -266,7 +266,6 @@ to_strkey(key, value, hash) VALUE value; VALUE hash; { - if (key == Qundef) return ST_CONTINUE; rb_hash_aset(hash, rb_funcall(key, ID_to_s, 0, 0), value); return ST_CHECK; } @@ -280,7 +279,7 @@ tk_symbolkey2str(self, keys) if NIL_P(keys) return new_keys; keys = rb_convert_type(keys, T_HASH, "Hash", "to_hash"); - st_foreach(RHASH_TBL(keys), to_strkey, new_keys); + st_foreach_check(RHASH_TBL(keys), to_strkey, new_keys, Qundef); return new_keys; } @@ -653,7 +652,6 @@ push_kv(key, val, args) ary = RARRAY_PTR(args)[0]; - if (key == Qundef) return ST_CONTINUE; #if 0 rb_ary_push(ary, key2keyname(key)); if (val != TK_None) rb_ary_push(ary, val); @@ -676,7 +674,7 @@ hash2kv(hash, ary, self) volatile VALUE dst = rb_ary_new2(2 * RHASH_SIZE(hash)); volatile VALUE args = rb_ary_new3(2, dst, self); - st_foreach(RHASH_TBL(hash), push_kv, args); + st_foreach_check(RHASH_TBL(hash), push_kv, args, Qundef); if (NIL_P(ary)) { return dst; @@ -695,7 +693,6 @@ push_kv_enc(key, val, args) ary = RARRAY_PTR(args)[0]; - if (key == Qundef) return ST_CONTINUE; #if 0 rb_ary_push(ary, key2keyname(key)); if (val != TK_None) { @@ -721,7 +718,7 @@ hash2kv_enc(hash, ary, self) volatile VALUE dst = rb_ary_new2(2 * RHASH_SIZE(hash)); volatile VALUE args = rb_ary_new3(2, dst, self); - st_foreach(RHASH_TBL(hash), push_kv_enc, args); + st_foreach_check(RHASH_TBL(hash), push_kv_enc, args, Qundef); if (NIL_P(ary)) { return dst; @@ -116,7 +116,6 @@ foreach_safe_i(st_data_t key, st_data_t value, struct foreach_safe_arg *arg) { int status; - if (key == Qundef) return ST_CONTINUE; status = (*arg->func)(key, value, arg->arg); if (status == ST_CONTINUE) { return ST_CHECK; @@ -132,7 +131,7 @@ st_foreach_safe(st_table *table, int (*func)(ANYARGS), st_data_t a) arg.tbl = table; arg.func = (st_foreach_func *)func; arg.arg = a; - if (st_foreach(table, foreach_safe_i, (st_data_t)&arg)) { + if (st_foreach_check(table, foreach_safe_i, (st_data_t)&arg, Qundef)) { rb_raise(rb_eRuntimeError, "hash modified during iteration"); } } @@ -187,7 +186,7 @@ hash_foreach_ensure(VALUE hash) static VALUE hash_foreach_call(struct hash_foreach_arg *arg) { - if (st_foreach(RHASH(arg->hash)->ntbl, hash_foreach_iter, (st_data_t)arg)) { + if (st_foreach_check(RHASH(arg->hash)->ntbl, hash_foreach_iter, (st_data_t)arg, Qundef)) { rb_raise(rb_eRuntimeError, "hash modified during iteration"); } return Qnil; diff --git a/include/ruby/st.h b/include/ruby/st.h index 3c48b3f8d2..c0d5e01b1a 100644 --- a/include/ruby/st.h +++ b/include/ruby/st.h @@ -123,6 +123,7 @@ int st_lookup(st_table *, st_data_t, st_data_t *); int st_get_key(st_table *, st_data_t, st_data_t *); int st_update(st_table *table, st_data_t key, int (*func)(st_data_t key, st_data_t *value, st_data_t arg), st_data_t arg); int st_foreach(st_table *, int (*)(ANYARGS), st_data_t); +int st_foreach_check(st_table *, int (*)(ANYARGS), st_data_t, st_data_t); int st_reverse_foreach(st_table *, int (*)(ANYARGS), st_data_t); void st_add_direct(st_table *, st_data_t, st_data_t); void st_free_table(st_table *); @@ -866,18 +866,19 @@ st_update(st_table *table, st_data_t key, int (*func)(st_data_t key, st_data_t * } int -st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) +st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t never) { st_table_entry *ptr, **last, *tmp; enum st_retval retval; st_index_t i; if (table->entries_packed) { - for (i = 0; i < table->real_entries; i++) { - st_data_t key, val; - key = PKEY(table, i); - val = PVAL(table, i); - retval = (*func)(key, val, arg); + for (i = 0; i < table->real_entries; i++) { + st_data_t key, val; + key = PKEY(table, i); + val = PVAL(table, i); + if (key == never) continue; + retval = (*func)(key, val, arg); if (!table->entries_packed) { FIND_ENTRY(table, ptr, key, i); if (retval == ST_CHECK) { @@ -886,8 +887,11 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) } goto unpacked; } - switch (retval) { + switch (retval) { case ST_CHECK: /* check if hash is modified during iteration */ + if (PKEY(table, i) == never) { + break; + } if (i != find_packed_index(table, key)) { goto deleted; } @@ -898,11 +902,11 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) return 0; case ST_DELETE: remove_packed_entry(table, i); - i--; - break; - } - } - return 0; + i--; + break; + } + } + return 0; } else { ptr = table->head; @@ -910,6 +914,8 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) if (ptr != 0) { do { + if (ptr->key == never) + goto unpacked_continue; i = ptr->hash % table->num_bins; retval = (*func)(ptr->key, ptr->record, arg); unpacked: @@ -949,6 +955,73 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) return 0; } +int +st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) +{ + st_table_entry *ptr, **last, *tmp; + enum st_retval retval; + st_index_t i; + + if (table->entries_packed) { + for (i = 0; i < table->real_entries; i++) { + st_data_t key, val; + key = PKEY(table, i); + val = PVAL(table, i); + retval = (*func)(key, val, arg); + if (!table->entries_packed) { + FIND_ENTRY(table, ptr, key, i); + if (!ptr) return 0; + goto unpacked; + } + switch (retval) { + case ST_CONTINUE: + break; + case ST_CHECK: + case ST_STOP: + return 0; + case ST_DELETE: + remove_packed_entry(table, i); + i--; + break; + } + } + return 0; + } + else { + ptr = table->head; + } + + if (ptr != 0) { + do { + i = ptr->hash % table->num_bins; + retval = (*func)(ptr->key, ptr->record, arg); + unpacked: + switch (retval) { + case ST_CONTINUE: + ptr = ptr->fore; + break; + case ST_CHECK: + case ST_STOP: + return 0; + case ST_DELETE: + last = &table->bins[ptr->hash % table->num_bins]; + for (; (tmp = *last) != 0; last = &tmp->next) { + if (ptr == tmp) { + tmp = ptr->fore; + *last = ptr->next; + remove_entry(table, ptr); + st_free_entry(ptr); + if (ptr == tmp) return 0; + ptr = tmp; + break; + } + } + } + } while (ptr && table->head); + } + return 0; +} + #if 0 /* unused right now */ int st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) diff --git a/test/-ext-/st/test_numhash.rb b/test/-ext-/st/test_numhash.rb index 53dbfedaaf..24dc87c1d9 100644 --- a/test/-ext-/st/test_numhash.rb +++ b/test/-ext-/st/test_numhash.rb @@ -32,5 +32,18 @@ class Bug::StNumHash assert_equal(up - 1, tbl.size, "delete_safe doesn't change size from #{up} to #{up-1}") end end + + def test_delete_safe_on_iteration + 10.downto(1) do |up| + tbl = Bug::StNumHash.new + 1.upto(up){|i| tbl[i] = i} + assert_nothing_raised("delete_safe forces iteration to fail with size #{up}") do + tbl.each do |k, v, t| + assert_equal k, t.delete_safe(k) + true + end + end + end + end end end |