Changeset 74f1c73e in rtems

Timestamp:

08/21/11 20:07:11 (11 years ago)

Author:

Joel Sherrill <joel.sherrill@…>

Branches:

4.11, 5, master

Children:

611909e

Parents:

08ef1631

Message:

2011-08-21 Petr Benes <benesp16@…>

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.

Location:

cpukit

Files:

• ChangeLog (modified) (1 diff)
• sapi/include/rtems/rbtree.h (modified) (1 diff)
• sapi/inline/rtems/rbtree.inl (modified) (4 diffs)
• score/include/rtems/score/rbtree.h (modified) (6 diffs)
• score/inline/rtems/score/rbtree.inl (modified) (6 diffs)
• score/src/rbtree.c (modified) (2 diffs)
• score/src/rbtreeinsert.c (modified) (4 diffs)

cpukit/ChangeLog

@@ +1 @@
+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>
 

cpukit/sapi/include/rtems/rbtree.h

@@ -44 +44 @@
 
 /**
+ * @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.
  */

cpukit/sapi/inline/rtems/rbtree.inl

@@ -36 +36 @@
  */
 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);
 }
 
@@ -53 +54 @@
  */
 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
-  rtems_rbtree_control *the_rbtree,
-  void                 *compare_function
-)
-{
-  _RBTree_Initialize_empty( the_rbtree, 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, is_unique );
 }
 
@@ -258 +260 @@
  *  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(
@@ -383 +388 @@
  *  This routine inserts @a the_node on @a the_rbtree.
  *  It disables interrupts to ensure the atomicity of the insert operation.
- */
-RTEMS_INLINE_ROUTINE void rtems_rbtree_insert(
+ *
+ *  @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 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) );
 }
 

cpukit/score/include/rtems/score/rbtree.h

@@ -101 +101 @@
 
 /**
+ * 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
  *
@@ -127 +137 @@
   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;
 
@@ -143 +155 @@
   .first[0] = NULL, \
   .first[1] = NULL, \
-  .compare_function = NULL \
+  .compare_function = NULL, \
+  .is_unique = 0 \
 }
 
@@ -177 +190 @@
  */
 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
 );
 
@@ -248 +262 @@
  *  @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
@@ -264 +278 @@
  *  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

cpukit/score/inline/rtems/score/rbtree.inl

@@ -236 +236 @@
  */
 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
     )
 {
@@ -245 +246 @@
   the_rbtree->first[1]         = NULL;
   the_rbtree->compare_function = compare_function;
+  the_rbtree->is_unique        = is_unique;
 }
 
@@ -318 +320 @@
  *  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(
@@ -325 +330 @@
 {
   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;
 }
 
@@ -429 +437 @@
   if (the_node == NULL) return;
   if (the_node->child[(1-dir)] == NULL) return;
-  
 
   c = the_node->child[(1-dir)];
@@ -444 +451 @@
   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 );
+}
 /**@}*/
 

cpukit/score/src/rbtree.c

@@ -33 +33 @@
 
 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
 )
 {
@@ -47 +48 @@
 
   /* could do sanity checks here */
-  _RBTree_Initialize_empty(the_rbtree, compare_function);
+  _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique);
 
   count = number_nodes;

cpukit/score/src/rbtreeinsert.c

@@ -73 +73 @@
  *  @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
@@ -98 +98 @@
     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]) {
@@ -139 +140 @@
  */
 
-void _RBTree_Insert(
+RBTree_Node *_RBTree_Insert(
   RBTree_Control *tree,
   RBTree_Node *node
@@ -147 +148 @@
 
   _ISR_Disable( level );
-    _RBTree_Insert_unprotected( tree, node );
+    return _RBTree_Insert_unprotected( tree, node );
   _ISR_Enable( level );
 }