diff options
-rw-r--r-- | ChangeLog | 15 | ||||
-rw-r--r-- | hash.c | 28 | ||||
-rw-r--r-- | include/ruby/st.h | 1 | ||||
-rw-r--r-- | st.c | 39 | ||||
-rw-r--r-- | version.h | 2 |
5 files changed, 66 insertions, 19 deletions
@@ -1,3 +1,18 @@ +Wed Jun 26 17:01:22 2013 NAKAMURA Usaku <usa@ruby-lang.org> + + * 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@callcc.net> * test/ruby/test_proc.rb (TestProc#test_block_given_method_to_proc): @@ -824,18 +824,6 @@ struct shift_var { }; 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) 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 { diff --git a/include/ruby/st.h b/include/ruby/st.h index 50f2a75328..68cc511809 100644 --- a/include/ruby/st.h +++ b/include/ruby/st.h @@ -109,6 +109,7 @@ st_table *st_init_strcasetable(void); 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 *); @@ -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) { @@ -1,5 +1,5 @@ #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 |