FD.io VPP  v20.01-48-g3e0dafb74
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);
57 void rb_tree_free_nodes (rb_tree_t * rt);
63  u32 key, rb_tree_lt_fn ltfn);
66 
67 static inline rb_node_index_t
69 {
70  return n - rt->nodes;
71 }
72 
73 static inline u8
75 {
76  return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
77 }
78 
79 static inline rb_node_t *
81 {
82  return pool_elt_at_index (rt->nodes, ri);
83 }
84 
85 static inline rb_node_t *
87 {
88  return pool_elt_at_index (rt->nodes, n->right);
89 }
90 
91 static inline rb_node_t *
93 {
94  return pool_elt_at_index (rt->nodes, n->left);
95 }
96 
97 static inline rb_node_t *
99 {
100  return pool_elt_at_index (rt->nodes, n->parent);
101 }
102 
103 #endif /* SRC_VPPINFRA_RBTREE_H_ */
104 
105 /*
106  * fd.io coding-style-patch-verification: ON
107  *
108  * Local Variables:
109  * eval: (c-set-style "gnu")
110  * End:
111  */
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:253
static rb_node_t * rb_node_left(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:92
rb_node_t * rb_tree_search_subtree(rb_tree_t *rt, rb_node_t *x, u32 key)
Definition: rbtree.c:230
Fixed length block allocator.
static rb_node_t * rb_node(rb_tree_t *rt, rb_node_index_t ri)
Definition: rbtree.h:80
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:86
rb_node_t * rb_tree_successor(rb_tree_t *rt, rb_node_t *x)
Definition: rbtree.c:269
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:241
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:68
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:519
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:286
void rb_tree_del_custom(rb_tree_t *rt, u32 key, rb_tree_lt_fn ltfn)
Definition: rbtree.c:456
u32 rb_node_index_t
Definition: rbtree.h:24
static rb_node_t * rb_node_parent(rb_tree_t *rt, rb_node_t *n)
Definition: rbtree.h:98
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:261
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
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:74
void rb_tree_free_nodes(rb_tree_t *rt)
Definition: rbtree.c:474
u64 uword
Definition: types.h:112
void rb_tree_init(rb_tree_t *rt)
Definition: rbtree.c:481
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:468
void rb_tree_del(rb_tree_t *rt, u32 key)
Definition: rbtree.c:444