[PATCH 01/29] score: Add postorder tree iteration support
Sebastian Huber
sebastian.huber at embedded-brains.de
Thu Jul 5 07:49:21 UTC 2018
Update #3465.
66 0 cpukit/include/rtems/score/rbtree.h
1 0 cpukit/score/Makefile.am
81 0 cpukit/score/src/rbtreepostorder.c
184 0 testsuites/sptests/sprbtree01/init.c
diff --git a/cpukit/include/rtems/score/rbtree.h b/cpukit/include/rtems/score/rbtree.h
index 15a3bc8913..fea3d13695 100644
--- a/cpukit/include/rtems/score/rbtree.h
+++ b/cpukit/include/rtems/score/rbtree.h
@@ -558,6 +558,72 @@ RTEMS_INLINE_ROUTINE void *_RBTree_Find_inline(
return NULL;
}
+/**
+ * @brief Returns the container of the first node of the specified red-black
+ * tree in postorder.
+ *
+ * Postorder traversal may be used to delete all nodes of a red-black tree.
+ *
+ * @param the_rbtree The red-black tree control.
+ * @param offset The offset to the red-black tree node in the container structure.
+ *
+ * @retval NULL The red-black tree is empty.
+ * @retval container The container of the first node of the specified red-black
+ * tree in postorder.
+ *
+ * @see _RBTree_Postorder_next().
+ *
+ * @code
+ * #include <rtems/score/rbtree.h>
+ *
+ * typedef struct {
+ * int data;
+ * RBTree_Node Node;
+ * } Container_Control;
+ *
+ * void visit( Container_Control *the_container );
+ *
+ * void postorder_traversal( RBTree_Control *the_rbtree )
+ * {
+ * Container_Control *the_container;
+ *
+ * the_container = _RBTree_Postorder_first(
+ * the_rbtree,
+ * offsetof( Container_Control, Node )
+ * );
+ *
+ * while ( the_container != NULL ) {
+ * visit( the_container );
+ *
+ * the_container = _RBTree_Postorder_next(
+ * &the_container->Node,
+ * offsetof( Container_Control, Node )
+ * );
+ * }
+ * }
+ * @endcode
+ */
+void *_RBTree_Postorder_first(
+ const RBTree_Control *the_rbtree,
+ size_t offset
+);
+
+/**
+ * @brief Returns the container of the next node in postorder.
+ *
+ * @param the_node The red-black tree node. The node must not be NULL.
+ * @param offset The offset to the red-black tree node in the container structure.
+ *
+ * @retval NULL The node is NULL or there is no next node in postorder.
+ * @retval container The container of the next node in postorder.
+ *
+ * @see _RBTree_Postorder_first().
+ */
+void *_RBTree_Postorder_next(
+ const RBTree_Node *the_node,
+ size_t offset
+);
+
/**@}*/
#ifdef __cplusplus
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index b7ce16c299..e345f77daa 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -157,6 +157,7 @@ libscore_a_SOURCES += src/freechain.c
libscore_a_SOURCES += \
src/rbtreeextract.c \
src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c
+libscore_a_SOURCES += src/rbtreepostorder.c
libscore_a_SOURCES += src/rbtreereplace.c
## THREAD_C_FILES
diff --git a/cpukit/score/src/rbtreepostorder.c b/cpukit/score/src/rbtreepostorder.c
new file mode 100644
index 0000000000..26555c8848
--- /dev/null
+++ b/cpukit/score/src/rbtreepostorder.c
@@ -0,0 +1,81 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Postorder_first() and _RBTree_Postorder_next()
+ * implementation.
+ */
+
+/*
+ * Copyright (c) 2018 embedded brains GmbH. All rights reserved.
+ *
+ * embedded brains GmbH
+ * Dornierstr. 4
+ * 82178 Puchheim
+ * Germany
+ * <rtems at 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.
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/score/rbtree.h>
+
+static void *_RBTree_Postorder_dive_left(
+ const RBTree_Node *the_node,
+ size_t offset
+)
+{
+ while ( true ) {
+ if ( _RBTree_Left( the_node ) != NULL ) {
+ the_node = _RBTree_Left( the_node );
+ } else if ( _RBTree_Right( the_node ) != NULL ) {
+ the_node = _RBTree_Right( the_node );
+ } else {
+ return (void *) ( (uintptr_t) the_node - offset );
+ }
+ }
+}
+
+void *_RBTree_Postorder_next(
+ const RBTree_Node *the_node,
+ size_t offset
+)
+{
+ const RBTree_Node *parent;
+
+ parent = _RBTree_Parent( the_node );
+ if ( parent == NULL ) {
+ return NULL;
+ }
+
+ if (
+ the_node == _RBTree_Left( parent )
+ && _RBTree_Right( parent ) != NULL
+ ) {
+ return _RBTree_Postorder_dive_left( _RBTree_Right( parent ), offset );
+ }
+
+ return (void *) ( (uintptr_t) parent - offset );
+}
+
+void *_RBTree_Postorder_first(
+ const RBTree_Control *the_rbtree,
+ size_t offset
+)
+{
+ const RBTree_Node *the_node;
+
+ the_node = _RBTree_Root( the_rbtree );
+ if ( the_node == NULL ) {
+ return NULL;
+ }
+
+ return _RBTree_Postorder_dive_left( the_node, offset );
+}
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index cbd6c8f9e1..7a969cfa4a 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -63,6 +63,8 @@ static test_node node_array[100];
#define BLACK RB_BLACK
+#define GREEN 2
+
static int rb_color( const rtems_rbtree_node *n )
{
return RB_COLOR( n, Node );
@@ -1756,6 +1758,187 @@ static void test_rbtree_random_ops( void )
}
}
+typedef struct {
+ rtems_rbtree_node *parent;
+ rtems_rbtree_node *left;
+ rtems_rbtree_node *right;
+} postorder_node_description;
+
+static const postorder_node_description postorder_tree_1[] = {
+ { NULL, NULL, NULL }
+};
+
+/*
+ * TN_1
+ * /
+ * TN_0
+ */
+static const postorder_node_description postorder_tree_2[] = {
+ { TN( 1 ), NULL, NULL },
+ { NULL, TN( 0 ), NULL }
+};
+
+/*
+ * TN_1
+ * \
+ * TN_0
+ */
+static const postorder_node_description postorder_tree_3[] = {
+ { TN( 1 ), NULL, NULL },
+ { NULL, NULL, TN( 0 ) }
+};
+
+/*
+ * TN_2
+ * / \
+ * TN_0 TN_1
+ */
+static const postorder_node_description postorder_tree_4[] = {
+ { TN( 2 ), NULL, NULL },
+ { TN( 2 ), NULL, NULL },
+ { NULL, TN( 0 ), TN( 1 ) }
+};
+
+/*
+ * TN_3
+ * /
+ * TN_2
+ * / \
+ * TN_0 TN_1
+ */
+static const postorder_node_description postorder_tree_5[] = {
+ { TN( 2 ), NULL, NULL },
+ { TN( 2 ), NULL, NULL },
+ { TN( 3 ), TN( 0 ), TN( 1 ) },
+ { NULL, TN( 2 ), NULL }
+};
+
+/*
+ * TN_10
+ * / \
+ * TN_6 TN_9
+ * / \ \
+ * TN_0 TN_5 TN_8
+ * / \ /
+ * TN_2 TN_4 TN_7
+ * / /
+ * TN_1 TN_3
+ */
+static const postorder_node_description postorder_tree_6[] = {
+ { TN( 6 ), NULL, NULL },
+ { TN( 2 ), NULL, NULL },
+ { TN( 5 ), TN( 1 ), NULL },
+ { TN( 4 ), NULL, NULL },
+ { TN( 5 ), TN( 3 ), NULL },
+ { TN( 6 ), TN( 2 ), TN( 4 ) },
+ { TN( 10 ), TN( 0 ), TN( 5 ) },
+ { TN( 8 ), NULL, NULL },
+ { TN( 9 ), TN( 7 ), NULL },
+ { TN( 10 ), NULL, TN( 8 ) },
+ { NULL, TN( 6 ), TN( 9 ) }
+};
+
+/*
+ * TN_5
+ * /
+ * TN_4
+ * /
+ * TN_3
+ * \
+ * TN_2
+ * \
+ * TN_1
+ * /
+ * TN_0
+ */
+static const postorder_node_description postorder_tree_7[] = {
+ { TN( 1 ), NULL, NULL },
+ { TN( 2 ), TN( 0 ), NULL },
+ { TN( 3 ), NULL, TN( 1 ) },
+ { TN( 4 ), NULL, TN( 2 ) },
+ { TN( 5 ), TN( 3 ), NULL },
+ { NULL, TN( 0 ), NULL }
+};
+
+typedef struct {
+ const postorder_node_description *tree;
+ size_t node_count;
+} postorder_tree;
+
+#define POSTORDER_TREE( idx ) \
+ { postorder_tree_##idx, RTEMS_ARRAY_SIZE( postorder_tree_##idx ) }
+
+static const postorder_tree postorder_trees[] = {
+ { NULL, 0 },
+ POSTORDER_TREE( 1 ),
+ POSTORDER_TREE( 2 ),
+ POSTORDER_TREE( 3 ),
+ POSTORDER_TREE( 4 ),
+ POSTORDER_TREE( 5 ),
+ POSTORDER_TREE( 6 ),
+ POSTORDER_TREE( 7 )
+};
+
+static void postorder_tree_init(
+ RBTree_Control *tree,
+ const postorder_tree *pt
+)
+{
+ size_t i;
+
+ memset( node_array, 0, pt->node_count * sizeof( node_array[ 0 ] ) );
+
+ if ( pt->node_count > 0 ) {
+ _RBTree_Initialize_node( TN( 0 ) );
+ _RBTree_Initialize_one( tree, TN( 0 ) );
+ } else {
+ _RBTree_Initialize_empty( tree );
+ }
+
+ for ( i = 0; i < pt->node_count; ++i ) {
+ const postorder_node_description *pnd;
+
+ pnd = &pt->tree[ i ];
+ RB_PARENT( TN( i ), Node) = pnd->parent;
+ RB_LEFT( TN( i ), Node) = pnd->left;
+ RB_RIGHT( TN( i ), Node) = pnd->right;
+ }
+}
+
+static void postorder_tree_check(
+ RBTree_Control *tree,
+ const postorder_tree *pt
+)
+{
+ test_node *node;
+ size_t i;
+
+ node = _RBTree_Postorder_first( tree, offsetof( test_node, Node ) );
+
+ for ( i = 0; i < pt->node_count; ++i ) {
+ rtems_test_assert( node == &node_array[ i ] );
+ node = _RBTree_Postorder_next( &node->Node, offsetof( test_node, Node ) );
+ }
+
+ rtems_test_assert( node == NULL );
+}
+
+static void test_rbtree_postorder( void )
+{
+ RBTree_Control tree;
+ size_t i;
+
+ puts( "INIT - Postorder operations" );
+
+ for ( i = 0; i < RTEMS_ARRAY_SIZE( postorder_trees ); ++i ) {
+ const postorder_tree *pt;
+
+ pt = &postorder_trees[ i ];
+ postorder_tree_init( &tree, pt );
+ postorder_tree_check( &tree, pt );
+ }
+}
+
rtems_task Init( rtems_task_argument ignored )
{
rtems_rbtree_control rbtree1;
@@ -2295,6 +2478,7 @@ rtems_task Init( rtems_task_argument ignored )
rtems_test_exit(0);
}
+ test_rbtree_postorder();
test_rbtree_init_one();
test_rbtree_min_max();
test_rbtree_insert_inline();
--
2.13.7
More information about the devel
mailing list