2011-08-21 Petr Benes <benesp16@fel.cvut.cz>

	PR 1886/cpukit
	* 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/rbtreeinsert.c: This patch enables inserting duplicate keys
	into rbtree. It is possible to turn on this feature when initializing
	the tree.

7 files changed, 127 insertions, 38 deletions

diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog
index 91784af690..d64fb79846 100644
--- a/cpukit/ChangeLog
+++ b/cpukit/ChangeLog
@@ -1,3 +1,13 @@
+2011-08-21	Petr Benes <benesp16@fel.cvut.cz>
+
+	PR 1886/cpukit
+	* 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/rbtreeinsert.c: This patch enables inserting duplicate keys
+	into rbtree. It is possible to turn on this feature when initializing
+	the tree.
+
 2011-08-21	Joel Sherrill <joel.sherrilL@OARcorp.com>
 
 	PR 1890/cpukit
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
index 68f4ec697e..9a09b27650 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -43,6 +43,29 @@ typedef RBTree_Node rtems_rbtree_node;
 typedef RBTree_Control rtems_rbtree_control;
 
 /**
+ * @typedef rtems_rbtree_compare_function
+ *
+ * This type defines function pointers for user-provided comparison
+ * function. The function compares two nodes in order to determine
+ * the order in a red-black tree.
+ */
+typedef RBTree_Compare_function rtems_rbtree_compare_function;
+
+/**
+ * @typedef rtems_rbtree_unique
+ *
+ * This enum type defines whether the tree can contain nodes with
+ * duplicate keys.
+ */
+typedef enum {
+  /** The tree is not unique, insertion of duplicate keys is performed
+   *  in a FIFO manner. */
+  RTEMS_RBTREE_DUPLICATE = false,
+  /** The tree is unique, insertion of duplicate key is refused. */
+  RTEMS_RBTREE_UNIQUE    = true
+} rtems_rbtree_unique;
+
+/**
  *  @brief RBTree initializer for an empty rbtree with designator @a name.
  */
 #define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
index 52fdcb3f23..16a6e2a0c6 100644
--- a/cpukit/sapi/inline/rtems/rbtree.inl
+++ b/cpukit/sapi/inline/rtems/rbtree.inl
@@ -35,15 +35,16 @@
  *  @a starting_address.  Each node is of @a node_size bytes.
  */
 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
-  rtems_rbtree_control *the_rbtree,
-  void                 *compare_function,
-  void                 *starting_address,
-  size_t                number_nodes,
-  size_t                node_size
+  rtems_rbtree_control          *the_rbtree,
+  rtems_rbtree_compare_function  compare_function,
+  void                          *starting_address,
+  size_t                         number_nodes,
+  size_t                         node_size,
+  rtems_rbtree_unique            is_unique
 )
 {
   _RBTree_Initialize( the_rbtree, compare_function, starting_address,
-    number_nodes, node_size);
+    number_nodes, node_size, is_unique);
 }
 
 /**
@@ -52,11 +53,12 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
  *  This routine initializes @a the_rbtree to contain zero nodes.
  */
 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
-  rtems_rbtree_control *the_rbtree,
-  void                 *compare_function
+  rtems_rbtree_control          *the_rbtree,
+  rtems_rbtree_compare_function  compare_function,
+  rtems_rbtree_unique            is_unique
 )
 {
-  _RBTree_Initialize_empty( the_rbtree, compare_function );
+  _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
 }
 
 /**
@@ -257,6 +259,9 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
  *  This function returns a pointer to the node having key equal to the key
  *  of @a the_node if it exists within @a the_rbtree, and NULL if not.
  *  @a the_node has to be made up before a search.
+ *
+ *  @note If the tree is not unique and contains duplicate keys, the set
+ *        of duplicate keys acts as FIFO.
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
   rtems_rbtree_control *the_rbtree,
@@ -382,13 +387,27 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
  *
  *  This routine inserts @a the_node on @a the_rbtree.
  *  It disables interrupts to ensure the atomicity of the insert operation.
+ *
+ *  @retval 0 Successfully inserted.
+ *  @retval -1 NULL @a the_node.
+ *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
+ *          in an unique @a the_rbtree.
  */
