← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/include/ut0rbt.h

  • Committer: Monty Taylor
  • Date: 2010-11-26 22:50:54 UTC
  • mfrom: (1953.1.6 build)
  • Revision ID: mordred@inaugust.com-20101126225054-sg90svw8579t5p3i
Stewart - InnoDB 1.1.1
Monty - Fixed some autoconf tests which were returning false positives.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/include/ut0rbt.h
1
 
/*****************************************************************************
2
 
Copyright (c) 2006, 2009, Innobase Oy. All Rights Reserved.
 
1
/***************************************************************************//**
 
2
 
 
3
Copyright (c) 2007, 2010, Innobase Oy. All Rights Reserved.
 
4
 
 
5
Portions of this file contain modifications contributed and copyrighted by
 
6
Sun Microsystems, Inc. Those modifications are gratefully acknowledged and
 
7
are described briefly in the InnoDB documentation. The contributions by
 
8
Sun Microsystems are incorporated with their permission, and subject to the
 
9
conditions contained in the file COPYING.Sun_Microsystems.
3
10
 
4
11
This program is free software; you can redistribute it and/or modify it under
5
12
the terms of the GNU General Public License as published by the Free Software
14
21
Place, Suite 330, Boston, MA 02111-1307 USA
15
22
 
16
23
*****************************************************************************/
17
 
 
18
 
/*******************************************************************//**
 
24
/******************************************************************//**
19
25
@file include/ut0rbt.h
20
 
Red-Black tree implementation.
 
26
Various utilities
21
27
 
22
28
Created 2007-03-20 Sunny Bains
23
 
************************************************************************/
 
29
*******************************************************/
24
30
 
25
31
#ifndef INNOBASE_UT0RBT_H
26
32
#define INNOBASE_UT0RBT_H
47
53
/* Red black tree typedefs */
48
54
typedef struct ib_rbt_struct ib_rbt_t;
49
55
typedef struct ib_rbt_node_struct ib_rbt_node_t;
50
 
/* FIXME: Iterator is a better name than _bound_ */
 
56
// FIXME: Iterator is a better name than _bound_
51
57
typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
52
58
typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
53
59
typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
54
60
 
55
 
/* Red black tree color types */
 
61
/** Red black tree color types */
56
62
enum ib_rbt_color_enum {
57
63
        IB_RBT_RED,
58
64
        IB_RBT_BLACK
60
66
 
61
67
typedef enum ib_rbt_color_enum ib_rbt_color_t;
62
68
 
63
 
/* Red black tree node */
 
69
/** Red black tree node */
64
70
struct ib_rbt_node_struct {
65
71
        ib_rbt_color_t  color;                  /* color of this node */
66
72
 
71
77
        char            value[1];               /* Data value */
72
78
};
73
79
 
74
 
/* Red black tree instance.*/
 
80
/** Red black tree instance.*/
75
81
struct  ib_rbt_struct {
76
82
        ib_rbt_node_t*  nil;                    /* Black colored node that is
77
83
                                                used as a sentinel. This is
87
93
        ulint           sizeof_value;           /* Sizeof the item in bytes */
88
94
};
89
95
 
90
 
/* The result of searching for a key in the tree, this is useful for
 
96
/** The result of searching for a key in the tree, this is useful for
91
97
a speedy lookup and insert if key doesn't exist.*/
92
98
struct ib_rbt_bound_struct {
93
99
        const ib_rbt_node_t*
110
116
/* Compare a key with the node value (t is tree, k is key, n is node)*/
111
117
#define rbt_compare(t, k, n) (t->compare(k, n->value))
112
118
 
113
 
/****************************************************************//**
 
119
/**********************************************************************//**
114
120
Free an instance of  a red black tree */
115
121
UNIV_INTERN
116
122
void
117
123
rbt_free(
118
124
/*=====*/
119
 
        ib_rbt_t*       tree);          /*!< in: rb tree to free */
120
 
/****************************************************************//**
 
125
        ib_rbt_t*       tree);                  /*!< in: rb tree to free */
 
126
/**********************************************************************//**
121
127
Create an instance of a red black tree
122
128
@return rb tree instance */
123
129
UNIV_INTERN
124
130
ib_rbt_t*
125
131
rbt_create(
126
132
/*=======*/
127
 
        size_t          sizeof_value,   /*!< in: size in bytes */
128
 
        ib_rbt_compare  compare);       /*!< in: comparator */
129
 
/****************************************************************//**
130
 
Delete a node from the red black tree, identified by key.
131
 
@return TRUE if success FALSE if not found */
 
133
        size_t          sizeof_value,           /*!< in: size in bytes */
 
134
        ib_rbt_compare  compare);               /*!< in: comparator */
 
135
/**********************************************************************//**
 
136
Delete a node from the red black tree, identified by key */
132
137
UNIV_INTERN
133
138
ibool
134
139
rbt_delete(
135
140
/*=======*/
136
 
        ib_rbt_t*       tree,           /*!< in: rb tree */
137
 
        const void*     key);           /*!< in: key to delete */
138
 
/****************************************************************//**
139
 
Remove a node from the rb tree, the node is not free'd, that is the
140
 
callers responsibility.
 
141
                                                /* in: TRUE on success */
 
142
        ib_rbt_t*       tree,                   /* in: rb tree */
 
143
        const void*     key);                   /* in: key to delete */
 
