usa	2013-06-26 17:02:39 +0900 (Wed, 26 Jun 2013)

  New Revision: 41652

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

  Log:
    [Backport #8328] [ruby-core:55250] Patch by funny-falcon
    
    * benchmark/bm_hash_shift.rb: add benchmark for Hash#shift
    
    * hash.c (rb_hash_shift): use st_shift if hash is not being iterated to
      delete element without iterating the whole hash.
    
    * hash.c (shift_i): remove function
    
    * include/ruby/st.h (st_shift): add st_shift function
    
    * st.c (st_shift): ditto

  Modified files:
    branches/ruby_1_9_3/ChangeLog
    branches/ruby_1_9_3/hash.c
    branches/ruby_1_9_3/include/ruby/st.h
    branches/ruby_1_9_3/st.c
    branches/ruby_1_9_3/version.h

Index: ruby_1_9_3/include/ruby/st.h
===================================================================
--- ruby_1_9_3/include/ruby/st.h	(revision 41651)
+++ ruby_1_9_3/include/ruby/st.h	(revision 41652)
@@ -109,6 +109,7 @@ st_table *st_init_strcasetable(void); https://github.com/ruby/ruby/blob/trunk/ruby_1_9_3/include/ruby/st.h#L109
 st_table *st_init_strcasetable_with_size(st_index_t);
 int st_delete(st_table *, st_data_t *, st_data_t *); /* returns 0:notfound 1:deleted */
 int st_delete_safe(st_table *, st_data_t *, st_data_t *, st_data_t);
+int st_shift(st_table *, st_data_t *, st_data_t *); /* returns 0:notfound 1:deleted */
 int st_insert(st_table *, st_data_t, st_data_t);
 int st_insert2(st_table *, st_data_t, st_data_t, st_data_t (*)(st_data_t));
 int st_lookup(st_table *, st_data_t, st_data_t *);
Index: ruby_1_9_3/ChangeLog
===================================================================
--- ruby_1_9_3/ChangeLog	(revision 41651)
+++ ruby_1_9_3/ChangeLog	(revision 41652)
@@ -1,3 +1,18 @@ https://github.com/ruby/ruby/blob/trunk/ruby_1_9_3/ChangeLog#L1
+Wed Jun 26 17:01:22 2013  NAKAMURA Usaku  <usa@r...>
+
+	* benchmark/bm_hash_shift.rb: add benchmark for Hash#shift
+
+	* hash.c (rb_hash_shift): use st_shift if hash is not being iterated to
+	  delete element without iterating the whole hash.
+
+	* hash.c (shift_i): remove function
+
+	* include/ruby/st.h (st_shift): add st_shift function
+
+	* st.c (st_shift): ditto
+
+	[Backport #8328] [ruby-core:55250] Patch by funny-falcon
+
 Wed Jun 26 16:52:57 2013  Kazuki Tsujimoto  <kazuki@c...>
 
 	* test/ruby/test_proc.rb (TestProc#test_block_given_method_to_proc):
Index: ruby_1_9_3/st.c
===================================================================
--- ruby_1_9_3/st.c	(revision 41651)
+++ ruby_1_9_3/st.c	(revision 41652)
@@ -695,6 +695,45 @@ st_delete_safe(register st_table *table, https://github.com/ruby/ruby/blob/trunk/ruby_1_9_3/st.c#L695
     return 0;
 }
 
+int
+st_shift(register st_table *table, register st_data_t *key, st_data_t *value)
+{
+    st_index_t hash_val;
+    st_table_entry **prev;
+    register st_table_entry *ptr;
+
+    if (table->num_entries == 0) {
+        if (value != 0) *value = 0;
+        return 0;
+    }
+
+    if (table->entries_packed) {
+        if (value != 0) *value = (st_data_t)table->bins[1];
+        *key = (st_data_t)table->bins[0];
+        table->num_entries--;
+        memmove(&table->bins[0], &table->bins[2],
+                sizeof(struct st_table_entry*) * 2*table->num_entries);
+        return 1;
+    }
+
+    hash_val = do_hash_bin(table->head->key, table);
+    prev = &table->bins[hash_val];
+    for (;(ptr = *prev) != 0; prev = &ptr->next) {
+	if (ptr == table->head) {
+	    *prev = ptr->next;
+            REMOVE_ENTRY(table, ptr);
+            if (value != 0) *value = ptr->record;
+            *key = ptr->key;
+            free(ptr);
+            return 1;
+	}
+    }
+
+    /* if hash is not consistent and need to be rehashed */
+    if (value != 0) *value = 0;
+    return 0;
+}
+
 void
 st_cleanup_safe(st_table *table, st_data_t never)
 {
Index: ruby_1_9_3/hash.c
===================================================================
--- ruby_1_9_3/hash.c	(revision 41651)
+++ ruby_1_9_3/hash.c	(revision 41652)
@@ -824,18 +824,6 @@ struct shift_var { https://github.com/ruby/ruby/blob/trunk/ruby_1_9_3/hash.c#L824
 };
 
 static int
-shift_i(VALUE key, VALUE value, VALUE arg)
-{
-    struct shift_var *var = (struct shift_var *)arg;
-
-    if (key == Qundef) return ST_CONTINUE;
-    if (var->key != Qundef) return ST_STOP;
-    var->key = key;
-    var->val = value;
-    return ST_DELETE;
-}
-
-static int
 shift_i_safe(VALUE key, VALUE value, VALUE arg)
 {
     struct shift_var *var = (struct shift_var *)arg;
@@ -866,16 +854,20 @@ rb_hash_shift(VALUE hash) https://github.com/ruby/ruby/blob/trunk/ruby_1_9_3/hash.c#L854
 
     rb_hash_modify(hash);
     var.key = Qundef;
-    rb_hash_foreach(hash, RHASH(hash)->iter_lev > 0 ? shift_i_safe : shift_i,
-		    (VALUE)&var);
+    if (RHASH(hash)->iter_lev == 0) {
+	if (st_shift(RHASH(hash)->ntbl, &var.key, &var.val)) {
+	    return rb_assoc_new(var.key, var.val);
+	}
+    }
+    else {
+	rb_hash_foreach(hash, shift_i_safe, (VALUE)&var);
 
-    if (var.key != Qundef) {
-	if (RHASH(hash)->iter_lev > 0) {
+	if (var.key != Qundef) {
 	    rb_hash_delete_key(hash, var.key);
+	    return rb_assoc_new(var.key, var.val);
 	}
-	return rb_assoc_new(var.key, var.val);
     }
-    else if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
+    if (FL_TEST(hash, HASH_PROC_DEFAULT)) {
 	return rb_funcall(RHASH_IFNONE(hash), id_yield, 2, hash, Qnil);
     }
     else {
Index: ruby_1_9_3/version.h
===================================================================
--- ruby_1_9_3/version.h	(revision 41651)
+++ ruby_1_9_3/version.h	(revision 41652)
@@ -1,5 +1,5 @@ https://github.com/ruby/ruby/blob/trunk/ruby_1_9_3/version.h#L1
 #define RUBY_VERSION "1.9.3"
-#define RUBY_PATCHLEVEL 443
+#define RUBY_PATCHLEVEL 444
 
 #define RUBY_RELEASE_DATE "2013-06-26"
 #define RUBY_RELEASE_YEAR 2013

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