[142b3b8] | 1 | /* |
---|
| 2 | * Copyright (c) 2010 Gedare Bloom. |
---|
| 3 | * |
---|
| 4 | * The license and distribution terms for this file may be |
---|
| 5 | * found in the file LICENSE in this distribution or at |
---|
[c499856] | 6 | * http://www.rtems.org/license/LICENSE. |
---|
[142b3b8] | 7 | */ |
---|
| 8 | |
---|
[4e8589d] | 9 | #ifdef HAVE_CONFIG_H |
---|
| 10 | #include "config.h" |
---|
| 11 | #endif |
---|
| 12 | |
---|
[142b3b8] | 13 | #include <tmacros.h> |
---|
| 14 | #include <rtems/rbtree.h> |
---|
[93fb3cb0] | 15 | #include <rtems/score/rbtreeimpl.h> |
---|
[142b3b8] | 16 | |
---|
[6c0301d] | 17 | const char rtems_test_name[] = "SPRBTREE 1"; |
---|
| 18 | |
---|
[3c8eda7] | 19 | /* forward declarations to avoid warnings */ |
---|
| 20 | rtems_task Init(rtems_task_argument argument); |
---|
| 21 | |
---|
[639117f] | 22 | static const int numbers[20] = { |
---|
| 23 | 52, 99, 0, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71 |
---|
| 24 | }; |
---|
[142b3b8] | 25 | |
---|
[639117f] | 26 | static const int numbers_sorted[20] = { |
---|
| 27 | 0, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99 |
---|
| 28 | }; |
---|
[142b3b8] | 29 | |
---|
| 30 | typedef struct { |
---|
| 31 | int id; |
---|
[b2f66e6] | 32 | int key; |
---|
[142b3b8] | 33 | rtems_rbtree_node Node; |
---|
| 34 | } test_node; |
---|
| 35 | |
---|
[849d4bbc] | 36 | static int test_compare_function ( |
---|
[890358f] | 37 | const rtems_rbtree_node *n1, |
---|
| 38 | const rtems_rbtree_node *n2 |
---|
[b2f66e6] | 39 | ) |
---|
| 40 | { |
---|
| 41 | int key1 = rtems_rbtree_container_of( n1, test_node, Node )->key; |
---|
| 42 | int key2 = rtems_rbtree_container_of( n2, test_node, Node )->key; |
---|
| 43 | |
---|
[890358f] | 44 | return key1 - key2; |
---|
[b2f66e6] | 45 | } |
---|
| 46 | |
---|
[64939bc] | 47 | static rtems_rbtree_node *rb_insert_unique( |
---|
| 48 | rtems_rbtree_control *rbtree, |
---|
| 49 | rtems_rbtree_node *node |
---|
| 50 | ) |
---|
| 51 | { |
---|
| 52 | return rtems_rbtree_insert( rbtree, node, test_compare_function, true ); |
---|
| 53 | } |
---|
| 54 | |
---|
| 55 | static rtems_rbtree_node *rb_insert_multi( |
---|
| 56 | rtems_rbtree_control *rbtree, |
---|
| 57 | rtems_rbtree_node *node |
---|
| 58 | ) |
---|
| 59 | { |
---|
| 60 | return rtems_rbtree_insert( rbtree, node, test_compare_function, false ); |
---|
| 61 | } |
---|
| 62 | |
---|
| 63 | static rtems_rbtree_node *rb_find_unique( |
---|
| 64 | rtems_rbtree_control *rbtree, |
---|
| 65 | rtems_rbtree_node *node |
---|
| 66 | ) |
---|
| 67 | { |
---|
| 68 | return rtems_rbtree_find( rbtree, node, test_compare_function, true ); |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | static rtems_rbtree_node *rb_find_multi( |
---|
| 72 | rtems_rbtree_control *rbtree, |
---|
| 73 | rtems_rbtree_node *node |
---|
| 74 | ) |
---|
| 75 | { |
---|
| 76 | return rtems_rbtree_find( rbtree, node, test_compare_function, false ); |
---|
| 77 | } |
---|
| 78 | |
---|
| 79 | /* |
---|
| 80 | * recursively checks tree. if the tree is built properly it should only |
---|
| 81 | * be a depth of 7 function calls for 100 entries in the tree. |
---|
[142b3b8] | 82 | */ |
---|
[849d4bbc] | 83 | static int rb_assert ( rtems_rbtree_node *root ) |
---|
[142b3b8] | 84 | { |
---|
| 85 | int lh, rh; |
---|
| 86 | |
---|
| 87 | if ( root == NULL ) |
---|
| 88 | return 1; |
---|
| 89 | else { |
---|
| 90 | rtems_rbtree_node *ln = rtems_rbtree_left(root); |
---|
| 91 | rtems_rbtree_node *rn = rtems_rbtree_right(root); |
---|
| 92 | |
---|
| 93 | /* Consecutive red links */ |
---|
| 94 | if ( root->color == RBT_RED ) { |
---|
| 95 | if ((ln && ln->color == RBT_RED) || (rn && rn->color == RBT_RED)) { |
---|
| 96 | puts ( "Red violation" ); |
---|
| 97 | return -1; |
---|
| 98 | } |
---|
| 99 | } |
---|
| 100 | |
---|
| 101 | lh = rb_assert ( ln ); |
---|
| 102 | rh = rb_assert ( rn ); |
---|
| 103 | |
---|
| 104 | /* Invalid binary search tree */ |
---|
[b2f66e6] | 105 | if ( ( ln != NULL && test_compare_function(ln, root) > 0 ) |
---|
| 106 | || ( rn != NULL && test_compare_function(rn, root) < 0 ) ) |
---|
[142b3b8] | 107 | { |
---|
| 108 | puts ( "Binary tree violation" ); |
---|
| 109 | return -1; |
---|
| 110 | } |
---|
| 111 | |
---|
| 112 | /* Black height mismatch */ |
---|
| 113 | if ( lh != -1 && rh != -1 && lh != rh ) { |
---|
| 114 | puts ( "Black violation" ); |
---|
| 115 | return -1; |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | /* Only count black links */ |
---|
| 119 | if ( lh != -1 && rh != -1 ) |
---|
| 120 | return ( root->color == RBT_RED ) ? lh : lh + 1; |
---|
| 121 | else |
---|
| 122 | return -1; |
---|
| 123 | } |
---|
| 124 | } |
---|
| 125 | |
---|
[639117f] | 126 | static test_node some_nodes[] = { |
---|
| 127 | { .key = 1 }, |
---|
| 128 | { .key = 1 }, |
---|
| 129 | { .key = 1 }, |
---|
| 130 | { .key = 2 }, |
---|
| 131 | { .key = 2 }, |
---|
| 132 | { .key = 2 } |
---|
| 133 | }; |
---|
| 134 | |
---|
| 135 | static void min_max_insert( |
---|
| 136 | rtems_rbtree_control *tree, |
---|
| 137 | rtems_rbtree_node *node, |
---|
| 138 | rtems_rbtree_node *min, |
---|
| 139 | rtems_rbtree_node *max |
---|
| 140 | ) |
---|
| 141 | { |
---|
| 142 | rb_insert_multi( tree, node ); |
---|
| 143 | rtems_test_assert( rb_assert( tree->root ) != -1 ); |
---|
| 144 | rtems_test_assert( tree->first[ 0 ] == min ); |
---|
| 145 | rtems_test_assert( tree->first[ 1 ] == max ); |
---|
| 146 | } |
---|
| 147 | |
---|
| 148 | static void min_max_extract( |
---|
| 149 | rtems_rbtree_control *tree, |
---|
| 150 | rtems_rbtree_node *node, |
---|
| 151 | rtems_rbtree_node *min, |
---|
| 152 | rtems_rbtree_node *max |
---|
| 153 | ) |
---|
| 154 | { |
---|
| 155 | rtems_rbtree_extract( tree, node ); |
---|
| 156 | rtems_test_assert( rb_assert( tree->root ) != -1 ); |
---|
| 157 | rtems_test_assert( tree->first[ 0 ] == min ); |
---|
| 158 | rtems_test_assert( tree->first[ 1 ] == max ); |
---|
| 159 | } |
---|
| 160 | |
---|
| 161 | static void test_rbtree_min_max(void) |
---|
| 162 | { |
---|
| 163 | rtems_rbtree_control tree; |
---|
| 164 | rtems_rbtree_node *node; |
---|
| 165 | rtems_rbtree_node *min; |
---|
| 166 | rtems_rbtree_node *max; |
---|
| 167 | |
---|
| 168 | puts( "INIT - Verify min/max node updates" ); |
---|
| 169 | |
---|
| 170 | rtems_rbtree_initialize_empty( &tree ); |
---|
| 171 | rtems_test_assert( rb_assert( tree.root ) == 1 ); |
---|
| 172 | |
---|
| 173 | node = &some_nodes[ 0 ].Node; |
---|
| 174 | min = node; |
---|
| 175 | max = node; |
---|
| 176 | min_max_insert( &tree, node, min, max ); |
---|
[142b3b8] | 177 | |
---|
[639117f] | 178 | node = &some_nodes[ 1 ].Node; |
---|
| 179 | max = node; |
---|
| 180 | min_max_insert( &tree, node, min, max ); |
---|
[142b3b8] | 181 | |
---|
[639117f] | 182 | node = &some_nodes[ 2 ].Node; |
---|
| 183 | max = node; |
---|
| 184 | min_max_insert( &tree, node, min, max ); |
---|
| 185 | |
---|
| 186 | node = &some_nodes[ 3 ].Node; |
---|
| 187 | max = node; |
---|
| 188 | min_max_insert( &tree, node, min, max ); |
---|
| 189 | |
---|
| 190 | node = &some_nodes[ 4 ].Node; |
---|
| 191 | max = node; |
---|
| 192 | min_max_insert( &tree, node, min, max ); |
---|
| 193 | |
---|
| 194 | node = &some_nodes[ 5 ].Node; |
---|
| 195 | max = node; |
---|
| 196 | min_max_insert( &tree, node, min, max ); |
---|
| 197 | |
---|
| 198 | node = &some_nodes[ 1 ].Node; |
---|
| 199 | min_max_extract( &tree, node, min, max ); |
---|
| 200 | |
---|
| 201 | node = &some_nodes[ 4 ].Node; |
---|
| 202 | min_max_extract( &tree, node, min, max ); |
---|
| 203 | |
---|
| 204 | node = &some_nodes[ 0 ].Node; |
---|
| 205 | min = &some_nodes[ 2 ].Node; |
---|
| 206 | min_max_extract( &tree, node, min, max ); |
---|
| 207 | |
---|
| 208 | node = &some_nodes[ 5 ].Node; |
---|
| 209 | max = &some_nodes[ 3 ].Node; |
---|
| 210 | min_max_extract( &tree, node, min, max ); |
---|
| 211 | |
---|
| 212 | node = &some_nodes[ 2 ].Node; |
---|
| 213 | min = &some_nodes[ 3 ].Node; |
---|
| 214 | min_max_extract( &tree, node, min, max ); |
---|
| 215 | |
---|
| 216 | node = &some_nodes[ 3 ].Node; |
---|
| 217 | min = NULL; |
---|
| 218 | max = NULL; |
---|
| 219 | min_max_extract( &tree, node, min, max ); |
---|
| 220 | rtems_test_assert( rtems_rbtree_is_empty( &tree ) ); |
---|
| 221 | } |
---|
| 222 | |
---|
| 223 | rtems_task Init( rtems_task_argument ignored ) |
---|
[142b3b8] | 224 | { |
---|
| 225 | rtems_rbtree_control rbtree1; |
---|
| 226 | rtems_rbtree_node *p; |
---|
| 227 | test_node node1, node2; |
---|
| 228 | test_node node_array[100]; |
---|
[b2f66e6] | 229 | test_node search_node; |
---|
[142b3b8] | 230 | int id; |
---|
| 231 | int i; |
---|
| 232 | |
---|
[6c0301d] | 233 | TEST_BEGIN(); |
---|
[142b3b8] | 234 | |
---|
| 235 | puts( "Init - Initialize rbtree empty" ); |
---|
[64939bc] | 236 | rtems_rbtree_initialize_empty( &rbtree1 ); |
---|
[611909e] | 237 | |
---|
[6e93c836] | 238 | rtems_rbtree_set_off_tree( &node1.Node ); |
---|
| 239 | rtems_test_assert( rtems_rbtree_is_node_off_tree( &node1.Node ) ); |
---|
[8abbbdde] | 240 | |
---|
[142b3b8] | 241 | /* verify that the rbtree insert work */ |
---|
| 242 | puts( "INIT - Verify rtems_rbtree_insert with two nodes" ); |
---|
| 243 | node1.id = 1; |
---|
[b2f66e6] | 244 | node1.key = 1; |
---|
[142b3b8] | 245 | node2.id = 2; |
---|
[b2f66e6] | 246 | node2.key = 2; |
---|
[64939bc] | 247 | rb_insert_unique( &rbtree1, &node1.Node ); |
---|
| 248 | rb_insert_unique( &rbtree1, &node2.Node ); |
---|
[142b3b8] | 249 | |
---|
[6e93c836] | 250 | rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) ); |
---|
[9a795cba] | 251 | |
---|
| 252 | _RBTree_Rotate(NULL, RBT_LEFT); |
---|
| 253 | i = (node1.Node.parent == &node2.Node); |
---|
| 254 | _RBTree_Rotate( &node1.Node, |
---|
| 255 | !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT |
---|
| 256 | ); |
---|
| 257 | if ( (node1.Node.parent == &node2.Node) != i ) |
---|
| 258 | puts( "INIT - FAILED FALSE ROTATION" ); |
---|
| 259 | |
---|
[142b3b8] | 260 | if (!rb_assert(rbtree1.root) ) |
---|
| 261 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 262 | |
---|
[4ea97d24] | 263 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; |
---|
| 264 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[142b3b8] | 265 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 266 | if ( id > 2 ) { |
---|
| 267 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 268 | rtems_test_exit(0); |
---|
| 269 | } |
---|
| 270 | if ( t->id != id ) { |
---|
| 271 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 272 | rtems_test_exit(0); |
---|
| 273 | } |
---|
| 274 | |
---|
| 275 | if (!rb_assert(rbtree1.root) ) |
---|
| 276 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 277 | } |
---|
| 278 | if (id < 2) { |
---|
| 279 | puts("INIT - NOT ENOUGH NODES ON RBTREE"); |
---|
| 280 | rtems_test_exit(0); |
---|
| 281 | } |
---|
| 282 | |
---|
| 283 | puts("INIT - Verify rtems_rbtree_insert with the same value twice"); |
---|
[b2f66e6] | 284 | node2.key = node1.key; |
---|
[64939bc] | 285 | rb_insert_unique(&rbtree1, &node1.Node); |
---|
| 286 | p = rb_insert_unique(&rbtree1, &node2.Node); |
---|
[611909e] | 287 | |
---|
| 288 | if (p != &node1.Node) |
---|
| 289 | puts( "INIT - FAILED DUPLICATE INSERT" ); |
---|
| 290 | |
---|
[4ea97d24] | 291 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; |
---|
| 292 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[142b3b8] | 293 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 294 | if ( id > 1 ) { |
---|
| 295 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 296 | rtems_test_exit(0); |
---|
| 297 | } |
---|
| 298 | if ( t->id != id ) { |
---|
| 299 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 300 | rtems_test_exit(0); |
---|
| 301 | } |
---|
| 302 | |
---|
| 303 | if (!rb_assert(rbtree1.root) ) |
---|
| 304 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 305 | } |
---|
| 306 | if (id < 1) { |
---|
| 307 | puts("INIT - NOT ENOUGH NODES ON RBTREE"); |
---|
| 308 | rtems_test_exit(0); |
---|
| 309 | } |
---|
[b2f66e6] | 310 | node2.key = 2; |
---|
[142b3b8] | 311 | |
---|
| 312 | /* verify that the rbtree is empty */ |
---|
| 313 | puts( "INIT - Verify rtems_rbtree_is_empty" ); |
---|
| 314 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 315 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 316 | rtems_test_exit(0); |
---|
| 317 | } |
---|
| 318 | |
---|
| 319 | puts( "INIT - Verify rtems_XXX on an empty tree" ); |
---|
[4ea97d24] | 320 | if(rtems_rbtree_get_min(&rbtree1)) { |
---|
[142b3b8] | 321 | puts("INIT - get_min on empty returned non-NULL"); |
---|
| 322 | rtems_test_exit(0); |
---|
| 323 | } |
---|
[4ea97d24] | 324 | if(rtems_rbtree_get_max(&rbtree1)) { |
---|
[142b3b8] | 325 | puts("INIT - get_max on empty returned non-NULL"); |
---|
| 326 | rtems_test_exit(0); |
---|
| 327 | } |
---|
| 328 | if(rtems_rbtree_peek_min(&rbtree1)) { |
---|
| 329 | puts("INIT - peek_min on empty returned non-NULL"); |
---|
| 330 | rtems_test_exit(0); |
---|
| 331 | } |
---|
| 332 | if(rtems_rbtree_peek_max(&rbtree1)) { |
---|
| 333 | puts("INIT - peek_max on empty returned non-NULL"); |
---|
| 334 | rtems_test_exit(0); |
---|
| 335 | } |
---|
| 336 | |
---|
| 337 | |
---|
| 338 | /* verify that the rbtree insert works after a tree is emptied */ |
---|
| 339 | puts( "INIT - Verify rtems_rbtree_insert after empty tree" ); |
---|
| 340 | node1.id = 2; |
---|
[b2f66e6] | 341 | node1.key = 2; |
---|
[142b3b8] | 342 | node2.id = 1; |
---|
[b2f66e6] | 343 | node2.key = 1; |
---|
[64939bc] | 344 | rb_insert_unique( &rbtree1, &node1.Node ); |
---|
| 345 | rb_insert_unique( &rbtree1, &node2.Node ); |
---|
[142b3b8] | 346 | |
---|
| 347 | puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" ); |
---|
[b2f66e6] | 348 | test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1), |
---|
| 349 | test_node,Node); |
---|
| 350 | test_node *t2 = rtems_rbtree_container_of(rtems_rbtree_peek_min(&rbtree1), |
---|
| 351 | test_node,Node); |
---|
| 352 | if (t1->key - t2->key != 1) { |
---|
[142b3b8] | 353 | puts( "INIT - Peek Min - Max failed" ); |
---|
| 354 | rtems_test_exit(0); |
---|
| 355 | } |
---|
| 356 | p = rtems_rbtree_peek_max(&rbtree1); |
---|
[4ea97d24] | 357 | rtems_rbtree_extract(&rbtree1, p); |
---|
[b2f66e6] | 358 | t1 = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 359 | if (t1->key != 2) { |
---|
[142b3b8] | 360 | puts( "INIT - rtems_rbtree_extract failed"); |
---|
| 361 | rtems_test_exit(0); |
---|
| 362 | } |
---|
[6e93c836] | 363 | rtems_test_assert( !rtems_rbtree_is_node_off_tree( p ) ); |
---|
[64939bc] | 364 | rb_insert_unique(&rbtree1, p); |
---|
[142b3b8] | 365 | |
---|
[4ea97d24] | 366 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; |
---|
| 367 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[142b3b8] | 368 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 369 | if ( id > 2 ) { |
---|
| 370 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 371 | rtems_test_exit(0); |
---|
| 372 | } |
---|
| 373 | if ( t->id != id ) { |
---|
| 374 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 375 | rtems_test_exit(0); |
---|
| 376 | } |
---|
| 377 | } |
---|
| 378 | |
---|
| 379 | puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" ); |
---|
| 380 | for (i = 0; i < 100; i++) { |
---|
| 381 | node_array[i].id = i; |
---|
[b2f66e6] | 382 | node_array[i].key = i; |
---|
[64939bc] | 383 | rb_insert_unique( &rbtree1, &node_array[i].Node ); |
---|
[142b3b8] | 384 | |
---|
| 385 | if (!rb_assert(rbtree1.root) ) |
---|
| 386 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 387 | } |
---|
| 388 | |
---|
| 389 | puts( "INIT - Removing 100 nodes" ); |
---|
| 390 | |
---|
[4ea97d24] | 391 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; |
---|
| 392 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[142b3b8] | 393 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 394 | if ( id > 99 ) { |
---|
| 395 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 396 | rtems_test_exit(0); |
---|
| 397 | } |
---|
| 398 | if ( t->id != id ) { |
---|
| 399 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 400 | rtems_test_exit(0); |
---|
| 401 | } |
---|
| 402 | |
---|
| 403 | if (!rb_assert(rbtree1.root) ) |
---|
| 404 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 405 | } |
---|
| 406 | |
---|
| 407 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 408 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 409 | rtems_test_exit(0); |
---|
| 410 | } |
---|
| 411 | |
---|
| 412 | puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" ); |
---|
| 413 | for (i = 0; i < 100; i++) { |
---|
| 414 | node_array[i].id = 99-i; |
---|
[b2f66e6] | 415 | node_array[i].key = 99-i; |
---|
[64939bc] | 416 | rb_insert_unique( &rbtree1, &node_array[i].Node ); |
---|
[142b3b8] | 417 | |
---|
| 418 | if (!rb_assert(rbtree1.root) ) |
---|
| 419 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 420 | } |
---|
| 421 | |
---|
| 422 | puts( "INIT - Removing 100 nodes" ); |
---|
| 423 | |
---|
[4ea97d24] | 424 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; |
---|
| 425 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[142b3b8] | 426 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 427 | if ( id > 99 ) { |
---|
| 428 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 429 | rtems_test_exit(0); |
---|
| 430 | } |
---|
| 431 | if ( t->id != id ) { |
---|
| 432 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 433 | rtems_test_exit(0); |
---|
| 434 | } |
---|
| 435 | |
---|
| 436 | if (!rb_assert(rbtree1.root) ) |
---|
| 437 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 438 | } |
---|
| 439 | |
---|
| 440 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 441 | puts( "INIT - TREE NOT EMPTY" ); |
---|
[1c5dde0b] | 442 | rtems_test_exit(0); |
---|
| 443 | } |
---|
| 444 | |
---|
| 445 | /* testing rbtree_extract by adding 100 nodes then removing the 20 with |
---|
| 446 | * keys specified by the numbers array, then removing the rest */ |
---|
| 447 | puts( "INIT - Verify rtems_rbtree_extract with 100 nodes value [0,99]" ); |
---|
| 448 | for (i = 0; i < 100; i++) { |
---|
| 449 | node_array[i].id = i; |
---|
[b2f66e6] | 450 | node_array[i].key = i; |
---|
[64939bc] | 451 | rb_insert_unique( &rbtree1, &node_array[i].Node ); |
---|
[1c5dde0b] | 452 | |
---|
| 453 | if (!rb_assert(rbtree1.root) ) |
---|
| 454 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 455 | } |
---|
| 456 | |
---|
| 457 | puts( "INIT - Extracting 20 random nodes" ); |
---|
| 458 | |
---|
| 459 | for (i = 0; i < 20; i++) { |
---|
| 460 | id = numbers[i]; |
---|
[4ea97d24] | 461 | rtems_rbtree_extract( &rbtree1, &node_array[id].Node ); |
---|
[1c5dde0b] | 462 | if (!rb_assert(rbtree1.root) ) |
---|
| 463 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 464 | } |
---|
| 465 | |
---|
| 466 | puts( "INIT - Removing 80 nodes" ); |
---|
| 467 | |
---|
[4ea97d24] | 468 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ; |
---|
| 469 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[1c5dde0b] | 470 | test_node *t = rtems_rbtree_container_of(p, test_node, Node); |
---|
| 471 | |
---|
| 472 | while ( id == numbers_sorted[i] ) { |
---|
| 473 | /* skip if expected minimum (id) is in the set of extracted numbers */ |
---|
| 474 | id++; |
---|
| 475 | i++; |
---|
| 476 | } |
---|
| 477 | |
---|
| 478 | if ( id > 99 ) { |
---|
| 479 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 480 | rtems_test_exit(0); |
---|
| 481 | } |
---|
| 482 | |
---|
| 483 | if ( t->id != id ) { |
---|
| 484 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 485 | rtems_test_exit(0); |
---|
| 486 | } |
---|
| 487 | |
---|
| 488 | if (!rb_assert(rbtree1.root) ) |
---|
| 489 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 490 | } |
---|
| 491 | |
---|
| 492 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 493 | puts( "INIT - TREE NOT EMPTY" ); |
---|
[142b3b8] | 494 | rtems_test_exit(0); |
---|
| 495 | } |
---|
| 496 | |
---|
[9a795cba] | 497 | /* Additional rtems_rbtree_extract test which removes a node |
---|
| 498 | * with two children while target node has a left child only. */ |
---|
| 499 | for ( i = 0; i < 7; i++ ) { |
---|
| 500 | node_array[i].id = i; |
---|
[b2f66e6] | 501 | node_array[i].key = i; |
---|
[9a795cba] | 502 | } |
---|
[64939bc] | 503 | rb_insert_unique( &rbtree1, &node_array[3].Node ); |
---|
| 504 | rb_insert_unique( &rbtree1, &node_array[1].Node ); |
---|
| 505 | rb_insert_unique( &rbtree1, &node_array[5].Node ); |
---|
| 506 | rb_insert_unique( &rbtree1, &node_array[0].Node ); |
---|
| 507 | rb_insert_unique( &rbtree1, &node_array[2].Node ); |
---|
| 508 | rb_insert_unique( &rbtree1, &node_array[4].Node ); |
---|
| 509 | rb_insert_unique( &rbtree1, &node_array[6].Node ); |
---|
[4ea97d24] | 510 | rtems_rbtree_extract( &rbtree1, &node_array[2].Node ); |
---|
[9a795cba] | 511 | /* node_array[1] has now only a left child. */ |
---|
| 512 | if ( !node_array[1].Node.child[RBT_LEFT] || |
---|
| 513 | node_array[1].Node.child[RBT_RIGHT] ) |
---|
| 514 | puts( "INIT - LEFT CHILD ONLY NOT FOUND" ); |
---|
[4ea97d24] | 515 | rtems_rbtree_extract( &rbtree1, &node_array[3].Node ); |
---|
| 516 | while( (p = rtems_rbtree_get_max(&rbtree1)) ); |
---|
[9a795cba] | 517 | |
---|
[142b3b8] | 518 | puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" ); |
---|
| 519 | for (i = 0; i < 100; i++) { |
---|
| 520 | node_array[i].id = 99-i; |
---|
[b2f66e6] | 521 | node_array[i].key = 99-i; |
---|
[64939bc] | 522 | rb_insert_unique( &rbtree1, &node_array[i].Node ); |
---|
[142b3b8] | 523 | |
---|
| 524 | if (!rb_assert(rbtree1.root) ) |
---|
| 525 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 526 | } |
---|
| 527 | |
---|
| 528 | puts( "INIT - Removing 100 nodes" ); |
---|
| 529 | |
---|
[4ea97d24] | 530 | for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ; |
---|
| 531 | p = rtems_rbtree_get_max(&rbtree1) , id++ ) { |
---|
[142b3b8] | 532 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 533 | if ( id > 99 ) { |
---|
| 534 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 535 | rtems_test_exit(0); |
---|
| 536 | } |
---|
| 537 | if ( t->id != 99-id ) { |
---|
| 538 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 539 | rtems_test_exit(0); |
---|
| 540 | } |
---|
| 541 | |
---|
| 542 | if (!rb_assert(rbtree1.root) ) |
---|
| 543 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 544 | } |
---|
| 545 | |
---|
| 546 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 547 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 548 | rtems_test_exit(0); |
---|
| 549 | } |
---|
| 550 | |
---|
| 551 | puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" ); |
---|
| 552 | for (i = 0; i < 100; i++) { |
---|
| 553 | node_array[i].id = i; |
---|
[b2f66e6] | 554 | node_array[i].key = i; |
---|
[64939bc] | 555 | rb_insert_unique( &rbtree1, &node_array[i].Node ); |
---|
[142b3b8] | 556 | |
---|
| 557 | if (!rb_assert(rbtree1.root) ) |
---|
| 558 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 559 | } |
---|
| 560 | |
---|
| 561 | puts( "INIT - Verify rtems_rbtree_find" ); |
---|
[b2f66e6] | 562 | search_node.key = 30; |
---|
[64939bc] | 563 | p = rb_find_unique(&rbtree1, &search_node.Node); |
---|
[9a795cba] | 564 | if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) { |
---|
[142b3b8] | 565 | puts ("INIT - ERROR ON RBTREE ID MISMATCH"); |
---|
| 566 | rtems_test_exit(0); |
---|
| 567 | } |
---|
| 568 | |
---|
| 569 | puts( "INIT - Verify rtems_rbtree_predecessor/successor"); |
---|
[4ea97d24] | 570 | p = rtems_rbtree_predecessor(p); |
---|
[a52be5ec] | 571 | if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 29) { |
---|
[142b3b8] | 572 | puts ("INIT - ERROR ON RBTREE ID MISMATCH"); |
---|
| 573 | rtems_test_exit(0); |
---|
| 574 | } |
---|
[64939bc] | 575 | p = rb_find_unique(&rbtree1, &search_node.Node); |
---|
[4ea97d24] | 576 | p = rtems_rbtree_successor(p); |
---|
[a52be5ec] | 577 | if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) { |
---|
[142b3b8] | 578 | puts ("INIT - ERROR ON RBTREE ID MISMATCH"); |
---|
| 579 | rtems_test_exit(0); |
---|
| 580 | } |
---|
| 581 | |
---|
[64939bc] | 582 | p = rb_find_unique(&rbtree1, &search_node.Node); |
---|
[b767683a] | 583 | puts( "INIT - Verify rtems_rbtree_find_control" ); |
---|
| 584 | if (rtems_rbtree_find_control(p) != &rbtree1) { |
---|
[142b3b8] | 585 | puts ("INIT - ERROR ON RBTREE HEADER MISMATCH"); |
---|
| 586 | rtems_test_exit(0); |
---|
| 587 | } |
---|
| 588 | |
---|
[9a795cba] | 589 | if ( _RBTree_Sibling( NULL ) != NULL ) |
---|
| 590 | puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" ); |
---|
| 591 | if ( _RBTree_Sibling( rbtree1.root ) != NULL ) |
---|
| 592 | puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" ); |
---|
| 593 | if ( _RBTree_Grandparent( NULL ) != NULL ) |
---|
| 594 | puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" ); |
---|
[6ba5971] | 595 | if ( _RBTree_Is_red( NULL ) != 0 ) |
---|
| 596 | puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" ); |
---|
[c976c70] | 597 | if ( _RBTree_Is_red( rbtree1.root ) != 0 ) |
---|
| 598 | puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" ); |
---|
[9a795cba] | 599 | |
---|
[142b3b8] | 600 | puts( "INIT - Removing 100 nodes" ); |
---|
| 601 | |
---|
[4ea97d24] | 602 | for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ; |
---|
| 603 | p = rtems_rbtree_get_max(&rbtree1) , id-- ) { |
---|
[142b3b8] | 604 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 605 | if ( id < 0 ) { |
---|
| 606 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 607 | rtems_test_exit(0); |
---|
| 608 | } |
---|
| 609 | if ( t->id != id ) { |
---|
| 610 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 611 | rtems_test_exit(0); |
---|
| 612 | } |
---|
| 613 | |
---|
| 614 | if (!rb_assert(rbtree1.root) ) |
---|
| 615 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 616 | } |
---|
| 617 | |
---|
| 618 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 619 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 620 | rtems_test_exit(0); |
---|
| 621 | } |
---|
| 622 | |
---|
| 623 | puts("INIT - Insert 20 random numbers"); |
---|
| 624 | for (i = 0; i < 20; i++) { |
---|
| 625 | node_array[i].id = numbers[i]; |
---|
[b2f66e6] | 626 | node_array[i].key = numbers[i]; |
---|
[64939bc] | 627 | rb_insert_unique( &rbtree1, &node_array[i].Node ); |
---|
[142b3b8] | 628 | |
---|
| 629 | if (!rb_assert(rbtree1.root) ) |
---|
| 630 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 631 | } |
---|
| 632 | |
---|
| 633 | puts( "INIT - Removing 20 nodes" ); |
---|
| 634 | |
---|
[4ea97d24] | 635 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; |
---|
| 636 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[142b3b8] | 637 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 638 | if ( id > 19 ) { |
---|
| 639 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 640 | rtems_test_exit(0); |
---|
| 641 | } |
---|
| 642 | if ( t->id != numbers_sorted[id] ) { |
---|
| 643 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 644 | rtems_test_exit(0); |
---|
| 645 | } |
---|
| 646 | |
---|
| 647 | if (!rb_assert(rbtree1.root) ) |
---|
| 648 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 649 | } |
---|
| 650 | |
---|
| 651 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 652 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 653 | rtems_test_exit(0); |
---|
| 654 | } |
---|
| 655 | |
---|
[9a795cba] | 656 | puts( "INIT - Verify rtems_rbtree_initialize with 100 nodes value [0,99]" ); |
---|
| 657 | for (i = 0; i < 100; i++) { |
---|
| 658 | node_array[i].id = i; |
---|
[b2f66e6] | 659 | node_array[i].key = i; |
---|
[9a795cba] | 660 | } |
---|
[b2f66e6] | 661 | rtems_rbtree_initialize( &rbtree1, &test_compare_function, |
---|
[611909e] | 662 | &node_array[0].Node, 100, |
---|
[8c6608bd] | 663 | sizeof(test_node), true ); |
---|
[9a795cba] | 664 | |
---|
| 665 | puts( "INIT - Removing 100 nodes" ); |
---|
| 666 | |
---|
[4ea97d24] | 667 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; |
---|
| 668 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[9a795cba] | 669 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 670 | if ( id > 99 ) { |
---|
| 671 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 672 | rtems_test_exit(0); |
---|
| 673 | } |
---|
| 674 | |
---|
| 675 | if ( t->id != id ) { |
---|
| 676 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 677 | rtems_test_exit(0); |
---|
| 678 | } |
---|
| 679 | |
---|
| 680 | if (!rb_assert(rbtree1.root) ) |
---|
| 681 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 682 | } |
---|
| 683 | |
---|
| 684 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 685 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 686 | rtems_test_exit(0); |
---|
| 687 | } |
---|
| 688 | |
---|
[611909e] | 689 | /* Initialize the tree for duplicate keys */ |
---|
| 690 | puts( "Init - Initialize duplicate rbtree empty" ); |
---|
[64939bc] | 691 | rtems_rbtree_initialize_empty( &rbtree1 ); |
---|
[611909e] | 692 | |
---|
| 693 | puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" ); |
---|
| 694 | for (i = 0; i < 100; i++) { |
---|
| 695 | node_array[i].id = i; |
---|
| 696 | node_array[i].key = i%5; |
---|
[64939bc] | 697 | rb_insert_multi( &rbtree1, &node_array[i].Node ); |
---|
[611909e] | 698 | |
---|
| 699 | if (!rb_assert(rbtree1.root) ) |
---|
| 700 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 701 | } |
---|
| 702 | |
---|
| 703 | puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" ); |
---|
| 704 | search_node.key = 2; |
---|
[64939bc] | 705 | p = rb_find_multi(&rbtree1, &search_node.Node); |
---|
[611909e] | 706 | if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) { |
---|
| 707 | puts ("INIT - ERROR ON RBTREE ID MISMATCH"); |
---|
| 708 | rtems_test_exit(0); |
---|
| 709 | } |
---|
| 710 | |
---|
| 711 | puts( "INIT - Removing 100 nodes" ); |
---|
| 712 | |
---|
[4ea97d24] | 713 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; |
---|
| 714 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[611909e] | 715 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 716 | if ( id > 99 ) { |
---|
| 717 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 718 | rtems_test_exit(0); |
---|
| 719 | } |
---|
| 720 | if ( t->id != ( ((id*5)%100) + (id/20) ) ) { |
---|
| 721 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 722 | rtems_test_exit(0); |
---|
| 723 | } |
---|
| 724 | |
---|
| 725 | if (!rb_assert(rbtree1.root) ) |
---|
| 726 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 727 | } |
---|
| 728 | |
---|
| 729 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 730 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 731 | rtems_test_exit(0); |
---|
| 732 | } |
---|
| 733 | |
---|
| 734 | puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" ); |
---|
| 735 | for (i = 0; i < 100; i++) { |
---|
| 736 | node_array[i].id = 99-i; |
---|
| 737 | node_array[i].key = (99-i)%5; |
---|
[64939bc] | 738 | rb_insert_multi( &rbtree1, &node_array[i].Node ); |
---|
[611909e] | 739 | |
---|
| 740 | if (!rb_assert(rbtree1.root) ) |
---|
| 741 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 742 | } |
---|
| 743 | |
---|
| 744 | puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" ); |
---|
| 745 | search_node.key = 2; |
---|
[64939bc] | 746 | p = rb_find_multi(&rbtree1, &search_node.Node); |
---|
[611909e] | 747 | if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) { |
---|
| 748 | puts ("INIT - ERROR ON RBTREE ID MISMATCH"); |
---|
| 749 | rtems_test_exit(0); |
---|
| 750 | } |
---|
| 751 | |
---|
| 752 | puts( "INIT - Removing 100 nodes" ); |
---|
| 753 | |
---|
[4ea97d24] | 754 | for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; |
---|
| 755 | p = rtems_rbtree_get_min(&rbtree1) , id++ ) { |
---|
[611909e] | 756 | test_node *t = rtems_rbtree_container_of(p,test_node,Node); |
---|
| 757 | if ( id > 99 ) { |
---|
| 758 | puts( "INIT - TOO MANY NODES ON RBTREE" ); |
---|
| 759 | rtems_test_exit(0); |
---|
| 760 | } |
---|
| 761 | if ( t->id != ( (((99-id)*5)%100) + (id/20) ) ) { |
---|
| 762 | puts( "INIT - ERROR ON RBTREE ID MISMATCH" ); |
---|
| 763 | rtems_test_exit(0); |
---|
| 764 | } |
---|
| 765 | |
---|
| 766 | if (!rb_assert(rbtree1.root) ) |
---|
| 767 | puts( "INIT - FAILED TREE CHECK" ); |
---|
| 768 | } |
---|
| 769 | |
---|
| 770 | if(!rtems_rbtree_is_empty(&rbtree1)) { |
---|
| 771 | puts( "INIT - TREE NOT EMPTY" ); |
---|
| 772 | rtems_test_exit(0); |
---|
| 773 | } |
---|
| 774 | |
---|
[639117f] | 775 | test_rbtree_min_max(); |
---|
| 776 | |
---|
[6c0301d] | 777 | TEST_END(); |
---|
[142b3b8] | 778 | rtems_test_exit(0); |
---|
| 779 | } |
---|
| 780 | |
---|
| 781 | /* configuration information */ |
---|
| 782 | |
---|
| 783 | #define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER |
---|
| 784 | #define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER |
---|
| 785 | |
---|
[6c0301d] | 786 | #define CONFIGURE_INITIAL_EXTENSIONS RTEMS_TEST_INITIAL_EXTENSION |
---|
| 787 | |
---|
[142b3b8] | 788 | #define CONFIGURE_RTEMS_INIT_TASKS_TABLE |
---|
| 789 | #define CONFIGURE_MAXIMUM_TASKS 1 |
---|
| 790 | |
---|
| 791 | #define CONFIGURE_INIT |
---|
| 792 | #include <rtems/confdefs.h> |
---|
| 793 | |
---|
| 794 | /* global variables */ |
---|