144
/**********************************************************************//**
 
145
Remove a node from the red black tree, NOTE: This function will not delete
 
146
the node instance, THAT IS THE CALLERS RESPONSIBILITY.
141
147
@return the deleted node with the const. */
142
148
UNIV_INTERN
143
149
ib_rbt_node_t*
144
150
rbt_remove_node(
145
151
/*============*/
146
 
        ib_rbt_t*       tree,           /*!< in: rb tree */
 
152
        ib_rbt_t*       tree,                   /*!< in: rb tree */
147
153
        const ib_rbt_node_t*
148
 
                        node);          /*!< in: node to delete, this
149
 
                                        is a fudge and declared const
150
 
                                        because the caller has access
151
 
                                        only to const nodes.*/
152
 
/****************************************************************//**
153
 
Find a matching node in the rb tree.
 
154
                        node);                  /*!< in: node to delete, this
 
155
                                                is a fudge and declared const
 
156
                                                because the caller has access
 
157
                                                only to const nodes.*/
 
158
/**********************************************************************//**
 
159
Return a node from the red black tree, identified by
 
160
key, NULL if not found
154
161
@return node if found else return NULL */
155
162
UNIV_INTERN
156
163
const ib_rbt_node_t*
157
164
rbt_lookup(
158
165
/*=======*/
159
 
        const ib_rbt_t* tree,           /*!< in: rb tree to search */
160
 
        const void*     key);           /*!< in: key to lookup */
161
 
/****************************************************************//**
162
 
Generic insert of a value in the rb tree.
 
166
        const ib_rbt_t* tree,                   /*!< in: rb tree to search */
 
167
        const void*     key);                   /*!< in: key to lookup */
 
168
/**********************************************************************//**
 
169
Add data to the red black tree, identified by key (no dups yet!)
163
170
@return inserted node */
164
171
UNIV_INTERN
165
172
const ib_rbt_node_t*
166
173
rbt_insert(
167
174
/*=======*/
168
 
        ib_rbt_t*       tree,           /*!< in: rb tree */
169
 
        const void*     key,            /*!< in: key for ordering */
170
 
        const void*     value);         /*!< in: data that will be
171
 
                                        copied to the node.*/
172
 
/****************************************************************//**
 
175
        ib_rbt_t*       tree,                   /*!< in: rb tree */
 
176
        const void*     key,                    /*!< in: key for ordering */
 
177
        const void*     value);                 /*!< in: data that will be
 
178
                                                copied to the node.*/
 
179
/**********************************************************************//**
173
180
Add a new node to the tree, useful for data that is pre-sorted.
174
181
@return appended node */
175
182
UNIV_INTERN
176
183
const ib_rbt_node_t*
177
184
rbt_add_node(
178
185
/*=========*/
179
 
        ib_rbt_t*       tree,           /*!< in: rb tree */
180
 
        ib_rbt_bound_t* parent,         /*!< in: parent */
181
 
        const void*     value);         /*!< in: this value is copied
182
 
                                        to the node */
