← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

Merge Joe, plus I updated the tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/include/ut0rbt.h
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.
10
 
 
11
 
This program is free software; you can redistribute it and/or modify it under
12
 
the terms of the GNU General Public License as published by the Free Software
13
 
Foundation; version 2 of the License.
14
 
 
15
 
This program is distributed in the hope that it will be useful, but WITHOUT
16
 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17
 
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
18
 
 
19
 
You should have received a copy of the GNU General Public License along with
20
 
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
21
 
Place, Suite 330, Boston, MA 02111-1307 USA
22
 
 
23
 
*****************************************************************************/
24
 
/******************************************************************//**
25
 
@file include/ut0rbt.h
26
 
Various utilities
27
 
 
28
 
Created 2007-03-20 Sunny Bains
29
 
*******************************************************/
30
 
 
31
 
#ifndef INNOBASE_UT0RBT_H
32
 
#define INNOBASE_UT0RBT_H
33
 
 
34
 
#if !defined(IB_RBT_TESTING)
35
 
#include "univ.i"
36
 
#include "ut0mem.h"
37
 
#else
38
 
#include <stdio.h>
39
 
#include <stdlib.h>
40
 
#include <string.h>
41
 
#include <assert.h>
42
 
 
43
 
#define ut_malloc       malloc
44
 
#define ut_free         free
45
 
#define ulint           unsigned long
46
 
#define ut_a(c)         assert(c)
47
 
#define ut_error        assert(0)
48
 
#define ibool           unsigned int
49
 
#define TRUE            1
50
 
#define FALSE           0
51
 
#endif
52
 
 
53
 
/* Red black tree typedefs */
54
 
typedef struct ib_rbt_struct ib_rbt_t;
55
 
typedef struct ib_rbt_node_struct ib_rbt_node_t;
56
 
/* FIXME: Iterator is a better name than _bound_ */
57
 
typedef struct ib_rbt_bound_struct ib_rbt_bound_t;
58
 
typedef void (*ib_rbt_print_node)(const ib_rbt_node_t* node);
59
 
typedef int (*ib_rbt_compare)(const void* p1, const void* p2);
60
 
 
61
 
/** Red black tree color types */
62
 
enum ib_rbt_color_enum {
63
 
        IB_RBT_RED,
64
 
        IB_RBT_BLACK
65
 
};
66
 
 
67
 
typedef enum ib_rbt_color_enum ib_rbt_color_t;
68
 
 
69
 
/** Red black tree node */
70
 
struct ib_rbt_node_struct {
71
 
        ib_rbt_color_t  color;                  /* color of this node */
72
 
 
73
 
        ib_rbt_node_t*  left;                   /* points left child */
74
 
        ib_rbt_node_t*  right;                  /* points right child */
75
 
        ib_rbt_node_t*  parent;                 /* points parent node */
76
 
 
77
 
        char            value[1];               /* Data value */
78
 
};
79
 
 
80
 
/** Red black tree instance.*/
81
 
struct  ib_rbt_struct {
82
 
        ib_rbt_node_t*  nil;                    /* Black colored node that is
83
 
                                                used as a sentinel. This is
84
 
                                                pre-allocated too.*/
85
 
 
86
 
        ib_rbt_node_t*  root;                   /* Root of the tree, this is
87
 
                                                pre-allocated and the first
88
 
                                                data node is the left child.*/
89
 
 
90
 
        ulint           n_nodes;                /* Total number of data nodes */
91
 
 
92
 
        ib_rbt_compare  compare;                /* Fn. to use for comparison */
93
 
        ulint           sizeof_value;           /* Sizeof the item in bytes */
94
 
};
95
 
 
96
 
/** The result of searching for a key in the tree, this is useful for
97
 
a speedy lookup and insert if key doesn't exist.*/
98
 
struct ib_rbt_bound_struct {
99
 
        const ib_rbt_node_t*
100
 
                        last;                   /* Last node visited */
101
 
 
102
 
        int             result;                 /* Result of comparing with
103
 
                                                the last non-nil node that
104
 
                                                was visited */
105
 
};
106
 
 
107
 
/* Size in elements (t is an rb tree instance) */
108
 
#define rbt_size(t)     (t->n_nodes)
109
 
 
110
 
/* Check whether the rb tree is empty (t is an rb tree instance) */
111
 
#define rbt_empty(t)    (rbt_size(t) == 0)
112
 
 
113
 
/* Get data value (t is the data type, n is an rb tree node instance) */
114
 
#define rbt_value(t, n) ((t*) &n->value[0])
115
 
 
116
 
/* Compare a key with the node value (t is tree, k is key, n is node)*/
117
 
#define rbt_compare(t, k, n) (t->compare(k, n->value))
118
 
 
119
 
/**********************************************************************//**
120
 
Free an instance of  a red black tree */
121
 
UNIV_INTERN
122
 
void
123
 
rbt_free(
124
 
/*=====*/
125
 
        ib_rbt_t*       tree);                  /*!< in: rb tree to free */
126
 
/**********************************************************************//**
127
 
Create an instance of a red black tree
128
 
@return rb tree instance */
129
 
UNIV_INTERN
130
 
ib_rbt_t*
131
 
