From f1201beb55a3a1163d9b3da0a284acca9112f467 Mon Sep 17 00:00:00 2001
From: a bellenir <a@bellenir.com>
Date: Tue, 5 Aug 2014 22:37:22 +0000
Subject: [PATCH] add pointer to parent

---
 source/rb/rb.c  |  3 +++
 source/rb/rb.h  |  1 +
 tests/test_rb.c | 26 ++++++++++++++++++++++++++
 3 files changed, 30 insertions(+)

diff --git a/source/rb/rb.c b/source/rb/rb.c
index e667cc0..abb678a 100644
--- a/source/rb/rb.c
+++ b/source/rb/rb.c
@@ -21,6 +21,7 @@ rb_node_t* rb_node_new(int contents){
 	rb_node_t* node = mem_allocate(sizeof(rb_node_t), &rb_node_free);
 	node->left = NULL;
 	node->right = NULL;
+	node->parent = NULL;
 	node->contents = contents;
 	node->color = RED;
 	return node;
@@ -65,6 +66,7 @@ static void rb_tree_insert_node(rb_tree_t* tree,
 		if(parent->left){
 			rb_tree_insert_node(tree, node, parent->left, parent, parent->right);
 		}else{
+			node->parent = parent;
 			parent->left = node;
 			rb_tree_recolor(node, parent, grandparent, uncle);
 		}
@@ -72,6 +74,7 @@ static void rb_tree_insert_node(rb_tree_t* tree,
 		if(parent->right){
 			rb_tree_insert_node(tree, node, parent->right, parent, parent->left);
 		}else{
+			node->parent = parent;
 			parent->right = node;
 			rb_tree_recolor(node, parent, grandparent, uncle);
 		}
diff --git a/source/rb/rb.h b/source/rb/rb.h
index 73421d9..6fac63a 100644
--- a/source/rb/rb.h
+++ b/source/rb/rb.h
@@ -15,6 +15,7 @@ typedef enum {
 typedef struct rb_node_t {
 	struct rb_node_t* left;
 	struct rb_node_t* right;
+	struct rb_node_t* parent;
 	rb_color_t color;
 	int contents; /* int for development; TODO: make this a void* */
 } rb_node_t;
diff --git a/tests/test_rb.c b/tests/test_rb.c
index e920c35..dbd51ab 100644
--- a/tests/test_rb.c
+++ b/tests/test_rb.c
@@ -17,6 +17,7 @@ TEST_SUITE(RB) {
 		CHECK(NULL != node);
 		CHECK(NULL == node->left);
 		CHECK(NULL == node->right);
+		CHECK(NULL == node->parent);
 		CHECK(42 == node->contents);
 		CHECK(rb_node_is_valid(node, -1, -1));
 		mem_release(node);
@@ -42,6 +43,9 @@ TEST_SUITE(RB) {
 		CHECK(NULL != node);
 		CHECK(tree->root == node);
 		CHECK(42 == node->contents);
+		CHECK(NULL == node->left);
+		CHECK(NULL == node->right);
+		CHECK(NULL == node->parent);
 		CHECK(rb_tree_is_valid(tree));
 		mem_release(tree);
     }
@@ -52,6 +56,7 @@ TEST_SUITE(RB) {
 		CHECK(NULL != root);
 		CHECK(NULL != node1);
 		CHECK(tree->root == root);
+		CHECK(root == node1->parent);
 		CHECK(31 == node1->contents);
 		CHECK(node1 == root->left);
 		CHECK(NULL == root->right);
@@ -66,6 +71,7 @@ TEST_SUITE(RB) {
 		CHECK(NULL != root);
 		CHECK(NULL != node2);
 		CHECK(tree->root == root);
+		CHECK(root == node2->parent);
 		CHECK(64 == node2->contents);
 		CHECK(node2 == root->right);
 		CHECK(NULL == root->left);
@@ -82,6 +88,8 @@ TEST_SUITE(RB) {
 		CHECK(NULL != node1);
 		CHECK(NULL != node2);
 		CHECK(tree->root == root);
+		CHECK(root == node1->parent);
+		CHECK(root == node2->parent);
 		CHECK(31 == node1->contents);
 		CHECK(64 == node2->contents);
 		CHECK(node1 == root->left);
@@ -91,5 +99,23 @@ TEST_SUITE(RB) {
 		CHECK(rb_tree_is_valid(tree));
 		mem_release(tree);
     }
+    /*
+    TEST(Verify_rb_insert_below_full_first_level_works){
+		rb_tree_t* tree = rb_tree_new();
+		rb_node_t* root = rb_tree_insert(tree, 42);
+		rb_node_t* node1 = rb_tree_insert(tree, 31);
+		rb_node_t* node2 = rb_tree_insert(tree, 64);
+		rb_node_t* node3 = rb_tree_insert(tree, 15);
+		CHECK(NULL != node3);
+		CHECK(15 == node3->contents);
+		CHECK(node1->left == node3);
+		CHECK(NULL == node3->left);
+		CHECK(NULL == node3->right);
+		CHECK(BLACK == root->color);
+		CHECK(
+		CHECK(rb_tree_is_valid(tree));
+		mem_release(tree);
+    }
+    */
 }
 
-- 
2.54.0