summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog6
-rw-r--r--ext/-test-/st/numhash/numhash.c4
-rw-r--r--ext/tk/tkutil/tkutil.c9
-rw-r--r--hash.c5
-rw-r--r--include/ruby/st.h1
-rw-r--r--st.c97
-rw-r--r--test/-ext-/st/test_numhash.rb13
7 files changed, 112 insertions, 23 deletions
diff --git a/ChangeLog b/ChangeLog
index bc06dbc175..b4a143f604 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -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;
diff --git a/hash.c b/hash.c
index dbd7082540..560b32e29a 100644
--- a/hash.c
+++ b/hash.c
@@ -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 *);
diff --git a/st.c b/st.c
index d4a0a81919..9fb29f6201 100644
--- a/st.c
+++ b/st.c
@@ -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
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-15 01:37:30 +0000