Mercurial > libjeffpc

changeset 503:5962e595fd54

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
tree: move BST expected values into separate file This cuts down on #ifdef mess. Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
author Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
date Fri, 20 Jul 2018 14:57:11 -0400
parents c87d9f4c410c
children 5a8e2ed5a662
files tests/test_tree_bst.c tests/test_tree_common.c
diffstat 2 files changed, 269 insertions(+), 154 deletions(-) [+]
line wrap: on
line diff
--- a/tests/test_tree_bst.c	Wed Jul 18 09:43:38 2018 -0400
+++ b/tests/test_tree_bst.c	Fri Jul 20 14:57:11 2018 -0400
@@ -23,3 +23,155 @@
 #define TEST_TREE_BST
 
 #include "test_tree_common.c"
+
+static struct test2 checks2[2] = {
+	[true]  = {
+		"ascending",
+		{ &a, NULL, &b },
+	},
+	[false] = {
+		"descending",
+		{ &b, &a, NULL },
+	},
+};
+
+static struct test3 checks3[6] = {
+	[0] = {
+		.pre = { &a,
+			 NULL, &b,
+			 NULL, NULL, NULL, &c },
+	},
+	[1] = {
+		.pre = { &a,
+			 NULL, &c,
+			 NULL, NULL, &b, NULL },
+	},
+	[2] = {
+		.pre = { &b,
+			 &a, &c },
+	},
+	[3] = {
+		.pre = { &b,
+			 &a, &c },
+	},
+	[4] = {
+		.pre = { &c,
+			 &a, NULL,
+			 NULL, &b, NULL, NULL },
+	},
+	[5] = {
+		.pre = { &c,
+			 &b, NULL,
+			 &a, NULL, NULL, NULL },
+	},
+};
+
+static struct test4 checks4[24] = {
+	[0]  = {
+		.pre = { &a,
+			 NULL, &b,
+			 NULL, NULL, NULL, &c,
+			 NULL, NULL, NULL, NULL, NULL, NULL, NULL, &d },
+	},
+	[1]  = {
+		.pre = { &a,
+			 NULL, &c,
+			 NULL, NULL, &b, &d },
+	},
+	[2]  = {
+		.pre = TEST4_BACD,
+	},
+	[3]  = {
+		.pre = TEST4_BACD,
+	},
+	[4]  = {
+		.pre = TEST4_CADB,
+	},
+	[5]  = {
+		.pre = TEST4_CBDA,
+	},
+
+	[6]  = {
+		.pre = { &a,
+			 NULL, &b,
+			 NULL, NULL, NULL, &d,
+			 NULL, NULL, NULL, NULL, NULL, NULL, &c, NULL },
+	},
+	[7]  = {
+		.pre = { &a,
+			 NULL, &c,
+			 NULL, NULL, &b, &d },
+	},
+	[8]  = {
+		.pre = TEST4_BADC,
+	},
+	[9]  = {
+		.pre = TEST4_BACD,
+	},
+	[10] = {
+		.pre = TEST4_CADB,
+	},
+	[11] = {
+		.pre = TEST4_CBDA,
+	},
+
+	[12] = {
+		.pre = { &a,
+			 NULL, &d,
+			 NULL, NULL, &b, NULL,
+			 NULL, NULL, NULL, NULL, NULL, &c, NULL, NULL },
+	},
+	[13] = {
+		.pre = { &a,
+			 NULL, &d,
+			 NULL, NULL, &c, NULL,
+			 NULL, NULL, NULL, NULL, &b, NULL, NULL, NULL },
+	},
+	[14] = {
+		.pre = TEST4_BADC,
+	},
+	[15] = {
+		.pre = TEST4_BADC,
+	},
+	[16] = {
+		.pre = TEST4_CADB,
+	},
+	[17] = {
+		.pre = TEST4_CBDA,
+	},
+
+	[18] = {
+		.pre = { &d,
+			 &a, NULL,
+			 NULL, &b, NULL, NULL,
+			 NULL, NULL, NULL, &c, NULL, NULL, NULL, NULL },
+	},
+	[19] = {
+		.pre = { &d,
+			 &a, NULL,
+			 NULL, &c, NULL, NULL,
+			 NULL, NULL, &b, NULL, NULL, NULL, NULL, NULL },
+	},
+	[20] = {
+		.pre = { &d,
+			 &b, NULL,
+			 &a, &c, NULL, NULL},
+	},
+	[21] = {
+		.pre = { &d,
+			 &b, NULL,
+			 &a, &c, NULL, NULL},
+	},
+	[22] = {
+		.pre = { &d,
+			 &c, NULL,
+			 &a, NULL, NULL, NULL,
+			 NULL, &b, NULL, NULL, NULL, NULL, NULL, NULL },
+	},
+	[23] = {
+		.pre = { &d,
+			 &c, NULL,
+			 &b, NULL, NULL, NULL,
+			 &a, NULL, NULL, NULL, NULL, NULL, NULL, NULL },
+	},
+};
--- a/tests/test_tree_common.c	Wed Jul 18 09:43:38 2018 -0400
+++ b/tests/test_tree_common.c	Fri Jul 20 14:57:11 2018 -0400
@@ -41,9 +41,67 @@
 
 struct node {
 	struct TREE_NODE node;
+	const char *name;
 	int v;
 };
 
