score: Add debug support to red-black trees

This helps to detect double insert and extract errors.

1 files changed, 49 insertions, 32 deletions

diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index e7e65f7b91..e94560ea88 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -20,6 +20,7 @@
 
 #include <sys/tree.h>
 #include <rtems/score/basedefs.h>
+#include <rtems/score/assert.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -69,6 +70,38 @@ typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
   RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
 
 /**
+ * @brief Sets a red-black tree node as off-tree.
+ *
+ * Do not use this function on nodes which are a part of a tree.
+ *
+ * @param[in] the_node The node to set off-tree.
+ *
+ * @see _RBTree_Is_node_off_tree().
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
+{
+  RB_COLOR( the_node, Node ) = -1;
+}
+
+/**
+ * @brief Returns true, if this red-black tree node is off-tree, and false
+ * otherwise.
+ *
+ * @param[in] the_node The node to test.
+ *
+ * @retval true The node is not a part of a tree (off-tree).
+ * @retval false Otherwise.
+ *
+ * @see _RBTree_Set_off_tree().
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
+  const RBTree_Node *the_node
+)
+{
+  return RB_COLOR( the_node, Node ) == -1;
+}
+
+/**
  * @brief Rebalances the red-black tree after insertion of the node.
  *
  * @param[in] the_rbtree The red-black tree control.
@@ -80,6 +113,21 @@ void _RBTree_Insert_color(
 );
 
 /**
+ * @brief Initializes a red-black tree node.
+ *
+ * In debug configurations, the node is set off tree.  In all other
+ * configurations, this function does nothing.
+ *
+ * @param[in] the_node The red-black tree node to initialize.
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node )
+{
+#if defined(RTEMS_DEBUG)
+  _RBTree_Set_off_tree( the_node );
+#endif
+}
+
+/**
  * @brief Adds a child node to a parent node.
  *
  * @param[in] child The child node.
@@ -92,6 +140,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Add_child(
   RBTree_Node **link
 )
 {
+  _Assert( _RBTree_Is_node_off_tree( child ) );
   RB_SET( child, parent, Node );
   *link = child;
 }
@@ -175,38 +224,6 @@ void _RBTree_Extract(
 );
 
 /**
- * @brief Sets a red-black tree node as off-tree.
- *
- * Do not use this function on nodes which are a part of a tree.
- *
- * @param[in] the_node The node to set off-tree.
- *
- * @see _RBTree_Is_node_off_tree().
- */
-RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
-{
-  RB_COLOR( the_node, Node ) = -1;
-}
-
-/**
- * @brief Returns true, if this red-black tree node is off-tree, and false
- * otherwise.
- *
- * @param[in] the_node The node to test.
- *
- * @retval true The node is not a part of a tree (off-tree).
- * @retval false Otherwise.
- *
- * @see _RBTree_Set_off_tree().
- */
-RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
-  const RBTree_Node *the_node
-)
-{
-  return RB_COLOR( the_node, Node ) == -1;
-}
-
-/**
  * @brief Returns a pointer to root node of the red-black tree.
  *
  * The root node may change after insert or extract operations.