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.

4 files changed, 476 insertions, 2 deletions

diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
index fb35b914f0..6f9b4cc0fe 100644
--- a/cpukit/sapi/Makefile.am
+++ b/cpukit/sapi/Makefile.am
@@ -10,12 +10,13 @@ include_rtemsdir = $(includedir)/rtems
 include_rtems_HEADERS = include/confdefs.h
 include_rtems_HEADERS += include/rtems/chain.h include/rtems/config.h \
     include/rtems/extension.h include/rtems/fatal.h include/rtems/init.h \
-    include/rtems/io.h include/rtems/mptables.h include/rtems/sptables.h
+    include/rtems/io.h include/rtems/mptables.h include/rtems/rbtree.h \
+		include/rtems/sptables.h
 
 EXTRA_DIST = include/rtems/README
 
 include_rtems_HEADERS += inline/rtems/chain.inl \
-    inline/rtems/extension.inl
+    inline/rtems/extension.inl inline/rtems/rbtree.inl
 
 ## src
 AM_CPPFLAGS += -D__RTEMS_INSIDE__
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
new file mode 100644
index 0000000000..68f4ec697e
--- /dev/null
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -0,0 +1,74 @@
+/**
+ * @file rtems/rbtree.h
+ *
+ *  This include file contains all the constants and structures associated
+ *  with the RBTree API in RTEMS. The rbtree is a Red Black Tree that
+ *  is part of the Super Core. This is the published interface to that
+ *  code.
+ *
+ */
+
+/*
+ *  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_RBTREE_H
+#define _RTEMS_RBTREE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/rbtree.h>
+
+/**
+ * @typedef rtems_rbtree_node
+ *
+ * A node that can be manipulated in the rbtree.
+ */
+typedef RBTree_Node rtems_rbtree_node;
+
+/**
+ * @typedef rtems_rbtree_control
+ *
+ * The rbtree's control anchors the rbtree.
+ */
+typedef RBTree_Control rtems_rbtree_control;
+
+/**
+ *  @brief RBTree initializer for an empty rbtree with designator @a name.
+ */
+#define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
+  RBTREE_INITIALIZER_EMPTY(name)
+
+/**
+ *  @brief RBTree definition for an empty rbtree with designator @a name.
+ */
+#define RTEMS_RBTREE_DEFINE_EMPTY(name) \
+  RBTREE_DEFINE_EMPTY(name)
+
+/**
+  * @brief macro to return the structure containing the @a node.
+  *
+  * This macro returns a pointer of type @a object_type that points 
+  * to the structure containing @a node, where @a object_member is the 
+  * field name of the rtems_rbtree_node structure in objects of @a object_type.
+  */
+#define rtems_rbtree_container_of(node,object_type, object_member) \
+  _RBTree_Container_of(node,object_type,object_member)
+
+#include <rtems/rbtree.inl>
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+/* end of include file */
diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
new file mode 100644
index 0000000000..3f2045189e
--- /dev/null
+++ b/cpukit/sapi/inline/rtems/rbtree.inl
@@ -0,0 +1,391 @@
+/**
+ * @file rtems/rbtree.inl
+ *
+ *  This include file contains all the constants and structures associated
+ *  with the RBTree API in RTEMS. The rbtree is a Red Black Tree that
+ *  is part of the Super Core. This is the published interface to that
+ *  code.
+ *
+ */
+ 
+/*
+ *  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_RBTREE_H
+# error "Never use <rtems/rbtree.inl> directly; include <rtems/rbtree.h> instead."
+#endif
+
+#ifndef _RTEMS_RBTREE_INL
+#define _RTEMS_RBTREE_INL
+
+#include <rtems/score/rbtree.inl>
+
+/**
+ *  @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.
+ */
+RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
+  rtems_rbtree_control *the_rbtree,
+  void                *starting_address,
+  size_t               number_nodes,
+  size_t               node_size
+)
+{
+  _RBTree_Initialize( the_rbtree, starting_address, number_nodes, node_size);
+}
+
+/**
+ *  @brief Initialize this RBTree as Empty
+ *
+ *  This routine initializes @a the_rbtree to contain zero nodes.
+ */
+RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  _RBTree_Initialize_empty( the_rbtree );
+}
+
+/**
+ *  @brief Set off rbtree
+ *
+ *  This function sets the next and previous fields of the @a node to NULL
+ *  indicating the @a node is not part of any rbtree.
+ */
+RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree(
+  rtems_rbtree_node *node
+)
+{
+  _RBTree_Set_off_rbtree( node );
+}
+
+/**
+ *  @brief Is the Node off RBTree
+ *
+ *  This function returns true if the @a node is not on a rbtree. A @a node is
+ *  off rbtree if the next and previous fields are set to NULL.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree(
+  const rtems_rbtree_node *node
+)
+{
+  return _RBTree_Is_node_off_rbtree( node );
+}
+
+/**
+ *  @brief Is the RBTree Node Pointer NULL
+ *
+ *  This function returns true if @a the_node is NULL and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_null_node(
+  const rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Is_null_node( the_node );
+}
+
+/**
+ *  @brief Return pointer to RBTree Root
+ *
+ *  This function returns a pointer to the root node of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Root( the_rbtree );
+}
+
+/**
+ *  @brief Return pointer to RBTree Minimum
+ *
+ *  This function returns a pointer to the minimum node of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_First( the_rbtree, RBT_LEFT );
+}
+
+/**
+ *  @brief Return pointer to RBTree Maximum
+ *
+ *  This function returns a pointer to the maximum node of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_First( the_rbtree, RBT_RIGHT );
+}
+
+/**
+ *  @brief Return pointer to the left child node from this node
+ *
+ *  This function returns a pointer to the left child node of @a the_node.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left(
+  rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Left( the_node );
+}
+
+/**
+ *  @brief Return pointer to the right child node from this node
+ *
+ *  This function returns a pointer to the right child node of @a the_node.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
+  rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Right( the_node );
+}
+
+/**
+ *  @brief Return pointer to the parent child node from this node
+ *
+ *  This function returns a pointer to the parent node of @a the_node.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
+  rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Parent( the_node );
+}
+
+/**
+ *  @brief Are Two Nodes Equal
+ *
+ *  This function returns true if @a left and @a right are equal,
+ *  and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_are_nodes_equal(
+  const rtems_rbtree_node *left,
+  const rtems_rbtree_node *right
+)
+{
+  return _RBTree_Are_nodes_equal( left, right );
+}
+
+/**
+ *  @brief Is the RBTree Empty
+ *
+ *  This function returns true if there a no nodes on @a the_rbtree and
+ *  false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Is_empty( the_rbtree );
+}
+
+/**
+ *  @brief Is this the Minimum Node on the RBTree
+ *
+ *  This function returns true if @a the_node is the min node on @a the_rbtree 
+ *  and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(
+  rtems_rbtree_control *the_rbtree,
+  const rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT );
+}
+
+/**
+ *  @brief Is this the Maximum Node on the RBTree
+ *
+ *  This function returns true if @a the_node is the max node on @a the_rbtree 
+ *  and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
+  rtems_rbtree_control *the_rbtree,
+  const rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT );
+}
+
+
+/**
+ *  @brief Does this RBTree have only One Node
+ *
+ *  This function returns true if there is only one node on @a the_rbtree and
+ *  false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_has_only_one_node(
+  const rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Has_only_one_node( the_rbtree );
+}
+
+/**
+ *  @brief Is this Node the RBTree Root
+ *
+ *  This function returns true if @a the_node is the root of @a the_rbtree and
+ *  false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
+  rtems_rbtree_control    *the_rbtree,
+  const rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Is_root( the_rbtree, the_node );
+}
+
+/** @brief Find the node with given value in the tree
+ *
+ *  This function returns a pointer to the node having value equal to @a value 
+ *  if it exists within @a the_rbtree, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
+  rtems_rbtree_control *the_rbtree,
+  unsigned int value
+)
+{
+  return _RBTree_Find( the_rbtree, value );
+}
+
+/** @brief Find the node's in-order predecessor 
+ *
+ * This function returns a pointer to the in-order predecessor 
+ * of @a the_node if it exists, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
+  rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Predecessor( the_node );
+}
+
+/** @brief Find the node's in-order successor 
+ *
+ *  This function returns a pointer to the in-order successor  
+ *  of @a the_node if it exists, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
+  rtems_rbtree_node *the_node
+)
+{
+  return _RBTree_Successor( the_node );
+}
+
+/**
+ *  @brief Extract the specified node from a rbtree
+ *
+ *  This routine extracts @a the_node from @a the_rbtree on which it resides.
+ *  It disables interrupts to ensure the atomicity of the extract operation.
+ */
+RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
+  rtems_rbtree_control *the_rbtree,
+  rtems_rbtree_node *the_node
+)
+{
+  _RBTree_Extract( the_rbtree, the_node );
+}
+
+/**
+ *  @brief Obtain the min node on a rbtree
+ *
+ *  This function removes the min node from @a the_rbtree and returns
+ *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
+ *  It disables interrupts to ensure the atomicity of the get operation.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Get( the_rbtree, RBT_LEFT );
+}
+
+/**
+ *  @brief Obtain the max node on a rbtree
+ *
+ *  This function removes the max node from @a the_rbtree and returns
+ *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
+ *  It disables interrupts to ensure the atomicity of the get operation.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Get( the_rbtree, RBT_RIGHT );
+}
+
+/**
+ *  @brief Peek at the min node on a rbtree
+ *
+ *  This function returns a pointer to the min node from @a the_rbtree 
+ *  without changing the tree.  If @a the_rbtree is empty, 
+ *  then NULL is returned.
+ *  It disables interrupts to ensure the atomicity of the peek operation.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Peek( the_rbtree, RBT_LEFT );
+}
+
+/**
+ *  @brief Peek at the max node on a rbtree
+ *
+ *  This function returns a pointer to the max node from @a the_rbtree 
+ *  without changing the tree.  If @a the_rbtree is empty, 
+ *  then NULL is returned.
+ *  It disables interrupts to ensure the atomicity of the peek operation.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
+  rtems_rbtree_control *the_rbtree
+)
+{
+  return _RBTree_Peek( the_rbtree, RBT_RIGHT );
+}
+
+
+/**
+ *  @brief Find the control header of the tree containing a given node.
+ *
+ *  This routine finds the rtems_rbtree_control structure of the tree 
+ *  containing @a the_node.
+ *  It disables interrupts to ensure the atomicity of the find operation.
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
+  rtems_rbtree_node *the_node
+)
+{
+  return(_RBTree_Find_header( the_node ));
+}
+
+/**
+ *  @brief Insert a node on a rbtree
+ *
+ *  This routine inserts @a the_node on @a the_rbtree.
+ *  It disables interrupts to ensure the atomicity of the insert operation.
+ */
+RTEMS_INLINE_ROUTINE void rtems_rbtree_insert(
+  rtems_rbtree_control *the_rbtree,
+  rtems_rbtree_node *the_node
+)
+{
+  _RBTree_Insert( the_rbtree, the_node );
+}
+
+#endif
+/* end of include file */
diff --git a/cpukit/sapi/preinstall.am b/cpukit/sapi/preinstall.am
index 975828246c..f49f81427c 100644
--- a/cpukit/sapi/preinstall.am
+++ b/cpukit/sapi/preinstall.am
@@ -60,6 +60,10 @@ $(PROJECT_INCLUDE)/rtems/mptables.h: include/rtems/mptables.h $(PROJECT_INCLUDE)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/mptables.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/mptables.h
 
+$(PROJECT_INCLUDE)/rtems/rbtree.h: include/rtems/rbtree.h $(PROJECT_INCLUDE)/rtems/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.h
+
 $(PROJECT_INCLUDE)/rtems/sptables.h: include/rtems/sptables.h $(PROJECT_INCLUDE)/rtems/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/sptables.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/sptables.h
@@ -72,6 +76,10 @@ $(PROJECT_INCLUDE)/rtems/extension.inl: inline/rtems/extension.inl $(PROJECT_INC
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/extension.inl
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/extension.inl
 
+$(PROJECT_INCLUDE)/rtems/rbtree.inl: inline/rtems/rbtree.inl $(PROJECT_INCLUDE)/rtems/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.inl
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.inl
+
 $(PROJECT_LIB)/libsapi.a: libsapi.a $(PROJECT_LIB)/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_LIB)/libsapi.a
 TMPINSTALL_FILES += $(PROJECT_LIB)/libsapi.a