-RTEMS_INLINE_ROUTINE void rtems_rbtree_insert(
+RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
   rtems_rbtree_control *the_rbtree,
   rtems_rbtree_node *the_node
 )
 {
-  _RBTree_Insert( the_rbtree, the_node );
+  return _RBTree_Insert( the_rbtree, the_node );
+}
+
+/** @brief Determines whether the tree is unique
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique(
+    rtems_rbtree_control *the_rbtree
+)
+{
+  return( _RBTree_Is_unique(the_rbtree) );
 }
 
 #endif
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index 8a9e11f795..d2cea57208 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -100,6 +100,16 @@ typedef enum {
 } RBTree_Direction;
 
 /**
+ * This type defines function pointers for user-provided comparison
+ * function. The function compares two nodes in order to determine
+ * the order in a red-black tree.
+ */
+typedef int (*RBTree_Compare_function)(
+    RBTree_Node *node1,
+    RBTree_Node *node2
+);
+
+/**
  *  @struct RBTree_Control
  *
  * This is used to manage a RBT.  A rbtree consists of a tree of zero or more
@@ -126,11 +136,13 @@ typedef struct {
   /** This points to the min and max nodes of this RBT. */
   RBTree_Node *first[2];
   /**
-   * Comparison function pointer. Keys to compare has to be found
+   * Comparison function pointer. Keys to compare have to be found
    * inside to maintain generality. It has to return 1 if first node
    * has higher key than second, -1 if lower, 0 if equal.
    */
-  int (*compare_function) (RBTree_Node*, RBTree_Node*);
+  RBTree_Compare_function compare_function;
+  /** Determines whether the tree accepts duplicate keys. */
+  bool is_unique;
 } RBTree_Control;
 
 /**
@@ -142,7 +154,8 @@ typedef struct {
   .root = NULL, \
   .first[0] = NULL, \
   .first[1] = NULL, \
-  .compare_function = NULL \
+  .compare_function = NULL, \
+  .is_unique = 0 \
 }
 
 /**
@@ -176,11 +189,12 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
  *  @a starting_address.  Each node is of @a node_size bytes.
  */
 void _RBTree_Initialize(
-  RBTree_Control *the_rbtree,
-  void           *compare_function,
-  void           *starting_address,
-  size_t          number_nodes,
-  size_t          node_size
+  RBTree_Control          *the_rbtree,
+  RBTree_Compare_function  compare_function,
+  void                    *starting_address,
+  size_t                   number_nodes,
+  size_t                   node_size,
+  bool                     is_unique
 );
 
 /**
@@ -247,8 +261,8 @@ RBTree_Control *_RBTree_Find_header(
  *
  *  @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.
+ *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
+ *          in an unique @a the_rbtree.
  *
  *  @note It does NOT disable interrupts to ensure the atomicity
  *        of the extract operation.
@@ -263,10 +277,15 @@ RBTree_Node *_RBTree_Insert_unprotected(
  *
  *  This routine inserts @a the_node on the 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 's key exists
+ *          in an unique @a the_rbtree.
+ *
  *  @note It disables interrupts to ensure the atomicity
  *  of the extract operation.
  */
