rbtreeimpl.h

Go to the documentation of this file.

/*
 *  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 <rtems/score/rbtree.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef bool (*RBTree_Visitor)(
  const RBTree_Node *node,
  RBTree_Direction dir,
  void *visitor_arg
);

void _RBTree_Iterate(
  const RBTree_Control *rbtree,
  RBTree_Direction dir,
  RBTree_Visitor visitor,
  void *visitor_arg
);

RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
  RBTree_Direction the_dir
)
{
  return (RBTree_Direction) !((int) the_dir);
}

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 bool _RBTree_Is_red(
    const RBTree_Node *the_node
    )
{
  return (the_node && the_node->color == RBT_RED);
}

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;
}

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 )
    grandchild->parent = the_node;

  child->child[ dir ] = the_node;

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

  child->parent = parent;
  the_node->parent = child;
}

#ifdef __cplusplus
}
#endif

#endif
/* end of include file */