[rtems commit] score: Create rbtree implementation header
Sebastian Huber
sebh at rtems.org
Tue Jul 23 13:09:29 UTC 2013
Module: rtems
Branch: master
Commit: 93fb3cb059d8f232b57fccebafa65311b94d9da7
Changeset: http://git.rtems.org/rtems/commit/?id=93fb3cb059d8f232b57fccebafa65311b94d9da7
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Tue Jul 23 10:38:11 2013 +0200
score: Create rbtree implementation header
Move implementation specific parts of rbtree.h and rbtree.inl into new
header file rbtreeimpl.h. The rbtree.h contains now only the
application visible API.
---
cpukit/score/Makefile.am | 2 +-
cpukit/score/include/rtems/score/rbtree.h | 360 ++++++++++++++++--
cpukit/score/include/rtems/score/rbtreeimpl.h | 217 +++++++++++
cpukit/score/inline/rtems/score/rbtree.inl | 507 -------------------------
cpukit/score/preinstall.am | 8 +-
cpukit/score/src/rbtreeextract.c | 4 +-
cpukit/score/src/rbtreefind.c | 4 +-
cpukit/score/src/rbtreeget.c | 4 +-
cpukit/score/src/rbtreeinsert.c | 4 +-
cpukit/score/src/rbtreeiterate.c | 2 +-
cpukit/score/src/rbtreenext.c | 2 +-
testsuites/libtests/rbheap01/init.c | 1 +
testsuites/sptests/sprbtree01/init.c | 2 +-
13 files changed, 555 insertions(+), 562 deletions(-)
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index cb5628a..c2ea6bf 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -40,6 +40,7 @@ include_rtems_score_HEADERS += include/rtems/score/percpu.h
include_rtems_score_HEADERS += include/rtems/score/priority.h
include_rtems_score_HEADERS += include/rtems/score/prioritybitmap.h
include_rtems_score_HEADERS += include/rtems/score/rbtree.h
+include_rtems_score_HEADERS += include/rtems/score/rbtreeimpl.h
include_rtems_score_HEADERS += include/rtems/score/scheduler.h
include_rtems_score_HEADERS += include/rtems/score/schedulercbs.h
include_rtems_score_HEADERS += include/rtems/score/scheduleredf.h
@@ -96,7 +97,6 @@ include_rtems_score_HEADERS += inline/rtems/score/heap.inl
include_rtems_score_HEADERS += inline/rtems/score/object.inl
include_rtems_score_HEADERS += inline/rtems/score/priority.inl
include_rtems_score_HEADERS += inline/rtems/score/prioritybitmap.inl
-include_rtems_score_HEADERS += inline/rtems/score/rbtree.inl
include_rtems_score_HEADERS += inline/rtems/score/scheduler.inl
include_rtems_score_HEADERS += inline/rtems/score/schedulerpriority.inl
include_rtems_score_HEADERS += inline/rtems/score/schedulersimple.inl
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 55b5c55..1414bdf 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -20,6 +20,12 @@
#include <stddef.h>
+#include <rtems/score/address.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
/**
* @defgroup ScoreRBTree Red-Black Tree Handler
*
@@ -33,12 +39,6 @@
*/
/**@{*/
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#include <rtems/score/address.h>
-
/**
* @typedef RBTree_Node
*
@@ -363,47 +363,337 @@ RBTree_Node *_RBTree_Next(
);
/**
- * @brief Red-black tree visitor.
+ * @brief Set off RBtree.
*
- * @param[in] node The node.
- * @param[in] dir The direction.
- * @param[in] visitor_arg The visitor argument.
+ * This function sets the parent and child fields of the @a node to NULL
+ * indicating the @a node is not part of a rbtree.
*
- * @retval true Stop the iteration.
- * @retval false Continue the iteration.
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
+ RBTree_Node *node
+ )
+{
+ node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
+}
+
+/**
+ * @brief Is the node off RBTree.
*
- * @see _RBTree_Iterate_unprotected().
+ * This function returns true if the @a node is not on a rbtree. A @a node is
+ * off rbtree if the parent and child fields are set to NULL.
*/
-typedef bool (*RBTree_Visitor)(
- const RBTree_Node *node,
- RBTree_Direction dir,
- void *visitor_arg
-);
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
+ const RBTree_Node *node
+ )
+{
+ return (node->parent == NULL) &&
+ (node->child[RBT_LEFT] == NULL) &&
+ (node->child[RBT_RIGHT] == NULL);
+}
/**
- * @brief Red-black tree iteration.
+ * @brief Are two Nodes equal.
*
- * @param[in] rbtree The red-black tree.
- * @param[in] dir The direction.
- * @param[in] visitor The visitor.
- * @param[in] visitor_arg The visitor argument.
- */
-void _RBTree_Iterate_unprotected(
- const RBTree_Control *rbtree,
- RBTree_Direction dir,
- RBTree_Visitor visitor,
- void *visitor_arg
-);
+ * This function returns true if @a left and @a right are equal,
+ * and false otherwise.
+ *
+ * @retval true @a left and @a right are equal.
+ * @retval false @a left and @a right are not equal.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
+ const RBTree_Node *left,
+ const RBTree_Node *right
+ )
+{
+ return left == right;
+}
-#ifndef __RTEMS_APPLICATION__
-#include <rtems/score/rbtree.inl>
-#endif
+/**
+ * @brief Is the RBTree node pointer NUL.
+ *
+ * This function returns true if @a the_node is NULL and false otherwise.
+ *
+ * @retval true @a the_node is @c NULL.
+ * @retval false @a the_node is not @c NULL.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node(
+ const RBTree_Node *the_node
+ )
+{
+ return (the_node == NULL);
+}
-#ifdef __cplusplus
+/**
+ * @brief Return pointer to RBTree's root node.
+ *
+ * This function returns a pointer to the root node of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
+ const RBTree_Control *the_rbtree
+)
+{
+ return the_rbtree->root;
+}
+
+/**
+ * @brief Return pointer to RBTree's first node.
+ *
+ * This function returns a pointer to the first node on @a the_rbtree,
+ * where @a dir specifies whether to return the minimum (0) or maximum (1).
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
+ const RBTree_Control *the_rbtree,
+ RBTree_Direction dir
+)
+{
+ return the_rbtree->first[dir];
+}
+
+/**
+ * @brief Return pointer to the parent of this node.
+ *
+ * This function returns a pointer to the parent node of @a the_node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
+ const RBTree_Node *the_node
+)
+{
+ if (!the_node->parent->parent) return NULL;
+ return the_node->parent;
+}
+
+/**
+ * @brief Return pointer to the left of this node.
+ *
+ * This function returns a pointer to the left node of this node.
+ *
+ * @param[in] the_node is the node to be operated upon.
+ *
+ * @return This method returns the left node on the rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
+ const RBTree_Node *the_node
+)
+{
+ return the_node->child[RBT_LEFT];
+}
+
+/**
+ * @brief Return pointer to the right of this node.
+ *
+ * This function returns a pointer to the right node of this node.
+ *
+ * @param[in] the_node is the node to be operated upon.
+ *
+ * @return This method returns the right node on the rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
+ const RBTree_Node *the_node
+)
+{
+ return the_node->child[RBT_RIGHT];
+}
+
+/**
+ * @brief Is the RBTree empty.
+ *
+ * This function returns true if there are no nodes on @a the_rbtree and
+ * false otherwise.
+ *
+ * @param[in] the_rbtree is the rbtree to be operated upon.
+ *
+ * @retval true There are no nodes on @a the_rbtree.
+ * @retval false There are nodes on @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
+ const RBTree_Control *the_rbtree
+)
+{
+ return (the_rbtree->root == NULL);
+}
+
+/**
+ * @brief Is this the first node on the RBTree.
+ *
+ * This function returns true if @a the_node is the first node on
+ * @a the_rbtree and false otherwise. @a dir specifies whether first means
+ * minimum (0) or maximum (1).
+ *
+ * @retval true @a the_node is the first node on @a the_rbtree.
+ * @retval false @a the_node is not the first node on @a the_rbtree.
+ *
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
+ const RBTree_Control *the_rbtree,
+ const RBTree_Node *the_node,
+ RBTree_Direction dir
+)
+{
+ return (the_node == _RBTree_First(the_rbtree, dir));
+}
+
+/**
+ * @brief Does this RBTree have only one node.
+ *
+ * This function returns true if there is only one node on @a the_rbtree and
+ * false otherwise.
+ *
+ * @retval true @a the_rbtree has only one node.
+ * @retval false @a the_rbtree has more than one nodes.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node(
+ const RBTree_Control *the_rbtree
+ )
+{
+ if(!the_rbtree) return false; /* TODO: expected behavior? */
+ return (the_rbtree->root->child[RBT_LEFT] == NULL &&
+ the_rbtree->root->child[RBT_RIGHT] == NULL);
+}
+
+/**
+ * @brief Is this node the RBTree root.
+ *
+ * This function returns true if @a the_node is the root of @a the_rbtree and
+ * false otherwise.
+ *
+ * @retval true @a the_node is the root of @a the_rbtree.
+ * @retval false @a the_node is not the root of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
+ const RBTree_Control *the_rbtree,
+ const RBTree_Node *the_node
+)
+{
+ return (the_node == _RBTree_Root(the_rbtree));
+}
+
+/**
+ * @brief Find the RBTree_Control header given a node in the tree.
+ *
+ * This function returns a pointer to the header of the Red Black
+ * Tree containing @a the_node if it exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
+ RBTree_Node *the_node
+ )
+{
+ if(!the_node) return NULL;
+ if(!(the_node->parent)) return NULL;
+ while(the_node->parent) the_node = the_node->parent;
+ return (RBTree_Control*)the_node;
+}
+
+/**
+ * @brief Initialize this RBTree as empty.
+ *
+ * This routine initializes @a the_rbtree to contain zero nodes.
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
+ RBTree_Control *the_rbtree,
+ RBTree_Compare_function compare_function,
+ bool is_unique
+ )
+{
+ the_rbtree->permanent_null = NULL;
+ the_rbtree->root = NULL;
+ the_rbtree->first[0] = NULL;
+ the_rbtree->first[1] = NULL;
+ the_rbtree->compare_function = compare_function;
+ the_rbtree->is_unique = is_unique;
+}
+
+/**
+ * @brief Returns the predecessor of a node.
+ *
+ * @param[in] node is the node.
+ *
+ * @retval NULL The predecessor does not exist. Otherwise it returns
+ * the predecessor node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
+ const RBTree_Node *node
+)
+{
+ return _RBTree_Next_unprotected( node, RBT_LEFT );
+}
+
+/**
+ * @copydoc _RBTree_Predecessor_unprotected()
+ *
+ * The function disables the interrupts protect the operation.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
+ const RBTree_Node *node
+)
+{
+ return _RBTree_Next( node, RBT_LEFT );
+}
+
+/**
+ * @brief Returns the successor of a node.
+ *
+ * @param[in] node is the node.
+ *
+ * @retval NULL The successor does not exist. Otherwise the successor node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
+ const RBTree_Node *node
+)
+{
+ return _RBTree_Next_unprotected( node, RBT_RIGHT );
+}
+
+/**
+ * @copydoc _RBTree_Successor_unprotected()
+ *
+ * The function disables the interrupts protect the operation.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
+ const RBTree_Node *node
+)
+{
+ return _RBTree_Next( node, RBT_RIGHT );
+}
+
+/**
+ * @brief Get the first node (unprotected).
+ *
+ * This function removes the minimum or maximum node from the_rbtree and
+ * returns a pointer to that node. It does NOT disable interrupts to ensure
+ * the atomicity of the get operation.
+ *
+ * @param[in] the_rbtree is the rbtree to attempt to get the min node from.
+ * @param[in] dir specifies whether to get minimum (0) or maximum (1)
+ *
+ * @return This method returns the min or max node on the rbtree, or NULL.
+ *
+ * @note This routine may return NULL if the RBTree is empty.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
+ RBTree_Control *the_rbtree,
+ RBTree_Direction dir
+ )
+{
+ RBTree_Node *the_node = the_rbtree->first[dir];
+ _RBTree_Extract_unprotected(the_rbtree, the_node);
+ return the_node;
+}
+
+/**
+ * @brief Determines whether the tree is unique.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
+ const RBTree_Control *the_rbtree
+)
+{
+ return( the_rbtree && the_rbtree->is_unique );
}
-#endif
/**@}*/
+#ifdef __cplusplus
+}
+#endif
+
#endif
/* end of include file */
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
new file mode 100644
index 0000000..30d55d2
--- /dev/null
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -0,0 +1,217 @@
+/**
+ * @file
+ *
+ * @brief Inlined Routines Associated with Red-Black Trees
+ *
+ * This include file contains the bodies of the routines which are
+ * associated with Red-Black Trees and inlined.
+ *
+ * @note The routines in this file are ordered from simple
+ * to complex. No other RBTree Handler routine is referenced
+ * unless it has already been defined.
+ */
+
+/*
+ * Copyright (c) 2010-2012 Gedare Bloom.
+ *
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
+ */
+
+#ifndef _RTEMS_SCORE_RBTREEIMPL_H
+#define _RTEMS_SCORE_RBTREEIMPL_H
+
+#include <rtems/score/rbtree.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @addtogroup ScoreRBTree
+ */
+/**@{**/
+
+/**
+ * @brief Red-black tree visitor.
+ *
+ * @param[in] node The node.
+ * @param[in] dir The direction.
+ * @param[in] visitor_arg The visitor argument.
+ *
+ * @retval true Stop the iteration.
+ * @retval false Continue the iteration.
+ *
+ * @see _RBTree_Iterate_unprotected().
+ */
+typedef bool (*RBTree_Visitor)(
+ const RBTree_Node *node,
+ RBTree_Direction dir,
+ void *visitor_arg
+);
+
+/**
+ * @brief Red-black tree iteration.
+ *
+ * @param[in] rbtree The red-black tree.
+ * @param[in] dir The direction.
+ * @param[in] visitor The visitor.
+ * @param[in] visitor_arg The visitor argument.
+ */
+void _RBTree_Iterate_unprotected(
+ const RBTree_Control *rbtree,
+ RBTree_Direction dir,
+ RBTree_Visitor visitor,
+ void *visitor_arg
+);
+
+/**
+ * @brief Get the direction opposite to @a the_dir.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
+ RBTree_Direction the_dir
+)
+{
+ return (RBTree_Direction) !((int) the_dir);
+}
+
+/**
+ * @brief Is this RBTree control pointer NULL.
+ *
+ * This function returns true if @a the_rbtree is NULL and false otherwise.
+ *
+ * @retval true @a the_rbtree is @c NULL.
+ * @retval false @a the_rbtree is not @c NULL.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
+ const RBTree_Control *the_rbtree
+ )
+{
+ return (the_rbtree == NULL);
+}
+
+/**
+ * @brief Is this node red.
+ *
+ * This function returns true if @a the_node is red and false otherwise.
+ *
+ * @retval true @a the_node is red.
+ * @retval false @a the_node in not red.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
+ const RBTree_Node *the_node
+ )
+{
+ return (the_node && the_node->color == RBT_RED);
+}
+
+/**
+ * @brief Return a pointer to node's grandparent.
+ *
+ * This function returns a pointer to the grandparent of @a the_node if it
+ * exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
+ const RBTree_Node *the_node
+)
+{
+ if(!the_node) return NULL;
+ if(!(the_node->parent)) return NULL;
+ if(!(the_node->parent->parent)) return NULL;
+ if(!(the_node->parent->parent->parent)) return NULL;
+ return(the_node->parent->parent);
+}
+
+/**
+ * @brief Return a pointer to node's sibling.
+ *
+ * This function returns a pointer to the sibling of @a the_node if it
+ * exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
+ const RBTree_Node *the_node
+)
+{
+ if(!the_node) return NULL;
+ if(!(the_node->parent)) return NULL;
+ if(!(the_node->parent->parent)) return NULL;
+
+ if(the_node == the_node->parent->child[RBT_LEFT])
+ return the_node->parent->child[RBT_RIGHT];
+ else
+ return the_node->parent->child[RBT_LEFT];
+}
+
+/**
+ * @brief Return a pointer to node's parent's sibling.
+ *
+ * This function returns a pointer to the sibling of the parent of
+ * @a the_node if it exists, and NULL if not.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
+ const RBTree_Node *the_node
+)
+{
+ if(!the_node) return NULL;
+ if(_RBTree_Grandparent(the_node) == NULL) return NULL;
+
+ return _RBTree_Sibling(the_node->parent);
+}
+
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
+{
+ return compare_result == 0;
+}
+
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
+ int compare_result
+)
+{
+ return compare_result > 0;
+}
+
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
+ int compare_result
+)
+{
+ return compare_result < 0;
+}
+
+/**
+ * @brief Rotate the_node in the direction passed as second argument.
+ *
+ * This routine rotates @a the_node to the direction @a dir, swapping
+ * @a the_node with its child\[@a dir\].
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
+ RBTree_Node *the_node,
+ RBTree_Direction dir
+ )
+{
+ RBTree_Node *c;
+ if (the_node == NULL) return;
+ if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
+
+ c = the_node->child[_RBTree_Opposite_direction(dir)];
+ the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
+
+ if (c->child[dir])
+ c->child[dir]->parent = the_node;
+
+ c->child[dir] = the_node;
+
+ the_node->parent->child[the_node != the_node->parent->child[0]] = c;
+
+ c->parent = the_node->parent;
+ the_node->parent = c;
+}
+
+/** @} */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+/* end of include file */
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
deleted file mode 100644
index 8b4234d..0000000
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ /dev/null
@@ -1,507 +0,0 @@
-/**
- * @file
- *
- * @brief Inlined Routines Associated with Red-Black Trees
- *
- * This include file contains the bodies of the routines which are
- * associated with Red-Black Trees and inlined.
- *
- * @note The routines in this file are ordered from simple
- * to complex. No other RBTree Handler routine is referenced
- * unless it has already been defined.
- */
-
-/*
- * Copyright (c) 2010-2012 Gedare Bloom.
- *
- * The license and distribution terms for this file may be
- * found in the file LICENSE in this distribution or at
- * http://www.rtems.com/license/LICENSE.
- */
-
-#ifndef _RTEMS_SCORE_RBTREE_H
-# error "Never use <rtems/score/rbtree.inl> directly; include <rtems/score/rbtree.h> instead."
-#endif
-
-#ifndef _RTEMS_SCORE_RBTREE_INL
-#define _RTEMS_SCORE_RBTREE_INL
-
-/**
- * @addtogroup ScoreRBTree
- */
-/**@{**/
-
-/**
- * @brief Get the direction opposite to @a the_dir.
- */
-RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
- RBTree_Direction the_dir
-)
-{
- return (RBTree_Direction) !((int) the_dir);
-}
-
-/**
- * @brief Set off RBtree.
- *
- * This function sets the parent and child fields of the @a node to NULL
- * indicating the @a node is not part of a rbtree.
- *
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
- RBTree_Node *node
- )
-{
- node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
-}
-
-/**
- * @brief Is the node off RBTree.
- *
- * This function returns true if the @a node is not on a rbtree. A @a node is
- * off rbtree if the parent and child fields are set to NULL.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
- const RBTree_Node *node
- )
-{
- return (node->parent == NULL) &&
- (node->child[RBT_LEFT] == NULL) &&
- (node->child[RBT_RIGHT] == NULL);
-}
-
-/**
- * @brief Are two Nodes equal.
- *
- * This function returns true if @a left and @a right are equal,
- * and false otherwise.
- *
- * @retval true @a left and @a right are equal.
- * @retval false @a left and @a right are not equal.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
- const RBTree_Node *left,
- const RBTree_Node *right
- )
-{
- return left == right;
-}
-
-/**
- * @brief Is this RBTree control pointer NULL.
- *
- * This function returns true if @a the_rbtree is NULL and false otherwise.
- *
- * @retval true @a the_rbtree is @c NULL.
- * @retval false @a the_rbtree is not @c NULL.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
- const RBTree_Control *the_rbtree
- )
-{
- return (the_rbtree == NULL);
-}
-
-/**
- * @brief Is the RBTree node pointer NUL.
- *
- * This function returns true if @a the_node is NULL and false otherwise.
- *
- * @retval true @a the_node is @c NULL.
- * @retval false @a the_node is not @c NULL.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node(
- const RBTree_Node *the_node
- )
-{
- return (the_node == NULL);
-}
-
-
-/**
- * @brief Return pointer to RBTree's root node.
- *
- * This function returns a pointer to the root node of @a the_rbtree.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
- const RBTree_Control *the_rbtree
-)
-{
- return the_rbtree->root;
-}
-
-/**
- * @brief Return pointer to RBTree's first node.
- *
- * This function returns a pointer to the first node on @a the_rbtree,
- * where @a dir specifies whether to return the minimum (0) or maximum (1).
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
- const RBTree_Control *the_rbtree,
- RBTree_Direction dir
-)
-{
- return the_rbtree->first[dir];
-}
-
-/**
- * @brief Return pointer to the parent of this node.
- *
- * This function returns a pointer to the parent node of @a the_node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
- const RBTree_Node *the_node
-)
-{
- if (!the_node->parent->parent) return NULL;
- return the_node->parent;
-}
-
-/**
- * @brief Return pointer to the left of this node.
- *
- * This function returns a pointer to the left node of this node.
- *
- * @param[in] the_node is the node to be operated upon.
- *
- * @return This method returns the left node on the rbtree.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
- const RBTree_Node *the_node
-)
-{
- return the_node->child[RBT_LEFT];
-}
-
-/**
- * @brief Return pointer to the right of this node.
- *
- * This function returns a pointer to the right node of this node.
- *
- * @param[in] the_node is the node to be operated upon.
- *
- * @return This method returns the right node on the rbtree.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
- const RBTree_Node *the_node
-)
-{
- return the_node->child[RBT_RIGHT];
-}
-
-/**
- * @brief Is the RBTree empty.
- *
- * This function returns true if there are no nodes on @a the_rbtree and
- * false otherwise.
- *
- * @param[in] the_rbtree is the rbtree to be operated upon.
- *
- * @retval true There are no nodes on @a the_rbtree.
- * @retval false There are nodes on @a the_rbtree.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
- const RBTree_Control *the_rbtree
-)
-{
- return (the_rbtree->root == NULL);
-}
-
-/**
- * @brief Is this the first node on the RBTree.
- *
- * This function returns true if @a the_node is the first node on
- * @a the_rbtree and false otherwise. @a dir specifies whether first means
- * minimum (0) or maximum (1).
- *
- * @retval true @a the_node is the first node on @a the_rbtree.
- * @retval false @a the_node is not the first node on @a the_rbtree.
- *
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
- const RBTree_Control *the_rbtree,
- const RBTree_Node *the_node,
- RBTree_Direction dir
-)
-{
- return (the_node == _RBTree_First(the_rbtree, dir));
-}
-
-/**
- * @brief Is this node red.
- *
- * This function returns true if @a the_node is red and false otherwise.
- *
- * @retval true @a the_node is red.
- * @retval false @a the_node in not red.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
- const RBTree_Node *the_node
- )
-{
- return (the_node && the_node->color == RBT_RED);
-}
-
-
-/**
- * @brief Does this RBTree have only one node.
- *
- * This function returns true if there is only one node on @a the_rbtree and
- * false otherwise.
- *
- * @retval true @a the_rbtree has only one node.
- * @retval false @a the_rbtree has more than one nodes.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node(
- const RBTree_Control *the_rbtree
- )
-{
- if(!the_rbtree) return false; /* TODO: expected behavior? */
- return (the_rbtree->root->child[RBT_LEFT] == NULL &&
- the_rbtree->root->child[RBT_RIGHT] == NULL);
-}
-
-/**
- * @brief Is this node the RBTree root.
- *
- * This function returns true if @a the_node is the root of @a the_rbtree and
- * false otherwise.
- *
- * @retval true @a the_node is the root of @a the_rbtree.
- * @retval false @a the_node is not the root of @a the_rbtree.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
- const RBTree_Control *the_rbtree,
- const RBTree_Node *the_node
-)
-{
- return (the_node == _RBTree_Root(the_rbtree));
-}
-
-/**
- * @brief Initialize this RBTree as empty.
- *
- * This routine initializes @a the_rbtree to contain zero nodes.
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
- RBTree_Control *the_rbtree,
- RBTree_Compare_function compare_function,
- bool is_unique
- )
-{
- the_rbtree->permanent_null = NULL;
- the_rbtree->root = NULL;
- the_rbtree->first[0] = NULL;
- the_rbtree->first[1] = NULL;
- the_rbtree->compare_function = compare_function;
- the_rbtree->is_unique = is_unique;
-}
-
-/**
- * @brief Return a pointer to node's grandparent.
- *
- * This function returns a pointer to the grandparent of @a the_node if it
- * exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
- const RBTree_Node *the_node
-)
-{
- if(!the_node) return NULL;
- if(!(the_node->parent)) return NULL;
- if(!(the_node->parent->parent)) return NULL;
- if(!(the_node->parent->parent->parent)) return NULL;
- return(the_node->parent->parent);
-}
-
-/**
- * @brief Return a pointer to node's sibling.
- *
- * This function returns a pointer to the sibling of @a the_node if it
- * exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
- const RBTree_Node *the_node
-)
-{
- if(!the_node) return NULL;
- if(!(the_node->parent)) return NULL;
- if(!(the_node->parent->parent)) return NULL;
-
- if(the_node == the_node->parent->child[RBT_LEFT])
- return the_node->parent->child[RBT_RIGHT];
- else
- return the_node->parent->child[RBT_LEFT];
-}
-
-/**
- * @brief Return a pointer to node's parent's sibling.
- *
- * This function returns a pointer to the sibling of the parent of
- * @a the_node if it exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
- const RBTree_Node *the_node
-)
-{
- if(!the_node) return NULL;
- if(_RBTree_Grandparent(the_node) == NULL) return NULL;
-
- return _RBTree_Sibling(the_node->parent);
-}
-
-/**
- * @brief Find the RBTree_Control header given a node in the tree.
- *
- * This function returns a pointer to the header of the Red Black
- * Tree containing @a the_node if it exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
- RBTree_Node *the_node
- )
-{
- if(!the_node) return NULL;
- if(!(the_node->parent)) return NULL;
- while(the_node->parent) the_node = the_node->parent;
- return (RBTree_Control*)the_node;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
-{
- return compare_result == 0;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
- int compare_result
-)
-{
- return compare_result > 0;
-}
-
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
- int compare_result
-)
-{
- return compare_result < 0;
-}
-
-/**
- * @brief Returns the predecessor of a node.
- *
- * @param[in] node is the node.
- *
- * @retval NULL The predecessor does not exist. Otherwise it returns
- * the predecessor node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
- const RBTree_Node *node
-)
-{
- return _RBTree_Next_unprotected( node, RBT_LEFT );
-}
-
-/**
- * @copydoc _RBTree_Predecessor_unprotected()
- *
- * The function disables the interrupts protect the operation.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
- const RBTree_Node *node
-)
-{
- return _RBTree_Next( node, RBT_LEFT );
-}
-
-/**
- * @brief Returns the successor of a node.
- *
- * @param[in] node is the node.
- *
- * @retval NULL The successor does not exist. Otherwise the successor node.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
- const RBTree_Node *node
-)
-{
- return _RBTree_Next_unprotected( node, RBT_RIGHT );
-}
-
-/**
- * @copydoc _RBTree_Successor_unprotected()
- *
- * The function disables the interrupts protect the operation.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
- const RBTree_Node *node
-)
-{
- return _RBTree_Next( node, RBT_RIGHT );
-}
-
-/**
- * @brief Get the first node (unprotected).
- *
- * This function removes the minimum or maximum node from the_rbtree and
- * returns a pointer to that node. It does NOT disable interrupts to ensure
- * the atomicity of the get operation.
- *
- * @param[in] the_rbtree is the rbtree to attempt to get the min node from.
- * @param[in] dir specifies whether to get minimum (0) or maximum (1)
- *
- * @return This method returns the min or max node on the rbtree, or NULL.
- *
- * @note This routine may return NULL if the RBTree is empty.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
- RBTree_Control *the_rbtree,
- RBTree_Direction dir
- )
-{
- RBTree_Node *the_node = the_rbtree->first[dir];
- _RBTree_Extract_unprotected(the_rbtree, the_node);
- return the_node;
-}
-
-/**
- * @brief Rotate the_node in the direction passed as second argument.
- *
- * This routine rotates @a the_node to the direction @a dir, swapping
- * @a the_node with its child\[@a dir\].
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
- RBTree_Node *the_node,
- RBTree_Direction dir
- )
-{
- RBTree_Node *c;
- if (the_node == NULL) return;
- if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
-
- c = the_node->child[_RBTree_Opposite_direction(dir)];
- the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
-
- if (c->child[dir])
- c->child[dir]->parent = the_node;
-
- c->child[dir] = the_node;
-
- the_node->parent->child[the_node != the_node->parent->child[0]] = c;
-
- c->parent = the_node->parent;
- the_node->parent = c;
-}
-
-/**
- * @brief Determines whether the tree is unique.
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
- const RBTree_Control *the_rbtree
-)
-{
- return( the_rbtree && the_rbtree->is_unique );
-}
-
-/** @} */
-
-#endif
-/* end of include file */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index dc687da..edf4e3e 100644
--- a/cpukit/score/preinstall.am
+++ b/cpukit/score/preinstall.am
@@ -143,6 +143,10 @@ $(PROJECT_INCLUDE)/rtems/score/rbtree.h: include/rtems/score/rbtree.h $(PROJECT_
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.h
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.h
+$(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h: include/rtems/score/rbtreeimpl.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+ $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtreeimpl.h
+
$(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h
@@ -315,10 +319,6 @@ $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl: inline/rtems/score/prioritybi
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl
-$(PROJECT_INCLUDE)/rtems/score/rbtree.inl: inline/rtems/score/rbtree.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
- $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.inl
-PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.inl
-
$(PROJECT_INCLUDE)/rtems/score/scheduler.inl: inline/rtems/score/scheduler.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.inl
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.inl
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 3079f10..0f38fbc 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -10,9 +10,7 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
#include <rtems/score/isr.h>
/** @brief Validate and fix-up tree properties after deleting a node
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 2eb92a5..b485845 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -17,9 +17,7 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
#include <rtems/score/isr.h>
RBTree_Node *_RBTree_Find(
diff --git a/cpukit/score/src/rbtreeget.c b/cpukit/score/src/rbtreeget.c
index 1570d47..a805a40 100644
--- a/cpukit/score/src/rbtreeget.c
+++ b/cpukit/score/src/rbtreeget.c
@@ -17,9 +17,7 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
#include <rtems/score/isr.h>
RBTree_Node *_RBTree_Get(
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 57a36b8..0d8e4a6 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -10,9 +10,7 @@
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
#include <rtems/score/isr.h>
/** @brief Validate and fix-up tree properties for a new insert/colored node
diff --git a/cpukit/score/src/rbtreeiterate.c b/cpukit/score/src/rbtreeiterate.c
index f6de82b..880fa2b 100644
--- a/cpukit/score/src/rbtreeiterate.c
+++ b/cpukit/score/src/rbtreeiterate.c
@@ -24,7 +24,7 @@
#include "config.h"
#endif
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
void _RBTree_Iterate_unprotected(
const RBTree_Control *rbtree,
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
index 0aee043..7dd305a 100644
--- a/cpukit/score/src/rbtreenext.c
+++ b/cpukit/score/src/rbtreenext.c
@@ -24,7 +24,7 @@
#include "config.h"
#endif
-#include <rtems/score/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
#include <rtems/score/isr.h>
RBTree_Node *_RBTree_Next_unprotected(
diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c
index 239853f..d00eefe 100644
--- a/testsuites/libtests/rbheap01/init.c
+++ b/testsuites/libtests/rbheap01/init.c
@@ -21,6 +21,7 @@
#include <rtems.h>
#include <rtems/rbheap.h>
#include <rtems/malloc.h>
+#include <rtems/score/rbtreeimpl.h>
/* forward declarations to avoid warnings */
static rtems_task Init(rtems_task_argument argument);
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 29fb71c..df2a947 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -10,9 +10,9 @@
#include "config.h"
#endif
-#define __RTEMS_VIOLATE_KERNEL_VISIBILITY__
#include <tmacros.h>
#include <rtems/rbtree.h>
+#include <rtems/score/rbtreeimpl.h>
/* forward declarations to avoid warnings */
rtems_task Init(rtems_task_argument argument);
More information about the vc
mailing list