[16/17] check hash table counts at expand

[Alexandre Oliva <oliva@adacore.com>]

On Dec 28, 2022, Martin Liška <mliska@suse.cz> wrote:

> I really like the verification code you added. It's quite similar to what
> I added to hash-table.h:

*nod*

Prompted by your encouragement, I've combined the element count
verification code with the verify() loop, and also added it to expand,
where it can be done cheaply.


Add cheap verification of element and deleted entry counts during
expand and hash verify.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* hash-table.h (expand): Check elements and deleted counts.
	(verify): Likewise.
---
 gcc/hash-table.h |   35 ++++++++++++++++++++++++++++-------
 1 file changed, 28 insertions(+), 7 deletions(-)

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 53507daae26c3..f4bda6102323e 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -805,19 +805,28 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
     hash_table_usage ().release_instance_overhead (this, sizeof (value_type)
 						    * osize);
 
+  size_t n_deleted = m_n_deleted;
+
   m_entries = nentries;
   m_size = nsize;
   m_size_prime_index = nindex;
   m_n_elements -= m_n_deleted;
   m_n_deleted = 0;
 
+  size_t n_elements = m_n_elements;
+
   value_type *p = oentries;
   do
     {
       value_type &x = *p;
 
-      if (!is_empty (x) && !is_deleted (x))
+      if (is_empty (x))
+	;
+      else if (is_deleted (x))
+	n_deleted--;
+      else
         {
+	  n_elements--;
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
 	  new ((void*) q) value_type (std::move (x));
 	  /* After the resources of 'x' have been moved to a new object at 'q',
@@ -829,6 +838,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
     }
   while (p < olimit);
 
+  gcc_checking_assert (!n_elements && !n_deleted);
+
   if (!m_ggc)
     Allocator <value_type> ::data_free (oentries);
   else
@@ -1018,8 +1029,9 @@ hash_table<Descriptor, Lazy, Allocator>
   return &m_entries[index];
 }
 
-/* Verify that all existing elements in th hash table which are
-   equal to COMPARABLE have an equal HASH value provided as argument.  */
+/* Verify that all existing elements in the hash table which are
+   equal to COMPARABLE have an equal HASH value provided as argument.
+   Also check that the hash table element counts are correct.  */
 
 template<typename Descriptor, bool Lazy,
 	 template<typename Type> class Allocator>
@@ -1027,14 +1039,23 @@ void
 hash_table<Descriptor, Lazy, Allocator>
 ::verify (const compare_type &comparable, hashval_t hash)
 {
+  size_t n_elements = m_n_elements;
+  size_t n_deleted = m_n_deleted;
   for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
     {
       value_type *entry = &m_entries[i];
-      if (!is_empty (*entry) && !is_deleted (*entry)
-	  && hash != Descriptor::hash (*entry)
-	  && Descriptor::equal (*entry, comparable))
-	hashtab_chk_error ();
+      if (!is_empty (*entry))
+	{
+	  n_elements--;
+	  if (is_deleted (*entry))
+	    n_deleted--;
+	  else if (hash != Descriptor::hash (*entry)
+		   && Descriptor::equal (*entry, comparable))
+	    hashtab_chk_error ();
+	}
     }
+  if (hash_table_sanitize_eq_limit >= m_size)
+    gcc_checking_assert (!n_elements && !n_deleted);
 }
 
 /* This function deletes an element with the given COMPARABLE value


-- 
Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
   Free Software Activist                       GNU Toolchain Engineer
Disinformation flourishes because many people care deeply about injustice
but very few check the facts.  Ask me about <https://stallmansupport.org>