+/* various balanced orderings */
+#define TEST3_BAC	{ &b, \
+			  &a, &c }
+#define TEST3_BAD	{ &b, \
+			  &a, &d }
+#define TEST3_CAD	{ &c, \
+			  &a, &d }
+#define TEST3_CBD	{ &c, \
+			  &b, &d }
+
+#define TEST4_BACD	{ &b, \
+			  &a, &c, \
+			  NULL, NULL, NULL, &d }
+#define TEST4_BADC	{ &b, \
+			  &a, &d, \
+			  NULL, NULL, &c, NULL }
+#define TEST4_CADB	{ &c, \
+			  &a, &d, \
+			  NULL, &b, NULL, NULL }
+#define TEST4_CBDA	{ &c, \
+			  &b, &d, \
+			  &a, NULL, NULL, NULL }
+
+static struct node a = { .name = "a", .v = 10 };
+static struct node b = { .name = "b", .v = 20 };
+static struct node c = { .name = "c", .v = 30 };
+static struct node d = { .name = "d", .v = 40 };
+
+struct test2 {
+	const char *name;
+	struct node *pre[3];
+	struct subtest {
+		struct node *remove;
+		struct node *post[1];
+	} sub[2];
+};
+
+struct test3 {
+	struct node *pre[7];
+	struct {
+		struct node *remove;
+		struct node *nodes[3];
+	} sub[3];
+};
+
+struct test4 {
+	struct node *pre[15];
+	struct {
+		struct node *remove;
+		struct node *nodes[7];
+	} sub[4];
+};
+
+static struct test2 checks2[2];
+static struct test3 checks3[6];
+static struct test4 checks4[24];
+
 static int cmp(const void *va, const void *vb)
 {
 	const struct node *a = va;
@@ -56,12 +114,14 @@
 	return 0;
 }
 
-static void init(struct TREE_TREE *tree, const char *testname,
-		 size_t numnodes, struct node **nodes)
+static void init(struct TREE_TREE *tree, const char *testname, const char *nodename,
+		 size_t numnodes, struct node **nodes, bool begin)
 {
 	size_t i;
 
-	fprintf(stderr, "Testing %zu node tree (%s)...", numnodes, testname);
+	if (begin)
+		fprintf(stderr, "%zu nodes: %s - %s...", numnodes, testname,
+			nodename);
 
 	TREE_CREATE(tree, cmp, sizeof(struct node),
 		    offsetof(struct node, node));
@@ -82,15 +142,14 @@
 	memset(&cookie, 0, sizeof(cookie));
 	removed_nodes = 0;
 
-	while ((node = TREE_DESTROY_NODES(tree, &cookie))) {
-		memset(node, 0xba, sizeof(struct node));
+	while ((node = TREE_DESTROY_NODES(tree, &cookie)))
 		removed_nodes++;
-	}
 
 	return removed_nodes;
 }
 
-static void destroy(struct TREE_TREE *tree, size_t expected_numnodes)
+static void destroy(struct TREE_TREE *tree, size_t expected_numnodes,
+		    bool done)
 {
 	size_t remaining_nodes;
 
@@ -106,7 +165,8 @@
 
 	TREE_DESTROY(tree);
 
-	fprintf(stderr, "ok.\n");
+	if (done)
+		fprintf(stderr, "ok.\n");
 }
 
 static void __verify_nodes(struct tree_node *node, size_t numnodes,
@@ -164,60 +224,55 @@
 	VERIFY3U(TREE_NUMNODES(tree), ==, expected_numnodes);
 }
 
