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.

11 files changed, 1419 insertions, 0 deletions

diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 9d3d97f593..b9ce843360 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -26,6 +26,7 @@ include_rtems_score_HEADERS = include/rtems/score/address.h \
     include/rtems/score/interr.h include/rtems/score/isr.h \
     include/rtems/score/object.h include/rtems/score/percpu.h \
     include/rtems/score/priority.h include/rtems/score/prioritybitmap.h \
+		include/rtems/score/rbtree.h \
     include/rtems/score/scheduler.h include/rtems/score/schedulerpriority.h \
     include/rtems/score/schedulersimple.h \
     include/rtems/score/stack.h include/rtems/score/states.h \
@@ -57,6 +58,7 @@ include_rtems_score_HEADERS += inline/rtems/score/address.inl \
     inline/rtems/score/coresem.inl inline/rtems/score/heap.inl \
     inline/rtems/score/isr.inl inline/rtems/score/object.inl \
     inline/rtems/score/priority.inl inline/rtems/score/prioritybitmap.inl \
+		inline/rtems/score/rbtree.inl \
     inline/rtems/score/scheduler.inl inline/rtems/score/schedulerpriority.inl \
     inline/rtems/score/schedulersimple.inl \
     inline/rtems/score/stack.inl inline/rtems/score/states.inl \
@@ -178,6 +180,11 @@ libscore_a_SOURCES += src/pheapallocate.c \
     src/pheapgetblocksize.c src/pheapgetfreeinfo.c src/pheapgetinfo.c \
     src/pheapinit.c src/pheapresizeblock.c src/pheapwalk.c
 
