tests/tree.c: Add test for tree_contains()

After writing the test, a failing case made me notice that the
comparison was reversed, and I then fixed the implementation :)

1 files changed, 102 insertions, 12 deletions

diff --git a/tests/tree.c b/tests/tree.c
index e2b2e0c..7676ab4 100644
--- a/tests/tree.c
+++ b/tests/tree.c
@@ -70,20 +70,110 @@ out:
 static void
 test_tree_contains(void) {
 
-	const int y0 = 7;
-	const int n0 = 1;
-
-	const struct Tree root = {
-		.value      = &y0,
-		.value_size = sizeof(int),
-		.left       = NULL,
-		.right      = NULL,
-		.height     = 3U,
+	const size_t value_size = sizeof(int);
+
+	/*
+		ASCII representation of the tree:
+
+		         12
+		      __/  \__
+		     /        \
+		    8          18
+		   / \        /
+		  5   11    17
+		 /
+		4
+
+	**/
+
+	// Values that don't exist on the tree
+	const int n0  = 0;
+	const int n1  = 1;
+	const int n2  = 2;
+	const int n3  = 3;
+	const int n6  = 6;
+	const int n7  = 7;
+	const int n9  = 9;
+	const int n10 = 10;
+	const int n13 = 13;
+	const int n14 = 14;
+	const int n15 = 15;
+	const int n16 = 16;
+	const int n19 = 19;
+
+	// Values that DO exist on the tree
+	const int y12 = 12;
+	const int y8  = 8;
+	const int y18 = 18;
+	const int y5  = 5;
+	const int y11 = 11;
+	const int y17 = 17;
+	const int y4  = 4;
+
+	const struct Tree *const t = &(struct Tree) {
+		.value      = &y12,
+		.value_size = value_size,
+		.height     = 4U,
+		.left       = &(struct Tree) {
+			.value      = &y8,
+			.value_size = value_size,
+			.left       = &(struct Tree) {
+				.value      = &y5,
+				.value_size = value_size,
+				.left       = &(struct Tree) {
+					.value      = &y4,
+					.value_size = value_size,
+					.left       = NULL,
+					.right      = NULL,
+					.height     = 1U
+				},
+				.right      = NULL,
+				.height     = 2U,
+			},
+			.right      = &(struct Tree) {
+				.value      = &y11,
+				.value_size = value_size,
+				.left       = NULL,
+				.right      = NULL,
+				.height     = 1U,
+			},
+			.height     = 3U,
+		},
+		.right      = &(struct Tree) {
+			.value      = &y18,
+			.value_size = value_size,
+			.left       = &(struct Tree) {
+				.value      = &y17,
+				.value_size = value_size,
+				.left       = NULL,
+				.right      = NULL,
+				.height     = 1U,
+			},
+			.right      = NULL,
+			.height     = 2U,
+		},
 	};
 
-	assert(tree_contains(&root, &y0));
-
-	assert(!tree_contains(&root, &n0));
+	assert(!tree_contains(t, &n0));
+	assert(!tree_contains(t, &n1));
+	assert(!tree_contains(t, &n2));
+	assert(!tree_contains(t, &n3));
+	assert( tree_contains(t, &y4));
+	assert( tree_contains(t, &y5));
+	assert(!tree_contains(t, &n6));
+	assert(!tree_contains(t, &n7));
+	assert( tree_contains(t, &y8));
+	assert(!tree_contains(t, &n9));
+	assert(!tree_contains(t, &n10));
+	assert( tree_contains(t, &y11));
+	assert( tree_contains(t, &y12));
+	assert(!tree_contains(t, &n13));
+	assert(!tree_contains(t, &n14));
+	assert(!tree_contains(t, &n15));
+	assert(!tree_contains(t, &n16));
+	assert( tree_contains(t, &y17));
+	assert( tree_contains(t, &y18));
+	assert(!tree_contains(t, &n19));
 }
 
 int