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 typedef int (*rb_tree_lt_fn) (u32 a, u32 b);
50 void rb_tree_init (rb_tree_t * rt);
51 rb_node_index_t rb_tree_add (rb_tree_t * rt, u32 key);
52 rb_node_index_t rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque);
53 rb_node_index_t rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque,
55 void rb_tree_del (rb_tree_t * rt, u32 key);
56 void rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn);
57 void rb_tree_free_nodes (rb_tree_t * rt);
58 u32 rb_tree_n_nodes (rb_tree_t * rt);
59 rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x);
60 rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x);
61 rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key);
62 rb_node_t *rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x,
63 u32 key, rb_tree_lt_fn ltfn);
64 rb_node_t *rb_tree_successor (rb_tree_t * rt, rb_node_t * x);
65 rb_node_t *rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x);
67 static inline rb_node_index_t
68 rb_node_index (rb_tree_t * rt, rb_node_t * n)
74 rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n)
76 return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
79 static inline rb_node_t *
80 rb_node (rb_tree_t * rt, rb_node_index_t ri)
82 return pool_elt_at_index (rt->nodes, ri);
85 static inline rb_node_t *
86 rb_node_right (rb_tree_t * rt, rb_node_t * n)
88 return pool_elt_at_index (rt->nodes, n->right);
91 static inline rb_node_t *
92 rb_node_left (rb_tree_t * rt, rb_node_t * n)
94 return pool_elt_at_index (rt->nodes, n->left);
97 static inline rb_node_t *
98 rb_node_parent (rb_tree_t * rt, rb_node_t * n)
100 return pool_elt_at_index (rt->nodes, n->parent);
103 #endif /* SRC_VPPINFRA_RBTREE_H_ */
106 * fd.io coding-style-patch-verification: ON
109 * eval: (c-set-style "gnu")