MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ut0rbt.h
Go to the documentation of this file.
1 /***************************************************************************/
18 /******************************************************************/
25 #ifndef INNOBASE_UT0RBT_H
26 #define INNOBASE_UT0RBT_H
27 
28 #if !defined(IB_RBT_TESTING)
29 #include "univ.i"
30 #include "ut0mem.h"
31 #else
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <assert.h>
36 
37 #define ut_malloc malloc
38 #define ut_free free
39 #define ulint unsigned long
40 #define ut_a(c) assert(c)
41 #define ut_error assert(0)
42 #define ibool unsigned int
43 #define TRUE 1
44 #define FALSE 0
45 #endif
46 
47 struct ib_rbt_node_t;
48 typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
49 typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
50 typedef int (*ib_rbt_arg_compare)(const void*, const void* p1, const void* p2);
51 
53 enum ib_rbt_color_t {
54  IB_RBT_RED,
55  IB_RBT_BLACK
56 };
57 
59 struct ib_rbt_node_t {
60  ib_rbt_color_t color; /* color of this node */
61 
62  ib_rbt_node_t* left; /* points left child */
63  ib_rbt_node_t* right; /* points right child */
64  ib_rbt_node_t* parent; /* points parent node */
65 
66  char value[1]; /* Data value */
67 };
68 
70 struct ib_rbt_t {
71  ib_rbt_node_t* nil; /* Black colored node that is
72  used as a sentinel. This is
73  pre-allocated too.*/
74 
75  ib_rbt_node_t* root; /* Root of the tree, this is
76  pre-allocated and the first
77  data node is the left child.*/
78 
79  ulint n_nodes; /* Total number of data nodes */
80 
81  ib_rbt_compare compare; /* Fn. to use for comparison */
82  ib_rbt_arg_compare
83  compare_with_arg; /* Fn. to use for comparison
84  with argument */
85  ulint sizeof_value; /* Sizeof the item in bytes */
86  void* cmp_arg; /* Compare func argument */
87 };
88 
91 struct ib_rbt_bound_t {
92  const ib_rbt_node_t*
93  last; /* Last node visited */
94 
95  int result; /* Result of comparing with
96  the last non-nil node that
97  was visited */
98 };
99 
100 /* Size in elements (t is an rb tree instance) */
101 #define rbt_size(t) (t->n_nodes)
102 
103 /* Check whether the rb tree is empty (t is an rb tree instance) */
104 #define rbt_empty(t) (rbt_size(t) == 0)
105 
106 /* Get data value (t is the data type, n is an rb tree node instance) */
107 #define rbt_value(t, n) ((t*) &n->value[0])
108 
109 /* Compare a key with the node value (t is tree, k is key, n is node)*/
110 #define rbt_compare(t, k, n) (t->compare(k, n->value))
111 
112 /**********************************************************************/
114 UNIV_INTERN
115 void
116 rbt_free(
117 /*=====*/
118  ib_rbt_t* tree);
119 /**********************************************************************/
122 UNIV_INTERN
123 ib_rbt_t*
124 rbt_create(
125 /*=======*/
126  size_t sizeof_value,
127  ib_rbt_compare compare);
128 /**********************************************************************/
132 UNIV_INTERN
133 ib_rbt_t*
134 rbt_create_arg_cmp(
135 /*===============*/
136  size_t sizeof_value,
137  ib_rbt_arg_compare
138  compare,
139  void* cmp_arg);
140 /**********************************************************************/
142 UNIV_INTERN
143 ibool
144 rbt_delete(
145 /*=======*/
146  /* in: TRUE on success */
147  ib_rbt_t* tree, /* in: rb tree */
148  const void* key); /* in: key to delete */
149 /**********************************************************************/
153 UNIV_INTERN
154 ib_rbt_node_t*
155 rbt_remove_node(
156 /*============*/
157  ib_rbt_t* tree,
158  const ib_rbt_node_t*
159  node);
163 /**********************************************************************/
167 UNIV_INTERN
168 const ib_rbt_node_t*
169 rbt_lookup(
170 /*=======*/
171  const ib_rbt_t* tree,
172  const void* key);
173 /**********************************************************************/
176 UNIV_INTERN
177 const ib_rbt_node_t*
178 rbt_insert(
179 /*=======*/
180  ib_rbt_t* tree,
181  const void* key,
182  const void* value);
184 /**********************************************************************/
187 UNIV_INTERN
188 const ib_rbt_node_t*
189 rbt_add_node(
190 /*=========*/
191  ib_rbt_t* tree,
192  ib_rbt_bound_t* parent,
193  const void* value);
195 /**********************************************************************/
198 UNIV_INTERN
199 const ib_rbt_node_t*
200 rbt_first(
201 /*======*/
202  const ib_rbt_t* tree);
203 /**********************************************************************/
206 UNIV_INTERN
207 const ib_rbt_node_t*
208 rbt_last(
209 /*=====*/
210  const ib_rbt_t* tree);
211 /**********************************************************************/
214 UNIV_INTERN
215 const ib_rbt_node_t*
216 rbt_next(
217 /*=====*/
218  const ib_rbt_t* tree,
219  const ib_rbt_node_t* /* in: current node */
220  current);
221 /**********************************************************************/
224 UNIV_INTERN
225 const ib_rbt_node_t*
226 rbt_prev(
227 /*=====*/
228  const ib_rbt_t* tree,
229  const ib_rbt_node_t* /* in: current node */
230  current);
231 /**********************************************************************/
234 UNIV_INTERN
235 const ib_rbt_node_t*
236 rbt_lower_bound(
237 /*============*/
238  const ib_rbt_t* tree,
239  const void* key);
240 /**********************************************************************/
243 UNIV_INTERN
244 const ib_rbt_node_t*
245 rbt_upper_bound(
246 /*============*/
247  const ib_rbt_t* tree,
248  const void* key);
249 /**********************************************************************/
254 UNIV_INTERN
255 int
256 rbt_search(
257 /*=======*/
258  const ib_rbt_t* tree,
259  ib_rbt_bound_t* parent,
260  const void* key);
261 /**********************************************************************/
266 UNIV_INTERN
267 int
268 rbt_search_cmp(
269 /*===========*/
270  const ib_rbt_t* tree,
271  ib_rbt_bound_t* parent,
272  const void* key,
273  ib_rbt_compare compare,
274  ib_rbt_arg_compare
275  arg_compare);
277 /**********************************************************************/
279 UNIV_INTERN
280 void
281 rbt_clear(
282 /*======*/
283  ib_rbt_t* tree);
284 /**********************************************************************/
287 UNIV_INTERN
288 ulint
289 rbt_merge_uniq(
290 /*===========*/
291  ib_rbt_t* dst,
292  const ib_rbt_t* src);
293 /**********************************************************************/
300 UNIV_INTERN
301 ulint
302 rbt_merge_uniq_destructive(
303 /*=======================*/
304  ib_rbt_t* dst,
305  ib_rbt_t* src);
306 /**********************************************************************/
310 UNIV_INTERN
311 ibool
312 rbt_validate(
313 /*=========*/
314  const ib_rbt_t* tree);
315 /**********************************************************************/
317 UNIV_INTERN
318 void
319 rbt_print(
320 /*======*/
321  const ib_rbt_t* tree,
322  ib_rbt_print_node print);
324 #endif /* INNOBASE_UT0RBT_H */