JFFS2: Use RTEMS red-black tree implementation

3 files changed, 112 insertions, 453 deletions

diff --git a/cpukit/libfs/Makefile.am b/cpukit/libfs/Makefile.am
index 678234b52e..7fccc2e11b 100644
--- a/cpukit/libfs/Makefile.am
+++ b/cpukit/libfs/Makefile.am
@@ -113,7 +113,6 @@ project_lib_LIBRARIES = libjffs2.a
 libjffs2_a_SOURCES =
 libjffs2_a_SOURCES += src/jffs2/src/build.c
 libjffs2_a_SOURCES += src/jffs2/src/compat-crc32.c
-libjffs2_a_SOURCES += src/jffs2/src/compat-rbtree.c
 libjffs2_a_SOURCES += src/jffs2/src/compr.c
 libjffs2_a_SOURCES += src/jffs2/src/compr_rtime.c
 libjffs2_a_SOURCES += src/jffs2/src/compr_zlib.c
diff --git a/cpukit/libfs/src/jffs2/include/linux/rbtree.h b/cpukit/libfs/src/jffs2/include/linux/rbtree.h
index 73cf937044..bbf285377a 100644
--- a/cpukit/libfs/src/jffs2/include/linux/rbtree.h
+++ b/cpukit/libfs/src/jffs2/include/linux/rbtree.h
@@ -1,50 +1,132 @@
-#ifndef	_LINUX_RBTREE_H
-#define	_LINUX_RBTREE_H
+/*
+ * Copyright (c) 2015 embedded brains GmbH.  All rights reserved.
+ *
+ *  embedded brains GmbH
+ *  Dornierstr. 4
+ *  82178 Puchheim
+ *  Germany
+ *  <rtems@embedded-brains.de>
+ *
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.org/license/LICENSE.
+ */
 
-#include <stddef.h>
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+#include <rtems/score/rbtree.h>
 
 struct rb_node {
-	struct rb_node *rb_left;
-	struct rb_node *rb_right;
-	struct rb_node *rb_parent;
-	int rb_color;
+  struct rb_node *rb_left;
+  struct rb_node *rb_right;
+  struct rb_node *rb_parent;
+  int rb_color;
 };
 
+RTEMS_STATIC_ASSERT(
+  sizeof( struct rb_node ) == sizeof( RBTree_Node ),
+  rb_node_size
+);
+
+RTEMS_STATIC_ASSERT(
+  offsetof( struct rb_node, rb_left ) == offsetof( RBTree_Node, Node.rbe_left ),
+  rb_node_left
+);
+
+RTEMS_STATIC_ASSERT(
+  offsetof( struct rb_node, rb_right ) == offsetof( RBTree_Node, Node.rbe_right ),
+  rb_node_right
+);
+
+RTEMS_STATIC_ASSERT(
+  offsetof( struct rb_node, rb_parent ) == offsetof( RBTree_Node, Node.rbe_parent ),
+  rb_node_parent
+);
+
+RTEMS_STATIC_ASSERT(
+  offsetof( struct rb_node, rb_color ) == offsetof( RBTree_Node, Node.rbe_color ),
+  rb_node_color
+);
+
 struct rb_root {
-	struct rb_node *rb_node;
+  struct rb_node *rb_node;
 };
-#define RB_ROOT ((struct rb_root){0})
-#define rb_entry(p, container, field)		\
-	((container *) ((char *)p - offsetof(container, field)))
 
-#define RB_BLACK	0
-#define RB_RED		1
+RTEMS_STATIC_ASSERT(
+  sizeof( struct rb_root ) == sizeof( RBTree_Control ),
+  rb_root_size
+);
 
+RTEMS_STATIC_ASSERT(
+  offsetof( struct rb_root, rb_node ) == offsetof( RBTree_Control, rbh_root ),
+  rb_root_node
+);
 
-extern void rb_insert_color(struct rb_node *, struct rb_root *);
-extern void rb_erase(struct rb_node *, struct rb_root *);
+#undef RB_ROOT
+#define RB_ROOT ( (struct rb_root) { NULL } )
 
