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). --- cpukit/score/include/rtems/score/rbtree.h | 16 ++-- cpukit/score/src/rbtreeinsert.c | 4 +- testsuites/sptests/sprbtree01/init.c | 111 +++++++++++++++++++++++++-- testsuites/sptests/sprbtree01/sprbtree01.scn | 5 +- 4 files changed, 118 insertions(+), 18 deletions(-)
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index b3f2ed4..2ec77ea 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -219,15 +219,16 @@ RBTree_Node *_RBTree_Find( ); /** - * @brief Insert @a the_node on the Red-Black Tree @a the_rbtree. + * @brief Inserts the node into the red-black tree. * - * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree. + * 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. * @param[in] the_node The node to insert. * @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. * @retval existing_node This is a unique insert and there exists a node with @@ -487,19 +488,20 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( } /** - * @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. * @param[in] dir Specifies whether to get a node with the minimum (RBT_LEFT) * or maximum (RBT_RIGHT) key value. * * @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. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get( diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index b31c8e7..afff1ef 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -96,8 +96,8 @@ RBTree_Node *_RBTree_Insert( ); 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; } diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index 956271b..2c62d12 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -19,11 +19,13 @@ const char rtems_test_name[] = "SPRBTREE 1"; /* forward declarations to avoid warnings */ 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}; +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 +}; -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_sorted[20] = { + 0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99 +}; typedef struct { int id; @@ -121,11 +123,104 @@ static int rb_assert ( rtems_rbtree_node *root ) } } +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 ); -rtems_task Init( - rtems_task_argument ignored - ) + 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; rtems_rbtree_node *p; @@ -682,6 +777,8 @@ rtems_task Init( rtems_test_exit(0); } + test_rbtree_min_max(); + TEST_END(); rtems_test_exit(0); } diff --git a/testsuites/sptests/sprbtree01/sprbtree01.scn b/testsuites/sptests/sprbtree01/sprbtree01.scn index 0bf2007..0d37566 100644 --- a/testsuites/sptests/sprbtree01/sprbtree01.scn +++ b/testsuites/sptests/sprbtree01/sprbtree01.scn @@ -1,4 +1,4 @@ -*** TEST OF RTEMS RBTREE API *** +*** BEGIN OF TEST SPRBTREE 1 *** Init - Initialize rbtree empty INIT - Verify rtems_rbtree_insert with two nodes INIT - Verify rtems_rbtree_insert with the same value twice @@ -31,4 +31,5 @@ INIT - Removing 100 nodes INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0] 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 *** -- 1.8.1.4 _______________________________________________ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel