ruby-changes:1808
From: ko1@a...
Date: 29 Aug 2007 11:37:03 +0900
Subject: [ruby-changes:1808] akr - Ruby:r13299 (trunk): * include/ruby/st.h (struct st_table): add entries_packed 1-bit
akr 2007-08-29 11:36:54 +0900 (Wed, 29 Aug 2007)
New Revision: 13299
Modified files:
trunk/ChangeLog
trunk/include/ruby/st.h
trunk/st.c
Log:
* include/ruby/st.h (struct st_table): add entries_packed 1-bit
bitfield. decrease num_bins 1-bit.
* st.c: pack numhash which have 5 or less entries in bins.
(st_init_table_with_size): setup entries_packed flag.
(st_clear): support packed mode.
(st_lookup): ditto.
(st_insert): ditto.
(st_add_direct): ditto.
(st_copy): ditto.
(st_delete): ditto.
(st_foreach): ditto.
(st_reverse_foreach): ditto.
(unpack_entries): new function for converting to unpacked mode.
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/include/ruby/st.h?r1=13299&r2=13298
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/ChangeLog?r1=13299&r2=13298
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/st.c?r1=13299&r2=13298
Index: include/ruby/st.h
===================================================================
--- include/ruby/st.h (revision 13298)
+++ include/ruby/st.h (revision 13299)
@@ -31,7 +31,8 @@
struct st_table {
const struct st_hash_type *type;
- int num_bins;
+ unsigned int entries_packed : 1;
+ int num_bins : sizeof(int) * 8 - 1;
int num_entries;
struct st_table_entry **bins;
struct st_table_entry *head;
Index: ChangeLog
===================================================================
--- ChangeLog (revision 13298)
+++ ChangeLog (revision 13299)
@@ -1,3 +1,20 @@
+Wed Aug 29 11:30:10 2007 Tanaka Akira <akr@f...>
+
+ * include/ruby/st.h (struct st_table): add entries_packed 1-bit
+ bitfield. decrease num_bins 1-bit.
+
+ * st.c: pack numhash which have 5 or less entries in bins.
+ (st_init_table_with_size): setup entries_packed flag.
+ (st_clear): support packed mode.
+ (st_lookup): ditto.
+ (st_insert): ditto.
+ (st_add_direct): ditto.
+ (st_copy): ditto.
+ (st_delete): ditto.
+ (st_foreach): ditto.
+ (st_reverse_foreach): ditto.
+ (unpack_entries): new function for converting to unpacked mode.
+
Wed Aug 29 10:46:37 2007 Yukihiro Matsumoto <matz@r...>
* include/ruby/defines.h (flush_register_windows): call "ta 0x03"
Index: st.c
===================================================================
--- st.c (revision 13298)
+++ st.c (revision 13299)
@@ -145,6 +145,8 @@
}
#endif
+#define MAX_PACKED_NUMHASH 5
+
st_table*
st_init_table_with_size(const struct st_hash_type *type, int size)
{
@@ -162,6 +164,7 @@
tbl = alloc(st_table);
tbl->type = type;
tbl->num_entries = 0;
+ tbl->entries_packed = type == &type_numhash && size/2 <= MAX_PACKED_NUMHASH;
tbl->num_bins = size;
tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
tbl->head = 0;
@@ -205,6 +208,11 @@
register st_table_entry *ptr, *next;
int i;
+ if (table->entries_packed) {
+ table->num_entries = 0;
+ return;
+ }
+
for(i = 0; i < table->num_bins; i++) {
ptr = table->bins[i];
table->bins[i] = 0;
@@ -253,6 +261,17 @@
unsigned int hash_val, bin_pos;
register st_table_entry *ptr;
+ if (table->entries_packed) {
+ int i;
+ for (i = 0; i < table->num_entries; i++) {
+ if ((st_data_t)table->bins[i*2] == key) {
+ if (value !=0) *value = (st_data_t)table->bins[i*2+1];
+ return 1;
+ }
+ }
+ return 0;
+ }
+
hash_val = do_hash(key, table);
FIND_ENTRY(table, ptr, hash_val, bin_pos);
@@ -291,12 +310,47 @@
table->num_entries++;\
} while (0)
+static void
+unpack_entries(register st_table *table)
+{
+ int i;
+ struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2];
+ int num_entries = table->num_entries;
+
+ memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * num_entries*2);
+ table->entries_packed = 0;
+ table->num_entries = 0;
+ memset(table->bins, 0, sizeof(struct st_table_entry *) * table->num_bins);
+ for (i = 0; i < num_entries; i++) {
+ st_insert(table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]);
+ }
+}
+
int
st_insert(register st_table *table, register st_data_t key, st_data_t value)
{
unsigned int hash_val, bin_pos;
register st_table_entry *ptr;
+ if (table->entries_packed) {
+ int i;
+ for (i = 0; i < table->num_entries; i++) {
+ if ((st_data_t)table->bins[i*2] == key) {
+ table->bins[i*2+1] = (struct st_table_entry*)value;
+ return 1;
+ }
+ }
+ if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) {
+ i = table->num_entries++;
+ table->bins[i*2] = (struct st_table_entry*)key;
+ table->bins[i*2+1] = (struct st_table_entry*)value;
+ return 0;
+ }
+ else {
+ unpack_entries(table);
+ }
+ }
+
hash_val = do_hash(key, table);
FIND_ENTRY(table, ptr, hash_val, bin_pos);
@@ -315,6 +369,19 @@
{
unsigned int hash_val, bin_pos;
+ if (table->entries_packed) {
+ int i;
+ if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) {
+ i = table->num_entries++;
+ table->bins[i*2] = (struct st_table_entry*)key;
+ table->bins[i*2+1] = (struct st_table_entry*)value;
+ return;
+ }
+ else {
+ unpack_entries(table);
+ }
+ }
+
hash_val = do_hash(key, table);
bin_pos = hash_val % table->num_bins;
ADD_DIRECT(table, key, value, hash_val, bin_pos);
@@ -365,6 +432,11 @@
return 0;
}
+ if (old_table->entries_packed) {
+ memcpy(new_table->bins, old_table->bins, sizeof(struct st_table_entry *) * old_table->num_bins);
+ return new_table;
+ }
+
if ((ptr = old_table->head) != 0) {
prev = 0;
tail = &new_table->head;
@@ -411,6 +483,21 @@
st_table_entry **prev;
register st_table_entry *ptr;
+ if (table->entries_packed) {
+ int i;
+ for (i = 0; i < table->num_entries; i++) {
+ if ((st_data_t)table->bins[i*2] == *key) {
+ if (value != 0) *value = (st_data_t)table->bins[i*2+1];
+ table->num_entries--;
+ memmove(&table->bins[i*2], &table->bins[(i+1)*2],
+ sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
+ return 1;
+ }
+ }
+ if (value != 0) *value = 0;
+ return 0;
+ }
+
hash_val = do_hash_bin(*key, table);
for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) {
@@ -479,6 +566,40 @@
enum st_retval retval;
int i, end;
+ if (table->entries_packed) {
+ for (i = 0; i < table->num_entries; i++) {
+ int j;
+ st_data_t key, val;
+ key = (st_data_t)table->bins[i*2];
+ val = (st_data_t)table->bins[i*2+1];
+ retval = (*func)(key, val, arg);
+ switch (retval) {
+ case ST_CHECK: /* check if hash is modified during iteration */
+ for (j = 0; j < table->num_entries; j++) {
+ if ((st_data_t)table->bins[j*2] == key)
+ break;
+ }
+ if (j == table->num_entries) {
+ /* call func with error notice */
+ retval = (*func)(0, 0, arg, 1);
+ return 1;
+ }
+ /* fall through */
+ case ST_CONTINUE:
+ break;
+ case ST_STOP:
+ return 0;
+ case ST_DELETE:
+ table->num_entries--;
+ memmove(&table->bins[i*2], &table->bins[(i+1)*2],
+ sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
+ i--;
+ break;
+ }
+ }
+ return 0;
+ }
+
if ((ptr = table->head) != 0) {
do {
end = ptr->fore == table->head;
@@ -525,6 +646,39 @@
enum st_retval retval;
int i, end;
+ if (table->entries_packed) {
+ for (i = table->num_entries-1; 0 <= i; i--) {
+ int j;
+ st_data_t key, val;
+ key = (st_data_t)table->bins[i*2];
+ val = (st_data_t)table->bins[i*2+1];
+ retval = (*func)(key, val, arg);
+ switch (retval) {
+ case ST_CHECK: /* check if hash is modified during iteration */
+ for (j = 0; j < table->num_entries; j++) {
+ if ((st_data_t)table->bins[j*2] == key)
+ break;
+ }
+ if (j == table->num_entries) {
+ /* call func with error notice */
+ retval = (*func)(0, 0, arg, 1);
+ return 1;
+ }
+ /* fall through */
+ case ST_CONTINUE:
+ break;
+ case ST_STOP:
+ return 0;
+ case ST_DELETE:
+ table->num_entries--;
+ memmove(&table->bins[i*2], &table->bins[(i+1)*2],
+ sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
+ break;
+ }
+ }
+ return 0;
+ }
+
if ((ptr = table->head) != 0) {
ptr = ptr->back;
do {
--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml