diff --git a/glib/ghash.c b/glib/ghash.c
index 4cf6af4..b94a1c5 100644
--- a/glib/ghash.c
+++ b/glib/ghash.c
@@ -947,64 +947,56 @@ g_hash_table_lookup_extended (GHashTable    *hash_table,
   return TRUE;
 }
 
-/*
- * g_hash_table_insert_internal:
- * @hash_table: our #GHashTable
- * @key: the key to insert
- * @value: the value to insert
- * @keep_new_key: if %TRUE and this key already exists in the table
- *   then call the destroy notify function on the old key.  If %FALSE
- *   then call the destroy notify function on the new key.
- *
- * Implements the common logic for the g_hash_table_insert() and
- * g_hash_table_replace() functions.
- *
- * Do a lookup of @key.  If it is found, replace it with the new
- * @value (and perhaps the new @key).  If it is not found, create a
- * new node.
+/**
+ * g_hash_table_probe:
+ * @hash_table: a #GHashTable
+ * @key: the key to lookup or insert
+ * @found_key: (allow-none): return location for the key in the hash table,
+ *     or %NULL
+ * @found_value: (allow-none): return location for the value in the hash
+ *     table, or %NULL
+ *
+ * Looks up @key in @hash_table.
+ *
+ * If @key is present in @hash_table, @found_key and @found_value are
+ * set to point to the locations of the found key-value pair matching
+ * @key.
+ *
+ * If @key is not yet present in @hash_table, it is inserted with a
+ * value of %NULL and @found_key and @found_value are set to point
+ * to the locations for the newly inserted key-value pair.
+ *
+ * The returned @found_key and @found_value can be used to modify the
+ * in-table key-value pair, but care must be taken to preserve the
+ * hash value of the key.
+ *
+ * Returns: %TRUE if an existing item matching @key was found in @hash_table
+ *
+ * Since: 2.30
  */
