-
-
Save funny-falcon/581ecf363c4aa7d8ac1d805473080a1b to your computer and use it in GitHub Desktop.
st.c after preprocessor
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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