You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
linux/lib/rbtree.c
*/
#include "rbtree.h"
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+static void __rb_rotate_left(struct fio_rb_node *node, struct rb_root *root)
{
- struct rb_node *right = node->rb_right;
- struct rb_node *parent = rb_parent(node);
+ struct fio_rb_node *right = node->rb_right;
+ struct fio_rb_node *parent = rb_parent(node);
if ((node->rb_right = right->rb_left))
rb_set_parent(right->rb_left, node);
rb_set_parent(node, right);
}
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+static void __rb_rotate_right(struct fio_rb_node *node, struct rb_root *root)
{
- struct rb_node *left = node->rb_left;
- struct rb_node *parent = rb_parent(node);
+ struct fio_rb_node *left = node->rb_left;
+ struct fio_rb_node *parent = rb_parent(node);
if ((node->rb_left = left->rb_right))
rb_set_parent(left->rb_right, node);
rb_set_parent(node, left);
}
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+void rb_insert_color(struct fio_rb_node *node, struct rb_root *root)
{
- struct rb_node *parent, *gparent;
+ struct fio_rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
if (parent == gparent->rb_left)
{
{
- register struct rb_node *uncle = gparent->rb_right;
+ register struct fio_rb_node *uncle = gparent->rb_right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
if (parent->rb_right == node)
{
- register struct rb_node *tmp;
+ register struct fio_rb_node *tmp;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
__rb_rotate_right(gparent, root);
} else {
{
- register struct rb_node *uncle = gparent->rb_left;
+ register struct fio_rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
if (parent->rb_left == node)
{
- register struct rb_node *tmp;
+ register struct fio_rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
rb_set_black(root->rb_node);
}
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+static void __rb_erase_color(struct fio_rb_node *node,
+ struct fio_rb_node *parent,
struct rb_root *root)
{
- struct rb_node *other;
+ struct fio_rb_node *other;
while ((!node || rb_is_black(node)) && node != root->rb_node)
{
{
if (!other->rb_right || rb_is_black(other->rb_right))
{
- struct rb_node *o_left;
+ struct fio_rb_node *o_left;
if ((o_left = other->rb_left))
rb_set_black(o_left);
rb_set_red(other);
{
if (!other->rb_left || rb_is_black(other->rb_left))
{
- register struct rb_node *o_right;
+ register struct fio_rb_node *o_right;
if ((o_right = other->rb_right))
rb_set_black(o_right);
rb_set_red(other);
rb_set_black(node);
}
-void rb_erase(struct rb_node *node, struct rb_root *root)
+void rb_erase(struct fio_rb_node *node, struct rb_root *root)
{
- struct rb_node *child, *parent;
+ struct fio_rb_node *child, *parent;
int color;
if (!node->rb_left)
child = node->rb_left;
else
{
- struct rb_node *old = node, *left;
+ struct fio_rb_node *old = node, *left;
node = node->rb_right;
while ((left = node->rb_left) != NULL)
/*
* This function returns the first node (in sort order) of the tree.
*/
-struct rb_node *rb_first(struct rb_root *root)
+struct fio_rb_node *rb_first(struct rb_root *root)
{
- struct rb_node *n;
+ struct fio_rb_node *n;
n = root->rb_node;
if (!n)
return n;
}
-struct rb_node *rb_next(const struct rb_node *node)
+struct fio_rb_node *rb_next(const struct fio_rb_node *node)
{
- struct rb_node *parent;
+ struct fio_rb_node *parent;
if (RB_EMPTY_NODE(node))
return NULL;
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
- return (struct rb_node *)node;
+ return (struct fio_rb_node *)node;
}
/*