From 672d5fc6d36ebc3a3815c4658a8ef3bf256ef044 Mon Sep 17 00:00:00 2001 From: Florin Coras Date: Mon, 15 Apr 2019 17:28:51 -0700 Subject: vppinfra: add basic rbtree Algorithm from CLRS, Introduction to Algorithms 3rd Edition, Ch. 13 Change-Id: I5bc2c507593770939cd5584f21dacf36ebd2b4c1 Signed-off-by: Florin Coras --- src/vppinfra/rbtree.h | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 84 insertions(+) create mode 100644 src/vppinfra/rbtree.h (limited to 'src/vppinfra/rbtree.h') 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 +#include + +#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: + */ -- cgit 1.2.3-korg