From 83c9c6fc1cc943f239a021b42a8ca9b0e162198c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 21 Feb 2017 15:31:29 -0800 Subject: [PATCH] Use float instead of Lisp_Object for rehash_size * src/alloc.c (purecopy_hash_table): * src/fns.c (maybe_resize_hash_table, Fmake_hash_table): (Fhash_table_rehash_size): * src/lisp.h (struct Lisp_Hash_Table.rehash_size): The rehash_size member of struct Lisp_Hash_Table is now a float, not a Lisp_Object. * src/alloc.c (purecopy_hash_table): Assign members in order. * src/fns.c (make_hash_table): Use EMACS_INT for size and float for rehash_size, instead of Lisp_Object for both. All callers changed. * src/lisp.h (DEFAULT_REHASH_SIZE): Now float, not double, and 1 smaller. * src/print.c (print_object): Simplify by calling Fhash_table_rehash_size and Fhash_table_rehash_threshold. Avoid unnecessary NILP. --- doc/lispref/hash.texi | 6 ++-- src/alloc.c | 6 ++-- src/category.c | 5 ++- src/emacs-module.c | 5 ++- src/fns.c | 95 ++++++++++++++++++++++++++++----------------------- src/image.c | 5 ++- src/lisp.h | 22 ++++++------ src/print.c | 10 +++--- src/profiler.c | 5 ++- src/xterm.c | 4 +-- 10 files changed, 84 insertions(+), 79 deletions(-) diff --git a/doc/lispref/hash.texi b/doc/lispref/hash.texi index 4ba3258d189..4d1582055fb 100644 --- a/doc/lispref/hash.texi +++ b/doc/lispref/hash.texi @@ -133,10 +133,10 @@ it grows automatically. This value specifies how to make the hash table larger, at that time. If @var{rehash-size} is an integer, it should be positive, and the hash -table grows by adding that much to the nominal size. If +table grows by adding approximately that much to the nominal size. If @var{rehash-size} is floating point, it had better be greater -than 1, and the hash table grows by multiplying the old size by that -number. +than 1, and the hash table grows by multiplying the old size by +approximately that number. The default value is 1.5. diff --git a/src/alloc.c b/src/alloc.c index 5da4290701e..b44b90e558a 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -5453,18 +5453,18 @@ purecopy_hash_table (struct Lisp_Hash_Table *table) pure_test.user_hash_function = purecopy (table->test.user_hash_function); pure_test.user_cmp_function = purecopy (table->test.user_cmp_function); - pure->test = pure_test; pure->header = table->header; pure->weak = purecopy (Qnil); - pure->rehash_size = purecopy (table->rehash_size); pure->hash = purecopy (table->hash); pure->next = purecopy (table->next); - pure->next_free = table->next_free; pure->index = purecopy (table->index); pure->count = table->count; + pure->next_free = table->next_free; pure->pure = table->pure; pure->rehash_threshold = table->rehash_threshold; + pure->rehash_size = table->rehash_size; pure->key_and_value = purecopy (table->key_and_value); + pure->test = pure_test; return pure; } diff --git a/src/category.c b/src/category.c index f5edd20c8a3..b633f65532a 100644 --- a/src/category.c +++ b/src/category.c @@ -64,9 +64,8 @@ hash_get_category_set (Lisp_Object table, Lisp_Object category_set) if (NILP (XCHAR_TABLE (table)->extras[1])) set_char_table_extras (table, 1, - make_hash_table (hashtest_equal, make_number (DEFAULT_HASH_SIZE), - make_float (DEFAULT_REHASH_SIZE), - DEFAULT_REHASH_THRESHOLD, + make_hash_table (hashtest_equal, DEFAULT_HASH_SIZE, + DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD, Qnil, false)); h = XHASH_TABLE (XCHAR_TABLE (table)->extras[1]); i = hash_lookup (h, category_set, &hash); diff --git a/src/emacs-module.c b/src/emacs-module.c index 5a66b516513..1b445dcc3b2 100644 --- a/src/emacs-module.c +++ b/src/emacs-module.c @@ -1013,9 +1013,8 @@ syms_of_module (void) doc: /* Module global reference table. */); Vmodule_refs_hash - = make_hash_table (hashtest_eq, make_number (DEFAULT_HASH_SIZE), - make_float (DEFAULT_REHASH_SIZE), - DEFAULT_REHASH_THRESHOLD, + = make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE, + DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD, Qnil, false); Funintern (Qmodule_refs_hash, Qnil); diff --git a/src/fns.c b/src/fns.c index 3769c4efb70..9668c885ab6 100644 --- a/src/fns.c +++ b/src/fns.c @@ -3684,13 +3684,13 @@ allocate_hash_table (void) `equal' or a symbol denoting a user-defined test named TEST with test and hash functions USER_TEST and USER_HASH. - Give the table initial capacity SIZE, SIZE >= 0, an integer. + Give the table initial capacity SIZE, 0 <= SIZE <= MOST_POSITIVE_FIXNUM. - If REHASH_SIZE is an integer, it must be > 0, and this hash table's - new size when it becomes full is computed by adding REHASH_SIZE to - its old size. If REHASH_SIZE is a float, it must be > 1.0, and the - table's new size is computed by multiplying its old size with - REHASH_SIZE. + If REHASH_SIZE is equal to a negative integer, this hash table's + new size when it becomes full is computed by subtracting + REHASH_SIZE from its old size. Otherwise it must be positive, and + the table's new size is computed by multiplying its old size by + REHASH_SIZE + 1. REHASH_THRESHOLD must be a float <= 1.0, and > 0. The table will be resized when the approximate ratio of table entries to table @@ -3704,34 +3704,31 @@ allocate_hash_table (void) changed after purecopy. */ Lisp_Object -make_hash_table (struct hash_table_test test, - Lisp_Object size, Lisp_Object rehash_size, - float rehash_threshold, Lisp_Object weak, - bool pure) +make_hash_table (struct hash_table_test test, EMACS_INT size, + float rehash_size, float rehash_threshold, + Lisp_Object weak, bool pure) { struct Lisp_Hash_Table *h; Lisp_Object table; - EMACS_INT index_size, sz; + EMACS_INT index_size; ptrdiff_t i; double index_float; /* Preconditions. */ eassert (SYMBOLP (test.name)); - eassert (INTEGERP (size) && XINT (size) >= 0); - eassert ((INTEGERP (rehash_size) && XINT (rehash_size) > 0) - || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size))); + eassert (0 <= size && size <= MOST_POSITIVE_FIXNUM); + eassert (rehash_size <= -1 || 0 < rehash_size); eassert (0 < rehash_threshold && rehash_threshold <= 1); - if (XFASTINT (size) == 0) - size = make_number (1); + if (size == 0) + size = 1; - sz = XFASTINT (size); double threshold = rehash_threshold; - index_float = sz / threshold; + index_float = size / threshold; index_size = (index_float < INDEX_SIZE_BOUND + 1 ? next_almost_prime (index_float) : INDEX_SIZE_BOUND + 1); - if (INDEX_SIZE_BOUND < max (index_size, 2 * sz)) + if (INDEX_SIZE_BOUND < max (index_size, 2 * size)) error ("Hash table too large"); /* Allocate a table and initialize it. */ @@ -3743,14 +3740,14 @@ make_hash_table (struct hash_table_test test, h->rehash_threshold = rehash_threshold; h->rehash_size = rehash_size; h->count = 0; - h->key_and_value = Fmake_vector (make_number (2 * sz), Qnil); - h->hash = Fmake_vector (size, Qnil); - h->next = Fmake_vector (size, make_number (-1)); + h->key_and_value = Fmake_vector (make_number (2 * size), Qnil); + h->hash = Fmake_vector (make_number (size), Qnil); + h->next = Fmake_vector (make_number (size), make_number (-1)); h->index = Fmake_vector (make_number (index_size), make_number (-1)); h->pure = pure; /* Set up the free list. */ - for (i = 0; i < sz - 1; ++i) + for (i = 0; i < size - 1; ++i) set_hash_next_slot (h, i, i + 1); h->next_free = 0; @@ -3810,22 +3807,21 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) ptrdiff_t old_size = HASH_TABLE_SIZE (h); EMACS_INT new_size, index_size, nsize; ptrdiff_t i; + double rehash_size = h->rehash_size; double index_float; - if (INTEGERP (h->rehash_size)) - new_size = old_size + XFASTINT (h->rehash_size); + if (rehash_size < 0) + new_size = old_size - rehash_size; else { - double float_new_size = old_size * XFLOAT_DATA (h->rehash_size); + double float_new_size = old_size * (rehash_size + 1); if (float_new_size < INDEX_SIZE_BOUND + 1) - { - new_size = float_new_size; - if (new_size <= old_size) - new_size = old_size + 1; - } + new_size = float_new_size; else new_size = INDEX_SIZE_BOUND + 1; } + if (new_size <= old_size) + new_size = old_size + 1; double threshold = h->rehash_threshold; index_float = new_size / threshold; index_size = (index_float < INDEX_SIZE_BOUND + 1 @@ -4408,7 +4404,7 @@ in an error. usage: (make-hash-table &rest KEYWORD-ARGS) */) (ptrdiff_t nargs, Lisp_Object *args) { - Lisp_Object test, size, rehash_size, weak; + Lisp_Object test, weak; bool pure; struct hash_table_test testdesc; ptrdiff_t i; @@ -4448,18 +4444,26 @@ usage: (make-hash-table &rest KEYWORD-ARGS) */) pure = i && !NILP (args[i]); /* See if there's a `:size SIZE' argument. */ i = get_key_arg (QCsize, nargs, args, used); - size = i ? args[i] : Qnil; - if (NILP (size)) - size = make_number (DEFAULT_HASH_SIZE); - else if (!INTEGERP (size) || XINT (size) < 0) - signal_error ("Invalid hash table size", size); + Lisp_Object size_arg = i ? args[i] : Qnil; + EMACS_INT size; + if (NILP (size_arg)) + size = DEFAULT_HASH_SIZE; + else if (NATNUMP (size_arg)) + size = XFASTINT (size_arg); + else + signal_error ("Invalid hash table size", size_arg); /* Look for `:rehash-size SIZE'. */ + float rehash_size; i = get_key_arg (QCrehash_size, nargs, args, used); - rehash_size = i ? args[i] : make_float (DEFAULT_REHASH_SIZE); - if (! ((INTEGERP (rehash_size) && 0 < XINT (rehash_size)) - || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size)))) - signal_error ("Invalid hash table rehash size", rehash_size); + if (!i) + rehash_size = DEFAULT_REHASH_SIZE; + else if (INTEGERP (args[i]) && 0 < XINT (args[i])) + rehash_size = - XINT (args[i]); + else if (FLOATP (args[i]) && 0 < (float) (XFLOAT_DATA (args[i]) - 1)) + rehash_size = (float) (XFLOAT_DATA (args[i]) - 1); + else + signal_error ("Invalid hash table rehash size", args[i]); /* Look for `:rehash-threshold THRESHOLD'. */ i = get_key_arg (QCrehash_threshold, nargs, args, used); @@ -4513,7 +4517,14 @@ DEFUN ("hash-table-rehash-size", Fhash_table_rehash_size, doc: /* Return the current rehash size of TABLE. */) (Lisp_Object table) { - return check_hash_table (table)->rehash_size; + double rehash_size = check_hash_table (table)->rehash_size; + if (rehash_size < 0) + { + EMACS_INT s = -rehash_size; + return make_number (min (s, MOST_POSITIVE_FIXNUM)); + } + else + return make_float (rehash_size + 1); } diff --git a/src/image.c b/src/image.c index 0a6bbd17d88..fc396c7353d 100644 --- a/src/image.c +++ b/src/image.c @@ -4017,9 +4017,8 @@ xpm_make_color_table_h (void (**put_func) (Lisp_Object, const char *, int, { *put_func = xpm_put_color_table_h; *get_func = xpm_get_color_table_h; - return make_hash_table (hashtest_equal, make_number (DEFAULT_HASH_SIZE), - make_float (DEFAULT_REHASH_SIZE), - DEFAULT_REHASH_THRESHOLD, + return make_hash_table (hashtest_equal, DEFAULT_HASH_SIZE, + DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD, Qnil, false); } diff --git a/src/lisp.h b/src/lisp.h index 027fd07d720..e048011a860 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -1969,11 +1969,6 @@ struct Lisp_Hash_Table weakness of the table. */ Lisp_Object weak; - /* When the table is resized, and this is an integer, compute the - new size by adding this to the old size. If a float, compute the - new size by multiplying the old size with this factor. */ - Lisp_Object rehash_size; - /* Vector of hash codes. If hash[I] is nil, this means that the I-th entry is unused. */ Lisp_Object hash; @@ -2008,6 +2003,13 @@ struct Lisp_Hash_Table ratio. */ float rehash_threshold; + /* Used when the table is resized. If equal to a negative integer, + the user rehash-size is the integer -REHASH_SIZE, and the new + size is the old size plus -REHASH_SIZE. If positive, the user + rehash-size is the floating-point value REHASH_SIZE + 1, and the + new size is the old size times REHASH_SIZE + 1. */ + float rehash_size; + /* Vector of keys and values. The key of item I is found at index 2 * I, the value is found at index 2 * I + 1. This is gc_marked specially if the table is weak. */ @@ -2076,9 +2078,9 @@ enum DEFAULT_HASH_SIZE { DEFAULT_HASH_SIZE = 65 }; static float const DEFAULT_REHASH_THRESHOLD = 0.8125; -/* Default factor by which to increase the size of a hash table. */ +/* Default factor by which to increase the size of a hash table, minus 1. */ -static double const DEFAULT_REHASH_SIZE = 1.5; +static float const DEFAULT_REHASH_SIZE = 1.5 - 1; /* Combine two integers X and Y for hashing. The result might not fit into a Lisp integer. */ @@ -3347,10 +3349,8 @@ extern Lisp_Object larger_vector (Lisp_Object, ptrdiff_t, ptrdiff_t); extern void sweep_weak_hash_tables (void); EMACS_UINT hash_string (char const *, ptrdiff_t); EMACS_UINT sxhash (Lisp_Object, int); -Lisp_Object make_hash_table (struct hash_table_test test, - Lisp_Object size, Lisp_Object rehash_size, - float rehash_threshold, Lisp_Object weak, - bool pure); +Lisp_Object make_hash_table (struct hash_table_test, EMACS_INT, float, float, + Lisp_Object, bool); ptrdiff_t hash_lookup (struct Lisp_Hash_Table *, Lisp_Object, EMACS_UINT *); ptrdiff_t hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object, EMACS_UINT); diff --git a/src/print.c b/src/print.c index 3a36a4eb54d..8c4bb24555e 100644 --- a/src/print.c +++ b/src/print.c @@ -1806,14 +1806,12 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag) print_object (h->weak, printcharfun, escapeflag); } - if (!NILP (h->rehash_size)) - { - print_c_string (" rehash-size ", printcharfun); - print_object (h->rehash_size, printcharfun, escapeflag); - } + print_c_string (" rehash-size ", printcharfun); + print_object (Fhash_table_rehash_size (obj), + printcharfun, escapeflag); print_c_string (" rehash-threshold ", printcharfun); - print_object (make_float (h->rehash_threshold), + print_object (Fhash_table_rehash_threshold (obj), printcharfun, escapeflag); if (h->pure) diff --git a/src/profiler.c b/src/profiler.c index 08ef6ee9623..6dc0d8ce72d 100644 --- a/src/profiler.c +++ b/src/profiler.c @@ -44,9 +44,8 @@ make_log (EMACS_INT heap_size, EMACS_INT max_stack_depth) a special way. This is OK as long as the object is not exposed to Elisp, i.e. until it is returned by *-profiler-log, after which it can't be used any more. */ - Lisp_Object log = make_hash_table (hashtest_profiler, - make_number (heap_size), - make_float (DEFAULT_REHASH_SIZE), + Lisp_Object log = make_hash_table (hashtest_profiler, heap_size, + DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD, Qnil, false); struct Lisp_Hash_Table *h = XHASH_TABLE (log); diff --git a/src/xterm.c b/src/xterm.c index b04c6999b39..52bc8f9eca2 100644 --- a/src/xterm.c +++ b/src/xterm.c @@ -12874,8 +12874,8 @@ keysyms. The default is nil, which is the same as `super'. */); DEFVAR_LISP ("x-keysym-table", Vx_keysym_table, doc: /* Hash table of character codes indexed by X keysym codes. */); - Vx_keysym_table = make_hash_table (hashtest_eql, make_number (900), - make_float (DEFAULT_REHASH_SIZE), + Vx_keysym_table = make_hash_table (hashtest_eql, 900, + DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD, Qnil, false); -- 2.11.4.GIT