return new;
}
+/*
+ * _quadtree_reposition_reqursively - Move everything under and
+ * including a given node under the new root node
+ */
+
+static void
+_quadtree_reposition_reqursively(struct quadtree *root,
+ struct quadtree *node,
+ int (*compare)(struct quadtree *a,
+ struct quadtree *b))
+{
+ int i;
+
+ /* First remove all children, if any */
+ for (i = 0; i < 4; i++) {
+ if (!node->child[i])
+ continue;
+
+ _quadtree_reposition_reqursively(root, node->child[i], compare);
+ node->child[i] = 0;
+ }
+
+ /* Then remove this node under the new root. */
+ quadtree_add(root, node, compare);
+}
+
+/*
+ * quadtree_del - Detach a node from the tree
+ *
+ * Return value: The new root node of the tree. If we are detaching
+ * anything but the root node of the entire tree, the returned root
+ * value will be the original root of the tree.
+ */
+struct quadtree *quadtree_del(struct quadtree *node,
+ int (*compare)(struct quadtree *a,
+ struct quadtree *b))
+{
+ struct quadtree *parent = 0;
+ int i;
+
+ /*
+ * We are deleting the root node. This means we have to select
+ * a new root node and reconstruct the entire tree under it
+ * again.
+ */
+ if (!node->parent) {
+ for (i = 0; i < 4; i++) {
+ if (!node->child[i])
+ continue;
+
+ if (!parent) {
+ parent = node->child[i];
+ continue;
+ }
+ _quadtree_reposition_reqursively(parent,
+ node->child[i],
+ compare);
+ node->child[i] = 0;
+ }
+
+ return parent;
+ }
+
+ /*
+ * We are not deleting the parent. Just relocate the children
+ * and detach the node from the tree.
+ */
+ for (i = 0; i < 4; i++) {
+ if (!node->child[i])
+ continue;
+
+ _quadtree_reposition_reqursively(node->parent, node->child[i],
+ compare);
+ }
+
+ parent = quadtree_find_parent(node);
+ node->parent = 0;
+
+ return parent;
+}
+
+
static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
{
int direction, count = 0;