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)
n = n->rb_left;
return n;
}
+
+struct fio_rb_node *rb_next(const struct fio_rb_node *node)
+{
+ struct fio_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 fio_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;
+}