-static void test_nodes(const char *testname,
+static void test_nodes(const char *testname, struct node *remove,
 		       size_t numinsert, struct node **inserts,
-		       size_t numcheck, struct node **checks)
+		       size_t npre, struct node **pre,
+		       size_t npost, struct node **post)
 {
 	struct TREE_TREE tree;
 
-	init(&tree, testname, numinsert, inserts);
-	verify_nodes(&tree, numcheck, checks);
+	init(&tree, testname, remove ? remove->name : "(none)", numinsert, inserts, true);
+	verify_nodes(&tree, npre, pre);
 	verify_iter(&tree, numinsert);
-	destroy(&tree, numinsert);
+	destroy(&tree, numinsert - 1, true);
 }
 
-static void test_insert_empty(void)
+static void test_empty(void)
 {
-	test_nodes("empty", 0, NULL, 0, NULL);
+	test_nodes("empty", NULL,
+		   0, NULL, 0, NULL, 0, NULL);
 }
 
-static void test_insert_one(void)
+static void test_one(void)
 {
-	struct node a = { .v = 10 };
 	struct node *inserts[1] = { &a };
 	struct node *checks[1] = { &a };
 
-	test_nodes("root",
+	test_nodes("root only", &a,
 		   ARRAY_LEN(inserts), inserts,
-		   ARRAY_LEN(checks), checks);
+		   ARRAY_LEN(checks), checks,
+		   0, NULL);
 }
 
-static void test_insert_two(bool asc)
+static void test_two(bool asc)
 {
-	struct node a = { .v = 10 };
-	struct node b = { .v = 20 };
+	size_t i;
 	struct node *inserts[2][2] = {
 		[true]  = { &a, &b },
 		[false] = { &b, &a },
 	};
-	struct node *checks[2][3] = {
-#if defined(TEST_TREE_BST)
-		[true]  = { &a, NULL, &b },
-		[false] = { &b, &a, NULL },
-#endif
-	};
 
-	test_nodes("two descending",
-		   ARRAY_LEN(inserts[asc]), inserts[asc],
-		   ARRAY_LEN(checks[asc]), checks[asc]);
+	for (i = 0; i < 2; i++)
+		test_nodes(checks2[asc].name,
+			   checks2[asc].sub[i].remove,
+			   ARRAY_LEN(inserts[asc]), inserts[asc],
+			   ARRAY_LEN(checks2[asc].pre), checks2[asc].pre,
+			   ARRAY_LEN(checks2[asc].sub[i].post), checks2[asc].sub[i].post);
 }
 
-static void test_insert_three(int perm)
+static void test_three(int perm)
 {
-	char name[64];
-	struct node a = { .v = 10 };
-	struct node b = { .v = 20 };
-	struct node c = { .v = 30 };
+	size_t i;
 	struct node *inserts[6][3] = {
 		[0] = { &a, &b, &c },
 		[1] = { &a, &c, &b },
@@ -226,41 +281,22 @@
 		[4] = { &c, &a, &b },
 		[5] = { &c, &b, &a },
 	};
-	struct node *checks[6][7] = {
-#if defined(TEST_TREE_BST)
-		[0] = { &a,
-			NULL, &b,
-			NULL, NULL, NULL, &c },
-		[1] = { &a,
-			NULL, &c,
-			NULL, NULL, &b, NULL },
-		[2] = { &b,
-			&a, &c },
-		[3] = { &b,
-			&a, &c },
-		[4] = { &c,
-			&a, NULL,
-			NULL, &b, NULL, NULL },
-		[5] = { &c,
-			&b, NULL,
-			&a, NULL, NULL, NULL },
-#endif
-	};
+
+	for (i = 0; i < 3 ; i++) {
+		char name[64];
+
+		snprintf(name, sizeof(name), "permutation: %d", perm);
 
-	snprintf(name, sizeof(name), "permutation: %d", perm);
-
-	test_nodes(name,
-		   ARRAY_LEN(inserts[perm]), inserts[perm],
-		   ARRAY_LEN(checks[perm]), checks[perm]);
+		test_nodes(name, checks3[perm].sub[i].remove,
+			   ARRAY_LEN(inserts[perm]), inserts[perm],
+			   ARRAY_LEN(checks3[perm].pre), checks3[perm].pre,
+			   ARRAY_LEN(checks3[perm].sub[i].nodes), checks3[perm].sub[i].nodes);
+	}
 }
 
