Grid Community Toolkit
6.2.1705709074 (tag: v6.2.20240202)
Main Page
Related Pages
Modules
Data Structures
Files
Examples
File List
Globals
All
Data Structures
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Groups
Pages
gsi_openssh
source
openbsd-compat
sys-tree.h
1
/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
2
/*
3
* Copyright 2002 Niels Provos <
[email protected]
>
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
/* OPENBSD ORIGINAL: sys/sys/tree.h */
28
29
#include "config.h"
30
#ifdef NO_ATTRIBUTE_ON_RETURN_TYPE
31
# define __attribute__(x)
32
#endif
33
34
#ifndef _SYS_TREE_H_
35
#define _SYS_TREE_H_
36
37
/*
38
* This file defines data structures for different types of trees:
39
* splay trees and red-black trees.
40
*
41
* A splay tree is a self-organizing data structure. Every operation
42
* on the tree causes a splay to happen. The splay moves the requested
43
* node to the root of the tree and partly rebalances it.
44
*
45
* This has the benefit that request locality causes faster lookups as
46
* the requested nodes move to the top of the tree. On the other hand,
47
* every lookup causes memory writes.
48
*
49
* The Balance Theorem bounds the total access time for m operations
50
* and n inserts on an initially empty tree as O((m + n)lg n). The
51
* amortized cost for a sequence of m accesses to a splay tree is O(lg n);
52
*
53
* A red-black tree is a binary search tree with the node color as an
54
* extra attribute. It fulfills a set of conditions:
55
* - every search path from the root to a leaf consists of the
56
* same number of black nodes,
57
* - each red node (except for the root) has a black parent,
58
* - each leaf node is black.
59
*
60
* Every operation on a red-black tree is bounded as O(lg n).
61
* The maximum height of a red-black tree is 2lg (n+1).
62
*/
63
64
#define SPLAY_HEAD(name, type) \
65
struct name { \
66
struct type *sph_root;
/* root of the tree */
\
67
}
68
69
#define SPLAY_INITIALIZER(root) \
70
{ NULL }
71
72
#define SPLAY_INIT(root) do { \
73
(root)->sph_root = NULL; \
74
} while (0)
75
76
#define SPLAY_ENTRY(type) \
77
struct { \
78
struct type *spe_left;
/* left element */
\
79
struct type *spe_right;
/* right element */
\
80
}
81
82
#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
83
#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
84
#define SPLAY_ROOT(head) (head)->sph_root
85
#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
86
87
/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
88
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
89
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
90
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
91
(head)->sph_root = tmp; \
92
} while (0)
93
94
#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
95
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
96
SPLAY_LEFT(tmp, field) = (head)->sph_root; \
97
(head)->sph_root = tmp; \
98
} while (0)
99
100
#define SPLAY_LINKLEFT(head, tmp, field) do { \
101
SPLAY_LEFT(tmp, field) = (head)->sph_root; \
102
tmp = (head)->sph_root; \
103
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
104
} while (0)
105
106
#define SPLAY_LINKRIGHT(head, tmp, field) do { \
107
SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
108
tmp = (head)->sph_root; \
109
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
110
} while (0)
111
112
#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
113
SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
114
SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
115
SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
116
SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
117
} while (0)
118
119
/* Generates prototypes and inline functions */
120
121
#define SPLAY_PROTOTYPE(name, type, field, cmp) \
122
void name##_SPLAY(struct name *, struct type *); \
123
void name##_SPLAY_MINMAX(struct name *, int); \
124
struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
125
struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
126
\
127
/* Finds the node with the same key as elm */
\
128
static __inline struct type * \
129
name##_SPLAY_FIND(struct name *head, struct type *elm) \
130
{ \
131
if (SPLAY_EMPTY(head)) \
132
return(NULL); \
133
name##_SPLAY(head, elm); \
134
if ((cmp)(elm, (head)->sph_root) == 0) \
135
return (head->sph_root); \
136
return (NULL); \
137
} \
138
\
139
static __inline struct type * \
140
name##_SPLAY_NEXT(struct name *head, struct type *elm) \
141
{ \
142
name##_SPLAY(head, elm); \
143
if (SPLAY_RIGHT(elm, field) != NULL) { \
144
elm = SPLAY_RIGHT(elm, field); \
145
while (SPLAY_LEFT(elm, field) != NULL) { \
146
elm = SPLAY_LEFT(elm, field); \
147
} \
148
} else \
149
elm = NULL; \
150
return (elm); \
151
} \
152
\
153
static __inline struct type * \
154
name##_SPLAY_MIN_MAX(struct name *head, int val) \
155
{ \
156
name##_SPLAY_MINMAX(head, val); \
157
return (SPLAY_ROOT(head)); \
158
}
159
160
/* Main splay operation.
161
* Moves node close to the key of elm to top
162
*/
163
#define SPLAY_GENERATE(name, type, field, cmp) \
164
struct type * \
165
name##_SPLAY_INSERT(struct name *head, struct type *elm) \
166
{ \
167
if (SPLAY_EMPTY(head)) { \
168
SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
169
} else { \
170
int __comp; \
171
name##_SPLAY(head, elm); \
172
__comp = (cmp)(elm, (head)->sph_root); \
173
if(__comp < 0) { \
174
SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
175
SPLAY_RIGHT(elm, field) = (head)->sph_root; \
176
SPLAY_LEFT((head)->sph_root, field) = NULL; \
177
} else if (__comp > 0) { \
178
SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
179
SPLAY_LEFT(elm, field) = (head)->sph_root; \
180
SPLAY_RIGHT((head)->sph_root, field) = NULL; \
181
} else \
182
return ((head)->sph_root); \
183
} \
184
(head)->sph_root = (elm); \
185
return (NULL); \
186
} \
187
\
188
struct type * \
189
name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
190
{ \
191
struct type *__tmp; \
192
if (SPLAY_EMPTY(head)) \
193
return (NULL); \
194
name##_SPLAY(head, elm); \
195
if ((cmp)(elm, (head)->sph_root) == 0) { \
196
if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
197
(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
198
} else { \
199
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
200
(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
201
name##_SPLAY(head, elm); \
202
SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
203
} \
204
return (elm); \
205
} \
206
return (NULL); \
207
} \
208
\
209
void \
210
name##_SPLAY(struct name *head, struct type *elm) \
211
{ \
212
struct type __node, *__left, *__right, *__tmp; \
213
int __comp; \
214
\
215
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
216
__left = __right = &__node; \
217
\
218
while ((__comp = (cmp)(elm, (head)->sph_root))) { \
219
if (__comp < 0) { \
220
__tmp = SPLAY_LEFT((head)->sph_root, field); \
221
if (__tmp == NULL) \
222
break; \
223
if ((cmp)(elm, __tmp) < 0){ \
224
SPLAY_ROTATE_RIGHT(head, __tmp, field); \
225
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
226
break; \
227
} \
228
SPLAY_LINKLEFT(head, __right, field); \
229
} else if (__comp > 0) { \
230
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
231
if (__tmp == NULL) \
232
break; \
233
if ((cmp)(elm, __tmp) > 0){ \
234
SPLAY_ROTATE_LEFT(head, __tmp, field); \
235
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
236
break; \
237
} \
238
SPLAY_LINKRIGHT(head, __left, field); \
239
} \
240
} \
241
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
242
} \
243
\
244
/* Splay with either the minimum or the maximum element \
245
* Used to find minimum or maximum element in tree. \
246
*/
\
247
void name##_SPLAY_MINMAX(struct name *head, int __comp) \
248
{ \
249
struct type __node, *__left, *__right, *__tmp; \
250
\
251
SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
252
__left = __right = &__node; \
253
\
254
while (1) { \
255
if (__comp < 0) { \
256
__tmp = SPLAY_LEFT((head)->sph_root, field); \
257
if (__tmp == NULL) \
258
break; \
259
if (__comp < 0){ \
260
SPLAY_ROTATE_RIGHT(head, __tmp, field); \
261
if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
262
break; \
263
} \
264
SPLAY_LINKLEFT(head, __right, field); \
265
} else if (__comp > 0) { \
266
__tmp = SPLAY_RIGHT((head)->sph_root, field); \
267
if (__tmp == NULL) \
268
break; \
269
if (__comp > 0) { \
270
SPLAY_ROTATE_LEFT(head, __tmp, field); \
271
if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
272
break; \
273
} \
274
SPLAY_LINKRIGHT(head, __left, field); \
275
} \
276
} \
277
SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
278
}
279
280
#define SPLAY_NEGINF -1
281
#define SPLAY_INF 1
282
283
#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
284
#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
285
#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
286
#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
287
#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
288
: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
289
#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
290
: name##_SPLAY_MIN_MAX(x, SPLAY_INF))
291
292
#define SPLAY_FOREACH(x, name, head) \
293
for ((x) = SPLAY_MIN(name, head); \
294
(x) != NULL; \
295
(x) = SPLAY_NEXT(name, head, x))
296
297
/* Macros that define a red-black tree */
298
#define RB_HEAD(name, type) \
299
struct name { \
300
struct type *rbh_root;
/* root of the tree */
\
301
}
302
303
#define RB_INITIALIZER(root) \
304
{ NULL }
305
306
#define RB_INIT(root) do { \
307
(root)->rbh_root = NULL; \
308
} while (0)
309
310
#define RB_BLACK 0
311
#define RB_RED 1
312
#define RB_ENTRY(type) \
313
struct { \
314
struct type *rbe_left;
/* left element */
\
315
struct type *rbe_right;
/* right element */
\
316
struct type *rbe_parent;
/* parent element */
\
317
int rbe_color;
/* node color */
\
318
}
319
320
#define RB_LEFT(elm, field) (elm)->field.rbe_left
321
#define RB_RIGHT(elm, field) (elm)->field.rbe_right
322
#define RB_PARENT(elm, field) (elm)->field.rbe_parent
323
#define RB_COLOR(elm, field) (elm)->field.rbe_color
324
#define RB_ROOT(head) (head)->rbh_root
325
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
326
327
#define RB_SET(elm, parent, field) do { \
328
RB_PARENT(elm, field) = parent; \
329
RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
330
RB_COLOR(elm, field) = RB_RED; \
331
} while (0)
332
333
#define RB_SET_BLACKRED(black, red, field) do { \
334
RB_COLOR(black, field) = RB_BLACK; \
335
RB_COLOR(red, field) = RB_RED; \
336
} while (0)
337
338
#ifndef RB_AUGMENT
339
#define RB_AUGMENT(x) do {} while (0)
340
#endif
341
342
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
343
(tmp) = RB_RIGHT(elm, field); \
344
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
345
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
346
} \
347
RB_AUGMENT(elm); \
348
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
349
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
350
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
351
else \
352
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
353
} else \
354
(head)->rbh_root = (tmp); \
355
RB_LEFT(tmp, field) = (elm); \
356
RB_PARENT(elm, field) = (tmp); \
357
RB_AUGMENT(tmp); \
358
if ((RB_PARENT(tmp, field))) \
359
RB_AUGMENT(RB_PARENT(tmp, field)); \
360
} while (0)
361
362
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
363
(tmp) = RB_LEFT(elm, field); \
364
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
365
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
366
} \
367
RB_AUGMENT(elm); \
368
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
369
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
370
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
371
else \
372
RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
373
} else \
374
(head)->rbh_root = (tmp); \
375
RB_RIGHT(tmp, field) = (elm); \
376
RB_PARENT(elm, field) = (tmp); \
377
RB_AUGMENT(tmp); \
378
if ((RB_PARENT(tmp, field))) \
379
RB_AUGMENT(RB_PARENT(tmp, field)); \
380
} while (0)
381
382
/* Generates prototypes and inline functions */
383
#define RB_PROTOTYPE(name, type, field, cmp) \
384
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
385
#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
386
RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
387
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
388
attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
389
attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
390
attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
391
attr struct type *name##_RB_INSERT(struct name *, struct type *); \
392
attr struct type *name##_RB_FIND(struct name *, struct type *); \
393
attr struct type *name##_RB_NFIND(struct name *, struct type *); \
394
attr struct type *name##_RB_NEXT(struct type *); \
395
attr struct type *name##_RB_PREV(struct type *); \
396
attr struct type *name##_RB_MINMAX(struct name *, int); \
397
\
398
399
/* Main rb operation.
400
* Moves node close to the key of elm to top
401
*/
402
#define RB_GENERATE(name, type, field, cmp) \
403
RB_GENERATE_INTERNAL(name, type, field, cmp,)
404
#define RB_GENERATE_STATIC(name, type, field, cmp) \
405
RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
406
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
407
attr void \
408
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
409
{ \
410
struct type *parent, *gparent, *tmp; \
411
while ((parent = RB_PARENT(elm, field)) && \
412
RB_COLOR(parent, field) == RB_RED) { \
413
gparent = RB_PARENT(parent, field); \
414
if (parent == RB_LEFT(gparent, field)) { \
415
tmp = RB_RIGHT(gparent, field); \
416
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
417
RB_COLOR(tmp, field) = RB_BLACK; \
418
RB_SET_BLACKRED(parent, gparent, field);\
419
elm = gparent; \
420
continue; \
421
} \
422
if (RB_RIGHT(parent, field) == elm) { \
423
RB_ROTATE_LEFT(head, parent, tmp, field);\
424
tmp = parent; \
425
parent = elm; \
426
elm = tmp; \
427
} \
428
RB_SET_BLACKRED(parent, gparent, field); \
429
RB_ROTATE_RIGHT(head, gparent, tmp, field); \
430
} else { \
431
tmp = RB_LEFT(gparent, field); \
432
if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
433
RB_COLOR(tmp, field) = RB_BLACK; \
434
RB_SET_BLACKRED(parent, gparent, field);\
435
elm = gparent; \
436
continue; \
437
} \
438
if (RB_LEFT(parent, field) == elm) { \
439
RB_ROTATE_RIGHT(head, parent, tmp, field);\
440
tmp = parent; \
441
parent = elm; \
442
elm = tmp; \
443
} \
444
RB_SET_BLACKRED(parent, gparent, field); \
445
RB_ROTATE_LEFT(head, gparent, tmp, field); \
446
} \
447
} \
448
RB_COLOR(head->rbh_root, field) = RB_BLACK; \
449
} \
450
\
451
attr void \
452
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
453
{ \
454
struct type *tmp; \
455
while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
456
elm != RB_ROOT(head)) { \
457
if (RB_LEFT(parent, field) == elm) { \
458
tmp = RB_RIGHT(parent, field); \
459
if (RB_COLOR(tmp, field) == RB_RED) { \
460
RB_SET_BLACKRED(tmp, parent, field); \
461
RB_ROTATE_LEFT(head, parent, tmp, field);\
462
tmp = RB_RIGHT(parent, field); \
463
} \
464
if ((RB_LEFT(tmp, field) == NULL || \
465
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
466
(RB_RIGHT(tmp, field) == NULL || \
467
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
468
RB_COLOR(tmp, field) = RB_RED; \
469
elm = parent; \
470
parent = RB_PARENT(elm, field); \
471
} else { \
472
if (RB_RIGHT(tmp, field) == NULL || \
473
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
474
struct type *oleft; \
475
if ((oleft = RB_LEFT(tmp, field)))\
476
RB_COLOR(oleft, field) = RB_BLACK;\
477
RB_COLOR(tmp, field) = RB_RED; \
478
RB_ROTATE_RIGHT(head, tmp, oleft, field);\
479
tmp = RB_RIGHT(parent, field); \
480
} \
481
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
482
RB_COLOR(parent, field) = RB_BLACK; \
483
if (RB_RIGHT(tmp, field)) \
484
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
485
RB_ROTATE_LEFT(head, parent, tmp, field);\
486
elm = RB_ROOT(head); \
487
break; \
488
} \
489
} else { \
490
tmp = RB_LEFT(parent, field); \
491
if (RB_COLOR(tmp, field) == RB_RED) { \
492
RB_SET_BLACKRED(tmp, parent, field); \
493
RB_ROTATE_RIGHT(head, parent, tmp, field);\
494
tmp = RB_LEFT(parent, field); \
495
} \
496
if ((RB_LEFT(tmp, field) == NULL || \
497
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
498
(RB_RIGHT(tmp, field) == NULL || \
499
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
500
RB_COLOR(tmp, field) = RB_RED; \
501
elm = parent; \
502
parent = RB_PARENT(elm, field); \
503
} else { \
504
if (RB_LEFT(tmp, field) == NULL || \
505
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
506
struct type *oright; \
507
if ((oright = RB_RIGHT(tmp, field)))\
508
RB_COLOR(oright, field) = RB_BLACK;\
509
RB_COLOR(tmp, field) = RB_RED; \
510
RB_ROTATE_LEFT(head, tmp, oright, field);\
511
tmp = RB_LEFT(parent, field); \
512
} \
513
RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
514
RB_COLOR(parent, field) = RB_BLACK; \
515
if (RB_LEFT(tmp, field)) \
516
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
517
RB_ROTATE_RIGHT(head, parent, tmp, field);\
518
elm = RB_ROOT(head); \
519
break; \
520
} \
521
} \
522
} \
523
if (elm) \
524
RB_COLOR(elm, field) = RB_BLACK; \
525
} \
526
\
527
attr struct type * \
528
name##_RB_REMOVE(struct name *head, struct type *elm) \
529
{ \
530
struct type *child, *parent, *old = elm; \
531
int color; \
532
if (RB_LEFT(elm, field) == NULL) \
533
child = RB_RIGHT(elm, field); \
534
else if (RB_RIGHT(elm, field) == NULL) \
535
child = RB_LEFT(elm, field); \
536
else { \
537
struct type *left; \
538
elm = RB_RIGHT(elm, field); \
539
while ((left = RB_LEFT(elm, field))) \
540
elm = left; \
541
child = RB_RIGHT(elm, field); \
542
parent = RB_PARENT(elm, field); \
543
color = RB_COLOR(elm, field); \
544
if (child) \
545
RB_PARENT(child, field) = parent; \
546
if (parent) { \
547
if (RB_LEFT(parent, field) == elm) \
548
RB_LEFT(parent, field) = child; \
549
else \
550
RB_RIGHT(parent, field) = child; \
551
RB_AUGMENT(parent); \
552
} else \
553
RB_ROOT(head) = child; \
554
if (RB_PARENT(elm, field) == old) \
555
parent = elm; \
556
(elm)->field = (old)->field; \
557
if (RB_PARENT(old, field)) { \
558
if (RB_LEFT(RB_PARENT(old, field), field) == old)\
559
RB_LEFT(RB_PARENT(old, field), field) = elm;\
560
else \
561
RB_RIGHT(RB_PARENT(old, field), field) = elm;\
562
RB_AUGMENT(RB_PARENT(old, field)); \
563
} else \
564
RB_ROOT(head) = elm; \
565
RB_PARENT(RB_LEFT(old, field), field) = elm; \
566
if (RB_RIGHT(old, field)) \
567
RB_PARENT(RB_RIGHT(old, field), field) = elm; \
568
if (parent) { \
569
left = parent; \
570
do { \
571
RB_AUGMENT(left); \
572
} while ((left = RB_PARENT(left, field))); \
573
} \
574
goto color; \
575
} \
576
parent = RB_PARENT(elm, field); \
577
color = RB_COLOR(elm, field); \
578
if (child) \
579
RB_PARENT(child, field) = parent; \
580
if (parent) { \
581
if (RB_LEFT(parent, field) == elm) \
582
RB_LEFT(parent, field) = child; \
583
else \
584
RB_RIGHT(parent, field) = child; \
585
RB_AUGMENT(parent); \
586
} else \
587
RB_ROOT(head) = child; \
588
color: \
589
if (color == RB_BLACK) \
590
name##_RB_REMOVE_COLOR(head, parent, child); \
591
return (old); \
592
} \
593
\
594
/* Inserts a node into the RB tree */
\
595
attr struct type * \
596
name##_RB_INSERT(struct name *head, struct type *elm) \
597
{ \
598
struct type *tmp; \
599
struct type *parent = NULL; \
600
int comp = 0; \
601
tmp = RB_ROOT(head); \
602
while (tmp) { \
603
parent = tmp; \
604
comp = (cmp)(elm, parent); \
605
if (comp < 0) \
606
tmp = RB_LEFT(tmp, field); \
607
else if (comp > 0) \
608
tmp = RB_RIGHT(tmp, field); \
609
else \
610
return (tmp); \
611
} \
612
RB_SET(elm, parent, field); \
613
if (parent != NULL) { \
614
if (comp < 0) \
615
RB_LEFT(parent, field) = elm; \
616
else \
617
RB_RIGHT(parent, field) = elm; \
618
RB_AUGMENT(parent); \
619
} else \
620
RB_ROOT(head) = elm; \
621
name##_RB_INSERT_COLOR(head, elm); \
622
return (NULL); \
623
} \
624
\
625
/* Finds the node with the same key as elm */
\
626
attr struct type * \
627
name##_RB_FIND(struct name *head, struct type *elm) \
628
{ \
629
struct type *tmp = RB_ROOT(head); \
630
int comp; \
631
while (tmp) { \
632
comp = cmp(elm, tmp); \
633
if (comp < 0) \
634
tmp = RB_LEFT(tmp, field); \
635
else if (comp > 0) \
636
tmp = RB_RIGHT(tmp, field); \
637
else \
638
return (tmp); \
639
} \
640
return (NULL); \
641
} \
642
\
643
/* Finds the first node greater than or equal to the search key */
\
644
attr struct type * \
645
name##_RB_NFIND(struct name *head, struct type *elm) \
646
{ \
647
struct type *tmp = RB_ROOT(head); \
648
struct type *res = NULL; \
649
int comp; \
650
while (tmp) { \
651
comp = cmp(elm, tmp); \
652
if (comp < 0) { \
653
res = tmp; \
654
tmp = RB_LEFT(tmp, field); \
655
} \
656
else if (comp > 0) \
657
tmp = RB_RIGHT(tmp, field); \
658
else \
659
return (tmp); \
660
} \
661
return (res); \
662
} \
663
\
664
/* ARGSUSED */
\
665
attr struct type * \
666
name##_RB_NEXT(struct type *elm) \
667
{ \
668
if (RB_RIGHT(elm, field)) { \
669
elm = RB_RIGHT(elm, field); \
670
while (RB_LEFT(elm, field)) \
671
elm = RB_LEFT(elm, field); \
672
} else { \
673
if (RB_PARENT(elm, field) && \
674
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
675
elm = RB_PARENT(elm, field); \
676
else { \
677
while (RB_PARENT(elm, field) && \
678
(elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
679
elm = RB_PARENT(elm, field); \
680
elm = RB_PARENT(elm, field); \
681
} \
682
} \
683
return (elm); \
684
} \
685
\
686
/* ARGSUSED */
\
687
attr struct type * \
688
name##_RB_PREV(struct type *elm) \
689
{ \
690
if (RB_LEFT(elm, field)) { \
691
elm = RB_LEFT(elm, field); \
692
while (RB_RIGHT(elm, field)) \
693
elm = RB_RIGHT(elm, field); \
694
} else { \
695
if (RB_PARENT(elm, field) && \
696
(elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
697
elm = RB_PARENT(elm, field); \
698
else { \
699
while (RB_PARENT(elm, field) && \
700
(elm == RB_LEFT(RB_PARENT(elm, field), field)))\
701
elm = RB_PARENT(elm, field); \
702
elm = RB_PARENT(elm, field); \
703
} \
704
} \
705
return (elm); \
706
} \
707
\
708
attr struct type * \
709
name##_RB_MINMAX(struct name *head, int val) \
710
{ \
711
struct type *tmp = RB_ROOT(head); \
712
struct type *parent = NULL; \
713
while (tmp) { \
714
parent = tmp; \
715
if (val < 0) \
716
tmp = RB_LEFT(tmp, field); \
717
else \
718
tmp = RB_RIGHT(tmp, field); \
719
} \
720
return (parent); \
721
}
722
723
#define RB_NEGINF -1
724
#define RB_INF 1
725
726
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
727
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
728
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
729
#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
730
#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
731
#define RB_PREV(name, x, y) name##_RB_PREV(y)
732
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
733
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
734
735
#define RB_FOREACH(x, name, head) \
736
for ((x) = RB_MIN(name, head); \
737
(x) != NULL; \
738
(x) = name##_RB_NEXT(x))
739
740
#define RB_FOREACH_SAFE(x, name, head, y) \
741
for ((x) = RB_MIN(name, head); \
742
((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
743
(x) = (y))
744
745
#define RB_FOREACH_REVERSE(x, name, head) \
746
for ((x) = RB_MAX(name, head); \
747
(x) != NULL; \
748
(x) = name##_RB_PREV(x))
749
750
#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
751
for ((x) = RB_MAX(name, head); \
752
((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
753
(x) = (y))
754
755
#endif
/* _SYS_TREE_H_ */
Generated by
1.8.5