rbt_create(
132
 
/*=======*/
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 */
137
 
UNIV_INTERN
138
 
ibool
139
 
rbt_delete(
140
 
/*=======*/
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.
147
 
@return the deleted node with the const. */
148
 
UNIV_INTERN
149
 
ib_rbt_node_t*
150
 
rbt_remove_node(
151
 
/*============*/
152
 
        ib_rbt_t*       tree,                   /*!< in: rb tree */
153
 
        const ib_rbt_node_t*
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
161
 
@return node if found else return NULL */
162
 
UNIV_INTERN
163
 
const ib_rbt_node_t*
164
 
rbt_lookup(
165
 
/*=======*/
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!)
170
 
@return inserted node */
171
 
UNIV_INTERN
172
 
const ib_rbt_node_t*
173
 
rbt_insert(
174
 
/*=======*/
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
 
/**********************************************************************//**
180
 
Add a new node to the tree, useful for data that is pre-sorted.
181
 
@return appended node */
182
 
UNIV_INTERN
183
 
const ib_rbt_node_t*
184
 
rbt_add_node(
185
 
/*=========*/
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
 
/**********************************************************************//**
191
 
Return the left most data node in the tree
192
 
@return left most node */
193
 
UNIV_INTERN
194
 
const ib_rbt_node_t*
195
 
rbt_first(
196
 
/*======*/
197
 
        const ib_rbt_t* tree);                  /*!< in: rb tree */
198
 
/**********************************************************************//**
199
 
Return the right most data node in the tree
200
 
@return right most node */
201
 
UNIV_INTERN
202
 
const ib_rbt_node_t*
203
 
rbt_last(
204
 
/*=====*/
205
 
        const ib_rbt_t* tree);                  /*!< in: rb tree */
206
 
/**********************************************************************//**
207
 
Return the next node from current.
208
 
@return successor node to current that is passed in. */
209
 
UNIV_INTERN
210
 
const ib_rbt_node_t*
211
 
rbt_next(
212
 
/*=====*/
213
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
214
 
        const ib_rbt_node_t*                    /* in: current node */
215
 
                        current);
216
 
/**********************************************************************//**
217
 
Return the prev node from current.
218
 
@return precedessor node to current that is passed in */
219
 
UNIV_INTERN
220
 
const ib_rbt_node_t*
221
 
rbt_prev(
222
 
/*=====*/
223
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
224
 
        const ib_rbt_node_t*                    /* in: current node */
225
 
                        current);
226
 
/**********************************************************************//**
227
 
Find the node that has the lowest key that is >= key.
228
 
@return node that satisfies the lower bound constraint or NULL */
229
 
UNIV_INTERN
230
 
const ib_rbt_node_t*
231
 
rbt_lower_bound(
232
 
/*============*/
233
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
234
 
        const void*     key);                   /*!< in: key to search */
235
 
/**********************************************************************//**
236
 
Find the node that has the greatest key that is <= key.
237
 
@return node that satisifies the upper bound constraint or NULL */
238
 
UNIV_INTERN
239
 
const ib_rbt_node_t*
240
 
rbt_upper_bound(
241
 
/*============*/
242
 
        const ib_rbt_t* tree,                   /*!< in: rb tree */
243
 
        const void*     key);                   /*!< in: key to search */
244
 
/**********************************************************************//**
245
 
Search for the key, a node will be retuned in parent.last, whether it
246
 
was found or not. If not found then parent.last will contain the
247
 
parent node for the possibly new key otherwise the matching node.
248
 
@return result of last comparison */
249
 
UNIV_INTERN
250
 
int
251
 
rbt_search(
252
 
/*=======*/
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
 
/**********************************************************************//**
257
 
Search for the key, a node will be retuned in parent.last, whether it
258
 
was found or not. If not found then parent.last will contain the
259
 
parent node for the possibly new key otherwise the matching node.
260
 
@return result of last comparison */
261
 
UNIV_INTERN
262
 
int
263
 
rbt_search_cmp(
264
 
/*===========*/
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
 
/**********************************************************************//**
270
 
Clear the tree, deletes (and free's) all the nodes. */
271
 
UNIV_INTERN
272
 
void
273
 
rbt_clear(
274
 
/*======*/
275
 
        ib_rbt_t*       tree);                  /*!< in: rb tree */
276
 
/**********************************************************************//**
277
 
Merge the node from dst into src. Return the number of nodes merged.
278
 
@return no. of recs merged */
279
 
UNIV_INTERN
280
 
ulint
281
 
rbt_merge_uniq(
282
 
/*===========*/
283
 
        ib_rbt_t*       dst,                    /*!< in: dst rb tree */
284
 
        const ib_rbt_t* src);                   /*!< in: src rb tree */
285
 
/**********************************************************************//**
286
 
Merge the node from dst into src. Return the number of nodes merged.
287
 
Delete the nodes from src after copying node to dst. As a side effect
288
 
the duplicates will be left untouched in the src, since we don't support
289
 
duplicates (yet). NOTE: src and dst must be similar, the function doesn't
290
 
check for this condition (yet).
291
 
@return no. of recs merged */
292
 
UNIV_INTERN
293
 
ulint
294
 
rbt_merge_uniq_destructive(
295
 
/*=======================*/
296
 
        ib_rbt_t*       dst,                    /*!< in: dst rb tree */
297
 
        ib_rbt_t*       src);                   /*!< in: src rb tree */
298
 
/**********************************************************************//**
299
 
Verify the integrity of the RB tree. For debugging. 0 failure else height
300
 
of tree (in count of black nodes).
301
 
@return TRUE if OK FALSE if tree invalid. */
302
 
UNIV_INTERN
303
 
ibool
304
 
rbt_validate(
305
 
/*=========*/
306
 
        const ib_rbt_t* tree);                  /*!< in: tree to validate */
307
 
/**********************************************************************//**
308
 
Iterate over the tree in depth first order. */
309
 
UNIV_INTERN
310
 
void
311
 
rbt_print(
312
 
/*======*/
313
 
        const ib_rbt_t*         tree,           /*!< in: tree to traverse */
314
 
        ib_rbt_print_node       print);         /*!< in: print function */
315
 
 
316
 
#endif /* INNOBASE_UT0RBT_H */