From 6539beab824d4b9718fc0ea841791caacb8ac02f Mon Sep 17 00:00:00 2001
From: Sebastian Huber <sebastian.huber@embedded-brains.de>
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 +++++++++++++++++++++++++++++++++++++
 3 files changed, 148 insertions(+)
 create mode 100644 cpukit/score/src/rbtreepostorder.c

(limited to 'cpukit')

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 );
+}
-- 
cgit v1.2.3