Blame gfs2/include/osi_tree.h

Packit Service 360c39
#ifndef __OSI_RBTREE_DOT_H__
Packit Service 360c39
#define __OSI_RBTREE_DOT_H__
Packit Service 360c39
Packit Service 360c39
#include <stdlib.h>
Packit Service 360c39
#include <stddef.h>
Packit Service 360c39
#include <assert.h>
Packit Service 360c39
Packit Service 360c39
/* Adapted from the kernel's rbtree.c */
Packit Service 360c39
struct osi_node {
Packit Service 360c39
	unsigned long  osi_parent_color;
Packit Service 360c39
#define	OSI_RED		0
Packit Service 360c39
#define	OSI_BLACK	1
Packit Service 360c39
	struct osi_node *osi_left;
Packit Service 360c39
	struct osi_node *osi_right;
Packit Service 360c39
};
Packit Service 360c39
Packit Service 360c39
#define osi_parent(r)   ((struct osi_node *)((r)->osi_parent_color & ~3))
Packit Service 360c39
#define osi_color(r)   ((r)->osi_parent_color & 1)
Packit Service 360c39
#define osi_is_red(r)   (!osi_color(r))
Packit Service 360c39
#define osi_is_black(r) osi_color(r)
Packit Service 360c39
#define osi_set_red(r)  do { (r)->osi_parent_color &= ~1; } while (0)
Packit Service 360c39
#define osi_set_black(r)  do { (r)->osi_parent_color |= 1; } while (0)
Packit Service 360c39
#define OSI_EMPTY_NODE(node) (osi_parent(node) == node)
Packit Service 360c39
Packit Service 360c39
struct osi_root
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *osi_node;
Packit Service 360c39
};
Packit Service 360c39
Packit Service 360c39
#define OSI_EMPTY_ROOT(root)  ((root)->osi_node == NULL)
Packit Service 360c39
Packit Service 360c39
static inline void osi_set_parent(struct osi_node *rb, struct osi_node *p)
Packit Service 360c39
{
Packit Service 360c39
        rb->osi_parent_color = (rb->osi_parent_color & 3) | (unsigned long)p;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void osi_set_color(struct osi_node *rb, int color)
Packit Service 360c39
{
Packit Service 360c39
	rb->osi_parent_color = (rb->osi_parent_color & ~1) | color;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void osi_link_node(struct osi_node *node,
Packit Service 360c39
				 struct osi_node *parent,
Packit Service 360c39
				 struct osi_node **osi_link)
Packit Service 360c39
{
Packit Service 360c39
	node->osi_parent_color = (unsigned long )parent;
Packit Service 360c39
	node->osi_left = node->osi_right = NULL;
Packit Service 360c39
Packit Service 360c39
	*osi_link = node;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void __osi_rotate_left(struct osi_node *node,
Packit Service 360c39
				     struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *right = node->osi_right;
Packit Service 360c39
	struct osi_node *parent = osi_parent(node);
Packit Service 360c39
Packit Service 360c39
	if ((node->osi_right = right->osi_left))
Packit Service 360c39
		osi_set_parent(right->osi_left, node);
Packit Service 360c39
	right->osi_left = node;
Packit Service 360c39
Packit Service 360c39
	osi_set_parent(right, parent);
Packit Service 360c39
Packit Service 360c39
	if (parent) {
Packit Service 360c39
		if (node == parent->osi_left)
Packit Service 360c39
			parent->osi_left = right;
Packit Service 360c39
		else
Packit Service 360c39
			parent->osi_right = right;
Packit Service 360c39
	}
Packit Service 360c39
	else
Packit Service 360c39
		root->osi_node = right;
Packit Service 360c39
	osi_set_parent(node, right);
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void __osi_rotate_right(struct osi_node *node,
Packit Service 360c39
				      struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *left = node->osi_left;
Packit Service 360c39
	struct osi_node *parent = osi_parent(node);
Packit Service 360c39
Packit Service 360c39
	if ((node->osi_left = left->osi_right))
Packit Service 360c39
		osi_set_parent(left->osi_right, node);
Packit Service 360c39
	left->osi_right = node;
Packit Service 360c39
Packit Service 360c39
	osi_set_parent(left, parent);
Packit Service 360c39
Packit Service 360c39
	if (parent) {
Packit Service 360c39
		if (node == parent->osi_right)
Packit Service 360c39
			parent->osi_right = left;
Packit Service 360c39
		else
Packit Service 360c39
			parent->osi_left = left;
Packit Service 360c39
	} else
Packit Service 360c39
		root->osi_node = left;
Packit Service 360c39
	osi_set_parent(node, left);
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void osi_insert_color(struct osi_node *node,
Packit Service 360c39
				    struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *parent, *gparent;
Packit Service 360c39
Packit Service 360c39
	while ((parent = osi_parent(node)) && osi_is_red(parent)) {
Packit Service 360c39
		gparent = osi_parent(parent);
Packit Service 360c39
Packit Service 360c39
		if (parent == gparent->osi_left) {
Packit Service 360c39
			{
Packit Service 360c39
				register struct osi_node *uncle = gparent->osi_right;
Packit Service 360c39
				if (uncle && osi_is_red(uncle)) {
Packit Service 360c39
					osi_set_black(uncle);
Packit Service 360c39
					osi_set_black(parent);
Packit Service 360c39
					osi_set_red(gparent);
Packit Service 360c39
					node = gparent;
Packit Service 360c39
					continue;
Packit Service 360c39
				}
Packit Service 360c39
			}
Packit Service 360c39
Packit Service 360c39
			if (parent->osi_right == node) {
Packit Service 360c39
				register struct osi_node *tmp;
Packit Service 360c39
Packit Service 360c39
				__osi_rotate_left(parent, root);
Packit Service 360c39
				tmp = parent;
Packit Service 360c39
				parent = node;
Packit Service 360c39
				node = tmp;
Packit Service 360c39
			}
Packit Service 360c39
Packit Service 360c39
			osi_set_black(parent);
Packit Service 360c39
			osi_set_red(gparent);
Packit Service 360c39
			__osi_rotate_right(gparent, root);
Packit Service 360c39
		} else {
Packit Service 360c39
			{
Packit Service 360c39
				register struct osi_node *uncle = gparent->osi_left;
Packit Service 360c39
				if (uncle && osi_is_red(uncle)) {
Packit Service 360c39
					osi_set_black(uncle);
Packit Service 360c39
					osi_set_black(parent);
Packit Service 360c39
					osi_set_red(gparent);
Packit Service 360c39
					node = gparent;
Packit Service 360c39
					continue;
Packit Service 360c39
				}
Packit Service 360c39
			}
Packit Service 360c39
Packit Service 360c39
			if (parent->osi_left == node) {
Packit Service 360c39
				register struct osi_node *tmp;
Packit Service 360c39
				__osi_rotate_right(parent, root);
Packit Service 360c39
				tmp = parent;
Packit Service 360c39
				parent = node;
Packit Service 360c39
				node = tmp;
Packit Service 360c39
			}
Packit Service 360c39
Packit Service 360c39
			osi_set_black(parent);
Packit Service 360c39
			osi_set_red(gparent);
Packit Service 360c39
			__osi_rotate_left(gparent, root);
Packit Service 360c39
		}
Packit Service 360c39
	}
Packit Service 360c39
Packit Service 360c39
	osi_set_black(root->osi_node);
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void __osi_erase_color(struct osi_node *node,
Packit Service 360c39
				     struct osi_node *parent,
Packit Service 360c39
				     struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *other;
Packit Service 360c39
Packit Service 360c39
	while ((!node || osi_is_black(node)) && node != root->osi_node) {
Packit Service 360c39
		if (parent->osi_left == node) {
Packit Service 360c39
			other = parent->osi_right;
Packit Service 360c39
			if (osi_is_red(other)) {
Packit Service 360c39
				osi_set_black(other);
Packit Service 360c39
				osi_set_red(parent);
Packit Service 360c39
				__osi_rotate_left(parent, root);
Packit Service 360c39
				other = parent->osi_right;
Packit Service 360c39
			}
Packit Service 360c39
			if ((!other->osi_left || osi_is_black(other->osi_left)) &&
Packit Service 360c39
			    (!other->osi_right || osi_is_black(other->osi_right)))
Packit Service 360c39
			{
Packit Service 360c39
				osi_set_red(other);
Packit Service 360c39
				node = parent;
Packit Service 360c39
				parent = osi_parent(node);
Packit Service 360c39
			} else {
Packit Service 360c39
				if (!other->osi_right || osi_is_black(other->osi_right))
Packit Service 360c39
				{
Packit Service 360c39
					struct osi_node *o_left;
Packit Service 360c39
					if ((o_left = other->osi_left))
Packit Service 360c39
						osi_set_black(o_left);
Packit Service 360c39
					osi_set_red(other);
Packit Service 360c39
					__osi_rotate_right(other, root);
Packit Service 360c39
					other = parent->osi_right;
Packit Service 360c39
				}
Packit Service 360c39
				osi_set_color(other, osi_color(parent));
Packit Service 360c39
				osi_set_black(parent);
Packit Service 360c39
				if (other->osi_right)
Packit Service 360c39
					osi_set_black(other->osi_right);
Packit Service 360c39
				__osi_rotate_left(parent, root);
Packit Service 360c39
				node = root->osi_node;
Packit Service 360c39
				break;
Packit Service 360c39
			}
Packit Service 360c39
		} else {
Packit Service 360c39
			other = parent->osi_left;
Packit Service 360c39
			if (osi_is_red(other)) {
Packit Service 360c39
				osi_set_black(other);
Packit Service 360c39
				osi_set_red(parent);
Packit Service 360c39
				__osi_rotate_right(parent, root);
Packit Service 360c39
				other = parent->osi_left;
Packit Service 360c39
			}
Packit Service 360c39
			if ((!other->osi_left || osi_is_black(other->osi_left)) &&
Packit Service 360c39
			    (!other->osi_right || osi_is_black(other->osi_right)))
Packit Service 360c39
			{
Packit Service 360c39
				osi_set_red(other);
Packit Service 360c39
				node = parent;
Packit Service 360c39
				parent = osi_parent(node);
Packit Service 360c39
			} else {
Packit Service 360c39
				if (!other->osi_left || osi_is_black(other->osi_left))
Packit Service 360c39
				{
Packit Service 360c39
					register struct osi_node *o_right;
Packit Service 360c39
					if ((o_right = other->osi_right))
Packit Service 360c39
						osi_set_black(o_right);
Packit Service 360c39
					osi_set_red(other);
Packit Service 360c39
					__osi_rotate_left(other, root);
Packit Service 360c39
					other = parent->osi_left;
Packit Service 360c39
				}
Packit Service 360c39
				osi_set_color(other, osi_color(parent));
Packit Service 360c39
				osi_set_black(parent);
Packit Service 360c39
				if (other->osi_left)
Packit Service 360c39
					osi_set_black(other->osi_left);
Packit Service 360c39
				__osi_rotate_right(parent, root);
Packit Service 360c39
				node = root->osi_node;
Packit Service 360c39
				break;
Packit Service 360c39
			}
Packit Service 360c39
		}
Packit Service 360c39
	}
Packit Service 360c39
	if (node)
Packit Service 360c39
		osi_set_black(node);
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void osi_erase(struct osi_node *node, struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *child, *parent;
Packit Service 360c39
	int color;
Packit Service 360c39
Packit Service 360c39
	if (!node->osi_left)
Packit Service 360c39
		child = node->osi_right;
Packit Service 360c39
	else if (!node->osi_right)
Packit Service 360c39
		child = node->osi_left;
Packit Service 360c39
	else {
Packit Service 360c39
		struct osi_node *old = node, *left;
Packit Service 360c39
Packit Service 360c39
		node = node->osi_right;
Packit Service 360c39
		while ((left = node->osi_left) != NULL)
Packit Service 360c39
			node = left;
Packit Service 360c39
Packit Service 360c39
		if (osi_parent(old)) {
Packit Service 360c39
			if (osi_parent(old)->osi_left == old)
Packit Service 360c39
				osi_parent(old)->osi_left = node;
Packit Service 360c39
			else
Packit Service 360c39
				osi_parent(old)->osi_right = node;
Packit Service 360c39
		} else
Packit Service 360c39
			root->osi_node = node;
Packit Service 360c39
Packit Service 360c39
		child = node->osi_right;
Packit Service 360c39
		parent = osi_parent(node);
Packit Service 360c39
		color = osi_color(node);
Packit Service 360c39
Packit Service 360c39
		if (parent == old) {
Packit Service 360c39
			parent = node;
Packit Service 360c39
		} else {
Packit Service 360c39
			if (child)
Packit Service 360c39
				osi_set_parent(child, parent);
Packit Service 360c39
			parent->osi_left = child;
Packit Service 360c39
Packit Service 360c39
			node->osi_right = old->osi_right;
Packit Service 360c39
			osi_set_parent(old->osi_right, node);
Packit Service 360c39
		}
Packit Service 360c39
Packit Service 360c39
		node->osi_parent_color = old->osi_parent_color;
Packit Service 360c39
		node->osi_left = old->osi_left;
Packit Service 360c39
		osi_set_parent(old->osi_left, node);
Packit Service 360c39
Packit Service 360c39
		goto color;
Packit Service 360c39
	}
Packit Service 360c39
Packit Service 360c39
	parent = osi_parent(node);
Packit Service 360c39
	color = osi_color(node);
Packit Service 360c39
Packit Service 360c39
	if (child)
Packit Service 360c39
		osi_set_parent(child, parent);
Packit Service 360c39
	if (parent)
Packit Service 360c39
	{
Packit Service 360c39
		if (parent->osi_left == node)
Packit Service 360c39
			parent->osi_left = child;
Packit Service 360c39
		else
Packit Service 360c39
			parent->osi_right = child;
Packit Service 360c39
	}
Packit Service 360c39
	else
Packit Service 360c39
		root->osi_node = child;
Packit Service 360c39
Packit Service 360c39
 color:
Packit Service 360c39
	if (color == OSI_BLACK)
Packit Service 360c39
		__osi_erase_color(child, parent, root);
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
/*
Packit Service 360c39
 * This function returns the first node (in sort order) of the tree.
Packit Service 360c39
 */
Packit Service 360c39
static inline struct osi_node *osi_first(struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node	*n;
Packit Service 360c39
Packit Service 360c39
	n = root->osi_node;
Packit Service 360c39
	if (!n)
Packit Service 360c39
		return NULL;
Packit Service 360c39
	while (n->osi_left)
Packit Service 360c39
		n = n->osi_left;
Packit Service 360c39
	return n;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline struct osi_node *osi_last(struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node	*n;
Packit Service 360c39
Packit Service 360c39
	n = root->osi_node;
Packit Service 360c39
	if (!n)
Packit Service 360c39
		return NULL;
Packit Service 360c39
	while (n->osi_right)
Packit Service 360c39
		n = n->osi_right;
Packit Service 360c39
	return n;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline struct osi_node *osi_next(struct osi_node *node)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *parent;
Packit Service 360c39
Packit Service 360c39
	if (OSI_EMPTY_NODE(node))
Packit Service 360c39
		return NULL;
Packit Service 360c39
Packit Service 360c39
	/* If we have a right-hand child, go down and then left as far
Packit Service 360c39
	   as we can. */
Packit Service 360c39
	if (node->osi_right) {
Packit Service 360c39
		node = node->osi_right;
Packit Service 360c39
		while (node->osi_left)
Packit Service 360c39
			node=node->osi_left;
Packit Service 360c39
		return node;
Packit Service 360c39
	}
Packit Service 360c39
Packit Service 360c39
	/* No right-hand children.  Everything down and left is
Packit Service 360c39
	   smaller than us, so any 'next' node must be in the general
Packit Service 360c39
	   direction of our parent. Go up the tree; any time the
Packit Service 360c39
	   ancestor is a right-hand child of its parent, keep going
Packit Service 360c39
	   up. First time it's a left-hand child of its parent, said
Packit Service 360c39
	   parent is our 'next' node. */
Packit Service 360c39
	while ((parent = osi_parent(node)) && node == parent->osi_right)
Packit Service 360c39
		node = parent;
Packit Service 360c39
Packit Service 360c39
	return parent;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline struct osi_node *osi_prev(struct osi_node *node)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *parent;
Packit Service 360c39
Packit Service 360c39
	if (OSI_EMPTY_NODE(node))
Packit Service 360c39
		return NULL;
Packit Service 360c39
Packit Service 360c39
	/* If we have a left-hand child, go down and then right as far
Packit Service 360c39
	   as we can. */
Packit Service 360c39
	if (node->osi_left) {
Packit Service 360c39
		node = node->osi_left;
Packit Service 360c39
		while (node->osi_right)
Packit Service 360c39
			node=node->osi_right;
Packit Service 360c39
		return node;
Packit Service 360c39
	}
Packit Service 360c39
Packit Service 360c39
	/* No left-hand children. Go up till we find an ancestor which
Packit Service 360c39
	   is a right-hand child of its parent */
Packit Service 360c39
	while ((parent = osi_parent(node)) && node == parent->osi_left)
Packit Service 360c39
		node = parent;
Packit Service 360c39
Packit Service 360c39
	return parent;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
static inline void osi_replace_node(struct osi_node *victim,
Packit Service 360c39
				    struct osi_node *new,
Packit Service 360c39
				    struct osi_root *root)
Packit Service 360c39
{
Packit Service 360c39
	struct osi_node *parent = osi_parent(victim);
Packit Service 360c39
Packit Service 360c39
	/* Set the surrounding nodes to point to the replacement */
Packit Service 360c39
	if (parent) {
Packit Service 360c39
		if (victim == parent->osi_left)
Packit Service 360c39
			parent->osi_left = new;
Packit Service 360c39
		else
Packit Service 360c39
			parent->osi_right = new;
Packit Service 360c39
	} else {
Packit Service 360c39
		root->osi_node = new;
Packit Service 360c39
	}
Packit Service 360c39
	if (victim->osi_left)
Packit Service 360c39
		osi_set_parent(victim->osi_left, new);
Packit Service 360c39
	if (victim->osi_right)
Packit Service 360c39
		osi_set_parent(victim->osi_right, new);
Packit Service 360c39
Packit Service 360c39
	/* Copy the pointers/colour from the victim to the replacement */
Packit Service 360c39
	*new = *victim;
Packit Service 360c39
}
Packit Service 360c39
Packit Service 360c39
#endif