summaryrefslogtreecommitdiff
path: root/st.c
diff options
context:
space:
mode:
authormame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2009-02-08 14:34:13 +0000
committermame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2009-02-08 14:34:13 +0000
commitf64018b111a371d6ece84d509535b760d072053f (patch)
tree2c4441983f254b86451e9abb73690c741832b880 /st.c
parent8f9d6d1863e3b00ed44ac693e9659b860cf1e507 (diff)
* 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
Diffstat (limited to 'st.c')
-rw-r--r--st.c41
1 files changed, 21 insertions, 20 deletions
diff --git a/st.c b/st.c
index 4b2be3d..b5d1152 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;
}