Boot Linux faster!

Check our new training course

Boot Linux faster!

Check our new training course
and Creative Commons CC-BY-SA
lecture and lab materials

Bootlin logo

Elixir Cross Referencer

/*
 * Copyright (c) 2017 Intel Corporation
 *
 * SPDX-License-Identifier: Apache-2.0
 */

#include <ztest.h>
#include <sys/rb.h>

#define TREE_SIZE 512
/* zephyr can't do floating-point arithmetic,
 * so manual: dlog_N = 2log(TREE_SIZE) = 18
 */
const static uint32_t dlog_N = 18;

/* rbnode structure is embeddedable in user structure */
struct container_node {
	struct rbnode node;
	int value;
};
static struct rbnode nodes[TREE_SIZE];
static struct rbtree tree;

/* Our "lessthan" is just the location of the struct */
bool node_lessthan(struct rbnode *a, struct rbnode *b)
{
	return a < b;
}

/**
 * @brief Test whether rbtree node struct is embedded
 * in any user struct
 *
 * @details Initialize a user defined structure contains
 * rbtree node.And into a rbtree and enumerate
 * the rbtree nodes.
 *
 * verify that the value enumerated is equal to the
 * value initialized.If the verification pass,the user
 * defined structure works.
 * verify "for each" style APIs work.
 *
 * @ingroup lib_rbtree_tests
 *
 * @see RB_FOR_EACH(),RB_FOR_EACH_CONTAINER()
 */
void test_rbtree_container(void)
{
	int count = 0;
	struct rbtree test_tree_l;
	struct container_node *c_foreach_node;
	struct rbnode *foreach_node;
	struct container_node tree_node[10];

	test_tree_l.lessthan_fn = node_lessthan;
	for (uint32_t i = 0; i < ARRAY_SIZE(tree_node); i++) {
		tree_node[i].value = i;
		rb_insert(&test_tree_l, &tree_node[i].node);
	}

	RB_FOR_EACH(&test_tree_l, foreach_node) {
		zassert_true(CONTAINER_OF(foreach_node, struct container_node,
		node)->value == count, "RB_FOR_EACH failed");
		count++;
	}

	count = 0;

	RB_FOR_EACH_CONTAINER(&test_tree_l, c_foreach_node, node) {
		zassert_true(c_foreach_node->value == count,
		"RB_FOR_EACH_CONTAINER failed");
		count++;
	}
}

/* initialize and insert a tree */
void init_tree(struct rbtree *tree, int size)
{
	tree->lessthan_fn = node_lessthan;

	for (uint32_t i = 0; i < size; i++) {
		rb_insert(tree, &nodes[i]);
	}
}

int search_height_recurse(struct rbnode *node, struct rbnode
			*final_node, uint32_t current_height)
{
	if (node == NULL) {
		return -1;
	}

	if (node == final_node) {
		return current_height;
	}

	current_height++;
	struct rbnode *ch = z_rb_child(node,
			!tree.lessthan_fn(final_node, node));

	return search_height_recurse(ch, final_node, current_height);
}

void verify_rbtree_perf(struct rbnode *root, struct rbnode *test)
{
	uint32_t node_height = 0;

	node_height = search_height_recurse(root, test, node_height);
	zassert_true(node_height <= dlog_N, NULL);
}

/**
 * @brief Test some operations of rbtree are running in
 * logarithmic time
 *
 * @details
 * Defining a rbtree and then searching height of maximum(minimum)
 * node(searched,inserted or removed),and finally record those heights.
 *
 * verify that search heights are less than the height of
 * worset-case condition(<= 2lg(N)).(N is the size of tree)
 *
 * @ingroup lib_rbtree_tests
 *
 * @see rb_get_min(),rb_get_max()
 */
void test_rbtree_perf(void)
{
	init_tree(&tree, TREE_SIZE);
	struct rbnode *root = tree.root;
	struct rbnode *test = NULL;

	test = rb_get_min(&tree);
	verify_rbtree_perf(root, test);

	test = rb_get_max(&tree);
	verify_rbtree_perf(root, test);

	/* insert and remove a same node with same height.Assume that
	 * the node nodes[TREE_SIZE/2] will be removed and inserted,
	 * verify that searching times is less than 2logN
	 * using the height of this node.
	 */
	test = &nodes[TREE_SIZE/2];
	verify_rbtree_perf(root, test);
}

void test_main(void)
{
	ztest_test_suite(rbtree,
			 ztest_unit_test(test_rbtree_container),
			 ztest_unit_test(test_rbtree_perf)
			 );
	ztest_run_test_suite(rbtree);
}