183
 
/****************************************************************//**
 
186
        ib_rbt_t*       tree,                   /*!< in: rb tree */
 
187
        ib_rbt_bound_t* parent,                 /*!< in: parent */
 
188
        const void*     value);                 /*!< in: this value is copied
 
189
                                                to the node */
 
190
/**********************************************************************//**
184
191
Return the left most data node in the tree
185
192
@return left most node */
186
193
UNIV_INTERN
187
194
const ib_rbt_node_t*
188
195
rbt_first(
189
196
/*======*/
190
 
        const ib_rbt_t* tree);          /*!< in: rb tree */
191
 
/****************************************************************//**
 
197
        const ib_rbt_t* tree);                  /*!< in: rb tree */
 
198
/**********************************************************************//**
192
199
Return the right most data node in the tree
193
200
@return right most node */
194
201
UNIV_INTERN
195
202
const ib_rbt_node_t*
196
203
rbt_last(
197
204
/*=====*/
198
 
        const ib_rbt_t* tree);          /*!< in: rb tree */
199
 
/****************************************************************//**
 
205
        const ib_rbt_t* tree);                  /*!< in: rb tree */
 
206
/**********************************************************************//**
200
207
Return the next node from current.
201
208
@return successor node to current that is passed in. */
202
209
UNIV_INTERN
203
210
const ib_rbt_node_t*
204
211
rbt_next(
205
212
/*=====*/
206
 
        const ib_rbt_t* tree,           /*!< in: rb tree */
207
 
        const ib_rbt_node_t*            /*!< in: current node */
 
213
        const ib_rbt_t* tree,                   /*!< in: rb tree */
 
214
        const ib_rbt_node_t*                    /* in: current node */
208
215
                        current);
209
 
/****************************************************************//**
 
216
/**********************************************************************//**
210
217
Return the prev node from current.
211
218
@return precedessor node to current that is passed in */
212
219
UNIV_INTERN
213
220
const ib_rbt_node_t*
214
221
rbt_prev(
215
222
/*=====*/
216
 
        const ib_rbt_t* tree,           /*!< in: rb tree */
217
 
        const ib_rbt_node_t*            /*!< in: current node */
 
223
        const ib_rbt_t* tree,                   /*!< in: rb tree */
 
224
        const ib_rbt_node_t*                    /* in: current node */
218
225
                        current);
219
 
/****************************************************************//**
 
226
/**********************************************************************//**
220
227
Find the node that has the lowest key that is >= key.
221
228
@return node that satisfies the lower bound constraint or NULL */
222
229
UNIV_INTERN
223
230
const ib_rbt_node_t*
224
231
rbt_lower_bound(
225
232
/*============*/
226
 
        const ib_rbt_t* tree,           /*!< in: rb tree */
227
 
        const void*     key);           /*!< in: key to search */
228
 
/****************************************************************//**
 
233
        const ib_rbt_t* tree,                   /*!< in: rb tree */
 
234
        const void*     key);                   /*!< in: key to search */
 
235
/**********************************************************************//**
229
236
Find the node that has the greatest key that is <= key.
230
237
@return node that satisifies the upper bound constraint or NULL */
231
238
UNIV_INTERN
232
239
const ib_rbt_node_t*
233
240
rbt_upper_bound(
234
241
/*============*/
235
 
        const ib_rbt_t* tree,           /*!< in: rb tree */
236
 
        const void*     key);           /*!< in: key to search */
237
 
/****************************************************************//**
 
242
        const ib_rbt_t* tree,                   /*!< in: rb tree */
 
243
        const void*     key);                   /*!< in: key to search */
 
244
/**********************************************************************//**
238
245
Search for the key, a node will be retuned in parent.last, whether it
239
246
was found or not. If not found then parent.last will contain the
240
247
parent node for the possibly new key otherwise the matching node.
243
250
int
244
251
rbt_search(
245
252
/*=======*/
246
 
        const ib_rbt_t* tree,           /*!< in: rb tree */
