FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
rbtree.h
Go to the documentation of this file.
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 
25 
26 typedef enum rb_tree_color_
27 {
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);
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);
58 void rb_tree_free_nodes (rb_tree_t * rt);
64  u32 key, rb_tree_lt_fn ltfn);
67 int rb_tree_is_init (rb_tree_t * rt);
68 
69 static inline rb_node_index_t
71 {
72  return n - rt->nodes;
73 }
74 
75 static inline u8
77 {
78  return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
79 }
80 
81 static inline rb_node_t *
83 {
84  return pool_elt_at_index (rt->nodes, ri);
85 }
86 
87 static inline rb_node_t *
89 {
90  return pool_elt_at_index (rt->nodes, n->right);
91 }
92 
93 static inline rb_node_t *
95 {
96  return pool_elt_at_index (rt->nodes, n->left);
97 }
98 
99 static inline rb_node_t *
101 {
102  return pool_elt_at_index (rt->nodes, n->parent);
103 }
104 
105 #endif /* SRC_VPPINFRA_RBTREE_H_ */
106 
107 /*
108  * fd.io coding-style-patch-verification: ON
109  *
110  * Local Variables:
111  * eval: (c-set-style "gnu")
112  * End:
113  */
rb_tree_color_
Definition: rbtree.h:26
a
Definition: bitmap.h:538
rb_node_t * rb_tree_min_subtree(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:254
static rb_node_t * rb_node_left(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:94
rb_node_t * rb_tree_search_subtree(rb_tree_t *rt, rb_node_t *x, u32 key)
Definition: rbtree.c:231
Fixed length block allocator.
static rb_node_t * rb_node(rb_tree_t *rt, rb_node_index_t ri)
Definition: rbtree.h:82
struct rb_tree_ rb_tree_t
#define RBTREE_TNIL_INDEX
Definition: rbtree.h:22
static rb_node_t * rb_node_right(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:88
rb_node_t * rb_tree_successor(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:270
rb_node_t * rb_tree_search_subtree_custom(rb_tree_t *rt, rb_node_t *x, u32 key, rb_tree_lt_fn ltfn)
Definition: rbtree.c:242
enum rb_tree_color_ rb_node_color_t
unsigned char u8
Definition: types.h:56
rb_node_index_t left
left child index
Definition: rbtree.h:36
rb_node_index_t parent
parent index
Definition: rbtree.h:35
static rb_node_index_t rb_node_index(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:70
unsigned int u32
Definition: types.h:88
u32 key
node key
Definition: rbtree.h:38
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:534
uword opaque
value stored by node
Definition: rbtree.h:39
rb_node_t * rb_tree_predecessor(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:287
void rb_tree_del_custom(rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
Definition: rbtree.c:461
u32 rb_node_index_t
Definition: rbtree.h:24
int rb_tree_is_init(rb_tree_t *rt)
Definition: rbtree.c:496
static rb_node_t * rb_node_parent(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:100
rb_node_index_t rb_tree_add(rb_tree_t *rt, u32 key)
Definition: rbtree.c:170
rb_node_t * rb_tree_max_subtree(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:262
rb_node_index_t right
right child index
Definition: rbtree.h:37
rb_node_index_t rb_tree_add2(rb_tree_t *rt, u32 key, uword opaque)
Definition: rbtree.c:182
void rb_tree_del_node(rb_tree_t *rt, rb_node_t *z)
Definition: rbtree.c:445
rb_node_index_t rb_tree_add_custom(rb_tree_t *rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
Definition: rbtree.c:195
u8 color
node color
Definition: rbtree.h:34
static u8 rb_node_is_tnil(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:76
void rb_tree_free_nodes(rb_tree_t *rt)
Definition: rbtree.c:476
u64 uword
Definition: types.h:112
void rb_tree_init(rb_tree_t *rt)
Definition: rbtree.c:483
rb_node_t * nodes
pool of nodes
Definition: rbtree.h:44
int(* rb_tree_lt_fn)(u32 a, u32 b)
Definition: rbtree.h:48
struct rb_node_ rb_node_t
rb_node_index_t root
root index
Definition: rbtree.h:45
u32 rb_tree_n_nodes(rb_tree_t *rt)
Definition: rbtree.c:470
void rb_tree_del(rb_tree_t *rt, u32 key)
Definition: rbtree.c:452