summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSebastian Huber <sebastian.huber@embedded-brains.de>2012-04-10 08:25:14 (UTC)
committerSebastian Huber <sebastian.huber@embedded-brains.de>2012-04-11 09:24:18 (UTC)
commitdc62a48cc5fc95f9bbe7ab2ed2712b70987bde6f (patch)
treeed98e81b6edd2b670c7a29f6004ef9e289d89fa3
parent7afcb2619bc2b413c6f082c2bcc8d281dba8fa33 (diff)
downloadrtems-dc62a48cc5fc95f9bbe7ab2ed2712b70987bde6f.tar.bz2
rbtree: PR1995: API change
New functions o _RBTree_Next_unprotected(), o _RBTree_Next(), o _RBTree_Successor_unprotected(), o _RBTree_Predecessor_unprotected(), o rtems_rbtree_successor_unprotected(), and o rtems_rbtree_predecessor_unprotected(). Change prototype of o _RBTree_Successor(), o _RBTree_Predecessor(), o rtems_rbtree_successor(), and o rtems_rbtree_predecessor().
-rw-r--r--cpukit/sapi/inline/rtems/rbtree.inl44
-rw-r--r--cpukit/score/Makefile.am2
-rw-r--r--cpukit/score/include/rtems/score/rbtree.h27
-rw-r--r--cpukit/score/inline/rtems/score/rbtree.inl74
-rw-r--r--cpukit/score/src/rbtreenext.c80
-rw-r--r--testsuites/sptests/sprbtree01/init.c4
6 files changed, 190 insertions, 41 deletions
diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
index 259a586..1a2e99e 100644
--- a/cpukit/sapi/inline/rtems/rbtree.inl
+++ b/cpukit/sapi/inline/rtems/rbtree.inl
@@ -271,28 +271,48 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
return _RBTree_Find( the_rbtree, the_node );
}
-/** @brief Find the node's in-order predecessor
- *
- * This function returns a pointer to the in-order predecessor
- * of @a the_node if it exists, and NULL if not.
+/**
+ * @copydoc _RBTree_Predecessor_unprotected()
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
+ const rtems_rbtree_control *rbtree,
+ const rtems_rbtree_node *node
+)
+{
+ return _RBTree_Predecessor_unprotected( rbtree, node );
+}
+
+/**
+ * @copydoc _RBTree_Predecessor()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
- rtems_rbtree_node *the_node
+ const rtems_rbtree_control *rbtree,
+ const rtems_rbtree_node *node
)
{
- return _RBTree_Predecessor( the_node );
+ return _RBTree_Predecessor( rbtree, node );
}
-/** @brief Find the node's in-order successor
- *
- * This function returns a pointer to the in-order successor
- * of @a the_node if it exists, and NULL if not.
+/**
+ * @copydoc _RBTree_Successor_unprotected()
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
+ const rtems_rbtree_control *rbtree,
+ const rtems_rbtree_node *node
+)
+{
+ return _RBTree_Successor_unprotected( rbtree, node );
+}
+
+/**
+ * @copydoc _RBTree_Successor()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
- rtems_rbtree_node *the_node
+ const rtems_rbtree_control *rbtree,
+ const rtems_rbtree_node *node
)
{
- return _RBTree_Successor( the_node );
+ return _RBTree_Successor( rbtree, node );
}
/**
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 597da3e..1c896e3 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -265,7 +265,7 @@ libscore_a_SOURCES += src/pheapallocate.c \
## RBTREE_C_FILES
libscore_a_SOURCES += src/rbtree.c \
src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \
- src/rbtreeget.c src/rbtreeinsert.c src/rbtreepeek.c
+ src/rbtreeget.c src/rbtreeinsert.c src/rbtreepeek.c src/rbtreenext.c
## THREAD_C_FILES
libscore_a_SOURCES += src/thread.c src/threadchangepriority.c \
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 03e8792..b2e5776 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -321,6 +321,33 @@ void _RBTree_Extract(
RBTree_Node *the_node
);
+/**
+ * @brief Returns the in-order next node of a node.
+ *
+ * @param[in] rbtree The red-black tree.
+ * @param[in] node The node.
+ * @param[in] dir The direction.
+ *
+ * @retval NULL The in-order next node does not exist.
+ * @retval otherwise The next node.
+ */
+RBTree_Node *_RBTree_Next_unprotected(
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node,
+ RBTree_Direction dir
+);
+
+/**
+ * @copydoc _RBTree_Next_unprotected()
+ *
+ * The function disables the interrupts protect the operation.
+ */
+RBTree_Node *_RBTree_Next(
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node,
+ RBTree_Direction dir
+);
+
#ifndef __RTEMS_APPLICATION__
#include <rtems/score/rbtree.inl>
#endif
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index 2ce0b2b..d646b06 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -376,42 +376,64 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
return found;
}
-/** @brief Find the nodes in-order predecessor
+/**
+ * @brief Returns the predecessor of a node.
+ *
+ * @param[in] rbtree The red-black tree.
+ * @param[in] node The node.
+ *
+ * @retval NULL The predecessor does not exist.
+ * @retval otherwise The predecessor node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node
+)
+{
+ return _RBTree_Next_unprotected( rbtree, node, RBT_LEFT );
+}
+
+/**
+ * @copydoc _RBTree_Predecessor_unprotected()
*
- * This function returns a pointer to the in-order predecessor
- * of @a the_node if it exists, and NULL if not.
+ * The function disables the interrupts protect the operation.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
- RBTree_Node *the_node
- )
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node
+)
{
- RBTree_Node* iter_node;
- if (!the_node) return NULL;
- iter_node = the_node->child[RBT_LEFT];
- if (!iter_node) return NULL;
- while (iter_node->child[RBT_RIGHT]) {
- iter_node = iter_node->child[RBT_RIGHT];
- }
- return iter_node;
+ return _RBTree_Next( rbtree, node, RBT_LEFT );
}
-/** @brief Find the nodes in-order successor
+/**
+ * @brief Returns the successor of a node.
+ *
+ * @param[in] rbtree The red-black tree.
+ * @param[in] node The node.
+ *
+ * @retval NULL The successor does not exist.
+ * @retval otherwise The successor node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node
+)
+{
+ return _RBTree_Next_unprotected( rbtree, node, RBT_RIGHT );
+}
+
+/**
+ * @copydoc _RBTree_Successor_unprotected()
*
- * This function returns a pointer to the in-order successor
- * of @a the_node if it exists, and NULL if not.
+ * The function disables the interrupts protect the operation.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
- RBTree_Node *the_node
- )
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node
+)
{
- RBTree_Node* iter_node;
- if (!the_node) return NULL;
- iter_node = the_node->child[RBT_RIGHT];
- if (!iter_node) return NULL;
- while (iter_node->child[RBT_LEFT]) {
- iter_node = iter_node->child[RBT_LEFT];
- }
- return iter_node;
+ return _RBTree_Next( rbtree, node, RBT_RIGHT );
}
/** @brief Get the First Node (unprotected)
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
new file mode 100644
index 0000000..e79f175
--- /dev/null
+++ b/cpukit/score/src/rbtreenext.c
@@ -0,0 +1,80 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Next_unprotected() and _RBTree_Next() implementation.
+ */
+
+/*
+ * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
+ *
+ * embedded brains GmbH
+ * Obere Lagerstr. 30
+ * 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.com/license/LICENSE.
+ */
+
+#if HAVE_CONFIG_H
+ #include "config.h"
+#endif
+
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+RBTree_Node *_RBTree_Next_unprotected(
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node,
+ RBTree_Direction dir
+)
+{
+ RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
+ RBTree_Node *current = node->child [dir];
+ RBTree_Node *next = NULL;
+
+ if ( current != NULL ) {
+ next = current;
+ while ( (current = current->child [opp_dir]) != NULL ) {
+ next = current;
+ }
+ } else {
+ const RBTree_Node *null = (const RBTree_Node *) rbtree;
+ RBTree_Node *parent = node->parent;
+
+ if ( parent != null && node == parent->child [opp_dir] ) {
+ next = parent;
+ } else {
+ while ( parent != null && node == parent->child [dir] ) {
+ node = parent;
+ parent = node->parent;
+ }
+
+ if ( parent != null ) {
+ next = parent;
+ }
+ }
+ }
+
+ return next;
+}
+
+RBTree_Node *_RBTree_Next(
+ const RBTree_Control *rbtree,
+ const RBTree_Node *node,
+ RBTree_Direction dir
+)
+{
+ RBTree_Node *next;
+ ISR_Level level;
+
+ _ISR_Disable( level );
+ next = _RBTree_Next_unprotected( rbtree, node, dir );
+ _ISR_Enable( level );
+
+ return next;
+}
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 754876d..f3f9c29 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -440,13 +440,13 @@ rtems_task Init(
}
puts( "INIT - Verify rtems_rbtree_predecessor/successor");
- p = rtems_rbtree_predecessor(p);
+ p = rtems_rbtree_predecessor(&rbtree1, p);
if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 29) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);
}
p = rtems_rbtree_find(&rbtree1, &search_node.Node);
- p = rtems_rbtree_successor(p);
+ p = rtems_rbtree_successor(&rbtree1, p);
if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
puts ("INIT - ERROR ON RBTREE ID MISMATCH");
rtems_test_exit(0);