Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
- (C) 2007 Andre Noll <maan@systemlinux.org>
+ (C) 2007 Andre Noll <maan@tuebingen.mpg.de>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
/*
* This function returns the first node (in sort order) of the tree.
*/
-struct rb_node *rb_first(struct rb_root *root)
+struct rb_node *rb_first(const struct rb_root *root)
{
struct rb_node *n;
return n;
}
-struct rb_node *rb_last(struct rb_root *root)
+struct rb_node *rb_last(const struct rb_root *root)
{
struct rb_node *n;
return n;
}
-struct rb_node *rb_next(struct rb_node *node)
+struct rb_node *rb_next(const struct rb_node *node)
{
struct rb_node *parent;
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
- return node;
+ return (struct rb_node *)node;
}
/* No right-hand children. Everything down and left is
return parent;
}
-struct rb_node *rb_prev(struct rb_node *node)
+struct rb_node *rb_prev(const struct rb_node *node)
{
struct rb_node *parent;
node = node->rb_left;
while (node->rb_right)
node=node->rb_right;
- return node;
+ return (struct rb_node *)node;
}
/* No left-hand children. Go up till we find an ancestor which
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 */
- if (parent) {
- if (victim == parent->rb_left)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else {
- root->rb_node = new;
- }
- 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;
-}
-
/**
* Get the n-th node (in sort order) of the tree.
*
*
* \return Pointer to the \a n th greatest node on success, \p NULL on errors.
*/
-struct rb_node *rb_nth(struct rb_node *node, unsigned n)
+struct rb_node *rb_nth(const struct rb_node *node, unsigned n)
{
unsigned size = 1;
if (node->rb_left)
size += node->rb_left->size;
if (n == size)
- return node;
+ return (struct rb_node *)node;
if (n < size)
return rb_nth(node->rb_left, n);
return rb_nth(node->rb_right, n - size);
*
* \return Positive on success, -1 on errors.
*/
-int rb_rank(struct rb_node *node, unsigned *rank)
+int rb_rank(const struct rb_node *node, unsigned *rank)
{
*rank = 1;
struct rb_node *parent;