From 2602d9ad82ebf27e42795688b9765e800a30abf9 Mon Sep 17 00:00:00 2001
From: a bellenir <a@bellenir.com>
Date: Tue, 5 Aug 2014 18:58:43 +0000
Subject: [PATCH] create red/black trees

---
 source/rb/rb.c  | 34 ++++++++++++++++++++++++++++++++++
 source/rb/rb.h  | 33 +++++++++++++++++++++++++++++++++
 tests/main.c    |  1 +
 tests/test_rb.c | 32 ++++++++++++++++++++++++++++++++
 4 files changed, 100 insertions(+)
 create mode 100644 source/rb/rb.c
 create mode 100644 source/rb/rb.h
 create mode 100644 tests/test_rb.c

diff --git a/source/rb/rb.c b/source/rb/rb.c
new file mode 100644
index 0000000..07de5f3
--- /dev/null
+++ b/source/rb/rb.c
@@ -0,0 +1,34 @@
+#include <stdlib.h>
+
+#include "mem.h"
+#include "rb.h"
+
+static void rb_tree_free(void* v_tree){
+	rb_tree_t* tree = (rb_tree_t*) v_tree;
+	if(tree && tree->root) mem_release(tree->root);
+}
+
+static void rb_node_free(void* v_node){
+	rb_node_t* node = (rb_node_t*) v_node;
+	if(node){
+		if(node->left) mem_release(node->left);
+		if(node->right) mem_release(node->right);
+	}
+}
+
+
+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->contents = contents;
+	node->color = RED;
+	return node;
+}
+
+rb_tree_t* rb_tree_new(){
+	rb_tree_t* tree = mem_allocate(sizeof(rb_tree_t), &rb_tree_free);
+	tree->root = NULL;
+	return tree;
+}
+
diff --git a/source/rb/rb.h b/source/rb/rb.h
new file mode 100644
index 0000000..06dd293
--- /dev/null
+++ b/source/rb/rb.h
@@ -0,0 +1,33 @@
+#ifndef RB_H
+#define RB_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef enum {
+	RED = 0,
+	BLACK
+} rb_color_t;
+
+typedef struct rb_node_t {
+	struct rb_node_t* left;
+	struct rb_node_t* right;
+	rb_color_t color;
+	int contents; /* int for development; TODO: make this a void* */
+} rb_node_t;
+
+typedef struct {
+	rb_node_t* root;
+} rb_tree_t;
+
+
+rb_node_t* rb_node_new(int contents);
+rb_tree_t* rb_tree_new();
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* RB_H */
+
diff --git a/tests/main.c b/tests/main.c
index 0e15d6b..b34c392 100644
--- a/tests/main.c
+++ b/tests/main.c
@@ -7,5 +7,6 @@ int main(int argc, char** argv)
     RUN_TEST_SUITE(Vector);
     RUN_TEST_SUITE(List);
     RUN_TEST_SUITE(Buffer);
+    RUN_TEST_SUITE(RB);
     return PRINT_TEST_RESULTS();
 }
diff --git a/tests/test_rb.c b/tests/test_rb.c
new file mode 100644
index 0000000..e2440c6
--- /dev/null
+++ b/tests/test_rb.c
@@ -0,0 +1,32 @@
+// Unit Test Framework Includes
+#include "test.h"
+
+#include "rb.h"
+#include "mem.h"
+
+static void test_setup(void) { }
+//-----------------------------------------------------------------------------
+// Begin Unit Tests
+//-----------------------------------------------------------------------------
+TEST_SUITE(RB) {
+    //-------------------------------------------------------------------------
+    // Test the rb_new functions
+    //-------------------------------------------------------------------------
+    TEST(Verify_rb_node_new_returns_a_new_node){
+		rb_node_t* node = rb_node_new(42);
+		CHECK(NULL != node);
+		CHECK(NULL == node->left);
+		CHECK(NULL == node->right);
+		CHECK(42 == node->contents);
+		mem_release(node);
+    }
+
+	TEST(Verify_rb_tree_new_returns_an_empty_red_black_tree){
+		rb_tree_t* rb = rb_tree_new();
+		CHECK(rb != NULL);
+		CHECK(rb->root == NULL);
+		mem_release(rb);
+	}
+
+}
+
-- 
2.52.0