-static void
-g_hash_table_insert_internal (GHashTable *hash_table,
-                              gpointer    key,
-                              gpointer    value,
-                              gboolean    keep_new_key)
+gboolean
+g_hash_table_probe (GHashTable  *hash_table,
+                    gpointer     key,
+                    gpointer   **found_key,
+                    gpointer   **found_value)
 {
   GHashNode *node;
   guint node_index;
   guint key_hash;
   guint old_hash;
 
-  g_return_if_fail (hash_table != NULL);
-  g_return_if_fail (hash_table->ref_count > 0);
+  g_return_val_if_fail (hash_table != NULL, FALSE);
+  g_return_val_if_fail (hash_table->ref_count > 0, FALSE);
 
   node_index = g_hash_table_lookup_node_for_insertion (hash_table, key, &key_hash);
   node = &hash_table->nodes [node_index];
 
   old_hash = node->key_hash;
 
-  if (old_hash > 1)
-    {
-      if (keep_new_key)
-        {
-          if (hash_table->key_destroy_func)
-            hash_table->key_destroy_func (node->key);
-          node->key = key;
-        }
-      else
-        {
-          if (hash_table->key_destroy_func)
-            hash_table->key_destroy_func (key);
-        }
-
-      if (hash_table->value_destroy_func)
-        hash_table->value_destroy_func (node->value);
-
-      node->value = value;
-    }
-  else
+  if (old_hash <= 1)
     {
       node->key = key;
-      node->value = value;
+      node->value = NULL;
       node->key_hash = key_hash;
 
       hash_table->nnodes++;
@@ -1020,6 +1012,14 @@ g_hash_table_insert_internal (GHashTable *hash_table,
       hash_table->version++;
 #endif
     }
+
+  if (found_key)
+    *found_key = &node->key;
+
+  if (found_value)
+    *found_value = &node->value;
+
+  return old_hash > 1;
 }
 
 /**
@@ -1041,7 +1041,19 @@ g_hash_table_insert (GHashTable *hash_table,
                      gpointer    key,
                      gpointer    value)
 {
-  g_hash_table_insert_internal (hash_table, key, value, FALSE);
+  gpointer *found_key;
+  gpointer *found_value;
+
+  if (g_hash_table_probe (hash_table, key, &found_key, &found_value))
+    {
+      if (hash_table->key_destroy_func)
+        hash_table->key_destroy_func (key);
+
+      if (hash_table->value_destroy_func)
+        hash_table->value_destroy_func (*found_value);
+    }
+
+  *found_value = value;
 }
 
 /**
@@ -1051,18 +1063,35 @@ g_hash_table_insert (GHashTable *hash_table,
  * @value: the value to associate with the key.
  *
  * Inserts a new key and value into a #GHashTable similar to
- * g_hash_table_insert(). The difference is that if the key already exists
- * in the #GHashTable, it gets replaced by the new key. If you supplied a
- * @value_destroy_func when creating the #GHashTable, the old value is freed
- * using that function. If you supplied a @key_destroy_func when creating the
- * #GHashTable, the old key is freed using that function.
+ * g_hash_table_insert().
+ *
+ * The difference is that if the key already exists in the
+ * #GHashTable, it gets replaced by the new key. If you supplied
+ * a @value_destroy_func when creating the #GHashTable, the old
+ * value is freed using that function. If you supplied a
+ * @key_destroy_func when creating the #GHashTable, the old key
+ * is freed using that function.
  **/
 void
 g_hash_table_replace (GHashTable *hash_table,
                       gpointer    key,
                       gpointer    value)
 {
-  g_hash_table_insert_internal (hash_table, key, value, TRUE);
+  gpointer *found_key;
+  gpointer *found_value;
+
+  if (g_hash_table_probe (hash_table, key, &found_key, &found_value))
+    {
+      if (hash_table->key_destroy_func)
+        hash_table->key_destroy_func (*found_key);
+
+      *found_key = key;
+
+      if (hash_table->value_destroy_func)
+        hash_table->value_destroy_func (*found_value);
+    }
+
+  *found_value = value;
 }
 
 /*
diff --git a/glib/ghash.h b/glib/ghash.h
index 9128721..b9369e3 100644
--- a/glib/ghash.h
+++ b/glib/ghash.h
@@ -70,6 +70,10 @@ void	    g_hash_table_insert		   (GHashTable	   *hash_table,
 void        g_hash_table_replace           (GHashTable     *hash_table,
 					    gpointer	    key,
 					    gpointer	    value);
+gboolean    g_hash_table_probe             (GHashTable     *hash_table,
+                                            gpointer        key,
+                                            gpointer      **found_key,
+                                            gpointer      **found_value);
 gboolean    g_hash_table_remove		   (GHashTable	   *hash_table,
 					    gconstpointer   key);
 void        g_hash_table_remove_all        (GHashTable     *hash_table);
diff --git a/glib/gtree.c b/glib/gtree.c
index 4aa5e5c..49133c1 100644
--- a/glib/gtree.c
+++ b/glib/gtree.c
@@ -95,17 +95,13 @@ struct _GTreeNode
   GTreeNode *left;        /* left subtree */
   GTreeNode *right;       /* right subtree */
   gint8      balance;     /* height (left) - height (right) */
-  guint8     left_child;  
+  guint8     left_child;
   guint8     right_child;
 };
 
 
 static GTreeNode* g_tree_node_new                   (gpointer       key,
 						     gpointer       value);
-static void       g_tree_insert_internal            (GTree         *tree,
-						     gpointer       key,
-						     gpointer       value,
-						     gboolean       replace);
 static gboolean   g_tree_remove_internal            (GTree         *tree,
 						     gconstpointer  key,
 						     gboolean       steal);
@@ -370,24 +366,38 @@ g_tree_destroy (GTree *tree)
  * @tree: a #GTree.
  * @key: the key to insert.
  * @value: the value corresponding to the key.
- * 
- * Inserts a key/value pair into a #GTree. If the given key already exists 
- * in the #GTree its corresponding value is set to the new value. If you 
- * supplied a value_destroy_func when creating the #GTree, the old value is 
- * freed using that function. If you supplied a @key_destroy_func when 
- * creating the #GTree, the passed key is freed using that function.
+ *
+ * Inserts a key/value pair into a #GTree.
+ *
+ * If the given key already exists in the #GTree its corresponding
+ * value is set to the new value. If you supplied a value_destroy_func
+ * when creating the #GTree, the old value is freed using that function.
+ * If you supplied a @key_destroy_func when creating the #GTree, the
+ * passed key is freed using that function.
  *
  * The tree is automatically 'balanced' as new key/value pairs are added,
  * so that the distance from the root to every leaf is as small as possible.
