src/plugins/unittest/rbtree_test.c

   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 rbtree_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
 214 static clib_error_t *
 215 rbtree_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
 235 done:
 236   if (res)
 237     return clib_error_return (0, "rbtree unit test failed");
 238   return 0;
 239 }
 240
 241 /* *INDENT-OFF* */
 242 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  */