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.

7 files changed, 657 insertions, 0 deletions

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;
+}