Add a test for the minimal rb-tree implementation

Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

2 files changed, 183 insertions, 2 deletions

diff --git a/tests/Makemodule.am b/tests/Makemodule.am
index 83f8666..8016c83 100644
--- a/tests/Makemodule.am
+++ b/tests/Makemodule.am
@@ -6,11 +6,15 @@ test_str_table_LDADD = libutil.a libcompat.a
 test_str_table_CPPFLAGS = $(AM_CPPFLAGS) -DTESTPATH=$(top_srcdir)/tests
 test_str_table_CPPFLAGS += -I$(top_srcdir)/lib/sqfs
 
+test_rbtree_SOURCES = tests/rbtree.c
+test_rbtree_LDADD = libutil.a libcompat.a
+test_rbtree_CPPFLAGS = $(AM_CPPFLAGS) -I$(top_srcdir)/lib/sqfs
+
 test_abi_SOURCES = tests/abi.c
 test_abi_LDADD = libsquashfs.la
 
-check_PROGRAMS += test_canonicalize_name test_str_table test_abi
-TESTS += test_canonicalize_name test_str_table test_abi
+check_PROGRAMS += test_canonicalize_name test_str_table test_abi test_rbtree
+TESTS += test_canonicalize_name test_str_table test_abi test_rbtree
 
 if BUILD_TOOLS
 test_mknode_simple_SOURCES = tests/mknode_simple.c
diff --git a/tests/rbtree.c b/tests/rbtree.c
new file mode 100644
index 0000000..1c5ab4d
--- /dev/null
+++ b/tests/rbtree.c
@@ -0,0 +1,177 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+/*
+ * rbtree.c
+ *
+ * Copyright (C) 2020 David Oberhollenzer <goliath@infraroot.at>
+ */
+#include "config.h"
+
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "rbtree.h"
+
+static int key_compare(const void *a, const void *b)
+{
+	return *((sqfs_s32 *)a) - *((sqfs_s32 *)b);
+}
+
+static size_t count_nodes_dfs(rbtree_node_t *n)
+{
+	return 1 + (n->left == NULL ? 0 : count_nodes_dfs(n->left))
+		+ (n->right == NULL ? 0 : count_nodes_dfs(n->right));
+}
+
+static size_t min_depth(rbtree_node_t *n)
+{
+	size_t lhs, rhs;
+
+	if (n == NULL)
+		return 0;
+
+	lhs = min_depth(n->left) + 1;
+	rhs = min_depth(n->right) + 1;
+
+	return lhs < rhs ? lhs : rhs;
+}
+
+static size_t max_depth(rbtree_node_t *n)
+{
+	size_t lhs, rhs;
+
+	if (n == NULL)
+		return 0;
+
+	lhs = min_depth(n->left) + 1;
+	rhs = min_depth(n->right) + 1;
+
+	return lhs > rhs ? lhs : rhs;
+}
+
+static size_t get_ref_black_depth(rbtree_t *rb)
+{
+	rbtree_node_t *n;
+	size_t count = 0;
+
+	for (n = rb->root; n != NULL; n = n->left) {
+		if (!n->is_red)
+			count += 1;
+	}
+
+	return count;
+}
+
+static void check_binary_tree_dfs(rbtree_node_t *n)
+{
+	const void *key = rbtree_node_key(n);
+	const void *cmp;
+
+	if (n->left != NULL) {
+		cmp = rbtree_node_key(n->left);
+		assert(key_compare(cmp, key) < 0);
+
+		check_binary_tree_dfs(n->left);
+	}
+
+	if (n->right != NULL) {
+		cmp = rbtree_node_key(n->right);
+		assert(key_compare(cmp, key) > 0);
+
+		check_binary_tree_dfs(n->right);
+	}
+}
+
+static void check_colors_dfs(rbtree_node_t *n)
+{
+	if (n->is_red) {
+		assert(n->left == NULL || !n->left->is_red);
+		assert(n->right == NULL || !n->right->is_red);
+	}
+
+	if (n->left != NULL)
+		check_colors_dfs(n->left);
+
+	if (n->right != NULL)
+		check_colors_dfs(n->right);
+}
+
+static void check_black_depth_dfs(rbtree_node_t *n, size_t ref,
+				  size_t counter)
+{
+	if (!n->is_red)
+		counter += 1;
+
+	if (n->left == NULL || n->right == NULL)
+		assert(counter == ref);
+
+	if (n->left != NULL)
+		check_black_depth_dfs(n->left, ref, counter);
+
+	if (n->right != NULL)
+		check_black_depth_dfs(n->right, ref, counter);
+}
+
+int main(void)
+{
+	size_t count, blkdepth, mind, maxd;
+	sqfs_s32 key, key2;
+	rbtree_node_t *n;
+	sqfs_u64 value;
+	rbtree_t rb;
+
+	assert(rbtree_init(&rb, sizeof(sqfs_s32),
+			   sizeof(sqfs_u64), key_compare) == 0);
+
+	count = 0;
+
+	for (key = -1000; key < 1000; ++key) {
+		/* lookup of current key must fail prior to insert */
+		assert(rbtree_lookup(&rb, &key) == NULL);
+
+		/* previous key/value pairs must still be there */
+		for (key2 = -1000; key2 < key; ++key2) {
+			n = rbtree_lookup(&rb, &key2);
+			assert(n != NULL);
+			value = *((sqfs_u64 *)rbtree_node_value(n));
+			assert((sqfs_u64)(key2 + 10000) == value);
+		}
+
+		/* insert key value pair */
+		value = key + 10000;
+		assert(rbtree_insert(&rb, &key, &value) == 0);
+		count += 1;
+
+		/* check if the tree has the right number of nodes */
+		assert(count_nodes_dfs(rb.root) == count);
+
+		/* check if it is still a binary tree */
+		check_binary_tree_dfs(rb.root);
+
+		/* root node must be black. Every red node
+		   must have black children. */
+		assert(!rb.root->is_red);
+		check_colors_dfs(rb.root);
+
+		/* every path from the root to a leave must have
+		   the same number of black nodes. */
+		blkdepth = get_ref_black_depth(&rb);
+		check_black_depth_dfs(rb.root, blkdepth, 0);
+
+		/* longest root to leaf path must be at most
+		   twice as long as the shortest. */
+		mind = min_depth(rb.root);
+		maxd = max_depth(rb.root);
+		assert(maxd <= mind * 2);
+
+		/* lookup of current key must work after insert */
+		n = rbtree_lookup(&rb, &key);
+		assert(n != NULL);
+		value = *((sqfs_u64 *)rbtree_node_value(n));
+		assert((sqfs_u64)(key + 10000) == value);
+	}
+
+	rbtree_cleanup(&rb);
+	return EXIT_SUCCESS;
+}