[PATCH] [google] [annotalysis] Fix remove operation from pointer_set in case of hash collisions

[Delesley Hutchins]

This patch fixes a bug in pointer_set.c, where removing a pointer from
a pointer set would corrupt the hash table if the pointer was involved
in any hash collisions.

Bootstrapped and passed gcc regression testsuite on x86_64-unknown-linux-gnu.

Okay for google/gcc-4_6?

  -DeLesley

gcc/Changelog.annotalysis:
2011-7-26  DeLesley Hutchins  <deles...@google.com>

        * gcc/pointer-set.c (pointer_set_delete)  bugfix for case of
hash collisions


Index: gcc/pointer-set.c
===================================================================
--- gcc/pointer-set.c   (revision 176809)
+++ gcc/pointer-set.c   (working copy)
@@ -192,19 +192,16 @@ int
 pointer_set_delete (struct pointer_set_t *pset, const void *p)
 {
   size_t n = hash1 (p, pset->n_slots, pset->log_slots);
+  size_t n2;
+  const void* ptr;

+  /* find location of p */
   while (true)
     {
       if (pset->slots[n] == p)
-        {
-          pset->slots[n] = 0;
-          --pset->n_elements;
-          return 1;
-        }
+        break;
       else if (pset->slots[n] == 0)
-        {
-          return 0;
-        }
+        return 0;
       else
         {
           ++n;
@@ -212,6 +209,29 @@ pointer_set_delete (struct pointer_set_t *pset, co
             n = 0;
         }
     }
+
+  /* Remove p from set. */
+  pset->slots[n] = 0;
+
+  /* Now we need to scan foward and re-hash every value that we encounter,
+     until we find an empty slot.
+   */
+  while (true)
+    {
+      ++n;
+      if (n >= pset->n_slots)
+        n = 0;
+      ptr = pset->slots[n];
+
+      if (ptr == 0) break;
+
+      pset->slots[n] = 0;      /* remove ptr from set. */
+      n2 = insert_aux(ptr, pset->slots, pset->n_slots, pset->log_slots);
+      pset->slots[n2] = ptr;   /* put ptr back in set. */
+    }
+
+  --pset->n_elements;
+  return 1;
 }

 /* Pass each pointer in PSET to the function in FN, together with the fixed


-- 
DeLesley Hutchins | Software Engineer | deles...@google.com | 505-206-0315