+## RBTREE_C_FILES
+libscore_a_SOURCES += src/rbtree.c \
+    src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \
+    src/rbtreeget.c src/rbtreeinsert.c src/rbtreepeek.c
+
 ## THREAD_C_FILES
 libscore_a_SOURCES += src/thread.c src/threadchangepriority.c \
     src/threadclearstate.c src/threadclose.c src/threadcreateidle.c \
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 */
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
new file mode 100644
index 0000000000..097cede027
--- /dev/null
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -0,0 +1,442 @@
+/**
+ *  @file  rtems/score/rbtree.inl
+ *
+ *  This include file contains the bodies of the routines which are
+ *  associated with Red-Black Trees and inlined.
+ *
+ *  @note  The routines in this file are ordered from simple
+ *         to complex.  No other RBTree Handler routine is referenced
+ *         unless it has already been defined.
+ */
+
+/*
+ *  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
+# error "Never use <rtems/score/rbtree.inl> directly; include <rtems/score/rbtree.h> instead."
+#endif
+
+#ifndef _RTEMS_SCORE_RBTREE_INL
+#define _RTEMS_SCORE_RBTREE_INL
+
+/**
+ *  @addtogroup ScoreRBTree 
+ *  @{
+ */
+
+/** @brief Set off rbtree
+ *
+ *  This function sets the parent and child fields of the @a node to NULL
+ *  indicating the @a node is not part of a rbtree.
+ *
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
+    RBTree_Node *node
+    )
+{
+  node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
+}
+
+/** @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 parent and child fields are set to NULL.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
+    const RBTree_Node *node
+    )
+{
+  return (node->parent == NULL) && (node->child[RBT_LEFT] == NULL) && (node->child[RBT_RIGHT] == NULL);
+}
+
+/** @brief Are Two Nodes Equal
+ *
+ *  This function returns true if @a left and @a right are equal,
+ *  and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal(
+    const RBTree_Node *left,
+    const RBTree_Node *right
+    )
+{
+  return left == right;
+}
+
+/** @brief Is this RBTree Control Pointer Null
+ *
+ *  This function returns true if @a the_rbtree is NULL and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_null(
+    const RBTree_Control *the_rbtree
+    )
+{
+  return (the_rbtree == NULL);
+}
+
+/** @brief Is the RBTree Node Pointer NULL
+ *
+ *  This function returns true if @a the_node is NULL and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node(
+    const RBTree_Node *the_node
+    )
+{
+  return (the_node == NULL);
+}
+
+
+/** @brief Return pointer to RBTree's root node
+ *
+ *  This function returns a pointer to the root node of @a the_rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
+    RBTree_Control *the_rbtree
+    )
+{
+  return the_rbtree->root;
+}
+
+/** @brief Return pointer to RBTree's First node
+ *
+ *  This function returns a pointer to the first node on @a the_rbtree, 
+ *  where @a dir specifies whether to return the minimum (0) or maximum (1).
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
+    RBTree_Control *the_rbtree,
+    RBTree_Direction dir
+    )
+{
+  return the_rbtree->first[dir];
+}
+
+/** @brief Return pointer to the parent of this node
+ *
+ *  This function returns a pointer to the parent node of @a the_node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
+    RBTree_Node *the_node
+    )
+{
+  if (!the_node->parent->parent) return NULL;
+  return the_node->parent;
+}
+
+/** @brief Return pointer to the left of this node
+ *
+ *  This function returns a pointer to the left node of this node.
+ *
+ *  @param[in] the_node is the node to be operated upon.
+ *
+ *  @return This method returns the left node on the rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
+    RBTree_Node *the_node
+    )
+{
+  return the_node->child[RBT_LEFT];
+}
+
+/** @brief Return pointer to the right of this node
+ *
+ *  This function returns a pointer to the right node of this node.
+ *
+ *  @param[in] the_node is the node to be operated upon.
+ *
+ *  @return This method returns the right node on the rbtree.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
+    RBTree_Node *the_node
+    )
+{
+  return the_node->child[RBT_RIGHT];
+}
+
+/** @brief Is the RBTree Empty
+ *
+ *  This function returns true if there are no nodes on @a the_rbtree and
+ *  false otherwise.
+ *
+ *  @param[in] the_rbtree is the rbtree to be operated upon.
+ *
+ *  @return This function returns true if there are no nodes on 
+ *  @a the_rbtree and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
+    RBTree_Control *the_rbtree
+    )
+{
+  return (the_rbtree->root == NULL);
+}
+
+/** @brief Is this the First Node on the RBTree
+ *
+ *  This function returns true if @a the_node is the first node on 
+ *  @a the_rbtree and false otherwise. @a dir specifies whether first means 
+ *  minimum (0) or maximum (1).
+ *
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
+    RBTree_Control *the_rbtree,
+    const RBTree_Node *the_node,
+    RBTree_Direction dir
+    )
+{
+  return (the_node == _RBTree_First(the_rbtree, dir));
+}
+
+/** @brief Is this node red?
+ *
+ *  This function returns true if @a the_node is red and false otherwise.
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
+    const RBTree_Node *the_node
+    )
+{
+  return (the_node && the_node->color == RBT_RED);
+}
+
+
+/** @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 _RBTree_Has_only_one_node(
+    const RBTree_Control *the_rbtree
+    )
+{
+  if(!the_rbtree) return NULL; /* TODO: expected behavior? */
+  return (the_rbtree->root->child[RBT_LEFT] == NULL && the_rbtree->root->child[RBT_RIGHT] == NULL);
+}
+
+/** @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 _RBTree_Is_root(
+    RBTree_Control *the_rbtree,
+    const RBTree_Node    *the_node
+    )
+{
+  return (the_node == _RBTree_Root(the_rbtree));
+}
+
+/** @brief Initialize this RBTree as Empty
+ *
+ *  This routine initializes @a the_rbtree to contain zero nodes.
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
+    RBTree_Control *the_rbtree
+    )
+{
+  the_rbtree->permanent_null = NULL;
+  the_rbtree->root           = NULL;
+  the_rbtree->first[0]       = NULL;
+  the_rbtree->first[1]       = NULL;
+}
+
+/** @brief Return a pointer to node's grandparent
+ *
+ *  This function returns a pointer to the grandparent of @a the_node if it 
+ *  exists, and NULL if not. 
+ *  
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
+    RBTree_Node *the_node
+    )
+{
+  if(!the_node) return NULL;
+  if(!(the_node->parent)) return NULL;
+  if(!(the_node->parent->parent)) return NULL;
+  if(!(the_node->parent->parent->parent)) return NULL;
+  return(the_node->parent->parent);
+}
+
+/** @brief Return a pointer to node's sibling
+ *
+ *  This function returns a pointer to the sibling of @a the_node if it 
+ *  exists, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
+    RBTree_Node *the_node
+    )
+{
+  if(!the_node) return NULL;
+  if(!(the_node->parent)) return NULL;
+  if(!(the_node->parent->parent)) return NULL;
+
+  if(the_node == the_node->parent->child[RBT_LEFT])
+    return the_node->parent->child[RBT_RIGHT];
+  else
+    return the_node->parent->child[RBT_LEFT];
+}
+
+/** @brief Return a pointer to node's parent's sibling
+ *
+ *  This function returns a pointer to the sibling of the parent of 
+ *  @a the_node if it exists, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
+    RBTree_Node *the_node
+    )
+{
+  if(!the_node) return NULL;
+  if(_RBTree_Grandparent(the_node) == NULL) return NULL;
+
+  return _RBTree_Sibling(the_node->parent);
+}
+
+/** @brief Find the RBTree_Control header given a node in the tree
+ *
+ *  This function returns a pointer to the header of the Red Black 
+ *  Tree containing @a the_node if it exists, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
+    RBTree_Node *the_node
+    )
+{
+  if(!the_node) return NULL;
+  if(!(the_node->parent)) return NULL;
+  while(the_node->parent) the_node = the_node->parent;
+  return (RBTree_Control*)the_node;
+}
+
+/** @brief Find the node with given value in the tree
+ *
+ *  This function returns a pointer to the node in @a the_rbtree 
+ *  having value equal to @a the_value if it exists, and NULL if not. 
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
+    RBTree_Control *the_rbtree,
+    unsigned int the_value
+    )
+{
+  RBTree_Node* iter_node = the_rbtree->root;
+  while (iter_node) {
+    if (the_value == iter_node->value) return(iter_node);
+
+    RBTree_Direction dir = the_value > iter_node->value;
+    iter_node = iter_node->child[dir];
+  } /* while(iter_node) */
+
+  return 0;
+}
+
+/** @brief Find the nodes 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 RBTree_Node *_RBTree_Predecessor(
+    RBTree_Node *the_node
+    )
+{
+  RBTree_Node* iter_node;
+  if (!the_node) return NULL;
+  iter_node = the_node->child[RBT_LEFT];
+  if (!iter_node) return NULL;
+  while (iter_node->child[RBT_RIGHT]) {
+    iter_node = iter_node->child[RBT_RIGHT];
+  } 
+  return iter_node;
+}
+
+/** @brief Find the nodes 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 RBTree_Node *_RBTree_Successor(
+    RBTree_Node *the_node
+    )
+{
+  RBTree_Node* iter_node;
+  if (!the_node) return NULL;
+  iter_node = the_node->child[RBT_RIGHT];
+  if (!iter_node) return NULL;
+  while (iter_node->child[RBT_LEFT]) {
+    iter_node = iter_node->child[RBT_LEFT];
+  } 
+  return iter_node;
+}
+
+/** @brief Get the First Node (unprotected)
+ *
+ *  This function removes the minimum or maximum node from the_rbtree and 
+ *  returns a pointer to that node.  It does NOT disable interrupts to ensure
+ *  the atomicity of the get operation.
+ *
+ *  @param[in] the_rbtree is the rbtree to attempt to get the min node from.
+ *  @param[in] dir specifies whether to get minimum (0) or maximum (1)
+ *
+ *  @return This method returns the min or max node on the rbtree, or NULL.
+ *
+ *  @note This routine may return NULL if the RBTree is empty.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected(
+    RBTree_Control *the_rbtree,
+    RBTree_Direction dir
+    )
+{
+  RBTree_Node *the_node = the_rbtree->first[dir];
+  _RBTree_Extract_unprotected(the_rbtree, the_node);
+  return the_node;
+}
+
+/** @brief Peek at the First Node (unprotected)
+ *
+ *  This function returns a pointer to the first node, minimum if @a dir is 0 
+ *  or maximum if @a dir is 1, from @a the_rbtree without extracting it.  
+ *  It does NOT disable interrupts to ensure the atomicity of the peek.
+ *
+ *  @retval NULL if @a the_rbtree is empty.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Peek_unprotected(
+    RBTree_Control *the_rbtree,
+    RBTree_Direction dir
+    )
+{
+  return(the_rbtree->first[dir]);
+}
+
+/** @brief Rotate the_node in the direction passed as second argument
+ *  
+ *  This routine rotates @a the_node to the direction @a dir, swapping
+ *  @a the_node with its child\[@a dir\].
+ */
+RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
+    RBTree_Node *the_node,
+    RBTree_Direction dir
+    )
+{
+  RBTree_Node *c;
+  if (the_node == NULL) return;
+  if (the_node->child[(1-dir)] == NULL) return;
+  
+
+  c = the_node->child[(1-dir)];
+  the_node->child[(1-dir)] = c->child[dir];
+
+  if (c->child[dir])
+    c->child[dir]->parent = the_node;
+
+  c->child[dir] = the_node;
+
+  the_node->parent->child[the_node != the_node->parent->child[0]] = c;
+
+  c->parent = the_node->parent;
+  the_node->parent = c;
+}
+/**@}*/
+
+#endif
+/* end of include file */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index 6979313a19..d228c69d86 100644
--- a/cpukit/score/preinstall.am
+++ b/cpukit/score/preinstall.am
@@ -115,6 +115,10 @@ $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.h: include/rtems/score/prioritybit
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.h
 
