ruby-changes:22913
From: nobu <ko1@a...>
Date: Sat, 10 Mar 2012 23:52:22 +0900 (JST)
Subject: [ruby-changes:22913] nobu:r34962 (trunk): * st.c: fix packed num_entries on delete_safe. patched by Sokolov
nobu 2012-03-10 23:52:06 +0900 (Sat, 10 Mar 2012) New Revision: 34962 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=34962 Log: * st.c: fix packed num_entries on delete_safe. patched by Sokolov Yura at https://github.com/ruby/ruby/pull/84 Modified files: trunk/ChangeLog trunk/ext/-test-/st/numhash/numhash.c trunk/include/ruby/st.h trunk/st.c trunk/test/-ext-/st/test_numhash.rb Index: include/ruby/st.h =================================================================== --- include/ruby/st.h (revision 34961) +++ include/ruby/st.h (revision 34962) @@ -96,7 +96,10 @@ struct st_table_entry **bins; struct st_table_entry *head, *tail; } big; - struct st_packed_bins *packed; + struct { + struct st_packed_entry *entries; + st_index_t real_entries; + } packed; } as; }; Index: ChangeLog =================================================================== --- ChangeLog (revision 34961) +++ ChangeLog (revision 34962) @@ -1,3 +1,8 @@ +Sat Mar 10 23:52:03 2012 Nobuyoshi Nakada <nobu@r...> + + * st.c: fix packed num_entries on delete_safe. patched by Sokolov + Yura at https://github.com/ruby/ruby/pull/84 + Fri Mar 9 14:29:32 2012 Shugo Maeda <shugo@r...> * enumerator.c (lazy_flat_map): add Enumerable::Lazy#flat_map. Index: st.c =================================================================== --- st.c (revision 34961) +++ st.c (revision 34962) @@ -38,12 +38,8 @@ #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)) -typedef struct st_packed_bins { - st_packed_entry kv[MAX_PACKED_HASH]; -} st_packed_bins; - STATIC_ASSERT(st_packed_entry, sizeof(st_packed_entry) == sizeof(st_table_entry*[PACKED_UNIT])) -STATIC_ASSERT(st_packed_bins, sizeof(st_packed_bins) <= sizeof(st_table_entry*[ST_DEFAULT_PACKED_TABLE_SIZE])) +STATIC_ASSERT(st_packed_bins, sizeof(st_packed_entry[MAX_PACKED_HASH]) <= sizeof(st_table_entry*[ST_DEFAULT_PACKED_TABLE_SIZE])) /* * DEFAULT_MAX_DENSITY is the default for the largest we allow the @@ -109,10 +105,11 @@ #define bins as.big.bins #define head as.big.head #define tail as.big.tail +#define real_entries as.packed.real_entries /* preparation for possible packing improvements */ -#define PACKED_BINS(table) (*(table)->as.packed) -#define PACKED_ENT(table, i) PACKED_BINS(table).kv[i] +#define PACKED_BINS(table) ((table)->as.packed.entries) +#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)) @@ -123,10 +120,11 @@ static inline void remove_packed_entry(st_table *table, st_index_t i) { + table->real_entries--; table->num_entries--; - if (i < table->num_entries) { + if (i < table->real_entries) { MEMMOVE(&PACKED_ENT(table, i), &PACKED_ENT(table, i+1), - st_packed_entry, table->num_entries - i); + st_packed_entry, table->real_entries - i); } } @@ -298,6 +296,7 @@ if (table->entries_packed) { table->num_entries = 0; + table->real_entries = 0; return; } @@ -381,7 +380,7 @@ find_packed_index(st_table *table, st_data_t key) { st_index_t i = 0; - while (i < table->num_entries && PKEY(table, i) != key) i++; + while (i < table->real_entries && PKEY(table, i) != key) i++; return i; } @@ -395,7 +394,7 @@ if (table->entries_packed) { st_index_t i = find_packed_index(table, key); - if (i < table->num_entries) { + if (i < table->real_entries) { if (value != 0) *value = PVAL(table, i); return 1; } @@ -422,7 +421,7 @@ if (table->entries_packed) { st_index_t i = find_packed_index(table, key); - if (i < table->num_entries) { + if (i < table->real_entries) { if (result != 0) *result = PKEY(table, i); return 1; } @@ -487,14 +486,13 @@ unpack_entries(register st_table *table) { st_index_t i; - st_packed_bins packed_bins; + st_packed_entry packed_bins[MAX_PACKED_HASH]; register st_table_entry *entry, *preventry = 0, **chain; st_table tmp_table = *table; - packed_bins = PACKED_BINS(table); - table->as.packed = &packed_bins; + MEMCPY(packed_bins, PACKED_BINS(table), st_packed_entry, MAX_PACKED_HASH); + table->as.packed.entries = packed_bins; tmp_table.entries_packed = 0; - tmp_table.num_entries = MAX_PACKED_HASH; #if ST_DEFAULT_INIT_TABLE_SIZE == ST_DEFAULT_PACKED_TABLE_SIZE MEMZERO(tmp_table.bins, st_table_entry*, tmp_table.num_bins); #else @@ -504,8 +502,8 @@ i = 0; chain = &tmp_table.head; do { - st_data_t key = packed_bins.kv[i].key; - st_data_t val = packed_bins.kv[i].val; + 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); entry = new_entry(&tmp_table, key, val, hash, @@ -523,10 +521,11 @@ static void add_packed_direct(st_table *table, st_data_t key, st_data_t value) { - if (table->num_entries < MAX_PACKED_HASH) { - st_index_t i = table->num_entries++; + if (table->real_entries < MAX_PACKED_HASH) { + st_index_t i = table->real_entries++; PKEY_SET(table, i, key); PVAL_SET(table, i, value); + table->num_entries++; } else { unpack_entries(table); @@ -544,7 +543,7 @@ if (table->entries_packed) { st_index_t i = find_packed_index(table, key); - if (i < table->num_entries) { + if (i < table->real_entries) { PVAL_SET(table, i, value); return 1; } @@ -575,7 +574,7 @@ if (table->entries_packed) { st_index_t i = find_packed_index(table, key); - if (i < table->num_entries) { + if (i < table->real_entries) { PVAL_SET(table, i, value); return 1; } @@ -740,9 +739,10 @@ if (table->entries_packed) { st_index_t i = find_packed_index(table, *key); - if (i < table->num_entries) { + if (i < table->real_entries) { if (value != 0) *value = PVAL(table, i); PKEY_SET(table, i, never); + table->num_entries--; return 1; } if (value != 0) *value = 0; @@ -775,13 +775,15 @@ if (table->entries_packed) { st_index_t i = 0, j = 0; while (PKEY(table, i) != never) { - if (i++ == table->num_entries) return; + if (i++ == table->real_entries) return; } - for (j = i; ++i < table->num_entries;) { + for (j = i; ++i < table->real_entries;) { if (PKEY(table, i) == never) continue; PACKED_ENT(table, j) = PACKED_ENT(table, i); j++; } + table->real_entries = j; + /* table->num_entries really should be equal j at this moment, but let set it anyway */ table->num_entries = j; return; } @@ -811,7 +813,7 @@ if (table->entries_packed) { st_index_t i = find_packed_index(table, key); - if (i < table->num_entries) { + if (i < table->real_entries) { value = PVAL(table, i); retval = (*func)(key, &value, arg); if (!table->entries_packed) { @@ -871,8 +873,7 @@ st_index_t i; if (table->entries_packed) { - for (i = 0; i < table->num_entries; i++) { - st_index_t j; + for (i = 0; i < table->real_entries; i++) { st_data_t key, val; key = PKEY(table, i); val = PVAL(table, i); @@ -887,13 +888,9 @@ } switch (retval) { case ST_CHECK: /* check if hash is modified during iteration */ - for (j = 0; j < table->num_entries; j++) { - if (PKEY(table, j) == key) - break; - } - if (j == table->num_entries) { + if (i != find_packed_index(table, key)) { goto deleted; - } + } /* fall through */ case ST_CONTINUE: break; Index: ext/-test-/st/numhash/numhash.c =================================================================== --- ext/-test-/st/numhash/numhash.c (revision 34961) +++ ext/-test-/st/numhash/numhash.c (revision 34962) @@ -81,6 +81,28 @@ return Qfalse; } +#if SIZEOF_LONG == SIZEOF_VOIDP +# define ST2NUM(x) ULONG2NUM(x) +#elif SIZEOF_LONG_LONG == SIZEOF_VOIDP +# define ST2NUM(x) ULL2NUM(x) +#endif + +static VALUE +numhash_size(VALUE self) +{ + return ST2NUM(((st_table *)DATA_PTR(self))->num_entries); +} + +static VALUE +numhash_delete_safe(VALUE self, VALUE key) +{ + st_data_t val, k = (st_data_t)key; + if (st_delete_safe((st_table *)DATA_PTR(self), &k, &val, (st_data_t)self)) { + return val; + } + return Qnil; +} + void Init_numhash(void) { @@ -91,5 +113,7 @@ rb_define_method(st, "[]=", numhash_aset, 2); rb_define_method(st, "each", numhash_each, 0); rb_define_method(st, "update", numhash_update, 1); + rb_define_method(st, "size", numhash_size, 0); + rb_define_method(st, "delete_safe", numhash_delete_safe, 1); } Index: test/-ext-/st/test_numhash.rb =================================================================== --- test/-ext-/st/test_numhash.rb (revision 34961) +++ test/-ext-/st/test_numhash.rb (revision 34962) @@ -23,5 +23,14 @@ assert_equal(:x, @tbl[0]) assert_equal(:x, @tbl[5]) end + + def test_size_after_delete_safe + 10.downto(1) do |up| + tbl = Bug::StNumHash.new + 1.upto(up){|i| tbl[i] = i} + assert_equal(1, tbl.delete_safe(1)) + assert_equal(up - 1, tbl.size, "delete_safe doesn't change size from #{up} to #{up-1}") + end + end end end -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/