From 11e467eb6004286765c1d8c408f8d773d9113aca Mon Sep 17 00:00:00 2001 From: =?utf8?q?Mattias=20Engdeg=C3=A5rd?= Date: Tue, 21 Nov 2023 22:12:08 +0100 Subject: [PATCH] Use key Qunbound instead of hash value hash_unused for free entries Previously, free hash table entries were indicated by both hash value hash_unused and key Qunbound; we now rely on the latter only. This allows us to change the hash representation to one that does not have an unused value. * src/lisp.h (hash_unused): Remove. All uses adapted to calling hash_unused_entry_key_p on the key instead. The hash values for unused hash table entries are now undefined; all initialisation and assignment to hash_unused has been removed. --- src/fns.c | 14 ++------------ src/lisp.h | 7 +------ src/macfont.m | 2 +- src/pdumper.c | 13 ++++++++----- 4 files changed, 12 insertions(+), 24 deletions(-) diff --git a/src/fns.c b/src/fns.c index b68fb393703..ed7b7bb2024 100644 --- a/src/fns.c +++ b/src/fns.c @@ -4577,8 +4577,6 @@ make_hash_table (const struct hash_table_test *test, EMACS_INT size, h->key_and_value[i] = HASH_UNUSED_ENTRY_KEY; h->hash = hash_table_alloc_bytes (size * sizeof *h->hash); - for (ptrdiff_t i = 0; i < size; i++) - h->hash[i] = hash_unused; h->next = hash_table_alloc_bytes (size * sizeof *h->next); for (ptrdiff_t i = 0; i < size - 1; i++) @@ -4682,8 +4680,6 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) hash_hash_t *hash = hash_table_alloc_bytes (new_size * sizeof *hash); memcpy (hash, h->hash, old_size * sizeof *hash); - for (ptrdiff_t i = old_size; i < new_size; i++) - hash[i] = hash_unused; ptrdiff_t old_index_size = h->index_size; ptrdiff_t index_size = hash_index_size (new_size); @@ -4755,8 +4751,6 @@ hash_table_thaw (Lisp_Object hash_table) h->next_free = -1; h->hash = hash_table_alloc_bytes (size * sizeof *h->hash); - for (ptrdiff_t i = 0; i < size; i++) - h->hash[i] = hash_unused; h->next = hash_table_alloc_bytes (size * sizeof *h->next); for (ptrdiff_t i = 0; i < size; i++) @@ -4831,14 +4825,13 @@ ptrdiff_t hash_put (struct Lisp_Hash_Table *h, Lisp_Object key, Lisp_Object value, hash_hash_t hash) { - eassert (!BASE_EQ (key, Qunbound)); + eassert (!hash_unused_entry_key_p (key)); /* Increment count after resizing because resizing may fail. */ maybe_resize_hash_table (h); h->count++; /* Store key/value in the key_and_value vector. */ ptrdiff_t i = h->next_free; - eassert (HASH_HASH (h, i) == hash_unused); eassert (hash_unused_entry_key_p (HASH_KEY (h, i))); h->next_free = HASH_NEXT (h, i); set_hash_key_slot (h, i, key); @@ -4883,7 +4876,6 @@ hash_remove_from_table (struct Lisp_Hash_Table *h, Lisp_Object key) the free list. */ set_hash_key_slot (h, i, HASH_UNUSED_ENTRY_KEY); set_hash_value_slot (h, i, Qnil); - set_hash_hash_slot (h, i, hash_unused); set_hash_next_slot (h, i, h->next_free); h->next_free = i; h->count--; @@ -4906,7 +4898,6 @@ hash_clear (struct Lisp_Hash_Table *h) ptrdiff_t size = HASH_TABLE_SIZE (h); for (ptrdiff_t i = 0; i < size; i++) { - set_hash_hash_slot (h, i, hash_unused); set_hash_next_slot (h, i, i < size - 1 ? i + 1 : -1); set_hash_key_slot (h, i, HASH_UNUSED_ENTRY_KEY); set_hash_value_slot (h, i, Qnil); @@ -4986,10 +4977,9 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool remove_entries_p) set_hash_next_slot (h, i, h->next_free); h->next_free = i; - /* Clear key, value, and hash. */ + /* Clear key and value. */ set_hash_key_slot (h, i, HASH_UNUSED_ENTRY_KEY); set_hash_value_slot (h, i, Qnil); - set_hash_hash_slot (h, i, hash_unused); eassert (h->count != 0); h->count--; diff --git a/src/lisp.h b/src/lisp.h index f27f506b58f..0701028c14c 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -2425,11 +2425,6 @@ typedef enum { both key and value remain. */ } hash_table_weakness_t; -/* An value that marks an unused hash entry. - Any hash_hash_t value that is not a valid fixnum will do here. */ -enum { hash_unused = (hash_hash_t)MOST_POSITIVE_FIXNUM + 1 }; -verify (FIXNUM_OVERFLOW_P (hash_unused)); - /* The type of a hash table index, both for table indices and index (hash) indices. It's signed and a subtype of ptrdiff_t. */ typedef int32_t hash_idx_t; @@ -2475,7 +2470,7 @@ struct Lisp_Hash_Table Otherwise it is heap-allocated. */ hash_idx_t *index; - /* Vector of hash codes. The value hash_unused marks an unused table entry. + /* Vector of hash codes. Unused entries have undefined values. This vector is table_size entries long. */ hash_hash_t *hash; diff --git a/src/macfont.m b/src/macfont.m index 48502c2ec00..6f192b00f1b 100644 --- a/src/macfont.m +++ b/src/macfont.m @@ -980,7 +980,7 @@ macfont_invalidate_family_cache (void) ptrdiff_t i, size = HASH_TABLE_SIZE (h); for (i = 0; i < size; ++i) - if (HASH_HASH (h, i) != hash_unused) + if (!hash_unused_entry_key_p (HASH_KEY (h, i))) { Lisp_Object value = HASH_VALUE (h, i); diff --git a/src/pdumper.c b/src/pdumper.c index 38682816f0a..54f0f2bca13 100644 --- a/src/pdumper.c +++ b/src/pdumper.c @@ -2676,11 +2676,14 @@ hash_table_contents (struct Lisp_Hash_Table *h) relies on it by expecting hash table indices to stay constant across the dump. */ for (ptrdiff_t i = 0; i < old_size; i++) - if (HASH_HASH (h, i) != hash_unused) - { - key_and_value[n++] = HASH_KEY (h, i); - key_and_value[n++] = HASH_VALUE (h, i); - } + { + Lisp_Object key = HASH_KEY (h, i); + if (!hash_unused_entry_key_p (key)) + { + key_and_value[n++] = key; + key_and_value[n++] = HASH_VALUE (h, i); + } + } return key_and_value; } -- 2.39.2