From 1f749a4994ce158dcf9439a86bd25276e820f6ec Mon Sep 17 00:00:00 2001
From: a bellenir <a@bellenir.com>
Date: Wed, 6 Aug 2014 02:25:48 +0000
Subject: [PATCH] additional insert tests

---
 tests/test_rb.c | 105 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 103 insertions(+), 2 deletions(-)

diff --git a/tests/test_rb.c b/tests/test_rb.c
index 2f2fe2c..380ab06 100644
--- a/tests/test_rb.c
+++ b/tests/test_rb.c
@@ -121,20 +121,24 @@ TEST_SUITE(RB) {
 		rb_tree_t* tree = rb_tree_new();
 		rb_node_t* node1 = rb_tree_insert(tree, 42);
 		rb_node_t* node2 = rb_tree_insert(tree, 32);
+		CHECK(node1 == tree->root);
+		CHECK(node2 == tree->root->left);
+		CHECK(NULL == tree->root->right);
 		CHECK(RED == node2->color);
 		//tree->root->right == NULL ; black implicitly
 		rb_node_t* node3 = rb_tree_insert(tree, 15);
+		CHECK(NULL != node3);
 		CHECK(node2 == tree->root);
 		//check node2 fields 
 		CHECK(node3 == node2->left);
 		CHECK(node1 == node2->right);
-		CHECK(NULL == node2->parent)
+		CHECK(NULL == node2->parent);
 		CHECK(BLACK == node2->color);
 		CHECK(32 == node2->contents);
 		//check node1 fields
 		CHECK(NULL == node1->left);
 		CHECK(NULL == node1->right);
-		CHECK(node2 == node1->parent)
+		CHECK(node2 == node1->parent);
 		CHECK(RED == node1->color);
 		CHECK(42 == node1->contents);
 		//check node3 fields
@@ -143,7 +147,104 @@ TEST_SUITE(RB) {
 		CHECK(node2 == node3->parent);
 		CHECK(RED == node3->color);
 		CHECK(15 == node3->contents);
+		CHECK(rb_tree_is_valid(tree));
 		mem_release(tree);
     }
+    TEST(Verify_rb_insert_parent_uncle_mismatch_outside_right){
+		rb_tree_t* tree = rb_tree_new();
+		rb_node_t* node1 = rb_tree_insert(tree, 42);
+		rb_node_t* node2 = rb_tree_insert(tree, 53);
+		CHECK(node1 == tree->root);
+		CHECK(node2 == tree->root->right);
+		CHECK(NULL == tree->root->left);
+		CHECK(RED == node2->color);
+		rb_node_t* node3 = rb_tree_insert(tree, 99);
+		CHECK(NULL != node3);
+		CHECK(node2 == tree->root);
+		//check node2 fields
+		CHECK(node3 == node2->right);
+		CHECK(node1 == node2->left);
+		CHECK(NULL == node2->parent);
+		CHECK(BLACK == node2->color);
+		CHECK(53 == node2->contents);
+		//check node1 fields
+		CHECK(NULL == node1->left);
+		CHECK(NULL == node1->right);
+		CHECK(node2 == node1->parent);
+		CHECK(RED == node1->color);
+		CHECK(42 == node1->contents);
+		//check node3 fields
+		CHECK(NULL == node3->left);
+		CHECK(NULL == node3->right);
+		CHECK(node2 == node3->parent);
+		CHECK(RED == node3->color);
+		CHECK(99 == node3->contents);
+		CHECK(rb_tree_is_valid(tree));
+		mem_release(tree);
+	}
+	TEST(Verify_rb_insert_parent_uncle_mismatch_inside_left){
+		rb_tree_t* tree = rb_tree_new();
+		rb_node_t* node1 = rb_tree_insert(tree, 42);
+		rb_node_t* node2 = rb_tree_insert(tree, 20);
+		CHECK(node1 == tree->root);
+		CHECK(node2 == tree->root->left);
+		CHECK(NULL == tree->root->right);
+		CHECK(RED == node2->color);
+		rb_node_t* node3 = rb_tree_insert(tree, 33);
+		CHECK(NULL != node3);
+		CHECK(node3 == tree->root);
+		//check node3 fields
+		CHECK(node2 == node3->left);
+		CHECK(node1 == node3->right);
+		CHECK(NULL == node3->parent);
+		CHECK(BLACK == node3->color);
+		CHECK(33 == node3->contents);
+		//check node2 fields
+		CHECK(NULL == node2->left);
+		CHECK(NULL == node2->right);
+		CHECK(node3 == node2->parent);
+		CHECK(RED == node2->color);
+		CHECK(20 == node2->contents);
+		//check node1 fields
+		CHECK(NULL == node1->left);
+		CHECK(NULL == node1->right);
+		CHECK(node3 == node1->parent);
+		CHECK(RED == node1->color);
+		CHECK(42 == node1->contents);
+		CHECK(rb_tree_is_valid(tree));
+		mem_release(tree);
+	}
+	TEST(Verify_rb_insert_parent_uncle_mismatch_inside_right){
+		rb_tree_t* tree = rb_tree_new();
+		rb_node_t* node1 = rb_tree_insert(tree, 42);
+		rb_node_t* node2 = rb_tree_insert(tree, 99);
+		CHECK(node1 == tree->root);
+		CHECK(node2 == tree->root->right);
+		CHECK(NULL == tree->root->left);
+		CHECK(RED == node2->color);
+		rb_node_t* node3 = rb_tree_insert(tree, 88);
+		CHECK(NULL != node3);
+		CHECK(node3 == tree->root);
+		//check node3 fields
+		CHECK(node1 == node3->left);
+		CHECK(node2 == node3->right);
+		CHECK(NULL == node3->parent);
+		CHECK(BLACK == node3->color);
+		CHECK(88 == node3->contents);
+		//check node2 fields
+		CHECK(NULL == node2->left);
+		CHECK(NULL == node2->right);
+		CHECK(node3 == node2->parent);
+		CHECK(RED == node2->color);
+		CHECK(99 == node2->contents);
+		//check node1 fields
+		CHECK(NULL == node1->left);
+		CHECK(NULL == node1->right);
+		CHECK(node3 == node1->parent);
+		CHECK(RED == node1->color);
+		CHECK(42 == node1->contents);
+		CHECK(rb_tree_is_valid(tree));
+		mem_release(tree);
+	}
 }
 
-- 
2.55.0