diff options
Diffstat (limited to 'st.c')
| -rw-r--r-- | st.c | 140 |
1 files changed, 94 insertions, 46 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> @@ -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 @@ -657,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); } @@ -718,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 @@ -725,14 +729,6 @@ count_collision(const struct st_hash_type *type) static void rebuild_table(st_table *tab) { - st_index_t i, ni; - unsigned int size_ind; - st_table *new_tab; - st_table_entry *new_entries; - st_table_entry *curr_entry_ptr; - st_index_t *bins; - st_index_t bin_ind; - if ((2 * tab->num_entries <= get_allocated_entries(tab) && REBUILD_THRESHOLD * tab->num_entries > get_allocated_entries(tab)) || tab->num_entries < (1 << MINIMAL_POWER2)) { @@ -740,17 +736,32 @@ rebuild_table(st_table *tab) tab->num_entries = 0; if (tab->bins != NULL) initialize_bins(tab); - new_tab = tab; - new_entries = tab->entries; + 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; + 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; @@ -773,17 +784,24 @@ rebuild_table(st_table *tab) 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); - } +} + +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++; @@ -1168,6 +1186,13 @@ st_add_direct_with_hash(st_table *tab, } } +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 @@ -1228,17 +1253,10 @@ st_insert2(st_table *tab, st_data_t key, st_data_t 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; @@ -1246,7 +1264,6 @@ 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 @@ -1255,7 +1272,6 @@ st_copy(st_table *old_tab) * sizeof(st_table_entry)); #ifndef RUBY if (new_tab->entries == NULL) { - st_free_table(new_tab); return NULL; } #endif @@ -1263,6 +1279,27 @@ st_copy(st_table *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; } @@ -2061,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. */ @@ -2077,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; @@ -2098,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)) @@ -2200,7 +2236,6 @@ st_rehash(st_table *tab) } while (rebuilt_p); } -#ifdef RUBY static st_data_t st_stringify(VALUE key) { @@ -2288,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 |