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
24typedef u32 rb_node_index_t;
25
26typedef enum rb_tree_color_
27{
28  RBTREE_RED,
29  RBTREE_BLACK
30} rb_node_color_t;
31
32typedef 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
42typedef 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
48typedef int (*rb_tree_lt_fn) (u32 a, u32 b);
49
50void rb_tree_init (rb_tree_t * rt);
51rb_node_index_t rb_tree_add (rb_tree_t * rt, u32 key);
52rb_node_index_t rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque);
53rb_node_index_t rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque,
54				    rb_tree_lt_fn ltfn);
55void rb_tree_del (rb_tree_t * rt, u32 key);
56void rb_tree_del_node (rb_tree_t * rt, rb_node_t * z);
57void rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn);
58void rb_tree_free_nodes (rb_tree_t * rt);
59u32 rb_tree_n_nodes (rb_tree_t * rt);
60rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x);
61rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x);
62rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key);
63rb_node_t *rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x,
64					  u32 key, rb_tree_lt_fn ltfn);
65rb_node_t *rb_tree_successor (rb_tree_t * rt, rb_node_t * x);
66rb_node_t *rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x);
67int rb_tree_is_init (rb_tree_t * rt);
68
69static inline rb_node_index_t
70rb_node_index (rb_tree_t * rt, rb_node_t * n)
71{
72  return n - rt->nodes;
73}
74
75static inline u8
76rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n)
77{
78  return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
79}
80
81static inline rb_node_t *
82rb_node (rb_tree_t * rt, rb_node_index_t ri)
83{
84  return pool_elt_at_index (rt->nodes, ri);
85}
86
87static inline rb_node_t *
88rb_node_right (rb_tree_t * rt, rb_node_t * n)
89{
90  return pool_elt_at_index (rt->nodes, n->right);
91}
92
93static inline rb_node_t *
94rb_node_left (rb_tree_t * rt, rb_node_t * n)
95{
96  return pool_elt_at_index (rt->nodes, n->left);
97}
98
99static inline rb_node_t *
100rb_node_parent (rb_tree_t * rt, rb_node_t * n)
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 */
114