Go to the documentation of this file.00001
00024
00031 #pragma once
00032 #ifndef INNOBASE_UT0RBT_H
00033 #define INNOBASE_UT0RBT_H
00034
00035 #if !defined(IB_RBT_TESTING)
00036 #include "univ.i"
00037 #include "ut0mem.h"
00038 #else
00039 #include <stdio.h>
00040 #include <stdlib.h>
00041 #include <string.h>
00042 #include <assert.h>
00043
00044 #define ut_malloc malloc
00045 #define ut_free free
00046 #define ulint unsigned long
00047 #define ut_a(c) assert(c)
00048 #define ut_error assert(0)
00049 #define ibool unsigned int
00050 #define TRUE 1
00051 #define FALSE 0
00052 #endif
00053
00054
00055 typedef struct ib_rbt_struct ib_rbt_t;
00056 typedef struct ib_rbt_node_struct ib_rbt_node_t;
00057
00058 typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
00059 typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
00060 typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
00061
00063 enum ib_rbt_color_enum {
00064 IB_RBT_RED,
00065 IB_RBT_BLACK
00066 };
00067
00068 typedef enum ib_rbt_color_enum ib_rbt_color_t;
00069
00071 struct ib_rbt_node_struct {
00072 ib_rbt_color_t color;
00073
00074 ib_rbt_node_t* left;
00075 ib_rbt_node_t* right;
00076 ib_rbt_node_t* parent;
00077
00078 char value[1];
00079 };
00080
00082 struct ib_rbt_struct {
00083 ib_rbt_node_t* nil;
00084
00085
00086
00087 ib_rbt_node_t* root;
00088
00089
00090
00091 ulint n_nodes;
00092
00093 ib_rbt_compare compare;
00094 ulint sizeof_value;
00095 };
00096
00099 struct ib_rbt_bound_struct {
00100 const ib_rbt_node_t*
00101 last;
00102
00103 int result;
00104
00105
00106 };
00107
00108
00109 #define rbt_size(t) (t->n_nodes)
00110
00111
00112 #define rbt_empty(t) (rbt_size(t) == 0)
00113
00114
00115 #define rbt_value(t, n) ((t*) &n->value[0])
00116
00117
00118 #define rbt_compare(t, k, n) (t->compare(k, n->value))
00119
00120
00122 UNIV_INTERN
00123 void
00124 rbt_free(
00125
00126 ib_rbt_t* tree);
00127
00130 UNIV_INTERN
00131 ib_rbt_t*
00132 rbt_create(
00133
00134 size_t sizeof_value,
00135 ib_rbt_compare compare);
00136
00138 UNIV_INTERN
00139 ibool
00140 rbt_delete(
00141
00142
00143 ib_rbt_t* tree,
00144 const void* key);
00145
00149 UNIV_INTERN
00150 ib_rbt_node_t*
00151 rbt_remove_node(
00152
00153 ib_rbt_t* tree,
00154 const ib_rbt_node_t*
00155 node);
00159
00163 UNIV_INTERN
00164 const ib_rbt_node_t*
00165 rbt_lookup(
00166
00167 const ib_rbt_t* tree,
00168 const void* key);
00169
00172 UNIV_INTERN
00173 const ib_rbt_node_t*
00174 rbt_insert(
00175
00176 ib_rbt_t* tree,
00177 const void* key,
00178 const void* value);
00180
00183 UNIV_INTERN
00184 const ib_rbt_node_t*
00185 rbt_add_node(
00186
00187 ib_rbt_t* tree,
00188 ib_rbt_bound_t* parent,
00189 const void* value);
00191
00194 UNIV_INTERN
00195 const ib_rbt_node_t*
00196 rbt_first(
00197
00198 const ib_rbt_t* tree);
00199
00202 UNIV_INTERN
00203 const ib_rbt_node_t*
00204 rbt_last(
00205
00206 const ib_rbt_t* tree);
00207
00210 UNIV_INTERN
00211 const ib_rbt_node_t*
00212 rbt_next(
00213
00214 const ib_rbt_t* tree,
00215 const ib_rbt_node_t*
00216 current);
00217
00220 UNIV_INTERN
00221 const ib_rbt_node_t*
00222 rbt_prev(
00223
00224 const ib_rbt_t* tree,
00225 const ib_rbt_node_t*
00226 current);
00227
00230 UNIV_INTERN
00231 const ib_rbt_node_t*
00232 rbt_lower_bound(
00233
00234 const ib_rbt_t* tree,
00235 const void* key);
00236
00239 UNIV_INTERN
00240 const ib_rbt_node_t*
00241 rbt_upper_bound(
00242
00243 const ib_rbt_t* tree,
00244 const void* key);
00245
00250 UNIV_INTERN
00251 int
00252 rbt_search(
00253
00254 const ib_rbt_t* tree,
00255 ib_rbt_bound_t* parent,
00256 const void* key);
00257
00262 UNIV_INTERN
00263 int
00264 rbt_search_cmp(
00265
00266 const ib_rbt_t* tree,
00267 ib_rbt_bound_t* parent,
00268 const void* key,
00269 ib_rbt_compare compare);
00270
00272 UNIV_INTERN
00273 void
00274 rbt_clear(
00275
00276 ib_rbt_t* tree);
00277
00280 UNIV_INTERN
00281 ulint
00282 rbt_merge_uniq(
00283
00284 ib_rbt_t* dst,
00285 const ib_rbt_t* src);
00286
00293 UNIV_INTERN
00294 ulint
00295 rbt_merge_uniq_destructive(
00296
00297 ib_rbt_t* dst,
00298 ib_rbt_t* src);
00299
00303 UNIV_INTERN
00304 ibool
00305 rbt_validate(
00306
00307 const ib_rbt_t* tree);
00308
00310 UNIV_INTERN
00311 void
00312 rbt_print(
00313
00314 const ib_rbt_t* tree,
00315 ib_rbt_print_node print);
00317 #endif