なかだです。

たしかruby-talkでHashを順序つきにするという話が出ていたと思うん
ですが、いつのだか分からなくなったのでdevに振ります。


Index: st.c =================================================================== RCS file: /cvs/ruby/src/ruby/st.c,v retrieving revision 1.30 diff -U2 -p -d -r1.30 st.c --- st.c 23 Sep 2004 00:51:31 -0000 1.30 +++ st.c 22 Oct 2004 16:18:59 -0000 @@ -20,4 +20,5 @@ struct st_table_entry { st_data_t record; st_table_entry *next; + st_table_entry *forw, *back; }; @@ -170,4 +171,5 @@ st_init_table_with_size(type, size) tbl->num_bins = size; tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); + tbl->head = 0; return tbl; @@ -270,5 +272,5 @@ st_lookup(table, key, value) #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ do {\ - st_table_entry *entry;\ + st_table_entry *entry, *head;\ if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\ rehash(table);\ @@ -282,4 +284,12 @@ do {\ entry->record = value;\ entry->next = table->bins[bin_pos];\ + if (head = table->head) {\ + entry->forw = head;\ + (entry->back = head->back)->forw = entry;\ + head->back = entry;\ + }\ + else {\ + table->head = entry->forw = entry->back = entry;\ + }\ table->bins[bin_pos] = entry;\ table->num_entries++;\ @@ -326,23 +336,21 @@ rehash(table) { register st_table_entry *ptr, *next, **new_bins; - int i, old_num_bins = table->num_bins, new_num_bins; + int i, new_num_bins; unsigned int hash_val; - new_num_bins = new_size(old_num_bins+1); - new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); + new_num_bins = new_size(table->num_bins+1); + new_bins = (st_table_entry**) + xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*)); + for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0; + table->num_bins = new_num_bins; + table->bins = new_bins; - for(i = 0; i < old_num_bins; i++) { - ptr = table->bins[i]; - while (ptr != 0) { - next = ptr->next; + if (ptr = table->head) { + do { hash_val = ptr->hash % new_num_bins; ptr->next = new_bins[hash_val]; new_bins[hash_val] = ptr; - ptr = next; - } + } while ((ptr = ptr->forw) != table->head); } - free(table->bins); - table->num_bins = new_num_bins; - table->bins = new_bins; } @@ -352,6 +360,7 @@ st_copy(old_table) { st_table *new_table; - st_table_entry *ptr, *entry; - int i, num_bins = old_table->num_bins; + st_table_entry *ptr, *entry, *prev, **tail; + int num_bins = old_table->num_bins; + unsigned int hash_val; new_table = alloc(st_table); @@ -369,23 +378,43 @@ st_copy(old_table) } - for(i = 0; i < num_bins; i++) { - new_table->bins[i] = 0; - ptr = old_table->bins[i]; - while (ptr != 0) { + if (ptr = old_table->head) { + prev = 0; + tail = &new_table->head; + do { entry = alloc(st_table_entry); if (entry == 0) { - free(new_table->bins); - free(new_table); + st_free_table(new_table); return 0; } *entry = *ptr; - entry->next = new_table->bins[i]; - new_table->bins[i] = entry; - ptr = ptr->next; - } + hash_val = entry->hash % num_bins; + entry->next = new_table->bins[hash_val]; + new_table->bins[hash_val] = entry; + entry->back = prev; + *tail = prev = entry; + tail = &entry->forw; + } while ((ptr = ptr->forw) != old_table->head); + entry = new_table->head; + entry->back = prev; + *tail = entry; } + return new_table; } +#define REMOVE_ENTRY(table, ptr) do {\ + if (ptr == ptr->forw) {\ + table->head = 0;\ + }\ + else {\ + st_table_entry *forw = ptr->forw, *back = ptr->back;\ + forw->back = back;\ + back->forw = forw;\ + if (ptr == table->head) table->head = forw;\ + }\ + table->num_entries--;\ +} while (0) + + int st_delete(table, key, value) @@ -395,36 +424,21 @@ st_delete(table, key, value) { unsigned int hash_val; - st_table_entry *tmp; + st_table_entry **prev; register st_table_entry *ptr; hash_val = do_hash_bin(*key, table); - ptr = table->bins[hash_val]; - - if (ptr == 0) { - if (value != 0) *value = 0; - return 0; - } - - if (EQUAL(table, *key, ptr->key)) { - table->bins[hash_val] = ptr->next; - table->num_entries--; - if (value != 0) *value = ptr->record; - *key = ptr->key; - free(ptr); - return 1; - } - for(; ptr->next != 0; ptr = ptr->next) { - if (EQUAL(table, ptr->next->key, *key)) { - tmp = ptr->next; - ptr->next = ptr->next->next; - table->num_entries--; - if (value != 0) *value = tmp->record; - *key = tmp->key; - free(tmp); + for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) { + if (EQUAL(table, *key, ptr->key)) { + *prev = ptr->next; + REMOVE_ENTRY(table, ptr); + if (value != 0) *value = ptr->record; + *key = ptr->key; + free(ptr); return 1; } } + if (value != 0) *value = 0; return 0; } @@ -443,12 +457,7 @@ st_delete_safe(table, key, value, never) ptr = table->bins[hash_val]; - if (ptr == 0) { - if (value != 0) *value = 0; - return 0; - } - - for(; ptr != 0; ptr = ptr->next) { + for (; ptr != 0; ptr = ptr->next) { if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { - table->num_entries--; + REMOVE_ENTRY(table, ptr); *key = ptr->key; if (value != 0) *value = ptr->record; @@ -458,15 +467,8 @@ st_delete_safe(table, key, value, never) } + if (value != 0) *value = 0; return 0; } -static int -delete_never(key, value, never) - st_data_t key, value, never; -{ - if (value == never) return ST_DELETE; - return ST_CONTINUE; -} - void st_cleanup_safe(table, never) @@ -474,11 +476,24 @@ st_cleanup_safe(table, never) st_data_t never; { - int num_entries = table->num_entries; + st_table_entry *ptr, **last, *tmp; + int i; - st_foreach(table, delete_never, never); - table->num_entries = num_entries; + for (i = 0; i < table->num_bins; i++) { + ptr = *(last = &table->bins[i]); + while (ptr != 0) { + if (ptr->forw == 0) { + tmp = ptr; + *last = ptr = ptr->next; + free(tmp); + table->num_entries--; + } + else { + ptr = *(last = &ptr->next); + } + } + } } -void +int st_foreach(table, func, arg) st_table *table; @@ -486,46 +501,94 @@ st_foreach(table, func, arg) st_data_t arg; { - st_table_entry *ptr, *last, *tmp; + st_table_entry *ptr, **last, *tmp; enum st_retval retval; int i; - for(i = 0; i < table->num_bins; i++) { - last = 0; - for(ptr = table->bins[i]; ptr != 0;) { + if ((ptr = table->head) != 0) { + do { retval = (*func)(ptr->key, ptr->record, arg, 0); switch (retval) { - case ST_CHECK: /* check if hash is modified during iteration */ - tmp = 0; - if (i < table->num_bins) { - for (tmp = table->bins[i]; tmp; tmp=tmp->next) { - if (tmp == ptr) break; + case ST_CHECK: /* check if hash is modified during iteration */ + i = ptr->hash % table->num_bins; + for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { + if (!tmp) { + /* call func with error notice */ + retval = (*func)(0, 0, arg, 1); + return 0; } } - if (!tmp) { - /* call func with error notice */ - retval = (*func)(0, 0, arg, 1); - return; - } /* fall through */ - case ST_CONTINUE: - last = ptr; - ptr = ptr->next; + case ST_CONTINUE: + ptr = ptr->forw; break; - case ST_STOP: - return; - case ST_DELETE: - tmp = ptr; - if (last == 0) { - table->bins[i] = ptr->next; + case ST_STOP: + return 0; + case ST_DELETE: + last = &table->bins[ptr->hash % table->num_bins]; + for (; (tmp = *last) != 0; last = &tmp->next) { + if (ptr == tmp) { + tmp = ptr->forw; + *last = ptr->next; + REMOVE_ENTRY(table, ptr); + free(ptr); + if (ptr == tmp) return 1; + ptr = tmp; + break; + } } - else { - last->next = ptr->next; + } + } while (ptr != table->head); + } + return 1; +} + +int +st_reverse_foreach(table, func, arg) + st_table *table; + int (*func)(); + st_data_t arg; +{ + st_table_entry *ptr, **last, *tmp; + enum st_retval retval; + int i, end; + + 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 */ + i = ptr->hash % table->num_bins; + for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) { + if (!tmp) { + /* call func with error notice */ + retval = (*func)(0, 0, arg, 1); + return 0; + } + } + /* fall through */ + case ST_CONTINUE: + ptr = ptr->back; + break; + case ST_STOP: + return 0; + case ST_DELETE: + last = &table->bins[ptr->hash % table->num_bins]; + for (; (tmp = *last) != 0; last = &tmp->next) { + if (ptr == tmp) { + tmp = ptr->back; + *last = ptr->next; + REMOVE_ENTRY(table, ptr); + free(ptr); + if (ptr == tmp) return 1; + ptr = tmp; + break; + } } - ptr = ptr->next; - free(tmp); - table->num_entries--; } - } + } while (!end); } + return 1; } Index: st.h =================================================================== RCS file: /cvs/ruby/src/ruby/st.h,v retrieving revision 1.10 diff -U2 -p -d -r1.10 st.h --- st.h 23 Sep 2004 00:51:31 -0000 1.10 +++ st.h 22 Oct 2004 15:06:24 -0000 @@ -22,4 +22,5 @@ struct st_table { int num_entries; struct st_table_entry **bins; + struct st_table_entry *head; }; @@ -42,5 +43,5 @@ int st_delete_safe _((st_table *, st_dat int st_insert _((st_table *, st_data_t, st_data_t)); int st_lookup _((st_table *, st_data_t, st_data_t *)); -void st_foreach _((st_table *, int (*)(), st_data_t)); +int st_foreach _((st_table *, int (*)(), st_data_t)); void st_add_direct _((st_table *, st_data_t, st_data_t)); void st_free_table _((st_table *));
-- --- 僕の前にBugはない。 --- 僕の後ろにBugはできる。 中田 伸悦