diff options
| -rw-r--r-- | src/plugins/unittest/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/plugins/unittest/rbtree_test.c | 202 | ||||
| -rw-r--r-- | src/vppinfra/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | src/vppinfra/rbtree.c | 411 | ||||
| -rw-r--r-- | src/vppinfra/rbtree.h | 84 |
5 files changed, 700 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: + */ diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt index df5ca5d407a..702f6fdcae5 100644 --- a/src/vppinfra/CMakeLists.txt +++ b/src/vppinfra/CMakeLists.txt @@ -63,6 +63,7 @@ set(VPPINFRA_SRCS random.c random_buffer.c random_isaac.c + rbtree.c serialize.c slist.c socket.c @@ -146,6 +147,7 @@ set(VPPINFRA_HEADERS random_buffer.h random.h random_isaac.h + rbtree.h serialize.h sha2.h slist.h diff --git a/src/vppinfra/rbtree.c b/src/vppinfra/rbtree.c new file mode 100644 index 00000000000..d99367a2c6f --- /dev/null +++ b/src/vppinfra/rbtree.c @@ -0,0 +1,411 @@ +/* + * 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. + */ +/* + * Algorithm from: + * Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). + * Introduction to algorithms. MIT press, 3rd Edition, Ch. 13 + */ + +#include <vppinfra/rbtree.h> + +static inline rb_node_t * +rb_node_right (rb_tree_t * rt, rb_node_t * n) +{ + return pool_elt_at_index (rt->nodes, n->right); +} + +static inline rb_node_t * +rb_node_left (rb_tree_t * rt, rb_node_t * n) +{ + return pool_elt_at_index (rt->nodes, n->left); +} + +static inline rb_node_t * +rb_node_parent (rb_tree_t * rt, rb_node_t * n) +{ + return pool_elt_at_index (rt->nodes, n->parent); +} + +static inline void +rb_tree_rotate_left (rb_tree_t * rt, rb_node_t * x) +{ + rb_node_t *y, *tmp, *xp; + rb_node_index_t xi, yi; + + xi = rb_node_index (rt, x); + yi = x->right; + y = rb_node_right (rt, x); + x->right = y->left; + if (y->left != RBTREE_TNIL_INDEX) + { + tmp = rb_node_left (rt, y); + tmp->parent = xi; + } + xp = rb_node_parent (rt, x); + y->parent = x->parent; + if (x->parent == RBTREE_TNIL_INDEX) + rt->root = rb_node_index (rt, y); + else if (xp->left == xi) + xp->left = yi; + else + xp->right = yi; + y->left = xi; + x->parent = yi; +} + +static inline void +rb_tree_rotate_right (rb_tree_t * rt, rb_node_t * y) +{ + rb_node_index_t yi, xi; + rb_node_t *x, *yp; + + yi = rb_node_index (rt, y); + xi = y->left; + x = rb_node_left (rt, y); + y->left = x->right; + if (x->right != RBTREE_TNIL_INDEX) + { + rb_node_t *tmp = rb_node_right (rt, x); + tmp->parent = yi; + } + yp = rb_node_parent (rt, y); + x->parent = y->parent; + if (y->parent == RBTREE_TNIL_INDEX) + rt->root = rb_node_index (rt, x); + else if (yp->right == yi) + yp->right = xi; + else + yp->left = xi; + x->right = yi; + y->parent = xi; +} + +static void +rb_tree_insert (rb_tree_t * rt, rb_node_t * z) +{ + rb_node_index_t yi = 0, xi = rt->root, zi; + rb_node_t *y, *zpp, *x, *zp; + + y = rb_node (rt, RBTREE_TNIL_INDEX); + while (xi != RBTREE_TNIL_INDEX) + { + x = rb_node (rt, xi); + y = x; + if (z->key < x->key) + xi = x->left; + else + xi = x->right; + } + yi = rb_node_index (rt, y); + z->parent = yi; + if (yi == RBTREE_TNIL_INDEX) + rt->root = rb_node_index (rt, z); + else if (z->key < y->key) + y->left = rb_node_index (rt, z); + else + y->right = rb_node_index (rt, z); + + /* Tree fixup stage */ + while (y->color == RBTREE_RED) + { + zi = rb_node_index (rt, z); + zp = rb_node_parent (rt, z); + zpp = rb_node_parent (rt, zp); + if (z->parent == zpp->left) + { + y = rb_node_right (rt, zpp); + if (y->color == RBTREE_RED) + { + zp->color = RBTREE_BLACK; + y->color = RBTREE_BLACK; + zpp->color = RBTREE_RED; + z = zpp; + } + else + { + if (zi == zp->right) + { + z = zp; + rb_tree_rotate_left (rt, z); + zp = rb_node (rt, z->parent); + zpp = rb_node (rt, zp->parent); + } + zp->color = RBTREE_BLACK; + zpp->color = RBTREE_RED; + rb_tree_rotate_right (rt, zpp); + } + } + else + { + y = rb_node (rt, zpp->left); + if (y->color == RBTREE_RED) + { + zp->color = RBTREE_BLACK; + y->color = RBTREE_BLACK; + zpp->color = RBTREE_RED; + z = zpp; + } + else + { + if (zi == zp->left) + { + z = zp; + rb_tree_rotate_right (rt, z); + zp = rb_node (rt, z->parent); + zpp = rb_node (rt, zp->parent); + } + zp->color = RBTREE_BLACK; + zpp->color = RBTREE_RED; + rb_tree_rotate_left (rt, zpp); + } + } + } + rb_node (rt, rt->root)->color = RBTREE_BLACK; +} + +rb_node_index_t +rb_tree_add (rb_tree_t * rt, u32 key) +{ + rb_node_t *n; + + pool_get_zero (rt->nodes, n); + n->key = key; + n->color = RBTREE_RED; + rb_tree_insert (rt, n); + return rb_node_index (rt, n); +} + +rb_node_index_t +rb_tree_add2 (rb_tree_t * rt, u32 key, u32 opaque) +{ + rb_node_t *n; + + pool_get_zero (rt->nodes, n); + n->key = key; + n->color = RBTREE_RED; + n->opaque = opaque; + rb_tree_insert (rt, n); + return rb_node_index (rt, n); +} + +rb_node_t * +rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key) +{ + while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key) + if (key < x->key) + x = rb_node_left (rt, x); + else + x = rb_node_right (rt, x); + return x; +} + +rb_node_t * +rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x) +{ + while (x->left != RBTREE_TNIL_INDEX) + x = rb_node_left (rt, x); + return x; +} + +rb_node_t * +rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x) +{ + while (x->right != RBTREE_TNIL_INDEX) + x = rb_node_right (rt, x); + return x; +} + +static inline void +rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v) +{ + rb_node_t *up; + + up = rb_node_parent (rt, u); + if (u->parent == RBTREE_TNIL_INDEX) + rt->root = rb_node_index (rt, v); + else if (rb_node_index (rt, u) == up->left) + up->left = rb_node_index (rt, v); + else + up->right = rb_node_index (rt, v); + v->parent = u->parent; +} + +void +rb_tree_del_node (rb_tree_t * rt, rb_node_t * z) +{ + rb_node_color_t y_original_color; + rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr; + rb_node_index_t xi, yi; + + y = z; + y_original_color = y->color; + + if (z->left == RBTREE_TNIL_INDEX) + { + x = rb_node_right (rt, z); + rb_tree_transplant (rt, z, x); + } + else if (z->right == RBTREE_TNIL_INDEX) + { + x = rb_node_left (rt, z); + rb_tree_transplant (rt, z, x); + } + else + { + y = rb_tree_min_subtree (rt, rb_node_right (rt, z)); + y_original_color = y->color; + x = rb_node_right (rt, y); + yi = rb_node_index (rt, y); + if (y->parent == rb_node_index (rt, z)) + x->parent = yi; + else + { + rb_tree_transplant (rt, y, rb_node_right (rt, y)); + y->right = z->right; + yr = rb_node_right (rt, y); + yr->parent = yi; + } + rb_tree_transplant (rt, z, y); + y->left = z->left; + yl = rb_node_left (rt, y); + yl->parent = yi; + y->color = z->color; + } + + if (y_original_color == RBTREE_RED) + return; + + /* Tree fixup needed */ + + xi = rb_node_index (rt, x); + while (xi != rt->root && x->color == RBTREE_BLACK) + { + xp = rb_node_parent (rt, x); + if (xi == xp->left) + { + w = rb_node_right (rt, xp); + if (w->color == RBTREE_RED) + { + w->color = RBTREE_BLACK; + xp->color = RBTREE_RED; + rb_tree_rotate_left (rt, xp); + w = rb_node_right (rt, xp); + } + wl = rb_node_left (rt, w); + wr = rb_node_right (rt, w); + if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK) + { + w->color = RBTREE_RED; + x = xp; + } + else + { + if (wr->color == RBTREE_BLACK) + { + wl->color = RBTREE_BLACK; + w->color = RBTREE_RED; + rb_tree_rotate_right (rt, w); + w = rb_node_right (rt, xp); + } + w->color = xp->color; + xp->color = RBTREE_BLACK; + wr->color = RBTREE_BLACK; + rb_tree_rotate_left (rt, xp); + x = rb_node (rt, rt->root); + } + } + else + { + w = rb_node_left (rt, xp); + if (w->color == RBTREE_RED) + { + w->color = RBTREE_BLACK; + xp->color = RBTREE_RED; + rb_tree_rotate_right (rt, xp); + w = rb_node_left (rt, xp); + } + wl = rb_node_left (rt, w); + wr = rb_node_right (rt, w); + if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK) + { + w->color = RBTREE_RED; + x = xp; + } + else + { + if (wl->color == RBTREE_BLACK) + { + wr->color = RBTREE_BLACK; + w->color = RBTREE_RED; + rb_tree_rotate_left (rt, w); + w = rb_node_left (rt, xp); + } + w->color = xp->color; + xp->color = RBTREE_BLACK; + wl->color = RBTREE_BLACK; + rb_tree_rotate_right (rt, xp); + x = rb_node (rt, rt->root); + } + } + xi = rb_node_index (rt, x); + } + x->color = RBTREE_BLACK; +} + +void +rb_tree_del (rb_tree_t * rt, u32 key) +{ + rb_node_t *n; + n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key); + if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX) + { + rb_tree_del_node (rt, n); + pool_put (rt->nodes, n); + } +} + +u32 +rb_tree_n_nodes (rb_tree_t * rt) +{ + return pool_elts (rt->nodes); +} + +void +rb_tree_free_nodes (rb_tree_t * rt) +{ + rb_node_t *n; + pool_flush (n, rt->nodes,;); +} + +void +rb_tree_init (rb_tree_t * rt) +{ + rb_node_t *tnil; + + rt->nodes = 0; + rt->root = RBTREE_TNIL_INDEX; + + /* By convention first node, index 0, is the T.nil sentinel */ + pool_get_zero (rt->nodes, tnil); + tnil->color = RBTREE_BLACK; +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/rbtree.h b/src/vppinfra/rbtree.h new file mode 100644 index 00000000000..ace07ac5622 --- /dev/null +++ b/src/vppinfra/rbtree.h @@ -0,0 +1,84 @@ +/* + * 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. + */ + +#ifndef SRC_VPPINFRA_RBTREE_H_ +#define SRC_VPPINFRA_RBTREE_H_ + +#include <vppinfra/types.h> +#include <vppinfra/pool.h> + +#define RBTREE_TNIL_INDEX 0 + +typedef u32 rb_node_index_t; + +typedef enum rb_tree_color_ +{ + RBTREE_RED, + RBTREE_BLACK +} rb_node_color_t; + +typedef struct rb_node_ +{ + u8 color; /**< node color */ + rb_node_index_t parent; /**< parent index */ + rb_node_index_t left; /**< left child index */ + rb_node_index_t right; /**< right child index */ + u32 key; /**< node key */ + u32 opaque; /**< value stored by node */ +} rb_node_t; + +typedef struct rb_tree_ +{ + rb_node_t *nodes; /**< pool of nodes */ + rb_node_index_t root; /**< root index */ +} rb_tree_t; + +void rb_tree_init (rb_tree_t * rt); +rb_node_index_t rb_tree_add (rb_tree_t * rt, u32 key); +rb_node_index_t rb_tree_add2 (rb_tree_t * rt, u32 key, u32 opaque); +void rb_tree_del (rb_tree_t * rt, u32 key); +void rb_tree_free_nodes (rb_tree_t * rt); +u32 rb_tree_n_nodes (rb_tree_t * rt); +rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x); +rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x); +rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key); + +static inline rb_node_index_t +rb_node_index (rb_tree_t * rt, rb_node_t * n) +{ + return n - rt->nodes; +} + +static inline u8 +rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n) +{ + return rb_node_index (rt, n) == RBTREE_TNIL_INDEX; +} + +static inline rb_node_t * +rb_node (rb_tree_t * rt, rb_node_index_t ri) +{ + return pool_elt_at_index (rt->nodes, ri); +} + +#endif /* SRC_VPPINFRA_RBTREE_H_ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |