shithub: lwext4

Download patch

ref: 753d3b470be3150f50d99fea84280424ae5c3eb2
parent: ce0087be0d06ad6efc332ba0c8146aa29d439b2d
author: ngkaho1234 <[email protected]>
date: Sun Oct 4 17:39:03 EDT 2015 

1. Use rbtree implementation from Freebsd kernel instead of the one from Linux Kernel.2. FIX: ext4_xattr_item_alloc_data: data_size == 1 when copying the on-disk data to memory.


--- a/lwext4/ext4_rbtree.c
+++ /dev/null
@@ -1,462 +1,0 @@
-/*
-  Red Black Trees
-  (C) 1999  Andrea Arcangeli <[email protected]>
-  (C) 2002  David Woodhouse <[email protected]>
-
-  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
-  the Free Software Foundation; either version 2 of the License, or
-  (at your option) any later version.
-
-  This program is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-  GNU General Public License for more details.
-
-  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
-
-  linux/lib/rbtree.c
-*/
-#include "ext4_rbtree.h"
-
-static void __ext4_rb_rotate_left(struct ext4_rb_node *node, struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *right = node->ext4_rb_right;
-	struct ext4_rb_node *parent = ext4_rb_parent(node);
-
-	if ((node->ext4_rb_right = right->ext4_rb_left))
-		ext4_rb_set_parent(right->ext4_rb_left, node);
-	right->ext4_rb_left = node;
-
-	ext4_rb_set_parent(right, parent);
-
-	if (parent) {
-		if (node == parent->ext4_rb_left)
-			parent->ext4_rb_left = right;
-		else
-			parent->ext4_rb_right = right;
-	} else
-		root->ext4_rb_node = right;
-	ext4_rb_set_parent(node, right);
-}
-
-static void __ext4_rb_rotate_right(struct ext4_rb_node *node, struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *left = node->ext4_rb_left;
-	struct ext4_rb_node *parent = ext4_rb_parent(node);
-
-	if ((node->ext4_rb_left = left->ext4_rb_right))
-		ext4_rb_set_parent(left->ext4_rb_right, node);
-	left->ext4_rb_right = node;
-
-	ext4_rb_set_parent(left, parent);
-
-	if (parent) {
-		if (node == parent->ext4_rb_right)
-			parent->ext4_rb_right = left;
-		else
-			parent->ext4_rb_left = left;
-	} else
-		root->ext4_rb_node = left;
-	ext4_rb_set_parent(node, left);
-}
-
-void ext4_rb_insert_color(struct ext4_rb_node *node, struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *parent, *gparent;
-
-	while ((parent = ext4_rb_parent(node)) && ext4_rb_is_red(parent)) {
-		gparent = ext4_rb_parent(parent);
-
-		if (parent == gparent->ext4_rb_left) {
-			{
-				register struct ext4_rb_node *uncle =
-				    gparent->ext4_rb_right;
-				if (uncle && ext4_rb_is_red(uncle)) {
-					ext4_rb_set_black(uncle);
-					ext4_rb_set_black(parent);
-					ext4_rb_set_red(gparent);
-					node = gparent;
-					continue;
-				}
-			}
-
-			if (parent->ext4_rb_right == node) {
-				register struct ext4_rb_node *tmp;
-				__ext4_rb_rotate_left(parent, root);
-				tmp = parent;
-				parent = node;
-				node = tmp;
-			}
-
-			ext4_rb_set_black(parent);
-			ext4_rb_set_red(gparent);
-			__ext4_rb_rotate_right(gparent, root);
-		} else {
-			{
-				register struct ext4_rb_node *uncle =
-				    gparent->ext4_rb_left;
-				if (uncle && ext4_rb_is_red(uncle)) {
-					ext4_rb_set_black(uncle);
-					ext4_rb_set_black(parent);
-					ext4_rb_set_red(gparent);
-					node = gparent;
-					continue;
-				}
-			}
-
-			if (parent->ext4_rb_left == node) {
-				register struct ext4_rb_node *tmp;
-				__ext4_rb_rotate_right(parent, root);
-				tmp = parent;
-				parent = node;
-				node = tmp;
-			}
-
-			ext4_rb_set_black(parent);
-			ext4_rb_set_red(gparent);
-			__ext4_rb_rotate_left(gparent, root);
-		}
-	}
-
-	ext4_rb_set_black(root->ext4_rb_node);
-}
-
-static void __ext4_rb_erase_color(struct ext4_rb_node *node, struct ext4_rb_node *parent,
-			       struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *other;
-
-	while ((!node || ext4_rb_is_black(node)) && node != root->ext4_rb_node) {
-		if (parent->ext4_rb_left == node) {
-			other = parent->ext4_rb_right;
-			if (ext4_rb_is_red(other)) {
-				ext4_rb_set_black(other);
-				ext4_rb_set_red(parent);
-				__ext4_rb_rotate_left(parent, root);
-				other = parent->ext4_rb_right;
-			}
-			if ((!other->ext4_rb_left ||
-			     ext4_rb_is_black(other->ext4_rb_left)) &&
-			    (!other->ext4_rb_right ||
-			     ext4_rb_is_black(other->ext4_rb_right))) {
-				ext4_rb_set_red(other);
-				node = parent;
-				parent = ext4_rb_parent(node);
-			} else {
-				if (!other->ext4_rb_right ||
-				    ext4_rb_is_black(other->ext4_rb_right)) {
-					ext4_rb_set_black(other->ext4_rb_left);
-					ext4_rb_set_red(other);
-					__ext4_rb_rotate_right(other, root);
-					other = parent->ext4_rb_right;
-				}
-				ext4_rb_set_color(other, ext4_rb_color(parent));
-				ext4_rb_set_black(parent);
-				ext4_rb_set_black(other->ext4_rb_right);
-				__ext4_rb_rotate_left(parent, root);
-				node = root->ext4_rb_node;
-				break;
-			}
-		} else {
-			other = parent->ext4_rb_left;
-			if (ext4_rb_is_red(other)) {
-				ext4_rb_set_black(other);
-				ext4_rb_set_red(parent);
-				__ext4_rb_rotate_right(parent, root);
-				other = parent->ext4_rb_left;
-			}
-			if ((!other->ext4_rb_left ||
-			     ext4_rb_is_black(other->ext4_rb_left)) &&
-			    (!other->ext4_rb_right ||
-			     ext4_rb_is_black(other->ext4_rb_right))) {
-				ext4_rb_set_red(other);
-				node = parent;
-				parent = ext4_rb_parent(node);
-			} else {
-				if (!other->ext4_rb_left ||
-				    ext4_rb_is_black(other->ext4_rb_left)) {
-					ext4_rb_set_black(other->ext4_rb_right);
-					ext4_rb_set_red(other);
-					__ext4_rb_rotate_left(other, root);
-					other = parent->ext4_rb_left;
-				}
-				ext4_rb_set_color(other, ext4_rb_color(parent));
-				ext4_rb_set_black(parent);
-				ext4_rb_set_black(other->ext4_rb_left);
-				__ext4_rb_rotate_right(parent, root);
-				node = root->ext4_rb_node;
-				break;
-			}
-		}
-	}
-	if (node)
-		ext4_rb_set_black(node);
-}
-
-void __ext4_rb_erase(struct ext4_rb_node *node, struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *child, *parent;
-	int color;
-
-	if (!node->ext4_rb_left)
-		child = node->ext4_rb_right;
-	else if (!node->ext4_rb_right)
-		child = node->ext4_rb_left;
-	else {
-		struct ext4_rb_node *old = node, *left;
-
-		node = node->ext4_rb_right;
-		while ((left = node->ext4_rb_left) != NULL)
-			node = left;
-
-		if (ext4_rb_parent(old)) {
-			if (ext4_rb_parent(old)->ext4_rb_left == old)
-				ext4_rb_parent(old)->ext4_rb_left = node;
-			else
-				ext4_rb_parent(old)->ext4_rb_right = node;
-		} else
-			root->ext4_rb_node = node;
-
-		child = node->ext4_rb_right;
-		parent = ext4_rb_parent(node);
-		color = ext4_rb_color(node);
-
-		if (parent == old) {
-			parent = node;
-		} else {
-			if (child)
-				ext4_rb_set_parent(child, parent);
-			parent->ext4_rb_left = child;
-
-			node->ext4_rb_right = old->ext4_rb_right;
-			ext4_rb_set_parent(old->ext4_rb_right, node);
-		}
-
-		node->ext4_rb_parent_color = old->ext4_rb_parent_color;
-		node->ext4_rb_left = old->ext4_rb_left;
-		ext4_rb_set_parent(old->ext4_rb_left, node);
-
-		goto color;
-	}
-
-	parent = ext4_rb_parent(node);
-	color = ext4_rb_color(node);
-
-	if (child)
-		ext4_rb_set_parent(child, parent);
-	if (parent) {
-		if (parent->ext4_rb_left == node)
-			parent->ext4_rb_left = child;
-		else
-			parent->ext4_rb_right = child;
-	} else
-		root->ext4_rb_node = child;
-
-color:
-	if (color == EXT4_RB_BLACK)
-		__ext4_rb_erase_color(child, parent, root);
-}
-
-static void ext4_rb_augment_path(struct ext4_rb_node *node, ext4_rb_augment_f func,
-			      void *data)
-{
-	struct ext4_rb_node *parent;
-
-up:
-	func(node, data);
-	parent = ext4_rb_parent(node);
-	if (!parent)
-		return;
-
-	if (node == parent->ext4_rb_left && parent->ext4_rb_right)
-		func(parent->ext4_rb_right, data);
-	else if (parent->ext4_rb_left)
-		func(parent->ext4_rb_left, data);
-
-	node = parent;
-	goto up;
-}
-
-/*
- * after inserting @node into the tree, update the tree to account for
- * both the new entry and any damage done by rebalance
- */
-void ext4_rb_augment_insert(struct ext4_rb_node *node, ext4_rb_augment_f func,
-			 void *data)
-{
-	if (node->ext4_rb_left)
-		node = node->ext4_rb_left;
-	else if (node->ext4_rb_right)
-		node = node->ext4_rb_right;
-
-	ext4_rb_augment_path(node, func, data);
-}
-
-/*
- * before removing the node, find the deepest node on the rebalance path
- * that will still be there after @node gets removed
- */
-struct ext4_rb_node *ext4_rb_augment_erase_begin(struct ext4_rb_node *node)
-{
-	struct ext4_rb_node *deepest;
-
-	if (!node->ext4_rb_right && !node->ext4_rb_left)
-		deepest = ext4_rb_parent(node);
-	else if (!node->ext4_rb_right)
-		deepest = node->ext4_rb_left;
-	else if (!node->ext4_rb_left)
-		deepest = node->ext4_rb_right;
-	else {
-		deepest = ext4_rb_next(node);
-		if (deepest->ext4_rb_right)
-			deepest = deepest->ext4_rb_right;
-		else if (ext4_rb_parent(deepest) != node)
-			deepest = ext4_rb_parent(deepest);
-	}
-
-	return deepest;
-}
-
-/*
- * after removal, update the tree to account for the removed entry
- * and any rebalance damage.
- */
-void ext4_rb_augment_erase_end(struct ext4_rb_node *node, ext4_rb_augment_f func,
-			    void *data)
-{
-	if (node)
-		ext4_rb_augment_path(node, func, data);
-}
-
-/*
- * This function returns the first node (in sort order) of the tree.
- */
-struct ext4_rb_node *ext4_rb_first(const struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *n;
-
-	n = root->ext4_rb_node;
-	if (!n)
-		return NULL;
-	while (n->ext4_rb_left)
-		n = n->ext4_rb_left;
-	return n;
-}
-
-struct ext4_rb_node *ext4_rb_last(const struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *n;
-
-	n = root->ext4_rb_node;
-	if (!n)
-		return NULL;
-	while (n->ext4_rb_right)
-		n = n->ext4_rb_right;
-	return n;
-}
-
-struct ext4_rb_node *ext4_rb_next(const struct ext4_rb_node *node)
-{
-	struct ext4_rb_node *parent;
-
-	if (ext4_rb_parent(node) == node)
-		return NULL;
-
-	/* If we have a right-hand child, go down and then left as far
-		as we can. */
-	if (node->ext4_rb_right) {
-		node = node->ext4_rb_right;
-		while (node->ext4_rb_left)
-			node = node->ext4_rb_left;
-		return (struct ext4_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 = ext4_rb_parent(node)) && node == parent->ext4_rb_right)
-		node = parent;
-
-	return parent;
-}
-
-struct ext4_rb_node *ext4_rb_prev(const struct ext4_rb_node *node)
-{
-	struct ext4_rb_node *parent;
-
-	if (ext4_rb_parent(node) == node)
-		return NULL;
-
-	/* If we have a left-hand child, go down and then right as far
-	   as we can. */
-	if (node->ext4_rb_left) {
-		node = node->ext4_rb_left;
-		while (node->ext4_rb_right)
-			node = node->ext4_rb_right;
-		return (struct ext4_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 = ext4_rb_parent(node)) && node == parent->ext4_rb_left)
-		node = parent;
-
-	return parent;
-}
-
-void ext4_rb_replace_node(struct ext4_rb_node *victim, struct ext4_rb_node *new,
-		       struct ext4_rb_root *root)
-{
-	struct ext4_rb_node *parent = ext4_rb_parent(victim);
-
-	/* Set the surrounding nodes to point to the replacement */
-	if (parent) {
-		if (victim == parent->ext4_rb_left)
-			parent->ext4_rb_left = new;
-		else
-			parent->ext4_rb_right = new;
-	} else {
-		root->ext4_rb_node = new;
-	}
-	if (victim->ext4_rb_left)
-		ext4_rb_set_parent(victim->ext4_rb_left, new);
-	if (victim->ext4_rb_right)
-		ext4_rb_set_parent(victim->ext4_rb_right, new);
-
-	/* Copy the pointers/colour from the victim to the replacement */
-	*new = *victim;
-}
-
-void ext4_rb_erase(struct ext4_rb_node *node, struct ext4_rb_root *root)
-{
-	__ext4_rb_erase(node, root);
-}
-
-void ext4_rb_insert(struct ext4_rb_root *root, struct ext4_rb_node *node,
-		 int (*cmp)(struct ext4_rb_node *, struct ext4_rb_node *))
-{
-	struct ext4_rb_node **new = &(root->ext4_rb_node), *parent = NULL;
-
-	/* Figure out where to put new node */
-	while (*new) {
-		int result = cmp(node, *new);
-
-		parent = *new;
-		if (result < 0) {
-			new = &((*new)->ext4_rb_left);
-		} else if (result > 0) {
-			new = &((*new)->ext4_rb_right);
-		} else
-			return;
-	}
-
-	/* Add new node and rebalance tree. */
-	ext4_rb_link_node(node, parent, new);
-	ext4_rb_insert_color(node, root);
-}
--- a/lwext4/ext4_rbtree.h
+++ /dev/null
@@ -1,201 +1,0 @@
-/*
-  Red Black Trees
-  (C) 1999  Andrea Arcangeli <[email protected]>
-
-  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
-  the Free Software Foundation; either version 2 of the License, or
-  (at your option) any later version.
-
-  This program is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-  GNU General Public License for more details.
-
-  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
-
-  linux/include/linux/rbtree.h
-
-  To use rbtrees you'll have to implement your own insert and search cores.
-  This will avoid us to use callbacks and to drop drammatically performances.
-  I know it's not the cleaner way,  but in C (not in C++) to get
-  performances and genericity...
-
-  Some example of insert and search follows here. The search is a plain
-  normal search over an ordered tree. The insert instead must be implemented
-  in two steps: First, the code must insert the element in order as a red leaf
-  in the tree, and then the support library function ext4_rb_insert_color() must
-  be called. Such function will do the not trivial work to rebalance the
-  rbtree, if necessary.
-
------------------------------------------------------------------------
-static inline struct page * ext4_rb_search_page_cache(struct inode * inode,
-						 unsigned long offset)
-{
-	struct ext4_rb_node * n = inode->i_ext4_rb_page_cache.ext4_rb_node;
-	struct page * page;
-
-	while (n)
-	{
-		page = ext4_rb_entry(n, struct page, ext4_rb_page_cache);
-
-		if (offset < page->offset)
-			n = n->ext4_rb_left;
-		else if (offset > page->offset)
-			n = n->ext4_rb_right;
-		else
-			return page;
-	}
-	return NULL;
-}
-
-static inline struct page * __ext4_rb_insert_page_cache(struct inode * inode,
-						   unsigned long offset,
-						   struct ext4_rb_node * node)
-{
-	struct ext4_rb_node ** p = &inode->i_ext4_rb_page_cache.ext4_rb_node;
-	struct ext4_rb_node * parent = NULL;
-	struct page * page;
-
-	while (*p)
-	{
-		parent = *p;
-		page = ext4_rb_entry(parent, struct page, ext4_rb_page_cache);
-
-		if (offset < page->offset)
-			p = &(*p)->ext4_rb_left;
-		else if (offset > page->offset)
-			p = &(*p)->ext4_rb_right;
-		else
-			return page;
-	}
-
-	ext4_rb_link_node(node, parent, p);
-
-	return NULL;
-}
-
-static inline struct page * ext4_rb_insert_page_cache(struct inode * inode,
-						 unsigned long offset,
-						 struct ext4_rb_node * node)
-{
-	struct page * ret;
-	if ((ret = __ext4_rb_insert_page_cache(inode, offset, node)))
-		goto out;
-	ext4_rb_insert_color(node, &inode->i_ext4_rb_page_cache);
- out:
-	return ret;
-}
------------------------------------------------------------------------
-*/
-
-#ifndef EXT4_RBTREE_H_
-#define EXT4_RBTREE_H_
-
-#include <stddef.h>
-#include <stdbool.h>
-
-#ifndef offsetof
-#define offsetof(type, member) ((size_t) & ((type *)0)->member)
-#endif
-#ifndef container_of
-#define container_of(ptr, type, member)                                        \
-	((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
-#endif
-
-struct ext4_rb_node
-{
-	unsigned long ext4_rb_parent_color;
-#define EXT4_RB_RED 0
-#define EXT4_RB_BLACK 1
-	struct ext4_rb_node *ext4_rb_right;
-	struct ext4_rb_node *ext4_rb_left;
-};
-/* The alignment might seem pointless, but allegedly CRIS needs it */
-
-struct ext4_rb_root
-{
-	struct ext4_rb_node *ext4_rb_node;
-};
-
-#define ext4_rb_parent(r) ((struct ext4_rb_node *)((r)->ext4_rb_parent_color & ~3))
-#define ext4_rb_color(r) ((r)->ext4_rb_parent_color & 1)
-#define ext4_rb_is_red(r) (!ext4_rb_color(r))
-#define ext4_rb_is_black(r) ext4_rb_color(r)
-#define ext4_rb_set_red(r)                                                        \
-	do {                                                                   \
-		(r)->ext4_rb_parent_color &= ~1;                                  \
-	} while (0)
-#define ext4_rb_set_black(r)                                                      \
-	do {                                                                   \
-		(r)->ext4_rb_parent_color |= 1;                                   \
-	} while (0)
-
-static inline void ext4_rb_set_parent(struct ext4_rb_node *rb, struct ext4_rb_node *p)
-{
-	rb->ext4_rb_parent_color =
-	    (rb->ext4_rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void ext4_rb_set_color(struct ext4_rb_node *rb, int color)
-{
-	rb->ext4_rb_parent_color = (rb->ext4_rb_parent_color & ~1) | color;
-}
-
-#define EXT4_RB_ROOT                                                          \
-	(struct ext4_rb_root)                                                     \
-	{                                                                      \
-		NULL,                                                          \
-	}
-#define ext4_rb_entry(ptr, type, member) container_of(ptr, type, member)
-
-#define EXT4_RB_EMPTY_ROOT(root) ((root)->ext4_rb_node == NULL)
-#define EXT4_RB_EMPTY_NODE(node) (ext4_rb_parent(node) == node)
-#define EXT4_RB_CLEAR_NODE(node) (ext4_rb_set_parent(node, node))
-
-static inline void ext4_rb_init_node(struct ext4_rb_node *rb)
-{
-	rb->ext4_rb_parent_color = 0;
-	rb->ext4_rb_right = NULL;
-	rb->ext4_rb_left = NULL;
-	EXT4_RB_CLEAR_NODE(rb);
-}
-
-extern void ext4_rb_insert_color(struct ext4_rb_node *, struct ext4_rb_root *);
-extern void ext4_rb_erase(struct ext4_rb_node *, struct ext4_rb_root *);
-
-typedef void (*ext4_rb_augment_f)(struct ext4_rb_node *node, void *data);
-
-extern void ext4_rb_augment_insert(struct ext4_rb_node *node, ext4_rb_augment_f func,
-				void *data);
-extern struct ext4_rb_node *ext4_rb_augment_erase_begin(struct ext4_rb_node *node);
-extern void ext4_rb_augment_erase_end(struct ext4_rb_node *node, ext4_rb_augment_f func,
-				   void *data);
-
-/* Find logical next and previous nodes in a tree */
-extern struct ext4_rb_node *ext4_rb_next(const struct ext4_rb_node *);
-extern struct ext4_rb_node *ext4_rb_prev(const struct ext4_rb_node *);
-extern struct ext4_rb_node *ext4_rb_first(const struct ext4_rb_root *);
-extern struct ext4_rb_node *ext4_rb_last(const struct ext4_rb_root *);
-
-/* Fast replacement of a single node without remove/rebalance/add/rebalance */
-extern void ext4_rb_replace_node(struct ext4_rb_node *victim, struct ext4_rb_node *new,
-			      struct ext4_rb_root *root);
-
-static inline void ext4_rb_link_node(struct ext4_rb_node *node,
-				  struct ext4_rb_node *parent,
-				  struct ext4_rb_node **ext4_rb_link)
-{
-	node->ext4_rb_parent_color = (unsigned long)parent;
-	node->ext4_rb_left = node->ext4_rb_right = NULL;
-
-	*ext4_rb_link = node;
-}
-
-extern void ext4_rb_erase(struct ext4_rb_node *, struct ext4_rb_root *);
-
-extern void ext4_rb_insert(struct ext4_rb_root *, struct ext4_rb_node *,
-			int (*)(struct ext4_rb_node *, struct ext4_rb_node *));
-
-#endif /* EXT4_RBTREE_H_ */
--- a/lwext4/ext4_types.h
+++ b/lwext4/ext4_types.h
@@ -45,6 +45,7 @@
 #include "ext4_config.h"
 #include "ext4_blockdev.h"
 #include "ext4_rbtree.h"
+#include "tree.h"
 
 #include <stdint.h>
 
@@ -678,7 +679,7 @@
 	void  *data;
 	size_t data_size;
 
-	struct ext4_rb_node node;
+	RB_ENTRY(ext4_xattr_item) node;
 };
 
 struct ext4_xattr_ref {
@@ -685,9 +686,12 @@
 	bool block_loaded;
 	struct ext4_block block;
 	struct ext4_inode_ref *inode_ref;
-	struct ext4_rb_root root;
 	bool   dirty;
+	size_t ea_size;
 	struct ext4_fs *fs;
+
+	RB_HEAD(ext4_xattr_tree,
+		ext4_xattr_item) root;
 };
 
 #define EXT4_GOOD_OLD_INODE_SIZE	128
--- a/lwext4/ext4_xattr.c
+++ b/lwext4/ext4_xattr.c
@@ -13,13 +13,10 @@
 #include <string.h>
 #include <stdlib.h>
 
-static int ext4_xattr_item_cmp(struct ext4_rb_node *a_,
-				struct ext4_rb_node *b_)
+static int ext4_xattr_item_cmp(struct ext4_xattr_item *a,
+				struct ext4_xattr_item *b)
 {
-	struct ext4_xattr_item *a, *b;
 	int result;
-	a = container_of(a_, struct ext4_xattr_item, node);
-	b = container_of(b_, struct ext4_xattr_item, node);
 	result = a->name_index - b->name_index;
 	if (result)
 		return result;
@@ -31,54 +28,11 @@
 	return memcmp(a->name, b->name, a->name_len);
 }
 
-static struct ext4_xattr_item *
-ext4_xattr_item_lookup(struct ext4_rb_root *root,
-			uint8_t name_index,
-			char   *name,
-			size_t  name_len)
-{
-	struct ext4_rb_node *new = root->ext4_rb_node;
+RB_GENERATE (ext4_xattr_tree,
+	     ext4_xattr_item,
+	     node,
+	     ext4_xattr_item_cmp)
 
-	/* Figure out where to put new node */
-	while (new) {
-		struct ext4_xattr_item *item =
-			container_of(new, struct ext4_xattr_item, node);
-		int result = name_index - item->name_index;
-		if (!result) {
-			result = name_len - item->name_len;
-			if (!result)
-				result = memcmp(name,
-						item->name, name_len);
-
-		}
-
-		if (result < 0)
-			new = new->ext4_rb_left;
-		else if (result > 0)
-			new = new->ext4_rb_right;
-		else
-			return item;
-
-	}
-
-	return NULL;
-}
-
-static void
-ext4_xattr_item_insert(struct ext4_rb_root *root,
-			struct ext4_xattr_item *item)
-{
-	ext4_rb_insert(root, &item->node, ext4_xattr_item_cmp);
-}
-
-static void
-ext4_xattr_item_remove(struct ext4_rb_root *root,
-			struct ext4_xattr_item *item)
-{
-	ext4_rb_erase(&item->node, root);
-}
-
-
 static struct ext4_xattr_item *
 ext4_xattr_item_alloc(uint8_t name_index,
 		      char   *name,
@@ -221,14 +175,13 @@
 		}
 		if (ext4_xattr_item_alloc_data(item,
 					       data,
-					       to_le32(entry->e_value_size)
-			!= EOK)) {
+					       to_le32(entry->e_value_size))
+			!= EOK) {
 			ext4_xattr_item_free(item);
 			ret = ENOMEM;
 			goto Finish;
 		}
-		ext4_xattr_item_insert(&xattr_ref->root,
-					item);
+		RB_INSERT(ext4_xattr_tree, &xattr_ref->root, item);
 
 	}
 
@@ -274,16 +227,13 @@
 		}
 		if (ext4_xattr_item_alloc_data(item,
 					       data,
-					       to_le32(entry->e_value_size)
-			!= EOK)) {
+					       to_le32(entry->e_value_size))
+			!= EOK) {
 			ext4_xattr_item_free(item);
 			ret = ENOMEM;
 			goto Finish;
 		}
