+ 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;