[rtems commit] score: Improve red-black tree debug support

[Sebastian Huber]

Module:    rtems
Branch:    master
Commit:    da15db787bffe90e8ea8baac6a0cf6153922d088
Changeset: http://git.rtems.org/rtems/commit/?id=da15db787bffe90e8ea8baac6a0cf6153922d088

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Wed Aug 24 15:25:33 2016 +0200

score: Improve red-black tree debug support

Ensure that we extract a node only from the right tree.

---

 cpukit/libfs/src/jffs2/include/linux/rbtree.h |  3 +++
 cpukit/score/include/rtems/score/rbtree.h     | 10 ++++++++++
 cpukit/score/src/rbtreeextract.c              |  5 ++---
 cpukit/score/src/rbtreeinsert.c               |  4 ++++
 4 files changed, 19 insertions(+), 3 deletions(-)

diff --git a/cpukit/libfs/src/jffs2/include/linux/rbtree.h b/cpukit/libfs/src/jffs2/include/linux/rbtree.h
index 2268434..f958e6d 100644
--- a/cpukit/libfs/src/jffs2/include/linux/rbtree.h
+++ b/cpukit/libfs/src/jffs2/include/linux/rbtree.h
@@ -22,6 +22,9 @@ struct rb_node {
   struct rb_node *rb_right;
   struct rb_node *rb_parent;
   int rb_color;
+#if defined(RTEMS_DEBUG)
+  const RBTree_Control *rb_tree;
+#endif
 };
 
 RTEMS_STATIC_ASSERT(
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 818eee4..dd420b3 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -39,6 +39,8 @@ extern "C" {
  */
 /**@{*/
 
+struct RBTree_Control;
+
 /**
  * @brief Red-black tree node.
  *
@@ -47,6 +49,9 @@ extern "C" {
  */
 typedef struct RBTree_Node {
   RB_ENTRY(RBTree_Node) Node;
+#if defined(RTEMS_DEBUG)
+  const struct RBTree_Control *tree;
+#endif
 } RBTree_Node;
 
 /**
@@ -124,6 +129,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node )
 {
 #if defined(RTEMS_DEBUG)
   _RBTree_Set_off_tree( the_node );
+  the_node->tree = NULL;
 #endif
 }
 
@@ -400,6 +406,10 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_one(
 )
 {
   _Assert( _RBTree_Is_node_off_tree( the_node ) );
+#if defined(RTEMS_DEBUG)
+  _Assert( the_node->tree == NULL );
+  the_node->tree = the_rbtree;
+#endif
   RB_ROOT( the_rbtree ) = the_node;
   RB_PARENT( the_node, Node ) = NULL;
   RB_LEFT( the_node, Node ) = NULL;
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 3905f64..8a87b2d 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -21,8 +21,7 @@ void _RBTree_Extract(
   RBTree_Node    *the_node
 )
 {
+  _Assert( the_node->tree == the_rbtree );
   RB_REMOVE( RBTree_Control, the_rbtree, the_node );
-#if defined(RTEMS_DEBUG)
-  _RBTree_Set_off_tree( the_node );
-#endif
+  _RBTree_Initialize_node( the_node );
 }
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index c8bbef9..99dc2a2 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -19,5 +19,9 @@ void _RBTree_Insert_color(
   RBTree_Node    *the_node
 )
 {
+#if defined(RTEMS_DEBUG)
+  _Assert( the_node->tree == NULL );
+  the_node->tree = the_rbtree;
+#endif
   RBTree_Control_RB_INSERT_COLOR( the_rbtree, the_node );
 }