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
38static int
39rbtree_test_basic (vlib_main_t * vm, unformat_input_t * input)
40{
41  int __clib_unused verbose, n_keys = 1e3, i;
42  u32 *test_keys = 0, search_key;
43  rb_tree_t _rt, *rt = &_rt;
44  rb_node_t *n, *aux;
45
46  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
47    {
48      if (unformat (input, "verbose"))
49	verbose = 1;
50      else if (unformat (input, "nkeys %u", &n_keys))
51	;
52      else
53	{
54	  vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
55			   input);
56	  return -1;
57	}
58    }
59
60  rb_tree_init (rt);
61  RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "tnil created");
62
63  /*
64   * Add keys
65   */
66  vec_validate (test_keys, n_keys - 1);
67  for (i = n_keys - 1; i >= 0; i--)
68    {
69      test_keys[i] = i;
70      rb_tree_add (rt, i);
71    }
72
73  RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "all nodes added");
74
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);
77
78  n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
79  RBTREE_TEST (n->key == 0, "min should be %u", 0);
80
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",
83	       n_keys / 2);
84
85  aux = rb_tree_successor (rt, n);
86  RBTREE_TEST (aux->key == n_keys / 2 + 1, "successor should be %u is %u",
87	       n_keys / 2 + 1, aux->key);
88
89  aux = rb_tree_predecessor (rt, n);
90  RBTREE_TEST (aux->key == n_keys / 2 - 1, "predecessor should be %u is %u",
91	       n_keys / 2 - 1, aux->key);
92
93  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys);
94  RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
95
96  /*
97   * Delete even keys
98   */
99  for (i = 0; i < n_keys; i += 2)
100    rb_tree_del (rt, i);
101
102  n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
103  RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
104
105  n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
106  RBTREE_TEST (n->key == 1, "min should be %u and is %u", 1, n->key);
107
108  search_key = 2 * ((n_keys - 1) / 4);
109  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
110  RBTREE_TEST (rb_node_is_tnil (rt, n), "search result for %u should be tnil",
111	       search_key);
112
113  search_key += 1;
114  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
115  RBTREE_TEST (n->key == search_key, "search result should be %u",
116	       search_key);
117
118  aux = rb_tree_successor (rt, n);
119  RBTREE_TEST (aux->key == search_key + 2, "successor should be %u is %u",
120	       search_key + 2, aux->key);
121
122  aux = rb_tree_predecessor (rt, n);
123  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  for (i = 0; i < n_keys; i += 2)
130    rb_tree_add (rt, i);
131
132  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  n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
136  RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
137
138  n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
139  RBTREE_TEST (n->key == 0, "min should be %u", 0);
140
141  search_key = 2 * ((n_keys - 1) / 4);
142  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
143  RBTREE_TEST (n->key == search_key, "search result should be %u",
144	       search_key);
145
146  search_key += 1;
147  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
148  RBTREE_TEST (n->key == search_key, "search result should be %u",
149	       search_key);
150
151  aux = rb_tree_successor (rt, n);
152  RBTREE_TEST (aux->key == search_key + 1, "successor should be %u is %u",
153	       search_key + 1, aux->key);
154
155  aux = rb_tree_predecessor (rt, n);
156  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  for (i = 0; i < n_keys; i++)
163    {
164      rb_tree_del (rt, i);
165      if (rt->nodes[RBTREE_TNIL_INDEX].color != RBTREE_BLACK)
166	RBTREE_TEST (0, "tnil should be black");
167    }
168
169  RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
170	       1, rb_tree_n_nodes (rt));
171
172  n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
173  RBTREE_TEST (rb_node_is_tnil (rt, n), "min should be tnil");
174
175  n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
176  RBTREE_TEST (rb_node_is_tnil (rt, n), "max should be tnil");
177
178  search_key = 2 * ((n_keys - 1) / 4);
179  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
180  RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
181
182  /*
183   * Test successor/predecessor
184   */
185  u8 test_vals[] = { 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 };
186  for (i = 0; i < sizeof (test_vals) / sizeof (u8); i++)
187    rb_tree_add (rt, test_vals[i]);
188
189  search_key = 13;
190  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
191  RBTREE_TEST (n->key == search_key, "search result should be %u",
192	       search_key);
193
194  aux = rb_tree_successor (rt, n);
195  RBTREE_TEST (aux->key == 15, "successor should be %u is %u", 15, aux->key);
196
197  aux = rb_tree_predecessor (rt, n);
198  RBTREE_TEST (aux->key == 9, "predecessor should be %u is %u", 9, aux->key);
199
200  n = aux;
201  aux = rb_tree_predecessor (rt, n);
202  RBTREE_TEST (aux->key == 7, "predecessor should be %u is %u", 7, aux->key);
203
204  /*
205   * Cleanup
206   */
207  rb_tree_free_nodes (rt);
208  RBTREE_TEST (rb_tree_n_nodes (rt) == 0, "number nodes %u is %u",
209	       0, rb_tree_n_nodes (rt));
210
211  return 0;
212}
213
214static clib_error_t *
215rbtree_test (vlib_main_t * vm,
216	     unformat_input_t * input, vlib_cli_command_t * cmd_arg)
217{
218  int res = 0;
219
220  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
221    {
222      if (unformat (input, "basic"))
223	{
224	  res = rbtree_test_basic (vm, input);
225	}
226      else if (unformat (input, "all"))
227	{
228	  if ((res = rbtree_test_basic (vm, input)))
229	    goto done;
230	}
231      else
232	break;
233    }
234
235done:
236  if (res)
237    return clib_error_return (0, "rbtree unit test failed");
238  return 0;
239}
240
241/* *INDENT-OFF* */
242VLIB_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 */
257