* 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

1 files changed, 63 insertions, 38 deletions

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;
 	    }