From 6539beab824d4b9718fc0ea841791caacb8ac02f Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 29 Jun 2018 20:00:28 +0200 Subject: score: Add postorder tree iteration support Update #3465. --- cpukit/include/rtems/score/rbtree.h | 66 +++++++++++++ cpukit/score/Makefile.am | 1 + cpukit/score/src/rbtreepostorder.c | 81 ++++++++++++++++ testsuites/sptests/sprbtree01/init.c | 182 +++++++++++++++++++++++++++++++++++ 4 files changed, 330 insertions(+) create mode 100644 cpukit/score/src/rbtreepostorder.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 + * + * 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 + * + * + * 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 + +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..419881b1d8 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -1756,6 +1756,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 +2476,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(); -- cgit v1.2.3