Changeset 993f5ac in rtems for cpukit/score/include/rtems/score/rbtree.h

Timestamp:

07/23/14 11:03:54 (9 years ago)

Author:

Sebastian Huber <sebastian.huber@…>

Branches:

4.11, 5, master

Children:

0ef6e3bf

Parents:

4752550f

git-author:

Sebastian Huber <sebastian.huber@…> (07/23/14 11:03:54)

git-committer:

Sebastian Huber <sebastian.huber@…> (08/07/14 13:59:29)

Message:

rbtree: Simplify insert and extract

Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more
superfluous NULL pointer checks. Change _RBTree_Is_root() to use only
the node. Add parent parameter to _RBTree_Sibling(). Delete
_RBTree_Grandparent() and _RBTree_Parent_sibling().

File:

• cpukit/score/include/rtems/score/rbtree.h (modified) (4 diffs)

cpukit/score/include/rtems/score/rbtree.h

@@ -301 +301 @@
 
 /**
- * @brief Return pointer to RBTree's root node.
- *
- * This function returns a pointer to the root node of @a the_rbtree.
+ * @brief Returns a pointer to root node of the red-black tree.
+ *
+ * The root node may change after insert or extract operations.
+ *
+ * @param[in] the_rbtree The red-black tree control.
+ *
+ * @retval NULL The tree is empty.
+ * @retval root The root node.
+ *
+ * @see _RBTree_Is_root().
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
@@ -327 +334 @@
 
 /**
- * @brief Return pointer to the parent of this node.
- *
- * This function returns a pointer to the parent node of @a the_node.
+ * @brief Returns a pointer to the parent of this node.
+ *
+ * The node must have a parent, thus it is invalid to use this function for the
+ * root node or a node that is not part of a tree.  To test for the root node
+ * compare with _RBTree_Root() or use _RBTree_Is_root().
+ *
+ * @param[in] the_node The node of interest.
+ *
+ * @retval parent The parent of this node.
+ * @retval undefined The node is the root node or not part of a tree.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
@@ -335 +349 @@
 )
 {
-  if (!the_node->parent->parent) return NULL;
   return the_node->parent;
 }
@@ -410 +423 @@
 
 /**
- * @brief Is this node the RBTree root.
- *
- * This function returns true if @a the_node is the root of @a the_rbtree and
+ * @brief Returns true if this node is the root node of a red-black tree, and
  * false otherwise.
  *
- * @retval true @a the_node is the root of @a the_rbtree.
- * @retval false @a the_node is not the root of @a the_rbtree.
+ * The root node may change after insert or extract operations.  In case the
+ * node is not a node of a tree, then this function yields unpredictable
+ * results.
+ *
+ * @param[in] the_node The node of interest.
+ *
+ * @retval true The node is the root node.
+ * @retval false Otherwise.
+ *
+ * @see _RBTree_Root().
  */
 RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
-  const RBTree_Control *the_rbtree,
-  const RBTree_Node    *the_node
-)
-{
-  return (the_node == _RBTree_Root(the_rbtree));
+  const RBTree_Node *the_node
+)
+{
+  return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL;
 }