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;
  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   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");
  87
  88   /*
  89    * Delete even keys
  90    */
  91   for (i = 0; i < (n_keys - 1) / 2; i += 2)
  92     rb_tree_del (rt, i);
  93
  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);
  96
  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);
  99
 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");
 103
 104   search_key += 1;
 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",
 107                search_key);
 108
 109   /*
 110    * Re-add even keys
 111    */
 112   for (i = 0; i < (n_keys - 1) / 2; i += 2)
 113     rb_tree_add (rt, i);
 114
 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));
 117
 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);
 120
 121   n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
 122   RBTREE_TEST (n->key == 0, "min should be %u", 0);
 123
 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",
 127                search_key);
 128
 129   search_key += 1;
 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",
 132                search_key);
 133
 134   /*
 135    * Delete all keys
 136    */
 137   for (i = 0; i < n_keys; i++)
 138     rb_tree_del (rt, i);
 139
 140   RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
 141                1, rb_tree_n_nodes (rt));
 142
 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");
 145
 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");
 148
 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");
 152
 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));
 156
 157   return 0;
 158 }
 159
 160 static clib_error_t *
 161 rbtree_test (vlib_main_t * vm,
 162              unformat_input_t * input, vlib_cli_command_t * cmd_arg)
 163 {
 164   int res = 0;
 165
 166   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 167     {
 168       if (unformat (input, "basic"))
 169         {
 170           res = rbtree_test_basic (vm, input);
 171         }
 172       else if (unformat (input, "all"))
 173         {
 174           if ((res = rbtree_test_basic (vm, input)))
 175             goto done;
 176         }
 177       else
 178         break;
 179     }
 180
 181 done:
 182   if (res)
 183     return clib_error_return (0, "rbtree unit test failed");
 184   return 0;
 185 }
 186
 187 /* *INDENT-OFF* */
 188 VLIB_CLI_COMMAND (rbtree_test_command, static) =
 189 {
 190   .path = "test rbtree",
 191   .short_help = "internal rbtree unit tests",
 192   .function = rbtree_test,
 193 };
 194 /* *INDENT-ON* */
 195
 196 /*
 197  * fd.io coding-style-patch-verification: ON
 198  *
 199  * Local Variables:
 200  * eval: (c-set-style "gnu")
 201  * End:
 202  */