[PATCH 3/3] JFFS2: Use RTEMS red-black tree implementation
Sebastian Huber
sebastian.huber at embedded-brains.de
Mon Aug 31 11:55:00 UTC 2015
---
cpukit/libfs/Makefile.am | 1 -
cpukit/libfs/src/jffs2/include/linux/rbtree.h | 128 ++++++--
cpukit/libfs/src/jffs2/src/compat-rbtree.c | 422 --------------------------
3 files changed, 98 insertions(+), 453 deletions(-)
delete mode 100644 cpukit/libfs/src/jffs2/src/compat-rbtree.c
diff --git a/cpukit/libfs/Makefile.am b/cpukit/libfs/Makefile.am
index 678234b..7fccc2e 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 73cf937..17d93f0 100644
--- a/cpukit/libfs/src/jffs2/include/linux/rbtree.h
+++ b/cpukit/libfs/src/jffs2/include/linux/rbtree.h
@@ -1,50 +1,118 @@
-#ifndef _LINUX_RBTREE_H
-#define _LINUX_RBTREE_H
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
-#include <stddef.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
+);
+
+#undef RB_ROOT
+#define RB_ROOT ( (struct rb_root) { NULL } )
+
+#define rb_entry( p, container, field ) RTEMS_CONTAINER_OF( p, container, field )
+
+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 struct rb_node *rb_next( struct rb_node *node )
+{
+ return (struct rb_node *) _RBTree_Successor( (RBTree_Node *) node );
+}
-extern void rb_insert_color(struct rb_node *, struct rb_root *);
-extern void rb_erase(struct rb_node *, struct rb_root *);
+static inline struct rb_node *rb_prev( struct rb_node *node )
+{
+ return (struct rb_node *) _RBTree_Predecessor( (RBTree_Node *) node );
+}
-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 *);
+static inline struct rb_node *rb_first( struct rb_root *root )
+{
+ return (struct rb_node *) _RBTree_Minimum( (RBTree_Control *) root );
+}
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *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_link_node(struct rb_node * node, struct rb_node * parent,
- struct rb_node ** rb_link)
+static inline void rb_replace_node(
+ struct rb_node *victim,
+ struct rb_node *replacement,
+ struct rb_root *root
+)
{
- node->rb_parent = parent;
- node->rb_color = RB_RED;
- node->rb_left = node->rb_right = NULL;
+ _RBTree_Replace_node(
+ (RBTree_Control *) root,
+ (RBTree_Node *) victim,
+ (RBTree_Node *) replacement
+ );
+}
- *rb_link = node;
+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 a73cdc2..0000000
--- 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 at 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;
-}
--
1.8.4.5
More information about the devel
mailing list