aboutsummaryrefslogtreecommitdiffstats
path: root/src/plugins
diff options
context:
space:
mode:
authorFlorin Coras <fcoras@cisco.com>2019-04-15 17:28:51 -0700
committerDave Barach <openvpp@barachs.net>2019-04-16 14:20:34 +0000
commit672d5fc6d36ebc3a3815c4658a8ef3bf256ef044 (patch)
treec2c02d3bb2c97e07c1fcfb665539483b8c53a955 /src/plugins
parent2a24987bbaeb30801900a15a7216555b0d4b6e05 (diff)
vppinfra: add basic rbtree
Algorithm from CLRS, Introduction to Algorithms 3rd Edition, Ch. 13 Change-Id: I5bc2c507593770939cd5584f21dacf36ebd2b4c1 Signed-off-by: Florin Coras <fcoras@cisco.com>
Diffstat (limited to 'src/plugins')
-rw-r--r--src/plugins/unittest/CMakeLists.txt1
-rw-r--r--src/plugins/unittest/rbtree_test.c202
2 files changed, 203 insertions, 0 deletions
diff --git a/src/plugins/unittest/CMakeLists.txt b/src/plugins/unittest/CMakeLists.txt
index 60a7cc166ab..64ad9a2c486 100644
--- a/src/plugins/unittest/CMakeLists.txt
+++ b/src/plugins/unittest/CMakeLists.txt
@@ -27,6 +27,7 @@ add_vpp_plugin(unittest
interface_test.c
mfib_test.c
punt_test.c
+ rbtree_test.c
session_test.c
string_test.c
tcp_test.c
diff --git a/src/plugins/unittest/rbtree_test.c b/src/plugins/unittest/rbtree_test.c
new file mode 100644
index 00000000000..a20ac1b111b
--- /dev/null
+++ b/src/plugins/unittest/rbtree_test.c
@@ -0,0 +1,202 @@
+/*
+ * Copyright (c) 2019 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <vppinfra/rbtree.h>
+#include <vlib/vlib.h>
+
+#define RBTREE_TEST_I(_cond, _comment, _args...) \
+({ \
+ int _evald = (_cond); \
+ if (!(_evald)) { \
+ fformat(stderr, "FAIL:%d: " _comment "\n", \
+ __LINE__, ##_args); \
+ } else { \
+ fformat(stderr, "PASS:%d: " _comment "\n", \
+ __LINE__, ##_args); \
+ } \
+ _evald; \
+})
+
+#define RBTREE_TEST(_cond, _comment, _args...) \
+{ \
+ if (!RBTREE_TEST_I(_cond, _comment, ##_args)) { \
+ return 1; \
+ } \
+}
+
+static int
+rbtree_test_basic (vlib_main_t * vm, unformat_input_t * input)
+{
+ int __clib_unused verbose, n_keys = 1e3, i;
+ u32 *test_keys = 0, search_key;
+ rb_tree_t _rt, *rt = &_rt;
+ rb_node_t *n;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+ {
+ if (unformat (input, "verbose"))
+ verbose = 1;
+ else if (unformat (input, "nkeys %u", &n_keys))
+ ;
+ else
+ {
+ vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
+ input);
+ return -1;
+ }
+ }
+
+ rb_tree_init (rt);
+ RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "tnil created");
+
+ /*
+ * Add keys
+ */
+ vec_validate (test_keys, n_keys - 1);
+ for (i = n_keys - 1; i >= 0; i--)
+ {
+ test_keys[i] = i;
+ rb_tree_add (rt, i);
+ }
+
+ RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "all nodes added");
+
+ n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
+
+ n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (n->key == 0, "min should be %u", 0);
+
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys / 2);
+ RBTREE_TEST (n->key == n_keys / 2, "search result should be %u",
+ n_keys / 2);
+
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), n_keys);
+ RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
+
+ /*
+ * Delete even keys
+ */
+ for (i = 0; i < (n_keys - 1) / 2; i += 2)
+ rb_tree_del (rt, i);
+
+ n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
+
+ n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (n->key == 1, "min should be %u and is %u", 1, n->key);
+
+ search_key = 2 * ((n_keys - 1) / 4);
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
+ RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
+
+ search_key += 1;
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
+ RBTREE_TEST (n->key == search_key, "search result should be %u",
+ search_key);
+
+ /*
+ * Re-add even keys
+ */
+ for (i = 0; i < (n_keys - 1) / 2; i += 2)
+ rb_tree_add (rt, i);
+
+ RBTREE_TEST (rb_tree_n_nodes (rt) == n_keys + 1, "number nodes %u is %u",
+ n_keys + 1, rb_tree_n_nodes (rt));
+
+ n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (n->key == n_keys - 1, "max should be %u", n_keys - 1);
+
+ n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (n->key == 0, "min should be %u", 0);
+
+ search_key = 2 * ((n_keys - 1) / 4);
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
+ RBTREE_TEST (n->key == search_key, "search result should be %u",
+ search_key);
+
+ search_key += 1;
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
+ RBTREE_TEST (n->key == search_key, "search result should be %u",
+ search_key);
+
+ /*
+ * Delete all keys
+ */
+ for (i = 0; i < n_keys; i++)
+ rb_tree_del (rt, i);
+
+ RBTREE_TEST (rb_tree_n_nodes (rt) == 1, "number nodes %u is %u",
+ 1, rb_tree_n_nodes (rt));
+
+ n = rb_tree_min_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (rb_node_is_tnil (rt, n), "min should be tnil");
+
+ n = rb_tree_max_subtree (rt, rb_node (rt, rt->root));
+ RBTREE_TEST (rb_node_is_tnil (rt, n), "max should be tnil");
+
+ search_key = 2 * ((n_keys - 1) / 4);
+ n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), search_key);
+ RBTREE_TEST (rb_node_is_tnil (rt, n), "search result should be tnil");
+
+ rb_tree_free_nodes (rt);
+ RBTREE_TEST (rb_tree_n_nodes (rt) == 0, "number nodes %u is %u",
+ 0, rb_tree_n_nodes (rt));
+
+ return 0;
+}
+
+static clib_error_t *
+rbtree_test (vlib_main_t * vm,
+ unformat_input_t * input, vlib_cli_command_t * cmd_arg)
+{
+ int res = 0;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+ {
+ if (unformat (input, "basic"))
+ {
+ res = rbtree_test_basic (vm, input);
+ }
+ else if (unformat (input, "all"))
+ {
+ if ((res = rbtree_test_basic (vm, input)))
+ goto done;
+ }
+ else
+ break;
+ }
+
+done:
+ if (res)
+ return clib_error_return (0, "rbtree unit test failed");
+ return 0;
+}
+
+/* *INDENT-OFF* */
+VLIB_CLI_COMMAND (rbtree_test_command, static) =
+{
+ .path = "test rbtree",
+ .short_help = "internal rbtree unit tests",
+ .function = rbtree_test,
+};
+/* *INDENT-ON* */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */