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.

2 files changed, 53 insertions, 11 deletions

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