MySQL 5.6.14 Source Code Document
Main Page
Related Pages
Modules
Namespaces
Classes
Files
Examples
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Groups
Pages
tree.h
1
/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
2
/*
3
* Copyright 2002 Niels Provos <provos@citi.umich.edu>
4
* All rights reserved.
5
*
6
* Redistribution and use in source and binary forms, with or without
7
* modification, are permitted provided that the following conditions
8
* are met:
9
* 1. Redistributions of source code must retain the above copyright
10
* notice, this list of conditions and the following disclaimer.
11
* 2. Redistributions in binary form must reproduce the above copyright
12
* notice, this list of conditions and the following disclaimer in the
13
* documentation and/or other materials provided with the distribution.
14
*
15
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
*/
26
27
#ifndef _SYS_TREE_H_
28
#define _SYS_TREE_H_
29
30
/*
31
* This file defines data structures for different types of trees:
32
* splay trees and red-black trees.
33
*
34
* A splay tree is a self-organizing data structure. Every operation
35
* on the tree causes a splay to happen. The splay moves the requested
36
* node to the root of the tree and partly rebalances it.
37
*
38
* This has the benefit that request locality causes faster lookups as
39
* the requested nodes move to the top of the tree. On the other hand,
40
* every lookup causes memory writes.
41
*
42
* The Balance Theorem bounds the total access time for m operations
43
* and n inserts on an initially empty tree as O((m + n)lg n). The
44
* amortized cost for a sequence of m accesses to a splay tree is O(lg n);
45
*
46
* A red-black tree is a binary search tree with the node color as an
47
* extra attribute. It fulfills a set of conditions:
48
* - every search path from the root to a leaf consists of the
49
* same number of black nodes,
50
* - each red node (except for the root) has a black parent,
51
* - each leaf node is black.
52
*
53
* Every operation on a red-black tree is bounded as O(lg n).
54
* The maximum height of a red-black tree is 2lg (n+1).
55
*/
56
57
#define SPLAY_HEAD(name, type) \
58
struct name { \
59
struct type *sph_root;
/* root of the tree */
\
60
}
61
62
#define SPLAY_INITIALIZER(root) \
63
{ NULL }
64
65
#define SPLAY_INIT(root) do { \
66
(root)->sph_root = NULL; \
67
} while (0)
68
69
#define SPLAY_ENTRY(type) \
70
struct { \
71
struct type *spe_left;
/* left element */
\
72
struct type *spe_right;
/* right element */
\
73
}
74
75
#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
76
#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
77
#define SPLAY_ROOT(head) (head)->sph_root
78
#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
79
80
/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
81
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
82
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
83
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
84
(head)->sph_root = tmp; \
85
} while (0)
86
87
#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
88
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
89
SPLAY_LEFT(tmp, field) = (head)->sph_root; \
90
(head)->sph_root = tmp; \
91
} while (0)
92
93
#define SPLAY_LINKLEFT(head, tmp, field) do { \
94
SPLAY_LEFT(tmp, field) = (head)->sph_root; \
95
tmp = (head)->sph_root; \
96
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
97
} while (0)
98
99
#define SPLAY_LINKRIGHT(head, tmp, field) do { \
100
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
101
tmp = (head)->sph_root; \
102
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
103
} while (0)
104
105
#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
106
SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
107
SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
108
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
109
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
110
} while (0)
111
112
/* Generates prototypes and inline functions */
113
114
#define SPLAY_PROTOTYPE(name, type, field, cmp) \
115
void name##_SPLAY(struct name *, struct type *); \
116
void name##_SPLAY_MINMAX(struct name *, int); \
117
struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
118
struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
119
\
120
/* Finds the node with the same key as elm */
\
121
static __inline struct type * \
122
name##_SPLAY_FIND(struct name *head, struct type *elm) \
123
{ \
124
if (SPLAY_EMPTY(head)) \
125
return(NULL); \
126
name##_SPLAY(head, elm); \
127
if ((cmp)(elm, (head)->sph_root) == 0) \
128
return (head->sph_root); \
129
return (NULL); \
130
} \
131
\
132
static __inline struct type * \
133
name##_SPLAY_NEXT(struct name *head, struct type *elm) \
134
{ \
135
name##_SPLAY(head, elm); \
136
if (SPLAY_RIGHT(elm, field) != NULL) { \
137
elm = SPLAY_RIGHT(elm, field); \
138
while (SPLAY_LEFT(elm, field) != NULL) { \
139
elm = SPLAY_LEFT(elm, field); \
140
} \
141
} else \
142
elm = NULL; \
143
return (elm); \
144
} \
145
\
146
static __inline struct type * \
147
name##_SPLAY_MIN_MAX(struct name *head, int val) \
148
{ \
149
name##_SPLAY_MINMAX(head, val); \
150
return (SPLAY_ROOT(head)); \
151
}
152
153
/* Main splay operation.
154
* Moves node close to the key of elm to top
155
*/
156
#define SPLAY_GENERATE(name, type, field, cmp) \
157
struct type * \
158
name##_SPLAY_INSERT(struct name *head, struct type *elm) \
159
{ \
160
if (SPLAY_EMPTY(head)) { \
161
SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
162
} else { \
163
int __comp; \
164
name##_SPLAY(head, elm); \
165
__comp = (cmp)(elm, (head)->sph_root); \
166
if(__comp < 0) { \
167
SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
168
SPLAY_RIGHT(elm, field) = (head)->sph_root; \
169
SPLAY_LEFT((head)->sph_root, field) = NULL; \
170
} else if (__comp > 0) { \
171
SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
172
SPLAY_LEFT(elm, field) = (head)->sph_root; \
173
SPLAY_RIGHT((head)->sph_root, field) = NULL; \
174
} else \
175
return ((head)->sph_root); \
176
} \
177
(head)->sph_root = (elm); \
178
return (NULL); \
179
} \
180
\
181
struct type * \
182
name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
183
{ \
184
struct type *__tmp; \
185
if (SPLAY_EMPTY(head)) \
186
return (NULL); \
187
name##_SPLAY(head, elm); \
188
if ((cmp)(elm, (head)->sph_root) == 0) { \
189
if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
190
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
191
} else { \
192
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
193
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
194
name##_SPLAY(head, elm); \
195
SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
196
} \
197
return (elm); \
198
} \
199
return (NULL); \
200
} \
201
\
202
void \
203
name##_SPLAY(struct name *head, struct type *elm) \
204
{ \
205
struct type __node, *__left, *__right, *__tmp; \
206
int __comp; \
207
\
208
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
209
__left = __right = &__node; \
210
\
211
while ((__comp = (cmp)(elm, (head)->sph_root))) { \
212
if (__comp < 0) { \
213
__tmp = SPLAY_LEFT((head)->sph_root, field); \
214
if (__tmp == NULL) \
215
break; \
216
if ((cmp)(elm, __tmp) < 0){ \
217
SPLAY_ROTATE_RIGHT(head, __tmp, field); \
218
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
219
break; \
220
} \
221
SPLAY_LINKLEFT(head, __right, field); \
222
} else if (__comp > 0) { \
223
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
224
if (__tmp == NULL) \
225
break; \
226
if ((cmp)(elm, __tmp) > 0){ \
227
SPLAY_ROTATE_LEFT(head, __tmp, field); \
228
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
229
break; \
230
} \
231
SPLAY_LINKRIGHT(head, __left, field); \
232
} \
233
} \
234
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
235
} \
236
\
237
/* Splay with either the minimum or the maximum element \
238
* Used to find minimum or maximum element in tree. \
239
*/
\
240
void name##_SPLAY_MINMAX(struct name *head, int __comp) \
241
{ \
242
struct type __node, *__left, *__right, *__tmp; \
243
\
244
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
245
__left = __right = &__node; \
246
\
247
while (1) { \
248
if (__comp < 0) { \
249
__tmp = SPLAY_LEFT((head)->sph_root, field); \
250
if (__tmp == NULL) \
251
break; \
252
if (__comp < 0){ \
253
SPLAY_ROTATE_RIGHT(head, __tmp, field); \
254
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
255
break; \
256
} \
257
SPLAY_LINKLEFT(head, __right, field); \
258
} else if (__comp > 0) { \
259
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
260
if (__tmp == NULL) \
261
break; \
262
if (__comp > 0) { \
263
SPLAY_ROTATE_LEFT(head, __tmp, field); \
264
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
265
break; \
266
} \
267
SPLAY_LINKRIGHT(head, __left, field); \
268
} \
269
} \
270
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
271
}
272
273
#define SPLAY_NEGINF -1
274
#define SPLAY_INF 1
275
276
#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
277
#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
278
#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
279
#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
280
#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
281
: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
282
#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
283
: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
284
285
#define SPLAY_FOREACH(x, name, head) \
286
for ((x) = SPLAY_MIN(name, head); \
287
(x) != NULL; \
288
(x) = SPLAY_NEXT(name, head, x))
289
290
/* Macros that define a red-back tree */
291
#define RB_HEAD(name, type) \
292
struct name { \
293
struct type *rbh_root;
/* root of the tree */
\
294
}
295
296
#define RB_INITIALIZER(root) \
297
{ NULL }
298
299
#define RB_INIT(root) do { \
300
(root)->rbh_root = NULL; \
301
} while (0)
302
303
#define RB_BLACK 0
304
#define RB_RED 1
305
#define RB_ENTRY(type) \
306
struct { \
307
struct type *rbe_left;
/* left element */
\
308
struct type *rbe_right;
/* right element */
\
309
struct type *rbe_parent;
/* parent element */
\
310
int rbe_color;
/* node color */
\
311
}
312
313
#define RB_LEFT(elm, field) (elm)->field.rbe_left
314
#define RB_RIGHT(elm, field) (elm)->field.rbe_right
315
#define RB_PARENT(elm, field) (elm)->field.rbe_parent
316
#define RB_COLOR(elm, field) (elm)->field.rbe_color
317
#define RB_ROOT(head) (head)->rbh_root
318
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
319
320
#define RB_SET(elm, parent, field) do { \
321
RB_PARENT(elm, field) = parent; \
322
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
323
RB_COLOR(elm, field) = RB_RED; \
324
} while (0)
325
326
#define RB_SET_BLACKRED(black, red, field) do { \
327
RB_COLOR(black, field) = RB_BLACK; \
328
RB_COLOR(red, field) = RB_RED; \
329
} while (0)
330
331
#ifndef RB_AUGMENT
332
#define RB_AUGMENT(x)
333
#endif
334
335
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
336
(tmp) = RB_RIGHT(elm, field); \
337
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
338
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
339
} \
340
RB_AUGMENT(elm); \
341
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
342
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
343
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
344
else \
345
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
346
} else \
347
(head)->rbh_root = (tmp); \
348
RB_LEFT(tmp, field) = (elm); \
349
RB_PARENT(elm, field) = (tmp); \
350
RB_AUGMENT(tmp); \
351
if ((RB_PARENT(tmp, field))) \
352
RB_AUGMENT(RB_PARENT(tmp, field)); \
353
} while (0)
354
355
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
356
(tmp) = RB_LEFT(elm, field); \
357
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
358
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
359
} \
360
RB_AUGMENT(elm); \
361
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
362
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
363
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
364
else \
365
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
366
} else \
367
(head)->rbh_root = (tmp); \
368
RB_RIGHT(tmp, field) = (elm); \
369
RB_PARENT(elm, field) = (tmp); \
370
RB_AUGMENT(tmp); \
371
if ((RB_PARENT(tmp, field))) \
372
RB_AUGMENT(RB_PARENT(tmp, field)); \
373
} while (0)
374
375
/* Generates prototypes and inline functions */
376
#define RB_PROTOTYPE(name, type, field, cmp) \
377
void name##_RB_INSERT_COLOR(struct name *, struct type *); \
378
void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
379
struct type *name##_RB_REMOVE(struct name *, struct type *); \
380
struct type *name##_RB_INSERT(struct name *, struct type *); \
381
struct type *name##_RB_FIND(struct name *, struct type *); \
382
struct type *name##_RB_NEXT(struct type *); \
383
struct type *name##_RB_MINMAX(struct name *, int); \
384
\
385
386
/* Main rb operation.
387
* Moves node close to the key of elm to top
388
*/
389
#define RB_GENERATE(name, type, field, cmp) \
390
void \
391
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
392
{ \
393
struct type *parent, *gparent, *tmp; \
394
while ((parent = RB_PARENT(elm, field)) && \
395
RB_COLOR(parent, field) == RB_RED) { \
396
gparent = RB_PARENT(parent, field); \
397
if (parent == RB_LEFT(gparent, field)) { \
398
tmp = RB_RIGHT(gparent, field); \
399
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
400
RB_COLOR(tmp, field) = RB_BLACK; \
401
RB_SET_BLACKRED(parent, gparent, field);\
402
elm = gparent; \
403
continue; \
404
} \
405
if (RB_RIGHT(parent, field) == elm) { \
406
RB_ROTATE_LEFT(head, parent, tmp, field);\
407
tmp = parent; \
408
parent = elm; \
409
elm = tmp; \
410
} \
411
RB_SET_BLACKRED(parent, gparent, field); \
412
RB_ROTATE_RIGHT(head, gparent, tmp, field); \
413
} else { \
414
tmp = RB_LEFT(gparent, field); \
415
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
416
RB_COLOR(tmp, field) = RB_BLACK; \
417
RB_SET_BLACKRED(parent, gparent, field);\
418
elm = gparent; \
419
continue; \
420
} \
421
if (RB_LEFT(parent, field) == elm) { \
422
RB_ROTATE_RIGHT(head, parent, tmp, field);\
423
tmp = parent; \
424
parent = elm; \
425
elm = tmp; \
426
} \
427
RB_SET_BLACKRED(parent, gparent, field); \
428
RB_ROTATE_LEFT(head, gparent, tmp, field); \
429
} \
430
} \
431
RB_COLOR(head->rbh_root, field) = RB_BLACK; \
432
} \
433
\
434
void \
435
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
436
{ \
437
struct type *tmp; \
438
while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
439
elm != RB_ROOT(head)) { \
440
if (RB_LEFT(parent, field) == elm) { \
441
tmp = RB_RIGHT(parent, field); \
442
if (RB_COLOR(tmp, field) == RB_RED) { \
443
RB_SET_BLACKRED(tmp, parent, field); \
444
RB_ROTATE_LEFT(head, parent, tmp, field);\
445
tmp = RB_RIGHT(parent, field); \
446
} \
447
if ((RB_LEFT(tmp, field) == NULL || \
448
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
449
(RB_RIGHT(tmp, field) == NULL || \
450
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
451
RB_COLOR(tmp, field) = RB_RED; \
452
elm = parent; \
453
parent = RB_PARENT(elm, field); \
454
} else { \
455
if (RB_RIGHT(tmp, field) == NULL || \
456
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
457
struct type *oleft; \
458
if ((oleft = RB_LEFT(tmp, field)))\
459
RB_COLOR(oleft, field) = RB_BLACK;\
460
RB_COLOR(tmp, field) = RB_RED; \
461
RB_ROTATE_RIGHT(head, tmp, oleft, field);\
462
tmp = RB_RIGHT(parent, field); \
463
} \
464
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
465
RB_COLOR(parent, field) = RB_BLACK; \
466
if (RB_RIGHT(tmp, field)) \
467
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
468
RB_ROTATE_LEFT(head, parent, tmp, field);\
469
elm = RB_ROOT(head); \
470
break; \
471
} \
472
} else { \
473
tmp = RB_LEFT(parent, field); \
474
if (RB_COLOR(tmp, field) == RB_RED) { \
475
RB_SET_BLACKRED(tmp, parent, field); \
476
RB_ROTATE_RIGHT(head, parent, tmp, field);\
477
tmp = RB_LEFT(parent, field); \
478
} \
479
if ((RB_LEFT(tmp, field) == NULL || \
480
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
481
(RB_RIGHT(tmp, field) == NULL || \
482
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
483
RB_COLOR(tmp, field) = RB_RED; \
484
elm = parent; \
485
parent = RB_PARENT(elm, field); \
486
} else { \
487
if (RB_LEFT(tmp, field) == NULL || \
488
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
489
struct type *oright; \
490
if ((oright = RB_RIGHT(tmp, field)))\
491
RB_COLOR(oright, field) = RB_BLACK;\
492
RB_COLOR(tmp, field) = RB_RED; \
493
RB_ROTATE_LEFT(head, tmp, oright, field);\
494
tmp = RB_LEFT(parent, field); \
495
} \
496
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
497
RB_COLOR(parent, field) = RB_BLACK; \
498
if (RB_LEFT(tmp, field)) \
499
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
500
RB_ROTATE_RIGHT(head, parent, tmp, field);\
501
elm = RB_ROOT(head); \
502
break; \
503
} \
504
} \
505
} \
506
if (elm) \
507
RB_COLOR(elm, field) = RB_BLACK; \
508
} \
509
\
510
struct type * \
511
name##_RB_REMOVE(struct name *head, struct type *elm) \
512
{ \
513
struct type *child, *parent, *old = elm; \
514
int color; \
515
if (RB_LEFT(elm, field) == NULL) \
516
child = RB_RIGHT(elm, field); \
517
else if (RB_RIGHT(elm, field) == NULL) \
518
child = RB_LEFT(elm, field); \
519
else { \
520
struct type *left; \
521
elm = RB_RIGHT(elm, field); \
522
while ((left = RB_LEFT(elm, field))) \
523
elm = left; \
524
child = RB_RIGHT(elm, field); \
525
parent = RB_PARENT(elm, field); \
526
color = RB_COLOR(elm, field); \
527
if (child) \
528
RB_PARENT(child, field) = parent; \
529
if (parent) { \
530
if (RB_LEFT(parent, field) == elm) \
531
RB_LEFT(parent, field) = child; \
532
else \
533
RB_RIGHT(parent, field) = child; \
534
RB_AUGMENT(parent); \
535
} else \
536
RB_ROOT(head) = child; \
537
if (RB_PARENT(elm, field) == old) \
538
parent = elm; \
539
(elm)->field = (old)->field; \
540
if (RB_PARENT(old, field)) { \
541
if (RB_LEFT(RB_PARENT(old, field), field) == old)\
542
RB_LEFT(RB_PARENT(old, field), field) = elm;\
543
else \
544
RB_RIGHT(RB_PARENT(old, field), field) = elm;\
545
RB_AUGMENT(RB_PARENT(old, field)); \
546
} else \
547
RB_ROOT(head) = elm; \
548
RB_PARENT(RB_LEFT(old, field), field) = elm; \
549
if (RB_RIGHT(old, field)) \
550
RB_PARENT(RB_RIGHT(old, field), field) = elm; \
551
if (parent) { \
552
left = parent; \
553
do { \
554
RB_AUGMENT(left); \
555
} while ((left = RB_PARENT(left, field))); \
556
} \
557
goto color; \
558
} \
559
parent = RB_PARENT(elm, field); \
560
color = RB_COLOR(elm, field); \
561
if (child) \
562
RB_PARENT(child, field) = parent; \
563
if (parent) { \
564
if (RB_LEFT(parent, field) == elm) \
565
RB_LEFT(parent, field) = child; \
566
else \
567
RB_RIGHT(parent, field) = child; \
568
RB_AUGMENT(parent); \
569
} else \
570
RB_ROOT(head) = child; \
571
color: \
572
if (color == RB_BLACK) \
573
name##_RB_REMOVE_COLOR(head, parent, child); \
574
return (old); \
575
} \
576
\
577
/* Inserts a node into the RB tree */
\
578
struct type * \
579
name##_RB_INSERT(struct name *head, struct type *elm) \
580
{ \
581
struct type *tmp; \
582
struct type *parent = NULL; \
583
int comp = 0; \
584
tmp = RB_ROOT(head); \
585
while (tmp) { \
586
parent = tmp; \
587
comp = (cmp)(elm, parent); \
588
if (comp < 0) \
589
tmp = RB_LEFT(tmp, field); \
590
else if (comp > 0) \
591
tmp = RB_RIGHT(tmp, field); \
592
else \
593
return (tmp); \
594
} \
595
RB_SET(elm, parent, field); \
596
if (parent != NULL) { \
597
if (comp < 0) \
598
RB_LEFT(parent, field) = elm; \
599
else \
600
RB_RIGHT(parent, field) = elm; \
601
RB_AUGMENT(parent); \
602
} else \
603
RB_ROOT(head) = elm; \
604
name##_RB_INSERT_COLOR(head, elm); \
605
return (NULL); \
606
} \
607
\
608
/* Finds the node with the same key as elm */
\
609
struct type * \
610
name##_RB_FIND(struct name *head, struct type *elm) \
611
{ \
612
struct type *tmp = RB_ROOT(head); \
613
int comp; \
614
while (tmp) { \
615
comp = cmp(elm, tmp); \
616
if (comp < 0) \
617
tmp = RB_LEFT(tmp, field); \
618
else if (comp > 0) \
619
tmp = RB_RIGHT(tmp, field); \
620
else \
621
return (tmp); \
622
} \
623
return (NULL); \
624
} \
625
\
626
struct type * \
627
name##_RB_NEXT(struct type *elm) \
628
{ \
629
if (RB_RIGHT(elm, field)) { \
630
elm = RB_RIGHT(elm, field); \
631
while (RB_LEFT(elm, field)) \
632
elm = RB_LEFT(elm, field); \
633
} else { \
634
if (RB_PARENT(elm, field) && \
635
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
636
elm = RB_PARENT(elm, field); \
637
else { \
638
while (RB_PARENT(elm, field) && \
639
(elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
640
elm = RB_PARENT(elm, field); \
641
elm = RB_PARENT(elm, field); \
642
} \
643
} \
644
return (elm); \
645
} \
646
\
647
struct type * \
648
name##_RB_MINMAX(struct name *head, int val) \
649
{ \
650
struct type *tmp = RB_ROOT(head); \
651
struct type *parent = NULL; \
652
while (tmp) { \
653
parent = tmp; \
654
if (val < 0) \
655
tmp = RB_LEFT(tmp, field); \
656
else \
657
tmp = RB_RIGHT(tmp, field); \
658
} \
659
return (parent); \
660
}
661
662
#define RB_NEGINF -1
663
#define RB_INF 1
664
665
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
666
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
667
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
668
#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
669
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
670
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
671
672
#define RB_FOREACH(x, name, head) \
673
for ((x) = RB_MIN(name, head); \
674
(x) != NULL; \
675
(x) = name##_RB_NEXT(x))
676
677
#endif
/* _SYS_TREE_H_ */
678
/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
679
/*
680
* Copyright 2002 Niels Provos <provos@citi.umich.edu>
681
* All rights reserved.
682
*
683
* Redistribution and use in source and binary forms, with or without
684
* modification, are permitted provided that the following conditions
685
* are met:
686
* 1. Redistributions of source code must retain the above copyright
687
* notice, this list of conditions and the following disclaimer.
688
* 2. Redistributions in binary form must reproduce the above copyright
689
* notice, this list of conditions and the following disclaimer in the
690
* documentation and/or other materials provided with the distribution.
691
*
692
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
693
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
694
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
695
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
696
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
697
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
698
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
699
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
700
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
701
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
702
*/
703
704
#ifndef _SYS_TREE_H_
705
#define _SYS_TREE_H_
706
707
/*
708
* This file defines data structures for different types of trees:
709
* splay trees and red-black trees.
710
*
711
* A splay tree is a self-organizing data structure. Every operation
712
* on the tree causes a splay to happen. The splay moves the requested
713
* node to the root of the tree and partly rebalances it.
714
*
715
* This has the benefit that request locality causes faster lookups as
716
* the requested nodes move to the top of the tree. On the other hand,
717
* every lookup causes memory writes.
718
*
719
* The Balance Theorem bounds the total access time for m operations
720
* and n inserts on an initially empty tree as O((m + n)lg n). The
721
* amortized cost for a sequence of m accesses to a splay tree is O(lg n);
722
*
723
* A red-black tree is a binary search tree with the node color as an
724
* extra attribute. It fulfills a set of conditions:
725
* - every search path from the root to a leaf consists of the
726
* same number of black nodes,
727
* - each red node (except for the root) has a black parent,
728
* - each leaf node is black.
729
*
730
* Every operation on a red-black tree is bounded as O(lg n).
731
* The maximum height of a red-black tree is 2lg (n+1).
732
*/
733
734
#define SPLAY_HEAD(name, type) \
735
struct name { \
736
struct type *sph_root;
/* root of the tree */
\
737
}
738
739
#define SPLAY_INITIALIZER(root) \
740
{ NULL }
741
742
#define SPLAY_INIT(root) do { \
743
(root)->sph_root = NULL; \
744
} while (0)
745
746
#define SPLAY_ENTRY(type) \
747
struct { \
748
struct type *spe_left;
/* left element */
\
749
struct type *spe_right;
/* right element */
\
750
}
751
752
#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
753
#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
754
#define SPLAY_ROOT(head) (head)->sph_root
755
#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
756
757
/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
758
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
759
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
760
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
761
(head)->sph_root = tmp; \
762
} while (0)
763
764
#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
765
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
766
SPLAY_LEFT(tmp, field) = (head)->sph_root; \
767
(head)->sph_root = tmp; \
768
} while (0)
769
770
#define SPLAY_LINKLEFT(head, tmp, field) do { \
771
SPLAY_LEFT(tmp, field) = (head)->sph_root; \
772
tmp = (head)->sph_root; \
773
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
774
} while (0)
775
776
#define SPLAY_LINKRIGHT(head, tmp, field) do { \
777
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
778
tmp = (head)->sph_root; \
779
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
780
} while (0)
781
782
#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
783
SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
784
SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
785
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
786
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
787
} while (0)
788
789
/* Generates prototypes and inline functions */
790
791
#define SPLAY_PROTOTYPE(name, type, field, cmp) \
792
void name##_SPLAY(struct name *, struct type *); \
793
void name##_SPLAY_MINMAX(struct name *, int); \
794
struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
795
struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
796
\
797
/* Finds the node with the same key as elm */
\
798
static __inline struct type * \
799
name##_SPLAY_FIND(struct name *head, struct type *elm) \
800
{ \
801
if (SPLAY_EMPTY(head)) \
802
return(NULL); \
803
name##_SPLAY(head, elm); \
804
if ((cmp)(elm, (head)->sph_root) == 0) \
805
return (head->sph_root); \
806
return (NULL); \
807
} \
808
\
809
static __inline struct type * \
810
name##_SPLAY_NEXT(struct name *head, struct type *elm) \
811
{ \
812
name##_SPLAY(head, elm); \
813
if (SPLAY_RIGHT(elm, field) != NULL) { \
814
elm = SPLAY_RIGHT(elm, field); \
815
while (SPLAY_LEFT(elm, field) != NULL) { \
816
elm = SPLAY_LEFT(elm, field); \
817
} \
818
} else \
819
elm = NULL; \
820
return (elm); \
821
} \
822
\
823
static __inline struct type * \
824
name##_SPLAY_MIN_MAX(struct name *head, int val) \
825
{ \
826
name##_SPLAY_MINMAX(head, val); \
827
return (SPLAY_ROOT(head)); \
828
}
829
830
/* Main splay operation.
831
* Moves node close to the key of elm to top
832
*/
833
#define SPLAY_GENERATE(name, type, field, cmp) \
834
struct type * \
835
name##_SPLAY_INSERT(struct name *head, struct type *elm) \
836
{ \
837
if (SPLAY_EMPTY(head)) { \
838
SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
839
} else { \
840
int __comp; \
841
name##_SPLAY(head, elm); \
842
__comp = (cmp)(elm, (head)->sph_root); \
843
if(__comp < 0) { \
844
SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
845
SPLAY_RIGHT(elm, field) = (head)->sph_root; \
846
SPLAY_LEFT((head)->sph_root, field) = NULL; \
847
} else if (__comp > 0) { \
848
SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
849
SPLAY_LEFT(elm, field) = (head)->sph_root; \
850
SPLAY_RIGHT((head)->sph_root, field) = NULL; \
851
} else \
852
return ((head)->sph_root); \
853
} \
854
(head)->sph_root = (elm); \
855
return (NULL); \
856
} \
857
\
858
struct type * \
859
name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
860
{ \
861
struct type *__tmp; \
862
if (SPLAY_EMPTY(head)) \
863
return (NULL); \
864
name##_SPLAY(head, elm); \
865
if ((cmp)(elm, (head)->sph_root) == 0) { \
866
if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
867
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
868
} else { \
869
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
870
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
871
name##_SPLAY(head, elm); \
872
SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
873
} \
874
return (elm); \
875
} \
876
return (NULL); \
877
} \
878
\
879
void \
880
name##_SPLAY(struct name *head, struct type *elm) \
881
{ \
882
struct type __node, *__left, *__right, *__tmp; \
883
int __comp; \
884
\
885
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
886
__left = __right = &__node; \
887
\
888
while ((__comp = (cmp)(elm, (head)->sph_root))) { \
889
if (__comp < 0) { \
890
__tmp = SPLAY_LEFT((head)->sph_root, field); \
891
if (__tmp == NULL) \
892
break; \
893
if ((cmp)(elm, __tmp) < 0){ \
894
SPLAY_ROTATE_RIGHT(head, __tmp, field); \
895
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
896
break; \
897
} \
898
SPLAY_LINKLEFT(head, __right, field); \
899
} else if (__comp > 0) { \
900
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
901
if (__tmp == NULL) \
902
break; \
903
if ((cmp)(elm, __tmp) > 0){ \
904
SPLAY_ROTATE_LEFT(head, __tmp, field); \
905
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
906
break; \
907
} \
908
SPLAY_LINKRIGHT(head, __left, field); \
909
} \
910
} \
911
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
912
} \
913
\
914
/* Splay with either the minimum or the maximum element \
915
* Used to find minimum or maximum element in tree. \
916
*/
\
917
void name##_SPLAY_MINMAX(struct name *head, int __comp) \
918
{ \
919
struct type __node, *__left, *__right, *__tmp; \
920
\
921
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
922
__left = __right = &__node; \
923
\
924
while (1) { \
925
if (__comp < 0) { \
926
__tmp = SPLAY_LEFT((head)->sph_root, field); \
927
if (__tmp == NULL) \
928
break; \
929
if (__comp < 0){ \
930
SPLAY_ROTATE_RIGHT(head, __tmp, field); \
931
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
932
break; \
933
} \
934
SPLAY_LINKLEFT(head, __right, field); \
935
} else if (__comp > 0) { \
936
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
937
if (__tmp == NULL) \
938
break; \
939
if (__comp > 0) { \
940
SPLAY_ROTATE_LEFT(head, __tmp, field); \
941
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
942
break; \
943
} \
944
SPLAY_LINKRIGHT(head, __left, field); \
945
} \
946
} \
947
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
948
}
949
950
#define SPLAY_NEGINF -1
951
#define SPLAY_INF 1
952
953
#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
954
#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
955
#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
956
#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
957
#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
958
: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
959
#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
960
: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
961
962
#define SPLAY_FOREACH(x, name, head) \
963
for ((x) = SPLAY_MIN(name, head); \
964
(x) != NULL; \
965
(x) = SPLAY_NEXT(name, head, x))
966
967
/* Macros that define a red-back tree */
968
#define RB_HEAD(name, type) \
969
struct name { \
970
struct type *rbh_root;
/* root of the tree */
\
971
}
972
973
#define RB_INITIALIZER(root) \
974
{ NULL }
975
976
#define RB_INIT(root) do { \
977
(root)->rbh_root = NULL; \
978
} while (0)
979
980
#define RB_BLACK 0
981
#define RB_RED 1
982
#define RB_ENTRY(type) \
983
struct { \
984
struct type *rbe_left;
/* left element */
\
985
struct type *rbe_right;
/* right element */
\
986
struct type *rbe_parent;
/* parent element */
\
987
int rbe_color;
/* node color */
\
988
}
989
990
#define RB_LEFT(elm, field) (elm)->field.rbe_left
991
#define RB_RIGHT(elm, field) (elm)->field.rbe_right
992
#define RB_PARENT(elm, field) (elm)->field.rbe_parent
993
#define RB_COLOR(elm, field) (elm)->field.rbe_color
994
#define RB_ROOT(head) (head)->rbh_root
995
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
996
997
#define RB_SET(elm, parent, field) do { \
998
RB_PARENT(elm, field) = parent; \
999
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
1000
RB_COLOR(elm, field) = RB_RED; \
1001
} while (0)
1002
1003
#define RB_SET_BLACKRED(black, red, field) do { \
1004
RB_COLOR(black, field) = RB_BLACK; \
1005
RB_COLOR(red, field) = RB_RED; \
1006
} while (0)
1007
1008
#ifndef RB_AUGMENT
1009
#define RB_AUGMENT(x)
1010
#endif
1011
1012
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
1013
(tmp) = RB_RIGHT(elm, field); \
1014
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
1015
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
1016
} \
1017
RB_AUGMENT(elm); \
1018
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1019
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1020
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1021
else \
1022
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1023
} else \
1024
(head)->rbh_root = (tmp); \
1025
RB_LEFT(tmp, field) = (elm); \
1026
RB_PARENT(elm, field) = (tmp); \
1027
RB_AUGMENT(tmp); \
1028
if ((RB_PARENT(tmp, field))) \
1029
RB_AUGMENT(RB_PARENT(tmp, field)); \
1030
} while (0)
1031
1032
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
1033
(tmp) = RB_LEFT(elm, field); \
1034
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
1035
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
1036
} \
1037
RB_AUGMENT(elm); \
1038
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1039
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1040
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1041
else \
1042
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1043
} else \
1044
(head)->rbh_root = (tmp); \
1045
RB_RIGHT(tmp, field) = (elm); \
1046
RB_PARENT(elm, field) = (tmp); \
1047
RB_AUGMENT(tmp); \
1048
if ((RB_PARENT(tmp, field))) \
1049
RB_AUGMENT(RB_PARENT(tmp, field)); \
1050
} while (0)
1051
1052
/* Generates prototypes and inline functions */
1053
#define RB_PROTOTYPE(name, type, field, cmp) \
1054
void name##_RB_INSERT_COLOR(struct name *, struct type *); \
1055
void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
1056
struct type *name##_RB_REMOVE(struct name *, struct type *); \
1057
struct type *name##_RB_INSERT(struct name *, struct type *); \
1058
struct type *name##_RB_FIND(struct name *, struct type *); \
1059
struct type *name##_RB_NEXT(struct type *); \
1060
struct type *name##_RB_MINMAX(struct name *, int); \
1061
\
1062
1063
/* Main rb operation.
1064
* Moves node close to the key of elm to top
1065
*/
1066
#define RB_GENERATE(name, type, field, cmp) \
1067
void \
1068
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
1069
{ \
1070
struct type *parent, *gparent, *tmp; \
1071
while ((parent = RB_PARENT(elm, field)) && \
1072
RB_COLOR(parent, field) == RB_RED) { \
1073
gparent = RB_PARENT(parent, field); \
1074
if (parent == RB_LEFT(gparent, field)) { \
1075
tmp = RB_RIGHT(gparent, field); \
1076
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1077
RB_COLOR(tmp, field) = RB_BLACK; \
1078
RB_SET_BLACKRED(parent, gparent, field);\
1079
elm = gparent; \
1080
continue; \
1081
} \
1082
if (RB_RIGHT(parent, field) == elm) { \
1083
RB_ROTATE_LEFT(head, parent, tmp, field);\
1084
tmp = parent; \
1085
parent = elm; \
1086
elm = tmp; \
1087
} \
1088
RB_SET_BLACKRED(parent, gparent, field); \
1089
RB_ROTATE_RIGHT(head, gparent, tmp, field); \
1090
} else { \
1091
tmp = RB_LEFT(gparent, field); \
1092
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1093
RB_COLOR(tmp, field) = RB_BLACK; \
1094
RB_SET_BLACKRED(parent, gparent, field);\
1095
elm = gparent; \
1096
continue; \
1097
} \
1098
if (RB_LEFT(parent, field) == elm) { \
1099
RB_ROTATE_RIGHT(head, parent, tmp, field);\
1100
tmp = parent; \
1101
parent = elm; \
1102
elm = tmp; \
1103
} \
1104
RB_SET_BLACKRED(parent, gparent, field); \
1105
RB_ROTATE_LEFT(head, gparent, tmp, field); \
1106
} \
1107
} \
1108
RB_COLOR(head->rbh_root, field) = RB_BLACK; \
1109
} \
1110
\
1111
void \
1112
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
1113
{ \
1114
struct type *tmp; \
1115
while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
1116
elm != RB_ROOT(head)) { \
1117
if (RB_LEFT(parent, field) == elm) { \
1118
tmp = RB_RIGHT(parent, field); \
1119
if (RB_COLOR(tmp, field) == RB_RED) { \
1120
RB_SET_BLACKRED(tmp, parent, field); \
1121
RB_ROTATE_LEFT(head, parent, tmp, field);\
1122
tmp = RB_RIGHT(parent, field); \
1123
} \
1124
if ((RB_LEFT(tmp, field) == NULL || \
1125
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1126
(RB_RIGHT(tmp, field) == NULL || \
1127
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1128
RB_COLOR(tmp, field) = RB_RED; \
1129
elm = parent; \
1130
parent = RB_PARENT(elm, field); \
1131
} else { \
1132
if (RB_RIGHT(tmp, field) == NULL || \
1133
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
1134
struct type *oleft; \
1135
if ((oleft = RB_LEFT(tmp, field)))\
1136
RB_COLOR(oleft, field) = RB_BLACK;\
1137
RB_COLOR(tmp, field) = RB_RED; \
1138
RB_ROTATE_RIGHT(head, tmp, oleft, field);\
1139
tmp = RB_RIGHT(parent, field); \
1140
} \
1141
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1142
RB_COLOR(parent, field) = RB_BLACK; \
1143
if (RB_RIGHT(tmp, field)) \
1144
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
1145
RB_ROTATE_LEFT(head, parent, tmp, field);\
1146
elm = RB_ROOT(head); \
1147
break; \
1148
} \
1149
} else { \
1150
tmp = RB_LEFT(parent, field); \
1151
if (RB_COLOR(tmp, field) == RB_RED) { \
1152
RB_SET_BLACKRED(tmp, parent, field); \
1153
RB_ROTATE_RIGHT(head, parent, tmp, field);\
1154
tmp = RB_LEFT(parent, field); \
1155
} \
1156
if ((RB_LEFT(tmp, field) == NULL || \
1157
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1158
(RB_RIGHT(tmp, field) == NULL || \
1159
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1160
RB_COLOR(tmp, field) = RB_RED; \
1161
elm = parent; \
1162
parent = RB_PARENT(elm, field); \
1163
} else { \
1164
if (RB_LEFT(tmp, field) == NULL || \
1165
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
1166
struct type *oright; \
1167
if ((oright = RB_RIGHT(tmp, field)))\
1168
RB_COLOR(oright, field) = RB_BLACK;\
1169
RB_COLOR(tmp, field) = RB_RED; \
1170
RB_ROTATE_LEFT(head, tmp, oright, field);\
1171
tmp = RB_LEFT(parent, field); \
1172
} \
1173
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1174
RB_COLOR(parent, field) = RB_BLACK; \
1175
if (RB_LEFT(tmp, field)) \
1176
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
1177
RB_ROTATE_RIGHT(head, parent, tmp, field);\
1178
elm = RB_ROOT(head); \
1179
break; \
1180
} \
1181
} \
1182
} \
1183
if (elm) \
1184
RB_COLOR(elm, field) = RB_BLACK; \
1185
} \
1186
\
1187
struct type * \
1188
name##_RB_REMOVE(struct name *head, struct type *elm) \
1189
{ \
1190
struct type *child, *parent, *old = elm; \
1191
int color; \
1192
if (RB_LEFT(elm, field) == NULL) \
1193
child = RB_RIGHT(elm, field); \
1194
else if (RB_RIGHT(elm, field) == NULL) \
1195
child = RB_LEFT(elm, field); \
1196
else { \
1197
struct type *left; \
1198
elm = RB_RIGHT(elm, field); \
1199
while ((left = RB_LEFT(elm, field))) \
1200
elm = left; \
1201
child = RB_RIGHT(elm, field); \
1202
parent = RB_PARENT(elm, field); \
1203
color = RB_COLOR(elm, field); \
1204
if (child) \
1205
RB_PARENT(child, field) = parent; \
1206
if (parent) { \
1207
if (RB_LEFT(parent, field) == elm) \
1208
RB_LEFT(parent, field) = child; \
1209
else \
1210
RB_RIGHT(parent, field) = child; \
1211
RB_AUGMENT(parent); \
1212
} else \
1213
RB_ROOT(head) = child; \
1214
if (RB_PARENT(elm, field) == old) \
1215
parent = elm; \
1216
(elm)->field = (old)->field; \
1217
if (RB_PARENT(old, field)) { \
1218
if (RB_LEFT(RB_PARENT(old, field), field) == old)\
1219
RB_LEFT(RB_PARENT(old, field), field) = elm;\
1220
else \
1221
RB_RIGHT(RB_PARENT(old, field), field) = elm;\
1222
RB_AUGMENT(RB_PARENT(old, field)); \
1223
} else \
1224
RB_ROOT(head) = elm; \
1225
RB_PARENT(RB_LEFT(old, field), field) = elm; \
1226
if (RB_RIGHT(old, field)) \
1227
RB_PARENT(RB_RIGHT(old, field), field) = elm; \
1228
if (parent) { \
1229
left = parent; \
1230
do { \
1231
RB_AUGMENT(left); \
1232
} while ((left = RB_PARENT(left, field))); \
1233
} \
1234
goto color; \
1235
} \
1236
parent = RB_PARENT(elm, field); \
1237
color = RB_COLOR(elm, field); \
1238
if (child) \
1239
RB_PARENT(child, field) = parent; \
1240
if (parent) { \
1241
if (RB_LEFT(parent, field) == elm) \
1242
RB_LEFT(parent, field) = child; \
1243
else \
1244
RB_RIGHT(parent, field) = child; \
1245
RB_AUGMENT(parent); \
1246
} else \
1247
RB_ROOT(head) = child; \
1248
color: \
1249
if (color == RB_BLACK) \
1250
name##_RB_REMOVE_COLOR(head, parent, child); \
1251
return (old); \
1252
} \
1253
\
1254
/* Inserts a node into the RB tree */
\
1255
struct type * \
1256
name##_RB_INSERT(struct name *head, struct type *elm) \
1257
{ \
1258
struct type *tmp; \
1259
struct type *parent = NULL; \
1260
int comp = 0; \
1261
tmp = RB_ROOT(head); \
1262
while (tmp) { \
1263
parent = tmp; \
1264
comp = (cmp)(elm, parent); \
1265
if (comp < 0) \
1266
tmp = RB_LEFT(tmp, field); \
1267
else if (comp > 0) \
1268
tmp = RB_RIGHT(tmp, field); \
1269
else \
1270
return (tmp); \
1271
} \
1272
RB_SET(elm, parent, field); \
1273
if (parent != NULL) { \
1274
if (comp < 0) \
1275
RB_LEFT(parent, field) = elm; \
1276
else \
1277
RB_RIGHT(parent, field) = elm; \
1278
RB_AUGMENT(parent); \
1279
} else \
1280
RB_ROOT(head) = elm; \
1281
name##_RB_INSERT_COLOR(head, elm); \
1282
return (NULL); \
1283
} \
1284
\
1285
/* Finds the node with the same key as elm */
\
1286
struct type * \
1287
name##_RB_FIND(struct name *head, struct type *elm) \
1288
{ \
1289
struct type *tmp = RB_ROOT(head); \
1290
int comp; \
1291
while (tmp) { \
1292
comp = cmp(elm, tmp); \
1293
if (comp < 0) \
1294
tmp = RB_LEFT(tmp, field); \
1295
else if (comp > 0) \
1296
tmp = RB_RIGHT(tmp, field); \
1297
else \
1298
return (tmp); \
1299
} \
1300
return (NULL); \
1301
} \
1302
\
1303
struct type * \
1304
name##_RB_NEXT(struct type *elm) \
1305
{ \
1306
if (RB_RIGHT(elm, field)) { \
1307
elm = RB_RIGHT(elm, field); \
1308
while (RB_LEFT(elm, field)) \
1309
elm = RB_LEFT(elm, field); \
1310
} else { \
1311
if (RB_PARENT(elm, field) && \
1312
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
1313
elm = RB_PARENT(elm, field); \
1314
else { \
1315
while (RB_PARENT(elm, field) && \
1316
(elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
1317
elm = RB_PARENT(elm, field); \
1318
elm = RB_PARENT(elm, field); \
1319
} \
1320
} \
1321
return (elm); \
1322
} \
1323
\
1324
struct type * \
1325
name##_RB_MINMAX(struct name *head, int val) \
1326
{ \
1327
struct type *tmp = RB_ROOT(head); \
1328
struct type *parent = NULL; \
1329
while (tmp) { \
1330
parent = tmp; \
1331
if (val < 0) \
1332
tmp = RB_LEFT(tmp, field); \
1333
else \
1334
tmp = RB_RIGHT(tmp, field); \
1335
} \
1336
return (parent); \
1337
}
1338
1339
#define RB_NEGINF -1
1340
#define RB_INF 1
1341
1342
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
1343
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
1344
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
1345
#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
1346
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
1347
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
1348
1349
#define RB_FOREACH(x, name, head) \
1350
for ((x) = RB_MIN(name, head); \
1351
(x) != NULL; \
1352
(x) = name##_RB_NEXT(x))
1353
1354
#endif
/* _SYS_TREE_H_ */
libevent
WIN32-Code
tree.h
Generated on Sat Nov 9 2013 01:24:48 for MySQL 5.6.14 Source Code Document by
1.8.1.2
1.8.1.2 
