Create a gist now

Instantly share code, notes, and snippets.

@funny-falcon /falcon-st.c Secret
Last active Nov 6, 2016

st.c after preprocessor
/*
cpp -I. -I.ext/include/x86_64-linux -I../include -I.. -I../enc/unicode/9.0.0 ../st.c | \
sed -n '/need_shrink/,/st_seed/ p' | \
grep -v -e '^\s*\([{};]\|break;\)\?\s*$' -e '^\(#\|static\|int\|void\|st_\|size_t\)[^(]*$'
*/
need_shrink(st_idx_t num_entries, int sz)
st_idx_t nen = st_sz[sz].nentries;
return sz > 1 && num_entries < nen / 2;
do_hash(st_data_t key, const st_table * table)
st_index_t h = table->use_strong == 0 ? (*table->type->hash)(key) :
(*table->type->stronghash)(key);
return h != (0) ? h : 0x71fe900d;
bin_size(int sz)
st_idx_t nen = st_sz[sz].nentries;
return nen < 255 ? 1 : (nen < 65535 ? 2 : sizeof(st_idx_t));
bins_size(int sz)
return (ssize_t)st_sz[sz].nbins * bin_size(sz);
entries_size(int sz)
return bins_size(sz) + st_sz[sz].nentries*sizeof(st_table_entry);
base_ptr(st_table_entry* e, int sz)
return (char*)e - bins_size(sz);
entries_ptr(char* e, int sz)
return (st_table_entry*)(e + bins_size(sz));
static st_idx_t fake_bins[2] = {(0x00) , (0x00) };
st_free_data(st_table_entry* entries, int sz)
if (sz != 0) {
ruby_xfree((base_ptr(entries, sz)));
st_grow_data(st_table_entry *e, int newsz, int oldsz)
if (oldsz == 0) {
if (newsz != 0) {
char* bins = ruby_xcalloc(1, entries_size(newsz));
memset(bins, (0x00), bins_size(newsz));
return entries_ptr(bins, newsz);
} else {
return (st_table_entry*)(fake_bins + 1);
} else if (newsz == 0) {
ruby_xfree((base_ptr(e, oldsz)));
return (st_table_entry*)(fake_bins + 1);
} else {
char* vbins = base_ptr(e, oldsz);
ssize_t bins_old = bins_size(oldsz);
ssize_t bins_new = bins_size(newsz);
if (bins_old > bins_new) {
memmove((vbins + bins_new), (vbins + bins_old), sizeof(st_table_entry)*(st_sz[newsz].nentries));
memset(vbins, (0x00), bins_new);
vbins = ruby_xrealloc((vbins), (entries_size(newsz)));
if (bins_old < bins_new) {
memmove((vbins + bins_new), (vbins + bins_old), sizeof(st_table_entry)*(st_sz[oldsz].nentries));
memset(vbins, (0x00), bins_new);
return entries_ptr(vbins, newsz);
new_sz(st_index_t size)
int i;
for (i = 1; st_sz[i].nentries != 0; i++)
if (st_sz[i].nentries >= size)
return i;
rb_raise(rb_eRuntimeError, "st_table too big");
return -1;
st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
st_table *tbl;
tbl = (st_table *)ruby_xcalloc(1, sizeof(st_table));
tbl->type = type;
tbl->num_entries = 0;
tbl->sz = new_sz(size);
tbl->as.entries = st_grow_data((0), tbl->sz, 0);
tbl->rebuild_num = 0;
tbl->first = 0;
tbl->last = 0;
return tbl;
st_init_table(const struct st_hash_type *type)
return st_init_table_with_size(type, 0);
st_init_numtable(void)
return st_init_table(&st_hashtype_num);
st_init_numtable_with_size(st_index_t size)
return st_init_table_with_size(&st_hashtype_num, size);
st_init_strtable(void)
return st_init_table(&type_strhash);
st_init_strtable_with_size(st_index_t size)
return st_init_table_with_size(&type_strhash, size);
st_init_strcasetable(void)
return st_init_table(&type_strcasehash);
st_init_strcasetable_with_size(st_index_t size)
return st_init_table_with_size(&type_strcasehash, size);
st_clear(st_table *table)
st_free_data(table->as.entries, table->sz);
table->sz = 0;
table->num_entries = 0;
table->as.bins = &fake_bins[1];
table->rebuild_num++;
table->first = 0;
table->last = 0;
st_free_table(st_table *table)
st_clear(table);
ruby_xfree((table));
st_memsize(const st_table *table)
return sizeof(st_table) + entries_size(table->sz);
bin_get(const void *bins, int sz, st_idx_t bin_pos)
st_idx_t idx;
st_idx_t nentries = st_sz[sz].nentries;
if ((__builtin_expect(!!(nentries < 255), 1))) {
idx = ((uint8_t*)bins)[((ssize_t)-1)-bin_pos];
} else if (nentries < 65535) {
idx = ((uint16_t*)bins)[((ssize_t)-1)-bin_pos];
} else {
idx = ((st_idx_t*)bins)[((ssize_t)-1)-bin_pos];
return idx;
bin_set(const void *bins, int sz, st_idx_t bin_pos, st_idx_t idx)
st_idx_t nentries = st_sz[sz].nentries;
if ((__builtin_expect(!!(nentries < 255), 1))) {
((uint8_t*)bins)[((ssize_t)-1)-bin_pos] = (uint8_t)idx;
} else if ((__builtin_expect(!!(nentries < 65535), 1))) {
((uint16_t*)bins)[((ssize_t)-1)-bin_pos] = (uint16_t)idx;
} else {
((st_idx_t*)bins)[((ssize_t)-1)-bin_pos] = idx;
EQUAL(const st_table *table, st_data_t key, const st_table_entry* ptr) {
return key == ptr->key || (*table->type->compare)(key, ptr->key) == 0;
find_entry(const st_table *table, st_data_t key, st_index_t hash_val)
st_table_entry* ptr;
if (table->sz <= 1) {
st_table_entry *end = table->as.entries + table->last;
ptr = table->as.entries + table->first;
for (; ptr < end; ptr++)
if (ptr->hash == hash_val && EQUAL(table, key, ptr))
return ptr;
return (0);
} else {
const void* bins = table->as.bins;
st_table_entry* entries = table->as.entries - 1;
int sz = table->sz;
st_idx_t flpos = (st_idx_t)(hash_val), fldlt = 1; st_index_t flmix = (((hash_val))<<(17)|((hash_val))>>(8*8 -(17)));
for (;;(flpos += fldlt++), (fldlt += (st_idx_t)(flmix >>= 7))) {
st_idx_t idx = bin_get(bins, sz, ((flpos) & (st_sz[(table)->sz].nbins-1)));
if (idx == (0)) break;
ptr = entries + idx;
if (ptr->hash == hash_val && EQUAL(table, key, ptr))
return ptr;
return (0);
find_exact_key(const st_table *table, st_data_t key, st_index_t hash_val)
st_table_entry* ptr;
if (table->sz <= 1) {
st_table_entry *end = table->as.entries + table->last;
ptr = table->as.entries + table->first;
for (; ptr < end; ptr++) {
if (ptr->hash == hash_val && ptr->key == key)
return ptr;
return (0);
} else {
const void* bins = table->as.bins;
st_table_entry* entries = table->as.entries - 1;
int sz = table->sz;
st_idx_t flpos = (st_idx_t)(hash_val), fldlt = 1; st_index_t flmix = (((hash_val))<<(17)|((hash_val))>>(8*8 -(17)));
for (;;(flpos += fldlt++), (fldlt += (st_idx_t)(flmix >>= 7))) {
st_idx_t idx = bin_get(bins, sz, ((flpos) & (st_sz[(table)->sz].nbins-1)));
if (idx == (0)) break;
ptr = entries + idx;
if (ptr->hash == hash_val && ptr->key == key)
return ptr;
return (0);
insert_entry_simple(st_table* table, st_index_t hash_val, st_idx_t idx)
const void* bins = table->as.bins;
int sz = table->sz;
st_idx_t bin_pos;
st_idx_t flpos = (st_idx_t)(hash_val), fldlt = 1; st_index_t flmix = (((hash_val))<<(17)|((hash_val))>>(8*8 -(17)));
for (;;(flpos += fldlt++), (fldlt += (st_idx_t)(flmix >>= 7))) {
bin_pos = ((flpos) & (st_sz[(table)->sz].nbins-1));
if (bin_get(bins, sz, bin_pos) == (0))
bin_set(bins, sz, bin_pos, idx+1);
insert_entry_reuse(st_table* table, st_index_t hash_val, st_idx_t idx)
const void* bins = table->as.bins;
const st_table_entry* entries = table->as.entries;
int sz = table->sz;
int cnt = 0;
int reuse = table->num_entries != table->last;
st_idx_t bin_pos, old;
st_idx_t flpos = (st_idx_t)(hash_val), fldlt = 1; st_index_t flmix = (((hash_val))<<(17)|((hash_val))>>(8*8 -(17)));
for (;;(flpos += fldlt++), (fldlt += (st_idx_t)(flmix >>= 7)), cnt++) {
bin_pos = ((flpos) & (st_sz[(table)->sz].nbins-1));
old = bin_get(bins, sz, bin_pos);
if (old == (0) || (reuse && entries[((old)-1)].hash == (0)))
bin_set(bins, sz, bin_pos, idx+1);
return cnt >= 40;
st_lookup(st_table *table, register st_data_t key, st_data_t *value)
st_table_entry* ptr = find_entry(table, key, do_hash(key, table));
if (ptr != (0)) {
if (value != 0) *value = ptr->record;
return 1;
return 0;
st_get_key(st_table *table, register st_data_t key, st_data_t *result)
st_table_entry* ptr = find_entry(table, key, do_hash(key, table));
if (ptr != (0)) {
if (result != 0) *result = ptr->key;
return 1;
return 0;
add_direct(st_table *table, st_data_t key, st_data_t value,
st_index_t hash_val)
register st_table_entry *entry;
st_idx_t en_idx;
if (table->last == st_sz[table->sz].nentries) {
st_rehash(table);
en_idx = table->last;
table->last++;
table->num_entries++;
entry = &table->as.entries[en_idx];
entry->hash = hash_val;
entry->key = key;
entry->record = value;
if (table->sz > 1) {
int attack = insert_entry_reuse(table, hash_val, en_idx);
if ((__builtin_expect(!!(attack), 0)) && !table->use_strong && table->type->stronghash != (0)) {
table->use_strong = 1;
st_recalc_hashvals(table);
st_insert(register st_table *table, register st_data_t key, st_data_t value)
st_index_t hash_val = do_hash(key, table);
st_table_entry* ptr = find_entry(table, key, hash_val);
if (ptr == (0)) {
add_direct(table, key, value, hash_val);
return 0;
else {
ptr->record = value;
return 1;
st_insert2(register st_table *table, register st_data_t key, st_data_t value,
st_data_t (*func)(st_data_t))
st_index_t hash_val;
st_table_entry* ptr;
st_idx_t rebuild_num __attribute__((unused)) = table->rebuild_num;
hash_val = do_hash(key, table);
ptr = find_entry(table, key, hash_val);
if (ptr == (0)) {
key = (*func)(key);
add_direct(table, key, value, hash_val);
return 0;
else {
ptr->record = value;
return 1;
st_add_direct(st_table *table, st_data_t key, st_data_t value)
add_direct(table, key, value, do_hash(key, table));
st_reclaim_without_bins(register st_table *table)
st_idx_t i;
st_table_entry *ptr, *optr;
ptr = table->as.entries;
optr = &table->as.entries[table->first];
for (i = table->last - table->first; i; i--, optr++) {
if (optr->hash != (0)) {
if (ptr != optr) *ptr = *optr;
ptr++;
table->first = 0;
table->last = (st_idx_t)(ptr - table->as.entries);
st_fix_bins(st_table *table)
if (st_sz[table->sz].nbins != 0) {
st_idx_t i;
st_table_entry* ptr;
memset(base_ptr(table->as.entries, table->sz), (0x00), bins_size(table->sz));
ptr = table->as.entries + table->first;
for (i = table->first; i < table->last; i++, ptr++) {
if (ptr->hash != (0)) {
insert_entry_simple(table, ptr->hash, i);
st_shrink(st_table *table)
unsigned sz = table->sz;
while (need_shrink(table->num_entries, sz))
sz--;
sz++;
table->as.entries = st_grow_data(table->as.entries, sz, table->sz);
table->sz = sz;
st_rehash(register st_table *table)
table->rebuild_num++;
if (need_shrink(table->num_entries, table->sz)) {
st_reclaim_without_bins(table);
if (need_shrink(table->num_entries, table->sz-1)) {
st_shrink(table);
if (st_sz[table->sz].nbins != 0) {
st_fix_bins(table);
return;
if (st_sz[table->sz + 1].nentries == 0) {
rb_raise(rb_eRuntimeError, "hash is too big");
table->as.entries = st_grow_data(table->as.entries, table->sz+1, table->sz);
table->sz++;
if (bins_size(table->sz) != bins_size(table->sz-1)) {
st_fix_bins(table);
st_recalc_hashvals(st_table *table)
st_idx_t i;
st_table_entry *ptr;
ptr = table->as.entries + table->first;
for (i = table->first; i < table->last; i++, ptr++) {
if (ptr->hash != (0)) {
ptr->hash = do_hash(ptr->key, table);
st_fix_bins(table);
table->rebuild_num++;
st_copy(st_table *old_table)
st_table *new_table;
new_table = (st_table *)ruby_xcalloc(1, sizeof(st_table));
*new_table = *old_table;
if (old_table->as.entries) {
new_table->as.entries = ruby_xmalloc(entries_size(new_table->sz));
memcpy(new_table->as.entries, base_ptr(old_table->as.entries, old_table->sz),
entries_size(new_table->sz));
new_table->as.entries = entries_ptr((char*)new_table->as.entries, new_table->sz);
return new_table;
remove_entry(st_table *table, st_table_entry* ptr)
table->num_entries--;
ptr->hash = (0);
ptr->key = ptr->record = 0;
if (table->as.entries + table->first == ptr) {
do {
table->first++;
ptr++;
} while (table->first < table->last && ptr->hash == (0));
st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
st_index_t hash_val;
register st_table_entry *ptr;
st_idx_t rebuild_num __attribute__((unused)) = table->rebuild_num;
hash_val = do_hash(*key, table);
ptr = find_entry(table, *key, hash_val);
if (ptr != (0)) {
if (value != 0) *value = ptr->record;
*key = ptr->key;
remove_entry(table, ptr);
return 1;
if (value != 0) *value = 0;
return 0;
st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never __attribute__((unused)))
return st_delete(table, key, value);
st_shift(register st_table *table, register st_data_t *key, st_data_t *value)
st_table_entry *ptr;
st_idx_t idx;
if (table->num_entries == 0) {
if (value != 0) *value = 0;
return 0;
idx = table->first;
ptr = &table->as.entries[idx];
if (value != 0) *value = ptr->record;
*key = ptr->key;
remove_entry(table, ptr);
return 1;
st_cleanup_safe(st_table *table, st_data_t never __attribute__((unused)))
st_idx_t head;
if (table->sz == 0)
return;
if (need_shrink(table->num_entries, table->sz-1)) {
st_rehash(table);
return;
head = table->first;
while (head < table->last && table->as.entries[head].hash == (0))
head++;
table->first = head;
st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg)
st_index_t hash_val;
register st_table_entry *ptr;
st_idx_t rebuild_num __attribute__((unused)) = table->rebuild_num;
st_data_t value = 0, old_key;
int retval, existing = 0;
hash_val = do_hash(key, table);
ptr = find_entry(table, key, hash_val);
if (ptr != (0)) {
key = ptr->key;
value = ptr->record;
existing = 1;
old_key = key;
retval = (*func)(&key, &value, arg, existing);
((rebuild_num == table->rebuild_num) ? (void)0 : __assert_fail("rebuild_num == table->rebuild_num"));
switch (retval) {
case ST_CONTINUE:
if (!existing) {
add_direct(table, key, value, hash_val);
if (old_key != key) {
ptr->key = key;
ptr->record = value;
case ST_DELETE:
if (existing) {
remove_entry(table, ptr);
return existing;
st_foreach(st_table *table, int (*func)(), st_data_t arg)
st_table_entry *ptr = 0;
enum st_retval retval;
st_idx_t rebuild_num = table->rebuild_num;
st_idx_t idx;
st_index_t hash;
st_data_t key;
ptr = table->as.entries + table->first;
for (idx = table->first; idx < table->last; idx++, ptr++) {
if ((__builtin_expect(!!(ptr->hash != (0)), 1))) {
key = ptr->key;
hash = ptr->hash;
retval = (*func)(key, ptr->record, arg, 0);
if ((__builtin_expect(!!(rebuild_num != table->rebuild_num), 0))) {
ptr = find_exact_key(table, key, hash);
if (ptr == (0)) {
((retval == ST_CHECK) ? (void)0 : __assert_fail("retval == ST_CHECK"));
(*func)(0, 0, arg, 1);
return 1;
} else {
rebuild_num = table->rebuild_num;
idx = ptr - table->as.entries;;
switch (retval) {
case ST_CHECK:
case ST_CONTINUE:
case ST_STOP:
return 0;
case ST_DELETE:
if (ptr->hash != (0)) {
remove_entry(table, ptr);
if (table->num_entries == 0) return 0;
return 0;
st_foreach_check(st_table *table, int (*func)(), st_data_t arg, st_data_t never __attribute__((unused)))
return st_foreach(table, func, arg);
get_keys(const st_table *table, st_data_t *keys, st_index_t size)
st_data_t *keys_start = keys;
st_data_t *keys_end = keys + size;
st_table_entry *ptr = table->as.entries + table->first;
st_table_entry *end = table->as.entries + table->last;
for (; ptr != end; ptr++) {
if (ptr->hash != (0)) {
if (keys >= keys_end) break;
*keys++ = ptr->key;
return keys - keys_start;
st_keys(st_table *table, st_data_t *keys, st_index_t size)
return get_keys(table, keys, size);
st_keys_check(st_table *table, st_data_t *keys, st_index_t size,
st_data_t never __attribute__((unused)))
return get_keys(table, keys, size);
get_values(const st_table *table, st_data_t *values, st_index_t size)
st_data_t *values_start = values;
st_data_t *values_end = values + size;
st_table_entry *ptr = table->as.entries + table->first;
st_table_entry *end = table->as.entries + table->last;
for (; ptr != end; ptr++) {
if (ptr->hash != (0)) {
if (values >= values_end) break;
*values++ = ptr->record;
return values - values_start;
st_values(st_table *table, st_data_t *values, st_index_t size)
return get_values(table, values, size);
st_values_check(st_table *table, st_data_t *values, st_index_t size,
st_data_t never __attribute__((unused)))
return get_values(table, values, size);
/*
cpp -I. -I.ext/include/x86_64-linux -I../include -I.. -I../enc/unicode/9.0.0 ../st.c | \
sed -n '/do_hash/,/murmur/ p' | \
grep -v -e '^\s*\([{};]\|break;\)\?\s*$' -e '^\(#\|static\|int\|void\|st_\|size_t\)[^(]*$'
*/
do_hash(st_data_t key, st_table *tab) {
st_index_t h = (st_index_t)(tab->curr_hash)(key);
st_hash_t hash = h;
return hash == (~(st_hash_t) 0) ? ((st_hash_t) 0) : hash;
get_power2(st_index_t size) {
unsigned int n;
for (n = 0; size != 0; n++)
size >>= 1;
if (n <= 62)
return n < 2 ? 2 : n;
rb_raise(rb_eRuntimeError, "st_table too big");
return -1;
get_bin(st_index_t *bins, int s, st_index_t n) {
return (s == 0 ? ((unsigned char *) bins)[n]
: s == 1 ? ((unsigned short *) bins)[n]
: s == 2 ? ((unsigned int *) bins)[n]
: ((st_index_t *) bins)[n]);
set_bin(st_index_t *bins, int s, st_index_t n, st_index_t v) {
if (s == 0) ((unsigned char *) bins)[n] = (unsigned char) v;
else if (s == 1) ((unsigned short *) bins)[n] = (unsigned short) v;
else if (s == 2) ((unsigned int *) bins)[n] = (unsigned int) v;
else ((st_index_t *) bins)[n] = v;
get_size_ind(const st_table *tab) {
return tab->size_ind;
get_bins_num(const st_table *tab) {
return 1<<tab->bin_power;
bins_mask(const st_table *tab) {
return get_bins_num(tab) - 1;
hash_bin(st_hash_t hash_value, st_table *tab) {
return hash_value & bins_mask(tab);
get_allocated_entries(const st_table *tab) {
return 1<<tab->entry_power;
bins_size(const st_table *tab) {
return features[tab->entry_power].bins_words * sizeof (st_index_t);
initialize_bins(st_table *tab) {
memset(tab->bins, 0, bins_size(tab));
make_tab_empty(st_table *tab)
tab->curr_hash = tab->type->hash;
tab->num_entries = 0;
tab->entries_start = tab->entries_bound = 0;
if (tab->bins != (0))
initialize_bins(tab);
st_init_table_with_size(const struct st_hash_type *type, st_index_t size) {
st_table *tab;
int n;
n = get_power2(size);
tab = (st_table *) ruby_xmalloc(sizeof (st_table));
tab->type = type;
tab->entry_power = n;
tab->bin_power = features[n].bin_power;
tab->size_ind = features[n].size_ind;
tab->inside_rebuild_p = FALSE;
if (n <= 4)
tab->bins = (0);
else
tab->bins = (st_index_t *) ruby_xmalloc(bins_size(tab));
tab->entries = (st_table_entry *) ruby_xmalloc(get_allocated_entries(tab)
* sizeof(st_table_entry));
make_tab_empty(tab);
tab->rebuilds_num = 0;
return tab;
st_init_table(const struct st_hash_type *type) {
return st_init_table_with_size(type, 0);
st_init_numtable(void) {
return st_init_table(&st_hashtype_num);
st_init_numtable_with_size(st_index_t size) {
return st_init_table_with_size(&st_hashtype_num, size);
st_init_strtable(void) {
return st_init_table(&type_strhash);
st_init_strtable_with_size(st_index_t size) {
return st_init_table_with_size(&type_strhash, size);
st_init_strcasetable(void) {
return st_init_table(&type_strcasehash);
st_init_strcasetable_with_size(st_index_t size) {
return st_init_table_with_size(&type_strcasehash, size);
st_clear(st_table *tab) {
make_tab_empty(tab);
tab->rebuilds_num++;
st_free_table(st_table *tab) {
if (tab->bins != (0))
ruby_xfree(tab->bins);
ruby_xfree(tab->entries);
ruby_xfree(tab);
st_memsize(const st_table *tab) {
return(sizeof(st_table)
+ (tab->bins == (0) ? 0 : bins_size(tab))
+ get_allocated_entries(tab) * sizeof(st_table_entry));
find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key);
find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key);
find_table_bin_ind_direct(st_table *table, st_hash_t hash_value, st_data_t key);
find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
st_data_t key, st_index_t *bin_ind);
rebuild_table(st_table *tab) {
st_index_t i, ni, bound;
unsigned int size_ind;
st_table *new_tab;
st_table_entry *entries, *new_entries;
st_table_entry *curr_entry_ptr;
st_index_t *bins;
st_index_t bin_ind;
bound = tab->entries_bound;
entries = tab->entries;
tab->inside_rebuild_p = TRUE;
if ((2 * tab->num_entries <= get_allocated_entries(tab)
&& 4 * tab->num_entries > get_allocated_entries(tab))
|| tab->num_entries < (1 << 2)) {
tab->num_entries = 0;
if (tab->bins != (0))
initialize_bins(tab);
new_tab = tab;
new_entries = entries;
else {
new_tab = st_init_table_with_size(tab->type,
2 * tab->num_entries - 1);
new_tab->curr_hash = tab->curr_hash;
new_entries = new_tab->entries;
ni = 0;
bins = new_tab->bins;
size_ind = get_size_ind(new_tab);
for (i = tab->entries_start; i < bound; i++) {
curr_entry_ptr = &entries[i];
__builtin_prefetch(entries + i + 1, 0);
if (__builtin_expect(((curr_entry_ptr)->hash == (~(st_hash_t) 0)), 0))
continue;
if (&new_entries[ni] != curr_entry_ptr)
new_entries[ni] = *curr_entry_ptr;
if (__builtin_expect(bins != (0), 1)) {
bin_ind = find_table_bin_ind_direct(new_tab, curr_entry_ptr->hash,
curr_entry_ptr->key);
set_bin(bins, size_ind, bin_ind, ni + 2);
new_tab->num_entries++;
ni++;
if (new_tab != tab) {
tab->entry_power = new_tab->entry_power;
tab->bin_power = new_tab->bin_power;
tab->size_ind = new_tab->size_ind;
if (tab->bins != (0))
ruby_xfree(tab->bins);
tab->bins = new_tab->bins;
ruby_xfree(tab->entries);
tab->entries = new_tab->entries;
ruby_xfree(new_tab);
tab->entries_start = 0;
tab->entries_bound = tab->num_entries;
tab->rebuilds_num++;
tab->inside_rebuild_p = FALSE;
secondary_hash(st_index_t ind, st_table *tab, st_index_t *perterb) {
*perterb >>= 11;
ind = (ind << 2) + ind + *perterb + 1;
return hash_bin(ind, tab);
find_entry(st_table *tab, st_hash_t hash_value, st_data_t key) {
st_index_t i, bound;
st_table_entry *entries;
bound = tab->entries_bound;
entries = tab->entries;
for (i = tab->entries_start; i < bound; i++) {
if (((&entries[i])->hash == (hash_value) && (((key)) == ((&entries[i])->key) || (*((tab))->type->compare)(((key)),((&entries[i])->key)) == 0)))
return i;
return (~(st_index_t) 0);
find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key) {
st_index_t ind;
st_index_t peterb;
st_index_t bin;
st_table_entry *entries = tab->entries;
ind = hash_bin(hash_value, tab);
peterb = hash_value;
for (;;) {
bin = get_bin(tab->bins, get_size_ind(tab), ind);
if (! ((bin) <= 1)
&& ((&entries[bin - 2])->hash == (hash_value) && (((key)) == ((&entries[bin - 2])->key) || (*((tab))->type->compare)(((key)),((&entries[bin - 2])->key)) == 0)))
else if (((bin) == 0))
return (~(st_index_t) 0);
ind = secondary_hash(ind, tab, &peterb);
return bin;
find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key) {
st_index_t ind;
st_index_t peterb;
st_index_t bin;
st_table_entry *entries = tab->entries;
ind = hash_bin(hash_value, tab);
peterb = hash_value;
for (;;) {
bin = get_bin(tab->bins, get_size_ind(tab), ind);
if (! ((bin) <= 1)
&& ((&entries[bin - 2])->hash == (hash_value) && (((key)) == ((&entries[bin - 2])->key) || (*((tab))->type->compare)(((key)),((&entries[bin - 2])->key)) == 0)))
else if (((bin) == 0))
return (~(st_index_t) 0);
ind = secondary_hash(ind, tab, &peterb);
return ind;
find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key) {
st_index_t ind;
st_index_t peterb;
st_index_t bin;
st_table_entry *entries = tab->entries;
ind = hash_bin(hash_value, tab);
peterb = hash_value;
for (;;) {
bin = get_bin(tab->bins, get_size_ind(tab), ind);
if (((bin) <= 1))
return ind;
ind = secondary_hash(ind, tab, &peterb);
reset_entry_hashes (st_table *tab)
st_index_t i, bound;
st_table_entry *entries, *curr_entry_ptr;
bound = tab->entries_bound;
entries = tab->entries;
for (i = tab->entries_start; i < bound; i++) {
curr_entry_ptr = &entries[i];
if (! ((curr_entry_ptr)->hash == (~(st_hash_t) 0)))
curr_entry_ptr->hash = do_hash(curr_entry_ptr->key, tab);
find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
st_data_t key, st_index_t *bin_ind) {
st_index_t ind;
st_hash_t curr_hash_value = *hash_value;
st_index_t peterb;
st_index_t entry_index;
st_index_t first_deleted_bin_ind;
st_table_entry *entries;
int hit;
repeat:
ind = hash_bin(curr_hash_value, tab);
peterb = curr_hash_value;
first_deleted_bin_ind = (~(st_index_t) 0);
entries = tab->entries;
hit = 0;
for (;;) {
entry_index = get_bin(tab->bins, get_size_ind(tab), ind);
if (((entry_index) == 0)) {
tab->num_entries++;
entry_index = (~(st_index_t) 0);
if (first_deleted_bin_ind != (~(st_index_t) 0)) {
ind = first_deleted_bin_ind;
(set_bin((tab)->bins, get_size_ind(tab), ind, 0));
} else if (! ((entry_index) == 1)) {
if (((&entries[entry_index - 2])->hash == (curr_hash_value) && (((key)) == ((&entries[entry_index - 2])->key) || (*((tab))->type->compare)(((key)),((&entries[entry_index - 2])->key)) == 0)))
if (curr_hash_value == entries[entry_index - 2].hash) {
hit++;
if (hit > 10
&& tab->curr_hash != tab->type->strong_hash
&& tab->type->strong_hash != (0)
&& ! tab->inside_rebuild_p) {
tab->curr_hash = tab->type->strong_hash;
*hash_value = curr_hash_value = do_hash(key, tab);
reset_entry_hashes(tab);
rebuild_table(tab);
goto repeat;
} else if (first_deleted_bin_ind == (~(st_index_t) 0))
first_deleted_bin_ind = ind;
ind = secondary_hash(ind, tab, &peterb);
*bin_ind = ind;
return entry_index;
st_lookup(st_table *tab, st_data_t key, st_data_t *value) {
st_index_t bin;
st_hash_t hash = do_hash(key, tab);
if (tab->bins == (0)) {
bin = find_entry(tab, hash, key);
if (bin == (~(st_index_t) 0))
return 0;
} else {
bin = find_table_entry_ind(tab, hash, key);
if (bin == (~(st_index_t) 0))
return 0;
bin -= 2;
if (value != 0)
*value = tab->entries[bin].record;
return 1;
st_get_key(st_table *tab, st_data_t key, st_data_t *result) {
st_index_t bin;
st_hash_t hash = do_hash(key, tab);
if (tab->bins == (0)) {
bin = find_entry(tab, hash, key);
if (bin == (~(st_index_t) 0))
return 0;
} else {
bin = find_table_entry_ind(tab, hash, key);
if (bin == (~(st_index_t) 0))
return 0;
bin -= 2;
if (result != 0)
*result = tab->entries[bin].key;
return 1;
rebuild_table_if_necessary (st_table *tab) {
st_index_t bound = tab->entries_bound;
if (bound == get_allocated_entries(tab))
rebuild_table(tab);
st_insert(st_table *tab, st_data_t key, st_data_t value) {
st_table_entry *entry;
st_index_t bin;
st_index_t ind;
st_hash_t hash_value;
st_index_t bin_ind;
int new_p;
rebuild_table_if_necessary(tab);
hash_value = do_hash(key, tab);
if (tab->bins == (0)) {
bin = find_entry(tab, hash_value, key);
new_p = bin == (~(st_index_t) 0);
if (new_p)
tab->num_entries++;
bin_ind = (~(st_index_t) 0);
} else {
bin = find_table_bin_ptr_and_reserve(tab, &hash_value,
key, &bin_ind);
new_p = bin == (~(st_index_t) 0);
bin -= 2;
if (new_p) {
ind = tab->entries_bound++;
entry = &tab->entries[ind];
entry->hash = hash_value;
entry->key = key;
entry->record = value;
if (bin_ind != (~(st_index_t) 0))
set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + 2);
return 0;
tab->entries[bin].record = value;
return 1;
st_data_t key, st_data_t value, st_hash_t hash) {
st_table_entry *entry;
st_index_t ind;
st_index_t bin_ind;
rebuild_table_if_necessary(tab);
ind = tab->entries_bound++;
entry = &tab->entries[ind];
entry->hash = hash;
entry->key = key;
entry->record = value;
tab->num_entries++;
if (tab->bins != (0)) {
bin_ind = find_table_bin_ind_direct(tab, hash, key);
set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + 2);
st_add_direct(st_table *tab, st_data_t key, st_data_t value) {
st_hash_t hash_value;
hash_value = do_hash(key, tab);
st_add_direct_with_hash(tab, key, value, hash_value);
st_data_t (*func)(st_data_t)) {
st_table_entry *entry;
st_index_t bin;
st_index_t ind, check;
st_hash_t hash_value;
st_index_t bin_ind;
int new_p;
rebuild_table_if_necessary (tab);
hash_value = do_hash(key, tab);
if (tab->bins == (0)) {
bin = find_entry(tab, hash_value, key);
new_p = bin == (~(st_index_t) 0);
bin_ind = (~(st_index_t) 0);
} else {
bin = find_table_bin_ptr_and_reserve(tab, &hash_value,
key, &bin_ind);
new_p = bin == (~(st_index_t) 0);
bin -= 2;
if (new_p) {
check = tab->rebuilds_num;
key = (*func)(key);
ind = tab->entries_bound++;
entry = &tab->entries[ind];
entry->hash = hash_value;
entry->key = key;
entry->record = value;
if (bin_ind != (~(st_index_t) 0))
set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + 2);
return 0;
tab->entries[bin].record = value;
return 1;
st_copy(st_table *old_tab) {
st_table *new_tab;
new_tab = (st_table *) ruby_xmalloc(sizeof(st_table));
*new_tab = *old_tab;
if (old_tab->bins == (0))
new_tab->bins = (0);
else
new_tab->bins = (st_index_t *) ruby_xmalloc(bins_size(old_tab));
new_tab->entries = (st_table_entry *) ruby_xmalloc(get_allocated_entries(old_tab)
* sizeof(st_table_entry));
memcpy((new_tab->entries), (old_tab->entries), sizeof(st_table_entry)*(get_allocated_entries(old_tab)))
if (old_tab->bins != (0))
memcpy((new_tab->bins), (old_tab->bins), sizeof(char)*(bins_size(old_tab)));
return new_tab;
update_range_for_deleted(st_table *tab, st_index_t n) {
if (tab->entries_start == n)
tab->entries_start = n + 1;
st_general_delete(st_table *tab, st_data_t *key, st_data_t *value)
st_table_entry *entry;
st_index_t bin;
st_index_t bin_ind;
st_hash_t hash;
hash = do_hash(*key, tab);
if (tab->bins == (0)) {
bin = find_entry(tab, hash, *key);
if (bin == (~(st_index_t) 0)) {
if (value != 0) *value = 0;
return 0;
} else {
bin_ind = find_table_bin_ind(tab, hash, *key);
if (bin_ind == (~(st_index_t) 0)) {
if (value != 0) *value = 0;
return 0;
bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - 2;
do { ; ; set_bin((tab)->bins, get_size_ind(tab), bin_ind, 1); } while (0);
entry = &tab->entries[bin];
*key = entry->key;
if (value != 0) *value = entry->record;
((entry)->hash = (~(st_hash_t) 0));
tab->num_entries--;
update_range_for_deleted(tab, bin);
return 1;
st_delete(st_table *tab, st_data_t *key, st_data_t *value) {
return st_general_delete(tab, key, value);
st_data_t never __attribute__((unused))) {
return st_general_delete(tab, key, value);
st_shift(st_table *tab, st_data_t *key, st_data_t *value) {
st_index_t i, bound;
st_index_t bin;
st_table_entry *entries, *curr_entry_ptr;
st_index_t bin_ind;
entries = tab->entries;
bound = tab->entries_bound;
for (i = tab->entries_start; i < bound; i++) {
curr_entry_ptr = &entries[i];
if (! ((curr_entry_ptr)->hash == (~(st_hash_t) 0))) {
if (value != 0) *value = curr_entry_ptr->record;
*key = curr_entry_ptr->key;
if (tab->bins == (0)) {
bin = find_entry(tab, curr_entry_ptr->hash, curr_entry_ptr->key);
} else {
bin_ind = find_table_bin_ind(tab, curr_entry_ptr->hash,
curr_entry_ptr->key);
do { ; ; set_bin((tab)->bins, get_size_ind(tab), bin_ind, 1); } while (0);
((curr_entry_ptr)->hash = (~(st_hash_t) 0));
tab->num_entries--;
update_range_for_deleted(tab, i);
return 1;
tab->entries_start = tab->entries_bound = 0;
if (value != 0) *value = 0;
return 0;
st_cleanup_safe(st_table *tab __attribute__((unused)),
st_data_t never __attribute__((unused))) {
st_update_callback_func *func, st_data_t arg) {
st_table_entry *entry = (0);
st_index_t bin = 0;
st_table_entry *entries;
st_index_t bin_ind;
st_data_t value = 0, old_key;
st_index_t check;
int retval, existing;
st_hash_t hash = do_hash(key, tab);
entries = tab->entries;
if (tab->bins == (0)) {
bin = find_entry(tab, hash, key);
existing = bin != (~(st_index_t) 0);
entry = &entries[bin];
bin_ind = (~(st_index_t) 0);
} else {
bin_ind = find_table_bin_ind(tab, hash, key);
existing = bin_ind != (~(st_index_t) 0);
if (existing) {
bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - 2;
entry = &entries[bin];
if (existing) {
key = entry->key;
value = entry->record;
old_key = key;
check = tab->rebuilds_num;
retval = (*func)(&key, &value, arg, existing);
switch (retval) {
case ST_CONTINUE:
if (! existing) {
st_add_direct_with_hash(tab, key, value, hash);
if (old_key != key) {
entry->key = key;
entry->record = value;
case ST_DELETE:
if (existing) {
if (bin_ind != (~(st_index_t) 0))
do { ; ; set_bin((tab)->bins, get_size_ind(tab), bin_ind, 1); } while (0);
((entry)->hash = (~(st_hash_t) 0));
tab->num_entries--;
update_range_for_deleted(tab, bin);
return existing;
st_general_foreach(st_table *tab, int (*func)(), st_data_t arg,
int check_p) {
st_index_t bin;
st_index_t bin_ind;
st_table_entry *entries, *curr_entry_ptr;
enum st_retval retval;
st_index_t i, rebuilds_num;
st_hash_t hash;
st_data_t key;
int error_p, packed_p = tab->bins == (0);
entries = tab->entries;
for (i = tab->entries_start; i < tab->entries_bound; i++) {
curr_entry_ptr = &entries[i];
if (__builtin_expect(((curr_entry_ptr)->hash == (~(st_hash_t) 0)), 0))
continue;
key = curr_entry_ptr->key;
rebuilds_num = tab->rebuilds_num;
hash = curr_entry_ptr->hash;
retval = (*func)(key, curr_entry_ptr->record, arg, 0);
if (rebuilds_num != tab->rebuilds_num) {
entries = tab->entries;
packed_p = tab->bins == (0);
if (packed_p) {
i = find_entry(tab, hash, key);
error_p = i == (~(st_index_t) 0);
} else {
i = find_table_entry_ind(tab, hash, key);
error_p = i == (~(st_index_t) 0);
i -= 2;
if (error_p && check_p) {
retval = (*func)(0, 0, arg, 1);
return 1;
curr_entry_ptr = &entries[i];
switch (retval) {
case ST_CONTINUE:
case ST_CHECK:
if (check_p)
case ST_STOP:
return 0;
case ST_DELETE:
if (packed_p) {
bin = find_entry(tab, hash, curr_entry_ptr->key);
if (bin == (~(st_index_t) 0))
} else {
bin_ind = find_table_bin_ind(tab, hash, curr_entry_ptr->key);
if (bin_ind == (~(st_index_t) 0))
bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - 2;
do { ; ; set_bin((tab)->bins, get_size_ind(tab), bin_ind, 1); } while (0);
((curr_entry_ptr)->hash = (~(st_hash_t) 0));
tab->num_entries--;
update_range_for_deleted(tab, bin);
return 0;
st_foreach(st_table *tab, int (*func)(), st_data_t arg) {
return st_general_foreach(tab, func, arg, FALSE);
st_foreach_check(st_table *tab, int (*func)(), st_data_t arg,
st_data_t never __attribute__((unused))) {
return st_general_foreach(tab, func, arg, TRUE);
st_general_keys(st_table *tab, st_data_t *keys, st_index_t size) {
st_index_t i, bound;
st_data_t key, *keys_start, *keys_end;
st_table_entry *curr_entry_ptr, *entries = tab->entries;
bound = tab->entries_bound;
keys_start = keys;
keys_end = keys + size;
for (i = tab->entries_start; i < bound; i++) {
if (keys == keys_end)
curr_entry_ptr = &entries[i];
key = curr_entry_ptr->key;
if (! ((curr_entry_ptr)->hash == (~(st_hash_t) 0)))
*keys++ = key;
return keys - keys_start;
st_keys(st_table *tab, st_data_t *keys, st_index_t size) {
return st_general_keys(tab, keys, size);
st_data_t never __attribute__((unused))) {
return st_general_keys(tab, keys, size);
st_general_values(st_table *tab, st_data_t *values, st_index_t size) {
st_index_t i, bound;
st_data_t *values_start, *values_end;
st_table_entry *curr_entry_ptr, *entries = tab->entries;
values_start = values;
values_end = values + size;
bound = tab->entries_bound;
for (i = tab->entries_start; i < bound; i++) {
if (values == values_end)
curr_entry_ptr = &entries[i];
if (! ((curr_entry_ptr)->hash == (~(st_hash_t) 0)))
*values++ = curr_entry_ptr->record;
return values - values_start;
st_values(st_table *tab, st_data_t *values, st_index_t size) {
return st_general_values(tab, values, size);
st_data_t never __attribute__((unused))) {
return st_general_values(tab, values, size);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment