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, 149 insertions, 0 deletions

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