rbtree.h

Go to the documentation of this file.

/*
 *  Copyright (c) 2010 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_RBTREE_H
#define _RTEMS_SCORE_RBTREE_H

#include <sys/tree.h>
#include <rtems/score/basedefs.h>
#include <rtems/score/assert.h>

#ifdef __cplusplus
extern "C" {
#endif

struct RBTree_Control;

typedef struct RBTree_Node {
  RB_ENTRY(RBTree_Node) Node;
} RBTree_Node;

typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;

#define RBTREE_INITIALIZER_EMPTY( name ) \
  RB_INITIALIZER( name )

#define RBTREE_DEFINE_EMPTY( name ) \
  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )

RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
{
  RB_COLOR( the_node, Node ) = -1;
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
  const RBTree_Node *the_node
)
{
  return RB_COLOR( the_node, Node ) == -1;
}

void _RBTree_Insert_color(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node
);

RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node( RBTree_Node *the_node )
{
#if defined(RTEMS_DEBUG)
  _RBTree_Set_off_tree( the_node );
#else
  (void) the_node;
#endif
}

RTEMS_INLINE_ROUTINE void _RBTree_Add_child(
  RBTree_Node  *child,
  RBTree_Node  *parent,
  RBTree_Node **link
)
{
  _Assert( _RBTree_Is_node_off_tree( child ) );
  RB_SET( child, parent, Node );
  *link = child;
}

RTEMS_INLINE_ROUTINE void _RBTree_Insert_with_parent(
  RBTree_Control  *the_rbtree,
  RBTree_Node     *the_node,
  RBTree_Node     *parent,
  RBTree_Node    **link
)
{
  _RBTree_Add_child( the_node, parent, link );
  _RBTree_Insert_color( the_rbtree, the_node );
}

void _RBTree_Extract(
  RBTree_Control *the_rbtree,
  RBTree_Node *the_node
);

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
  const RBTree_Control *the_rbtree
)
{
  return RB_ROOT( the_rbtree );
}

RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference(
  RBTree_Control *the_rbtree
)
{
  return &RB_ROOT( the_rbtree );
}

RTEMS_INLINE_ROUTINE RBTree_Node * const *_RBTree_Root_const_reference(
  const RBTree_Control *the_rbtree
)
{
  return &RB_ROOT( the_rbtree );
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
  const RBTree_Node *the_node
)
{
  return RB_PARENT( the_node, Node );
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
  const RBTree_Node *the_node
)
{
  return RB_LEFT( the_node, Node );
}

RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference(
  RBTree_Node *the_node
)
{
  return &RB_LEFT( the_node, Node );
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
  const RBTree_Node *the_node
)
{
  return RB_RIGHT( the_node, Node );
}

RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference(
  RBTree_Node *the_node
)
{
  return &RB_RIGHT( the_node, Node );
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
  const RBTree_Control *the_rbtree
)
{
  return RB_EMPTY( the_rbtree );
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
  const RBTree_Node *the_node
)
{
  return _RBTree_Parent( the_node ) == NULL;
}

RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
  RBTree_Control *the_rbtree
)
{
  RB_INIT( the_rbtree );
}

RTEMS_INLINE_ROUTINE void _RBTree_Initialize_one(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node
)
{
  _Assert( _RBTree_Is_node_off_tree( the_node ) );
  RB_ROOT( the_rbtree ) = the_node;
  RB_PARENT( the_node, Node ) = NULL;
  RB_LEFT( the_node, Node ) = NULL;
  RB_RIGHT( the_node, Node ) = NULL;
  RB_COLOR( the_node, Node ) = RB_BLACK;
}

RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );

RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );

RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node );

RBTree_Node *_RBTree_Successor( const RBTree_Node *node );

void _RBTree_Replace_node(
  RBTree_Control *the_rbtree,
  RBTree_Node    *victim,
  RBTree_Node    *replacement
);

RTEMS_INLINE_ROUTINE bool _RBTree_Insert_inline(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node,
  const void     *key,
  bool         ( *less )( const void *, const RBTree_Node * )
)
{
  RBTree_Node **link;
  RBTree_Node  *parent;
  bool          is_new_minimum;

  link = _RBTree_Root_reference( the_rbtree );
  parent = NULL;
  is_new_minimum = true;

  while ( *link != NULL ) {
    parent = *link;

    if ( ( *less )( key, parent ) ) {
      link = _RBTree_Left_reference( parent );
    } else {
      link = _RBTree_Right_reference( parent );
      is_new_minimum = false;
    }
  }

  _RBTree_Add_child( the_node, parent, link );
  _RBTree_Insert_color( the_rbtree, the_node );
  return is_new_minimum;
}

RTEMS_INLINE_ROUTINE void *_RBTree_Find_inline(
  const RBTree_Control *the_rbtree,
  const void           *key,
  bool               ( *equal )( const void *, const RBTree_Node * ),
  bool               ( *less )( const void *, const RBTree_Node * ),
  void              *( *map )( RBTree_Node * )
)
{
  RBTree_Node * const *link;
  RBTree_Node         *parent;

  link = _RBTree_Root_const_reference( the_rbtree );
  parent = NULL;

  while ( *link != NULL ) {
    parent = *link;

    if ( ( *equal )( key, parent ) ) {
      return ( *map )( parent );
    } else if ( ( *less )( key, parent ) ) {
      link = _RBTree_Left_reference( parent );
    } else {
      link = _RBTree_Right_reference( parent );
    }
  }

  return NULL;
}

void *_RBTree_Postorder_first(
  const RBTree_Control *the_rbtree,
  size_t                offset
);

void *_RBTree_Postorder_next(
  const RBTree_Node *the_node,
  size_t             offset
);

#ifdef __cplusplus
}
#endif

#endif
/* end of include file */