- **/
+ */
 void
 g_tree_insert (GTree    *tree,
-	       gpointer  key,
-	       gpointer  value)
+               gpointer  key,
+               gpointer  value)
 {
+  gpointer *found_key;
+  gpointer *found_value;
+
   g_return_if_fail (tree != NULL);
 
-  g_tree_insert_internal (tree, key, value, FALSE);
+  if (g_tree_probe (tree, key, &found_key, &found_value))
+    {
+      if (tree->key_destroy_func)
+        tree->key_destroy_func (key);
+
+      if (tree->value_destroy_func)
+        tree->value_destroy_func (*found_value);
+    }
+
+  *found_value = value;
 
 #ifdef G_TREE_DEBUG
   g_tree_node_check (tree->root);
@@ -399,49 +409,100 @@ g_tree_insert (GTree    *tree,
  * @tree: a #GTree.
  * @key: the key to insert.
  * @value: the value corresponding to the key.
- * 
- * Inserts a new key and value into a #GTree similar to g_tree_insert(). 
- * The difference is that if the key already exists in the #GTree, it gets 
- * replaced by the new key. If you supplied a @value_destroy_func when 
- * creating the #GTree, the old value is freed using that function. If you 
- * supplied a @key_destroy_func when creating the #GTree, the old key is 
- * freed using that function. 
+ *
+ * Inserts a new key and value into a #GTree,
+ * similar to g_tree_insert().
+ *
+ * The difference is that if the key already exists in the #GTree,
+ * it gets replaced by the new key. If you supplied a @value_destroy_func
+ * when creating the #GTree, the old value is freed using that function.
+ * If you supplied a @key_destroy_func when creating the #GTree, the old
+ * key is freed using that function.
  *
  * The tree is automatically 'balanced' as new key/value pairs are added,
  * so that the distance from the root to every leaf is as small as possible.
- **/
+ */
 void
 g_tree_replace (GTree    *tree,
-		gpointer  key,
-		gpointer  value)
+                gpointer  key,
+                gpointer  value)
 {
+  gpointer *found_key;
+  gpointer *found_value;
   g_return_if_fail (tree != NULL);
 
-  g_tree_insert_internal (tree, key, value, TRUE);
+  if (g_tree_probe (tree, key, &found_key, &found_value))
+    {
+      if (tree->key_destroy_func)
+        tree->key_destroy_func (*found_key);
+
+      if (tree->value_destroy_func)
+        tree->value_destroy_func (*found_value);
+
+      *found_key = key;
+    }
+
+  *found_value = value;
 
 #ifdef G_TREE_DEBUG
   g_tree_node_check (tree->root);
 #endif
 }
 
-/* internal insert routine */
-static void
-g_tree_insert_internal (GTree    *tree,
-                        gpointer  key,
-                        gpointer  value,
-                        gboolean  replace)
+/**
+ * g_tree_probe:
+ * @tree: a #GTree
+ * @key: the key to insert or find
+ * @found_key: (allow-none): return location for the key in the tree,
+ *     or %NULL
+ * @found_value: (allow-none): return location for the value in the tree,
+ *     or %NULL
+ *
+ * Looks up @key in @tree.
+ *
+ * If @key is present in @tree, @found_key and @found_value are
+ * set to point to the locations of the found key-value pair
+ * matching @key.
+ *
+ * If @key is not yet present in @tree, it is inserted with a value
+ * of %NULL and @found_key and @found_value are set to point to the
+ * locations for the newly inserted key-value pair.
+ *
+ * The returned @found_key and @found_value can be used to modify the
+ * in-tree key-value pair, but care must be taken to preserve the
+ * ordering of the key wrt. to other items that are present in the
+ * tree.
+ *
+ * Returns: %TRUE if and existing item matching @key was found in @tree
+ *
+ * Since: 2.30
+ */
+gboolean
+g_tree_probe (GTree     *tree,
+              gpointer   key,
+              gpointer **found_key,
+              gpointer **found_value)
 {
   GTreeNode *node;
   GTreeNode *path[MAX_GTREE_HEIGHT];
   int idx;
 
-  g_return_if_fail (tree != NULL);
+  g_return_val_if_fail (tree != NULL, FALSE);
 
   if (!tree->root)
     {
-      tree->root = g_tree_node_new (key, value);
+      node = g_tree_node_new (key, NULL);
+
+      if (found_key)
+        *found_key = &node->key;
+
+      if (found_value)
+        *found_value = &node->value;
+
+      tree->root = node;
       tree->nnodes++;
-      return;
+
+      return FALSE;
     }
 
   idx = 0;
@@ -451,29 +512,16 @@ g_tree_insert_internal (GTree    *tree,
   while (1)
     {
       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
-      
+
       if (cmp == 0)
         {
-          if (tree->value_destroy_func)
-            tree->value_destroy_func (node->value);
-
-          node->value = value;
+          if (found_key)
+            *found_key = &node->key;
 
-          if (replace)
-            {
-              if (tree->key_destroy_func)
-                tree->key_destroy_func (node->key);
-
-              node->key = key;
-            }
-          else
-            {
-              /* free the passed key */
-              if (tree->key_destroy_func)
-                tree->key_destroy_func (key);
-            }
+          if (found_value)
+            *found_value = &node->value;
 
-          return;
+          return TRUE;
         }
       else if (cmp < 0)
         {
@@ -484,7 +532,13 @@ g_tree_insert_internal (GTree    *tree,
             }
           else
             {
-              GTreeNode *child = g_tree_node_new (key, value);
+              GTreeNode *child = g_tree_node_new (key, NULL);
+
+              if (found_key)
+                *found_key = &child->key;
+
+              if (found_value)
+                *found_value = &child->value;
 
               child->left = node->left;
               child->right = node;
@@ -492,7 +546,7 @@ g_tree_insert_internal (GTree    *tree,
               node->left_child = TRUE;
               node->balance -= 1;
 
-	      tree->nnodes++;
+              tree->nnodes++;
 
               break;
             }
@@ -506,7 +560,13 @@ g_tree_insert_internal (GTree    *tree,
             }
           else
             {
-              GTreeNode *child = g_tree_node_new (key, value);
+              GTreeNode *child = g_tree_node_new (key, NULL);
+
+              if (found_key)
+                *found_key = &child->key;
+
+              if (found_value)
+                *found_value = &child->value;
 
               child->right = node->right;
               child->left = node;
@@ -514,7 +574,7 @@ g_tree_insert_internal (GTree    *tree,
               node->right_child = TRUE;
               node->balance += 1;
 
-	      tree->nnodes++;
+              tree->nnodes++;
 
               break;
             }
@@ -543,7 +603,7 @@ g_tree_insert_internal (GTree    *tree,
 
       if (node->balance == 0 || bparent == NULL)
         break;
-      
+
       if (left_node)
         bparent->balance -= 1;
       else
@@ -551,6 +611,8 @@ g_tree_insert_internal (GTree    *tree,
 
       node = bparent;
     }
+
+  return FALSE;
 }
 
 /**
@@ -638,14 +700,14 @@ g_tree_remove_internal (GTree         *tree,
   while (1)
     {
       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
-      
+
       if (cmp == 0)
         break;
       else if (cmp < 0)
         {
           if (!node->left_child)
             return FALSE;
-	  
+
 	  path[idx++] = node;
 	  node = node->left;
         }
diff --git a/glib/gtree.h b/glib/gtree.h
index db06ba3..05db846 100644
--- a/glib/gtree.h
+++ b/glib/gtree.h
@@ -56,6 +56,10 @@ void     g_tree_destroy         (GTree            *tree);
 void     g_tree_insert          (GTree            *tree,
                                  gpointer          key,
                                  gpointer          value);
+gboolean g_tree_probe           (GTree            *tree,
+                                 gpointer          key,
+                                 gpointer        **found_key,
+                                 gpointer        **found_value);
 void     g_tree_replace         (GTree            *tree,
                                  gpointer          key,
                                  gpointer          value);
