From f54e3b3ba01ced7ecda3caed51b42f707d489c77 Mon Sep 17 00:00:00 2001
From: Alexandre Oliva <oliva@adacore.com>
Date: Thu, 12 Jan 2023 00:29:33 -0300
Subject: [PATCH] check hash table counts at expand

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


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 a505b1e..1d31665 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -849,19 +849,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',
@@ -873,6 +882,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
@@ -1070,8 +1081,9 @@ hash_table<Descriptor, Lazy, Allocator>
   return check_insert_slot (&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>
@@ -1079,14 +1091,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
-- 
2.7.4