[glib] hashtable: properly handle insert() de-set-ifying

[Matthias Clasen <matthiasc src gnome org>]

commit bb1df4d01b25e6e12ff30adcd3b07b37c4837bc0
Author: Ryan Lortie <desrt desrt ca>
Date:   Wed Jan 30 01:23:48 2013 +0100

    hashtable: properly handle insert() de-set-ifying
    
    GHashTable remains a set for as long as all of the keys are exactly
    equal (in pointer value) to all of the values.  We check this by
    comparing keys to values when we do inserts.
    
    Unfortunately, when doing g_hash_table_insert() when a key is already in
    the table, the old key pointer value is kept, but the new value pointer
    is used.  Now we have a situation where a key pointer is unequal to a
    value pointer, but we were not treating this case properly.
    
    Fix that.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=692815

 glib/ghash.c |   74 +++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 56 insertions(+), 18 deletions(-)
---
diff --git a/glib/ghash.c b/glib/ghash.c
index 587059e..492aa20 100644
--- a/glib/ghash.c
+++ b/glib/ghash.c
@@ -834,34 +834,72 @@ static void
 g_hash_table_insert_node (GHashTable *hash_table,
                           guint       node_index,
                           guint       key_hash,
-                          gpointer    key,
-                          gpointer    value,
+                          gpointer    new_key,
+                          gpointer    new_value,
                           gboolean    keep_new_key,
                           gboolean    reusing_key)
 {
+  gboolean already_exists;
   guint old_hash;
-  gpointer old_key;
-  gpointer old_value;
-
-  if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
-    hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
+  gpointer key_to_free;
+  gpointer value_to_free;
 
   old_hash = hash_table->hashes[node_index];
-  old_key = hash_table->keys[node_index];
-  old_value = hash_table->values[node_index];
-
-  if (HASH_IS_REAL (old_hash))
+  already_exists = HASH_IS_REAL (old_hash);
+
+  /* Proceed in three steps.  First, deal with the key because it is the
+   * most complicated.  Then consider if we need to split the table in
+   * two (because writing the value will result in the set invariant
+   * becoming broken).  Then deal with the value.
+   *
+   * There are three cases for the key:
+   *
+   *  - entry already exists in table, reusing key:
+   *    free the just-passed-in new_key and use the existing value
+   *
+   *  - entry already exists in table, not reusing key:
+   *    free the entry in the table, use the new key
+   *
+   *  - entry not already in table:
+   *    use the new key, free nothing
+   *
+   * We update the hash at the same time...
+   */
+  if (already_exists)
     {
+      /* Note: we must record the old value before writing the new key
+       * because we might change the value in the event that the two
+       * arrays are shared.
+       */
+      value_to_free = hash_table->values[node_index];
+
       if (keep_new_key)
-        hash_table->keys[node_index] = key;
-      hash_table->values[node_index] = value;
+        {
+          key_to_free = hash_table->keys[node_index];
+          hash_table->keys[node_index] = new_key;
+        }
+      else
+        key_to_free = new_key;
     }
   else
     {
-      hash_table->keys[node_index] = key;
-      hash_table->values[node_index] = value;
       hash_table->hashes[node_index] = key_hash;
+      hash_table->keys[node_index] = new_key;
+    }
 
+  /* Step two: check if the value that we are about to write to the
+   * table is the same as the key in the same position.  If it's not,
+   * split the table.
+   */
+  if (G_UNLIKELY (hash_table->keys == hash_table->values && hash_table->keys[node_index] != new_value))
+    hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
+
+  /* Step 3: Actually do the write */
+  hash_table->values[node_index] = new_value;
+
+  /* Now, the bookkeeping... */
+  if (!already_exists)
+    {
       hash_table->nnodes++;
 
       if (HASH_IS_UNUSED (old_hash))
@@ -876,12 +914,12 @@ g_hash_table_insert_node (GHashTable *hash_table,
 #endif
     }
 
-  if (HASH_IS_REAL (old_hash))
+  if (already_exists)
     {
       if (hash_table->key_destroy_func && !reusing_key)
-        hash_table->key_destroy_func (keep_new_key ? old_key : key);
+        (* hash_table->key_destroy_func) (key_to_free);
       if (hash_table->value_destroy_func)
-        hash_table->value_destroy_func (old_value);
+        (* hash_table->value_destroy_func) (value_to_free);
     }
 }