[前][次][番号順一覧][スレッド一覧]

ruby-changes:22914

From: nobu <ko1@a...>
Date: Sat, 10 Mar 2012 23:52:34 +0900 (JST)
Subject: [ruby-changes:22914] nobu:r34963 (trunk): * st.c: add st_foreach_check for fixing iteration over packed table

nobu	2012-03-10 23:52:19 +0900 (Sat, 10 Mar 2012)

  New Revision: 34963

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

  Log:
    * 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

  Modified files:
    trunk/ChangeLog
    trunk/ext/-test-/st/numhash/numhash.c
    trunk/ext/tk/tkutil/tkutil.c
    trunk/hash.c
    trunk/include/ruby/st.h
    trunk/st.c
    trunk/test/-ext-/st/test_numhash.rb

Index: include/ruby/st.h
===================================================================
--- include/ruby/st.h	(revision 34962)
+++ include/ruby/st.h	(revision 34963)
@@ -123,6 +123,7 @@
 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 *);
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 34962)
+++ ChangeLog	(revision 34963)
@@ -1,5 +1,9 @@
-Sat Mar 10 23:52:03 2012  Nobuyoshi Nakada  <nobu@r...>
+Sat Mar 10 23:52:16 2012  Nobuyoshi Nakada  <nobu@r...>
 
+	* 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
 
Index: st.c
===================================================================
--- st.c	(revision 34962)
+++ st.c	(revision 34963)
@@ -866,18 +866,19 @@
 }
 
 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 @@
 		}
 		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 @@
 		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 @@
 
     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 @@
     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)
Index: ext/-test-/st/numhash/numhash.c
===================================================================
--- ext/-test-/st/numhash/numhash.c	(revision 34962)
+++ ext/-test-/st/numhash/numhash.c	(revision 34963)
@@ -54,7 +54,9 @@
 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
Index: ext/tk/tkutil/tkutil.c
===================================================================
--- ext/tk/tkutil/tkutil.c	(revision 34962)
+++ ext/tk/tkutil/tkutil.c	(revision 34963)
@@ -266,7 +266,6 @@
     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 @@
 
     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 @@
 
     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 @@
     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 @@
 
     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 @@
     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;
Index: hash.c
===================================================================
--- hash.c	(revision 34962)
+++ hash.c	(revision 34963)
@@ -116,7 +116,6 @@
 {
     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 @@
     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 @@
 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;
Index: test/-ext-/st/test_numhash.rb
===================================================================
--- test/-ext-/st/test_numhash.rb	(revision 34962)
+++ test/-ext-/st/test_numhash.rb	(revision 34963)
@@ -32,5 +32,18 @@
         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

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

[前][次][番号順一覧][スレッド一覧]