Drizzled Public API Documentation

ut0rbt.h
Go to the documentation of this file.
1 /***************************************************************************/
24 /******************************************************************/
31 #pragma once
32 #ifndef INNOBASE_UT0RBT_H
33 #define INNOBASE_UT0RBT_H
34 
35 #if !defined(IB_RBT_TESTING)
36 #include "univ.i"
37 #include "ut0mem.h"
38 #else
39 #include <stdio.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <assert.h>
43 
44 #define ut_malloc malloc
45 #define ut_free free
46 #define ulint unsigned long
47 #define ut_a(c) assert(c)
48 #define ut_error assert(0)
49 #define ibool unsigned int
50 #define TRUE 1
51 #define FALSE 0
52 #endif
53 
54 /* Red black tree typedefs */
55 typedef struct ib_rbt_struct ib_rbt_t;
56 typedef struct ib_rbt_node_struct ib_rbt_node_t;
57 /* FIXME: Iterator is a better name than _bound_ */
58 typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
59 typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
60 typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
61 
64  IB_RBT_RED,
65  IB_RBT_BLACK
66 };
67 
68 typedef enum ib_rbt_color_enum ib_rbt_color_t;
69 
72  ib_rbt_color_t color; /* color of this node */
73 
74  ib_rbt_node_t* left; /* points left child */
75  ib_rbt_node_t* right; /* points right child */
76  ib_rbt_node_t* parent; /* points parent node */
77 
78  char value[1]; /* Data value */
79 };
80 
82 struct ib_rbt_struct {
83  ib_rbt_node_t* nil; /* Black colored node that is
84  used as a sentinel. This is
85  pre-allocated too.*/
86 
87  ib_rbt_node_t* root; /* Root of the tree, this is
88  pre-allocated and the first
89  data node is the left child.*/
90 
91  ulint n_nodes; /* Total number of data nodes */
92 
93  ib_rbt_compare compare; /* Fn. to use for comparison */
94  ulint sizeof_value; /* Sizeof the item in bytes */
95 };
96 
100  const ib_rbt_node_t*
101  last; /* Last node visited */
102 
103  int result; /* Result of comparing with
104  the last non-nil node that
105  was visited */
106 };
107 
108 /* Size in elements (t is an rb tree instance) */
109 #define rbt_size(t) (t->n_nodes)
110 
111 /* Check whether the rb tree is empty (t is an rb tree instance) */
112 #define rbt_empty(t) (rbt_size(t) == 0)
113 
114 /* Get data value (t is the data type, n is an rb tree node instance) */
115 #define rbt_value(t, n) ((t*) &n->value[0])
116 
117 /* Compare a key with the node value (t is tree, k is key, n is node)*/
118 #define rbt_compare(t, k, n) (t->compare(k, n->value))
119 
120 /**********************************************************************/
122 UNIV_INTERN
123 void
124 rbt_free(
125 /*=====*/
126  ib_rbt_t* tree);
127 /**********************************************************************/
130 UNIV_INTERN
131 ib_rbt_t*
132 rbt_create(
133 /*=======*/
134  size_t sizeof_value,
135  ib_rbt_compare compare);
136 /**********************************************************************/
138 UNIV_INTERN
139 ibool
140 rbt_delete(
141 /*=======*/
142  /* in: TRUE on success */
143  ib_rbt_t* tree, /* in: rb tree */
144  const void* key); /* in: key to delete */
145 /**********************************************************************/
149 UNIV_INTERN
152 /*============*/
153  ib_rbt_t* tree,
154  const ib_rbt_node_t*
155  node);
159 /**********************************************************************/
163 UNIV_INTERN
164 const ib_rbt_node_t*
165 rbt_lookup(
166 /*=======*/
167  const ib_rbt_t* tree,
168  const void* key);
169 /**********************************************************************/
172 UNIV_INTERN
173 const ib_rbt_node_t*
174 rbt_insert(
175 /*=======*/
176  ib_rbt_t* tree,
177  const void* key,
178  const void* value);
180 /**********************************************************************/
183 UNIV_INTERN
184 const ib_rbt_node_t*
186 /*=========*/
187  ib_rbt_t* tree,
188  ib_rbt_bound_t* parent,
189  const void* value);
191 /**********************************************************************/
194 UNIV_INTERN
195 const ib_rbt_node_t*
196 rbt_first(
197 /*======*/
198  const ib_rbt_t* tree);
199 /**********************************************************************/
202 UNIV_INTERN
203 const ib_rbt_node_t*
204 rbt_last(
205 /*=====*/
206  const ib_rbt_t* tree);
207 /**********************************************************************/
210 UNIV_INTERN
211 const ib_rbt_node_t*
212 rbt_next(
213 /*=====*/
214  const ib_rbt_t* tree,
215  const ib_rbt_node_t* /* in: current node */
216  current);
217 /**********************************************************************/
220 UNIV_INTERN
221 const ib_rbt_node_t*
222 rbt_prev(
223 /*=====*/
224  const ib_rbt_t* tree,
225  const ib_rbt_node_t* /* in: current node */
226  current);
227 /**********************************************************************/
230 UNIV_INTERN
231 const ib_rbt_node_t*
233 /*============*/
234  const ib_rbt_t* tree,
235  const void* key);
236 /**********************************************************************/
239 UNIV_INTERN
240 const ib_rbt_node_t*
242 /*============*/
243  const ib_rbt_t* tree,
244  const void* key);
245 /**********************************************************************/
250 UNIV_INTERN
251 int
252 rbt_search(
253 /*=======*/
254  const ib_rbt_t* tree,
255  ib_rbt_bound_t* parent,
256  const void* key);
257 /**********************************************************************/
262 UNIV_INTERN
263 int
265 /*===========*/
266  const ib_rbt_t* tree,
267  ib_rbt_bound_t* parent,
268  const void* key,
269  ib_rbt_compare compare);
270 /**********************************************************************/
272 UNIV_INTERN
273 void
274 rbt_clear(
275 /*======*/
276  ib_rbt_t* tree);
277 /**********************************************************************/
280 UNIV_INTERN
281 ulint
283 /*===========*/
284  ib_rbt_t* dst,
285  const ib_rbt_t* src);
286 /**********************************************************************/
293 UNIV_INTERN
294 ulint
296 /*=======================*/
297  ib_rbt_t* dst,
298  ib_rbt_t* src);
299 /**********************************************************************/
303 UNIV_INTERN
304 ibool
306 /*=========*/
307  const ib_rbt_t* tree);
308 /**********************************************************************/
310 UNIV_INTERN
311 void
312 rbt_print(
313 /*======*/
314  const ib_rbt_t* tree,
315  ib_rbt_print_node print);
317 #endif /* INNOBASE_UT0RBT_H */