path: root/cpukit/score/include/rtems/score/rbtree.h

/**
 *  @file  rtems/score/rbtree.h
 *
 *  @brief Constants and Structures Associated with the Red-Black Tree Handler
 *
 *  This include file contains all the constants and structures associated
 *  with the Red-Black Tree Handler.
 */

/*
 *  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.com/license/LICENSE.
 */

#ifndef _RTEMS_SCORE_RBTREE_H
#define _RTEMS_SCORE_RBTREE_H

#include <stddef.h>

/**
 *  @defgroup ScoreRBTree Red-Black Tree Handler
 *
 *  @ingroup Score
 *
 *  The Red-Black Tree Handler is used to manage sets of entities.  This handler
 *  provides two data structures.  The rbtree Node data structure is included
 *  as the first part of every data structure that will be placed on
 *  a RBTree.  The second data structure is rbtree Control which is used
 *  to manage a set of rbtree Nodes.
 */
/**@{*/

#ifdef __cplusplus
extern "C" {
#endif

#include <rtems/score/address.h>

/**
 *  @typedef RBTree_Node
 *
 *  This type definition promotes the name for the RBTree Node used by
 *  all RTEMS code.  It is a separate type definition because a forward
 *  reference is required to define it.  See @ref RBTree_Node_struct for
 *  detailed information.
 */
typedef struct RBTree_Node_struct RBTree_Node;

/**
 * This enum type defines the colors available for the RBTree Nodes
 */
typedef enum {
  RBT_BLACK,
  RBT_RED
} RBTree_Color;

/**
 *  @struct RBTree_Node_struct
 *
 *  This is used to manage each element (node) which is placed
 *  on a RBT.
 *
 *  @note Typically, a more complicated structure will use the
 *        rbtree package.  The more complicated structure will
 *        include a rbtree node as the first element in its
 *        control structure.  It will then call the rbtree package
 *        with a pointer to that node element.  The node pointer
 *        and the higher level structure start at the same address
 *        so the user can cast the pointers back and forth.
 *
 */
struct RBTree_Node_struct {
  /** This points to the node's parent */
  RBTree_Node *parent;
  /** child[0] points to the left child, child[1] points to the right child */
  RBTree_Node *child[2];
  /** The color of the node. Either red or black */
  RBTree_Color color;
};

/**
 * @brief Macro to return the structure containing the @a node.
 *
 * This macro returns a pointer of type @a container_type that points
 * to the structure containing @a node, where @a node_field_name is the
 * field name of the RBTree_Node structure in @a container_type.
 *
 */
#define _RBTree_Container_of(node, container_type, node_field_name) \
( \
  (container_type*) \
    ( (uintptr_t)(node) - offsetof(container_type, node_field_name) ) \
)

/**
 *  This type indicates the direction.
 */
typedef enum {
  RBT_LEFT=0,
  RBT_RIGHT=1
} RBTree_Direction;

/**
 * This type defines function pointers for user-provided comparison
 * function. The function compares two nodes in order to determine
 * the order in a red-black tree.
 */
typedef int (*RBTree_Compare_function)(
  const RBTree_Node *node1,
  const RBTree_Node *node2
);

/**
 *  @struct RBTree_Control
 *
 * This is used to manage a RBT.  A rbtree consists of a tree of zero or more
 * nodes.
 *
 * @note This implementation does not require special checks for
 *   manipulating the root element of the RBT.
 *   To accomplish this the @a RBTree_Control structure can be overlaid
 *   with a @ref RBTree_Node structure to act as a "dummy root",
 *   which has a NULL parent and its left child is the root.
 */

/* 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 {
  /** This points to a NULL. Useful for finding the root. */
  RBTree_Node *permanent_null;
  /** This points to the root node of the RBT. */
  RBTree_Node *root;
  /** This points to the min and max nodes of this RBT. */
  RBTree_Node *first[2];
  /**
   * Comparison function pointer. Keys to compare have to be found
   * inside to maintain generality. It has to return 1 if first node
   * has higher key than second, -1 if lower, 0 if equal.
   */
  RBTree_Compare_function compare_function;
  /** Determines whether the tree accepts duplicate keys. */
  bool is_unique;
} RBTree_Control;

/**
 *  @brief RBTree initializer for an empty rbtree with designator @a name.
 */
#define RBTREE_INITIALIZER_EMPTY(name) \
{ \
  .permanent_null = NULL, \
  .root = NULL, \
  .first[0] = NULL, \
  .first[1] = NULL, \
  .compare_function = NULL, \
  .is_unique = 0 \
}

/**
 *  @brief RBTree definition for an empty rbtree with designator @a name.
 */
#define RBTREE_DEFINE_EMPTY(name) \
RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)

/**
 *  @brief RBTree_Node initializer for an empty node with designator @a name.
 */
#define RBTREE_NODE_INITIALIZER_EMPTY(name) \
{ \
  .parent = NULL, \
  .child[0] = NULL, \
  .child[1] = NULL, \
  RBT_RED \
}

/**
 *  @brief RBTree definition for an empty rbtree with designator @a name.
 */
#define RBTREE_NODE_DEFINE_EMPTY(name) \
RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)

/**
 *  @brief Initialize a RBTree Header.
 *
 *  This routine initializes @a the_rbtree structure to manage the
 *  contiguous array of @a number_nodes nodes which starts at
 *  @a starting_address.  Each node is of @a node_size bytes.
 *
 *  @param[in] the_rbtree is the pointer to rbtree header
 *  @param[in] starting_address is the starting address of first node
 *  @param[in] number_nodes is the number of nodes in rbtree
 *  @param[in] node_size is the size of node in bytes
 */