+$(PROJECT_INCLUDE)/rtems/score/rbtree.h: include/rtems/score/rbtree.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.h
+
 $(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h
@@ -265,6 +269,10 @@ $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl: inline/rtems/score/prioritybi
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl
 
+$(PROJECT_INCLUDE)/rtems/score/rbtree.inl: inline/rtems/score/rbtree.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.inl
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.inl
+
 $(PROJECT_INCLUDE)/rtems/score/scheduler.inl: inline/rtems/score/scheduler.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.inl
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.inl
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
new file mode 100644
index 0000000000..2c1035b3dc
--- /dev/null
+++ b/cpukit/score/src/rbtree.c
@@ -0,0 +1,58 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/*PAGE
+ *
+ *  _RBTree_Initialize
+ *
+ *  This kernel routine initializes a Red-Black Tree.
+ *
+ *  Input parameters:
+ *    the_rbtree        - pointer to rbtree header
+ *    starting_address - starting address of first node
+ *    number_nodes     - number of nodes in rbtree
+ *    node_size        - size of node in bytes
+ *
+ *  Output parameters:  NONE
+ */
+
+void _RBTree_Initialize(
+  RBTree_Control *the_rbtree,
+  void           *starting_address,
+  size_t         number_nodes,
+  size_t         node_size
+)
+{
+  size_t      count;
+  RBTree_Node *next;
+
+  /* TODO: Error message? */
+  if (!the_rbtree) return;
+
+  /* could do sanity checks here */
+  _RBTree_Initialize_empty(the_rbtree);
+ 
+  count = number_nodes;
+  next  = starting_address;
+  while ( count-- ) {
+    _RBTree_Insert(the_rbtree, next);
+    next           = (RBTree_Node *)
+                        _Addresses_Add_offset( (void *) next, node_size );
+  }
+}
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
new file mode 100644
index 0000000000..97328beb49
--- /dev/null
+++ b/cpukit/score/src/rbtreeextract.c
@@ -0,0 +1,245 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/** @brief  Validate and fix-up tree properties after deleting a node
+ *
+ *  This routine is called on a black node, @a the_node, after its deletion.
+ *  This function maintains the properties of the red-black tree.
+ *
+ *  @note It does NOT disable interrupts to ensure the atomicity
+ *        of the extract operation.
+ */
+void _RBTree_Extract_validate_unprotected(
+    RBTree_Node *the_node
+    )
+{
+  RBTree_Node *parent, *sibling;
+  RBTree_Direction dir;
+
+  parent = the_node->parent; 
+  if(!parent->parent) return;
+
+  sibling = _RBTree_Sibling(the_node);
+
+  /* continue to correct tree as long as the_node is black and not the root */
+  while (!_RBTree_Is_red(the_node) && parent->parent) {
+
+    /* if sibling is red, switch parent (black) and sibling colors, 
+     * then rotate parent left, making the sibling be the_node's grandparent.
+     * Now the_node has a black sibling and red parent. After rotation, 
+     * update sibling pointer.
+     */
+    if (_RBTree_Is_red(sibling)) {
+      parent->color = RBT_RED;
+      sibling->color = RBT_BLACK;
+      dir = the_node != parent->child[0];
+      _RBTree_Rotate(parent, dir);
+      sibling = parent->child[!dir];
+    }
+
+    /* sibling is black, see if both of its children are also black. */
+    if (sibling && 
+        !_RBTree_Is_red(sibling->child[RBT_RIGHT]) && 
+        !_RBTree_Is_red(sibling->child[RBT_LEFT])) {
+        sibling->color = RBT_RED;
+        if (_RBTree_Is_red(parent)) {
+          parent->color = RBT_BLACK;
+          break;
+        }
+        the_node = parent; /* done if parent is red */
+        parent = the_node->parent;
+        sibling = _RBTree_Sibling(the_node);
+    } else if(sibling) {
+      /* at least one of sibling's children is red. we now proceed in two 
+       * cases, either the_node is to the left or the right of the parent. 
+       * In both cases, first check if one of sibling's children is black, 
+       * and if so rotate in the proper direction and update sibling pointer.
+       * Then switch the sibling and parent colors, and rotate through parent.
+       */
+      dir = the_node != parent->child[0];
+      if (!_RBTree_Is_red(sibling->child[!dir])) {
+        sibling->color = RBT_RED;
+        sibling->child[dir]->color = RBT_BLACK;
+        _RBTree_Rotate(sibling, !dir);
+        sibling = parent->child[!dir];
+      }
+      sibling->color = parent->color;
+      parent->color = RBT_BLACK;
+      sibling->child[!dir]->color = RBT_BLACK;
+      _RBTree_Rotate(parent, dir);
+      break; /* done */
+    }
+  } /* while */
+  if(!the_node->parent->parent) the_node->color = RBT_BLACK;
+}
+
+/** @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
+    )
+{
+  RBTree_Node *leaf, *target;
+  RBTree_Color victim_color;
+  RBTree_Direction dir;
+
+  if(!the_node) return;
+
+  /* check if min needs to be updated */
+  if (the_node == the_rbtree->first[RBT_LEFT]) {
+    if (the_node->child[RBT_RIGHT])
+      the_rbtree->first[RBT_LEFT] = the_node->child[RBT_RIGHT];
+    else {
+      the_rbtree->first[RBT_LEFT] = the_node->parent;
+      if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree, 
+            the_rbtree->first[RBT_LEFT]))
+        the_rbtree->first[RBT_LEFT] = NULL;
+    }
+  }
+  /* check if max needs to be updated: note, min can equal max (1 element) */
+  if (the_node == the_rbtree->first[RBT_RIGHT]) {
+    if (the_node->child[RBT_LEFT])
+      the_rbtree->first[RBT_RIGHT] = the_node->child[RBT_LEFT];
+    else {
+      the_rbtree->first[RBT_RIGHT] = the_node->parent;
+      if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree, 
+            the_rbtree->first[RBT_RIGHT]))
+        the_rbtree->first[RBT_RIGHT] = NULL;
+    }
+  }
+
+  /* if the_node has at most one non-null child then it is safe to proceed
+   * check if both children are non-null, if so then we must find a target node
+   * either max in node->child[RBT_LEFT] or min in node->child[RBT_RIGHT], 
+   * and replace the_node with the target node. This maintains the binary 
+   * search tree property, but may violate the red-black properties.
+   */
+
+  if (the_node->child[RBT_LEFT] && the_node->child[RBT_RIGHT]) {
+    target = the_node->child[RBT_LEFT]; /* find max in node->child[RBT_LEFT] */
+    while (target->child[RBT_RIGHT]) target = target->child[RBT_RIGHT];
+
+    /* if the target node has a child, need to move it up the tree into 
+     * target's position (target is the right child of target->parent) 
+     * when target vacates it. if there is no child, then target->parent 
+     * should become NULL. This may cause the coloring to be violated.
+     * For now we store the color of the node being deleted in victim_color.
+     */
+     leaf = target->child[RBT_LEFT];
+    if(leaf) { 
+      leaf->parent = target->parent;
+    } else {
+      /* fix the tree here if the child is a null leaf. */
+      _RBTree_Extract_validate_unprotected(target);
+    }
+    victim_color = target->color;
+    dir = target != target->parent->child[0];
+    target->parent->child[dir] = leaf;
+
+    /* now replace the_node with target */
+    dir = the_node != the_node->parent->child[0];
+    the_node->parent->child[dir] = target;
+
+    /* set target's new children to the original node's children */
+    target->child[RBT_RIGHT] = the_node->child[RBT_RIGHT];
+    the_node->child[RBT_RIGHT]->parent = target;
+    target->child[RBT_LEFT] = the_node->child[RBT_LEFT];
+    the_node->child[RBT_LEFT]->parent = target;
+
+    /* finally, update the parent node and recolor. target has completely 
+     * replaced the_node, and target's child has moved up the tree if needed.
+     * the_node is no longer part of the tree, although it has valid pointers
+     * still.
+     */
+    target->parent = the_node->parent;
+    target->color = the_node->color;
+  } else { 
+    /* the_node has at most 1 non-null child. Move the child in to 
+     * the_node's location in the tree. This may cause the coloring to be 
+     * violated. We will fix it later.
+     * For now we store the color of the node being deleted in victim_color.
+     */
+    leaf = the_node->child[RBT_LEFT] ? 
+              the_node->child[RBT_LEFT] : the_node->child[RBT_RIGHT];
+    if( leaf ) {
+      leaf->parent = the_node->parent;
+    } else {
+      /* fix the tree here if the child is a null leaf. */
+      _RBTree_Extract_validate_unprotected(the_node);
+    }
+    victim_color = the_node->color;
+
+    /* remove the_node from the tree */
+    dir = the_node != the_node->parent->child[0];
+    the_node->parent->child[dir] = leaf;
+  }
+
+  /* fix coloring. leaf has moved up the tree. The color of the deleted 
+   * node is in victim_color. There are three cases:
+   *   1. Deleted a red node, its child must be black. Nothing must be done. 
+   *   2. Deleted a black node and the child is red. Paint child black.
+   *   3. Deleted a black node and its child is black. This requires some
+   *      care and rotations.
+   */
+  if (victim_color == RBT_BLACK) { /* eliminate case 1 */
+    if (_RBTree_Is_red(leaf))
+      leaf->color = RBT_BLACK; /* case 2 */
+    else if(leaf)
+      _RBTree_Extract_validate_unprotected(leaf); /* case 3 */
+  }
+
+  /* Wipe the_node */
+  _RBTree_Set_off_rbtree(the_node);
+
+  /* set root to black, if it exists */
+  if (the_rbtree->root) the_rbtree->root->color = RBT_BLACK;
+}
+
+
+/*
+ *  _RBTree_Extract
+ *
+ *  This kernel routine deletes the given node from a rbtree.
+ *
+ *  Input parameters:
+ *    node - pointer to node in rbtree to be deleted
+ *
+ *  Output parameters:  NONE
+ *
+ *  INTERRUPT LATENCY:
+ *    only case
+ */
+
+void _RBTree_Extract(
+  RBTree_Control *the_rbtree,
+  RBTree_Node *the_node
+)
+{
+  ISR_Level level;
+
+  _ISR_Disable( level );
+    _RBTree_Extract_unprotected( the_rbtree, the_node );
+  _ISR_Enable( level );
+}
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
new file mode 100644
index 0000000000..a11918ebde
--- /dev/null
+++ b/cpukit/score/src/rbtreefind.c
@@ -0,0 +1,52 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/*
+ *  _RBTree_Find
+ *
+ *  This kernel routine returns a pointer to the rbtree node containing the 
+ *  given value within the given tree, if it exists, or NULL otherwise. 
+ * 
+ *  Input parameters:
+ *    the_rbtree - pointer to rbtree control
+ *    the_value - value of the node to search for
+ *
+ *  Output parameters:
+ *    return_node - pointer to control header of rbtree
+ *    NULL   - if there is no control header available (the node is not part
+ *    of a tree)
+ *
+ *  INTERRUPT LATENCY:
+ *    only case
+ */
+
+RBTree_Node *_RBTree_Find(
+  RBTree_Control *the_rbtree,
+  unsigned int the_value
+)
+{
+  ISR_Level          level;
+  RBTree_Node *return_node;
+
+  return_node = NULL;
+  _ISR_Disable( level );
+      return_node = _RBTree_Find_unprotected( the_rbtree, the_value );
+  _ISR_Enable( level );
+  return return_node;
+}
diff --git a/cpukit/score/src/rbtreefindheader.c b/cpukit/score/src/rbtreefindheader.c
new file mode 100644
index 0000000000..f73514c3a7
--- /dev/null
+++ b/cpukit/score/src/rbtreefindheader.c
@@ -0,0 +1,50 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/*
+ *  _RBTree_Find_header
+ *
+ *  This kernel routine returns a pointer to the rbtree header of the tree
+ *  containing the given node.
+ *
+ *  Input parameters:
+ *    the_node - pointer to rbtree node
+ *
+ *  Output parameters:
+ *    return_header - pointer to control header of rbtree
+ *    NULL   - if there is no control header available (the node is not part
+ *    of a tree)
+ *
+ *  INTERRUPT LATENCY:
+ *    only case
+ */
+
+RBTree_Control *_RBTree_Find_header(
+  RBTree_Node *the_node
+)
+{
+  ISR_Level          level;
+  RBTree_Control *return_header;
+
+  return_header = NULL;
+  _ISR_Disable( level );
+      return_header = _RBTree_Find_header_unprotected( the_node );
+  _ISR_Enable( level );
+  return return_header;
+}
diff --git a/cpukit/score/src/rbtreeget.c b/cpukit/score/src/rbtreeget.c
new file mode 100644
index 0000000000..7e4c84db0a
--- /dev/null
+++ b/cpukit/score/src/rbtreeget.c
@@ -0,0 +1,52 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/*
+ *  _RBTree_Get
+ *
+ *  This kernel routine returns a pointer to a node taken from the
+ *  given rbtree.
+ *
+ *  Input parameters:
+ *    the_rbtree - pointer to rbtree header
+ *    dir - specifies min (0) or max (1)
+ *
+ *  Output parameters:
+ *    return_node - pointer to node in rbtree allocated
+ *    NULL   - if no nodes available
+ *
+ *  INTERRUPT LATENCY:
+ *    only case
+ */
+
+RBTree_Node *_RBTree_Get(
+  RBTree_Control *the_rbtree,
+  RBTree_Direction dir
+)
+{
+  ISR_Level          level;
+  RBTree_Node *return_node;
+
+  return_node = NULL;
+  _ISR_Disable( level );
+      return_node = _RBTree_Get_unprotected( the_rbtree, dir );
+  _ISR_Enable( level );
+  return return_node;
+}
+
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
new file mode 100644
index 0000000000..b9a7c994d8
--- /dev/null
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -0,0 +1,149 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/** @brief Validate and fix-up tree properties for a new insert/colored node
+ *
+ *  This routine checks and fixes the Red-Black Tree properties based on 
+ *  @a the_node being just added to the tree.
+ * 
+ *  @note It does NOT disable interrupts to ensure the atomicity of the
+ *        append operation.
+ */
+void _RBTree_Validate_insert_unprotected(
+    RBTree_Node    *the_node
+    )
+{
+  RBTree_Node *u,*g;
+
+  /* note: the insert root case is handled already */
+  /* if the parent is black, nothing needs to be done
+   * otherwise may need to loop a few times */
+  while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
+    u = _RBTree_Parent_sibling(the_node);
+    g = the_node->parent->parent;
+    
+    /* if uncle is red, repaint uncle/parent black and grandparent red */
+    if(_RBTree_Is_red(u)) {
+      the_node->parent->color = RBT_BLACK;
+      u->color = RBT_BLACK;
+      g->color = RBT_RED;
+      the_node = g;
+    } else { /* if uncle is black */
+      RBTree_Direction dir = the_node != the_node->parent->child[0];
+      RBTree_Direction pdir = the_node->parent != g->child[0];
+      
+      /* ensure node is on the same branch direction as parent */
+      if (dir != pdir) {
+        _RBTree_Rotate(the_node->parent, pdir);
+        the_node = the_node->child[pdir];
+      }
+      the_node->parent->color = RBT_BLACK;
+      g->color = RBT_RED;
+      
+      /* now rotate grandparent in the other branch direction (toward uncle) */
+      _RBTree_Rotate(g, (1-pdir));
+    }
+  }
+  if(!the_node->parent->parent) the_node->color = RBT_BLACK;
+}
+
+
+
+/** @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
+    )
+{
+  if(!the_node) return (RBTree_Node*)-1;
+
+  RBTree_Node *iter_node = the_rbtree->root;
+
+  if (!iter_node) { /* special case: first node inserted */
+    the_node->color = RBT_BLACK;
+    the_rbtree->root = the_node;
+    the_rbtree->first[0] = the_rbtree->first[1] = the_node;
+    the_node->parent = (RBTree_Node *) the_rbtree;
+    the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
+  } else { 
+    /* typical binary search tree insert, descend tree to leaf and insert */
+    while (iter_node) {
+      if(the_node->value == iter_node->value) return(iter_node);
+      RBTree_Direction dir = the_node->value > iter_node->value;
+      if (!iter_node->child[dir]) {
+        the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
+        the_node->color = RBT_RED;
+        iter_node->child[dir] = the_node;
+        the_node->parent = iter_node;
+        /* update min/max */
+        if (_RBTree_Is_first(the_rbtree, iter_node, dir)) {
+          the_rbtree->first[dir] = the_node;
+        }
+        break;
+      } else {
+        iter_node = iter_node->child[dir];
+      }
+
+    } /* while(iter_node) */
+    
+    /* verify red-black properties */
+    _RBTree_Validate_insert_unprotected(the_node);
+  }
+  return (RBTree_Node*)0;
+}
+
+
+/*
+ *  _RBTree_Insert
+ *
+ *  This kernel routine inserts a given node after a specified node
+ *  a requested rbtree.
+ *
+ *  Input parameters:
+ *    tree - pointer to RBTree Control for tree to insert to
+ *    node       - pointer to node to be inserted
+ *
+ *  Output parameters:  NONE
+ *
+ *  INTERRUPT LATENCY:
+ *    only case
+ */
+
+void _RBTree_Insert(
+  RBTree_Control *tree,
+  RBTree_Node *node
+)
+{
+  ISR_Level level;
+
+  _ISR_Disable( level );
+    _RBTree_Insert_unprotected( tree, node );
+  _ISR_Enable( level );
+}
diff --git a/cpukit/score/src/rbtreepeek.c b/cpukit/score/src/rbtreepeek.c
new file mode 100644
index 0000000000..3363197dc3
--- /dev/null
+++ b/cpukit/score/src/rbtreepeek.c
@@ -0,0 +1,51 @@
+/*
+ *  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$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/address.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/isr.h>
+
+/*
+ *  _RBTree_Get
+ *
+ *  This kernel routine returns a pointer to the min or max node on the tree, 
+ *  without removing that node.
+ *
+ *  Input parameters:
+ *    the_rbtree - pointer to rbtree header
+ *    dir - specifies whether to return minimum (0) or maximum (1)
+ *
+ *  Output parameters:
+ *    return_node - pointer to node in rbtree allocated
+ *    NULL   - if no nodes available
+ *
+ *  INTERRUPT LATENCY:
+ *    only case
+ */
+
+RBTree_Node *_RBTree_Peek(
+  RBTree_Control *the_rbtree,
+  RBTree_Direction dir
+)
+{
+  ISR_Level          level;
+  RBTree_Node *return_node;
+
+  return_node = NULL;
+  _ISR_Disable( level );
+      return_node = _RBTree_Peek_unprotected( the_rbtree, dir );
+  _ISR_Enable( level );
+  return return_node;
+}