* 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]


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@22132 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

3 files changed, 28 insertions, 21 deletions

diff --git a/ChangeLog b/ChangeLog
index 09681d5c1a..6063712d27 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+Sun Feb  8 23:28:05 2009  Yusuke Endoh  <mame@tsg.ne.jp>
+
+	* 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@fsij.org>
 
 	* ext/socket/option.c (inspect_peercred): new function to show
diff --git a/include/ruby/st.h b/include/ruby/st.h
index 09a7c58226..73216ba45c 100644
--- a/include/ruby/st.h
+++ b/include/ruby/st.h
@@ -75,7 +75,7 @@ struct st_table {
 #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)
diff --git a/st.c b/st.c
index 4b2be3d8c7..b5d115261c 100644
--- a/st.c
+++ b/st.c
@@ -176,6 +176,7 @@ st_init_table_with_size(const struct st_hash_type *type, int size)
     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 @@ st_clear(st_table *table)
     }
     table->num_entries = 0;
     table->head = 0;
+    table->tail = 0;
 }
 
 void
@@ -335,7 +337,7 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
 
 #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 @@ do {\
     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 @@ rehash(register st_table *table)
 	    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 @@ st_copy(st_table *old_table)
 	    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 @@ st_copy(st_table *old_table)
 
 #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_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 {
     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 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 
     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 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 		    }
 		}
 	    }
-	} while (!end && table->head);
+	} while (ptr && table->head);
     }
     return 0;
 }
@@ -694,7 +696,7 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 {
     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 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
     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 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 		free(tmp);
 		table->num_entries--;
 	    }
-	} while (!end && table->head);
+	} while (ptr && table->head);
     }
     return 0;
 }