Changeset d472d21 in rtems


Ignore:
Timestamp:
08/05/14 12:07:07 (8 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 5, master
Children:
4752550f
Parents:
888edf6
git-author:
Sebastian Huber <sebastian.huber@…> (08/05/14 12:07:07)
git-committer:
Sebastian Huber <sebastian.huber@…> (08/05/14 13:17:51)
Message:

sptests/sprbtree01: Check tree layout

File:
1 edited

Legend:

Unmodified
Added
Removed

  • testsuites/sptests/sprbtree01/init.c

    r888edf6 rd472d21  
    221221  min_max_extract( &tree, node, min, max );
    222222  rtems_test_assert( rtems_rbtree_is_empty( &tree ) );
     223}
     224
     225#define TN( i ) &node_array[ i ].Node
     226
     227typedef struct {
     228  int key;
     229  const rtems_rbtree_node *parent;
     230  const rtems_rbtree_node *left;
     231  const rtems_rbtree_node *right;
     232  RBTree_Color color;
     233} test_node_description;
     234
     235static const test_node_description test_insert_tree_0[] = {
     236  { 52, NULL, NULL, NULL , RBT_BLACK }
     237};
     238
     239static const test_node_description test_insert_tree_1[] = {
     240  { 52, NULL, NULL, TN( 1 ) , RBT_BLACK },
     241  { 99, TN( 0 ), NULL, NULL , RBT_RED }
     242};
     243
     244static const test_node_description test_insert_tree_2[] = {
     245  { 0, TN( 0 ), NULL, NULL , RBT_RED },
     246  { 52, NULL, TN( 2 ), TN( 1 ) , RBT_BLACK },
     247  { 99, TN( 0 ), NULL, NULL , RBT_RED }
     248};
     249
     250static const test_node_description test_insert_tree_3[] = {
     251  { 0, TN( 0 ), NULL, NULL , RBT_BLACK },
     252  { 52, NULL, TN( 2 ), TN( 1 ) , RBT_BLACK },
     253  { 85, TN( 1 ), NULL, NULL , RBT_RED },
     254  { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK }
     255};
     256
     257static const test_node_description test_insert_tree_4[] = {
     258  { 0, TN( 0 ), NULL, TN( 4 ) , RBT_BLACK },
     259  { 43, TN( 2 ), NULL, NULL , RBT_RED },
     260  { 52, NULL, TN( 2 ), TN( 1 ) , RBT_BLACK },
     261  { 85, TN( 1 ), NULL, NULL , RBT_RED },
     262  { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK }
     263};
     264
     265static const test_node_description test_insert_tree_5[] = {
     266  { 0, TN( 4 ), NULL, NULL , RBT_RED },
     267  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_BLACK },
     268  { 44, TN( 4 ), NULL, NULL , RBT_RED },
     269  { 52, NULL, TN( 4 ), TN( 1 ) , RBT_BLACK },
     270  { 85, TN( 1 ), NULL, NULL , RBT_RED },
     271  { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK }
     272};
     273
     274static const test_node_description test_insert_tree_6[] = {
     275  { 0, TN( 4 ), NULL, TN( 6 ) , RBT_BLACK },
     276  { 10, TN( 2 ), NULL, NULL , RBT_RED },
     277  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_RED },
     278  { 44, TN( 4 ), NULL, NULL , RBT_BLACK },
     279  { 52, NULL, TN( 4 ), TN( 1 ) , RBT_BLACK },
     280  { 85, TN( 1 ), NULL, NULL , RBT_RED },
     281  { 99, TN( 0 ), TN( 3 ), NULL , RBT_BLACK }
     282};
     283
     284static const test_node_description test_insert_tree_7[] = {
     285  { 0, TN( 4 ), NULL, TN( 6 ) , RBT_BLACK },
     286  { 10, TN( 2 ), NULL, NULL , RBT_RED },
     287  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_RED },
     288  { 44, TN( 4 ), NULL, NULL , RBT_BLACK },
     289  { 52, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK },
     290  { 60, TN( 3 ), NULL, NULL , RBT_RED },
     291  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK },
     292  { 99, TN( 3 ), NULL, NULL , RBT_RED }
     293};
     294
     295static const test_node_description test_insert_tree_8[] = {
     296  { 0, TN( 4 ), NULL, TN( 6 ) , RBT_BLACK },
     297  { 10, TN( 2 ), NULL, NULL , RBT_RED },
     298  { 43, TN( 0 ), TN( 2 ), TN( 5 ) , RBT_RED },
     299  { 44, TN( 4 ), NULL, TN( 8 ) , RBT_BLACK },
     300  { 50, TN( 5 ), NULL, NULL , RBT_RED },
     301  { 52, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK },
     302  { 60, TN( 3 ), NULL, NULL , RBT_RED },
     303  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK },
     304  { 99, TN( 3 ), NULL, NULL , RBT_RED }
     305};
     306
     307static const test_node_description test_insert_tree_9[] = {
     308  { 0, TN( 6 ), NULL, NULL , RBT_RED },
     309  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     310  { 19, TN( 6 ), NULL, NULL , RBT_RED },
     311  { 43, TN( 0 ), TN( 6 ), TN( 5 ) , RBT_RED },
     312  { 44, TN( 4 ), NULL, TN( 8 ) , RBT_BLACK },
     313  { 50, TN( 5 ), NULL, NULL , RBT_RED },
     314  { 52, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK },
     315  { 60, TN( 3 ), NULL, NULL , RBT_RED },
     316  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK },
     317  { 99, TN( 3 ), NULL, NULL , RBT_RED }
     318};
     319
     320static const test_node_description test_insert_tree_10[] = {
     321  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     322  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     323  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_RED },
     324  { 19, TN( 6 ), NULL, NULL , RBT_BLACK },
     325  { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK },
     326  { 44, TN( 0 ), NULL, TN( 8 ) , RBT_BLACK },
     327  { 50, TN( 5 ), NULL, NULL , RBT_RED },
     328  { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RBT_RED },
     329  { 60, TN( 3 ), NULL, NULL , RBT_RED },
     330  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_BLACK },
     331  { 99, TN( 3 ), NULL, NULL , RBT_RED }
     332};
     333
     334static const test_node_description test_insert_tree_11[] = {
     335  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     336  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     337  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     338  { 19, TN( 6 ), NULL, NULL , RBT_BLACK },
     339  { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK },
     340  { 44, TN( 0 ), NULL, TN( 8 ) , RBT_BLACK },
     341  { 50, TN( 5 ), NULL, NULL , RBT_RED },
     342  { 52, TN( 4 ), TN( 5 ), TN( 3 ) , RBT_BLACK },
     343  { 60, TN( 3 ), NULL, TN( 11 ) , RBT_BLACK },
     344  { 68, TN( 7 ), NULL, NULL , RBT_RED },
     345  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED },
     346  { 99, TN( 3 ), NULL, NULL , RBT_BLACK }
     347};
     348
     349static const test_node_description test_insert_tree_12[] = {
     350  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     351  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     352  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     353  { 19, TN( 6 ), NULL, NULL , RBT_BLACK },
     354  { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK },
     355  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     356  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     357  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     358  { 52, TN( 4 ), TN( 12 ), TN( 3 ) , RBT_BLACK },
     359  { 60, TN( 3 ), NULL, TN( 11 ) , RBT_BLACK },
     360  { 68, TN( 7 ), NULL, NULL , RBT_RED },
     361  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED },
     362  { 99, TN( 3 ), NULL, NULL , RBT_BLACK }
     363};
     364
     365static const test_node_description test_insert_tree_13[] = {
     366  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     367  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     368  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     369  { 19, TN( 6 ), NULL, NULL , RBT_BLACK },
     370  { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK },
     371  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     372  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     373  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     374  { 52, TN( 4 ), TN( 12 ), TN( 3 ) , RBT_BLACK },
     375  { 57, TN( 7 ), NULL, NULL , RBT_RED },
     376  { 60, TN( 3 ), TN( 13 ), TN( 11 ) , RBT_BLACK },
     377  { 68, TN( 7 ), NULL, NULL , RBT_RED },
     378  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED },
     379  { 99, TN( 3 ), NULL, NULL , RBT_BLACK }
     380};
     381
     382static const test_node_description test_insert_tree_14[] = {
     383  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     384  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     385  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     386  { 17, TN( 9 ), NULL, NULL , RBT_RED },
     387  { 19, TN( 6 ), TN( 14 ), NULL , RBT_BLACK },
     388  { 43, NULL, TN( 6 ), TN( 0 ) , RBT_BLACK },
     389  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     390  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     391  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     392  { 52, TN( 4 ), TN( 12 ), TN( 3 ) , RBT_BLACK },
     393  { 57, TN( 7 ), NULL, NULL , RBT_RED },
     394  { 60, TN( 3 ), TN( 13 ), TN( 11 ) , RBT_BLACK },
     395  { 68, TN( 7 ), NULL, NULL , RBT_RED },
     396  { 85, TN( 0 ), TN( 7 ), TN( 1 ) , RBT_RED },
     397  { 99, TN( 3 ), NULL, NULL , RBT_BLACK }
     398};
     399
     400static const test_node_description test_insert_tree_15[] = {
     401  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     402  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     403  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     404  { 17, TN( 9 ), NULL, NULL , RBT_RED },
     405  { 19, TN( 6 ), TN( 14 ), NULL , RBT_BLACK },
     406  { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK },
     407  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     408  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     409  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     410  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED },
     411  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     412  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK },
     413  { 67, TN( 11 ), NULL, NULL , RBT_RED },
     414  { 68, TN( 3 ), TN( 15 ), NULL , RBT_BLACK },
     415  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED },
     416  { 99, TN( 3 ), NULL, NULL , RBT_BLACK }
     417};
     418
     419static const test_node_description test_insert_tree_16[] = {
     420  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     421  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     422  { 10, TN( 4 ), TN( 2 ), TN( 9 ) , RBT_BLACK },
     423  { 17, TN( 9 ), NULL, NULL , RBT_RED },
     424  { 19, TN( 6 ), TN( 14 ), NULL , RBT_BLACK },
     425  { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK },
     426  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     427  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     428  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     429  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED },
     430  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     431  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK },
     432  { 67, TN( 11 ), NULL, NULL , RBT_RED },
     433  { 68, TN( 3 ), TN( 15 ), NULL , RBT_BLACK },
     434  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED },
     435  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     436  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     437};
     438
     439static const test_node_description test_insert_tree_17[] = {
     440  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     441  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     442  { 10, TN( 4 ), TN( 2 ), TN( 14 ) , RBT_BLACK },
     443  { 12, TN( 14 ), NULL, NULL , RBT_RED },
     444  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK },
     445  { 19, TN( 14 ), NULL, NULL , RBT_RED },
     446  { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK },
     447  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     448  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     449  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     450  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED },
     451  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     452  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK },
     453  { 67, TN( 11 ), NULL, NULL , RBT_RED },
     454  { 68, TN( 3 ), TN( 15 ), NULL , RBT_BLACK },
     455  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED },
     456  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     457  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     458};
     459
     460static const test_node_description test_insert_tree_18[] = {
     461  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     462  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     463  { 10, TN( 4 ), TN( 2 ), TN( 14 ) , RBT_BLACK },
     464  { 12, TN( 14 ), NULL, NULL , RBT_RED },
     465  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK },
     466  { 19, TN( 14 ), NULL, NULL , RBT_RED },
     467  { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK },
     468  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     469  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     470  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     471  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_RED },
     472  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     473  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_BLACK },
     474  { 67, TN( 11 ), NULL, NULL , RBT_RED },
     475  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_BLACK },
     476  { 77, TN( 11 ), NULL, NULL , RBT_RED },
     477  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_RED },
     478  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     479  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     480};
     481
     482static const test_node_description test_insert_tree_19[] = {
     483  { 0, TN( 6 ), NULL, TN( 10 ) , RBT_BLACK },
     484  { 8, TN( 2 ), NULL, NULL , RBT_RED },
     485  { 10, TN( 4 ), TN( 2 ), TN( 14 ) , RBT_BLACK },
     486  { 12, TN( 14 ), NULL, NULL , RBT_RED },
     487  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK },
     488  { 19, TN( 14 ), NULL, NULL , RBT_RED },
     489  { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK },
     490  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     491  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     492  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     493  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     494  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     495  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED },
     496  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     497  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     498  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     499  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     500  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     501  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     502  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     503};
     504
     505static const test_node_description *const test_insert_trees[] = {
     506  &test_insert_tree_0[ 0 ],
     507  &test_insert_tree_1[ 0 ],
     508  &test_insert_tree_2[ 0 ],
     509  &test_insert_tree_3[ 0 ],
     510  &test_insert_tree_4[ 0 ],
     511  &test_insert_tree_5[ 0 ],
     512  &test_insert_tree_6[ 0 ],
     513  &test_insert_tree_7[ 0 ],
     514  &test_insert_tree_8[ 0 ],
     515  &test_insert_tree_9[ 0 ],
     516  &test_insert_tree_10[ 0 ],
     517  &test_insert_tree_11[ 0 ],
     518  &test_insert_tree_12[ 0 ],
     519  &test_insert_tree_13[ 0 ],
     520  &test_insert_tree_14[ 0 ],
     521  &test_insert_tree_15[ 0 ],
     522  &test_insert_tree_16[ 0 ],
     523  &test_insert_tree_17[ 0 ],
     524  &test_insert_tree_18[ 0 ],
     525  &test_insert_tree_19[ 0 ]
     526};
     527
     528static const test_node_description test_remove_tree_0[] = {
     529  { 8, TN( 6 ), NULL, NULL , RBT_BLACK },
     530  { 10, TN( 4 ), TN( 10 ), TN( 14 ) , RBT_BLACK },
     531  { 12, TN( 14 ), NULL, NULL , RBT_RED },
     532  { 17, TN( 6 ), TN( 17 ), TN( 9 ) , RBT_BLACK },
     533  { 19, TN( 14 ), NULL, NULL , RBT_RED },
     534  { 43, NULL, TN( 6 ), TN( 7 ) , RBT_BLACK },
     535  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     536  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     537  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     538  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     539  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     540  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED },
     541  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     542  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     543  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     544  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     545  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     546  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     547  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     548};
     549
     550static const test_node_description test_remove_tree_1[] = {
     551  { 10, TN( 14 ), NULL, TN( 17 ) , RBT_BLACK },
     552  { 12, TN( 6 ), NULL, NULL , RBT_RED },
     553  { 17, TN( 4 ), TN( 6 ), TN( 9 ) , RBT_BLACK },
     554  { 19, TN( 14 ), NULL, NULL , RBT_BLACK },
     555  { 43, NULL, TN( 14 ), TN( 7 ) , RBT_BLACK },
     556  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     557  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     558  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     559  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     560  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     561  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED },
     562  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     563  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     564  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     565  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     566  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     567  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     568  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     569};
     570
     571static const test_node_description test_remove_tree_2[] = {
     572  { 12, TN( 14 ), NULL, NULL , RBT_BLACK },
     573  { 17, TN( 4 ), TN( 17 ), TN( 9 ) , RBT_BLACK },
     574  { 19, TN( 14 ), NULL, NULL , RBT_BLACK },
     575  { 43, NULL, TN( 14 ), TN( 7 ) , RBT_BLACK },
     576  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     577  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     578  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     579  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     580  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     581  { 60, TN( 4 ), TN( 0 ), TN( 3 ) , RBT_RED },
     582  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     583  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     584  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     585  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     586  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     587  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     588  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     589};
     590
     591static const test_node_description test_remove_tree_3[] = {
     592  { 17, TN( 4 ), NULL, TN( 9 ) , RBT_BLACK },
     593  { 19, TN( 14 ), NULL, NULL , RBT_RED },
     594  { 43, TN( 7 ), TN( 14 ), TN( 0 ) , RBT_BLACK },
     595  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     596  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     597  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     598  { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RBT_RED },
     599  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     600  { 60, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK },
     601  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     602  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     603  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     604  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     605  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     606  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     607  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     608};
     609
     610static const test_node_description test_remove_tree_4[] = {
     611  { 19, TN( 4 ), NULL, NULL , RBT_BLACK },
     612  { 43, TN( 7 ), TN( 9 ), TN( 0 ) , RBT_BLACK },
     613  { 44, TN( 12 ), NULL, NULL , RBT_RED },
     614  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_BLACK },
     615  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     616  { 52, TN( 4 ), TN( 12 ), TN( 13 ) , RBT_RED },
     617  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     618  { 60, NULL, TN( 4 ), TN( 3 ) , RBT_BLACK },
     619  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     620  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     621  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     622  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     623  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     624  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     625  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     626};
     627
     628static const test_node_description test_remove_tree_5[] = {
     629  { 43, TN( 12 ), NULL, TN( 5 ) , RBT_BLACK },
     630  { 44, TN( 4 ), NULL, NULL , RBT_RED },
     631  { 48, TN( 0 ), TN( 4 ), TN( 8 ) , RBT_RED },
     632  { 50, TN( 12 ), NULL, NULL , RBT_BLACK },
     633  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     634  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     635  { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK },
     636  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     637  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     638  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     639  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     640  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     641  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     642  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     643};
     644
     645static const test_node_description test_remove_tree_6[] = {
     646  { 44, TN( 12 ), NULL, NULL , RBT_BLACK },
     647  { 48, TN( 0 ), TN( 5 ), TN( 8 ) , RBT_RED },
     648  { 50, TN( 12 ), NULL, NULL , RBT_BLACK },
     649  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     650  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     651  { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK },
     652  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     653  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     654  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     655  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     656  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     657  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     658  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     659};
     660
     661static const test_node_description test_remove_tree_7[] = {
     662  { 48, TN( 0 ), NULL, TN( 8 ) , RBT_BLACK },
     663  { 50, TN( 12 ), NULL, NULL , RBT_RED },
     664  { 52, TN( 7 ), TN( 12 ), TN( 13 ) , RBT_BLACK },
     665  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     666  { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK },
     667  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     668  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     669  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     670  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     671  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     672  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     673  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     674};
     675
     676static const test_node_description test_remove_tree_8[] = {
     677  { 50, TN( 0 ), NULL, NULL , RBT_BLACK },
     678  { 52, TN( 7 ), TN( 8 ), TN( 13 ) , RBT_BLACK },
     679  { 57, TN( 0 ), NULL, NULL , RBT_BLACK },
     680  { 60, NULL, TN( 0 ), TN( 3 ) , RBT_BLACK },
     681  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     682  { 68, TN( 3 ), TN( 15 ), TN( 18 ) , RBT_RED },
     683  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     684  { 77, TN( 11 ), TN( 19 ), NULL , RBT_BLACK },
     685  { 85, TN( 7 ), TN( 11 ), TN( 1 ) , RBT_BLACK },
     686  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     687  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     688};
     689
     690static const test_node_description test_remove_tree_9[] = {
     691  { 52, TN( 7 ), NULL, TN( 13 ) , RBT_BLACK },
     692  { 57, TN( 0 ), NULL, NULL , RBT_RED },
     693  { 60, TN( 11 ), TN( 0 ), TN( 15 ) , RBT_BLACK },
     694  { 67, TN( 7 ), NULL, NULL , RBT_BLACK },
     695  { 68, NULL, TN( 7 ), TN( 3 ) , RBT_BLACK },
     696  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     697  { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK },
     698  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_BLACK },
     699  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     700  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     701};
     702
     703static const test_node_description test_remove_tree_10[] = {
     704  { 57, TN( 7 ), NULL, NULL , RBT_BLACK },
     705  { 60, TN( 11 ), TN( 13 ), TN( 15 ) , RBT_BLACK },
     706  { 67, TN( 7 ), NULL, NULL , RBT_BLACK },
     707  { 68, NULL, TN( 7 ), TN( 3 ) , RBT_BLACK },
     708  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     709  { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK },
     710  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_BLACK },
     711  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     712  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     713};
     714
     715static const test_node_description test_remove_tree_11[] = {
     716  { 60, TN( 11 ), NULL, TN( 15 ) , RBT_BLACK },
     717  { 67, TN( 7 ), NULL, NULL , RBT_RED },
     718  { 68, NULL, TN( 7 ), TN( 3 ) , RBT_BLACK },
     719  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     720  { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK },
     721  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_RED },
     722  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     723  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     724};
     725
     726static const test_node_description test_remove_tree_12[] = {
     727  { 67, TN( 11 ), NULL, NULL , RBT_BLACK },
     728  { 68, NULL, TN( 15 ), TN( 3 ) , RBT_BLACK },
     729  { 71, TN( 18 ), NULL, NULL , RBT_RED },
     730  { 77, TN( 3 ), TN( 19 ), NULL , RBT_BLACK },
     731  { 85, TN( 11 ), TN( 18 ), TN( 1 ) , RBT_RED },
     732  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     733  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     734};
     735
     736static const test_node_description test_remove_tree_13[] = {
     737  { 68, TN( 19 ), NULL, NULL , RBT_BLACK },
     738  { 71, TN( 3 ), TN( 11 ), TN( 18 ) , RBT_RED },
     739  { 77, TN( 19 ), NULL, NULL , RBT_BLACK },
     740  { 85, NULL, TN( 19 ), TN( 1 ) , RBT_BLACK },
     741  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     742  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     743};
     744
     745static const test_node_description test_remove_tree_14[] = {
     746  { 71, TN( 3 ), NULL, TN( 18 ) , RBT_BLACK },
     747  { 77, TN( 19 ), NULL, NULL , RBT_RED },
     748  { 85, NULL, TN( 19 ), TN( 1 ) , RBT_BLACK },
     749  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     750  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     751};
     752
     753static const test_node_description test_remove_tree_15[] = {
     754  { 77, TN( 3 ), NULL, NULL , RBT_BLACK },
     755  { 85, NULL, TN( 18 ), TN( 1 ) , RBT_BLACK },
     756  { 90, TN( 1 ), NULL, NULL , RBT_RED },
     757  { 99, TN( 3 ), TN( 16 ), NULL , RBT_BLACK }
     758};
     759
     760static const test_node_description test_remove_tree_16[] = {
     761  { 85, TN( 16 ), NULL, NULL , RBT_BLACK },
     762  { 90, NULL, TN( 3 ), TN( 1 ) , RBT_BLACK },
     763  { 99, TN( 16 ), NULL, NULL , RBT_BLACK }
     764};
     765
     766static const test_node_description test_remove_tree_17[] = {
     767  { 90, NULL, NULL, TN( 1 ) , RBT_BLACK },
     768  { 99, TN( 16 ), NULL, NULL , RBT_RED }
     769};
     770
     771static const test_node_description test_remove_tree_18[] = {
     772  { 99, NULL, NULL, NULL , RBT_BLACK }
     773};
     774
     775static const test_node_description *const test_remove_trees[] = {
     776  &test_remove_tree_0[ 0 ],
     777  &test_remove_tree_1[ 0 ],
     778  &test_remove_tree_2[ 0 ],
     779  &test_remove_tree_3[ 0 ],
     780  &test_remove_tree_4[ 0 ],
     781  &test_remove_tree_5[ 0 ],
     782  &test_remove_tree_6[ 0 ],
     783  &test_remove_tree_7[ 0 ],
     784  &test_remove_tree_8[ 0 ],
     785  &test_remove_tree_9[ 0 ],
     786  &test_remove_tree_10[ 0 ],
     787  &test_remove_tree_11[ 0 ],
     788  &test_remove_tree_12[ 0 ],
     789  &test_remove_tree_13[ 0 ],
     790  &test_remove_tree_14[ 0 ],
     791  &test_remove_tree_15[ 0 ],
     792  &test_remove_tree_16[ 0 ],
     793  &test_remove_tree_17[ 0 ],
     794  &test_remove_tree_18[ 0 ]
     795};
     796
     797typedef struct {
     798  int current;
     799  int count;
     800  const test_node_description *tree;
     801} visitor_context;
     802
     803static bool visit_nodes(
     804  const RBTree_Node *node,
     805  RBTree_Direction   dir,
     806  void              *visitor_arg
     807)
     808{
     809  visitor_context *ctx = visitor_arg;
     810  const test_node_description *td = &ctx->tree[ ctx->current ];
     811  const test_node *tn = RTEMS_CONTAINER_OF( node, test_node, Node );
     812
     813  rtems_test_assert( ctx->current < ctx->count );
     814
     815  rtems_test_assert( td->key == tn->id );
     816  rtems_test_assert( td->key == tn->key );
     817
     818  if ( td->parent == NULL ) {
     819    rtems_test_assert( td->parent == tn->Node.parent->parent );
     820  } else {
     821    rtems_test_assert( td->parent == tn->Node.parent );
     822  }
     823
     824  rtems_test_assert( td->left == tn->Node.child[ RBT_LEFT ] );
     825  rtems_test_assert( td->right == tn->Node.child[ RBT_RIGHT ] );
     826  rtems_test_assert( td->color == tn->Node.color );
     827
     828  ++ctx->current;
     829
     830  return false;
    223831}
    224832
    … …  
    6241232  puts("INIT - Insert 20 random numbers");
    6251233  for (i = 0; i < 20; i++) {
     1234    visitor_context ctx = { 0, i + 1, test_insert_trees[ i ] };
     1235
    6261236    node_array[i].id = numbers[i];
    6271237    node_array[i].key = numbers[i];
    6281238    rb_insert_unique( &rbtree1, &node_array[i].Node );
     1239
     1240    _RBTree_Iterate( &rbtree1, RBT_RIGHT, visit_nodes, &ctx );
     1241    rtems_test_assert( ctx.current == ctx.count );
    6291242
    6301243    if (!rb_assert(rbtree1.root) )
    … …  
    6481261    if (!rb_assert(rbtree1.root) )
    6491262      puts( "INIT - FAILED TREE CHECK" );
     1263
     1264    if ( id < 19 ) {
     1265      visitor_context ctx = { 0, 20 - id - 1, test_remove_trees[ id ] };
     1266
     1267      _RBTree_Iterate( &rbtree1, RBT_RIGHT, visit_nodes, &ctx );
     1268      rtems_test_assert( ctx.current == ctx.count );
     1269    }
    6501270  }
    6511271
Note: See TracChangeset for help on using the changeset viewer.