+ return removed;
+}
+
+/* internal remove routine */
+static gboolean
+g_tree_remove_internal (GTree *tree,
+ gconstpointer key,
+ gboolean steal)
+{
+ GTreeNode *node, *parent, *balance;
+ GTreeNode *path[MAX_GTREE_HEIGHT];
+ int idx;
+ gboolean left_node;
+
+ g_return_val_if_fail (tree != NULL, FALSE);
+
+ if (!tree->root)
+ return FALSE;
+
+ idx = 0;
+ path[idx++] = NULL;
+ node = tree->root;
+
+ 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;
+ }
+ else
+ {
+ if (!node->right_child)
+ return FALSE;
+
+ path[idx++] = node;
+ node = node->right;
+ }
+ }
+
+ /* The following code is almost equal to g_tree_remove_node,
+ * except that we do not have to call g_tree_node_parent.
+ */
+ balance = parent = path[--idx];
+ g_assert (!parent || parent->left == node || parent->right == node);
+ left_node = (parent && node == parent->left);
+
+ if (!node->left_child)
+ {
+ if (!node->right_child)
+ {
+ if (!parent)
+ tree->root = NULL;
+ else if (left_node)
+ {
+ parent->left_child = FALSE;
+ parent->left = node->left;
+ parent->balance += 1;
+ }
+ else
+ {
+ parent->right_child = FALSE;
+ parent->right = node->right;
+ parent->balance -= 1;
+ }
+ }
+ else /* node has a right child */
+ {
+ GTreeNode *tmp = g_tree_node_next (node);
+ tmp->left = node->left;
+
+ if (!parent)
+ tree->root = node->right;
+ else if (left_node)
+ {
+ parent->left = node->right;
+ parent->balance += 1;
+ }
+ else
+ {
+ parent->right = node->right;
+ parent->balance -= 1;
+ }
+ }
+ }
+ else /* node has a left child */
+ {
+ if (!node->right_child)
+ {
+ GTreeNode *tmp = g_tree_node_previous (node);
+ tmp->right = node->right;
+
+ if (parent == NULL)
+ tree->root = node->left;
+ else if (left_node)
+ {
+ parent->left = node->left;
+ parent->balance += 1;
+ }
+ else
+ {
+ parent->right = node->left;
+ parent->balance -= 1;
+ }
+ }
+ else /* node has a both children (pant, pant!) */
+ {
+ GTreeNode *prev = node->left;
+ GTreeNode *next = node->right;
+ GTreeNode *nextp = node;
+ int old_idx = idx + 1;
+ idx++;
+
+ /* path[idx] == parent */
+ /* find the immediately next node (and its parent) */
+ while (next->left_child)
+ {
+ path[++idx] = nextp = next;
+ next = next->left;
+ }
+
+ path[old_idx] = next;
+ balance = path[idx];
+
+ /* remove 'next' from the tree */
+ if (nextp != node)
+ {
+ if (next->right_child)
+ nextp->left = next->right;
+ else
+ nextp->left_child = FALSE;
+ nextp->balance += 1;
+
+ next->right_child = TRUE;
+ next->right = node->right;
+ }
+ else
+ node->balance -= 1;
+
+ /* set the prev to point to the right place */
+ while (prev->right_child)
+ prev = prev->right;
+ prev->right = next;
+
+ /* prepare 'next' to replace 'node' */
+ next->left_child = TRUE;
+ next->left = node->left;
+ next->balance = node->balance;
+
+ if (!parent)
+ tree->root = next;
+ else if (left_node)
+ parent->left = next;
+ else
+ parent->right = next;
+ }
+ }
+
+ /* restore balance */
+ if (balance)
+ while (1)
+ {
+ GTreeNode *bparent = path[--idx];
+ g_assert (!bparent || bparent->left == balance || bparent->right == balance);
+ left_node = (bparent && balance == bparent->left);
+
+ if(balance->balance < -1 || balance->balance > 1)
+ {
+ balance = g_tree_node_balance (balance);
+ if (!bparent)
+ tree->root = balance;
+ else if (left_node)
+ bparent->left = balance;
+ else
+ bparent->right = balance;
+ }
+
+ if (balance->balance != 0 || !bparent)
+ break;
+
+ if (left_node)
+ bparent->balance += 1;
+ else
+ bparent->balance -= 1;
+
+ balance = bparent;
+ }
+
+ if (!steal)
+ {
+ if (tree->key_destroy_func)
+ tree->key_destroy_func (node->key);
+ if (tree->value_destroy_func)
+ tree->value_destroy_func (node->value);
+ }
+
+ g_slice_free (GTreeNode, node);
+
+ tree->nnodes--;
+
+ return TRUE;