drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
ut0rbt.h
Go to the documentation of this file.
1/***************************************************************************/
24/******************************************************************/
30
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 */
55typedef struct ib_rbt_struct ib_rbt_t;
56typedef struct ib_rbt_node_struct ib_rbt_node_t;
57/* FIXME: Iterator is a better name than _bound_ */
58typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
59typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
60typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
61
64 IB_RBT_RED,
65 IB_RBT_BLACK
66};
67
68typedef 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
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/**********************************************************************/
122UNIV_INTERN
123void
125/*=====*/
126 ib_rbt_t* tree);
127/**********************************************************************/
130UNIV_INTERN
131ib_rbt_t*
133/*=======*/
134 size_t sizeof_value,
135 ib_rbt_compare compare);
136/**********************************************************************/
138UNIV_INTERN
139ibool
141/*=======*/
142 /* in: TRUE on success */
143 ib_rbt_t* tree, /* in: rb tree */
144 const void* key); /* in: key to delete */
145/**********************************************************************/
149UNIV_INTERN
150ib_rbt_node_t*
152/*============*/
153 ib_rbt_t* tree,
154 const ib_rbt_node_t*
155 node);
159/**********************************************************************/
163UNIV_INTERN
164const ib_rbt_node_t*
166/*=======*/
167 const ib_rbt_t* tree,
168 const void* key);
169/**********************************************************************/
172UNIV_INTERN
173const ib_rbt_node_t*
175/*=======*/
176 ib_rbt_t* tree,
177 const void* key,
178 const void* value);
180/**********************************************************************/
183UNIV_INTERN
184const ib_rbt_node_t*
186/*=========*/
187 ib_rbt_t* tree,
188 ib_rbt_bound_t* parent,
189 const void* value);
191/**********************************************************************/
194UNIV_INTERN
195const ib_rbt_node_t*
197/*======*/
198 const ib_rbt_t* tree);
199/**********************************************************************/
202UNIV_INTERN
203const ib_rbt_node_t*
205/*=====*/
206 const ib_rbt_t* tree);
207/**********************************************************************/
210UNIV_INTERN
211const ib_rbt_node_t*
213/*=====*/
214 const ib_rbt_t* tree,
215 const ib_rbt_node_t* /* in: current node */
216 current);
217/**********************************************************************/
220UNIV_INTERN
221const ib_rbt_node_t*
223/*=====*/
224 const ib_rbt_t* tree,
225 const ib_rbt_node_t* /* in: current node */
226 current);
227/**********************************************************************/
230UNIV_INTERN
231const ib_rbt_node_t*
233/*============*/
234 const ib_rbt_t* tree,
235 const void* key);
236/**********************************************************************/
239UNIV_INTERN
240const ib_rbt_node_t*
242/*============*/
243 const ib_rbt_t* tree,
244 const void* key);
245/**********************************************************************/
250UNIV_INTERN
251int
253/*=======*/
254 const ib_rbt_t* tree,
255 ib_rbt_bound_t* parent,
256 const void* key);
257/**********************************************************************/
262UNIV_INTERN
263int
265/*===========*/
266 const ib_rbt_t* tree,
267 ib_rbt_bound_t* parent,
268 const void* key,
269 ib_rbt_compare compare);
270/**********************************************************************/
272UNIV_INTERN
273void
275/*======*/
276 ib_rbt_t* tree);
277/**********************************************************************/
280UNIV_INTERN
281ulint
283/*===========*/
284 ib_rbt_t* dst,
285 const ib_rbt_t* src);
286/**********************************************************************/
293UNIV_INTERN
294ulint
296/*=======================*/
297 ib_rbt_t* dst,
298 ib_rbt_t* src);
299/**********************************************************************/
303UNIV_INTERN
304ibool
306/*=========*/
307 const ib_rbt_t* tree);
308/**********************************************************************/
310UNIV_INTERN
311void
313/*======*/
314 const ib_rbt_t* tree,
315 ib_rbt_print_node print);
316
317#endif /* INNOBASE_UT0RBT_H */
UNIV_INTERN ib_rbt_node_t * rbt_remove_node(ib_rbt_t *tree, const ib_rbt_node_t *node)
Definition ut0rbt.cc:914
UNIV_INTERN void rbt_free(ib_rbt_t *tree)
Definition ut0rbt.cc:743
UNIV_INTERN const ib_rbt_node_t * rbt_lookup(const ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:862
UNIV_INTERN const ib_rbt_node_t * rbt_first(const ib_rbt_t *tree)
Definition ut0rbt.cc:1074
UNIV_INTERN void rbt_clear(ib_rbt_t *tree)
Definition ut0rbt.cc:1140
UNIV_INTERN const ib_rbt_node_t * rbt_add_node(ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
Definition ut0rbt.cc:824
UNIV_INTERN ibool rbt_validate(const ib_rbt_t *tree)
Definition ut0rbt.cc:1233
UNIV_INTERN const ib_rbt_node_t * rbt_next(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Definition ut0rbt.cc:1115
UNIV_INTERN int rbt_search(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key)
Definition ut0rbt.cc:1005
UNIV_INTERN ib_rbt_t * rbt_create(size_t sizeof_value, ib_rbt_compare compare)
Definition ut0rbt.cc:757
UNIV_INTERN const ib_rbt_node_t * rbt_last(const ib_rbt_t *tree)
Definition ut0rbt.cc:1095
UNIV_INTERN ulint rbt_merge_uniq(ib_rbt_t *dst, const ib_rbt_t *src)
Definition ut0rbt.cc:1155
UNIV_INTERN void rbt_print(const ib_rbt_t *tree, ib_rbt_print_node print)
Definition ut0rbt.cc:1248
UNIV_INTERN const ib_rbt_node_t * rbt_upper_bound(const ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:971
UNIV_INTERN ulint rbt_merge_uniq_destructive(ib_rbt_t *dst, ib_rbt_t *src)
Definition ut0rbt.cc:1186
ib_rbt_color_enum
Definition ut0rbt.h:63
UNIV_INTERN int rbt_search_cmp(const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare)
Definition ut0rbt.cc:1040
UNIV_INTERN const ib_rbt_node_t * rbt_lower_bound(const ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:937
UNIV_INTERN ibool rbt_delete(ib_rbt_t *tree, const void *key)
Definition ut0rbt.cc:890
UNIV_INTERN const ib_rbt_node_t * rbt_prev(const ib_rbt_t *tree, const ib_rbt_node_t *current)
Definition ut0rbt.cc:1128
UNIV_INTERN const ib_rbt_node_t * rbt_insert(ib_rbt_t *tree, const void *key, const void *value)
Definition ut0rbt.cc:795