Drizzled Public API Documentation
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
File Members
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
63
enum
ib_rbt_color_enum
{
64
IB_RBT_RED,
65
IB_RBT_BLACK
66
};
67
68
typedef
enum
ib_rbt_color_enum
ib_rbt_color_t;
69
71
struct
ib_rbt_node_struct
{
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
99
struct
ib_rbt_bound_struct
{
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
150
ib_rbt_node_t
*
151
rbt_remove_node
(
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
*
185
rbt_add_node
(
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
*
232
rbt_lower_bound
(
233
/*============*/
234
const
ib_rbt_t
* tree,
235
const
void
* key);
236
/**********************************************************************/
239
UNIV_INTERN
240
const
ib_rbt_node_t
*
241
rbt_upper_bound
(
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
264
rbt_search_cmp
(
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
282
rbt_merge_uniq
(
283
/*===========*/
284
ib_rbt_t
* dst,
285
const
ib_rbt_t
* src);
286
/**********************************************************************/
293
UNIV_INTERN
294
ulint
295
rbt_merge_uniq_destructive
(
296
/*=======================*/
297
ib_rbt_t
* dst,
298
ib_rbt_t
* src);
299
/**********************************************************************/
303
UNIV_INTERN
304
ibool
305
rbt_validate
(
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 */
plugin
innobase
include
ut0rbt.h
Generated on Tue Jun 19 2012 18:56:54 for drizzle by
1.8.1