diff options
| -rw-r--r-- | tests/Makemodule.am | 8 | ||||
| -rw-r--r-- | tests/rbtree.c | 177 |
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; +} |