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 <stddef.h>

#include <rtems/score/address.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct RBTree_Node_struct RBTree_Node;

typedef enum {
  RBT_BLACK,
  RBT_RED
} RBTree_Color;

struct RBTree_Node_struct {
  RBTree_Node *parent;
  RBTree_Node *child[2];
  RBTree_Color color;
};

typedef enum {
  RBT_LEFT=0,
  RBT_RIGHT=1
} RBTree_Direction;

typedef long RBTree_Compare_result;

typedef RBTree_Compare_result ( *RBTree_Compare )(
  const RBTree_Node *first,
  const RBTree_Node *second
);

/* the RBTree_Control is actually part of the RBTree structure as an
 * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
 *   permanent_null == parent
 *   root == left
 *   first[0] == right
 */
typedef struct {
  RBTree_Node *permanent_null;
  RBTree_Node *root;
  RBTree_Node *first[2];
} RBTree_Control;

#define RBTREE_INITIALIZER_EMPTY( name ) \
  { NULL, NULL, { NULL, NULL } }

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

#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
  { NULL, { NULL, NULL }, RBT_RED }

#define RBTREE_NODE_DEFINE_EMPTY( name ) \
  RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )

void _RBTree_Initialize(
  RBTree_Control *the_rbtree,
  RBTree_Compare  compare,
  void           *starting_address,
  size_t          number_nodes,
  size_t          node_size,
  bool            is_unique
);

RBTree_Node *_RBTree_Find(
  const RBTree_Control *the_rbtree,
  const RBTree_Node    *the_node,
  RBTree_Compare        compare,
  bool                  is_unique
);

RBTree_Node *_RBTree_Insert(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node,
  RBTree_Compare  compare,
  bool            is_unique
);

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

RBTree_Node *_RBTree_Next(
  const RBTree_Node *node,
  RBTree_Direction dir
);

RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
{
  the_node->parent = NULL;
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
  const RBTree_Node *the_node
)
{
  return the_node->parent == NULL;
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
  const RBTree_Control *the_rbtree
)
{
  return the_rbtree->root;
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
  const RBTree_Control *the_rbtree,
  RBTree_Direction dir
)
{
  return the_rbtree->first[dir];
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
  const RBTree_Node *the_node
)
{
  return the_node->parent;
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
  const RBTree_Node *the_node
)
{
  return the_node->child[RBT_LEFT];
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
  const RBTree_Node *the_node
)
{
  return the_node->child[RBT_RIGHT];
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
  const RBTree_Control *the_rbtree
)
{
  return (the_rbtree->root == NULL);
}

RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
  const RBTree_Control *the_rbtree,
  const RBTree_Node *the_node,
  RBTree_Direction dir
)
{
  return (the_node == _RBTree_First(the_rbtree, dir));
}

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

RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
  RBTree_Control *the_rbtree
)
{
  the_rbtree->permanent_null   = NULL;
  the_rbtree->root             = NULL;
  the_rbtree->first[RBT_LEFT]  = NULL;
  the_rbtree->first[RBT_RIGHT] = NULL;
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
  const RBTree_Node *node
)
{
  return _RBTree_Next( node, RBT_LEFT );
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
  const RBTree_Node *node
)
{
  return _RBTree_Next( node, RBT_RIGHT );
}

RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
  RBTree_Control *the_rbtree,
  RBTree_Direction dir
)
{
  RBTree_Node *the_node = the_rbtree->first[ dir ];

  if ( the_node != NULL ) {
    _RBTree_Extract( the_rbtree, the_node );
  }

  return the_node;
}

#ifdef __cplusplus
}
#endif

#endif
/* end of include file */