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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #ifndef SRC_VPPINFRA_RBTREE_H_
17 #define SRC_VPPINFRA_RBTREE_H_
19 #include <vppinfra/types.h>
20 #include <vppinfra/pool.h>
22 #define RBTREE_TNIL_INDEX 0
24 typedef u32 rb_node_index_t;
26 typedef enum rb_tree_color_
32 typedef struct rb_node_
34 u8 color; /**< node color */
35 rb_node_index_t parent; /**< parent index */
36 rb_node_index_t left; /**< left child index */
37 rb_node_index_t right; /**< right child index */
38 u32 key; /**< node key */
39 uword opaque; /**< value stored by node */
42 typedef struct rb_tree_
44 rb_node_t *nodes; /**< pool of nodes */
45 rb_node_index_t root; /**< root index */
48 void rb_tree_init (rb_tree_t * rt);
49 rb_node_index_t rb_tree_add (rb_tree_t * rt, u32 key);
50 rb_node_index_t rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque);
51 void rb_tree_del (rb_tree_t * rt, u32 key);
52 void rb_tree_free_nodes (rb_tree_t * rt);
53 u32 rb_tree_n_nodes (rb_tree_t * rt);
54 rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x);
55 rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x);
56 rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key);
57 rb_node_t *rb_tree_successor (rb_tree_t * rt, rb_node_t * x);
58 rb_node_t *rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x);
60 static inline rb_node_index_t
61 rb_node_index (rb_tree_t * rt, rb_node_t * n)
67 rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n)
69 return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
72 static inline rb_node_t *
73 rb_node (rb_tree_t * rt, rb_node_index_t ri)
75 return pool_elt_at_index (rt->nodes, ri);
78 static inline rb_node_t *
79 rb_node_right (rb_tree_t * rt, rb_node_t * n)
81 return pool_elt_at_index (rt->nodes, n->right);
84 static inline rb_node_t *
85 rb_node_left (rb_tree_t * rt, rb_node_t * n)
87 return pool_elt_at_index (rt->nodes, n->left);
90 static inline rb_node_t *
91 rb_node_parent (rb_tree_t * rt, rb_node_t * n)
93 return pool_elt_at_index (rt->nodes, n->parent);
96 #endif /* SRC_VPPINFRA_RBTREE_H_ */
99 * fd.io coding-style-patch-verification: ON
102 * eval: (c-set-style "gnu")