ruby-changes:10946
From: yugui <ko1@a...>
Date: Sun, 22 Feb 2009 18:49:04 +0900 (JST)
Subject: [ruby-changes:10946] Ruby:r22522 (ruby_1_9_1): merges r22132 from trunk into ruby_1_9_1.
yugui 2009-02-22 18:48:50 +0900 (Sun, 22 Feb 2009) New Revision: 22522 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=22522 Log: merges r22132 from trunk into ruby_1_9_1. * include/ruby/st.h, st.c: order entries by a linked list instead of a loop to fix iteration miss when hash is modified during iteration. [ruby-dev:37910] Modified files: branches/ruby_1_9_1/ChangeLog branches/ruby_1_9_1/include/ruby/st.h branches/ruby_1_9_1/st.c Index: ruby_1_9_1/include/ruby/st.h =================================================================== --- ruby_1_9_1/include/ruby/st.h (revision 22521) +++ ruby_1_9_1/include/ruby/st.h (revision 22522) @@ -75,7 +75,7 @@ #endif st_index_t num_entries : ST_INDEX_BITS - 1; struct st_table_entry **bins; - struct st_table_entry *head; + struct st_table_entry *head, *tail; }; #define st_is_member(table,key) st_lookup(table,key,(st_data_t *)0) Index: ruby_1_9_1/ChangeLog =================================================================== --- ruby_1_9_1/ChangeLog (revision 22521) +++ ruby_1_9_1/ChangeLog (revision 22522) @@ -1,3 +1,9 @@ +Sun Feb 8 23:28:05 2009 Yusuke Endoh <mame@t...> + + * include/ruby/st.h, st.c: order entries by a linked list instead of + a loop to fix iteration miss when hash is modified during iteration. + [ruby-dev:37910] + Sun Feb 8 22:44:20 2009 Nobuyoshi Nakada <nobu@r...> * include/ruby/backward/rubysig.h (rb_thread_blocking_region_begin), Index: ruby_1_9_1/st.c =================================================================== --- ruby_1_9_1/st.c (revision 22521) +++ ruby_1_9_1/st.c (revision 22522) @@ -176,6 +176,7 @@ tbl->num_bins = size; tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); tbl->head = 0; + tbl->tail = 0; return tbl; } @@ -244,6 +245,7 @@ } table->num_entries = 0; table->head = 0; + table->tail = 0; } void @@ -335,7 +337,7 @@ #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ do {\ - st_table_entry *entry, *head;\ + st_table_entry *entry;\ if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\ rehash(table);\ bin_pos = hash_val % table->num_bins;\ @@ -347,13 +349,14 @@ entry->key = key;\ entry->record = value;\ entry->next = table->bins[bin_pos];\ - if ((head = table->head) != 0) {\ - entry->fore = head;\ - (entry->back = head->back)->fore = entry;\ - head->back = entry;\ + if (table->head != 0) {\ + entry->fore = 0;\ + (entry->back = table->tail)->fore = entry;\ + table->tail = entry;\ }\ else {\ - table->head = entry->fore = entry->back = entry;\ + table->head = table->tail = entry;\ + entry->fore = entry->back = 0;\ }\ table->bins[bin_pos] = entry;\ table->num_entries++;\ @@ -455,7 +458,7 @@ hash_val = ptr->hash % new_num_bins; ptr->next = new_bins[hash_val]; new_bins[hash_val] = ptr; - } while ((ptr = ptr->fore) != table->head); + } while ((ptr = ptr->fore) != 0); } } @@ -502,10 +505,8 @@ entry->back = prev; *tail = prev = entry; tail = &entry->fore; - } while ((ptr = ptr->fore) != old_table->head); - entry = new_table->head; - entry->back = prev; - *tail = entry; + } while ((ptr = ptr->fore) != 0); + new_table->tail = prev; } return new_table; @@ -513,14 +514,16 @@ #define REMOVE_ENTRY(table, ptr) do \ { \ - if (ptr == ptr->fore) { \ + if (ptr->fore == 0 && ptr->back == 0) { \ table->head = 0; \ + table->tail = 0; \ } \ else { \ st_table_entry *fore = ptr->fore, *back = ptr->back; \ - fore->back = back; \ - back->fore = fore; \ + if (fore) fore->back = back; \ + if (back) back->fore = fore; \ if (ptr == table->head) table->head = fore; \ + if (ptr == table->tail) table->tail = back; \ } \ table->num_entries--; \ } while (0) @@ -613,7 +616,7 @@ { st_table_entry *ptr, **last, *tmp; enum st_retval retval; - int i, end; + int i; if (table->entries_packed) { for (i = 0; i < table->num_entries; i++) { @@ -651,7 +654,6 @@ if ((ptr = table->head) != 0) { do { - end = ptr->fore == table->head; retval = (*func)(ptr->key, ptr->record, arg); switch (retval) { case ST_CHECK: /* check if hash is modified during iteration */ @@ -683,7 +685,7 @@ } } } - } while (!end && table->head); + } while (ptr && table->head); } return 0; } @@ -694,7 +696,7 @@ { st_table_entry *ptr, **last, *tmp; enum st_retval retval; - int i, end; + int i; if (table->entries_packed) { for (i = table->num_entries-1; 0 <= i; i--) { @@ -732,7 +734,6 @@ if ((ptr = table->head) != 0) { ptr = ptr->back; do { - end = ptr == table->head; retval = (*func)(ptr->key, ptr->record, arg, 0); switch (retval) { case ST_CHECK: /* check if hash is modified during iteration */ @@ -766,7 +767,7 @@ free(tmp); table->num_entries--; } - } while (!end && table->head); + } while (ptr && table->head); } return 0; } -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/