rbtree.c: Delete augmented rbtree functions
authorEric Biggers <ebiggers3@gmail.com>
Sun, 11 Nov 2012 23:57:48 +0000 (17:57 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Sun, 11 Nov 2012 23:57:48 +0000 (17:57 -0600)
src/rbtree.c

index 978844084dca8b22197b58f6c6d667a893a7318e..90e467d739af9baa862cad5c58ee2d7827f858e6 100644 (file)
@@ -380,118 +380,3 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 {
        rb_erase_augmented(node, root, &dummy_callbacks);
 }
-
-/*
- * Augmented rbtree manipulation functions.
- *
- * This instantiates the same ALWAYS_INLINE functions as in the non-augmented
- * case, but this time with user-defined callbacks.
- */
-
-void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
-       void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
-{
-       __rb_insert(node, root, augment_rotate);
-}
-
-/*
- * This function returns the first node (in sort order) of the tree.
- */
-struct rb_node *rb_first(const struct rb_root *root)
-{
-       struct rb_node  *n;
-
-       n = root->rb_node;
-       if (!n)
-               return NULL;
-       while (n->rb_left)
-               n = n->rb_left;
-       return n;
-}
-
-struct rb_node *rb_last(const struct rb_root *root)
-{
-       struct rb_node  *n;
-
-       n = root->rb_node;
-       if (!n)
-               return NULL;
-       while (n->rb_right)
-               n = n->rb_right;
-       return n;
-}
-
-struct rb_node *rb_next(const struct rb_node *node)
-{
-       struct rb_node *parent;
-
-       if (RB_EMPTY_NODE(node))
-               return NULL;
-
-       /*
-        * If we have a right-hand child, go down and then left as far
-        * as we can.
-        */
-       if (node->rb_right) {
-               node = node->rb_right;
-               while (node->rb_left)
-                       node=node->rb_left;
-               return (struct rb_node *)node;
-       }
-
-       /*
-        * No right-hand children. Everything down and left is smaller than us,
-        * so any 'next' node must be in the general direction of our parent.
-        * Go up the tree; any time the ancestor is a right-hand child of its
-        * parent, keep going up. First time it's a left-hand child of its
-        * parent, said parent is our 'next' node.
-        */
-       while ((parent = rb_parent(node)) && node == parent->rb_right)
-               node = parent;
-
-       return parent;
-}
-
-struct rb_node *rb_prev(const struct rb_node *node)
-{
-       struct rb_node *parent;
-
-       if (RB_EMPTY_NODE(node))
-               return NULL;
-
-       /*
-        * If we have a left-hand child, go down and then right as far
-        * as we can.
-        */
-       if (node->rb_left) {
-               node = node->rb_left;
-               while (node->rb_right)
-                       node=node->rb_right;
-               return (struct rb_node *)node;
-       }
-
-       /*
-        * No left-hand children. Go up till we find an ancestor which
-        * is a right-hand child of its parent.
-        */
-       while ((parent = rb_parent(node)) && node == parent->rb_left)
-               node = parent;
-
-       return parent;
-}
-
-void rb_replace_node(struct rb_node *victim, struct rb_node *new,
-                    struct rb_root *root)
-{
-       struct rb_node *parent = rb_parent(victim);
-
-       /* Set the surrounding nodes to point to the replacement */
-       __rb_change_child(victim, new, parent, root);
-       if (victim->rb_left)
-               rb_set_parent(victim->rb_left, new);
-       if (victim->rb_right)
-               rb_set_parent(victim->rb_right, new);
-
-       /* Copy the pointers/colour from the victim to the replacement */
-       *new = *victim;
-}