charliesome	2013-04-25 14:03:30 +0900 (Thu, 25 Apr 2013)

  New Revision: 40457

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

  Log:
    * 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
    
    [Bug #8312] [ruby-core:54524] Patch by funny-falcon

  Added files:
    trunk/benchmark/bm_hash_shift.rb
  Modified files:
    trunk/ChangeLog
    trunk/hash.c
    trunk/include/ruby/st.h
    trunk/st.c

Index: include/ruby/st.h
===================================================================
--- include/ruby/st.h	(revision 40456)
+++ include/ruby/st.h	(revision 40457)
@@ -102,6 +102,7 @@ st_table *st_init_strcasetable(void); https://github.com/ruby/ruby/blob/trunk/include/ruby/st.h#L102
 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: ChangeLog
===================================================================
--- ChangeLog	(revision 40456)
+++ ChangeLog	(revision 40457)
@@ -1,3 +1,18 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Wed Apr 25 14:26:00 2013  Charlie Somerville  <charlie@c...>
+
+	* 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
+
+	[Bug #8312] [ruby-core:54524] Patch by funny-falcon
+
 Thu Apr 25 12:03:38 2013  Tanaka Akira  <akr@f...>
 
 	* ext/socket/extconf.rb: Extract C programs as toplevel constants.
Index: st.c
===================================================================
--- st.c	(revision 40456)
+++ st.c	(revision 40457)
@@ -793,6 +793,35 @@ st_delete_safe(register st_table *table, https://github.com/ruby/ruby/blob/trunk/st.c#L793
     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 = PVAL(table, 0);
+        *key = PKEY(table, 0);
+        remove_packed_entry(table, 0);
+        return 1;
+    }
+
+    prev = &table->bins[table->head->hash % table->num_bins];
+    while ((ptr = *prev) != table->head) prev = &ptr->next;
+    *prev = ptr->next;
+    if (value != 0) *value = ptr->record;
+    *key = ptr->key;
+    remove_entry(table, ptr);
+    st_free_entry(ptr);
+    return 1;
+}
+
 void
 st_cleanup_safe(st_table *table, st_data_t never)
 {
Index: hash.c
===================================================================
--- hash.c	(revision 40456)
+++ hash.c	(revision 40457)
@@ -875,17 +875,6 @@ struct shift_var { https://github.com/ruby/ruby/blob/trunk/hash.c#L875
 };
 
 static int
-shift_i(VALUE key, VALUE value, VALUE arg)
-{
-    struct shift_var *var = (struct shift_var *)arg;
-
-    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;
@@ -916,14 +905,17 @@ rb_hash_shift(VALUE hash) https://github.com/ruby/ruby/blob/trunk/hash.c#L905
     rb_hash_modify_check(hash);
     if (RHASH(hash)->ntbl) {
 	var.key = Qundef;
-	rb_hash_foreach(hash, RHASH_ITER_LEV(hash) > 0 ? shift_i_safe : shift_i,
-			(VALUE)&var);
-
-	if (var.key != Qundef) {
-	    if (RHASH_ITER_LEV(hash) > 0) {
+	if (RHASH_ITER_LEV(hash) == 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) {
 		rb_hash_delete_key(hash, var.key);
+		return rb_assoc_new(var.key, var.val);
 	    }
-	    return rb_assoc_new(var.key, var.val);
 	}
     }
     return hash_default_value(hash, Qnil);
Index: benchmark/bm_hash_shift.rb
===================================================================
--- benchmark/bm_hash_shift.rb	(revision 0)
+++ benchmark/bm_hash_shift.rb	(revision 40457)
@@ -0,0 +1,10 @@ https://github.com/ruby/ruby/blob/trunk/benchmark/bm_hash_shift.rb#L1
+h = {}
+
+10000.times do |i|
+  h[i] = nil
+end
+
+50000.times do
+  k, v = h.shift
+  h[k] = v
+end

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