Line data Source code
1 : /*
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:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
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.
14 : */
15 : #include <vppinfra/rbtree.h>
16 : #include <vlib/vlib.h>
17 :
18 : #define RBTREE_TEST_I(_cond, _comment, _args...) \
19 : ({ \
20 : int _evald = (_cond); \
21 : if (!(_evald)) { \
22 : fformat(stderr, "FAIL:%d: " _comment "\n", \
23 : __LINE__, ##_args); \
24 : } else { \
25 : fformat(stderr, "PASS:%d: " _comment "\n", \
26 : __LINE__, ##_args); \
27 : } \
28 : _evald; \
29 : })
30 :
31 : #define RBTREE_TEST(_cond, _comment, _args...) \
32 : { \
33 : if (!RBTREE_TEST_I(_cond, _comment, ##_args)) { \
34 : return 1; \
35 : } \
36 : }
37 :
38 : static int
39 0 : rbtree_test_basic (vlib_main_t * vm, unformat_input_t * input)
40 : {
41 0 : int __clib_unused verbose, n_keys = 1e3, i;
42 0 : u32 *test_keys = 0, search_key;
43 0 : rb_tree_t _rt, *rt = &_rt;
44 : rb_node_t *n, *aux;
45 :
46 0 : while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
47 : {
48 0 : if (unformat (input, "verbose"))
49 0 : verbose = 1;
50 0 : else if (unformat (input, "nkeys %u", &n_keys))
51 : ;
52 : else
53 : {
54 0 : vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
55 : input);
56 0 : return -1;
57 : }
58 : }
59 :
60 0 : rb_tree_init (rt);
61 0 : RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "tnil created");
62 :
63 : /*
64 : * Add keys
65 : */
66 0 : vec_validate (test_keys, n_keys - 1);
67 0 : for (i = n_keys - 1; i >= 0; i--)
68 : {
69 0 : test_keys[i] = i;
70 0 : rb_tree_add (rt, i);
71 : }
72 :
73 0 : RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "all nodes added");
74 :
75 0 : n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
76 0 : RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
77 :
78 0 : n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
79 0 : RBTREE_TEST (n->key == 0, "min should be %u", 0);
80 :
81 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys / 2);
82 0 : RBTREE_TEST (n->key == n_keys / 2, "search result should be %u",
83 : n_keys / 2);
84 :
85 0 : aux = rb_tree_successor (rt, n);
86 0 : RBTREE_TEST (aux->key == n_keys / 2 + 1, "successor should be %u is %u",
87 : n_keys / 2 + 1, aux->key);
88 :
89 0 : aux = rb_tree_predecessor (rt, n);
90 0 : RBTREE_TEST (aux->key == n_keys / 2 - 1, "predecessor should be %u is %u",
91 : n_keys / 2 - 1, aux->key);
92 :
93 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys);
94 0 : RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
95 :
96 : /*
97 : * Delete even keys
98 : */
99 0 : for (i = 0; i < n_keys; i += 2)
100 0 : rb_tree_del (rt, i);
101 :
102 0 : n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
103 0 : RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
104 :
105 0 : n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
106 0 : RBTREE_TEST (n->key == 1, "min should be %u and is %u", 1, n->key);
107 :
108 0 : search_key = 2 * ((n_keys - 1) / 4);
109 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
110 0 : RBTREE_TEST (rb_node_is_tnil (rt, n), "search result for %u should be tnil",
111 : search_key);
112 :
113 0 : search_key += 1;
114 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
115 0 : RBTREE_TEST (n->key == search_key, "search result should be %u",
116 : search_key);
117 :
118 0 : aux = rb_tree_successor (rt, n);
119 0 : RBTREE_TEST (aux->key == search_key + 2, "successor should be %u is %u",
120 : search_key + 2, aux->key);
121 :
122 0 : aux = rb_tree_predecessor (rt, n);
123 0 : RBTREE_TEST (aux->key == search_key - 2, "predecessor should be %u is %u",
124 : search_key - 2, aux->key);
125 :
126 : /*
127 : * Re-add even keys
128 : */
129 0 : for (i = 0; i < n_keys; i += 2)
130 0 : rb_tree_add (rt, i);
131 :
132 0 : RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "number nodes %u is %u",
133 : n_keys + 1, rb_tree_n_nodes (rt));
134 :
135 0 : n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
136 0 : RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
137 :
138 0 : n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
139 0 : RBTREE_TEST (n->key == 0, "min should be %u", 0);
140 :
141 0 : search_key = 2 * ((n_keys - 1) / 4);
142 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
143 0 : RBTREE_TEST (n->key == search_key, "search result should be %u",
144 : search_key);
145 :
146 0 : search_key += 1;
147 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
148 0 : RBTREE_TEST (n->key == search_key, "search result should be %u",
149 : search_key);
150 :
151 0 : aux = rb_tree_successor (rt, n);
152 0 : RBTREE_TEST (aux->key == search_key + 1, "successor should be %u is %u",
153 : search_key + 1, aux->key);
154 :
155 0 : aux = rb_tree_predecessor (rt, n);
156 0 : RBTREE_TEST (aux->key == search_key - 1, "predecessor should be %u is %u",
157 : search_key - 1, aux->key);
158 :
159 : /*
160 : * Delete all keys
161 : */
162 0 : for (i = 0; i < n_keys; i++)
163 : {
164 0 : rb_tree_del (rt, i);
165 0 : if (rt->nodes[RBTREE_TNIL_INDEX].color != RBTREE_BLACK)
166 0 : RBTREE_TEST (0, "tnil should be black");
167 : }
168 :
169 0 : RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
170 : 1, rb_tree_n_nodes (rt));
171 :
172 0 : n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
173 0 : RBTREE_TEST (rb_node_is_tnil (rt, n), "min should be tnil");
174 :
175 0 : n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
176 0 : RBTREE_TEST (rb_node_is_tnil (rt, n), "max should be tnil");
177 :
178 0 : search_key = 2 * ((n_keys - 1) / 4);
179 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
180 0 : RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
181 :
182 : /*
183 : * Test successor/predecessor
184 : */
185 0 : u8 test_vals[] = { 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 };
186 0 : for (i = 0; i < sizeof (test_vals) / sizeof (u8); i++)
187 0 : rb_tree_add (rt, test_vals[i]);
188 :
189 0 : search_key = 13;
190 0 : n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
191 0 : RBTREE_TEST (n->key == search_key, "search result should be %u",
192 : search_key);
193 :
194 0 : aux = rb_tree_successor (rt, n);
195 0 : RBTREE_TEST (aux->key == 15, "successor should be %u is %u", 15, aux->key);
196 :
197 0 : aux = rb_tree_predecessor (rt, n);
198 0 : RBTREE_TEST (aux->key == 9, "predecessor should be %u is %u", 9, aux->key);
199 :
200 0 : n = aux;
201 0 : aux = rb_tree_predecessor (rt, n);
202 0 : RBTREE_TEST (aux->key == 7, "predecessor should be %u is %u", 7, aux->key);
203 :
204 : /*
205 : * Cleanup
206 : */
207 0 : rb_tree_free_nodes (rt);
208 0 : RBTREE_TEST (rb_tree_n_nodes (rt) == 0, "number nodes %u is %u",
209 : 0, rb_tree_n_nodes (rt));
210 :
211 0 : return 0;
212 : }
213 :
214 : static clib_error_t *
215 0 : rbtree_test (vlib_main_t * vm,
216 : unformat_input_t * input, vlib_cli_command_t * cmd_arg)
217 : {
218 0 : int res = 0;
219 :
220 0 : while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
221 : {
222 0 : if (unformat (input, "basic"))
223 : {
224 0 : res = rbtree_test_basic (vm, input);
225 : }
226 0 : else if (unformat (input, "all"))
227 : {
228 0 : if ((res = rbtree_test_basic (vm, input)))
229 0 : goto done;
230 : }
231 : else
232 0 : break;
233 : }
234 :
235 0 : done:
236 0 : if (res)
237 0 : return clib_error_return (0, "rbtree unit test failed");
238 0 : return 0;
239 : }
240 :
241 : /* *INDENT-OFF* */
242 16239 : VLIB_CLI_COMMAND (rbtree_test_command, static) =
243 : {
244 : .path = "test rbtree",
245 : .short_help = "internal rbtree unit tests",
246 : .function = rbtree_test,
247 : };
248 : /* *INDENT-ON* */
249 :
250 : /*
251 : * fd.io coding-style-patch-verification: ON
252 : *
253 : * Local Variables:
254 : * eval: (c-set-style "gnu")
255 : * End:
256 : */
|
