Feature #9425 ยป 0001-st-use-power-of-two-sizes-to-avoid-slow-modulo-ops.patch
st.c | ||
---|---|---|
#define STATIC_ASSERT(name, expr) typedef int static_assert_##name##_check[(expr) ? 1 : -1];
|
||
#define ST_DEFAULT_MAX_DENSITY 5
|
||
#define ST_DEFAULT_INIT_TABLE_SIZE 11
|
||
#define ST_DEFAULT_SECOND_TABLE_SIZE 19
|
||
#define ST_DEFAULT_INIT_TABLE_SIZE 16
|
||
#define ST_DEFAULT_SECOND_TABLE_SIZE 32
|
||
#define ST_DEFAULT_PACKED_TABLE_SIZE 18
|
||
#define PACKED_UNIT (int)(sizeof(st_packed_entry) / sizeof(st_table_entry*))
|
||
#define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry))
|
||
... | ... | |
#define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
|
||
#define do_hash(key,table) (st_index_t)(*(table)->type->hash)((key))
|
||
#define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
|
||
#define HMASK(tbl) ((tbl)->num_bins-1)
|
||
#define do_hash_bin(key,table) (do_hash((key), (table))&(HMASK(table)))
|
||
/* preparation for possible allocation improvements */
|
||
#define st_alloc_entry() (st_table_entry *)malloc(sizeof(st_table_entry))
|
||
... | ... | |
PHASH_SET(table, i, 0);
|
||
}
|
||
/*
|
||
* MINSIZE is the minimum size of a dictionary.
|
||
*/
|
||
#define MINSIZE 8
|
||
/*
|
||
Table of prime numbers 2^n+a, 2<=n<=30.
|
||
*/
|
||
static const unsigned int primes[] = {
|
||
ST_DEFAULT_INIT_TABLE_SIZE,
|
||
ST_DEFAULT_SECOND_TABLE_SIZE,
|
||
32 + 5,
|
||
64 + 3,
|
||
128 + 3,
|
||
256 + 27,
|
||
512 + 9,
|
||
1024 + 9,
|
||
2048 + 5,
|
||
4096 + 3,
|
||
8192 + 27,
|
||
16384 + 43,
|
||
32768 + 3,
|
||
65536 + 45,
|
||
131072 + 29,
|
||
262144 + 3,
|
||
524288 + 21,
|
||
1048576 + 7,
|
||
2097152 + 17,
|
||
4194304 + 15,
|
||
8388608 + 9,
|
||
16777216 + 43,
|
||
33554432 + 35,
|
||
67108864 + 15,
|
||
134217728 + 29,
|
||
268435456 + 3,
|
||
536870912 + 11,
|
||
1073741824 + 85,
|
||
0
|
||
};
|
||
static st_index_t
|
||
new_size(st_index_t size)
|
||
{
|
||
int i;
|
||
st_index_t i;
|
||
#if 0
|
||
for (i=3; i<31; i++) {
|
||
if ((1<<i) > size) return 1<<i;
|
||
}
|
||
return -1;
|
||
#else
|
||
st_index_t newsize;
|
||
for (i = 0, newsize = MINSIZE; i < numberof(primes); i++, newsize <<= 1) {
|
||
if (newsize > size) return primes[i];
|
||
if ((st_index_t)(1<<i) > size) return 1<<i;
|
||
}
|
||
/* Ran out of primes */
|
||
#ifndef NOT_RUBY
|
||
rb_raise(rb_eRuntimeError, "st_table too big");
|
||
#endif
|
||
return -1; /* should raise exception */
|
||
#endif
|
||
}
|
||
#ifdef HASH_LOG
|
||
... | ... | |
#endif
|
||
#define FIND_ENTRY(table, ptr, hash_val, bin_pos) \
|
||
((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = (hash_val)%(table)->num_bins)))
|
||
((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = (hash_val)&(HMASK(table)))))
|
||
static st_table_entry *
|
||
find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos)
|
||
... | ... | |
return 0;
|
||
}
|
||
ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);
|
||
ptr = find_entry(table, key, hash_val, hash_val & HMASK(table));
|
||
if (ptr == 0) {
|
||
return 0;
|
||
... | ... | |
return 0;
|
||
}
|
||
ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);
|
||
ptr = find_entry(table, key, hash_val, hash_val & HMASK(table));
|
||
if (ptr == 0) {
|
||
return 0;
|
||
... | ... | |
register st_table_entry *entry;
|
||
if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) {
|
||
rehash(table);
|
||
bin_pos = hash_val % table->num_bins;
|
||
bin_pos = hash_val & HMASK(table);
|
||
}
|
||
entry = new_entry(table, key, value, hash_val, bin_pos);
|
||
... | ... | |
st_data_t val = packed_bins[i].val;
|
||
st_index_t hash = packed_bins[i].hash;
|
||
entry = new_entry(&tmp_table, key, val, hash,
|
||
hash % ST_DEFAULT_INIT_TABLE_SIZE);
|
||
hash & (ST_DEFAULT_INIT_TABLE_SIZE - 1));
|
||
*chain = entry;
|
||
entry->back = preventry;
|
||
preventry = entry;
|
||
... | ... | |
}
|
||
else {
|
||
unpack_entries(table);
|
||
add_direct(table, key, value, hash_val, hash_val % table->num_bins);
|
||
add_direct(table, key, value, hash_val, hash_val & HMASK(table));
|
||
}
|
||
}
|
||
... | ... | |
return;
|
||
}
|
||
add_direct(table, key, value, hash_val, hash_val % table->num_bins);
|
||
add_direct(table, key, value, hash_val, hash_val & HMASK(table));
|
||
}
|
||
static void
|
||
... | ... | |
if ((ptr = table->head) != 0) {
|
||
do {
|
||
hash_val = ptr->hash % new_num_bins;
|
||
hash_val = ptr->hash & (new_num_bins - 1);
|
||
ptr->next = new_bins[hash_val];
|
||
new_bins[hash_val] = ptr;
|
||
} while ((ptr = ptr->fore) != 0);
|
||
... | ... | |
return 0;
|
||
}
|
||
*entry = *ptr;
|
||
hash_val = entry->hash % num_bins;
|
||
hash_val = entry->hash & (num_bins - 1);
|
||
entry->next = new_table->bins[hash_val];
|
||
new_table->bins[hash_val] = entry;
|
||
entry->back = prev;
|
||
... | ... | |
return 0;
|
||
}
|
||
prev = &table->bins[hash_val % table->num_bins];
|
||
prev = &table->bins[hash_val & HMASK(table)];
|
||
for (;(ptr = *prev) != 0; prev = &ptr->next) {
|
||
if (EQUAL(table, *key, ptr->key)) {
|
||
*prev = ptr->next;
|
||
... | ... | |
return 0;
|
||
}
|
||
ptr = table->bins[hash_val % table->num_bins];
|
||
ptr = table->bins[hash_val & HMASK(table)];
|
||
for (; ptr != 0; ptr = ptr->next) {
|
||
if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
|
||
... | ... | |
return 1;
|
||
}
|
||
prev = &table->bins[table->head->hash % table->num_bins];
|
||
prev = &table->bins[table->head->hash & HMASK(table)];
|
||
while ((ptr = *prev) != table->head) prev = &ptr->next;
|
||
*prev = ptr->next;
|
||
if (value != 0) *value = ptr->record;
|
||
... | ... | |
switch (retval) {
|
||
case ST_CONTINUE:
|
||
if (!existing) {
|
||
add_direct(table, key, value, hash_val, hash_val % table->num_bins);
|
||
add_direct(table, key, value, hash_val, hash_val & HMASK(table));
|
||
break;
|
||
}
|
||
ptr->record = value;
|
||
... | ... | |
do {
|
||
if (ptr->key == never)
|
||
goto unpacked_continue;
|
||
i = ptr->hash % table->num_bins;
|
||
i = ptr->hash & HMASK(table);
|
||
retval = (*func)(ptr->key, ptr->record, arg, 0);
|
||
unpacked:
|
||
switch (retval) {
|
||
... | ... | |
case ST_STOP:
|
||
return 0;
|
||
case ST_DELETE:
|
||
last = &table->bins[ptr->hash % table->num_bins];
|
||
last = &table->bins[ptr->hash & HMASK(table)];
|
||
for (; (tmp = *last) != 0; last = &tmp->next) {
|
||
if (ptr == tmp) {
|
||
tmp = ptr->fore;
|
||
... | ... | |
if (ptr != 0) {
|
||
do {
|
||
i = ptr->hash % table->num_bins;
|
||
i = ptr->hash & HMASK(table);
|
||
retval = (*func)(ptr->key, ptr->record, arg, 0);
|
||
unpacked:
|
||
switch (retval) {
|
||
... | ... | |
case ST_STOP:
|
||
return 0;
|
||
case ST_DELETE:
|
||
last = &table->bins[ptr->hash % table->num_bins];
|
||
last = &table->bins[ptr->hash & HMASK(table)];
|
||
for (; (tmp = *last) != 0; last = &tmp->next) {
|
||
if (ptr == tmp) {
|
||
tmp = ptr->fore;
|
||
... | ... | |
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;
|
||
i = ptr->hash & HMASK(table));
|
||
for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
|
||
if (!tmp) {
|
||
/* call func with error notice */
|
||
... | ... | |
case ST_STOP:
|
||
return 0;
|
||
case ST_DELETE:
|
||
last = &table->bins[ptr->hash % table->num_bins];
|
||
last = &table->bins[ptr->hash & HMASK(table)];
|
||
for (; (tmp = *last) != 0; last = &tmp->next) {
|
||
if (ptr == tmp) {
|
||
tmp = ptr->back;
|