[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


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_9_3@41652 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 39 insertions, 0 deletions

diff --git a/st.c b/st.c
index c093bfd392..8c238c33f8 100644
--- a/st.c
+++ b/st.c
@@ -695,6 +695,45 @@ st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *val
     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)
 {