-void _RBTree_Insert(
+RBTree_Node *_RBTree_Insert(
   RBTree_Control *the_rbtree,
   RBTree_Node *the_node
 );
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index 08eddfecba..bbc60477c8 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -235,8 +235,9 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
  *  This routine initializes @a the_rbtree to contain zero nodes.
  */
 RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
-    RBTree_Control *the_rbtree,
-    void           *compare_function
+    RBTree_Control          *the_rbtree,
+    RBTree_Compare_function  compare_function,
+    bool                     is_unique
     )
 {
   the_rbtree->permanent_null   = NULL;
@@ -244,6 +245,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
   the_rbtree->first[0]         = NULL;
   the_rbtree->first[1]         = NULL;
   the_rbtree->compare_function = compare_function;
+  the_rbtree->is_unique        = is_unique;
 }
 
 /** @brief Return a pointer to node's grandparent
@@ -317,6 +319,9 @@ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected(
  *  This function returns a pointer to the node in @a the_rbtree 
  *  having key equal to key of  @a the_node if it exists,
  *  and NULL if not. @a the_node has to be made up before a search.
+ *
+ *  @note If the tree is not unique and contains duplicate keys, the set
+ *        of duplicate keys acts as FIFO.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
     RBTree_Control *the_rbtree,
@@ -324,18 +329,21 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
     )
 {
   RBTree_Node* iter_node = the_rbtree->root;
+  RBTree_Node* found = NULL;
   int compare_result;
   while (iter_node) {
     compare_result = the_rbtree->compare_function(the_node, iter_node);
     if (compare_result == 0) {
-        return(iter_node);
+      found = iter_node;
+      if ( the_rbtree->is_unique )
+        break;
     }
 
-    RBTree_Direction dir = (compare_result != -1);
+    RBTree_Direction dir = (compare_result == 1);
     iter_node = iter_node->child[dir];
   } /* while(iter_node) */
 
-  return 0;
+  return found;
 }
 
 /** @brief Find the nodes in-order predecessor
@@ -428,7 +436,6 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
   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];
@@ -443,6 +450,15 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
   c->parent = the_node->parent;
   the_node->parent = c;
 }
+
+/** @brief Determines whether the tree is unique
+ */
+RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
+    RBTree_Control *the_rbtree
+)
+{
+  return( the_rbtree && the_rbtree->is_unique );
+}
 /**@}*/
 
 #endif
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
index eb3af773cb..e0fc560229 100644
--- a/cpukit/score/src/rbtree.c
+++ b/cpukit/score/src/rbtree.c
@@ -32,11 +32,12 @@
  */
 
 void _RBTree_Initialize(
-  RBTree_Control *the_rbtree,
-  void           *compare_function,
-  void           *starting_address,
-  size_t         number_nodes,
-  size_t         node_size
+  RBTree_Control          *the_rbtree,
+  RBTree_Compare_function  compare_function,
+  void                    *starting_address,
+  size_t                   number_nodes,
+  size_t                   node_size,
+  bool                     is_unique
 )
 {
   size_t      count;
@@ -46,7 +47,7 @@ void _RBTree_Initialize(
   if (!the_rbtree) return;
 
   /* could do sanity checks here */
-  _RBTree_Initialize_empty(the_rbtree, compare_function);
+  _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
 
   count = number_nodes;
   next  = starting_address;
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index bb1915de54..1208a3c81a 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -72,7 +72,7 @@ void _RBTree_Validate_insert_unprotected(
  *  @retval 0 Successfully inserted.
  *  @retval -1 NULL @a the_node.
  *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
- *          in @a the_rbtree.
+ *          in an unique @a the_rbtree.
  *
  *  @note It does NOT disable interrupts to ensure the atomicity
  *        of the extract operation.
@@ -97,7 +97,8 @@ RBTree_Node *_RBTree_Insert_unprotected(
     /* typical binary search tree insert, descend tree to leaf and insert */
     while (iter_node) {
       compare_result = the_rbtree->compare_function(the_node, iter_node);
-      if ( !compare_result ) return iter_node;
+      if ( the_rbtree->is_unique && !compare_result )
+        return iter_node;
       RBTree_Direction dir = (compare_result != -1);
       if (!iter_node->child[dir]) {
         the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
@@ -138,7 +139,7 @@ RBTree_Node *_RBTree_Insert_unprotected(
  *    only case
  */
 
-void _RBTree_Insert(
+RBTree_Node *_RBTree_Insert(
   RBTree_Control *tree,
   RBTree_Node *node
 )
@@ -146,6 +147,6 @@ void _RBTree_Insert(
   ISR_Level level;
 
   _ISR_Disable( level );
-    _RBTree_Insert_unprotected( tree, node );
+    return _RBTree_Insert_unprotected( tree, node );
   _ISR_Enable( level );
 }