dde2fbfb8365c3141589b7da47bd5f4902cb9640
[vpp.git] / src / vppinfra / rbtree.h
1 /*
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:
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
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.
14  */
15
16 #ifndef SRC_VPPINFRA_RBTREE_H_
17 #define SRC_VPPINFRA_RBTREE_H_
18
19 #include <vppinfra/types.h>
20 #include <vppinfra/pool.h>
21
22 #define RBTREE_TNIL_INDEX 0
23
24 typedef u32 rb_node_index_t;
25
26 typedef enum rb_tree_color_
27 {
28   RBTREE_RED,
29   RBTREE_BLACK
30 } rb_node_color_t;
31
32 typedef struct rb_node_
33 {
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 */
40 } rb_node_t;
41
42 typedef struct rb_tree_
43 {
44   rb_node_t *nodes;             /**< pool of nodes */
45   rb_node_index_t root;         /**< root index */
46 } rb_tree_t;
47
48 typedef int (*rb_tree_lt_fn) (u32 a, u32 b);
49
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,
54                                     rb_tree_lt_fn ltfn);
55 void rb_tree_del (rb_tree_t * rt, u32 key);
56 void rb_tree_del_node (rb_tree_t * rt, rb_node_t * z);
57 void rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn);
58 void rb_tree_free_nodes (rb_tree_t * rt);
59 u32 rb_tree_n_nodes (rb_tree_t * rt);
60 rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x);
61 rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x);
62 rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key);
63 rb_node_t *rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x,
64                                           u32 key, rb_tree_lt_fn ltfn);
65 rb_node_t *rb_tree_successor (rb_tree_t * rt, rb_node_t * x);
66 rb_node_t *rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x);
67
68 static inline rb_node_index_t
69 rb_node_index (rb_tree_t * rt, rb_node_t * n)
70 {
71   return n - rt->nodes;
72 }
73
74 static inline u8
75 rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n)
76 {
77   return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
78 }
79
80 static inline rb_node_t *
81 rb_node (rb_tree_t * rt, rb_node_index_t ri)
82 {
83   return pool_elt_at_index (rt->nodes, ri);
84 }
85
86 static inline rb_node_t *
87 rb_node_right (rb_tree_t * rt, rb_node_t * n)
88 {
89   return pool_elt_at_index (rt->nodes, n->right);
90 }
91
92 static inline rb_node_t *
93 rb_node_left (rb_tree_t * rt, rb_node_t * n)
94 {
95   return pool_elt_at_index (rt->nodes, n->left);
96 }
97
98 static inline rb_node_t *
99 rb_node_parent (rb_tree_t * rt, rb_node_t * n)
100 {
101   return pool_elt_at_index (rt->nodes, n->parent);
102 }
103
104 #endif /* SRC_VPPINFRA_RBTREE_H_ */
105
106 /*
107  * fd.io coding-style-patch-verification: ON
108  *
109  * Local Variables:
110  * eval: (c-set-style "gnu")
111  * End:
112  */