/*
* Copyright (c) 2019 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <vppinfra/rbtree.h>
#include <vlib/vlib.h>
#define RBTREE_TEST_I(_cond, _comment, _args...) \
({ \
int _evald = (_cond); \
if (!(_evald)) { \
fformat(stderr, "FAIL:%d: " _comment "\n", \
__LINE__, ##_args); \
} else { \
fformat(stderr, "PASS:%d: " _comment "\n", \
__LINE__, ##_args); \
} \
_evald; \
})
#define RBTREE_TEST(_cond, _comment, _args...) \
{ \
if (!RBTREE_TEST_I(_cond, _comment, ##_args)) { \
return 1; \
} \
}
static int
rbtree_test_basic (vlib_main_t * vm, unformat_input_t * input)
{
int __clib_unused verbose, n_keys = 1e3, i;
u32 *test_keys = 0, search_key;
rb_tree_t _rt, *rt = &_rt;
rb_node_t *n, *aux;
while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
{
if (unformat (input, "verbose"))
verbose = 1;
else if (unformat (input, "nkeys %u", &n_keys))
;
else
{
vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
input);
return -1;
}
}
rb_tree_init (rt);
RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "tnil created");
/*
* Add keys
*/
vec_validate (test_keys, n_keys - 1);
for (i = n_keys - 1; i >= 0; i--)
{
test_keys[i] = i;
rb_tree_add (rt, i);
}
RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "all nodes added");
n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (n->key == 0, "min should be %u", 0);
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys / 2);
RBTREE_TEST (n->key == n_keys / 2, "search result should be %u",
n_keys / 2);
aux = rb_tree_successor (rt, n);
RBTREE_TEST (aux->key == n_keys / 2 + 1, "successor should be %u is %u",
n_keys / 2 + 1, aux->key);
aux = rb_tree_predecessor (rt, n);
RBTREE_TEST (aux->key == n_keys / 2 - 1, "predecessor should be %u is %u",
n_keys / 2 - 1, aux->key);
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys);
RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
/*
* Delete even keys
*/
for (i = 0; i < n_keys; i += 2)
rb_tree_del (rt, i);
n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (n->key == 1, "min should be %u and is %u", 1, n->key);
search_key = 2 * ((n_keys - 1) / 4);
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
RBTREE_TEST (rb_node_is_tnil (rt, n), "search result for %u should be tnil",
search_key);
search_key += 1;
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
RBTREE_TEST (n->key == search_key, "search result should be %u",
search_key);
aux = rb_tree_successor (rt, n);
RBTREE_TEST (aux->key == search_key + 2, "successor should be %u is %u",
search_key + 2, aux->key);
aux = rb_tree_predecessor (rt, n);
RBTREE_TEST (aux->key == search_key - 2, "predecessor should be %u is %u",
search_key - 2, aux->key);
/*
* Re-add even keys
*/
for (i = 0; i < n_keys; i += 2)
rb_tree_add (rt, i);
RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "number nodes %u is %u",
n_keys + 1, rb_tree_n_nodes (rt));
n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (n->key == 0, "min should be %u", 0);
search_key = 2 * ((n_keys - 1) / 4);
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
RBTREE_TEST (n->key == search_key, "search result should be %u",
search_key);
search_key += 1;
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
RBTREE_TEST (n->key == search_key, "search result should be %u",
search_key);
aux = rb_tree_successor (rt, n);
RBTREE_TEST (aux->key == search_key + 1, "successor should be %u is %u",
search_key + 1, aux->key);
aux = rb_tree_predecessor (rt, n);
RBTREE_TEST (aux->key == search_key - 1, "predecessor should be %u is %u",
search_key - 1, aux->key);
/*
* Delete all keys
*/
for (i = 0; i < n_keys; i++)
{
rb_tree_del (rt, i);
if (rt->nodes[RBTREE_TNIL_INDEX].color != RBTREE_BLACK)
RBTREE_TEST (0, "tnil should be black");
}
RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
1, rb_tree_n_nodes (rt));
n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (rb_node_is_tnil (rt, n), "min should be tnil");
n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
RBTREE_TEST (rb_node_is_tnil (rt, n), "max should be tnil");
search_key = 2 * ((n_keys - 1) / 4);
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
/*
* Test successor/predecessor
*/
u8 test_vals[] = { 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 };
for (i = 0; i < sizeof (test_vals) / sizeof (u8); i++)
rb_tree_add (rt, test_vals[i]);
search_key = 13;
n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
RBTREE_TEST (n->key == search_key, "search result should be %u",
search_key);
aux = rb_tree_successor (rt, n);
RBTREE_TEST (aux->key == 15, "successor should be %u is %u", 15, aux->key);
aux = rb_tree_predecessor (rt, n);
RBTREE_TEST (aux->key == 9, "predecessor should be %u is %u", 9, aux->key);
n = aux;
aux = rb_tree_predecessor (rt, n);
RBTREE_TEST (aux->key == 7, "predecessor should be %u is %u", 7, aux->key);
/*
* Cleanup
*/
rb_tree_free_nodes (rt);
RBTREE_TEST (rb_tree_n_nodes (rt) == 0, "number nodes %u is %u",
0, rb_tree_n_nodes (rt));
return 0;
}
static clib_error_t *
rbtree_test (vlib_main_t * vm,
unformat_input_t * input, vlib_cli_command_t * cmd_arg)
{
int res = 0;
while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
{
if (unformat (input, "basic"))
{
res = rbtree_test_basic (vm, input);
}
else if (unformat (input, "all"))
{
if ((res = rbtree_test_basic (vm, input)))
goto done;
}
else
break;
}
done:
if (res)
return clib_error_return (0, "rbtree unit test failed");
return 0;
}
VLIB_CLI_COMMAND (rbtree_test_command, static) =
{
.path = "test rbtree",
.short_help = "internal rbtree unit tests",
.function = rbtree_test,
};
/*
* fd.io coding-style-patch-verification: ON
*
* Local Variables:
* eval: (c-set-style "gnu")
* End:
*/