summaryrefslogtreecommitdiff
path: root/st.c
diff options
context:
space:
mode:
authorTakashi Kokubun <takashikkbn@gmail.com>2022-07-21 09:23:58 -0700
committerTakashi Kokubun <takashikkbn@gmail.com>2022-07-21 09:42:04 -0700
commit5b21e94bebed90180d8ff63dad03b8b948361089 (patch)
treef9f7196d84b51b7a3a8001658e4391a63b71c396 /st.c
parent3ff53c8e04ecc91e0190de6d5950ecce2a2ea188 (diff)
Expand tabs [ci skip]
[Misc #18891]
Notes
Notes: Merged: https://github.com/ruby/ruby/pull/6094
Diffstat (limited to 'st.c')
-rw-r--r--st.c634
1 files changed, 317 insertions, 317 deletions
diff --git a/st.c b/st.c
index c4966f1d8c..6b534a856a 100644
--- a/st.c
+++ b/st.c
@@ -181,9 +181,9 @@ static const struct st_hash_type type_strcasehash = {
up to TRUE if the table is rebuilt during the comparison. */
#define DO_PTR_EQUAL_CHECK(tab, ptr, hash_val, key, res, rebuilt_p) \
do { \
- unsigned int _old_rebuilds_num = (tab)->rebuilds_num; \
- res = PTR_EQUAL(tab, ptr, hash_val, key); \
- rebuilt_p = _old_rebuilds_num != (tab)->rebuilds_num; \
+ unsigned int _old_rebuilds_num = (tab)->rebuilds_num; \
+ res = PTR_EQUAL(tab, ptr, hash_val, key); \
+ rebuilt_p = _old_rebuilds_num != (tab)->rebuilds_num; \
} while (FALSE)
/* Features of a table. */
@@ -356,9 +356,9 @@ static inline st_index_t
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]);
+ : s == 1 ? ((unsigned short *) bins)[n]
+ : s == 2 ? ((unsigned int *) bins)[n]
+ : ((st_index_t *) bins)[n]);
}
/* Set up N-th bin in array BINS of table with bins size index S to
@@ -557,7 +557,7 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
#endif
}
tab->entries = (st_table_entry *) malloc(get_allocated_entries(tab)
- * sizeof(st_table_entry));
+ * sizeof(st_table_entry));
#ifndef RUBY
if (tab->entries == NULL) {
st_free_table(tab);
@@ -661,7 +661,7 @@ find_table_bin_ind_direct(st_table *table, st_hash_t hash_value, st_data_t key);
static st_index_t
find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
- st_data_t key, st_index_t *bin_ind);
+ st_data_t key, st_index_t *bin_ind);
#ifdef HASH_LOG
static void
@@ -714,48 +714,48 @@ rebuild_table(st_table *tab)
bound = tab->entries_bound;
entries = tab->entries;
if ((2 * tab->num_entries <= get_allocated_entries(tab)
- && REBUILD_THRESHOLD * tab->num_entries > get_allocated_entries(tab))
- || tab->num_entries < (1 << MINIMAL_POWER2)) {
+ && REBUILD_THRESHOLD * tab->num_entries > get_allocated_entries(tab))
+ || tab->num_entries < (1 << MINIMAL_POWER2)) {
/* Compaction: */
tab->num_entries = 0;
- if (tab->bins != NULL)
- initialize_bins(tab);
- new_tab = tab;
- new_entries = entries;
+ if (tab->bins != NULL)
+ 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_entries = new_tab->entries;
+ 2 * tab->num_entries - 1);
+ 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];
- PREFETCH(entries + i + 1, 0);
- if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 0))
- continue;
- if (&new_entries[ni] != curr_entry_ptr)
- new_entries[ni] = *curr_entry_ptr;
- if (EXPECT(bins != NULL, 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 + ENTRY_BASE);
- }
- new_tab->num_entries++;
- ni++;
+ PREFETCH(entries + i + 1, 0);
+ if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 0))
+ continue;
+ if (&new_entries[ni] != curr_entry_ptr)
+ new_entries[ni] = *curr_entry_ptr;
+ if (EXPECT(bins != NULL, 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 + ENTRY_BASE);
+ }
+ 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 != NULL)
- free(tab->bins);
- tab->bins = new_tab->bins;
- free(tab->entries);
- tab->entries = new_tab->entries;
- free(new_tab);
+ tab->bin_power = new_tab->bin_power;
+ tab->size_ind = new_tab->size_ind;
+ if (tab->bins != NULL)
+ free(tab->bins);
+ tab->bins = new_tab->bins;
+ free(tab->entries);
+ tab->entries = new_tab->entries;
+ free(new_tab);
}
tab->entries_start = 0;
tab->entries_bound = tab->num_entries;
@@ -796,11 +796,11 @@ find_entry(st_table *tab, st_hash_t hash_value, st_data_t key)
bound = tab->entries_bound;
entries = tab->entries;
for (i = tab->entries_start; i < bound; i++) {
- DO_PTR_EQUAL_CHECK(tab, &entries[i], hash_value, key, eq_p, rebuilt_p);
- if (EXPECT(rebuilt_p, 0))
- return REBUILT_TABLE_ENTRY_IND;
- if (eq_p)
- return i;
+ DO_PTR_EQUAL_CHECK(tab, &entries[i], hash_value, key, eq_p, rebuilt_p);
+ if (EXPECT(rebuilt_p, 0))
+ return REBUILT_TABLE_ENTRY_IND;
+ if (eq_p)
+ return i;
}
return UNDEFINED_ENTRY_IND;
}
@@ -836,17 +836,17 @@ find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key)
for (;;) {
bin = get_bin(tab->bins, get_size_ind(tab), ind);
if (! EMPTY_OR_DELETED_BIN_P(bin)) {
- DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
- if (EXPECT(rebuilt_p, 0))
- return REBUILT_TABLE_ENTRY_IND;
- if (eq_p)
- break;
- }
- else if (EMPTY_BIN_P(bin))
+ DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
+ if (EXPECT(rebuilt_p, 0))
+ return REBUILT_TABLE_ENTRY_IND;
+ if (eq_p)
+ break;
+ }
+ else if (EMPTY_BIN_P(bin))
return UNDEFINED_ENTRY_IND;
#ifdef QUADRATIC_PROBE
- ind = hash_bin(ind + d, tab);
- d++;
+ ind = hash_bin(ind + d, tab);
+ d++;
#else
ind = secondary_hash(ind, tab, &peterb);
#endif
@@ -882,17 +882,17 @@ find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key)
for (;;) {
bin = get_bin(tab->bins, get_size_ind(tab), ind);
if (! EMPTY_OR_DELETED_BIN_P(bin)) {
- DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
- if (EXPECT(rebuilt_p, 0))
- return REBUILT_TABLE_BIN_IND;
- if (eq_p)
- break;
- }
- else if (EMPTY_BIN_P(bin))
+ DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
+ if (EXPECT(rebuilt_p, 0))
+ return REBUILT_TABLE_BIN_IND;
+ if (eq_p)
+ break;
+ }
+ else if (EMPTY_BIN_P(bin))
return UNDEFINED_BIN_IND;
#ifdef QUADRATIC_PROBE
- ind = hash_bin(ind + d, tab);
- d++;
+ ind = hash_bin(ind + d, tab);
+ d++;
#else
ind = secondary_hash(ind, tab, &peterb);
#endif
@@ -925,10 +925,10 @@ find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key)
for (;;) {
bin = get_bin(tab->bins, get_size_ind(tab), ind);
if (EMPTY_OR_DELETED_BIN_P(bin))
- return ind;
+ return ind;
#ifdef QUADRATIC_PROBE
- ind = hash_bin(ind + d, tab);
- d++;
+ ind = hash_bin(ind + d, tab);
+ d++;
#else
ind = secondary_hash(ind, tab, &peterb);
#endif
@@ -947,7 +947,7 @@ find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key)
during the search, return REBUILT_TABLE_ENTRY_IND. */
static st_index_t
find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
- st_data_t key, st_index_t *bin_ind)
+ st_data_t key, st_index_t *bin_ind)
{
int eq_p, rebuilt_p;
st_index_t ind;
@@ -974,26 +974,26 @@ find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
entry_index = get_bin(tab->bins, get_size_ind(tab), ind);
if (EMPTY_BIN_P(entry_index)) {
tab->num_entries++;
- entry_index = UNDEFINED_ENTRY_IND;
+ entry_index = UNDEFINED_ENTRY_IND;
if (first_deleted_bin_ind != UNDEFINED_BIN_IND) {
/* We can reuse bin of a deleted entry. */
ind = first_deleted_bin_ind;
MARK_BIN_EMPTY(tab, ind);
}
break;
- }
- else if (! DELETED_BIN_P(entry_index)) {
- DO_PTR_EQUAL_CHECK(tab, &entries[entry_index - ENTRY_BASE], curr_hash_value, key, eq_p, rebuilt_p);
- if (EXPECT(rebuilt_p, 0))
- return REBUILT_TABLE_ENTRY_IND;
+ }
+ else if (! DELETED_BIN_P(entry_index)) {
+ DO_PTR_EQUAL_CHECK(tab, &entries[entry_index - ENTRY_BASE], curr_hash_value, key, eq_p, rebuilt_p);
+ if (EXPECT(rebuilt_p, 0))
+ return REBUILT_TABLE_ENTRY_IND;
if (eq_p)
break;
- }
- else if (first_deleted_bin_ind == UNDEFINED_BIN_IND)
+ }
+ else if (first_deleted_bin_ind == UNDEFINED_BIN_IND)
first_deleted_bin_ind = ind;
#ifdef QUADRATIC_PROBE
- ind = hash_bin(ind + d, tab);
- d++;
+ ind = hash_bin(ind + d, tab);
+ d++;
#else
ind = secondary_hash(ind, tab, &peterb);
#endif
@@ -1014,18 +1014,18 @@ st_lookup(st_table *tab, st_data_t key, st_data_t *value)
retry:
if (tab->bins == NULL) {
bin = find_entry(tab, hash, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- if (bin == UNDEFINED_ENTRY_IND)
- return 0;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ if (bin == UNDEFINED_ENTRY_IND)
+ return 0;
}
else {
bin = find_table_entry_ind(tab, hash, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- if (bin == UNDEFINED_ENTRY_IND)
- return 0;
- bin -= ENTRY_BASE;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ if (bin == UNDEFINED_ENTRY_IND)
+ return 0;
+ bin -= ENTRY_BASE;
}
if (value != 0)
*value = tab->entries[bin].record;
@@ -1043,18 +1043,18 @@ st_get_key(st_table *tab, st_data_t key, st_data_t *result)
retry:
if (tab->bins == NULL) {
bin = find_entry(tab, hash, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- if (bin == UNDEFINED_ENTRY_IND)
- return 0;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ if (bin == UNDEFINED_ENTRY_IND)
+ return 0;
}
else {
bin = find_table_entry_ind(tab, hash, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- if (bin == UNDEFINED_ENTRY_IND)
- return 0;
- bin -= ENTRY_BASE;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ if (bin == UNDEFINED_ENTRY_IND)
+ return 0;
+ bin -= ENTRY_BASE;
}
if (result != 0)
*result = tab->entries[bin].key;
@@ -1089,29 +1089,29 @@ st_insert(st_table *tab, st_data_t key, st_data_t value)
rebuild_table_if_necessary(tab);
if (tab->bins == NULL) {
bin = find_entry(tab, hash_value, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- new_p = bin == UNDEFINED_ENTRY_IND;
- if (new_p)
- tab->num_entries++;
- bin_ind = UNDEFINED_BIN_IND;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ new_p = bin == UNDEFINED_ENTRY_IND;
+ if (new_p)
+ tab->num_entries++;
+ bin_ind = UNDEFINED_BIN_IND;
}
else {
bin = find_table_bin_ptr_and_reserve(tab, &hash_value,
- key, &bin_ind);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- new_p = bin == UNDEFINED_ENTRY_IND;
- bin -= ENTRY_BASE;
+ key, &bin_ind);
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ new_p = bin == UNDEFINED_ENTRY_IND;
+ bin -= ENTRY_BASE;
}
if (new_p) {
- ind = tab->entries_bound++;
+ ind = tab->entries_bound++;
entry = &tab->entries[ind];
entry->hash = hash_value;
entry->key = key;
entry->record = value;
- if (bin_ind != UNDEFINED_BIN_IND)
- set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
+ if (bin_ind != UNDEFINED_BIN_IND)
+ set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
return 0;
}
tab->entries[bin].record = value;
@@ -1122,7 +1122,7 @@ st_insert(st_table *tab, st_data_t key, st_data_t value)
entry with KEY before the insertion. */
static inline void
st_add_direct_with_hash(st_table *tab,
- st_data_t key, st_data_t value, st_hash_t hash)
+ st_data_t key, st_data_t value, st_hash_t hash)
{
st_table_entry *entry;
st_index_t ind;
@@ -1137,7 +1137,7 @@ st_add_direct_with_hash(st_table *tab,
tab->num_entries++;
if (tab->bins != NULL) {
bin_ind = find_table_bin_ind_direct(tab, hash, key);
- set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
+ set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
}
}
@@ -1171,20 +1171,20 @@ st_insert2(st_table *tab, st_data_t key, st_data_t value,
rebuild_table_if_necessary (tab);
if (tab->bins == NULL) {
bin = find_entry(tab, hash_value, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- new_p = bin == UNDEFINED_ENTRY_IND;
- if (new_p)
- tab->num_entries++;
- bin_ind = UNDEFINED_BIN_IND;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ new_p = bin == UNDEFINED_ENTRY_IND;
+ if (new_p)
+ tab->num_entries++;
+ bin_ind = UNDEFINED_BIN_IND;
}
else {
bin = find_table_bin_ptr_and_reserve(tab, &hash_value,
- key, &bin_ind);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- new_p = bin == UNDEFINED_ENTRY_IND;
- bin -= ENTRY_BASE;
+ key, &bin_ind);
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ new_p = bin == UNDEFINED_ENTRY_IND;
+ bin -= ENTRY_BASE;
}
if (new_p) {
key = (*func)(key);
@@ -1193,8 +1193,8 @@ st_insert2(st_table *tab, st_data_t key, st_data_t value,
entry->hash = hash_value;
entry->key = key;
entry->record = value;
- if (bin_ind != UNDEFINED_BIN_IND)
- set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
+ if (bin_ind != UNDEFINED_BIN_IND)
+ set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
return 0;
}
tab->entries[bin].record = value;
@@ -1225,7 +1225,7 @@ st_copy(st_table *old_tab)
#endif
}
new_tab->entries = (st_table_entry *) malloc(get_allocated_entries(old_tab)
- * sizeof(st_table_entry));
+ * sizeof(st_table_entry));
#ifndef RUBY
if (new_tab->entries == NULL) {
st_free_table(new_tab);
@@ -1233,7 +1233,7 @@ st_copy(st_table *old_tab)
}
#endif
MEMCPY(new_tab->entries, old_tab->entries, st_table_entry,
- get_allocated_entries(old_tab));
+ get_allocated_entries(old_tab));
if (old_tab->bins != NULL)
MEMCPY(new_tab->bins, old_tab->bins, char, bins_size(old_tab));
return new_tab;
@@ -1271,23 +1271,23 @@ st_general_delete(st_table *tab, st_data_t *key, st_data_t *value)
retry:
if (tab->bins == NULL) {
bin = find_entry(tab, hash, *key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- if (bin == UNDEFINED_ENTRY_IND) {
- if (value != 0) *value = 0;
- return 0;
- }
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ if (bin == UNDEFINED_ENTRY_IND) {
+ if (value != 0) *value = 0;
+ return 0;
+ }
}
else {
bin_ind = find_table_bin_ind(tab, hash, *key);
- if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
- goto retry;
- if (bin_ind == UNDEFINED_BIN_IND) {
- if (value != 0) *value = 0;
- return 0;
- }
- bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
- MARK_BIN_DELETED(tab, bin_ind);
+ if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
+ goto retry;
+ if (bin_ind == UNDEFINED_BIN_IND) {
+ if (value != 0) *value = 0;
+ return 0;
+ }
+ bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
+ MARK_BIN_DELETED(tab, bin_ind);
}
entry = &tab->entries[bin];
*key = entry->key;
@@ -1332,36 +1332,36 @@ st_shift(st_table *tab, st_data_t *key, st_data_t *value)
bound = tab->entries_bound;
for (i = tab->entries_start; i < bound; i++) {
curr_entry_ptr = &entries[i];
- if (! DELETED_ENTRY_P(curr_entry_ptr)) {
- st_hash_t entry_hash = curr_entry_ptr->hash;
- st_data_t entry_key = curr_entry_ptr->key;
-
- if (value != 0) *value = curr_entry_ptr->record;
- *key = entry_key;
- retry:
- if (tab->bins == NULL) {
- bin = find_entry(tab, entry_hash, entry_key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) {
- entries = tab->entries;
- goto retry;
- }
- curr_entry_ptr = &entries[bin];
- }
- else {
- bin_ind = find_table_bin_ind(tab, entry_hash, entry_key);
- if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0)) {
- entries = tab->entries;
- goto retry;
- }
- curr_entry_ptr = &entries[get_bin(tab->bins, get_size_ind(tab), bin_ind)
- - ENTRY_BASE];
- MARK_BIN_DELETED(tab, bin_ind);
- }
- MARK_ENTRY_DELETED(curr_entry_ptr);
- tab->num_entries--;
- update_range_for_deleted(tab, i);
- return 1;
- }
+ if (! DELETED_ENTRY_P(curr_entry_ptr)) {
+ st_hash_t entry_hash = curr_entry_ptr->hash;
+ st_data_t entry_key = curr_entry_ptr->key;
+
+ if (value != 0) *value = curr_entry_ptr->record;
+ *key = entry_key;
+ retry:
+ if (tab->bins == NULL) {
+ bin = find_entry(tab, entry_hash, entry_key);
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) {
+ entries = tab->entries;
+ goto retry;
+ }
+ curr_entry_ptr = &entries[bin];
+ }
+ else {
+ bin_ind = find_table_bin_ind(tab, entry_hash, entry_key);
+ if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0)) {
+ entries = tab->entries;
+ goto retry;
+ }
+ curr_entry_ptr = &entries[get_bin(tab->bins, get_size_ind(tab), bin_ind)
+ - ENTRY_BASE];
+ MARK_BIN_DELETED(tab, bin_ind);
+ }
+ MARK_ENTRY_DELETED(curr_entry_ptr);
+ tab->num_entries--;
+ update_range_for_deleted(tab, i);
+ return 1;
+ }
}
if (value != 0) *value = 0;
return 0;
@@ -1385,7 +1385,7 @@ st_cleanup_safe(st_table *tab ATTRIBUTE_UNUSED,
the table before the call. */
int
st_update(st_table *tab, st_data_t key,
- st_update_callback_func *func, st_data_t arg)
+ st_update_callback_func *func, st_data_t arg)
{
st_table_entry *entry = NULL; /* to avoid uninitialized value warning */
st_index_t bin = 0; /* Ditto */
@@ -1399,21 +1399,21 @@ st_update(st_table *tab, st_data_t key,
entries = tab->entries;
if (tab->bins == NULL) {
bin = find_entry(tab, hash, key);
- if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- existing = bin != UNDEFINED_ENTRY_IND;
- entry = &entries[bin];
- bin_ind = UNDEFINED_BIN_IND;
+ if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ existing = bin != UNDEFINED_ENTRY_IND;
+ entry = &entries[bin];
+ bin_ind = UNDEFINED_BIN_IND;
}
else {
bin_ind = find_table_bin_ind(tab, hash, key);
- if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
- goto retry;
- existing = bin_ind != UNDEFINED_BIN_IND;
- if (existing) {
- bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
- entry = &entries[bin];
- }
+ if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
+ goto retry;
+ existing = bin_ind != UNDEFINED_BIN_IND;
+ if (existing) {
+ bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
+ entry = &entries[bin];
+ }
}
if (existing) {
key = entry->key;
@@ -1424,7 +1424,7 @@ st_update(st_table *tab, st_data_t key,
switch (retval) {
case ST_CONTINUE:
if (! existing) {
- st_add_direct_with_hash(tab, key, value, hash);
+ st_add_direct_with_hash(tab, key, value, hash);
break;
}
if (old_key != key) {
@@ -1434,11 +1434,11 @@ st_update(st_table *tab, st_data_t key,
break;
case ST_DELETE:
if (existing) {
- if (bin_ind != UNDEFINED_BIN_IND)
- MARK_BIN_DELETED(tab, bin_ind);
+ if (bin_ind != UNDEFINED_BIN_IND)
+ MARK_BIN_DELETED(tab, bin_ind);
MARK_ENTRY_DELETED(entry);
- tab->num_entries--;
- update_range_for_deleted(tab, bin);
+ tab->num_entries--;
+ update_range_for_deleted(tab, bin);
}
break;
}
@@ -1455,7 +1455,7 @@ st_update(st_table *tab, st_data_t key,
during traversing. */
static inline int
st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_update_callback_func *replace, st_data_t arg,
- int check_p)
+ int check_p)
{
st_index_t bin;
st_index_t bin_ind;
@@ -1471,12 +1471,12 @@ st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_updat
the table, e.g. by an entry insertion. */
for (i = tab->entries_start; i < tab->entries_bound; i++) {
curr_entry_ptr = &entries[i];
- if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 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 (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 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 (retval == ST_REPLACE && replace) {
st_data_t value;
@@ -1486,44 +1486,44 @@ st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_updat
curr_entry_ptr->record = value;
}
- if (rebuilds_num != tab->rebuilds_num) {
- retry:
- entries = tab->entries;
- packed_p = tab->bins == NULL;
- if (packed_p) {
- i = find_entry(tab, hash, key);
- if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- error_p = i == UNDEFINED_ENTRY_IND;
- }
- else {
- i = find_table_entry_ind(tab, hash, key);
- if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
- goto retry;
- error_p = i == UNDEFINED_ENTRY_IND;
- i -= ENTRY_BASE;
- }
- if (error_p && check_p) {
- /* call func with error notice */
- retval = (*func)(0, 0, arg, 1);
- return 1;
- }
- curr_entry_ptr = &entries[i];
- }
- switch (retval) {
+ if (rebuilds_num != tab->rebuilds_num) {
+ retry:
+ entries = tab->entries;
+ packed_p = tab->bins == NULL;
+ if (packed_p) {
+ i = find_entry(tab, hash, key);
+ if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ error_p = i == UNDEFINED_ENTRY_IND;
+ }
+ else {
+ i = find_table_entry_ind(tab, hash, key);
+ if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
+ goto retry;
+ error_p = i == UNDEFINED_ENTRY_IND;
+ i -= ENTRY_BASE;
+ }
+ if (error_p && check_p) {
+ /* call func with error notice */
+ retval = (*func)(0, 0, arg, 1);
+ return 1;
+ }
+ curr_entry_ptr = &entries[i];
+ }
+ switch (retval) {
case ST_REPLACE:
break;
- case ST_CONTINUE:
+ case ST_CONTINUE:
break;
- case ST_CHECK:
+ case ST_CHECK:
if (check_p)
break;
- case ST_STOP:
+ case ST_STOP:
return 0;
- case ST_DELETE: {
+ case ST_DELETE: {
st_data_t key = curr_entry_ptr->key;
- again:
+ again:
if (packed_p) {
bin = find_entry(tab, hash, key);
if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
@@ -1545,8 +1545,8 @@ st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_updat
tab->num_entries--;
update_range_for_deleted(tab, bin);
break;
- }
- }
+ }
+ }
}
return 0;
}
@@ -1597,12 +1597,12 @@ st_general_keys(st_table *tab, st_data_t *keys, st_index_t size)
keys_start = keys;
keys_end = keys + size;
for (i = tab->entries_start; i < bound; i++) {
- if (keys == keys_end)
- break;
- curr_entry_ptr = &entries[i];
- key = curr_entry_ptr->key;
+ if (keys == keys_end)
+ break;
+ curr_entry_ptr = &entries[i];
+ key = curr_entry_ptr->key;
if (! DELETED_ENTRY_P(curr_entry_ptr))
- *keys++ = key;
+ *keys++ = key;
}
return keys - keys_start;
@@ -1635,11 +1635,11 @@ st_general_values(st_table *tab, st_data_t *values, st_index_t size)
values_end = values + size;
bound = tab->entries_bound;
for (i = tab->entries_start; i < bound; i++) {
- if (values == values_end)
- break;
+ if (values == values_end)
+ break;
curr_entry_ptr = &entries[i];
if (! DELETED_ENTRY_P(curr_entry_ptr))
- *values++ = curr_entry_ptr->record;
+ *values++ = curr_entry_ptr->record;
}
return values - values_start;
@@ -1654,7 +1654,7 @@ st_values(st_table *tab, st_data_t *values, st_index_t size)
/* See comments for function st_delete_safe. */
st_index_t
st_values_check(st_table *tab, st_data_t *values, st_index_t size,
- st_data_t never ATTRIBUTE_UNUSED)
+ st_data_t never ATTRIBUTE_UNUSED)
{
return st_general_values(tab, values, size);
}
@@ -1770,87 +1770,87 @@ st_hash(const void *ptr, size_t len, st_index_t h)
#undef SKIP_TAIL
if (len >= sizeof(st_index_t)) {
#if !UNALIGNED_WORD_ACCESS
- int align = (int)((st_data_t)data % sizeof(st_index_t));
- if (align) {
- st_index_t d = 0;
- int sl, sr, pack;
+ int align = (int)((st_data_t)data % sizeof(st_index_t));
+ if (align) {
+ st_index_t d = 0;
+ int sl, sr, pack;
- switch (align) {
+ switch (align) {
#ifdef WORDS_BIGENDIAN
# define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
- t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
+ t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
#else
# define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
- t |= data_at(n) << CHAR_BIT*(n)
+ t |= data_at(n) << CHAR_BIT*(n)
#endif
- UNALIGNED_ADD_ALL;
+ UNALIGNED_ADD_ALL;
#undef UNALIGNED_ADD
- }
+ }
#ifdef WORDS_BIGENDIAN
- t >>= (CHAR_BIT * align) - CHAR_BIT;
+ t >>= (CHAR_BIT * align) - CHAR_BIT;
#else
- t <<= (CHAR_BIT * align);
+ t <<= (CHAR_BIT * align);
#endif
- data += sizeof(st_index_t)-align;
- len -= sizeof(st_index_t)-align;
+ data += sizeof(st_index_t)-align;
+ len -= sizeof(st_index_t)-align;
- sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align);
- sr = CHAR_BIT * align;
+ sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align);
+ sr = CHAR_BIT * align;
- while (len >= sizeof(st_index_t)) {
- d = *(st_index_t *)data;
+ while (len >= sizeof(st_index_t)) {
+ d = *(st_index_t *)data;
#ifdef WORDS_BIGENDIAN
- t = (t << sr) | (d >> sl);
+ t = (t << sr) | (d >> sl);
#else
- t = (t >> sr) | (d << sl);
+ t = (t >> sr) | (d << sl);
#endif
- h = murmur_step(h, t);
- t = d;
- data += sizeof(st_index_t);
- len -= sizeof(st_index_t);
- }
-
- pack = len < (size_t)align ? (int)len : align;
- d = 0;
- switch (pack) {
+ h = murmur_step(h, t);
+ t = d;
+ data += sizeof(st_index_t);
+ len -= sizeof(st_index_t);
+ }
+
+ pack = len < (size_t)align ? (int)len : align;
+ d = 0;
+ switch (pack) {
#ifdef WORDS_BIGENDIAN
# define UNALIGNED_ADD(n) case (n) + 1: \
- d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
+ d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
#else
# define UNALIGNED_ADD(n) case (n) + 1: \
- d |= data_at(n) << CHAR_BIT*(n)
+ d |= data_at(n) << CHAR_BIT*(n)
#endif
- UNALIGNED_ADD_ALL;
+ UNALIGNED_ADD_ALL;
#undef UNALIGNED_ADD
- }
+ }
#ifdef WORDS_BIGENDIAN
- t = (t << sr) | (d >> sl);
+ t = (t << sr) | (d >> sl);
#else
- t = (t >> sr) | (d << sl);
+ t = (t >> sr) | (d << sl);
#endif
- if (len < (size_t)align) goto skip_tail;
+ if (len < (size_t)align) goto skip_tail;
# define SKIP_TAIL 1
- h = murmur_step(h, t);
- data += pack;
- len -= pack;
- }
- else
+ h = murmur_step(h, t);
+ data += pack;
+ len -= pack;
+ }
+ else
#endif
#ifdef HAVE_BUILTIN___BUILTIN_ASSUME_ALIGNED
#define aligned_data __builtin_assume_aligned(data, sizeof(st_index_t))
#else
#define aligned_data data
#endif
- {
- do {
- h = murmur_step(h, *(st_index_t *)aligned_data);
- data += sizeof(st_index_t);
- len -= sizeof(st_index_t);
- } while (len >= sizeof(st_index_t));
- }
+ {
+ do {
+ h = murmur_step(h, *(st_index_t *)aligned_data);
+ data += sizeof(st_index_t);
+ len -= sizeof(st_index_t);
+ } while (len >= sizeof(st_index_t));
+ }
}
t = 0;
@@ -1862,8 +1862,8 @@ st_hash(const void *ptr, size_t len, st_index_t h)
case 6: t |= data_at(5) << 40;
case 5: t |= data_at(4) << 32;
case 4:
- t |= (st_index_t)*(uint32_t*)aligned_data;
- goto skip_tail;
+ t |= (st_index_t)*(uint32_t*)aligned_data;
+ goto skip_tail;
# define SKIP_TAIL 1
#endif
case 3: t |= data_at(2) << 16;
@@ -1872,19 +1872,19 @@ st_hash(const void *ptr, size_t len, st_index_t h)
#else
#ifdef WORDS_BIGENDIAN
# define UNALIGNED_ADD(n) case (n) + 1: \
- t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
+ t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
#else
# define UNALIGNED_ADD(n) case (n) + 1: \
- t |= data_at(n) << CHAR_BIT*(n)
+ t |= data_at(n) << CHAR_BIT*(n)
#endif
- UNALIGNED_ADD_ALL;
+ UNALIGNED_ADD_ALL;
#undef UNALIGNED_ADD
#endif
#ifdef SKIP_TAIL
skip_tail:
#endif
- h ^= t; h -= ROTL(t, 7);
- h *= C2;
+ h ^= t; h -= ROTL(t, 7);
+ h *= C2;
}
h ^= l;
#undef aligned_data
@@ -2010,12 +2010,12 @@ strcasehash(st_data_t arg)
* FNV-1a hash each octet in the buffer
*/
while (*string) {
- unsigned int c = (unsigned char)*string++;
- if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
- hval ^= c;
+ unsigned int c = (unsigned char)*string++;
+ if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
+ hval ^= c;
- /* multiply by the 32 bit FNV magic prime mod 2^32 */
- hval *= FNV_32_PRIME;
+ /* multiply by the 32 bit FNV magic prime mod 2^32 */
+ hval *= FNV_32_PRIME;
}
return hval;
}
@@ -2082,10 +2082,10 @@ st_rehash_linear(st_table *tab)
q = &tab->entries[j];
if (DELETED_ENTRY_P(q))
continue;
- DO_PTR_EQUAL_CHECK(tab, p, q->hash, q->key, eq_p, rebuilt_p);
- if (EXPECT(rebuilt_p, 0))
- return TRUE;
- if (eq_p) {
+ DO_PTR_EQUAL_CHECK(tab, p, q->hash, q->key, eq_p, rebuilt_p);
+ if (EXPECT(rebuilt_p, 0))
+ return TRUE;
+ if (eq_p) {
*p = *q;
MARK_ENTRY_DELETED(q);
tab->num_entries--;
@@ -2130,27 +2130,27 @@ st_rehash_indexed(st_table *tab)
}
else {
st_table_entry *q = &tab->entries[bin - ENTRY_BASE];
- DO_PTR_EQUAL_CHECK(tab, q, p->hash, p->key, eq_p, rebuilt_p);
- if (EXPECT(rebuilt_p, 0))
- return TRUE;
- if (eq_p) {
- /* duplicated key; delete it */
- q->record = p->record;
- MARK_ENTRY_DELETED(p);
- tab->num_entries--;
- update_range_for_deleted(tab, bin);
- break;
- }
- else {
- /* hash collision; skip it */
+ DO_PTR_EQUAL_CHECK(tab, q, p->hash, p->key, eq_p, rebuilt_p);
+ if (EXPECT(rebuilt_p, 0))
+ return TRUE;
+ if (eq_p) {
+ /* duplicated key; delete it */
+ q->record = p->record;
+ MARK_ENTRY_DELETED(p);
+ tab->num_entries--;
+ update_range_for_deleted(tab, bin);
+ break;
+ }
+ else {
+ /* hash collision; skip it */
#ifdef QUADRATIC_PROBE
- ind = hash_bin(ind + d, tab);
- d++;
+ ind = hash_bin(ind + d, tab);
+ d++;
#else
- ind = secondary_hash(ind, tab, &peterb);
+ ind = secondary_hash(ind, tab, &peterb);
#endif
- }
- }
+ }
+ }
}
}
return FALSE;
@@ -2165,10 +2165,10 @@ st_rehash(st_table *tab)
int rebuilt_p;
do {
- if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS)
- rebuilt_p = st_rehash_linear(tab);
- else
- rebuilt_p = st_rehash_indexed(tab);
+ if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS)
+ rebuilt_p = st_rehash_linear(tab);
+ else
+ rebuilt_p = st_rehash_indexed(tab);
} while (rebuilt_p);
}