From 1d1c00a74b17d1656c37f5628d2c6892c4cfb13d Mon Sep 17 00:00:00 2001 From: a bellenir Date: Tue, 2 Sep 2014 19:49:59 +0000 Subject: [PATCH] +blank lines --- source/rbt/rbt.c | 4 +++ tests/test_rbt.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 67 insertions(+) diff --git a/source/rbt/rbt.c b/source/rbt/rbt.c index 4faeb80..4d426ac 100644 --- a/source/rbt/rbt.c +++ b/source/rbt/rbt.c @@ -19,6 +19,7 @@ static void rbt_free(void* v_tree){ assert(NULL != tree); if(tree->root) mem_release(tree->root); } + rbt_t* rbt_new(comparator_t comparator){ rbt_t* tree = mem_allocate(sizeof(rbt_t), &rbt_free); tree->root = NULL; @@ -34,6 +35,7 @@ static void rbt_node_free(void* v_node){ if(node->left) mem_release(node->left); if(node->right) mem_release(node->right); } + #ifndef TESTING static #endif @@ -81,10 +83,12 @@ static rbt_node_t* rightmost_descendant(rbt_node_t* node){ static int rbt_count(rbt_node_t* node){ return (!node ? 0 : (1 + rbt_count(node->left) + rbt_count(node->right))); } + int rbt_size(rbt_t* tree){ return rbt_count(tree->root); } + /* ----------------------------------------- */ /* generally helpful tree manipulation */ /* ----------------------------------------- */ diff --git a/tests/test_rbt.c b/tests/test_rbt.c index 0cd9c41..1863fe7 100644 --- a/tests/test_rbt.c +++ b/tests/test_rbt.c @@ -70,6 +70,7 @@ static rbt_status_t rbt_check_status(rbt_t* tree){ } static void test_setup(void) { } + //----------------------------------------------------------------------------- // Begin Unit Tests //----------------------------------------------------------------------------- @@ -109,6 +110,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_checks_root_is_always_black_property){ void* box88 = mem_box(88); rbt_t* tree = rbt_new(test_compare); @@ -119,6 +121,7 @@ TEST_SUITE(RBT) { CHECK(BAD_ROOT_COLOR == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_nodes_not_sorted_two_nodes){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -137,6 +140,7 @@ TEST_SUITE(RBT) { CHECK(OUT_OF_ORDER == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_nodes_not_sorted_four_nodes){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -173,6 +177,7 @@ TEST_SUITE(RBT) { CHECK(OUT_OF_ORDER == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_black_nodes_are_unbalanced_two_nodes){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -193,6 +198,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_black_nodes_are_unbalanced_three_nodes){ void* box42 = mem_box(42); void* box22 = mem_box(22); @@ -226,6 +232,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_black_nodes_are_unbalanced_four_nodes){ void* box42 = mem_box(42); void* box22 = mem_box(22); @@ -267,6 +274,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_node_is_unvalid_color){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -287,6 +295,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_root_parent_pointer_is_not_null){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -307,6 +316,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_node_parent_poitners_are_wrong_two_nodes){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -334,6 +344,7 @@ TEST_SUITE(RBT) { mem_release(tree); mem_release(node3); } + TEST(Verify_tree_is_valid_fails_when_node_parent_poitners_are_wrong_four_nodes){ void* box42 = mem_box(42); void* box22 = mem_box(22); @@ -372,6 +383,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_tree_is_valid_fails_when_node_points_to_itself){ void* box42 = mem_box(42); void* box22 = mem_box(22); @@ -446,6 +458,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_node_to_root_left_works){ void* box42 = mem_box(42); void* box31 = mem_box(31); @@ -463,6 +476,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_node_to_root_right_works){ void* box42 = mem_box(42); void* box64 = mem_box(64); @@ -480,6 +494,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_first_level_works){ void* box42 = mem_box(42); void* box31 = mem_box(31); @@ -503,6 +518,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_below_full_first_level_works){ void* box42 = mem_box(42); void* box31 = mem_box(31); @@ -525,6 +541,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_parent_uncle_mismatch_outside_left){ void* box42 = mem_box(42); void* box32 = mem_box(32); @@ -561,6 +578,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_parent_uncle_mismatch_outside_right){ void* box42 = mem_box(42); void* box53 = mem_box(53); @@ -596,6 +614,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_parent_uncle_mismatch_inside_left){ void* box42 = mem_box(42); void* box20 = mem_box(20); @@ -631,6 +650,7 @@ TEST_SUITE(RBT) { CHECK(OK == rbt_check_status(tree)); mem_release(tree); } + TEST(Verify_rbt_insert_parent_uncle_mismatch_inside_right){ void* box42 = mem_box(42); void* box99 = mem_box(99); @@ -685,6 +705,7 @@ TEST_SUITE(RBT) { mem_release(tree); mem_release(box78); } + TEST(Verify_rbt_lookup_returns_correct_node){ void* box42 = mem_box(42); void* box33 = mem_box(33); @@ -747,6 +768,7 @@ TEST_SUITE(RBT) { mem_release(node4); mem_release(tree); } + //case 2: black node, one red child TEST(Verify_rbt_delete_left_black_node_with_single_red_left_child){ void* box42 = mem_box(42); @@ -779,6 +801,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_left_black_node_with_single_red_right_child){ void* box42 = mem_box(42); void* box33 = mem_box(33); @@ -810,6 +833,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_right_black_node_with_single_red_right_child){ void* box42 = mem_box(42); void* box33 = mem_box(33); @@ -841,6 +865,7 @@ TEST_SUITE(RBT) { mem_release(node3); mem_release(tree); } + TEST(Verify_rbt_delete_right_black_node_with_single_red_left_child){ void* box42 = mem_box(42); void* box33 = mem_box(33); @@ -872,6 +897,7 @@ TEST_SUITE(RBT) { mem_release(node3); mem_release(tree); } + //case 3: black node, no non-null children, red parent //red parent implies non-null black sibbling //four subcases for sibbling's children @@ -917,6 +943,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.1.2: test when node being deleted is parent->left and parent is grandparent->left TEST(Verify_rbt_delete_black_node_from_red_parent_sib_no_children_left){ void* target = mem_box(15); @@ -958,6 +985,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.2: sibbling has outside child //3.2.1: test when node being deleted is parent->right and parent is grandparent->right TEST(Verify_rbt_delete_black_node_from_red_parent_sib_has_outside_child_right){ @@ -1004,6 +1032,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.2.2: test when node being deleted is parent->left and parent is grandparent->left TEST(Verify_rbt_delete_black_node_from_red_parent_sib_has_outside_child_left){ void* target = mem_box(12); @@ -1049,6 +1078,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.3: sibbling has inside child //3.3.1: test when node being deleted is parent->right and parent is grandparent->right TEST(Verify_rbt_delete_black_node_from_red_parent_sib_has_inside_child_right){ @@ -1095,6 +1125,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.3.2: test when node being deleted is parent->left and parent is grandparent->left TEST(Verify_rbt_delete_black_node_from_red_parent_sib_has_inside_child_left){ void* target = mem_box(15); @@ -1140,6 +1171,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.4: sibbling has no children //3.4.1: test when node being deleted is parent->right and parent is grandparent->right TEST(Verify_rbt_delete_black_node_from_red_parent_sib_has_two_children_right){ @@ -1190,6 +1222,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //3.4.2: test when node being deleted is parent->left and parent is grandparent->left TEST(Verify_rbt_delete_black_node_from_red_parent_sib_has_two_children_left){ void* target = mem_box(15); @@ -1239,6 +1272,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //case 4: black node, no non-null children, black parent //properties of RBT imply node has a sibbling //five subcases @@ -1276,6 +1310,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_no_children_left){ void* target = mem_box(22); //create tree w/ several nodes @@ -1309,6 +1344,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + //test tree rebalancing after remove. case 4.1 is the only rm case that requires a structural rebalancing: //trivial case: parent is tree->root (tested above) ; no action required //A: rebalance node w/ red sibbling (rotation moves to have black sibbling to fall in one of the following cases) @@ -1376,6 +1412,7 @@ TEST_SUITE(RBT) { mem_release(node11); mem_release(tree); } + TEST(Verify_rbt_delete_rebalance_red_sibbling_right){ void* target = mem_box(88); void* box42 = mem_box(42); @@ -1440,6 +1477,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + //B: rebalance w/ black parent, black sibbling w/ black children TEST(Verify_rbt_delete_rebalance_black_parent_black_sib_with_black_children_left){ void* target = mem_box(15); @@ -1488,6 +1526,7 @@ TEST_SUITE(RBT) { mem_release(node7); mem_release(tree); } + TEST(Verify_rbt_delete_rebalance_black_parent_black_sib_with_black_children_right){ void* target = mem_box(75); void* box42 = mem_box(42); @@ -1535,6 +1574,7 @@ TEST_SUITE(RBT) { mem_release(node5); mem_release(tree); } + //C: rebalance w/ red parent, red sibbling w/ black children TEST(Verify_rbt_delete_rebalance_red_parent_black_sib_with_black_children_left){ void* target = mem_box(11); @@ -1600,6 +1640,7 @@ TEST_SUITE(RBT) { mem_release(node11); mem_release(tree); } + TEST(Verify_rbt_delete_rebalance_red_parent_black_sib_with_black_children_right){ void* target = mem_box(99); void* box42 = mem_box(42); @@ -1664,6 +1705,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + //D: rebalance for sibbling w/ outside red child TEST(Verify_rbt_delete_rebalance_sib_with_red_child_outside_left){ void* target = mem_box(11); @@ -1720,6 +1762,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + TEST(Verify_rbt_delete_rebalance_sib_with_red_child_outside_right){ void* target = mem_box(88); void* box42 = mem_box(42); @@ -1775,6 +1818,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + //E: rebalance for sibbling w/ inside red child TEST(Verify_rbt_delete_rebalance_sib_with_red_child_inside_left){ void* target = mem_box(11); @@ -1831,6 +1875,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + TEST(Verify_rbt_delete_rebalance_sib_with_red_child_inside_right){ void* target = mem_box(88); void* box42 = mem_box(42); @@ -1886,6 +1931,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + //F: rebalance for sibbling with two red children TEST(Verify_rbt_delete_rebalance_sib_with_two_red_children_left){ void* target = mem_box(11); @@ -1950,6 +1996,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + TEST(Verify_rbt_delete_rebalance_sib_with_two_red_children_right){ void* target = mem_box(88); void* box42 = mem_box(42); @@ -2013,6 +2060,7 @@ TEST_SUITE(RBT) { mem_release(node06); mem_release(tree); } + //4.2: sibbling is black, outside red child TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_outside_red_child_right){ void* target = mem_box(99); @@ -2051,6 +2099,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_outside_red_child_left){ void* target = mem_box(8); //create tree w/ several nodes @@ -2088,6 +2137,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + //4.3: sibbling is black, inside red child TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_inside_red_child_right){ void* target = mem_box(99); @@ -2126,6 +2176,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_inside_red_child_left){ void* target = mem_box(8); //create tree w/ several nodes @@ -2163,6 +2214,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + //4.4: sibbling is black, two red children TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_two_children_right){ void* target = mem_box(99); @@ -2205,6 +2257,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_black_node_from_black_parent_sib_has_two_children_left){ void* target = mem_box(8); //create tree w/ several nodes @@ -2246,6 +2299,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + //4.5: sibbling is red, two black children TEST(Verify_rbt_delete_black_node_from_black_parent_red_sib_right){ void* target = mem_box(99); @@ -2288,6 +2342,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + TEST(Verify_rbt_delete_black_node_from_black_parent_red_sib_left){ void* target = mem_box(8); //create tree w/ several nodes @@ -2329,6 +2384,7 @@ TEST_SUITE(RBT) { mem_release(node2); mem_release(tree); } + //second class: deleting nodes that have two children TEST(Verify_rbt_delete_node_with_two_children_successor_is_left){ void* target = mem_box(22); @@ -2358,6 +2414,7 @@ TEST_SUITE(RBT) { mem_release(doomed); mem_release(tree); } + TEST(Verify_rbt_delete_node_with_two_children){ void* target = mem_box(42); void* box88 = mem_box(88); @@ -2400,6 +2457,7 @@ TEST_SUITE(RBT) { mem_release(doomed); mem_release(tree); } + //third class: special cases: deleting root TEST(Verify_rbt_delete_root_node_with_single_red_left_child){ void* box88 = mem_box(88); @@ -2422,6 +2480,7 @@ TEST_SUITE(RBT) { mem_release(node1); mem_release(tree); } + TEST(Verify_rbt_delete_root_node_with_single_red_right_child){ void* box42 = mem_box(42); void* box88 = mem_box(88); @@ -2443,6 +2502,7 @@ TEST_SUITE(RBT) { mem_release(node1); mem_release(tree); } + TEST(Verify_rbt_delete_root_node_with_no_children){ void* box88 = mem_box(88); rbt_t* tree = rbt_new(test_compare); @@ -2458,6 +2518,7 @@ TEST_SUITE(RBT) { mem_release(node1); mem_release(tree); } + TEST(Verify_rbt_delete_root_node_with_two_children){ void* target = mem_box(22); void* box42 = mem_box(42); @@ -2500,6 +2561,7 @@ TEST_SUITE(RBT) { mem_release(doomed); mem_release(tree); } + TEST(Verify_rbt_delete_node_with_four_nodes){ void* target = mem_box(42); void* box88 = mem_box(88); @@ -2526,6 +2588,7 @@ TEST_SUITE(RBT) { mem_release(doomed); mem_release(tree); } + //deleting node that is not present TEST(Verify_rbt_delete_node_not_present_does_nothing){ void* target = mem_box(42); -- 2.52.0