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/score/Makefile.am           |  1 +
 cpukit/score/src/rbtreepostorder.c | 81 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 82 insertions(+)
 create mode 100644 cpukit/score/src/rbtreepostorder.c

(limited to 'cpukit/score')

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