diff options
| -rw-r--r-- | hash.c | 86 | ||||
| -rw-r--r-- | st.c | 7 | ||||
| -rw-r--r-- | test/ruby/test_hash.rb | 20 |
3 files changed, 79 insertions, 34 deletions
@@ -767,31 +767,39 @@ ar_free_and_clear_table(VALUE hash) HASH_ASSERT(RHASH_TRANSIENT_P(hash) == 0); } -static void -ar_try_convert_table(VALUE hash) -{ - if (!RHASH_AR_TABLE_P(hash)) return; - - const unsigned size = RHASH_AR_TABLE_SIZE(hash); +void rb_st_add_direct_with_hash(st_table *tab, st_data_t key, st_data_t value, st_hash_t hash); // st.c - st_table *new_tab; - st_index_t i; +enum ar_each_key_type { + ar_each_key_copy, + ar_each_key_cmp, + ar_each_key_insert, +}; - if (size < RHASH_AR_TABLE_MAX_SIZE) { - return; +static inline int +ar_each_key(ar_table *ar, int max, enum ar_each_key_type type, st_data_t *dst_keys, st_table *new_tab, st_hash_t *hashes) +{ + for (int i = 0; i < max; i++) { + ar_table_pair *pair = &ar->pairs[i]; + + switch (type) { + case ar_each_key_copy: + dst_keys[i] = pair->key; + break; + case ar_each_key_cmp: + if (dst_keys[i] != pair->key) return 1; + break; + case ar_each_key_insert: + if (UNDEF_P(pair->key)) continue; // deleted entry + rb_st_add_direct_with_hash(new_tab, pair->key, pair->val, hashes[i]); + break; + } } - new_tab = st_init_table_with_size(&objhash, size * 2); - - for (i = 0; i < RHASH_AR_TABLE_MAX_BOUND; i++) { - ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i); - st_add_direct(new_tab, pair->key, pair->val); - } - ar_free_and_clear_table(hash); - RHASH_ST_TABLE_SET(hash, new_tab); - return; + return 0; } + + static st_table * ar_force_convert_table(VALUE hash, const char *file, int line) { @@ -802,22 +810,32 @@ ar_force_convert_table(VALUE hash, const char *file, int line) } if (RHASH_AR_TABLE(hash)) { - unsigned i, bound = RHASH_AR_TABLE_BOUND(hash); - -#if defined(RHASH_CONVERT_TABLE_DEBUG) && RHASH_CONVERT_TABLE_DEBUG - rb_obj_info_dump(hash); - fprintf(stderr, "force_convert: %s:%d\n", file, line); - RB_DEBUG_COUNTER_INC(obj_hash_force_convert); -#endif + ar_table *ar = RHASH_AR_TABLE(hash); + st_hash_t hashes[RHASH_AR_TABLE_MAX_SIZE]; + unsigned int bound, size; + + // prepare hash values + do { + st_data_t keys[RHASH_AR_TABLE_MAX_SIZE]; + bound = RHASH_AR_TABLE_BOUND(hash); + size = RHASH_AR_TABLE_SIZE(hash); + ar_each_key(ar, bound, ar_each_key_copy, keys, NULL, NULL); + + for (unsigned int i = 0; i < bound; i++) { + // do_hash calls #hash method and it can modify hash object + hashes[i] = UNDEF_P(keys[i]) ? 0 : ar_do_hash(keys[i]); + } - new_tab = st_init_table_with_size(&objhash, RHASH_AR_TABLE_SIZE(hash)); + // check if modified + if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) return RHASH_ST_TABLE(hash); + if (UNLIKELY(RHASH_AR_TABLE_BOUND(hash) != bound)) continue; + if (UNLIKELY(ar_each_key(ar, bound, ar_each_key_cmp, keys, NULL, NULL))) continue; + } while (0); - for (i = 0; i < bound; i++) { - if (ar_cleared_entry(hash, i)) continue; - ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i); - st_add_direct(new_tab, pair->key, pair->val); - } + // make st + new_tab = st_init_table_with_size(&objhash, size); + ar_each_key(ar, bound, ar_each_key_insert, NULL, new_tab, hashes); ar_free_and_clear_table(hash); } else { @@ -1724,7 +1742,7 @@ rb_hash_stlike_update(VALUE hash, st_data_t key, st_update_callback_func *func, if (RHASH_AR_TABLE_P(hash)) { int result = ar_update(hash, key, func, arg); if (result == -1) { - ar_try_convert_table(hash); + ar_force_convert_table(hash, __FILE__, __LINE__); } else { return result; @@ -4801,7 +4819,7 @@ rb_hash_add_new_element(VALUE hash, VALUE key, VALUE val) if (ret != -1) { return ret; } - ar_try_convert_table(hash); + ar_force_convert_table(hash, __FILE__, __LINE__); } tbl = RHASH_TBL_RAW(hash); return st_update(tbl, (st_data_t)key, add_new_i, (st_data_t)args); @@ -1159,6 +1159,13 @@ st_add_direct_with_hash(st_table *tab, } } +void +rb_st_add_direct_with_hash(st_table *tab, + st_data_t key, st_data_t value, st_hash_t hash) +{ + st_add_direct_with_hash(tab, key, value, hash); +} + /* Insert (KEY, VALUE) into table TAB. The table should not have entry with KEY before the insertion. */ void diff --git a/test/ruby/test_hash.rb b/test/ruby/test_hash.rb index 8d36cf657f..639c0105c0 100644 --- a/test/ruby/test_hash.rb +++ b/test/ruby/test_hash.rb @@ -2246,4 +2246,24 @@ class TestHash < Test::Unit::TestCase end; end end + + def test_ar_hash_to_st_hash + assert_normal_exit("#{<<~"begin;"}\n#{<<~'end;'}", 'https://bugs.ruby-lang.org/issues/20050#note-5') + begin; + srand(0) + class Foo + def to_a + [] + end + def hash + $h.delete($h.keys.sample) if rand < 0.1 + to_a.hash + end + end + 1000.times do + $h = {} + (0..10).each {|i| $h[Foo.new] ||= {} } + end + end; + end end |