-static void test_insert_four(int perm)
+static void test_four(int perm)
 {
-	char name[64];
-	struct node a = { .v = 10 };
-	struct node b = { .v = 20 };
-	struct node c = { .v = 30 };
-	struct node d = { .v = 40 };
+	size_t i;
 	struct node *inserts[24][4] = {
 		[0]  = { &a, &b, &c, &d },
 		[1]  = { &a, &c, &b, &d },
@@ -291,103 +327,30 @@
 		[23] = { &d, &c, &b, &a },
 	};
 
-	/* various balanced orderings */
-#define TEST4_BACD	{ &b, \
-			  &a, &c, \
-			  NULL, NULL, NULL, &d }
-#define TEST4_BADC	{ &b, \
-			  &a, &d, \
-			  NULL, NULL, &c, NULL }
-#define TEST4_CADB	{ &c, \
-			  &a, &d, \
-			  NULL, &b, NULL, NULL }
-#define TEST4_CBDA	{ &c, \
-			  &b, &d, \
-			  &a, NULL, NULL, NULL }
+	for (i = 0; i < 4 ; i++) {
+		char name[64];
 
-	struct node *checks[24][15] = {
-#if defined(TEST_TREE_BST)
-		[0]  = { &a,
-			 NULL, &b,
-			 NULL, NULL, NULL, &c,
-			 NULL, NULL, NULL, NULL, NULL, NULL, NULL, &d },
-		[1]  = { &a,
-			 NULL, &c,
-			 NULL, NULL, &b, &d },
-		[2]  = TEST4_BACD,
-		[3]  = TEST4_BACD,
-		[4]  = TEST4_CADB,
-		[5]  = TEST4_CBDA,
-
-		[6]  = { &a,
-			 NULL, &b,
-			 NULL, NULL, NULL, &d,
-			 NULL, NULL, NULL, NULL, NULL, NULL, &c, NULL },
-		[7]  = { &a,
-			 NULL, &c,
-			 NULL, NULL, &b, &d },
-		[8]  = TEST4_BADC,
-		[9]  = TEST4_BACD,
-		[10] = TEST4_CADB,
-		[11] = TEST4_CBDA,
+		snprintf(name, sizeof(name), "permutation: %d", perm);
 
-		[12] = { &a,
-			 NULL, &d,
-			 NULL, NULL, &b, NULL,
-			 NULL, NULL, NULL, NULL, NULL, &c, NULL, NULL },
-		[13] = { &a,
-			 NULL, &d,
-			 NULL, NULL, &c, NULL,
-			 NULL, NULL, NULL, NULL, &b, NULL, NULL, NULL },
-		[14] = TEST4_BADC,
-		[15] = TEST4_BADC,
-		[16] = TEST4_CADB,
-		[17] = TEST4_CBDA,
-
-		[18] = { &d,
-			 &a, NULL,
-			 NULL, &b, NULL, NULL,
-			 NULL, NULL, NULL, &c, NULL, NULL, NULL, NULL },
-		[19] = { &d,
-			 &a, NULL,
-			 NULL, &c, NULL, NULL,
-			 NULL, NULL, &b, NULL, NULL, NULL, NULL, NULL },
-		[20] = { &d,
-			 &b, NULL,
-			 &a, &c, NULL, NULL},
-		[21] = { &d,
-			 &b, NULL,
-			 &a, &c, NULL, NULL},
-		[22] = { &d,
-			 &c, NULL,
-			 &a, NULL, NULL, NULL,
-			 NULL, &b, NULL, NULL, NULL, NULL, NULL, NULL },
-		[23] = { &d,
-			 &c, NULL,
-			 &b, NULL, NULL, NULL,
-			 &a, NULL, NULL, NULL, NULL, NULL, NULL, NULL },
-#endif
-	};
-
-	snprintf(name, sizeof(name), "permutation: %d", perm);
-
-	test_nodes(name,
-		   ARRAY_LEN(inserts[perm]), inserts[perm],
-		   ARRAY_LEN(checks[perm]), checks[perm]);
+		test_nodes(name, checks4[perm].sub[i].remove,
+			   ARRAY_LEN(inserts[perm]), inserts[perm],
+			   ARRAY_LEN(checks4[perm].pre), checks4[perm].pre,
+			   ARRAY_LEN(checks4[perm].sub[i].nodes), checks4[perm].sub[i].nodes);
+	}
 }
 
 static void test_insert(void)
 {
 	int i;
 
-	test_insert_empty();
-	test_insert_one();
-	test_insert_two(true);
-	test_insert_two(false);
+	test_empty();
+	test_one();
+	test_two(true);
+	test_two(false);
 	for (i = 0; i < 6; i++)
-		test_insert_three(i);
+		test_three(i);
 	for (i = 0; i < 24; i++)
-		test_insert_four(i);
+		test_four(i);
 }
 
 void test(void)