2 * Copyright (c) 2019 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
15 #include <vppinfra/rbtree.h>
16 #include <vlib/vlib.h>
18 #define RBTREE_TEST_I(_cond, _comment, _args...) \
20 int _evald = (_cond); \
22 fformat(stderr, "FAIL:%d: " _comment "\n", \
25 fformat(stderr, "PASS:%d: " _comment "\n", \
31 #define RBTREE_TEST(_cond, _comment, _args...) \
33 if (!RBTREE_TEST_I(_cond, _comment, ##_args)) { \
39 rbtree_test_basic (vlib_main_t * vm, unformat_input_t * input)
41 int __clib_unused verbose, n_keys = 1e3, i;
42 u32 *test_keys = 0, search_key;
43 rb_tree_t _rt, *rt = &_rt;
46 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
48 if (unformat (input, "verbose"))
50 else if (unformat (input, "nkeys %u", &n_keys))
54 vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
61 RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "tnil created");
66 vec_validate (test_keys, n_keys - 1);
67 for (i = n_keys - 1; i >= 0; i--)
73 RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "all nodes added");
75 n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
76 RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
78 n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
79 RBTREE_TEST (n->key == 0, "min should be %u", 0);
81 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys / 2);
82 RBTREE_TEST (n->key == n_keys / 2, "search result should be %u",
85 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys);
86 RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
91 for (i = 0; i < (n_keys - 1) / 2; i += 2)
94 n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
95 RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
97 n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
98 RBTREE_TEST (n->key == 1, "min should be %u and is %u", 1, n->key);
100 search_key = 2 * ((n_keys - 1) / 4);
101 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
102 RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
105 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
106 RBTREE_TEST (n->key == search_key, "search result should be %u",
112 for (i = 0; i < (n_keys - 1) / 2; i += 2)
115 RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "number nodes %u is %u",
116 n_keys + 1, rb_tree_n_nodes (rt));
118 n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
119 RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
121 n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
122 RBTREE_TEST (n->key == 0, "min should be %u", 0);
124 search_key = 2 * ((n_keys - 1) / 4);
125 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
126 RBTREE_TEST (n->key == search_key, "search result should be %u",
130 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
131 RBTREE_TEST (n->key == search_key, "search result should be %u",
137 for (i = 0; i < n_keys; i++)
140 RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
141 1, rb_tree_n_nodes (rt));
143 n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
144 RBTREE_TEST (rb_node_is_tnil (rt, n), "min should be tnil");
146 n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
147 RBTREE_TEST (rb_node_is_tnil (rt, n), "max should be tnil");
149 search_key = 2 * ((n_keys - 1) / 4);
150 n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
151 RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
153 rb_tree_free_nodes (rt);
154 RBTREE_TEST (rb_tree_n_nodes (rt) == 0, "number nodes %u is %u",
155 0, rb_tree_n_nodes (rt));
160 static clib_error_t *
161 rbtree_test (vlib_main_t * vm,
162 unformat_input_t * input, vlib_cli_command_t * cmd_arg)
166 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
168 if (unformat (input, "basic"))
170 res = rbtree_test_basic (vm, input);
172 else if (unformat (input, "all"))
174 if ((res = rbtree_test_basic (vm, input)))
183 return clib_error_return (0, "rbtree unit test failed");
188 VLIB_CLI_COMMAND (rbtree_test_command, static) =
190 .path = "test rbtree",
191 .short_help = "internal rbtree unit tests",
192 .function = rbtree_test,
197 * fd.io coding-style-patch-verification: ON
200 * eval: (c-set-style "gnu")