-extern struct rb_node *rb_next(struct rb_node *);
-extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
-extern struct rb_node *rb_last(struct rb_root *);
+#define rb_entry( p, container, field ) RTEMS_CONTAINER_OF( p, container, field )
 
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
-			    struct rb_root *root);
+static inline void rb_insert_color( struct rb_node *node, struct rb_root *root)
+{
+  _RBTree_Insert_color( (RBTree_Control *) root, (RBTree_Node *) node );
+}
+
+static inline void rb_erase( struct rb_node *node, struct rb_root *root )
+{
+  _RBTree_Extract( (RBTree_Control *) root, (RBTree_Node *) node );
+}
 
-static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
-				struct rb_node ** rb_link)
+static inline struct rb_node *rb_next( struct rb_node *node )
 {
-	node->rb_parent = parent;
-	node->rb_color = RB_RED;
-	node->rb_left = node->rb_right = NULL;
+  return (struct rb_node *) _RBTree_Successor( (RBTree_Node *) node );
+}
 
-	*rb_link = node;
+static inline struct rb_node *rb_prev( struct rb_node *node )
+{
+  return (struct rb_node *) _RBTree_Predecessor( (RBTree_Node *) node );
+}
+
+static inline struct rb_node *rb_first( struct rb_root *root )
+{
+  return (struct rb_node *) _RBTree_Minimum( (RBTree_Control *) root );
+}
+
+static inline struct rb_node *rb_last( struct rb_root *root )
+{
+  return (struct rb_node *) _RBTree_Maximum( (RBTree_Control *) root );
+}
+
+static inline void rb_replace_node(
+  struct rb_node *victim,
+  struct rb_node *replacement, 
+  struct rb_root *root
+)
+{
+  _RBTree_Replace_node(
+    (RBTree_Control *) root,
+    (RBTree_Node *) victim,
+    (RBTree_Node *) replacement
+  );
+}
+
+static inline void rb_link_node(
+  struct rb_node *node,
+  struct rb_node *parent,
+  struct rb_node **link
+)
+{
+  _RBTree_Add_child(
+    (RBTree_Node *) node,
+    (RBTree_Node *) parent,
+    (RBTree_Node **) link
+  );
 }
 
-static inline struct rb_node *rb_parent(struct rb_node * node)
+static inline struct rb_node *rb_parent( struct rb_node *node )
 {
-	return node->rb_parent;
+  return (struct rb_node *) _RBTree_Parent( (RBTree_Node *) node );
 }
 
