diff options
Diffstat (limited to 'st.c')
-rw-r--r-- | st.c | 840 |
1 files changed, 458 insertions, 382 deletions
@@ -103,11 +103,12 @@ #ifdef NOT_RUBY #include "regint.h" #include "st.h" -#else +#elif defined RUBY_EXPORT #include "internal.h" #include "internal/bits.h" #include "internal/hash.h" #include "internal/sanitizers.h" +#include "internal/st.h" #endif #include <stdio.h> @@ -181,9 +182,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. */ @@ -342,7 +343,7 @@ get_power2(st_index_t size) unsigned int n = ST_INDEX_BITS - nlz_intptr(size); if (n <= MAX_POWER2) return n < MINIMAL_POWER2 ? MINIMAL_POWER2 : n; -#ifndef NOT_RUBY +#ifdef RUBY /* Ran out of the table entries */ rb_raise(rb_eRuntimeError, "st_table too big"); #endif @@ -356,9 +357,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 @@ -509,13 +510,9 @@ stat_col(void) } #endif -/* Create and return table with TYPE which can hold at least SIZE - entries. The real number of entries which the table can hold is - the nearest power of two for SIZE. */ st_table * -st_init_table_with_size(const struct st_hash_type *type, st_index_t size) +st_init_existing_table_with_size(st_table *tab, const struct st_hash_type *type, st_index_t size) { - st_table *tab; int n; #ifdef HASH_LOG @@ -536,11 +533,7 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size) if (n < 0) return NULL; #endif - tab = (st_table *) malloc(sizeof (st_table)); -#ifndef RUBY - if (tab == NULL) - return NULL; -#endif + tab->type = type; tab->entry_power = n; tab->bin_power = features[n].bin_power; @@ -557,7 +550,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); @@ -569,6 +562,36 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size) return tab; } +/* Create and return table with TYPE which can hold at least SIZE + entries. The real number of entries which the table can hold is + the nearest power of two for SIZE. */ +st_table * +st_init_table_with_size(const struct st_hash_type *type, st_index_t size) +{ + st_table *tab = malloc(sizeof(st_table)); +#ifndef RUBY + if (tab == NULL) + return NULL; +#endif + +#ifdef RUBY + st_init_existing_table_with_size(tab, type, size); +#else + if (st_init_existing_table_with_size(tab, type, size) == NULL) { + free(tab); + return NULL; + } +#endif + + return tab; +} + +size_t +st_table_size(const struct st_table *tbl) +{ + return tbl->num_entries; +} + /* Create and return table with TYPE which can hold a minimal number of entries (see comments for get_power2). */ st_table * @@ -635,8 +658,7 @@ st_clear(st_table *tab) void st_free_table(st_table *tab) { - if (tab->bins != NULL) - free(tab->bins); + free(tab->bins); free(tab->entries); free(tab); } @@ -661,7 +683,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 @@ -696,6 +718,10 @@ count_collision(const struct st_hash_type *type) #error "REBUILD_THRESHOLD should be >= 2" #endif +static void rebuild_table_with(st_table *const new_tab, st_table *const tab); +static void rebuild_move_table(st_table *const new_tab, st_table *const tab); +static void rebuild_cleanup(st_table *const tab); + /* Rebuild table TAB. Rebuilding removes all deleted bins and entries and can change size of the table entries and bins arrays. Rebuilding is implemented by creation of a new table or by @@ -703,67 +729,86 @@ count_collision(const struct st_hash_type *type) static void 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; 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); + rebuild_table_with(tab, tab); } else { + st_table *new_tab; + /* This allocation could trigger GC and compaction. If tab is the + * gen_iv_tbl, then tab could have changed in size due to objects being + * freed and/or moved. Do not store attributes of tab before this line. */ new_tab = st_init_table_with_size(tab->type, - 2 * tab->num_entries - 1); - new_entries = new_tab->entries; + 2 * tab->num_entries - 1); + rebuild_table_with(new_tab, tab); + rebuild_move_table(new_tab, tab); } + rebuild_cleanup(tab); +} + +static void +rebuild_table_with(st_table *const new_tab, st_table *const tab) +{ + st_index_t i, ni; + unsigned int size_ind; + st_table_entry *new_entries; + st_table_entry *curr_entry_ptr; + st_index_t *bins; + st_index_t bin_ind; + + new_entries = new_tab->entries; + ni = 0; bins = new_tab->bins; size_ind = get_size_ind(new_tab); + st_index_t bound = tab->entries_bound; + st_table_entry *entries = tab->entries; + 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++; - } - 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); + 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++; } +} + +static void +rebuild_move_table(st_table *const new_tab, st_table *const tab) +{ + tab->entry_power = new_tab->entry_power; + tab->bin_power = new_tab->bin_power; + tab->size_ind = new_tab->size_ind; + free(tab->bins); + tab->bins = new_tab->bins; + free(tab->entries); + tab->entries = new_tab->entries; + free(new_tab); +} + +static void +rebuild_cleanup(st_table *const tab) +{ tab->entries_start = 0; tab->entries_bound = tab->num_entries; tab->rebuilds_num++; } /* Return the next secondary hash index for table TAB using previous - index IND and PERTERB. Finally modulo of the function becomes a + index IND and PERTURB. Finally modulo of the function becomes a full *cycle linear congruential generator*, in other words it guarantees traversing all table bins in extreme case. @@ -775,10 +820,10 @@ rebuild_table(st_table *tab) For our case a is 5, c is 1, and m is a power of two. */ static inline st_index_t -secondary_hash(st_index_t ind, st_table *tab, st_index_t *perterb) +secondary_hash(st_index_t ind, st_table *tab, st_index_t *perturb) { - *perterb >>= 11; - ind = (ind << 2) + ind + *perterb + 1; + *perturb >>= 11; + ind = (ind << 2) + ind + *perturb + 1; return hash_bin(ind, tab); } @@ -796,11 +841,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; } @@ -821,7 +866,7 @@ find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key) #ifdef QUADRATIC_PROBE st_index_t d; #else - st_index_t peterb; + st_index_t perturb; #endif st_index_t bin; st_table_entry *entries = tab->entries; @@ -830,25 +875,25 @@ find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key) #ifdef QUADRATIC_PROBE d = 1; #else - peterb = hash_value; + perturb = hash_value; #endif FOUND_BIN; 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); + ind = secondary_hash(ind, tab, &perturb); #endif COLLISION; } @@ -867,7 +912,7 @@ find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key) #ifdef QUADRATIC_PROBE st_index_t d; #else - st_index_t peterb; + st_index_t perturb; #endif st_index_t bin; st_table_entry *entries = tab->entries; @@ -876,25 +921,25 @@ find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key) #ifdef QUADRATIC_PROBE d = 1; #else - peterb = hash_value; + perturb = hash_value; #endif FOUND_BIN; 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); + ind = secondary_hash(ind, tab, &perturb); #endif COLLISION; } @@ -911,7 +956,7 @@ find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key) #ifdef QUADRATIC_PROBE st_index_t d; #else - st_index_t peterb; + st_index_t perturb; #endif st_index_t bin; @@ -919,18 +964,18 @@ find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key) #ifdef QUADRATIC_PROBE d = 1; #else - peterb = hash_value; + perturb = hash_value; #endif FOUND_BIN; 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); + ind = secondary_hash(ind, tab, &perturb); #endif COLLISION; } @@ -947,7 +992,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; @@ -955,7 +1000,7 @@ find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value, #ifdef QUADRATIC_PROBE st_index_t d; #else - st_index_t peterb; + st_index_t perturb; #endif st_index_t entry_index; st_index_t first_deleted_bin_ind; @@ -965,7 +1010,7 @@ find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value, #ifdef QUADRATIC_PROBE d = 1; #else - peterb = curr_hash_value; + perturb = curr_hash_value; #endif FOUND_BIN; first_deleted_bin_ind = UNDEFINED_BIN_IND; @@ -974,28 +1019,28 @@ 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); + ind = secondary_hash(ind, tab, &perturb); #endif COLLISION; } @@ -1014,18 +1059,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 +1088,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 +1134,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 +1167,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,10 +1182,17 @@ 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); } } +void +rb_st_add_direct_with_hash(st_table *tab, + st_data_t key, st_data_t value, st_hash_t hash) +{ + st_add_direct_with_hash(tab, key, value, hash); +} + /* Insert (KEY, VALUE) into table TAB. The table should not have entry with KEY before the insertion. */ void @@ -1171,20 +1223,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,25 +1245,18 @@ 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; return 1; } -/* Create and return a copy of table OLD_TAB. */ +/* Create a copy of old_tab into new_tab. */ st_table * -st_copy(st_table *old_tab) +st_replace(st_table *new_tab, st_table *old_tab) { - st_table *new_tab; - - new_tab = (st_table *) malloc(sizeof(st_table)); -#ifndef RUBY - if (new_tab == NULL) - return NULL; -#endif *new_tab = *old_tab; if (old_tab->bins == NULL) new_tab->bins = NULL; @@ -1219,23 +1264,42 @@ st_copy(st_table *old_tab) new_tab->bins = (st_index_t *) malloc(bins_size(old_tab)); #ifndef RUBY if (new_tab->bins == NULL) { - free(new_tab); return NULL; } #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); return NULL; } #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; +} + +/* Create and return a copy of table OLD_TAB. */ +st_table * +st_copy(st_table *old_tab) +{ + st_table *new_tab; + + new_tab = (st_table *) malloc(sizeof(st_table)); +#ifndef RUBY + if (new_tab == NULL) + return NULL; +#endif + + if (st_replace(new_tab, old_tab) == NULL) { + st_free_table(new_tab); + return NULL; + } + return new_tab; } @@ -1271,23 +1335,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 +1396,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 +1449,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 +1463,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 +1488,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 +1498,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 +1519,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 +1535,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 +1550,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 +1609,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 +1661,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 +1699,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 +1718,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); } @@ -1666,10 +1730,11 @@ st_values_check(st_table *tab, st_data_t *values, st_index_t size, */ #define FNV_32_PRIME 0x01000193 +/* __POWERPC__ added to accommodate Darwin case. */ #ifndef UNALIGNED_WORD_ACCESS # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \ defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD64) || \ - defined(__powerpc64__) || defined(__aarch64__) || \ + defined(__powerpc64__) || defined(__POWERPC__) || defined(__aarch64__) || \ defined(__mc68020__) # define UNALIGNED_WORD_ACCESS 1 # endif @@ -1770,87 +1835,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 +1927,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 +1937,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 +2075,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; } @@ -2033,6 +2098,7 @@ st_numhash(st_data_t n) return (st_index_t)((n>>s1|(n<<s2)) ^ (n>>s2)); } +#ifdef RUBY /* Expand TAB to be suitable for holding SIZ entries in total. Pre-existing entries remain not deleted inside of TAB, but its bins are cleared to expect future reconstruction. See rehash below. */ @@ -2049,10 +2115,8 @@ st_expand_table(st_table *tab, st_index_t siz) n = get_allocated_entries(tab); MEMCPY(tmp->entries, tab->entries, st_table_entry, n); free(tab->entries); - if (tab->bins != NULL) - free(tab->bins); - if (tmp->bins != NULL) - free(tmp->bins); + free(tab->bins); + free(tmp->bins); tab->entry_power = tmp->entry_power; tab->bin_power = tmp->bin_power; tab->size_ind = tmp->size_ind; @@ -2070,10 +2134,10 @@ st_rehash_linear(st_table *tab) int eq_p, rebuilt_p; st_index_t i, j; st_table_entry *p, *q; - if (tab->bins) { - free(tab->bins); - tab->bins = NULL; - } + + free(tab->bins); + tab->bins = NULL; + for (i = tab->entries_start; i < tab->entries_bound; i++) { p = &tab->entries[i]; if (DELETED_ENTRY_P(p)) @@ -2082,10 +2146,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--; @@ -2114,7 +2178,7 @@ st_rehash_indexed(st_table *tab) #ifdef QUADRATIC_PROBE st_index_t d = 1; #else - st_index_t peterb = p->hash; + st_index_t perturb = p->hash; #endif if (DELETED_ENTRY_P(p)) @@ -2130,27 +2194,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, &perturb); #endif - } - } + } + } } } return FALSE; @@ -2165,14 +2229,13 @@ 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); } -#ifdef RUBY static st_data_t st_stringify(VALUE key) { @@ -2260,4 +2323,17 @@ rb_st_nth_key(st_table *tab, st_index_t index) } } +void +rb_st_compact_table(st_table *tab) +{ + st_index_t num = tab->num_entries; + if (REBUILD_THRESHOLD * num <= get_allocated_entries(tab)) { + /* Compaction: */ + st_table *new_tab = st_init_table_with_size(tab->type, 2 * num); + rebuild_table_with(new_tab, tab); + rebuild_move_table(new_tab, tab); + rebuild_cleanup(tab); + } +} + #endif |