From 3007acfbc6faaf65148697edcb9907ba23551e85 Mon Sep 17 00:00:00 2001 From: nobu Date: Sat, 10 Mar 2012 14:52:30 +0000 Subject: * st.c: pack tables also generic keys. patched by Sokolov Yura at https://github.com/ruby/ruby/pull/84 git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@34964 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- st.c | 101 ++++++++++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 63 insertions(+), 38 deletions(-) (limited to 'st.c') diff --git a/st.c b/st.c index 9fb29f6201..ad943e925d 100644 --- a/st.c +++ b/st.c @@ -26,6 +26,7 @@ struct st_table_entry { }; typedef struct st_packed_entry { + st_index_t hash; st_data_t key, val; } st_packed_entry; @@ -34,7 +35,7 @@ typedef struct st_packed_entry { #define ST_DEFAULT_MAX_DENSITY 5 #define ST_DEFAULT_INIT_TABLE_SIZE 11 #define ST_DEFAULT_SECOND_TABLE_SIZE 19 -#define ST_DEFAULT_PACKED_TABLE_SIZE ST_DEFAULT_INIT_TABLE_SIZE +#define ST_DEFAULT_PACKED_TABLE_SIZE 18 #define PACKED_UNIT (int)(sizeof(st_packed_entry) / sizeof(st_table_entry*)) #define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry)) @@ -112,9 +113,10 @@ st_realloc_bins(st_table_entry **bins, st_index_t newsize, st_index_t oldsize) #define PACKED_ENT(table, i) PACKED_BINS(table)[i] #define PKEY(table, i) PACKED_ENT((table), (i)).key #define PVAL(table, i) PACKED_ENT((table), (i)).val -#define PHASH(table, i) PKEY((table), (i)) +#define PHASH(table, i) PACKED_ENT((table), (i)).hash #define PKEY_SET(table, i, v) (PKEY((table), (i)) = (v)) #define PVAL_SET(table, i, v) (PVAL((table), (i)) = (v)) +#define PHASH_SET(table, i, v) (PHASH((table), (i)) = (v)) /* this function depends much on packed layout, so that it placed here */ static inline void @@ -232,12 +234,17 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size) } #endif - size = new_size(size); /* round up to prime number */ tbl = st_alloc_table(); tbl->type = type; tbl->num_entries = 0; - tbl->entries_packed = type == &type_numhash && size/PACKED_UNIT <= MAX_PACKED_HASH; + tbl->entries_packed = size <= MAX_PACKED_HASH; + if (tbl->entries_packed) { + size = ST_DEFAULT_PACKED_TABLE_SIZE; + } + else { + size = new_size(size); /* round up to prime number */ + } tbl->num_bins = size; tbl->bins = st_alloc_bins(size); tbl->head = 0; @@ -377,10 +384,13 @@ find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_p } static inline st_index_t -find_packed_index(st_table *table, st_data_t key) +find_packed_index(st_table *table, st_index_t hash_val, st_data_t key) { st_index_t i = 0; - while (i < table->real_entries && PKEY(table, i) != key) i++; + while (i < table->real_entries && + (PHASH(table, i) != hash_val || !EQUAL(table, key, PKEY(table, i)))) { + i++; + } return i; } @@ -392,8 +402,10 @@ st_lookup(st_table *table, register st_data_t key, st_data_t *value) st_index_t hash_val; register st_table_entry *ptr; + hash_val = do_hash(key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, key); + st_index_t i = find_packed_index(table, hash_val, key); if (i < table->real_entries) { if (value != 0) *value = PVAL(table, i); return 1; @@ -401,7 +413,6 @@ st_lookup(st_table *table, register st_data_t key, st_data_t *value) return 0; } - hash_val = do_hash(key, table); ptr = find_entry(table, key, hash_val, hash_val % table->num_bins); if (ptr == 0) { @@ -419,8 +430,10 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result) st_index_t hash_val; register st_table_entry *ptr; + hash_val = do_hash(key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, key); + st_index_t i = find_packed_index(table, hash_val, key); if (i < table->real_entries) { if (result != 0) *result = PKEY(table, i); return 1; @@ -428,7 +441,6 @@ st_get_key(st_table *table, register st_data_t key, st_data_t *result) return 0; } - hash_val = do_hash(key, table); ptr = find_entry(table, key, hash_val, hash_val % table->num_bins); if (ptr == 0) { @@ -504,8 +516,7 @@ unpack_entries(register st_table *table) do { st_data_t key = packed_bins[i].key; st_data_t val = packed_bins[i].val; - /* packed table should be numhash */ - st_index_t hash = st_numhash(key); + st_index_t hash = packed_bins[i].hash; entry = new_entry(&tmp_table, key, val, hash, hash % ST_DEFAULT_INIT_TABLE_SIZE); *chain = entry; @@ -519,17 +530,18 @@ unpack_entries(register st_table *table) } static void -add_packed_direct(st_table *table, st_data_t key, st_data_t value) +add_packed_direct(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val) { if (table->real_entries < MAX_PACKED_HASH) { st_index_t i = table->real_entries++; PKEY_SET(table, i, key); PVAL_SET(table, i, value); + PHASH_SET(table, i, hash_val); table->num_entries++; } else { unpack_entries(table); - add_direct(table, key, value, key, key % table->num_bins); + add_direct(table, key, value, hash_val, hash_val % table->num_bins); } } @@ -541,17 +553,18 @@ st_insert(register st_table *table, register st_data_t key, st_data_t value) register st_index_t bin_pos; register st_table_entry *ptr; + hash_val = do_hash(key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, key); + st_index_t i = find_packed_index(table, hash_val, key); if (i < table->real_entries) { PVAL_SET(table, i, value); return 1; } - add_packed_direct(table, key, value); + add_packed_direct(table, key, value, hash_val); return 0; } - hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) { @@ -572,17 +585,19 @@ st_insert2(register st_table *table, register st_data_t key, st_data_t value, register st_index_t bin_pos; register st_table_entry *ptr; + hash_val = do_hash(key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, key); + st_index_t i = find_packed_index(table, hash_val, key); if (i < table->real_entries) { PVAL_SET(table, i, value); return 1; - } - add_packed_direct(table, key, value); + } + key = (*func)(key); + add_packed_direct(table, key, value, hash_val); return 0; } - hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) { @@ -601,12 +616,12 @@ st_add_direct(st_table *table, st_data_t key, st_data_t value) { st_index_t hash_val; + hash_val = do_hash(key, table); if (table->entries_packed) { - add_packed_direct(table, key, value); + add_packed_direct(table, key, value, hash_val); return; } - hash_val = do_hash(key, table); add_direct(table, key, value, hash_val, hash_val % table->num_bins); } @@ -703,10 +718,13 @@ st_delete(register st_table *table, register st_data_t *key, st_data_t *value) st_table_entry **prev; register st_table_entry *ptr; + hash_val = do_hash(*key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, *key); + st_index_t i = find_packed_index(table, hash_val, *key); if (i < table->num_entries) { if (value != 0) *value = PVAL(table, i); + *key = PKEY(table, i); remove_packed_entry(table, i); return 1; } @@ -714,9 +732,8 @@ st_delete(register st_table *table, register st_data_t *key, st_data_t *value) return 0; } - hash_val = do_hash_bin(*key, table); - - for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) { + prev = &table->bins[hash_val % table->num_bins]; + for (;(ptr = *prev) != 0; prev = &ptr->next) { if (EQUAL(table, *key, ptr->key)) { *prev = ptr->next; remove_entry(table, ptr); @@ -737,11 +754,16 @@ st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *val st_index_t hash_val; register st_table_entry *ptr; + hash_val = do_hash(*key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, *key); + st_index_t i = find_packed_index(table, hash_val, *key); if (i < table->real_entries) { if (value != 0) *value = PVAL(table, i); + *key = PKEY(table, i); PKEY_SET(table, i, never); + PVAL_SET(table, i, never); + PHASH_SET(table, i, 0); table->num_entries--; return 1; } @@ -749,8 +771,7 @@ st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *val return 0; } - hash_val = do_hash_bin(*key, table); - ptr = table->bins[hash_val]; + ptr = table->bins[hash_val % table->num_bins]; for (; ptr != 0; ptr = ptr->next) { if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { @@ -811,13 +832,14 @@ st_update(st_table *table, st_data_t key, int (*func)(st_data_t key, st_data_t * st_data_t value; int retval; + hash_val = do_hash(key, table); + if (table->entries_packed) { - st_index_t i = find_packed_index(table, key); + st_index_t i = find_packed_index(table, hash_val, key); if (i < table->real_entries) { value = PVAL(table, i); retval = (*func)(key, &value, arg); if (!table->entries_packed) { - hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) return 0; goto unpacked; @@ -834,7 +856,6 @@ st_update(st_table *table, st_data_t key, int (*func)(st_data_t key, st_data_t * return 0; } - hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) { @@ -875,12 +896,14 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t if (table->entries_packed) { for (i = 0; i < table->real_entries; i++) { st_data_t key, val; + st_index_t hash; key = PKEY(table, i); val = PVAL(table, i); + hash = PHASH(table, i); if (key == never) continue; retval = (*func)(key, val, arg); if (!table->entries_packed) { - FIND_ENTRY(table, ptr, key, i); + FIND_ENTRY(table, ptr, hash, i); if (retval == ST_CHECK) { if (!ptr) goto deleted; goto unpacked_continue; @@ -889,10 +912,11 @@ st_foreach_check(st_table *table, int (*func)(ANYARGS), st_data_t arg, st_data_t } switch (retval) { case ST_CHECK: /* check if hash is modified during iteration */ - if (PKEY(table, i) == never) { + if (PHASH(table, i) == 0 && PKEY(table, i) == never) { break; } - if (i != find_packed_index(table, key)) { + i = find_packed_index(table, hash, key); + if (i == table->real_entries) { goto deleted; } /* fall through */ @@ -964,12 +988,13 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) if (table->entries_packed) { for (i = 0; i < table->real_entries; i++) { - st_data_t key, val; + st_data_t key, val, hash; key = PKEY(table, i); val = PVAL(table, i); + hash = PHASH(table, i); retval = (*func)(key, val, arg); if (!table->entries_packed) { - FIND_ENTRY(table, ptr, key, i); + FIND_ENTRY(table, ptr, hash, i); if (!ptr) return 0; goto unpacked; } -- cgit v1.2.3