ruby-changes:10576
From: mame <ko1@a...>
Date: Sun, 8 Feb 2009 23:35:16 +0900 (JST)
Subject: [ruby-changes:10576] Ruby:r22132 (trunk): * include/ruby/st.h, st.c: order entries by a linked list instead of
mame 2009-02-08 23:34:13 +0900 (Sun, 08 Feb 2009) New Revision: 22132 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=22132 Log: * 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: trunk/ChangeLog trunk/include/ruby/st.h trunk/st.c Index: include/ruby/st.h =================================================================== --- include/ruby/st.h (revision 22131) +++ include/ruby/st.h (revision 22132) @@ -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: ChangeLog =================================================================== --- ChangeLog (revision 22131) +++ ChangeLog (revision 22132) @@ -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 23:22:35 2009 Tanaka Akira <akr@f...> * ext/socket/option.c (inspect_peercred): new function to show Index: st.c =================================================================== --- st.c (revision 22131) +++ st.c (revision 22132) @@ -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/