summaryrefslogtreecommitdiff
path: root/st.c
diff options
context:
space:
mode:
authorshyouhei <shyouhei@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2012-01-15 15:46:34 +0000
committershyouhei <shyouhei@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2012-01-15 15:46:34 +0000
commitcada5343a6fb66185f7e34da71b42d8fa5765935 (patch)
treee5aabb3d5fb478c52f2d7bac40c085beb0fb369d /st.c
parent978a4ef1542cbce0b70e8391795b031483409a43 (diff)
downloadruby-cada5343a6fb66185f7e34da71b42d8fa5765935.tar.gz
st macroses for packed table
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@34310 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'st.c')
-rw-r--r--st.c92
1 files changed, 49 insertions, 43 deletions
diff --git a/st.c b/st.c
index 9f2432d81c..01687f62b9 100644
--- a/st.c
+++ b/st.c
@@ -27,6 +27,8 @@ struct st_table_entry {
#define ST_DEFAULT_MAX_DENSITY 5
#define ST_DEFAULT_INIT_TABLE_SIZE 11
+#define ST_DEFAULT_SECOND_TABLE_SIZE 19
+#define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
/*
* DEFAULT_MAX_DENSITY is the default for the largest we allow the
@@ -76,6 +78,24 @@ static void rehash(st_table *);
#define do_hash(key,table) (unsigned int)(st_index_t)(*(table)->type->hash)((key))
#define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
+/* preparation for possible packing improvements */
+#define PKEY_POS(i, num_bins) ((i)*2)
+#define PVAL_POS(i, num_bins) ((i)*2+1)
+#define PKEY(table, i) (st_data_t)(table)->bins[PKEY_POS(i, (table)->num_bins)]
+#define PVAL(table, i) (st_data_t)(table)->bins[PVAL_POS(i, (table)->num_bins)]
+#define PKEY_SET(table, i, v) do{ (table)->bins[PKEY_POS(i, (table)->num_bins)] = (st_table_entry *)(v); } while(0)
+#define PVAL_SET(table, i, v) do{ (table)->bins[PVAL_POS(i, (table)->num_bins)] = (st_table_entry *)(v); } while(0)
+/* this function depends much on packed layout, so that it placed here */
+static inline void
+remove_packed_entry(st_table *table, st_index_t i)
+{
+ table->num_entries--;
+ if (i < table->num_entries) {
+ memmove(table->bins + 2*i, table->bins + 2*(i+1),
+ sizeof(st_table_entry *) * 2 * (table->num_entries - i));
+ }
+}
+
/*
* MINSIZE is the minimum size of a dictionary.
*/
@@ -87,7 +107,7 @@ Table of prime numbers 2^n+a, 2<=n<=30.
*/
static const unsigned int primes[] = {
ST_DEFAULT_INIT_TABLE_SIZE,
- 16 + 3,
+ ST_DEFAULT_SECOND_TABLE_SIZE,
32 + 5,
64 + 3,
128 + 3,
@@ -162,8 +182,6 @@ stat_col(void)
}
#endif
-#define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
-
st_table*
st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
{
@@ -326,7 +344,7 @@ static inline st_index_t
find_packed_index(st_table *table, st_data_t key)
{
st_index_t i = 0;
- while (i < table->num_entries && (st_data_t)table->bins[i*2] != key) i++;
+ while (i < table->num_entries && PKEY(table, i) != key) i++;
return i;
}
@@ -341,7 +359,7 @@ st_lookup(st_table *table, register st_data_t key, st_data_t *value)
if (table->entries_packed) {
st_index_t i = find_packed_index(table, key);
if (i < table->num_entries) {
- if (value != 0) *value = (st_data_t)table->bins[i*2+1];
+ if (value != 0) *value = PVAL(table, i);
return 1;
}
return 0;
@@ -368,7 +386,7 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
if (table->entries_packed) {
st_index_t i = find_packed_index(table, key);
if (i < table->num_entries) {
- if (result != 0) *result = (st_data_t)table->bins[i*2];
+ if (result != 0) *result = PKEY(table, i);
return 1;
}
return 0;
@@ -389,10 +407,6 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result)
#undef collision_check
#define collision_check 1
-#define MORE_PACKABLE_P(table) \
- ((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \
- (table)->num_entries+1 <= MAX_PACKED_NUMHASH)
-
static void
add_direct(st_table * table, st_data_t key, st_data_t value,
st_index_t hash_val, st_index_t bin_pos)
@@ -426,16 +440,18 @@ static void
unpack_entries(register st_table *table)
{
st_index_t i;
- struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2];
+ struct st_table_entry *packed_bins[ST_DEFAULT_INIT_TABLE_SIZE];
st_table tmp_table = *table;
- memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * table->num_entries*2);
+ memcpy(packed_bins, table->bins, sizeof(st_table_entry *) * ST_DEFAULT_INIT_TABLE_SIZE);
table->bins = packed_bins;
tmp_table.entries_packed = 0;
tmp_table.num_entries = 0;
memset(tmp_table.bins, 0, sizeof(struct st_table_entry *) * tmp_table.num_bins);
for (i = 0; i < table->num_entries; i++) {
- st_insert(&tmp_table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]);
+ st_index_t hash_val = PKEY(table, i); /* do_hash(PKEY(table, i), &tmp_table); */
+ add_direct(&tmp_table, PKEY(table, i), PVAL(table, i),
+ hash_val, hash_val % tmp_table.num_bins);
}
*table = tmp_table;
}
@@ -444,10 +460,10 @@ static int
add_packed_direct(st_table *table, st_data_t key, st_data_t value)
{
int res = 1;
- if (MORE_PACKABLE_P(table)) {
+ if (table->num_entries < MAX_PACKED_NUMHASH) {
st_index_t i = table->num_entries++;
- table->bins[i*2] = (struct st_table_entry*)key;
- table->bins[i*2+1] = (struct st_table_entry*)value;
+ PKEY_SET(table, i, key);
+ PVAL_SET(table, i, value);
}
else {
unpack_entries(table);
@@ -466,7 +482,7 @@ st_insert(register st_table *table, register st_data_t key, st_data_t value)
if (table->entries_packed) {
st_index_t i = find_packed_index(table, key);
if (i < table->num_entries) {
- table->bins[i*2+1] = (struct st_table_entry*)value;
+ PVAL_SET(table, i, value);
return 1;
}
if (add_packed_direct(table, key, value)) {
@@ -498,7 +514,7 @@ st_insert2(register st_table *table, register st_data_t key, st_data_t value,
if (table->entries_packed) {
st_index_t i = find_packed_index(table, key);
if (i < table->num_entries) {
- table->bins[i*2+1] = (struct st_table_entry*)value;
+ PVAL_SET(table, i, value);
return 1;
}
if (add_packed_direct(table, key, value)) {
@@ -626,16 +642,6 @@ remove_entry(st_table *table, st_table_entry *ptr)
table->num_entries--;
}
-static inline void
-remove_packed_entry(st_table *table, st_index_t pos)
-{
- table->num_entries--;
- if (pos < table->num_entries) {
- memmove(&table->bins[pos*2], &table->bins[(pos+1)*2],
- sizeof(struct st_table_entry*) * 2*(table->num_entries-pos));
- }
-}
-
int
st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
{
@@ -646,7 +652,7 @@ st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
if (table->entries_packed) {
st_index_t i = find_packed_index(table, *key);
if (i < table->num_entries) {
- if (value != 0) *value = (st_data_t)table->bins[i*2+1];
+ if (value != 0) *value = PVAL(table, i);
remove_packed_entry(table, i);
return 1;
}
@@ -680,8 +686,8 @@ st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *val
if (table->entries_packed) {
st_index_t i = find_packed_index(table, *key);
if (i < table->num_entries) {
- if (value != 0) *value = (st_data_t)table->bins[i*2+1];
- table->bins[i*2] = (void *)never;
+ if (value != 0) *value = PVAL(table, i);
+ PKEY_SET(table, i, never);
return 1;
}
if (value != 0) *value = 0;
@@ -713,13 +719,13 @@ st_cleanup_safe(st_table *table, st_data_t never)
if (table->entries_packed) {
st_index_t i = 0, j = 0;
- while ((st_data_t)table->bins[i*2] != never) {
+ while (PKEY(table, i) != never) {
if (i++ == table->num_entries) return;
}
for (j = i; ++i < table->num_entries;) {
- if ((st_data_t)table->bins[i*2] == never) continue;
- table->bins[j*2] = table->bins[i*2];
- table->bins[j*2+1] = table->bins[i*2+1];
+ if (PKEY(table, i) == never) continue;
+ PKEY_SET(table, j, PKEY(table, i));
+ PVAL_SET(table, j, PVAL(table, i));
j++;
}
table->num_entries = j;
@@ -751,10 +757,10 @@ st_update(st_table *table, st_data_t key, int (*func)(st_data_t key, st_data_t *
if (table->entries_packed) {
st_index_t i = find_packed_index(table, key);
if (i < table->num_entries) {
- value = (st_data_t)table->bins[i*2+1];
+ value = PVAL(table, i);
switch ((*func)(key, &value, arg)) {
case ST_CONTINUE:
- table->bins[i*2+1] = (struct st_table_entry*)value;
+ PVAL_SET(table, i, value);
break;
case ST_DELETE:
remove_packed_entry(table, i);
@@ -805,14 +811,14 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
for (i = 0; i < table->num_entries; i++) {
st_index_t j;
st_data_t key, val;
- key = (st_data_t)table->bins[i*2];
- val = (st_data_t)table->bins[i*2+1];
+ key = PKEY(table, i);
+ val = PVAL(table, i);
retval = (*func)(key, val, arg);
if (!table->entries_packed) goto unpacked;
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)
+ if (PKEY(table, j) == key)
break;
}
if (j == table->num_entries) {
@@ -892,13 +898,13 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
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];
+ key = PKEY(table, i);
+ val = PVAL(table, i);
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)
+ if (PKEY(table, j) == key)
break;
}
if (j == table->num_entries) {