public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Alexandre Oliva <aoliva@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-5162] hash table: enforce testing is_empty before is_deleted Date: Sat, 14 Jan 2023 00:16:51 +0000 (GMT) [thread overview] Message-ID: <20230114001651.3E7CB38654B0@sourceware.org> (raw) https://gcc.gnu.org/g:88679960c2665d87c8354ce35a48aaadbe3f0793 commit r13-5162-g88679960c2665d87c8354ce35a48aaadbe3f0793 Author: Alexandre Oliva <oliva@adacore.com> Date: Fri Jan 13 21:15:44 2023 -0300 hash table: enforce testing is_empty before is_deleted Existing hash_table traits that use the same representation for empty and deleted slots reject marking slots as deleted, and to not pass is_deleted for slots that pass is_empty. Nevertheless, nearly everywhere, we only test for is_deleted after checking that !is_empty first. The one exception was the copy constructor, that would fail if traits recognized is_empty slots as is_deleted, but then refused to mark_deleted. This asymmetry is neither necessary nor desirable, and there is a theoretical risk that traits might not only fail to refuse to mark_deleted, but also return is_deleted for is_empty slots. This patch introduces checks that detect these potentially problematic situations, and reorders the tests in the copy constructor so as to use the conventional testing order and thus avoid them. for gcc/ChangeLog * hash-table.h (is_deleted): Precheck !is_empty. (mark_deleted): Postcheck !is_empty. (copy constructor): Test is_empty before is_deleted. Diff: --- gcc/hash-table.h | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 1d3166504c3..e37625dc315 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -534,6 +534,11 @@ private: void expand (); static bool is_deleted (value_type &v) { + /* Traits are supposed to avoid recognizing elements as both empty + and deleted, but to fail safe in case custom traits fail to do + that, make sure we never test for is_deleted without having + first ruled out is_empty. */ + gcc_checking_assert (!Descriptor::is_empty (v)); return Descriptor::is_deleted (v); } @@ -545,6 +550,11 @@ private: static void mark_deleted (value_type &v) { Descriptor::mark_deleted (v); + /* Traits are supposed to refuse to set elements as deleted if + those would be indistinguishable from empty, but to fail safe + in case custom traits fail to do that, check that the + just-deleted element does not look empty. */ + gcc_checking_assert (!Descriptor::is_empty (v)); } static void mark_empty (value_type &v) @@ -700,9 +710,11 @@ hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h, for (size_t i = 0; i < size; ++i) { value_type &entry = h.m_entries[i]; - if (is_deleted (entry)) + if (is_empty (entry)) + continue; + else if (is_deleted (entry)) mark_deleted (nentries[i]); - else if (!is_empty (entry)) + else new ((void*) (nentries + i)) value_type (entry); } m_entries = nentries;
reply other threads:[~2023-01-14 0:16 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20230114001651.3E7CB38654B0@sourceware.org \ --to=aoliva@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).