Changeset 639117f in rtems

Timestamp:

07/22/14 12:50:07 (9 years ago)

Author:

Sebastian Huber <sebastian.huber@…>

Branches:

4.11, 5, master

Children:

4cd55724

Parents:

9113798c

git-author:

Sebastian Huber <sebastian.huber@…> (07/22/14 12:50:07)

git-committer:

Sebastian Huber <sebastian.huber@…> (07/26/14 10:01:25)

Message:

rbtree: Update maximum node in LIFO order

The test sptests/sp35 showed a NULL pointer access due to an invalid
maximum node field (e.g. a tree with one element and NULL as the maximum
node).

Files:

• cpukit/score/include/rtems/score/rbtree.h (modified) (4 diffs)
• cpukit/score/src/rbtreeinsert.c (modified) (1 diff)
• testsuites/sptests/sprbtree01/init.c (modified) (3 diffs)
• testsuites/sptests/sprbtree01/sprbtree01.scn (modified) (2 diffs)

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

@@ -220 +220 @@
 
 /**
- *  @brief Insert @a the_node on the Red-Black Tree @a the_rbtree.
- *
- *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
+ * @brief Inserts the node into the red-black tree.
+ *
+ * In case the node is already a node of a tree, then this function yields
+ * unpredictable results.
  *
  * @param[in] the_rbtree The red-black tree control.
@@ -228 +229 @@
  * @param[in] compare The node compare function.
  * @param[in] is_unique If true, then reject nodes with a duplicate key, else
- *   otherwise.
+ *   insert nodes in FIFO order in case the key value is equal to existing nodes.
  *
  * @retval NULL Successfully inserted.
@@ -488 +489 @@
 
 /**
- * @brief Gets a node with an extremal key value.
+ * @brief Gets a node with an extremal key value from the red-black tree.
  *
  * This function extracts a node with the minimum or maximum key value from
  * tree and returns a pointer to that node if it exists.  In case multiple
- * nodes with an extremal key value exist, then they are extracted in FIFO
- * order.
+ * nodes with a minimum key value exist, then they are extracted in FIFO order.
+ * In case multiple nodes with a maximum key value exist, then they are
+ * extracted in LIFO order.
  *
  * @param[in] the_rbtree The red-black tree control.
@@ -500 +502 @@
  *
  * @retval NULL The tree is empty.
- * @retval extremal_node A node with the minimal or maximal key value on the
+ * @retval extremal_node A node with a minimal or maximal key value on the
  *   tree.
  */

cpukit/score/src/rbtreeinsert.c

@@ -97 +97 @@
 
         if (
-          ( !dir && _RBTree_Is_lesser( compare_result ) )
-            || ( dir && _RBTree_Is_greater( compare_result ) )
+          ( dir == RBT_LEFT && _RBTree_Is_lesser( compare_result ) )
+            || ( dir == RBT_RIGHT && !_RBTree_Is_lesser( compare_result ) )
         ) {
           the_rbtree->first[ dir ] = the_node;

testsuites/sptests/sprbtree01/init.c

@@ -20 +20 @@
 rtems_task Init(rtems_task_argument argument);
 
-int numbers[20] = {
-52, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71};
-
-int numbers_sorted[20] = {
-  0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99};
+static const int numbers[20] = {
+  52, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71
+};
+
+static const int numbers_sorted[20] = {
+  0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99
+};
 
 typedef struct {
@@ -122 +124 @@
 }
 
-
-
-rtems_task Init(
-    rtems_task_argument ignored
-    )
+static test_node some_nodes[] = {
+  { .key = 1 },
+  { .key = 1 },
+  { .key = 1 },
+  { .key = 2 },
+  { .key = 2 },
+  { .key = 2 }
+};
+
+static void min_max_insert(
+  rtems_rbtree_control *tree,
+  rtems_rbtree_node    *node,
+  rtems_rbtree_node    *min,
+  rtems_rbtree_node    *max
+)
+{
+  rb_insert_multi( tree, node );
+  rtems_test_assert( rb_assert( tree->root ) != -1 );
+  rtems_test_assert( tree->first[ 0 ] == min );
+  rtems_test_assert( tree->first[ 1 ] == max );
+}
+
+static void min_max_extract(
+  rtems_rbtree_control *tree,
+  rtems_rbtree_node    *node,
+  rtems_rbtree_node    *min,
+  rtems_rbtree_node    *max
+)
+{
+  rtems_rbtree_extract( tree, node );
+  rtems_test_assert( rb_assert( tree->root ) != -1 );
+  rtems_test_assert( tree->first[ 0 ] == min );
+  rtems_test_assert( tree->first[ 1 ] == max );
+}
+
+static void test_rbtree_min_max(void)
+{
+  rtems_rbtree_control  tree;
+  rtems_rbtree_node    *node;
+  rtems_rbtree_node    *min;
+  rtems_rbtree_node    *max;
+
+  puts( "INIT - Verify min/max node updates" );
+
+  rtems_rbtree_initialize_empty( &tree );
+  rtems_test_assert( rb_assert( tree.root ) == 1 );
+
+  node = &some_nodes[ 0 ].Node;
+  min = node;
+  max = node;
+  min_max_insert( &tree, node, min, max );
+
+  node = &some_nodes[ 1 ].Node;
+  max = node;
+  min_max_insert( &tree, node, min, max );
+
+  node = &some_nodes[ 2 ].Node;
+  max = node;
+  min_max_insert( &tree, node, min, max );
+
+  node = &some_nodes[ 3 ].Node;
+  max = node;
+  min_max_insert( &tree, node, min, max );
+
+  node = &some_nodes[ 4 ].Node;
+  max = node;
+  min_max_insert( &tree, node, min, max );
+
+  node = &some_nodes[ 5 ].Node;
+  max = node;
+  min_max_insert( &tree, node, min, max );
+
+  node = &some_nodes[ 1 ].Node;
+  min_max_extract( &tree, node, min, max );
+
+  node = &some_nodes[ 4 ].Node;
+  min_max_extract( &tree, node, min, max );
+
+  node = &some_nodes[ 0 ].Node;
+  min = &some_nodes[ 2 ].Node;
+  min_max_extract( &tree, node, min, max );
+
+  node = &some_nodes[ 5 ].Node;
+  max = &some_nodes[ 3 ].Node;
+  min_max_extract( &tree, node, min, max );
+
+  node = &some_nodes[ 2 ].Node;
+  min = &some_nodes[ 3 ].Node;
+  min_max_extract( &tree, node, min, max );
+
+  node = &some_nodes[ 3 ].Node;
+  min = NULL;
+  max = NULL;
+  min_max_extract( &tree, node, min, max );
+  rtems_test_assert( rtems_rbtree_is_empty( &tree ) );
+}
+
+rtems_task Init( rtems_task_argument ignored )
 {
   rtems_rbtree_control  rbtree1;
@@ -683 +778 @@
   }
 
+  test_rbtree_min_max();
+
   TEST_END();
   rtems_test_exit(0);

testsuites/sptests/sprbtree01/sprbtree01.scn

@@ -1 @@
-*** TEST OF RTEMS RBTREE API ***
+*** BEGIN OF TEST SPRBTREE 1 ***
 Init - Initialize rbtree empty
 INIT - Verify rtems_rbtree_insert with two nodes
@@ -32 +32 @@
 INIT - Verify rtems_rbtree_find in a duplicate tree
 INIT - Removing 100 nodes
-*** END OF RTEMS RBTREE API TEST ***
+INIT - Verify min/max node updates
+*** END OF TEST SPRBTREE 1 ***