-		ext4_xattr_item_insert(&xattr_ref->root,
-					item);
-
-
+		RB_INSERT(ext4_xattr_tree, &xattr_ref->root, item);
 	}
 
 Finish:
@@ -312,13 +262,15 @@
 static void
 ext4_xattr_purge_items(struct ext4_xattr_ref *xattr_ref)
 {
-	struct ext4_rb_node *node;
-	while ((node = ext4_rb_first(&xattr_ref->root))) {
-		struct ext4_xattr_item *item = ext4_rb_entry(
-				node, struct ext4_xattr_item, node);
-		ext4_xattr_item_remove(&xattr_ref->root, item);
+	struct ext4_xattr_item *item, *save_item;
+	RB_FOREACH_SAFE(item,
+			ext4_xattr_tree,
+			&xattr_ref->root,
+			save_item) {
+		RB_REMOVE(ext4_xattr_tree, &xattr_ref->root, item);
 		ext4_xattr_item_free(item);
 	}
+	xattr_ref->ea_size = 0;
 }
 
 int ext4_fs_get_xattr_ref(struct ext4_fs *fs,
@@ -329,7 +281,7 @@
 	uint64_t xattr_block;
 	xattr_block = ext4_inode_get_file_acl(inode_ref->inode,
 					      &fs->sb);
-	memset(&ref->root, 0, sizeof(ref->root));
+	RB_INIT(&ref->root);
 	if (xattr_block) {
 		rc = ext4_block_get(fs->bdev,
 				    &inode_ref->block, xattr_block);
--- /dev/null
+++ b/lwext4/tree.h
@@ -1,0 +1,801 @@
+/*	$NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $	*/
+/*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/
+/* $FreeBSD$ */
+
+/*-
+ * Copyright 2002 Niels Provos <[email protected]>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef	_SYS_TREE_H_
+#define	_SYS_TREE_H_
+
+#include <sys/cdefs.h>
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure.  Every operation
+ * on the tree causes a splay to happen.  The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree.  On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n).  The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute.  It fulfills a set of conditions:
+ *	- every search path from the root to a leaf consists of the
+ *	  same number of black nodes,
+ *	- each red node (except for the root) has a black parent,
+ *	- each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type)						\
+struct name {								\
+	struct type *sph_root; /* root of the tree */			\
+}
+
+#define SPLAY_INITIALIZER(root)						\
+	{ NULL }
+
+#define SPLAY_INIT(root) do {						\
+	(root)->sph_root = NULL;					\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ENTRY(type)						\
+struct {								\
+	struct type *spe_left; /* left element */			\
+	struct type *spe_right; /* right element */			\
+}
+
+#define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
+#define SPLAY_ROOT(head)		(head)->sph_root
+#define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
+	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
+	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
+	(head)->sph_root = tmp;						\
+} while (/*CONSTCOND*/ 0)
+	
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
+	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
+	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
+	(head)->sph_root = tmp;						\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do {				\
+	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
+	tmp = (head)->sph_root;						\
+	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do {				\
+	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
+	tmp = (head)->sph_root;						\
+	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
+} while (/*CONSTCOND*/ 0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
+	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
+	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
+	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp)				\
+void name##_SPLAY(struct name *, struct type *);			\
+void name##_SPLAY_MINMAX(struct name *, int);				\
+struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
+									\
+/* Finds the node with the same key as elm */				\
+static __inline struct type *						\
+name##_SPLAY_FIND(struct name *head, struct type *elm)			\
+{									\
+	if (SPLAY_EMPTY(head))						\
+		return(NULL);						\
+	name##_SPLAY(head, elm);					\
+	if ((cmp)(elm, (head)->sph_root) == 0)				\
+		return (head->sph_root);				\
+	return (NULL);							\
+}									\
+									\
+static __inline struct type *						\
+name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
+{									\
+	name##_SPLAY(head, elm);					\
+	if (SPLAY_RIGHT(elm, field) != NULL) {				\
+		elm = SPLAY_RIGHT(elm, field);				\
+		while (SPLAY_LEFT(elm, field) != NULL) {		\
+			elm = SPLAY_LEFT(elm, field);			\
+		}							\
+	} else								\
+		elm = NULL;						\
+	return (elm);							\
+}									\
+									\
+static __inline struct type *						\
+name##_SPLAY_MIN_MAX(struct name *head, int val)			\
+{									\
+	name##_SPLAY_MINMAX(head, val);					\
+        return (SPLAY_ROOT(head));					\
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp)				\
+struct type *								\
+name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
+{									\
+    if (SPLAY_EMPTY(head)) {						\
+	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
+    } else {								\
+	    int __comp;							\
+	    name##_SPLAY(head, elm);					\
+	    __comp = (cmp)(elm, (head)->sph_root);			\
+	    if(__comp < 0) {						\
+		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
+		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
+	    } else if (__comp > 0) {					\
+		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
+		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
+	    } else							\
+		    return ((head)->sph_root);				\
+    }									\
+    (head)->sph_root = (elm);						\
+    return (NULL);							\
+}									\
+									\
+struct type *								\
+name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
+{									\
+	struct type *__tmp;						\
+	if (SPLAY_EMPTY(head))						\
+		return (NULL);						\
+	name##_SPLAY(head, elm);					\
+	if ((cmp)(elm, (head)->sph_root) == 0) {			\
+		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
+			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+		} else {						\
+			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
+			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+			name##_SPLAY(head, elm);			\
+			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
+		}							\
+		return (elm);						\
+	}								\
+	return (NULL);							\
+}									\
+									\
+void									\
+name##_SPLAY(struct name *head, struct type *elm)			\
+{									\
+	struct type __node, *__left, *__right, *__tmp;			\
+	int __comp;							\
+\
+	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+	__left = __right = &__node;					\
+\
+	while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {		\
+		if (__comp < 0) {					\
+			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if ((cmp)(elm, __tmp) < 0){			\
+				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
+				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKLEFT(head, __right, field);		\
+		} else if (__comp > 0) {				\
+			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if ((cmp)(elm, __tmp) > 0){			\
+				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
+				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKRIGHT(head, __left, field);		\
+		}							\
+	}								\
+	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
+}									\
+									\
+/* Splay with either the minimum or the maximum element			\
+ * Used to find minimum or maximum element in tree.			\
+ */									\
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{									\
+	struct type __node, *__left, *__right, *__tmp;			\
+\
+	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+	__left = __right = &__node;					\
+\
+	while (1) {							\
+		if (__comp < 0) {					\
+			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if (__comp < 0){				\
+				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
+				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKLEFT(head, __right, field);		\
+		} else if (__comp > 0) {				\
+			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
+			if (__tmp == NULL)				\
+				break;					\
+			if (__comp > 0) {				\
+				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
+				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+					break;				\
+			}						\
+			SPLAY_LINKRIGHT(head, __left, field);		\
+		}							\
+	}								\
+	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
+}
+
+#define SPLAY_NEGINF	-1
+#define SPLAY_INF	1
+
+#define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\
+					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\
+					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head)					\
+	for ((x) = SPLAY_MIN(name, head);				\
+	     (x) != NULL;						\
+	     (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type)						\
+struct name {								\
+	struct type *rbh_root; /* root of the tree */			\
+}
+
+#define RB_INITIALIZER(root)						\
+	{ NULL }
+
+#define RB_INIT(root) do {						\
+	(root)->rbh_root = NULL;					\
+} while (/*CONSTCOND*/ 0)
+
+#define RB_BLACK	0
+#define RB_RED		1
+#define RB_ENTRY(type)							\
+struct {								\
+	struct type *rbe_left;		/* left element */		\
+	struct type *rbe_right;		/* right element */		\
+	struct type *rbe_parent;	/* parent element */		\
+	int rbe_color;			/* node color */		\
+}
+
+#define RB_LEFT(elm, field)		(elm)->field.rbe_left
+#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
+#define RB_PARENT(elm, field)		(elm)->field.rbe_parent
+#define RB_COLOR(elm, field)		(elm)->field.rbe_color
+#define RB_ROOT(head)			(head)->rbh_root
+#define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do {					\
+	RB_PARENT(elm, field) = parent;					\
+	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
+	RB_COLOR(elm, field) = RB_RED;					\
+} while (/*CONSTCOND*/ 0)
+
+#define RB_SET_BLACKRED(black, red, field) do {				\
+	RB_COLOR(black, field) = RB_BLACK;				\
+	RB_COLOR(red, field) = RB_RED;					\
+} while (/*CONSTCOND*/ 0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x)	do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
+	(tmp) = RB_RIGHT(elm, field);					\
+	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
+		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
+	}								\
+	RB_AUGMENT(elm);						\
+	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
+		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
+			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
+		else							\
+			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
+	} else								\
+		(head)->rbh_root = (tmp);				\
+	RB_LEFT(tmp, field) = (elm);					\
+	RB_PARENT(elm, field) = (tmp);					\
+	RB_AUGMENT(tmp);						\
+	if ((RB_PARENT(tmp, field)))					\
+		RB_AUGMENT(RB_PARENT(tmp, field));			\
+} while (/*CONSTCOND*/ 0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
+	(tmp) = RB_LEFT(elm, field);					\
+	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
+		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
+	}								\
+	RB_AUGMENT(elm);						\
+	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
+		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
+			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
+		else							\
+			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
+	} else								\
+		(head)->rbh_root = (tmp);				\
+	RB_RIGHT(tmp, field) = (elm);					\
+	RB_PARENT(elm, field) = (tmp);					\
+	RB_AUGMENT(tmp);						\
+	if ((RB_PARENT(tmp, field)))					\
+		RB_AUGMENT(RB_PARENT(tmp, field));			\
+} while (/*CONSTCOND*/ 0)
+
+/* Generates prototypes and inline functions */
+#define	RB_PROTOTYPE(name, type, field, cmp)				\
+	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
+	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
+	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_INSERT(name, type, attr);				\
+	RB_PROTOTYPE_REMOVE(name, type, attr);				\
+	RB_PROTOTYPE_FIND(name, type, attr);				\
+	RB_PROTOTYPE_NFIND(name, type, attr);				\
+	RB_PROTOTYPE_NEXT(name, type, attr);				\
+	RB_PROTOTYPE_PREV(name, type, attr);				\
+	RB_PROTOTYPE_MINMAX(name, type, attr);
+#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\
+	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
+#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
+	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
+#define RB_PROTOTYPE_REMOVE(name, type, attr)				\
+	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT(name, type, attr)				\
+	attr struct type *name##_RB_INSERT(struct name *, struct type *)
+#define RB_PROTOTYPE_FIND(name, type, attr)				\
+	attr struct type *name##_RB_FIND(struct name *, struct type *)
+#define RB_PROTOTYPE_NFIND(name, type, attr)				\
+	attr struct type *name##_RB_NFIND(struct name *, struct type *)
+#define RB_PROTOTYPE_NEXT(name, type, attr)				\
+	attr struct type *name##_RB_NEXT(struct type *)
+#define RB_PROTOTYPE_PREV(name, type, attr)				\
+	attr struct type *name##_RB_PREV(struct type *)
+#define RB_PROTOTYPE_MINMAX(name, type, attr)				\
+	attr struct type *name##_RB_MINMAX(struct name *, int)
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define	RB_GENERATE(name, type, field, cmp)				\
+	RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define	RB_GENERATE_STATIC(name, type, field, cmp)			\
+	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
+	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
+	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
+	RB_GENERATE_REMOVE(name, type, field, attr)			\
+	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
+	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
+	RB_GENERATE_NEXT(name, type, field, attr)			\
+	RB_GENERATE_PREV(name, type, field, attr)			\
+	RB_GENERATE_MINMAX(name, type, field, attr)
+
+#define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
+attr void								\
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+{									\
+	struct type *parent, *gparent, *tmp;				\
+	while ((parent = RB_PARENT(elm, field)) != NULL &&		\
+	    RB_COLOR(parent, field) == RB_RED) {			\
+		gparent = RB_PARENT(parent, field);			\
+		if (parent == RB_LEFT(gparent, field)) {		\
+			tmp = RB_RIGHT(gparent, field);			\
+			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
+				RB_COLOR(tmp, field) = RB_BLACK;	\
+				RB_SET_BLACKRED(parent, gparent, field);\
+				elm = gparent;				\
+				continue;				\
+			}						\
+			if (RB_RIGHT(parent, field) == elm) {		\
+				RB_ROTATE_LEFT(head, parent, tmp, field);\
+				tmp = parent;				\
+				parent = elm;				\
+				elm = tmp;				\
+			}						\
+			RB_SET_BLACKRED(parent, gparent, field);	\
+			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
+		} else {						\
+			tmp = RB_LEFT(gparent, field);			\
+			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
+				RB_COLOR(tmp, field) = RB_BLACK;	\
+				RB_SET_BLACKRED(parent, gparent, field);\
+				elm = gparent;				\
+				continue;				\
+			}						\
+			if (RB_LEFT(parent, field) == elm) {		\
+				RB_ROTATE_RIGHT(head, parent, tmp, field);\
+				tmp = parent;				\
+				parent = elm;				\
+				elm = tmp;				\
+			}						\
+			RB_SET_BLACKRED(parent, gparent, field);	\
+			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
+		}							\
+	}								\
+	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
+}
+
+#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+attr void								\
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{									\
+	struct type *tmp;						\
+	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
+	    elm != RB_ROOT(head)) {					\
+		if (RB_LEFT(parent, field) == elm) {			\
+			tmp = RB_RIGHT(parent, field);			\
+			if (RB_COLOR(tmp, field) == RB_RED) {		\
+				RB_SET_BLACKRED(tmp, parent, field);	\
+				RB_ROTATE_LEFT(head, parent, tmp, field);\
+				tmp = RB_RIGHT(parent, field);		\
+			}						\
+			if ((RB_LEFT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+			    (RB_RIGHT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+				RB_COLOR(tmp, field) = RB_RED;		\
+				elm = parent;				\
+				parent = RB_PARENT(elm, field);		\
+			} else {					\
+				if (RB_RIGHT(tmp, field) == NULL ||	\
+				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
+					struct type *oleft;		\
+					if ((oleft = RB_LEFT(tmp, field)) \
+					    != NULL)			\
+						RB_COLOR(oleft, field) = RB_BLACK;\
+					RB_COLOR(tmp, field) = RB_RED;	\
+					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+					tmp = RB_RIGHT(parent, field);	\
+				}					\
+				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+				RB_COLOR(parent, field) = RB_BLACK;	\
+				if (RB_RIGHT(tmp, field))		\
+					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
+				RB_ROTATE_LEFT(head, parent, tmp, field);\
+				elm = RB_ROOT(head);			\
+				break;					\
+			}						\
+		} else {						\
+			tmp = RB_LEFT(parent, field);			\
+			if (RB_COLOR(tmp, field) == RB_RED) {		\
+				RB_SET_BLACKRED(tmp, parent, field);	\
+				RB_ROTATE_RIGHT(head, parent, tmp, field);\
+				tmp = RB_LEFT(parent, field);		\
+			}						\
+			if ((RB_LEFT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+			    (RB_RIGHT(tmp, field) == NULL ||		\
+			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+				RB_COLOR(tmp, field) = RB_RED;		\
+				elm = parent;				\
+				parent = RB_PARENT(elm, field);		\
+			} else {					\
+				if (RB_LEFT(tmp, field) == NULL ||	\
+				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
+					struct type *oright;		\
+					if ((oright = RB_RIGHT(tmp, field)) \
+					    != NULL)			\
+						RB_COLOR(oright, field) = RB_BLACK;\
+					RB_COLOR(tmp, field) = RB_RED;	\
+					RB_ROTATE_LEFT(head, tmp, oright, field);\
+					tmp = RB_LEFT(parent, field);	\
+				}					\
+				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+				RB_COLOR(parent, field) = RB_BLACK;	\
+				if (RB_LEFT(tmp, field))		\
+					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
+				RB_ROTATE_RIGHT(head, parent, tmp, field);\
+				elm = RB_ROOT(head);			\
+				break;					\
+			}						\
+		}							\
+	}								\
+	if (elm)							\
+		RB_COLOR(elm, field) = RB_BLACK;			\
+}
+
+#define RB_GENERATE_REMOVE(name, type, field, attr)			\
+attr struct type *							\
+name##_RB_REMOVE(struct name *head, struct type *elm)			\
+{									\
+	struct type *child, *parent, *old = elm;			\
+	int color;							\
+	if (RB_LEFT(elm, field) == NULL)				\
+		child = RB_RIGHT(elm, field);				\
+	else if (RB_RIGHT(elm, field) == NULL)				\
+		child = RB_LEFT(elm, field);				\
+	else {								\
+		struct type *left;					\
+		elm = RB_RIGHT(elm, field);				\
+		while ((left = RB_LEFT(elm, field)) != NULL)		\
+			elm = left;					\
+		child = RB_RIGHT(elm, field);				\
+		parent = RB_PARENT(elm, field);				\
+		color = RB_COLOR(elm, field);				\
+		if (child)						\
+			RB_PARENT(child, field) = parent;		\
+		if (parent) {						\
+			if (RB_LEFT(parent, field) == elm)		\
+				RB_LEFT(parent, field) = child;		\
+			else						\
+				RB_RIGHT(parent, field) = child;	\
+			RB_AUGMENT(parent);				\
+		} else							\
+			RB_ROOT(head) = child;				\
+		if (RB_PARENT(elm, field) == old)			\
+			parent = elm;					\
+		(elm)->field = (old)->field;				\
+		if (RB_PARENT(old, field)) {				\
+			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+				RB_LEFT(RB_PARENT(old, field), field) = elm;\
+			else						\
+				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+			RB_AUGMENT(RB_PARENT(old, field));		\
+		} else							\
+			RB_ROOT(head) = elm;				\
+		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
+		if (RB_RIGHT(old, field))				\
+			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
+		if (parent) {						\
+			left = parent;					\
+			do {						\
+				RB_AUGMENT(left);			\
+			} while ((left = RB_PARENT(left, field)) != NULL); \
+		}							\
+		goto color;						\
+	}								\
+	parent = RB_PARENT(elm, field);					\
+	color = RB_COLOR(elm, field);					\
+	if (child)							\
+		RB_PARENT(child, field) = parent;			\
+	if (parent) {							\
+		if (RB_LEFT(parent, field) == elm)			\
+			RB_LEFT(parent, field) = child;			\
+		else							\
+			RB_RIGHT(parent, field) = child;		\
+		RB_AUGMENT(parent);					\
+	} else								\
+		RB_ROOT(head) = child;					\
+color:									\
+	if (color == RB_BLACK)						\
+		name##_RB_REMOVE_COLOR(head, parent, child);		\
+	return (old);							\
+}									\
+
+#define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
+/* Inserts a node into the RB tree */					\
+attr struct type *							\
+name##_RB_INSERT(struct name *head, struct type *elm)			\
+{									\
+	struct type *tmp;						\
+	struct type *parent = NULL;					\
+	int comp = 0;							\
+	tmp = RB_ROOT(head);						\
+	while (tmp) {							\
+		parent = tmp;						\
+		comp = (cmp)(elm, parent);				\
+		if (comp < 0)						\
+			tmp = RB_LEFT(tmp, field);			\
+		else if (comp > 0)					\
+			tmp = RB_RIGHT(tmp, field);			\
+		else							\
+			return (tmp);					\
+	}								\
+	RB_SET(elm, parent, field);					\
+	if (parent != NULL) {						\
+		if (comp < 0)						\
+			RB_LEFT(parent, field) = elm;			\
+		else							\
+			RB_RIGHT(parent, field) = elm;			\
+		RB_AUGMENT(parent);					\
+	} else								\
+		RB_ROOT(head) = elm;					\
+	name##_RB_INSERT_COLOR(head, elm);				\
+	return (NULL);							\
+}
+
+#define RB_GENERATE_FIND(name, type, field, cmp, attr)			\
+/* Finds the node with the same key as elm */				\
+attr struct type *							\
+name##_RB_FIND(struct name *head, struct type *elm)			\
+{									\
+	struct type *tmp = RB_ROOT(head);				\
+	int comp;							\
+	while (tmp) {							\
+		comp = cmp(elm, tmp);					\
+		if (comp < 0)						\
+			tmp = RB_LEFT(tmp, field);			\
+		else if (comp > 0)					\
+			tmp = RB_RIGHT(tmp, field);			\
+		else							\
+			return (tmp);					\
+	}								\
+	return (NULL);							\
+}
+
+#define RB_GENERATE_NFIND(name, type, field, cmp, attr)			\
+/* Finds the first node greater than or equal to the search key */	\
+attr struct type *							\
+name##_RB_NFIND(struct name *head, struct type *elm)			\
+{									\
+	struct type *tmp = RB_ROOT(head);				\
+	struct type *res = NULL;					\
+	int comp;							\
+	while (tmp) {							\
+		comp = cmp(elm, tmp);					\
+		if (comp < 0) {						\
+			res = tmp;					\
+			tmp = RB_LEFT(tmp, field);			\
+		}							\
+		else if (comp > 0)					\
+			tmp = RB_RIGHT(tmp, field);			\
+		else							\
+			return (tmp);					\
+	}								\
+	return (res);							\
+}
+
+#define RB_GENERATE_NEXT(name, type, field, attr)			\
+/* ARGSUSED */								\
+attr struct type *							\
+name##_RB_NEXT(struct type *elm)					\
+{									\
+	if (RB_RIGHT(elm, field)) {					\
+		elm = RB_RIGHT(elm, field);				\
+		while (RB_LEFT(elm, field))				\
+			elm = RB_LEFT(elm, field);			\
+	} else {							\
+		if (RB_PARENT(elm, field) &&				\
+		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
+			elm = RB_PARENT(elm, field);			\
+		else {							\
+			while (RB_PARENT(elm, field) &&			\
+			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+				elm = RB_PARENT(elm, field);		\
+			elm = RB_PARENT(elm, field);			\
+		}							\
+	}								\
+	return (elm);							\
+}
+
+#define RB_GENERATE_PREV(name, type, field, attr)			\
+/* ARGSUSED */								\
+attr struct type *							\
+name##_RB_PREV(struct type *elm)					\
+{									\
+	if (RB_LEFT(elm, field)) {					\
+		elm = RB_LEFT(elm, field);				\
+		while (RB_RIGHT(elm, field))				\
+			elm = RB_RIGHT(elm, field);			\
+	} else {							\
+		if (RB_PARENT(elm, field) &&				\
+		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\
+			elm = RB_PARENT(elm, field);			\
+		else {							\
+			while (RB_PARENT(elm, field) &&			\
+			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+				elm = RB_PARENT(elm, field);		\
+			elm = RB_PARENT(elm, field);			\
+		}							\
+	}								\
+	return (elm);							\
+}
+
+#define RB_GENERATE_MINMAX(name, type, field, attr)			\
+attr struct type *							\
+name##_RB_MINMAX(struct name *head, int val)				\
+{									\
+	struct type *tmp = RB_ROOT(head);				\
+	struct type *parent = NULL;					\
+	while (tmp) {							\
+		parent = tmp;						\
+		if (val < 0)						\
+			tmp = RB_LEFT(tmp, field);			\
+		else							\
+			tmp = RB_RIGHT(tmp, field);			\
+	}								\
+	return (parent);						\
+}
+
+#define RB_NEGINF	-1
+#define RB_INF	1
+
+#define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y)	name##_RB_NEXT(y)
+#define RB_PREV(name, x, y)	name##_RB_PREV(y)
+#define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head)					\
+	for ((x) = RB_MIN(name, head);					\
+	     (x) != NULL;						\
+	     (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_FROM(x, name, y)					\
+	for ((x) = (y);							\
+	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
+	     (x) = (y))
+
+#define RB_FOREACH_SAFE(x, name, head, y)				\
+	for ((x) = RB_MIN(name, head);					\
+	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
+	     (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head)				\
+	for ((x) = RB_MAX(name, head);					\
+	     (x) != NULL;						\
+	     (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_FROM(x, name, y)				\
+	for ((x) = (y);							\
+	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
+	     (x) = (y))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
+	for ((x) = RB_MAX(name, head);					\
+	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
+	     (x) = (y))
+
+#endif	/* _SYS_TREE_H_ */