Project

General

Profile

Bug #9646

Updated by nobu (Nobuyoshi Nakada) about 10 years ago

Hashでキーを同じにすると、無限ループしてしまいます。 

 再現コードは 
 ruby -e 'h={};h[a=[]]=1;a<<1;h[[]] = 2;a.clear;h.each{|i| p i}' 
 です。 

 `st_foreach_check`で`callcc`対応のために st\_foreach\_checkでcallcc対応のために 
 `find_packed_index`を毎回呼んでおり、そこで`i`が進まなくなっています。 find\_packed\_indexを毎回呼んでおり、そこでiが進まなくなっています。 
 そもそも、同じキーの状態を作り出せるのがどうなんだという話はあるかもしれませんが、 
 そちらを直すのは大きな変更になりそうなので、とりあえず以下のような感じでどうでしょうか? 
 callccでの後戻りをあきらめています。 

 #または、callccでイテレータの中に戻るのを禁止した方がよいのかもしれません。 

 ~~~diff ~~~ 
 --- a/st.c 
 +++ b/st.c 
 @@ -394,9 +394,8 @@ find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_p 
  } 

  static inline st_index_t 
 -find_packed_index(st_table *table, st_index_t hash_val, st_data_t key) 
 +find_packed_index_from(st_table *table, st_index_t hash_val, st_data_t key,st_index_t i) 
  { 
 -      st_index_t i = 0; 
      while (i < table->real_entries && 
            (PHASH(table, i) != hash_val || !EQUAL(table, key, PKEY(table, i)))) { 
         i++; 
 @@ -404,6 +403,12 @@ find_packed_index(st_table *table, st_index_t hash_val, st_data_t key) 
      return i; 
  } 

 +static inline st_index_t 
 +find_packed_index(st_table *table, st_index_t hash_val, st_data_t key) 
 +{ 
 +      return find_packed_index_from(table,hash_val,key,0); 
 +} 
 + 
  #define collision_check 0 

  int 
 @@ -963,8 +968,8 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t 
                 if (PHASH(table, i) == 0 && PKEY(table, i) == never) { 
                     break; 
                 } 
 -                 i = find_packed_index(table, hash, key); 
 -                 if (i == table->real_entries) { 
 +                 i = find_packed_index_from(table, hash, key, i); 
 +                 if (i >= table->real_entries) { 
                     goto deleted; 
                 } 
                 /* fall through */ 
 ~~~ 

Back