rbtree-rtems-compact-impl.h

/**
 * @file
 *
 * @brief Inlined Routines Associated with Red-Black Trees
 *
 * This include file contains the bodies of the routines which are
 * associated with Red-Black Trees and inlined.
 *
 * @note  The routines in this file are ordered from simple
 *        to complex.  No other RBTree Handler routine is referenced
 *        unless it has already been defined.
 */

/*
 *  Copyright (c) 2010-2012 Gedare Bloom.
 *
 *  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.
 */

#ifndef _RTEMS_SCORE_RBTREEIMPL_H
#define _RTEMS_SCORE_RBTREEIMPL_H

#include "rbtree-rtems-compact.h"

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @addtogroup ScoreRBTree
 */
/**@{**/

/**
 * @brief Red-black tree visitor.
 *
 * @param[in] node The node.
 * @param[in] dir The direction.
 * @param[in] visitor_arg The visitor argument.
 *
 * @retval true Stop the iteration.
 * @retval false Continue the iteration.
 *
 * @see _RBTree_Iterate().
 */
typedef bool (*RBTree_Visitor)(
  const RBTree_Node *node,
  RBTree_Direction dir,
  void *visitor_arg
);

/**
 * @brief Red-black tree iteration.
 *
 * @param[in] rbtree The red-black tree.
 * @param[in] dir The direction.
 * @param[in] visitor The visitor.
 * @param[in] visitor_arg The visitor argument.
 */
void _RBTree_Iterate(
  const RBTree_Control *rbtree,
  RBTree_Direction dir,
  RBTree_Visitor visitor,
  void *visitor_arg
);

/**
 * @brief Get the direction opposite to @a the_dir.
 */
RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
  RBTree_Direction the_dir
)
{
  return (RBTree_Direction) !((int) the_dir);
}

/**
 * @brief Returns the direction of the node.
 *
 * @param[in] the_node The node of interest.
 * @param[in] parent The parent of the node.  The parent must exist, thus it is
 * invalid to use this function for the root node.
 */
RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction(
  const RBTree_Node *the_node,
  const RBTree_Node *parent
)
{
  return (RBTree_Direction) ( the_node != parent->child[ 0 ] );
}

RTEMS_INLINE_ROUTINE RBTree_Color _RBTree_Color(
  const RBTree_Node *the_node
)
{
  return the_node->parent_and_color & RBT_COLOR_MASK;
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_and_color(
  const RBTree_Node *the_node,
  RBTree_Color      *color
)
{
  uintptr_t parent_and_color = the_node->parent_and_color;

  *color = parent_and_color & RBT_COLOR_MASK;

  return (RBTree_Node *) ( parent_and_color & ~RBT_COLOR_MASK );
}

RTEMS_INLINE_ROUTINE void _RBTree_Set_parent_and_color(
  RBTree_Node  *the_node,
  RBTree_Node  *parent,
  RBTree_Color  color
)
{
  the_node->parent_and_color = (uintptr_t) parent | color;
}

RTEMS_INLINE_ROUTINE void _RBTree_Set_parent(
  RBTree_Node *the_node,
  RBTree_Node *parent
)
{
  _RBTree_Set_parent_and_color( the_node, parent, _RBTree_Color( the_node ) );
}

RTEMS_INLINE_ROUTINE void _RBTree_Set_color(
  RBTree_Node  *the_node,
  RBTree_Color  color
)
{
  _RBTree_Set_parent_and_color( the_node, _RBTree_Parent( the_node ), color );
}

/**
 * @brief Returns the sibling of the node.
 *
 * @param[in] the_node The node of interest.
 * @param[in] parent The parent of the node.  The parent must exist, thus it is
 * invalid to use this function for the root node.
 *
 * @retval NULL No sibling exists.
 * @retval sibling The sibling of the node.
 */
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
  const RBTree_Node *the_node,
  const RBTree_Node *parent
)
{
  RBTree_Node *left_child = parent->child[ RBT_LEFT ];

  return the_node == left_child ? parent->child[ RBT_RIGHT ] : left_child;
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
  RBTree_Compare_result compare_result
)
{
  return compare_result == 0;
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
  RBTree_Compare_result compare_result
)
{
  return compare_result > 0;
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
  RBTree_Compare_result compare_result
)
{
  return compare_result < 0;
}

/**
 * @brief Rotates the node in the specified direction.
 *
 * The node is swapped with its child in the opposite direction if it exists.
 *
 * Sub-tree before rotation:
 * @dot
 * digraph state {
 *   parent -> the_node;
 *   the_node -> sibling [label="dir"];
 *   the_node -> child [label="opp_dir"];
 *   child -> grandchild [label="dir"];
 *   child -> grandchildsibling [label="opp_dir"];
 * }
 * @enddot
 *
 * Sub-tree after rotation:
 * @dot
 * digraph state {
 *   parent -> child;
 *   the_node -> sibling [label="dir"];
 *   the_node -> grandchild [label="opp_dir"];
 *   child -> the_node [label="dir"];
 *   child -> grandchildsibling [label="opp_dir"];
 * }
 * @enddot
 *
 * @param[in] the_node The node to rotate.
 * @param[in] dir The rotation direction.
 */
RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
  RBTree_Node      *the_node,
  RBTree_Direction  dir
)
{
  RBTree_Direction  opp_dir = _RBTree_Opposite_direction( dir );
  RBTree_Node      *child = the_node->child[ opp_dir ];
  RBTree_Node      *grandchild;
  RBTree_Node      *parent;

  if ( child == NULL)
    return;

  grandchild = child->child[ dir ];
  the_node->child[ opp_dir ] = grandchild;

  if ( grandchild != NULL )
    _RBTree_Set_parent( grandchild, the_node );

  child->child[ dir ] = the_node;

  parent = _RBTree_Parent( the_node );
  parent->child[ _RBTree_Direction( the_node, parent ) ] = child;

  _RBTree_Set_parent( child, parent );
  _RBTree_Set_parent( the_node, child );
}

/** @} */

#ifdef __cplusplus
}
#endif

#endif
/* end of include file */