WPILibC++
2023.4.3-108-ge5452e3
tree.h
Go to the documentation of this file.
1
/*-
2
* Copyright 2002 Niels Provos <provos@citi.umich.edu>
3
* All rights reserved.
4
*
5
* Redistribution and use in source and binary forms, with or without
6
* modification, are permitted provided that the following conditions
7
* are met:
8
* 1. Redistributions of source code must retain the above copyright
9
* notice, this list of conditions and the following disclaimer.
10
* 2. Redistributions in binary form must reproduce the above copyright
11
* notice, this list of conditions and the following disclaimer in the
12
* documentation and/or other materials provided with the distribution.
13
*
14
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24
*/
25
26
#ifndef UV_TREE_H_
27
#define UV_TREE_H_
28
29
#ifndef UV__UNUSED
30
# if __GNUC__
31
# define UV__UNUSED __attribute__((unused))
32
# else
33
# define UV__UNUSED
34
# endif
35
#endif
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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)) != 0) { \
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
for (;;) { \
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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 (
/*CONSTCOND*/
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)) != NULL) { \
345
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
346
} \
347
RB_AUGMENT(elm); \
348
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
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 (
/*CONSTCOND*/
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)) != NULL) { \
365
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
366
} \
367
RB_AUGMENT(elm); \
368
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
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 (
/*CONSTCOND*/
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, UV__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, UV__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)) != NULL && \
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, \
453
struct type *elm) \
454
{ \
455
struct type *tmp; \
456
while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
457
elm != RB_ROOT(head)) { \
458
if (RB_LEFT(parent, field) == elm) { \
459
tmp = RB_RIGHT(parent, field); \
460
if (RB_COLOR(tmp, field) == RB_RED) { \
461
RB_SET_BLACKRED(tmp, parent, field); \
462
RB_ROTATE_LEFT(head, parent, tmp, field); \
463
tmp = RB_RIGHT(parent, field); \
464
} \
465
if ((RB_LEFT(tmp, field) == NULL || \
466
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
467
(RB_RIGHT(tmp, field) == NULL || \
468
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
469
RB_COLOR(tmp, field) = RB_RED; \
470
elm = parent; \
471
parent = RB_PARENT(elm, field); \
472
} else { \
473
if (RB_RIGHT(tmp, field) == NULL || \
474
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \
475
struct type *oleft; \
476
if ((oleft = RB_LEFT(tmp, field)) \
477
!= NULL) \
478
RB_COLOR(oleft, field) = RB_BLACK; \
479
RB_COLOR(tmp, field) = RB_RED; \
480
RB_ROTATE_RIGHT(head, tmp, oleft, field); \
481
tmp = RB_RIGHT(parent, field); \
482
} \
483
RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
484
RB_COLOR(parent, field) = RB_BLACK; \
485
if (RB_RIGHT(tmp, field)) \
486
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
487
RB_ROTATE_LEFT(head, parent, tmp, field); \
488
elm = RB_ROOT(head); \
489
break; \
490
} \
491
} else { \
492
tmp = RB_LEFT(parent, field); \
493
if (RB_COLOR(tmp, field) == RB_RED) { \
494
RB_SET_BLACKRED(tmp, parent, field); \
495
RB_ROTATE_RIGHT(head, parent, tmp, field); \
496
tmp = RB_LEFT(parent, field); \
497
} \
498
if ((RB_LEFT(tmp, field) == NULL || \
499
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
500
(RB_RIGHT(tmp, field) == NULL || \
501
RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
502
RB_COLOR(tmp, field) = RB_RED; \
503
elm = parent; \
504
parent = RB_PARENT(elm, field); \
505
} else { \
506
if (RB_LEFT(tmp, field) == NULL || \
507
RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \
508
struct type *oright; \
509
if ((oright = RB_RIGHT(tmp, field)) \
510
!= NULL) \
511
RB_COLOR(oright, field) = RB_BLACK; \
512
RB_COLOR(tmp, field) = RB_RED; \
513
RB_ROTATE_LEFT(head, tmp, oright, field); \
514
tmp = RB_LEFT(parent, field); \
515
} \
516
RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
517
RB_COLOR(parent, field) = RB_BLACK; \
518
if (RB_LEFT(tmp, field)) \
519
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
520
RB_ROTATE_RIGHT(head, parent, tmp, field); \
521
elm = RB_ROOT(head); \
522
break; \
523
} \
524
} \
525
} \
526
if (elm) \
527
RB_COLOR(elm, field) = RB_BLACK; \
528
} \
529
\
530
attr struct type * \
531
name##_RB_REMOVE(struct name *head, struct type *elm) \
532
{ \
533
struct type *child, *parent, *old = elm; \
534
int color; \
535
if (RB_LEFT(elm, field) == NULL) \
536
child = RB_RIGHT(elm, field); \
537
else if (RB_RIGHT(elm, field) == NULL) \
538
child = RB_LEFT(elm, field); \
539
else { \
540
struct type *left; \
541
elm = RB_RIGHT(elm, field); \
542
while ((left = RB_LEFT(elm, field)) != NULL) \
543
elm = left; \
544
child = RB_RIGHT(elm, field); \
545
parent = RB_PARENT(elm, field); \
546
color = RB_COLOR(elm, field); \
547
if (child) \
548
RB_PARENT(child, field) = parent; \
549
if (parent) { \
550
if (RB_LEFT(parent, field) == elm) \
551
RB_LEFT(parent, field) = child; \
552
else \
553
RB_RIGHT(parent, field) = child; \
554
RB_AUGMENT(parent); \
555
} else \
556
RB_ROOT(head) = child; \
557
if (RB_PARENT(elm, field) == old) \
558
parent = elm; \
559
(elm)->field = (old)->field; \
560
if (RB_PARENT(old, field)) { \
561
if (RB_LEFT(RB_PARENT(old, field), field) == old) \
562
RB_LEFT(RB_PARENT(old, field), field) = elm; \
563
else \
564
RB_RIGHT(RB_PARENT(old, field), field) = elm; \
565
RB_AUGMENT(RB_PARENT(old, field)); \
566
} else \
567
RB_ROOT(head) = elm; \
568
RB_PARENT(RB_LEFT(old, field), field) = elm; \
569
if (RB_RIGHT(old, field)) \
570
RB_PARENT(RB_RIGHT(old, field), field) = elm; \
571
if (parent) { \
572
left = parent; \
573
do { \
574
RB_AUGMENT(left); \
575
} while ((left = RB_PARENT(left, field)) != NULL); \
576
} \
577
goto color; \
578
} \
579
parent = RB_PARENT(elm, field); \
580
color = RB_COLOR(elm, field); \
581
if (child) \
582
RB_PARENT(child, field) = parent; \
583
if (parent) { \
584
if (RB_LEFT(parent, field) == elm) \
585
RB_LEFT(parent, field) = child; \
586
else \
587
RB_RIGHT(parent, field) = child; \
588
RB_AUGMENT(parent); \
589
} else \
590
RB_ROOT(head) = child; \
591
color: \
592
if (color == RB_BLACK) \
593
name##_RB_REMOVE_COLOR(head, parent, child); \
594
return (old); \
595
} \
596
\
597
/* Inserts a node into the RB tree */
\
598
attr struct type * \
599
name##_RB_INSERT(struct name *head, struct type *elm) \
600
{ \
601
struct type *tmp; \
602
struct type *parent = NULL; \
603
int comp = 0; \
604
tmp = RB_ROOT(head); \
605
while (tmp) { \
606
parent = tmp; \
607
comp = (cmp)(elm, parent); \
608
if (comp < 0) \
609
tmp = RB_LEFT(tmp, field); \
610
else if (comp > 0) \
611
tmp = RB_RIGHT(tmp, field); \
612
else \
613
return (tmp); \
614
} \
615
RB_SET(elm, parent, field); \
616
if (parent != NULL) { \
617
if (comp < 0) \
618
RB_LEFT(parent, field) = elm; \
619
else \
620
RB_RIGHT(parent, field) = elm; \
621
RB_AUGMENT(parent); \
622
} else \
623
RB_ROOT(head) = elm; \
624
name##_RB_INSERT_COLOR(head, elm); \
625
return (NULL); \
626
} \
627
\
628
/* Finds the node with the same key as elm */
\
629
attr struct type * \
630
name##_RB_FIND(struct name *head, struct type *elm) \
631
{ \
632
struct type *tmp = RB_ROOT(head); \
633
int comp; \
634
while (tmp) { \
635
comp = cmp(elm, tmp); \
636
if (comp < 0) \
637
tmp = RB_LEFT(tmp, field); \
638
else if (comp > 0) \
639
tmp = RB_RIGHT(tmp, field); \
640
else \
641
return (tmp); \
642
} \
643
return (NULL); \
644
} \
645
\
646
/* Finds the first node greater than or equal to the search key */
\
647
attr struct type * \
648
name##_RB_NFIND(struct name *head, struct type *elm) \
649
{ \
650
struct type *tmp = RB_ROOT(head); \
651
struct type *res = NULL; \
652
int comp; \
653
while (tmp) { \
654
comp = cmp(elm, tmp); \
655
if (comp < 0) { \
656
res = tmp; \
657
tmp = RB_LEFT(tmp, field); \
658
} \
659
else if (comp > 0) \
660
tmp = RB_RIGHT(tmp, field); \
661
else \
662
return (tmp); \
663
} \
664
return (res); \
665
} \
666
\
667
/* ARGSUSED */
\
668
attr struct type * \
669
name##_RB_NEXT(struct type *elm) \
670
{ \
671
if (RB_RIGHT(elm, field)) { \
672
elm = RB_RIGHT(elm, field); \
673
while (RB_LEFT(elm, field)) \
674
elm = RB_LEFT(elm, field); \
675
} else { \
676
if (RB_PARENT(elm, field) && \
677
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
678
elm = RB_PARENT(elm, field); \
679
else { \
680
while (RB_PARENT(elm, field) && \
681
(elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
682
elm = RB_PARENT(elm, field); \
683
elm = RB_PARENT(elm, field); \
684
} \
685
} \
686
return (elm); \
687
} \
688
\
689
/* ARGSUSED */
\
690
attr struct type * \
691
name##_RB_PREV(struct type *elm) \
692
{ \
693
if (RB_LEFT(elm, field)) { \
694
elm = RB_LEFT(elm, field); \
695
while (RB_RIGHT(elm, field)) \
696
elm = RB_RIGHT(elm, field); \
697
} else { \
698
if (RB_PARENT(elm, field) && \
699
(elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
700
elm = RB_PARENT(elm, field); \
701
else { \
702
while (RB_PARENT(elm, field) && \
703
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
704
elm = RB_PARENT(elm, field); \
705
elm = RB_PARENT(elm, field); \
706
} \
707
} \
708
return (elm); \
709
} \
710
\
711
attr struct type * \
712
name##_RB_MINMAX(struct name *head, int val) \
713
{ \
714
struct type *tmp = RB_ROOT(head); \
715
struct type *parent = NULL; \
716
while (tmp) { \
717
parent = tmp; \
718
if (val < 0) \
719
tmp = RB_LEFT(tmp, field); \
720
else \
721
tmp = RB_RIGHT(tmp, field); \
722
} \
723
return (parent); \
724
}
725
726
#define RB_NEGINF -1
727
#define RB_INF 1
728
729
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
730
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
731
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
732
#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
733
#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
734
#define RB_PREV(name, x, y) name##_RB_PREV(y)
735
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
736
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
737
738
#define RB_FOREACH(x, name, head) \
739
for ((x) = RB_MIN(name, head); \
740
(x) != NULL; \
741
(x) = name##_RB_NEXT(x))
742
743
#define RB_FOREACH_FROM(x, name, y) \
744
for ((x) = (y); \
745
((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
746
(x) = (y))
747
748
#define RB_FOREACH_SAFE(x, name, head, y) \
749
for ((x) = RB_MIN(name, head); \
750
((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
751
(x) = (y))
752
753
#define RB_FOREACH_REVERSE(x, name, head) \
754
for ((x) = RB_MAX(name, head); \
755
(x) != NULL; \
756
(x) = name##_RB_PREV(x))
757
758
#define RB_FOREACH_REVERSE_FROM(x, name, y) \
759
for ((x) = (y); \
760
((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
761
(x) = (y))
762
763
#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
764
for ((x) = RB_MAX(name, head); \
765
((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
766
(x) = (y))
767
768
#endif
/* UV_TREE_H_ */
thirdparty
libuv
include
uv
tree.h
Generated on Mon Jul 10 2023 17:03:00 for WPILibC++ by
1.9.4
1.9.4