score: Add postorder tree iteration support

Update #3465.

4 files changed, 330 insertions, 0 deletions

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@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..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();