2010-07-28 Gedare Bloom <giddyup44@yahoo.com>

	PR 1641/cpukit
	* sapi/Makefile.am, sapi/preinstall.am, score/Makefile.am,
	score/preinstall.am: Add Red Black Tree data structure to score.
	* sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl,
	score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl,
	score/src/rbtree.c, score/src/rbtreeextract.c,
	score/src/rbtreefind.c, score/src/rbtreefindheader.c,
	score/src/rbtreeget.c, score/src/rbtreeinsert.c,
	score/src/rbtreepeek.c: New files.

1 files changed, 305 insertions, 0 deletions

diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
new file mode 100644
index 0000000000..8360c99497
--- /dev/null
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -0,0 +1,305 @@
+
+/**
+ *  @file  rtems/score/rbtree.h
+ *
+ *  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.
+ *
+ *  $Id$
+ */
+
+#ifndef _RTEMS_SCORE_RBTREE_H
+#define _RTEMS_SCORE_RBTREE_H
+
+/**
+ *  @defgroup ScoreRBTree Red-Black Tree Handler
+ *
+ *  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];
+    /** This is the integer value stored by this node, used for sorting */
+    unsigned int value;
+    /** 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*) \
+   ((size_t)node - ((size_t)(&((container_type *)0)->node_field_name))))
+
+
+  typedef enum {
+    RBT_LEFT=0,
+    RBT_RIGHT=1
+  } RBTree_Direction;
+
+  /**
+   *  @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];
+  } 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, \
+  }
+
+  /**
+   *  @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, \
+    .value = -1, \
+    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.
+   */
+  void _RBTree_Initialize(
+      RBTree_Control *the_rbtree,
+      void          *starting_address,
+      size_t         number_nodes,
+      size_t         node_size
+      );
+
+  /**
+   *  @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).
+   *
+   *  @return 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 Check the min or max node on a rbtree
+   *
+   *  This function returns a pointer to the min or max node of @a the_rbtree.
+   *  If @a the_rbtree is empty, then NULL is returned. @a dir specifies 
+   *  whether to return the min (0) or max (1).
+   *
+   *  @return This method returns a pointer to a node.
+   *          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_Peek(
+      RBTree_Control *the_rbtree,
+      RBTree_Direction dir
+      );
+
+  /** @brief Find the node with given value in the tree
+   *
+   *  This function returns a pointer to the node with value equal to @a value 
+   *  if it exists in the Red-Black Tree @a the_rbtree, and NULL if not. 
+   */
+  RBTree_Node *_RBTree_Find(
+      RBTree_Control *the_rbtree, 
+      unsigned int value
+      );
+
+  /** @brief Find the control structure of the tree containing the given node 
+   *
+   *  This function returns a pointer to the control structure of the tree 
+   *  containing @a the_node, if it exists, and NULL if not. 
+   */
+  RBTree_Control *_RBTree_Find_header(
+      RBTree_Node *the_node
+      );
+
+  /** @brief Insert a Node (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->value exists 
+   *          in @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.
+   *
+   *  @note It disables interrupts to ensure the atomicity
+   *  of the extract operation.
+   */
+  void _RBTree_Insert(
+      RBTree_Control *the_rbtree,
+      RBTree_Node *the_node
+      );
+
+
+  /** @brief Extract a Node (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
+      );
+
+#ifndef __RTEMS_APPLICATION__
+#include <rtems/score/rbtree.inl>
+#endif
+
+#ifdef __cplusplus
+}
+#endif
+
+/**@}*/
+
+#endif
+/* end of include file */