void _RBTree_Initialize(
  RBTree_Control          *the_rbtree,
  RBTree_Compare_function  compare_function,
  void                    *starting_address,
  size_t                   number_nodes,
  size_t                   node_size,
  bool                     is_unique
);

/**
 *  @brief Obtain the min or max node of a rbtree.
 *
 *  This function removes the min or max node from @a the_rbtree and returns
 *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
 *  @a dir specifies whether to return the min (0) or max (1).
 *
 *  @retval This method returns a pointer to a node.  If a node was removed,
 *          then a pointer to that node is returned.  If @a the_rbtree was
 *          empty, then NULL is returned.
 *
 *  @note It disables interrupts to ensure the atomicity of the get operation.
 */
RBTree_Node *_RBTree_Get(
  RBTree_Control *the_rbtree,
  RBTree_Direction dir
);

/** @brief Find the node with given key in the tree
 *
 *  This function returns a pointer to the node in @a the_rbtree
 *  having key equal to key of  @a the_node if it exists,
 *  and NULL if not. @a the_node has to be made up before a search.
 *
 *  @note If the tree is not unique and contains duplicate keys, the set
 *        of duplicate keys acts as FIFO.
 */
RBTree_Node *_RBTree_Find_unprotected(
  const RBTree_Control *the_rbtree,
  const RBTree_Node *the_node
);

/**
 *  @brief Find the node with given key in the tree.
 *
 *  This function returns a pointer to the node with key equal to a key
 *  of @a the_node if it exists in the Red-Black Tree @a the_rbtree,
 *  and NULL if not.
 *
 *  @param[in] the_rbtree pointer to rbtree control
 *  @param[in] the_node node with the key to search for
 *  @retval This method returns pointer to control header of rbtree. *
 *          If there is no control header available (the node is not part
 *          of a tree), then NULL is returned. *
 *
 *  - INTERRUPT LATENCY:
 *    + single case
 */
RBTree_Node *_RBTree_Find(
  const RBTree_Control *the_rbtree,
  const RBTree_Node *the_node
);

/**
 *  @brief Find the control structure of the tree containing the given node.
 *
 *  This function returns a pointer called @a return_header to the
 *  control structure of the tree containing @a the_node, if it exists,
 *   and @a NULL if not.
 *
 *  @param[in] the_node is the pointer to the rbtree node.
 *
 *  -INTERRUPT LATENCY:
 *    + single case
 */
RBTree_Control *_RBTree_Find_header(
  RBTree_Node *the_node
);

/**
 *  @brief Insert @a the_node on the Red-Black Tree @a the_rbtree (unprotected).
 *
 *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
 *
 *  @retval 0 Successfully inserted.
 *  @retval -1 NULL @a the_node.
 *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
 *          in an unique @a the_rbtree.
 *
 *  @note It does NOT disable interrupts to ensure the atomicity
 *        of the extract operation.
 */
RBTree_Node *_RBTree_Insert_unprotected(
  RBTree_Control *the_rbtree,
  RBTree_Node *the_node
);

/**
 *  @brief Insert a node on a rbtree.
 *
 *  This routine inserts @a the_node on the tree @a the_rbtree.
 *
 *  @retval 0 Successfully inserted.
 *  @retval -1 NULL @a the_node.
 *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
 *          in an unique @a the_rbtree.
 *
 *  @note It disables interrupts to ensure the atomicity
 *  of the extract operation.
 */
RBTree_Node *_RBTree_Insert(
  RBTree_Control *the_rbtree,
  RBTree_Node *the_node
);


/**
 *  @brief Extracts (removes) @a the_node from @a the_rbtree (unprotected).
 *
 *  This routine extracts (removes) @a the_node from @a the_rbtree.
 *
 *  @note It does NOT disable interrupts to ensure the atomicity
 *        of the extract operation.
 */
void _RBTree_Extract_unprotected(
  RBTree_Control *the_rbtree,
  RBTree_Node *the_node
);

/**
 *  @brief Delete a node from the rbtree.
 *
 *  This routine deletes @a the_node from @a the_rbtree.
 *
 *  @note It disables interrupts to ensure the atomicity of the
 *  append operation.
 */
void _RBTree_Extract(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node
);

/**
 * @brief Returns the in-order next node of a node.
 *
 * @param[in] node The node.
 * @param[in] dir The direction.
 *
 * @retval NULL The in-order next node does not exist.
 * @retval otherwise The next node.
 */
RBTree_Node *_RBTree_Next_unprotected(
  const RBTree_Node *node,
  RBTree_Direction dir
);

/**
 * @copydoc _RBTree_Next_unprotected()
 *
 * The function disables the interrupts protect the operation.
 */
RBTree_Node *_RBTree_Next(
  const RBTree_Node *node,
  RBTree_Direction dir
);

/**
 * @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_unprotected().
 */
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_unprotected(
  const RBTree_Control *rbtree,
  RBTree_Direction dir,
  RBTree_Visitor visitor,
  void *visitor_arg
);

#ifndef __RTEMS_APPLICATION__
#include <rtems/score/rbtree.inl>
#endif

#ifdef __cplusplus
}
#endif

/**@}*/

#endif
/* end of include file */