247
 
        ib_rbt_bound_t* parent,         /*!< in: search bounds */
248
 
        const void*     key);           /*!< in: key to search */
249
 
/****************************************************************//**
 
253
        const ib_rbt_t* tree,                   /*!< in: rb tree */
 
254
        ib_rbt_bound_t* parent,                 /*!< in: search bounds */
 
255
        const void*     key);                   /*!< in: key to search */
 
256
/**********************************************************************//**
250
257
Search for the key, a node will be retuned in parent.last, whether it
251
258
was found or not. If not found then parent.last will contain the
252
259
parent node for the possibly new key otherwise the matching node.
255
262
int
256
263
rbt_search_cmp(
257
264
/*===========*/
258
 
        const ib_rbt_t* tree,           /*!< in: rb tree */
259
 
        ib_rbt_bound_t* parent,         /*!< in: search bounds */
260
 
        const void*     key,            /*!< in: key to search */
261
 
        ib_rbt_compare  compare);       /*!< in: comparator */
262
 
/****************************************************************//**
 
265
        const ib_rbt_t* tree,                   /*!< in: rb tree */
 
266
        ib_rbt_bound_t* parent,                 /*!< in: search bounds */
 
267
        const void*     key,                    /*!< in: key to search */
 
268
        ib_rbt_compare  compare);               /*!< in: comparator */
 
269
/**********************************************************************//**
263
270
Clear the tree, deletes (and free's) all the nodes. */
264
271
UNIV_INTERN
265
272
void
266
273
rbt_clear(
267
274
/*======*/
268
 
        ib_rbt_t*       tree);          /*!< in: rb tree */
269
 
/****************************************************************//**
 
275
        ib_rbt_t*       tree);                  /*!< in: rb tree */
 
276
/**********************************************************************//**
270
277
Merge the node from dst into src. Return the number of nodes merged.
271
278
@return no. of recs merged */
272
279
UNIV_INTERN
273
280
ulint
274
281
rbt_merge_uniq(
275
282
/*===========*/
276
 
        ib_rbt_t*       dst,            /*!< in: dst rb tree */
277
 
        const ib_rbt_t* src);           /*!< in: src rb tree */
278
 
/****************************************************************//**
 
283
        ib_rbt_t*       dst,                    /*!< in: dst rb tree */
 
284
        const ib_rbt_t* src);                   /*!< in: src rb tree */
 
285
/**********************************************************************//**
279
286
Merge the node from dst into src. Return the number of nodes merged.
280
287
Delete the nodes from src after copying node to dst. As a side effect
281
288
the duplicates will be left untouched in the src, since we don't support
286
293
ulint
287
294
rbt_merge_uniq_destructive(
288
295
/*=======================*/
289
 
        ib_rbt_t*       dst,            /*!< in: dst rb tree */
290
 
        ib_rbt_t*       src);           /*!< in: src rb tree */
291
 
/****************************************************************//**
 
296
        ib_rbt_t*       dst,                    /*!< in: dst rb tree */
 
297
        ib_rbt_t*       src);                   /*!< in: src rb tree */
 
298
/**********************************************************************//**
292
299
Verify the integrity of the RB tree. For debugging. 0 failure else height
293
300
of tree (in count of black nodes).
294
301
@return TRUE if OK FALSE if tree invalid. */
296
303
ibool
297
304
rbt_validate(
298
305
/*=========*/
299
 
        const ib_rbt_t* tree);          /*!< in: tree to validate */
300
 
/****************************************************************//**
 
306
        const ib_rbt_t* tree);                  /*!< in: tree to validate */
 
307
/**********************************************************************//**
301
308
Iterate over the tree in depth first order. */
302
309
UNIV_INTERN
303
310
void
304
311
rbt_print(
305
312
/*======*/
306
 
        const ib_rbt_t*         tree,   /*!< in: tree to traverse */
307
 
        ib_rbt_print_node       print); /*!< in: print function */
 
313
        const ib_rbt_t*         tree,           /*!< in: tree to traverse */
 
314
        ib_rbt_print_node       print);         /*!< in: print function */
308
315
 
309
316
#endif /* INNOBASE_UT0RBT_H */