FD.io VPP  v21.06-3-gbb25fbf28
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);
64  u32 key, rb_tree_lt_fn ltfn);
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_search_subtree_custom
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
RBTREE_BLACK
@ RBTREE_BLACK
Definition: rbtree.h:29
rb_node
static rb_node_t * rb_node(rb_tree_t *rt, rb_node_index_t ri)
Definition: rbtree.h:82
RBTREE_TNIL_INDEX
#define RBTREE_TNIL_INDEX
Definition: rbtree.h:22
types.h
rb_tree_::root
rb_node_index_t root
root index
Definition: rbtree.h:45
rb_node_left
static rb_node_t * rb_node_left(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:94
pool_elt_at_index
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:553
rb_node_t
struct rb_node_ rb_node_t
rb_tree_lt_fn
int(* rb_tree_lt_fn)(u32 a, u32 b)
Definition: rbtree.h:48
rb_node_::key
u32 key
node key
Definition: rbtree.h:38
rb_tree_del
void rb_tree_del(rb_tree_t *rt, u32 key)
Definition: rbtree.c:452
rb_node_color_t
enum rb_tree_color_ rb_node_color_t
rb_tree_min_subtree
rb_node_t * rb_tree_min_subtree(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:254
key
typedef key
Definition: ipsec_types.api:88
rb_tree_del_node
void rb_tree_del_node(rb_tree_t *rt, rb_node_t *z)
Definition: rbtree.c:445
rb_node_::left
rb_node_index_t left
left child index
Definition: rbtree.h:36
rb_tree_color_
rb_tree_color_
Definition: rbtree.h:26
RBTREE_RED
@ RBTREE_RED
Definition: rbtree.h:28
rb_tree_del_custom
void rb_tree_del_custom(rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
Definition: rbtree.c:461
rb_node_::opaque
uword opaque
value stored by node
Definition: rbtree.h:39
rb_node_index
static rb_node_index_t rb_node_index(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:70
rb_tree_add_custom
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
rb_tree_successor
rb_node_t * rb_tree_successor(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:270
rb_node_parent
static rb_node_t * rb_node_parent(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:100
rb_node_::parent
rb_node_index_t parent
parent index
Definition: rbtree.h:35
uword
u64 uword
Definition: types.h:112
pool.h
Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedl...
rb_tree_add2
rb_node_index_t rb_tree_add2(rb_tree_t *rt, u32 key, uword opaque)
Definition: rbtree.c:182
rb_tree_init
void rb_tree_init(rb_tree_t *rt)
Definition: rbtree.c:483
rb_node_index_t
u32 rb_node_index_t
Definition: rbtree.h:24
rb_tree_max_subtree
rb_node_t * rb_tree_max_subtree(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:262
u32
unsigned int u32
Definition: types.h:88
rb_tree_
Definition: rbtree.h:42
rb_tree_search_subtree
rb_node_t * rb_tree_search_subtree(rb_tree_t *rt, rb_node_t *x, u32 key)
Definition: rbtree.c:231
rb_node_::right
rb_node_index_t right
right child index
Definition: rbtree.h:37
rb_tree_predecessor
rb_node_t * rb_tree_predecessor(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:287
rb_tree_free_nodes
void rb_tree_free_nodes(rb_tree_t *rt)
Definition: rbtree.c:476
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
rb_node_
Definition: rbtree.h:32
u8
unsigned char u8
Definition: types.h:56
a
a
Definition: bitmap.h:544
rt
vnet_interface_output_runtime_t * rt
Definition: interface_output.c:399
rb_tree_add
rb_node_index_t rb_tree_add(rb_tree_t *rt, u32 key)
Definition: rbtree.c:170
rb_tree_::nodes
rb_node_t * nodes
pool of nodes
Definition: rbtree.h:44
rb_node_right
static rb_node_t * rb_node_right(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:88
rb_tree_is_init
int rb_tree_is_init(rb_tree_t *rt)
Definition: rbtree.c:496
rb_tree_n_nodes
u32 rb_tree_n_nodes(rb_tree_t *rt)
Definition: rbtree.c:470
rb_node_::color
u8 color
node color
Definition: rbtree.h:34
rb_node_is_tnil
static u8 rb_node_is_tnil(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:76
rb_tree_t
struct rb_tree_ rb_tree_t