From e49a472aad43e92e7b71ed38d6c7c091645a90f6 Mon Sep 17 00:00:00 2001 From: ko1 Date: Mon, 7 Nov 2016 00:45:00 +0000 Subject: Introduce table improvement by Vladimir Makarov . [Feature #12142] See header of st.c for improvment details. You can see all of code history here: This improvement is discussed at 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 --- include/ruby/st.h | 65 ++++++++++++++++++++++++++++++------------------------- 1 file changed, 35 insertions(+), 30 deletions(-) (limited to 'include/ruby/st.h') 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 . */ #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); -- cgit v1.2.3