hash: check for resize before insertion

* lib/hash.c (hash_insert): Check whether bucket usage exceeds
threshold before insertion, so that a pathological hash_rehash
that fills every bucket can still trigger another rehash.

Signed-off-by: Eric Blake <ebb9@byu.net>

1 files changed, 29 insertions, 25 deletions

diff --git a/lib/hash.c b/lib/hash.c
index 5068202a3d..4de106960c 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -931,30 +931,6 @@ hash_insert (Hash_table *table, const void *entry)
   if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
     return data;
 
-  /* ENTRY is not matched, it should be inserted.  */
-
-  if (bucket->data)
-    {
-      struct hash_entry *new_entry = allocate_entry (table);
-
-      if (new_entry == NULL)
-	return NULL;
-
-      /* Add ENTRY in the overflow of the bucket.  */
-
-      new_entry->data = (void *) entry;
-      new_entry->next = bucket->next;
-      bucket->next = new_entry;
-      table->n_entries++;
-      return (void *) entry;
-    }
-
-  /* Add ENTRY right in the bucket head.  */
-
-  bucket->data = (void *) entry;
-  table->n_entries++;
-  table->n_buckets_used++;
-
   /* If the growth threshold of the buckets in use has been reached, increase
      the table size and rehash.  There's no point in checking the number of
      entries:  if the hashing function is ill-conditioned, rehashing is not
@@ -981,10 +957,38 @@ hash_insert (Hash_table *table, const void *entry)
 
 	  /* If the rehash fails, arrange to return NULL.  */
 	  if (!hash_rehash (table, candidate))
-	    entry = NULL;
+	    return NULL;
+
+	  /* Update the bucket we are interested in.  */
+	  if (hash_find_entry (table, entry, &bucket, false) != NULL)
+	    abort ();
 	}
     }
 
+  /* ENTRY is not matched, it should be inserted.  */
+
+  if (bucket->data)
+    {
+      struct hash_entry *new_entry = allocate_entry (table);
+
+      if (new_entry == NULL)
+	return NULL;
+
+      /* Add ENTRY in the overflow of the bucket.  */
+
+      new_entry->data = (void *) entry;
+      new_entry->next = bucket->next;
+      bucket->next = new_entry;
+      table->n_entries++;
+      return (void *) entry;
+    }
+
+  /* Add ENTRY right in the bucket head.  */
+
+  bucket->data = (void *) entry;
+  table->n_entries++;
+  table->n_buckets_used++;
+
   return (void *) entry;
 }