Introduce table improvement by Vladimir Makarov <vmakarov@redhat.com>.

	[Feature #12142]
	See header of st.c for improvment details.

	You can see all of code history here:
	<https://github.com/vnmakarov/ruby/tree/hash_tables_with_open_addressing>

	This improvement is discussed at
	<https://bugs.ruby-lang.org/issues/12142>
	with many people, especially with Yura Sokolov.

	* st.c: improve st_table.

	* include/ruby/st.h: ditto.

	* internal.h, numeric.c, hash.c (rb_dbl_long_hash): extract a function.

	* ext/-test-/st/foreach/foreach.c: catch up this change.


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@56650 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 35 insertions, 30 deletions

diff --git a/include/ruby/st.h b/include/ruby/st.h
index de5aaaebec..ede75458c4 100644
--- a/include/ruby/st.h
+++ b/include/ruby/st.h
@@ -1,6 +1,8 @@
-/* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
+/* This is a public domain general purpose hash table package
+   originally written by Peter Moore @ UCB.
 
-/* @(#) st.h 5.1 89/12/14 */
+   The hash table data strutures were redesigned and the package was
+   rewritten by Vladimir Makarov <vmakarov@redhat.com>.  */
 
 #ifndef RUBY_ST_H
 #define RUBY_ST_H 1
@@ -46,6 +48,10 @@ typedef unsigned LONG_LONG st_data_t;
 typedef struct st_table st_table;
 
 typedef st_data_t st_index_t;
+
+/* Maximal value of unsigned integer type st_index_t.  */
+#define MAX_ST_INDEX_VAL (~(st_index_t) 0)
+
 typedef int st_compare_func(st_data_t, st_data_t);
 typedef st_index_t st_hash_func(st_data_t);
 
@@ -55,10 +61,13 @@ typedef char st_check_for_sizeof_st_index_t[SIZEOF_VOIDP == (int)sizeof(st_index
 struct st_hash_type {
     int (*compare)(ANYARGS /*st_data_t, st_data_t*/); /* st_compare_func* */
     st_index_t (*hash)(ANYARGS /*st_data_t*/);        /* st_hash_func* */
+    /* The following is an optional func for stronger hash.  When we
+       have many different keys with the same hash we can switch to
+       use it to prevent a denial attack with usage of hash table
+       collisions. */
+    st_index_t (*strong_hash)(ANYARGS /*st_data_t*/);
 };
 
-#define ST_INDEX_BITS (sizeof(st_index_t) * CHAR_BIT)
-
 #if defined(HAVE_BUILTIN___BUILTIN_CHOOSE_EXPR) && defined(HAVE_BUILTIN___BUILTIN_TYPES_COMPATIBLE_P)
 # define ST_DATA_COMPATIBLE_P(type) \
    __builtin_choose_expr(__builtin_types_compatible_p(type, st_data_t), 1, 0)
@@ -66,33 +75,30 @@ struct st_hash_type {
 # define ST_DATA_COMPATIBLE_P(type) 0
 #endif
 
+typedef struct st_table_entry st_table_entry;
+
+struct st_table_entry; /* defined in st.c */
+
 struct st_table {
+    /* Cached features of the table -- see st.c for more details.  */
+    unsigned char entry_power, bin_power, size_ind;
+    /* True when we are rebuilding the table.  */
+    unsigned char inside_rebuild_p;
+    /* How many times the table was rebuilt.  */
+    unsigned int rebuilds_num;
+    /* Currently used hash function.  */
+    st_index_t (*curr_hash)(ANYARGS /*st_data_t*/);
     const struct st_hash_type *type;
-    st_index_t num_bins;
-    unsigned int entries_packed : 1;
-#ifdef __GNUC__
-    /*
-     * C spec says,
-     *   A bit-field shall have a type that is a qualified or unqualified
-     *   version of _Bool, signed int, unsigned int, or some other
-     *   implementation-defined type. It is implementation-defined whether
-     *   atomic types are permitted.
-     * In short, long and long long bit-field are implementation-defined
-     * feature. Therefore we want to suppress a warning explicitly.
-     */
-    __extension__
-#endif
-    st_index_t num_entries : ST_INDEX_BITS - 1;
-    union {
-	struct {
-	    struct st_table_entry **bins;
-	    void *private_list_head[2];
-	} big;
-	struct {
-	    struct st_packed_entry *entries;
-	    st_index_t real_entries;
-	} packed;
-    } as;
+    /* Number of entries currently in the table.  */
+    st_index_t num_entries;
+    /* Array of bins used for access by keys.  */
+    st_index_t *bins;
+    /* Start and bound index of entries in array entries.
+       entries_starts and entries_bound are in interval
+       [0,allocated_entries].  */
+    st_index_t entries_start, entries_bound;
+    /* Array of size 2^entry_power.  */
+    st_table_entry *entries;
 };
 
 #define st_is_member(table,key) st_lookup((table),(key),(st_data_t *)0)
@@ -121,7 +127,6 @@ typedef int st_update_callback_func(st_data_t *key, st_data_t *value, st_data_t
 int st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg);
 int st_foreach(st_table *, int (*)(ANYARGS), st_data_t);
 int st_foreach_check(st_table *, int (*)(ANYARGS), st_data_t, st_data_t);
-int st_reverse_foreach(st_table *, int (*)(ANYARGS), st_data_t);
 st_index_t st_keys(st_table *table, st_data_t *keys, st_index_t size);
 st_index_t st_keys_check(st_table *table, st_data_t *keys, st_index_t size, st_data_t never);
 st_index_t st_values(st_table *table, st_data_t *values, st_index_t size);