From: Nobuyoshi Nakada Date: 2007-09-04T17:43:49+09:00 Subject: [ruby-dev:31729] packed st_table なかだです。 田中さんに「Hashの順序はどっちでもいいからこっちをやれ」といわれ たので、st_tableのentries_packedを一般化してみました。 Index: st.c =================================================================== --- st.c (revision 13339) +++ st.c (working copy) @@ -61,5 +61,4 @@ static void rehash(st_table *); #define alloc(type) (type*)malloc((size_t)sizeof(type)) -#define Calloc(n,s) (char*)calloc((n),(s)) #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0) @@ -77,5 +76,5 @@ static void rehash(st_table *); Table of prime numbers 2^n+a, 2<=n<=30. */ -static long primes[] = { +static const unsigned int primes[] = { 8 + 3, 16 + 3, @@ -110,5 +109,5 @@ static long primes[] = { static int -new_size(int size) +new_size(unsigned int size) { int i; @@ -120,8 +119,8 @@ new_size(int size) return -1; #else - int newsize; + unsigned int newsize; for (i = 0, newsize = MINSIZE; - i < (int )(sizeof(primes)/sizeof(primes[0])); + i < (int)(sizeof(primes)/sizeof(primes[0])) - 1; i++, newsize <<= 1) { @@ -146,5 +145,12 @@ stat_col() #endif -#define MAX_PACKED_NUMHASH 5 +#define PACKED_RATIO(table) ((table)->type == &type_numhash ? 2 : 3) +#define PACKED_COUNT(table, n) ((n) * PACKED_RATIO(table)) +#define PACKABLE(table, n) \ + ((n) * PACKED_RATIO(table) <= ST_DEFAULT_INIT_TABLE_SIZE) + +#define PACKED_EQUAL(table, i, r, hash_val, key)\ + (((r) < 3 || (st_data_t)(table)->bins[(i)+2] == (hash_val)) &&\ + EQUAL((table), (st_data_t)(table)->bins[i], (key))) st_table* @@ -161,11 +167,12 @@ st_init_table_with_size(const struct st_ size = new_size(size); /* round up to prime number */ + if (size == -1) return 0; 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->entries_packed = 1; + tbl->num_bins = 0; + tbl->bins = calloc(size, sizeof(st_table_entry*)); tbl->head = 0; @@ -207,8 +214,9 @@ st_clear(st_table *table) { register st_table_entry *ptr, *next; - int i; + unsigned int i; if (table->entries_packed) { table->num_entries = 0; + table->num_bins = 0; return; } @@ -263,10 +271,12 @@ st_lookup(st_table *table, register st_d 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; - } + unsigned int i, hash_val; + const unsigned int r = PACKED_RATIO(table); + hash_val = r > 2 ? do_hash(key, table) : key; + for (i = 0; i < table->num_bins; i += r) { + if (PACKED_EQUAL(table, i, r, hash_val, key)) { + if (value != 0) *value = (st_data_t)table->bins[i+1]; + return 1; + } } return 0; @@ -314,17 +324,45 @@ 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; + struct st_table_entry *packed_bins[ST_DEFAULT_INIT_TABLE_SIZE]; + unsigned int i, num_bins = table->num_bins; + const unsigned int r = PACKED_RATIO(table); - memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * num_entries*2); + memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * num_bins); table->entries_packed = 0; table->num_entries = 0; + table->num_bins = ST_DEFAULT_INIT_TABLE_SIZE; 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]); + for (i = 0; i < num_bins; i += r) { + st_data_t key = (st_data_t)packed_bins[i]; + st_data_t value = (st_data_t)packed_bins[i+1]; + unsigned int hash_val, bin_pos; + + hash_val = r > 2 ? (unsigned int)packed_bins[i+2] : key; + bin_pos = hash_val % table->num_bins; + ADD_DIRECT(table, key, value, hash_val, bin_pos); } } +static int +add_direct_packed(register st_table *table, const unsigned int r, + st_data_t key, st_data_t value, unsigned int hash_val) +{ + unsigned int i; + + if (table->num_bins >= ST_DEFAULT_INIT_TABLE_SIZE / r * r) { + table->bins = xrealloc(table->bins, sizeof(struct st_table_entry *) * (table->num_bins+r)); + } + else if (!PACKABLE(table, table->num_bins+r)) { + return 0; + } + i = table->num_bins; + table->num_bins += r; + table->num_entries++; + table->bins[i] = (struct st_table_entry*)key; + table->bins[i+1] = (struct st_table_entry*)value; + if (r > 2) table->bins[i+2] = (struct st_table_entry*)hash_val; + return 1; +} + int st_insert(register st_table *table, register st_data_t key, st_data_t value) @@ -334,20 +372,17 @@ st_insert(register st_table *table, regi 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; + unsigned int i, hash_val; + const unsigned int r = PACKED_RATIO(table); + hash_val = r > 2 ? do_hash(key, table) : key; + for (i = 0; i < table->num_bins; i += r) { + if (PACKED_EQUAL(table, i, r, hash_val, key)) { + table->bins[i+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; + if (add_direct_packed(table, r, key, value, hash_val)) { return 0; } - else { - unpack_entries(table); - } + unpack_entries(table); } @@ -371,14 +406,11 @@ st_add_direct(st_table *table, st_data_t 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; + unsigned int hash_val; + const unsigned int r = PACKED_RATIO(table); + hash_val = r > 2 ? do_hash(key, table) : key; + if (add_direct_packed(table, r, key, value, hash_val)) { return; } - else { - unpack_entries(table); - } + unpack_entries(table); } @@ -392,10 +424,11 @@ rehash(register st_table *table) { register st_table_entry *ptr, **new_bins; - int i, new_num_bins; + unsigned int i, new_num_bins; unsigned int hash_val; + int size = new_size(table->num_bins+1); - new_num_bins = new_size(table->num_bins+1); - new_bins = (st_table_entry**) - xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*)); + if (size == -1) return; + new_num_bins = (unsigned int)size; + new_bins = 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; @@ -416,5 +449,5 @@ st_copy(st_table *old_table) st_table *new_table; st_table_entry *ptr, *entry, *prev, **tail; - int num_bins = old_table->num_bins; + unsigned int num_bins = old_table->num_bins; unsigned int hash_val; @@ -425,6 +458,5 @@ st_copy(st_table *old_table) *new_table = *old_table; - new_table->bins = (st_table_entry**) - Calloc((unsigned)num_bins, sizeof(st_table_entry*)); + new_table->bins = calloc(num_bins, sizeof(st_table_entry*)); if (new_table->bins == 0) { @@ -485,11 +517,14 @@ st_delete(register st_table *table, regi 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]; + unsigned int i; + const unsigned int r = PACKED_RATIO(table); + hash_val = r > 2 ? do_hash(*key, table) : 0; + for (i = 0; i < table->num_bins; i += r) { + if (PACKED_EQUAL(table, i, r, hash_val, *key)) { + if (value != 0) *value = (st_data_t)table->bins[i+1]; table->num_entries--; - memmove(&table->bins[i*2], &table->bins[(i+1)*2], - sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); + table->num_bins -= r; + memmove(&table->bins[i], &table->bins[i+r], + sizeof(struct st_table_entry*) * (table->num_bins-i)); return 1; } @@ -522,4 +557,20 @@ st_delete_safe(register st_table *table, register st_table_entry *ptr; + if (table->entries_packed) { + unsigned int i; + const unsigned int r = PACKED_RATIO(table); + hash_val = r > 2 ? do_hash(*key, table) : 0; + for (i = 0; i < table->num_bins; i += r) { + if (PACKED_EQUAL(table, i, r, hash_val, *key)) { + if (value != 0) *value = (st_data_t)table->bins[i+1]; + table->num_entries--; + table->bins[i] = table->bins[i+1] = (struct st_table_entry *)never; + return 1; + } + } + if (value != 0) *value = 0; + return 0; + } + hash_val = do_hash_bin(*key, table); ptr = table->bins[hash_val]; @@ -543,5 +594,18 @@ st_cleanup_safe(st_table *table, st_data { st_table_entry *ptr, **last, *tmp; - int i; + unsigned int i; + + if (table->entries_packed) { + unsigned int j; + const unsigned int r = PACKED_RATIO(table); + for (i = j = 0; i < table->num_bins; i += r) { + if ((st_data_t)table->bins[i] != never && i > j) { + memcpy(&table->bins[j], table->bins[i], + sizeof(st_table_entry *) * r); + j++; + } + } + return; + } for (i = 0; i < table->num_bins; i++) { @@ -565,24 +629,16 @@ st_foreach(st_table *table, int (*func)( st_table_entry *ptr, **last, *tmp; enum st_retval retval; - int i, end; + unsigned int i; + int end; if (table->entries_packed) { - for (i = 0; i < table->num_entries; i++) { - int j; + const unsigned int r = PACKED_RATIO(table); + for (i = 0; i < table->num_bins; i += r) { st_data_t key, val; - key = (st_data_t)table->bins[i*2]; - val = (st_data_t)table->bins[i*2+1]; + key = (st_data_t)table->bins[i]; + val = (st_data_t)table->bins[i+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: @@ -592,7 +648,7 @@ st_foreach(st_table *table, int (*func)( 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--; + if (i >= (table->num_bins -= r)) return 0; + memmove(&table->bins[i], &table->bins[i+1], + sizeof(struct st_table_entry*) * (table->num_bins-i)); break; } @@ -645,24 +701,17 @@ st_reverse_foreach(st_table *table, int st_table_entry *ptr, **last, *tmp; enum st_retval retval; - int i, end; + unsigned int i; + int end; if (table->entries_packed) { - for (i = table->num_entries-1; 0 <= i; i--) { - int j; + const unsigned int r = PACKED_RATIO(table); + for (i = table->num_bins; i > 0;) { st_data_t key, val; - key = (st_data_t)table->bins[i*2]; - val = (st_data_t)table->bins[i*2+1]; + i -= r; + key = (st_data_t)table->bins[i]; + val = (st_data_t)table->bins[i+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: @@ -672,6 +721,7 @@ st_reverse_foreach(st_table *table, int 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)); + if (i >= (table->num_bins -= r)) break; + memmove(&table->bins[i], &table->bins[i+1], + sizeof(struct st_table_entry*) * (table->num_bins-i)); break; } -- --- 僕の前にBugはない。 --- 僕の後ろにBugはできる。 中田 伸悦