-#endif	/* _LINUX_RBTREE_H */
+#endif /* _LINUX_RBTREE_H */
diff --git a/cpukit/libfs/src/jffs2/src/compat-rbtree.c b/cpukit/libfs/src/jffs2/src/compat-rbtree.c
deleted file mode 100644
index a73cdc256c..0000000000
--- a/cpukit/libfs/src/jffs2/src/compat-rbtree.c
+++ /dev/null
@@ -1,422 +0,0 @@
-/*========================================================================
-//
-//      rbtree.c
-//
-//      Red Black tree implementation
-//
-//========================================================================
-// ####ECOSGPLCOPYRIGHTBEGIN####                                            
-// -------------------------------------------                              
-// This file is part of eCos, the Embedded Configurable Operating System.   
-// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
-//
-// eCos 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 or (at your option) any later      
-// version.                                                                 
-//
-// eCos 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 eCos; if not, write to the Free Software Foundation, Inc.,    
-// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            
-//
-// As a special exception, if other files instantiate templates or use      
-// macros or inline functions from this file, or you compile this file      
-// and link it with other works to produce a work based on this file,       
-// this file does not by itself cause the resulting work to be covered by   
-// the GNU General Public License. However the source code for this file    
-// must still be made available in accordance with section (3) of the GNU   
-// General Public License v2.                                               
-//
-// This exception does not invalidate any other reasons why a work based    
-// on this file might be covered by the GNU General Public License.         
-// -------------------------------------------                              
-// ####ECOSGPLCOPYRIGHTEND####                                              
-//========================================================================
-//#####DESCRIPTIONBEGIN####
-//
-// Author(s):     Niels Provos/OpenBSD
-// Contributors:  dwmw2
-// Date:          2003-01-21
-// Purpose:       This file provides an implementation of red-black trees.
-// Description:   Derived from OpenBSD src/sys/sys/tree.h
-// Usage:         
-//
-//####DESCRIPTIONEND####
-//
-//======================================================================
-*/
-
-/*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/
-/*
- * Copyright 2002 Niels Provos <provos@citi.umich.edu>
- * 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.
- */
-
-/* Fields renamed to match Linux ones. */
-#include <linux/rbtree.h>
-
-
-#define RB_HEAD(head)		(head)->rb_node
-#define RB_LEFT(elm)		(elm)->rb_left
-#define RB_RIGHT(elm)		(elm)->rb_right
-#define RB_PARENT(elm)		(elm)->rb_parent
-#define RB_COLOR(elm)		(elm)->rb_color
-
-
-#define RB_SET(elm, parent) do {				\
-	RB_PARENT(elm) = parent;				\
-	RB_LEFT(elm) = RB_RIGHT(elm) = NULL;	\
-	RB_COLOR(elm) = RB_RED;				\
-} while (0)
-
-#define RB_SET_BLACKRED(black, red) do {			\
-	RB_COLOR(black) = RB_BLACK;				\
-	RB_COLOR(red) = RB_RED;					\
-} while (0)
-
-#ifndef RB_AUGMENT
-#define RB_AUGMENT(x)
-#endif
-
-#define RB_ROTATE_LEFT(head, elm, tmp) do {			\
-	(tmp) = RB_RIGHT(elm);					\
-	if ((RB_RIGHT(elm) = RB_LEFT(tmp))) {			\
-		RB_PARENT(RB_LEFT(tmp)) = (elm);		\
-	}							\
-	RB_AUGMENT(elm);					\
-	if ((RB_PARENT(tmp) = RB_PARENT(elm))) {		\
-		if ((elm) == RB_LEFT(RB_PARENT(elm)))		\
-			RB_LEFT(RB_PARENT(elm)) = (tmp);	\
-		else						\
-			RB_RIGHT(RB_PARENT(elm)) = (tmp);	\
-	} else							\
-		(head)->rb_node = (tmp);			\
-	RB_LEFT(tmp) = (elm);					\
-	RB_PARENT(elm) = (tmp);					\
-	RB_AUGMENT(tmp);					\
-	if ((RB_PARENT(tmp))) {					\
-		RB_AUGMENT(RB_PARENT(tmp));			\
-	}							\
-} while (0)
-
-#define RB_ROTATE_RIGHT(head, elm, tmp) do {			\
-	(tmp) = RB_LEFT(elm);					\
-	if ((RB_LEFT(elm) = RB_RIGHT(tmp))) {			\
-		RB_PARENT(RB_RIGHT(tmp)) = (elm);		\
-	}							\
-	RB_AUGMENT(elm);					\
-	if ((RB_PARENT(tmp) = RB_PARENT(elm))) {		\
-		if ((elm) == RB_LEFT(RB_PARENT(elm)))		\
-			RB_LEFT(RB_PARENT(elm)) = (tmp);	\
-		else						\
-			RB_RIGHT(RB_PARENT(elm)) = (tmp);	\
-	} else							\
-		(head)->rb_node = (tmp);			\
-	RB_RIGHT(tmp) = (elm);					\
-	RB_PARENT(elm) = (tmp);					\
-	RB_AUGMENT(tmp);					\
-	if ((RB_PARENT(tmp))) {					\
-		RB_AUGMENT(RB_PARENT(tmp));			\
-	}							\
-} while(0)
-
-/* Note args swapped to match Linux */
-void rb_insert_color(struct rb_node *elm, struct rb_root *head)
-{
-	struct rb_node *parent, *gparent, *tmp;
-	while ((parent = RB_PARENT(elm)) &&
-	    RB_COLOR(parent) == RB_RED) {
-		gparent = RB_PARENT(parent);
-		if (parent == RB_LEFT(gparent)) {
-			tmp = RB_RIGHT(gparent);
-			if (tmp && RB_COLOR(tmp) == RB_RED) {
-				RB_COLOR(tmp) = RB_BLACK;
-				RB_SET_BLACKRED(parent, gparent);
-				elm = gparent;
-				continue;
-			}
-			if (RB_RIGHT(parent) == elm) {
-				RB_ROTATE_LEFT(head, parent, tmp);
-				tmp = parent;
-				parent = elm;
-				elm = tmp;
-			}
-			RB_SET_BLACKRED(parent, gparent);
-			RB_ROTATE_RIGHT(head, gparent, tmp);
-		} else {
-			tmp = RB_LEFT(gparent);
-			if (tmp && RB_COLOR(tmp) == RB_RED) {
-				RB_COLOR(tmp) = RB_BLACK;
-				RB_SET_BLACKRED(parent, gparent);
-				elm = gparent;
-				continue;
-			}
-			if (RB_LEFT(parent) == elm) {
-				RB_ROTATE_RIGHT(head, parent, tmp);
-				tmp = parent;
-				parent = elm;
-				elm = tmp;
-			}
-			RB_SET_BLACKRED(parent, gparent);
-			RB_ROTATE_LEFT(head, gparent, tmp);
-		}
-	}
-	RB_COLOR(head->rb_node) = RB_BLACK;
-}
-
-
-static void rb_remove_color(struct rb_root *head, struct rb_node *parent,
-			    struct rb_node *elm)
-{
-	struct rb_node *tmp;
-	while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
-	    elm != RB_HEAD(head)) {
-		if (RB_LEFT(parent) == elm) {
-			tmp = RB_RIGHT(parent);
-			if (RB_COLOR(tmp) == RB_RED) {
-				RB_SET_BLACKRED(tmp, parent);
-				RB_ROTATE_LEFT(head, parent, tmp);
-				tmp = RB_RIGHT(parent);
-			}
-			if ((RB_LEFT(tmp) == NULL ||
-			    RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
-			    (RB_RIGHT(tmp) == NULL ||
-			    RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
-				RB_COLOR(tmp) = RB_RED;
-				elm = parent;
-				parent = RB_PARENT(elm);
-			} else {
-				if (RB_RIGHT(tmp) == NULL ||
-				    RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
-					struct rb_node *oleft;
-					if ((oleft = RB_LEFT(tmp)))
-						RB_COLOR(oleft) = RB_BLACK;
-					RB_COLOR(tmp) = RB_RED;
-					RB_ROTATE_RIGHT(head, tmp, oleft);
-					tmp = RB_RIGHT(parent);
-				}
-				RB_COLOR(tmp) = RB_COLOR(parent);
-				RB_COLOR(parent) = RB_BLACK;
-				if (RB_RIGHT(tmp))
-					RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
-				RB_ROTATE_LEFT(head, parent, tmp);
-				elm = RB_HEAD(head);
-				break;
-			}
-		} else {
-			tmp = RB_LEFT(parent);
-			if (RB_COLOR(tmp) == RB_RED) {
-				RB_SET_BLACKRED(tmp, parent);
-				RB_ROTATE_RIGHT(head, parent, tmp);
-				tmp = RB_LEFT(parent);
-			}
-			if ((RB_LEFT(tmp) == NULL ||
-			    RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
-			    (RB_RIGHT(tmp) == NULL ||
-			    RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
-				RB_COLOR(tmp) = RB_RED;
-				elm = parent;
-				parent = RB_PARENT(elm);
-			} else {
-				if (RB_LEFT(tmp) == NULL ||
-				    RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
-					struct rb_node *oright;
-					if ((oright = RB_RIGHT(tmp)))
-						RB_COLOR(oright) = RB_BLACK;
-					RB_COLOR(tmp) = RB_RED;
-					RB_ROTATE_LEFT(head, tmp, oright);
-					tmp = RB_LEFT(parent);
-				}
-				RB_COLOR(tmp) = RB_COLOR(parent);
-				RB_COLOR(parent) = RB_BLACK;
-				if (RB_LEFT(tmp))
-					RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
-				RB_ROTATE_RIGHT(head, parent, tmp);
-				elm = RB_HEAD(head);
-				break;
-			}
-		}
-	}
-	if (elm)
-		RB_COLOR(elm) = RB_BLACK;
-}
-
-/* Note name changed. Guess why :) */
-void rb_erase(struct rb_node *elm, struct rb_root *head)
-{
-	struct rb_node *child, *parent, *old = elm;
-	int color;
-	if (RB_LEFT(elm) == NULL)
-		child = RB_RIGHT(elm);
-	else if (RB_RIGHT(elm) == NULL)
-		child = RB_LEFT(elm);
-	else {
-		struct rb_node *left;
-		elm = RB_RIGHT(elm);
-		while ((left = RB_LEFT(elm)))
-			elm = left;
-		child = RB_RIGHT(elm);
-		parent = RB_PARENT(elm);
-		color = RB_COLOR(elm);
-		if (child)
-			RB_PARENT(child) = parent;
-		if (parent) {
-			if (RB_LEFT(parent) == elm)
-				RB_LEFT(parent) = child;
-			else
-				RB_RIGHT(parent) = child;
-			RB_AUGMENT(parent);
-		} else
-			RB_HEAD(head) = child;
-		if (RB_PARENT(elm) == old)
-			parent = elm;
-		*(elm) = *(old);
-		if (RB_PARENT(old)) {
-			if (RB_LEFT(RB_PARENT(old)) == old)
-				RB_LEFT(RB_PARENT(old)) = elm;
-			else
-				RB_RIGHT(RB_PARENT(old)) = elm;
-			RB_AUGMENT(RB_PARENT(old));
-		} else
-			RB_HEAD(head) = elm;
-		RB_PARENT(RB_LEFT(old)) = elm;
-		if (RB_RIGHT(old))
-			RB_PARENT(RB_RIGHT(old)) = elm;
-		if (parent) {
-			left = parent;
-			do {
-				RB_AUGMENT(left);
-			} while ((left = RB_PARENT(left)));
-		}
-		goto color;
-	}
-	parent = RB_PARENT(elm);
-	color = RB_COLOR(elm);
-	if (child)
-		RB_PARENT(child) = parent;
-	if (parent) {
-		if (RB_LEFT(parent) == elm)
-			RB_LEFT(parent) = child;
-		else
-			RB_RIGHT(parent) = child;
-		RB_AUGMENT(parent);
-	} else
-		RB_HEAD(head) = child;
-color:
-	if (color == RB_BLACK)
-		rb_remove_color(head, parent, child);
-}
-
-struct rb_node *rb_next(struct rb_node *elm)
-{
-	if (RB_RIGHT(elm)) {
-		elm = RB_RIGHT(elm);
-		while (RB_LEFT(elm))
-			elm = RB_LEFT(elm);
-	} else {
-		if (RB_PARENT(elm) &&
-		    (elm == RB_LEFT(RB_PARENT(elm))))
-			elm = RB_PARENT(elm);
-		else {
-			while (RB_PARENT(elm) &&
-			    (elm == RB_RIGHT(RB_PARENT(elm))))
-				elm = RB_PARENT(elm);
-			elm = RB_PARENT(elm);
-		}
-	}
-	return (elm);
-}
-
-struct rb_node *rb_prev(struct rb_node *elm)
-{
-	if (RB_LEFT(elm)) {
-		elm = RB_LEFT(elm);
-		while (RB_RIGHT(elm))
-			elm = RB_RIGHT(elm);
-	} else {
-		if (RB_PARENT(elm) &&
-		    (elm == RB_RIGHT(RB_PARENT(elm))))
-			elm = RB_PARENT(elm);
-		else {
-			while (RB_PARENT(elm) &&
-			    (elm == RB_LEFT(RB_PARENT(elm))))
-				elm = RB_PARENT(elm);
-			elm = RB_PARENT(elm);
-		}
-	}
-	return (elm);
-}
-
-/* These ones are lifted from Linux -- but that's OK because I
-   wrote them. dwmw2. */
-struct rb_node *rb_first(struct rb_root *root)
-{
-        struct rb_node  *n;
-
-        n = root->rb_node;
-        if (!n)
-                return 0;
-        while (n->rb_left)
-                n = n->rb_left;
-        return n;
-}
-
-struct rb_node *rb_last(struct rb_root *root)
-{
-	struct rb_node	*n;
-
-	n = root->rb_node;
-	if (!n)
-		return 0;
-	while (n->rb_right)
-		n = n->rb_right;
-	return n;
-}
-
-void rb_replace_node(struct rb_node *victim, struct rb_node *new,
-                     struct rb_root *root)
-{
-        struct rb_node *parent = victim->rb_parent;
-
-        /* 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)
-                victim->rb_left->rb_parent = new;
-        if (victim->rb_right)
-                victim->rb_right->rb_parent = new;
-
-        /* Copy the pointers/colour from the victim to the replacement */
-        *new = *victim;
-}