« back to all changes in this revision
Viewing changes to compat/sys/tree.h
- browse files at revision 6
- compare with another revision
- download diff
- download tarball
- view history from revision 6
- Committer: Bazaar Package Importer
- Author(s): Anibal Monsalve Salazar
- Date: 2009-05-15 20:11:06 UTC
- mfrom: (1.3.1 upstream) (5.2.1 sid)
- Revision ID: james.westby@ubuntu.com-20090515201106-auauq7m2l4sej5n9
Tags: 1.4.11-stable-1
* New upstream release
- Fix a bug when removing a timeout from the heap
- Remove the limit on size of HTTP headers by removing static buffers
- Fix a nasty dangling pointer bug in epoll.c that could occur after
epoll_recalc()
- Fix a bug when removing a timeout from the heap
- Remove the limit on size of HTTP headers by removing static buffers
- Fix a nasty dangling pointer bug in epoll.c that could occur after
epoll_recalc()
- files added:
- Doxyfile
- WIN32-Prj/regress
- debian/patches
- files removed:
- WIN32-Code/misc.c
- files modified:
- ChangeLog
added
removed
compat/sys/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_ */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1