From 5b21e94bebed90180d8ff63dad03b8b948361089 Mon Sep 17 00:00:00 2001 From: Takashi Kokubun Date: Thu, 21 Jul 2022 09:23:58 -0700 Subject: Expand tabs [ci skip] [Misc #18891] --- st.c | 634 +++++++++++++++++++++++++++++++++---------------------------------- 1 file changed, 317 insertions(+), 317 deletions(-) (limited to 'st.c') 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); } -- cgit v1.2.3