diff options
Diffstat (limited to 'st.c')
| -rw-r--r-- | st.c | 372 |
1 files changed, 228 insertions, 144 deletions
@@ -107,6 +107,7 @@ #elif defined RUBY_EXPORT #include "internal.h" #include "internal/bits.h" +#include "internal/gc.h" #include "internal/hash.h" #include "internal/sanitizers.h" #include "internal/set_table.h" @@ -173,7 +174,14 @@ static const struct st_hash_type type_strcasehash = { #define malloc ruby_xmalloc #define calloc ruby_xcalloc #define realloc ruby_xrealloc +#define sized_realloc ruby_xrealloc_sized #define free ruby_xfree +#define sized_free ruby_xfree_sized +#define free_fixed_ptr(v) ruby_xfree_sized((v), sizeof(*(v))) +#else +#define sized_realloc(ptr, new_size, old_size) realloc(ptr, new_size) +#define sized_free(v, s) free(v) +#define free_fixed_ptr(v) free(v) #endif #define EQUAL(tab,x,y) ((x) == (y) || (*(tab)->type->compare)((x),(y)) == 0) @@ -390,7 +398,7 @@ set_bin(st_index_t *bins, int s, st_index_t n, st_index_t v) /* Mark I-th bin of table TAB as empty, in other words not corresponding to any entry. */ -#define MARK_BIN_EMPTY(tab, i) (set_bin((tab)->bins, get_size_ind(tab), i, EMPTY_BIN)) +#define MARK_BIN_EMPTY(tab, i) (set_bin(st_bins_ptr(tab), get_size_ind(tab), i, EMPTY_BIN)) /* Values used for not found entry and bin with given characteristics. */ @@ -407,7 +415,7 @@ set_bin(st_index_t *bins, int s, st_index_t n, st_index_t v) corresponding to deleted entries. */ #define MARK_BIN_DELETED(tab, i) \ do { \ - set_bin((tab)->bins, get_size_ind(tab), i, DELETED_BIN); \ + set_bin(st_bins_ptr(tab), get_size_ind(tab), i, DELETED_BIN); \ } while (0) /* Macros to check that value B is used empty bins and bins @@ -418,15 +426,22 @@ set_bin(st_index_t *bins, int s, st_index_t n, st_index_t v) /* Macros to check empty bins and bins corresponding to deleted entries. Bins are given by their index I in table TAB. */ -#define IND_EMPTY_BIN_P(tab, i) (EMPTY_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i))) -#define IND_DELETED_BIN_P(tab, i) (DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i))) -#define IND_EMPTY_OR_DELETED_BIN_P(tab, i) (EMPTY_OR_DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i))) +#define IND_EMPTY_BIN_P(tab, i) (EMPTY_BIN_P(get_bin(st_bins_ptr(tab), get_size_ind(tab), i))) +#define IND_DELETED_BIN_P(tab, i) (DELETED_BIN_P(get_bin(st_bins_ptr(tab), get_size_ind(tab), i))) +#define IND_EMPTY_OR_DELETED_BIN_P(tab, i) (EMPTY_OR_DELETED_BIN_P(get_bin(st_bins_ptr(tab), get_size_ind(tab), i))) /* Macros for marking and checking deleted entries given by their pointer E_PTR. */ #define MARK_ENTRY_DELETED(e_ptr) ((e_ptr)->hash = RESERVED_HASH_VAL) #define DELETED_ENTRY_P(e_ptr) ((e_ptr)->hash == RESERVED_HASH_VAL) +/* Return the number of allocated entries of table TAB. */ +static inline st_index_t +get_allocated_entries(const st_table *tab) +{ + return ((st_index_t) 1)<<tab->entry_power; +} + /* Return bin size index of table TAB. */ static inline unsigned int get_size_ind(const st_table *tab) @@ -448,6 +463,28 @@ bins_mask(const st_table *tab) return get_bins_num(tab) - 1; } +static inline bool +st_has_bins(const st_table *tab) +{ + return tab->entry_power > MAX_POWER2_FOR_TABLES_WITHOUT_BINS; +} + +static inline size_t +st_allocated_entries_size(const st_table *tab) +{ + return get_allocated_entries(tab) * sizeof(st_table_entry); +} + +static inline st_index_t * +st_bins_ptr(const st_table *tab) +{ + if (st_has_bins(tab)) { + return (st_index_t *)(((char *)tab->entries) + st_allocated_entries_size(tab)); + } + + return NULL; +} + /* Return the index of table TAB bin corresponding to HASH_VALUE. */ static inline st_index_t @@ -456,25 +493,21 @@ hash_bin(st_hash_t hash_value, st_table *tab) return hash_value & bins_mask(tab); } -/* Return the number of allocated entries of table TAB. */ -static inline st_index_t -get_allocated_entries(const st_table *tab) -{ - return ((st_index_t) 1)<<tab->entry_power; -} - /* Return size of the allocated bins of table TAB. */ static inline st_index_t bins_size(const st_table *tab) { - return features[tab->entry_power].bins_words * sizeof (st_index_t); + if (st_has_bins(tab)) { + return features[tab->entry_power].bins_words * sizeof (st_index_t); + } + return 0; } /* Mark all bins of table TAB as empty. */ static void initialize_bins(st_table *tab) { - memset(tab->bins, 0, bins_size(tab)); + memset(st_bins_ptr(tab), 0, bins_size(tab)); } /* Make table TAB empty. */ @@ -483,7 +516,7 @@ make_tab_empty(st_table *tab) { tab->num_entries = 0; tab->entries_start = tab->entries_bound = 0; - if (tab->bins != NULL) + if (st_bins_ptr(tab) != NULL) initialize_bins(tab); } @@ -545,19 +578,12 @@ st_init_existing_table_with_size(st_table *tab, const struct st_hash_type *type, tab->entry_power = n; tab->bin_power = features[n].bin_power; tab->size_ind = features[n].size_ind; - if (n <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) - tab->bins = NULL; - else { - tab->bins = (st_index_t *) malloc(bins_size(tab)); -#ifndef RUBY - if (tab->bins == NULL) { - free(tab); - return NULL; - } -#endif + + size_t memsize = get_allocated_entries(tab) * sizeof(st_table_entry); + if (tab->entry_power > MAX_POWER2_FOR_TABLES_WITHOUT_BINS) { + memsize += bins_size(tab); } - tab->entries = (st_table_entry *) malloc(get_allocated_entries(tab) - * sizeof(st_table_entry)); + tab->entries = (st_table_entry *)malloc(memsize); #ifndef RUBY if (tab->entries == NULL) { st_free_table(tab); @@ -569,6 +595,12 @@ st_init_existing_table_with_size(st_table *tab, const struct st_hash_type *type, return tab; } +st_table * +st_init_existing_numtable_with_size(st_table *tab, st_index_t size) +{ + return st_init_existing_table_with_size(tab, &type_numhash, size); +} + /* 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. */ @@ -585,7 +617,7 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size) st_init_existing_table_with_size(tab, type, size); #else if (st_init_existing_table_with_size(tab, type, size) == NULL) { - free(tab); + free_fixed_ptr(tab); return NULL; } #endif @@ -637,6 +669,13 @@ st_init_strtable_with_size(st_index_t size) return st_init_table_with_size(&type_strhash, size); } +st_table * +st_init_existing_strtable_with_size(st_table *tab, st_index_t size) +{ + return st_init_existing_table_with_size(tab, &type_strhash, size); +} + + /* Create and return table which can hold a minimal number of strings whose character case is ignored. */ st_table * @@ -661,22 +700,40 @@ st_clear(st_table *tab) tab->rebuilds_num++; } +static inline size_t +st_entries_memsize(const st_table *tab) +{ + return get_allocated_entries(tab) * sizeof(st_table_entry); +} + +static inline void +st_free_entries(const st_table *tab) +{ + sized_free(tab->entries, st_entries_memsize(tab) + bins_size(tab)); +} + +void +st_free_embedded_table(st_table *tab) +{ + st_free_entries(tab); +} + /* Free table TAB space. */ void st_free_table(st_table *tab) { - free(tab->bins); - free(tab->entries); - free(tab); + st_free_embedded_table(tab); + free_fixed_ptr(tab); } /* Return byte size of memory allocated for table TAB. */ size_t st_memsize(const st_table *tab) { + RUBY_ASSERT(tab != NULL); return(sizeof(st_table) - + (tab->bins == NULL ? 0 : bins_size(tab)) - + get_allocated_entries(tab) * sizeof(st_table_entry)); + + bins_size(tab) + + st_entries_memsize(tab)); } static st_index_t @@ -741,14 +798,14 @@ rebuild_table(st_table *tab) || tab->num_entries < (1 << MINIMAL_POWER2)) { /* Compaction: */ tab->num_entries = 0; - if (tab->bins != NULL) + if (st_has_bins(tab)) 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 + * gen_fields_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); @@ -771,7 +828,7 @@ rebuild_table_with(st_table *const new_tab, st_table *const tab) new_entries = new_tab->entries; ni = 0; - bins = new_tab->bins; + bins = st_bins_ptr(new_tab); size_ind = get_size_ind(new_tab); st_index_t bound = tab->entries_bound; st_table_entry *entries = tab->entries; @@ -798,14 +855,12 @@ 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) { + st_free_entries(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); + free_fixed_ptr(new_tab); } static void @@ -888,7 +943,7 @@ find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key) #endif FOUND_BIN; for (;;) { - bin = get_bin(tab->bins, get_size_ind(tab), ind); + bin = get_bin(st_bins_ptr(tab), 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)) @@ -934,7 +989,7 @@ find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key) #endif FOUND_BIN; for (;;) { - bin = get_bin(tab->bins, get_size_ind(tab), ind); + bin = get_bin(st_bins_ptr(tab), 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)) @@ -977,7 +1032,7 @@ find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key) #endif FOUND_BIN; for (;;) { - bin = get_bin(tab->bins, get_size_ind(tab), ind); + bin = get_bin(st_bins_ptr(tab), get_size_ind(tab), ind); if (EMPTY_OR_DELETED_BIN_P(bin)) return ind; #ifdef QUADRATIC_PROBE @@ -1025,7 +1080,7 @@ find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value, first_deleted_bin_ind = UNDEFINED_BIN_IND; entries = tab->entries; for (;;) { - entry_index = get_bin(tab->bins, get_size_ind(tab), ind); + entry_index = get_bin(st_bins_ptr(tab), get_size_ind(tab), ind); if (EMPTY_BIN_P(entry_index)) { tab->num_entries++; entry_index = UNDEFINED_ENTRY_IND; @@ -1066,7 +1121,7 @@ st_lookup(st_table *tab, st_data_t key, st_data_t *value) st_hash_t hash = do_hash(key, tab); retry: - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, hash, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -1095,7 +1150,7 @@ st_get_key(st_table *tab, st_data_t key, st_data_t *result) st_hash_t hash = do_hash(key, tab); retry: - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, hash, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -1141,7 +1196,7 @@ st_insert(st_table *tab, st_data_t key, st_data_t value) hash_value = do_hash(key, tab); retry: rebuild_table_if_necessary(tab); - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, hash_value, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -1165,7 +1220,7 @@ st_insert(st_table *tab, st_data_t key, st_data_t 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); + set_bin(st_bins_ptr(tab), get_size_ind(tab), bin_ind, ind + ENTRY_BASE); return 0; } tab->entries[bin].record = value; @@ -1191,9 +1246,9 @@ st_add_direct_with_hash(st_table *tab, entry->key = key; entry->record = value; tab->num_entries++; - if (tab->bins != NULL) { + if (st_has_bins(tab)) { 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(st_bins_ptr(tab), get_size_ind(tab), bin_ind, ind + ENTRY_BASE); } } @@ -1232,7 +1287,7 @@ st_insert2(st_table *tab, st_data_t key, st_data_t value, hash_value = do_hash(key, tab); retry: rebuild_table_if_necessary (tab); - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, hash_value, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -1257,7 +1312,7 @@ st_insert2(st_table *tab, st_data_t key, st_data_t 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); + set_bin(st_bins_ptr(tab), get_size_ind(tab), bin_ind, ind + ENTRY_BASE); return 0; } tab->entries[bin].record = value; @@ -1269,27 +1324,15 @@ st_table * st_replace(st_table *new_tab, st_table *old_tab) { *new_tab = *old_tab; - if (old_tab->bins == NULL) - new_tab->bins = NULL; - else { - new_tab->bins = (st_index_t *) malloc(bins_size(old_tab)); -#ifndef RUBY - if (new_tab->bins == NULL) { - return NULL; - } -#endif - } - new_tab->entries = (st_table_entry *) malloc(get_allocated_entries(old_tab) - * sizeof(st_table_entry)); + size_t memsize = get_allocated_entries(old_tab) * sizeof(st_table_entry); + memsize += bins_size(old_tab); + new_tab->entries = (st_table_entry *) malloc(memsize); #ifndef RUBY if (new_tab->entries == NULL) { return NULL; } #endif - MEMCPY(new_tab->entries, old_tab->entries, st_table_entry, - get_allocated_entries(old_tab)); - if (old_tab->bins != NULL) - MEMCPY(new_tab->bins, old_tab->bins, char, bins_size(old_tab)); + MEMCPY(new_tab->entries, old_tab->entries, char, memsize); return new_tab; } @@ -1344,7 +1387,7 @@ st_general_delete(st_table *tab, st_data_t *key, st_data_t *value) hash = do_hash(*key, tab); retry: - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, hash, *key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -1361,7 +1404,7 @@ st_general_delete(st_table *tab, st_data_t *key, st_data_t *value) if (value != 0) *value = 0; return 0; } - bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE; + bin = get_bin(st_bins_ptr(tab), get_size_ind(tab), bin_ind) - ENTRY_BASE; MARK_BIN_DELETED(tab, bin_ind); } entry = &tab->entries[bin]; @@ -1414,7 +1457,7 @@ st_shift(st_table *tab, st_data_t *key, st_data_t *value) if (value != 0) *value = curr_entry_ptr->record; *key = entry_key; retry: - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, entry_hash, entry_key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) { entries = tab->entries; @@ -1428,7 +1471,7 @@ st_shift(st_table *tab, st_data_t *key, st_data_t *value) entries = tab->entries; goto retry; } - curr_entry_ptr = &entries[get_bin(tab->bins, get_size_ind(tab), bin_ind) + curr_entry_ptr = &entries[get_bin(st_bins_ptr(tab), get_size_ind(tab), bin_ind) - ENTRY_BASE]; MARK_BIN_DELETED(tab, bin_ind); } @@ -1472,7 +1515,7 @@ st_update(st_table *tab, st_data_t key, retry: entries = tab->entries; - if (tab->bins == NULL) { + if (!st_has_bins(tab)) { bin = find_entry(tab, hash, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -1486,7 +1529,7 @@ st_update(st_table *tab, st_data_t key, goto retry; existing = bin_ind != UNDEFINED_BIN_IND; if (existing) { - bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE; + bin = get_bin(st_bins_ptr(tab), get_size_ind(tab), bin_ind) - ENTRY_BASE; entry = &entries[bin]; } } @@ -1495,7 +1538,16 @@ st_update(st_table *tab, st_data_t key, value = entry->record; } old_key = key; + + unsigned int rebuilds_num = tab->rebuilds_num; + retval = (*func)(&key, &value, arg, existing); + + // We need to make sure that the callback didn't cause a table rebuild + // Ideally we would make sure no operations happened + assert(rebuilds_num == tab->rebuilds_num); + (void)rebuilds_num; + switch (retval) { case ST_CONTINUE: if (! existing) { @@ -1539,7 +1591,7 @@ st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_updat st_index_t i, rebuilds_num; st_hash_t hash; st_data_t key; - int error_p, packed_p = tab->bins == NULL; + int error_p, packed_p = !st_has_bins(tab); entries = tab->entries; /* The bound can change inside the loop even without rebuilding @@ -1564,7 +1616,7 @@ st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_updat if (rebuilds_num != tab->rebuilds_num) { retry: entries = tab->entries; - packed_p = tab->bins == NULL; + packed_p = !st_has_bins(tab); if (packed_p) { i = find_entry(tab, hash, key); if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0)) @@ -1612,7 +1664,7 @@ st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_updat goto again; if (bin_ind == UNDEFINED_BIN_IND) break; - bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE; + bin = get_bin(st_bins_ptr(tab), get_size_ind(tab), bin_ind) - ENTRY_BASE; MARK_BIN_DELETED(tab, bin_ind); } curr_entry_ptr = &entries[bin]; @@ -2125,16 +2177,14 @@ st_expand_table(st_table *tab, st_index_t siz) tmp = st_init_table_with_size(tab->type, siz); n = get_allocated_entries(tab); MEMCPY(tmp->entries, tab->entries, st_table_entry, n); - free(tab->entries); - free(tab->bins); - free(tmp->bins); + st_free_entries(tab); + tab->entry_power = tmp->entry_power; tab->bin_power = tmp->bin_power; tab->size_ind = tmp->size_ind; tab->entries = tmp->entries; - tab->bins = NULL; tab->rebuilds_num++; - free(tmp); + free_fixed_ptr(tmp); } /* Rehash using linear search. Return TRUE if we found that the table @@ -2146,9 +2196,6 @@ st_rehash_linear(st_table *tab) st_index_t i, j; st_table_entry *p, *q; - 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)) @@ -2178,10 +2225,8 @@ st_rehash_indexed(st_table *tab) { int eq_p, rebuilt_p; st_index_t i; - st_index_t const n = bins_size(tab); + unsigned int const size_ind = get_size_ind(tab); - st_index_t *bins = realloc(tab->bins, n); - tab->bins = bins; initialize_bins(tab); for (i = tab->entries_start; i < tab->entries_bound; i++) { st_table_entry *p = &tab->entries[i]; @@ -2197,10 +2242,10 @@ st_rehash_indexed(st_table *tab) ind = hash_bin(p->hash, tab); for (;;) { - st_index_t bin = get_bin(bins, size_ind, ind); + st_index_t bin = get_bin(st_bins_ptr(tab), size_ind, ind); if (EMPTY_OR_DELETED_BIN_P(bin)) { /* ok, new room */ - set_bin(bins, size_ind, ind, i + ENTRY_BASE); + set_bin(st_bins_ptr(tab), size_ind, ind, i + ENTRY_BASE); break; } else { @@ -2240,7 +2285,7 @@ st_rehash(st_table *tab) int rebuilt_p; do { - if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) + if (tab->entry_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) rebuilt_p = st_rehash_linear(tab); else rebuilt_p = st_rehash_indexed(tab); @@ -2314,7 +2359,7 @@ rb_hash_bulk_insert_into_st_table(long argc, const VALUE *argv, VALUE hash) st_insert_generic(tab, argc, argv, hash); else if (argc <= 2) st_insert_single(tab, hash, argv[0], argv[1]); - else if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) + else if (tab->entry_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) st_insert_linear(tab, argc, argv, hash); else st_insert_generic(tab, argc, argv, hash); @@ -2386,18 +2431,44 @@ set_get_allocated_entries(const set_table *tab) return ((st_index_t) 1)<<tab->entry_power; } +static inline size_t +set_allocated_entries_size(const set_table *tab) +{ + return set_get_allocated_entries(tab) * sizeof(set_table_entry); +} + +static inline bool +set_has_bins(const set_table *tab) +{ + return tab->entry_power > MAX_POWER2_FOR_TABLES_WITHOUT_BINS; +} + /* Return size of the allocated bins of table TAB. */ static inline st_index_t set_bins_size(const set_table *tab) { - return features[tab->entry_power].bins_words * sizeof (st_index_t); + if (set_has_bins(tab)) { + return features[tab->entry_power].bins_words * sizeof (st_index_t); + } + + return 0; +} + +static inline st_index_t * +set_bins_ptr(const set_table *tab) +{ + if (set_has_bins(tab)) { + return (st_index_t *)(((char *)tab->entries) + set_allocated_entries_size(tab)); + } + + return NULL; } /* Mark all bins of table TAB as empty. */ static void set_initialize_bins(set_table *tab) { - memset(tab->bins, 0, set_bins_size(tab)); + memset(set_bins_ptr(tab), 0, set_bins_size(tab)); } /* Make table TAB empty. */ @@ -2406,10 +2477,20 @@ set_make_tab_empty(set_table *tab) { tab->num_entries = 0; tab->entries_start = tab->entries_bound = 0; - if (tab->bins != NULL) + if (set_bins_ptr(tab) != NULL) set_initialize_bins(tab); } +static inline size_t +set_entries_memsize(set_table *tab) +{ + size_t memsize = set_get_allocated_entries(tab) * sizeof(set_table_entry); + if (set_has_bins(tab)) { + memsize += set_bins_size(tab); + } + return memsize; +} + static set_table * set_init_existing_table_with_size(set_table *tab, const struct st_hash_type *type, st_index_t size) { @@ -2434,13 +2515,8 @@ set_init_existing_table_with_size(set_table *tab, const struct st_hash_type *typ tab->entry_power = n; tab->bin_power = features[n].bin_power; tab->size_ind = features[n].size_ind; - if (n <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS) - tab->bins = NULL; - else { - tab->bins = (st_index_t *) malloc(set_bins_size(tab)); - } - tab->entries = (set_table_entry *) malloc(set_get_allocated_entries(tab) - * sizeof(set_table_entry)); + + tab->entries = (set_table_entry *)malloc(set_entries_memsize(tab)); set_make_tab_empty(tab); tab->rebuilds_num = 0; return tab; @@ -2465,6 +2541,18 @@ set_init_numtable(void) return set_init_table_with_size(NULL, &type_numhash, 0); } +set_table * +set_init_numtable_with_size(st_index_t size) +{ + return set_init_table_with_size(NULL, &type_numhash, size); +} + +set_table * +set_init_embedded_numtable_with_size(set_table *tab, st_index_t size) +{ + return set_init_existing_table_with_size(tab, &type_numhash, size); +} + size_t set_table_size(const struct set_table *tbl) { @@ -2473,20 +2561,25 @@ set_table_size(const struct set_table *tbl) /* Make table TAB empty. */ void -set_clear(set_table *tab) +set_table_clear(set_table *tab) { set_make_tab_empty(tab); tab->rebuilds_num++; } +void +set_free_embedded_table(set_table *tab) +{ + sized_free(tab->entries, set_entries_memsize(tab)); +} + /* Free table TAB space. This should only be used if you passed NULL to set_init_table_with_size/set_copy when creating the table. */ void set_free_table(set_table *tab) { - free(tab->bins); - free(tab->entries); - free(tab); + set_free_embedded_table(tab); + free_fixed_ptr(tab); } /* Return byte size of memory allocated for table TAB. */ @@ -2494,7 +2587,7 @@ size_t set_memsize(const set_table *tab) { return(sizeof(set_table) - + (tab->bins == NULL ? 0 : set_bins_size(tab)) + + (tab->entry_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS ? 0 : set_bins_size(tab)) + set_get_allocated_entries(tab) * sizeof(set_table_entry)); } @@ -2527,14 +2620,14 @@ set_rebuild_table(set_table *tab) || tab->num_entries < (1 << MINIMAL_POWER2)) { /* Compaction: */ tab->num_entries = 0; - if (tab->bins != NULL) + if (set_has_bins(tab)) set_initialize_bins(tab); set_rebuild_table_with(tab, tab); } else { set_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 + * gen_fields_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 = set_init_table_with_size(NULL, tab->type, 2 * tab->num_entries - 1); @@ -2557,7 +2650,7 @@ set_rebuild_table_with(set_table *const new_tab, set_table *const tab) new_entries = new_tab->entries; ni = 0; - bins = new_tab->bins; + bins = set_bins_ptr(new_tab); size_ind = set_get_size_ind(new_tab); st_index_t bound = tab->entries_bound; set_table_entry *entries = tab->entries; @@ -2584,14 +2677,14 @@ set_rebuild_table_with(set_table *const new_tab, set_table *const tab) static void set_rebuild_move_table(set_table *const new_tab, set_table *const tab) { + sized_free(tab->entries, set_entries_memsize(tab)); + tab->entries = new_tab->entries; + 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); + + free_fixed_ptr(new_tab); } static void @@ -2673,7 +2766,7 @@ set_find_table_entry_ind(set_table *tab, st_hash_t hash_value, st_data_t key) perturb = hash_value; #endif for (;;) { - bin = get_bin(tab->bins, set_get_size_ind(tab), ind); + bin = get_bin(set_bins_ptr(tab), set_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)) @@ -2717,7 +2810,7 @@ set_find_table_bin_ind(set_table *tab, st_hash_t hash_value, st_data_t key) perturb = hash_value; #endif for (;;) { - bin = get_bin(tab->bins, set_get_size_ind(tab), ind); + bin = get_bin(set_bins_ptr(tab), set_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)) @@ -2758,7 +2851,7 @@ set_find_table_bin_ind_direct(set_table *tab, st_hash_t hash_value, st_data_t ke perturb = hash_value; #endif for (;;) { - bin = get_bin(tab->bins, set_get_size_ind(tab), ind); + bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), ind); if (EMPTY_OR_DELETED_BIN_P(bin)) return ind; #ifdef QUADRATIC_PROBE @@ -2772,7 +2865,7 @@ set_find_table_bin_ind_direct(set_table *tab, st_hash_t hash_value, st_data_t ke /* Mark I-th bin of table TAB as empty, in other words not corresponding to any entry. */ -#define MARK_SET_BIN_EMPTY(tab, i) (set_bin((tab)->bins, set_get_size_ind(tab), i, EMPTY_BIN)) +#define MARK_SET_BIN_EMPTY(tab, i) (set_bin(set_bins_ptr(tab), set_get_size_ind(tab), i, EMPTY_BIN)) /* Return index of table TAB bin for HASH_VALUE and KEY through BIN_IND and the pointed value as the function result. Reserve the @@ -2808,7 +2901,7 @@ set_find_table_bin_ptr_and_reserve(set_table *tab, st_hash_t *hash_value, firset_deleted_bin_ind = UNDEFINED_BIN_IND; entries = tab->entries; for (;;) { - entry_index = get_bin(tab->bins, set_get_size_ind(tab), ind); + entry_index = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), ind); if (EMPTY_BIN_P(entry_index)) { tab->num_entries++; entry_index = UNDEFINED_ENTRY_IND; @@ -2842,13 +2935,13 @@ set_find_table_bin_ptr_and_reserve(set_table *tab, st_hash_t *hash_value, /* Find an entry with KEY in table TAB. Return non-zero if we found it. */ int -set_lookup(set_table *tab, st_data_t key) +set_table_lookup(set_table *tab, st_data_t key) { st_index_t bin; st_hash_t hash = set_do_hash(key, tab); retry: - if (tab->bins == NULL) { + if (!set_has_bins(tab)) { bin = set_find_entry(tab, hash, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -2892,7 +2985,7 @@ set_insert(set_table *tab, st_data_t key) hash_value = set_do_hash(key, tab); retry: set_rebuild_table_if_necessary(tab); - if (tab->bins == NULL) { + if (!set_has_bins(tab)) { bin = set_find_entry(tab, hash_value, key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -2915,7 +3008,7 @@ set_insert(set_table *tab, st_data_t key) entry->hash = hash_value; entry->key = key; if (bin_ind != UNDEFINED_BIN_IND) - set_bin(tab->bins, set_get_size_ind(tab), bin_ind, ind + ENTRY_BASE); + set_bin(set_bins_ptr(tab), set_get_size_ind(tab), bin_ind, ind + ENTRY_BASE); return 0; } return 1; @@ -2926,18 +3019,9 @@ static set_table * set_replace(set_table *new_tab, set_table *old_tab) { *new_tab = *old_tab; - if (old_tab->bins == NULL) - new_tab->bins = NULL; - else { - new_tab->bins = (st_index_t *) malloc(set_bins_size(old_tab)); - } - new_tab->entries = (set_table_entry *) malloc(set_get_allocated_entries(old_tab) - * sizeof(set_table_entry)); - MEMCPY(new_tab->entries, old_tab->entries, set_table_entry, - set_get_allocated_entries(old_tab)); - if (old_tab->bins != NULL) - MEMCPY(new_tab->bins, old_tab->bins, char, set_bins_size(old_tab)); - + size_t memsize = set_allocated_entries_size(old_tab) + set_bins_size(old_tab); + new_tab->entries = (set_table_entry *)malloc(memsize); + MEMCPY(new_tab->entries, old_tab->entries, char, memsize); return new_tab; } @@ -2976,13 +3060,13 @@ set_update_range_for_deleted(set_table *tab, st_index_t n) corresponding to deleted entries. */ #define MARK_SET_BIN_DELETED(tab, i) \ do { \ - set_bin((tab)->bins, set_get_size_ind(tab), i, DELETED_BIN); \ + set_bin(set_bins_ptr(tab), set_get_size_ind(tab), i, DELETED_BIN); \ } while (0) /* Delete entry with KEY from table TAB, and return non-zero. If there is no entry with KEY in the table, return zero. */ int -set_delete(set_table *tab, st_data_t *key) +set_table_delete(set_table *tab, st_data_t *key) { set_table_entry *entry; st_index_t bin; @@ -2991,7 +3075,7 @@ set_delete(set_table *tab, st_data_t *key) hash = set_do_hash(*key, tab); retry: - if (tab->bins == NULL) { + if (!set_has_bins(tab)) { bin = set_find_entry(tab, hash, *key); if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) goto retry; @@ -3006,7 +3090,7 @@ set_delete(set_table *tab, st_data_t *key) if (bin_ind == UNDEFINED_BIN_IND) { return 0; } - bin = get_bin(tab->bins, set_get_size_ind(tab), bin_ind) - ENTRY_BASE; + bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), bin_ind) - ENTRY_BASE; MARK_SET_BIN_DELETED(tab, bin_ind); } entry = &tab->entries[bin]; @@ -3037,7 +3121,7 @@ set_general_foreach(set_table *tab, set_foreach_check_callback_func *func, st_index_t i, rebuilds_num; st_hash_t hash; st_data_t key; - int error_p, packed_p = tab->bins == NULL; + int error_p, packed_p = !set_has_bins(tab); entries = tab->entries; /* The bound can change inside the loop even without rebuilding @@ -3059,7 +3143,7 @@ set_general_foreach(set_table *tab, set_foreach_check_callback_func *func, if (rebuilds_num != tab->rebuilds_num) { retry: entries = tab->entries; - packed_p = tab->bins == NULL; + packed_p = !set_has_bins(tab); if (packed_p) { i = set_find_entry(tab, hash, key); if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0)) @@ -3107,7 +3191,7 @@ set_general_foreach(set_table *tab, set_foreach_check_callback_func *func, goto again; if (bin_ind == UNDEFINED_BIN_IND) break; - bin = get_bin(tab->bins, set_get_size_ind(tab), bin_ind) - ENTRY_BASE; + bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), bin_ind) - ENTRY_BASE; MARK_SET_BIN_DELETED(tab, bin_ind); } curr_entry_ptr = &entries[bin]; @@ -3140,7 +3224,7 @@ set_apply_functor(st_data_t k, st_data_t d, int _) } int -set_foreach(set_table *tab, set_foreach_callback_func *func, st_data_t arg) +set_table_foreach(set_table *tab, set_foreach_callback_func *func, st_data_t arg) { const struct set_functor f = { func, arg }; return set_general_foreach(tab, set_apply_functor, NULL, (st_data_t)&f, FALSE); |