2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
5 * Copyright 2018-2019 Netflix, Inc.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #include <sys/cdefs.h>
36 /* Array-based red-black trees. */
38 #define ARB_NULLIDX -1
39 #define ARB_NULLCOL -1
47 #define ARB_HEAD(name, type, idxbits) \
49 int##idxbits##_t arb_curnodes; \
50 int##idxbits##_t arb_maxnodes; \
51 int##idxbits##_t arb_root_idx; \
52 int##idxbits##_t arb_free_idx; \
53 int##idxbits##_t arb_min_idx; \
54 int##idxbits##_t arb_max_idx; \
55 struct type arb_nodes[]; \
57 #define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8)
58 #define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16)
59 #define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32)
61 #define ARB_ALLOCSIZE(head, maxn, x) \
62 (sizeof(*head) + (maxn) * sizeof(*x))
64 #define ARB_INITIALIZER(name, maxn) \
65 ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \
66 ARB_NULLIDX, ARB_NULLIDX })
68 #define ARB_INIT(x, field, head, maxn) \
69 (head)->arb_curnodes = 0; \
70 (head)->arb_maxnodes = (maxn); \
71 (head)->arb_root_idx = (head)->arb_free_idx = \
72 (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \
73 /* The ARB_RETURNFREE() puts all entries on the free list. */ \
74 ARB_ARRFOREACH_REVWCOND(x, field, head, \
75 ARB_RETURNFREE(head, x, field))
77 #define ARB_ENTRY(idxbits) \
79 int##idxbits##_t arbe_parent_idx; \
80 int##idxbits##_t arbe_left_idx; \
81 int##idxbits##_t arbe_right_idx; \
84 #define ARB8_ENTRY() ARB_ENTRY(8)
85 #define ARB16_ENTRY() ARB_ENTRY(16)
86 #define ARB32_ENTRY() ARB_ENTRY(32)
88 #define ARB_ENTRYINIT(elm, field) do { \
89 (elm)->field.arbe_parent_idx = \
90 (elm)->field.arbe_left_idx = \
91 (elm)->field.arbe_right_idx = ARB_NULLIDX; \
92 (elm)->field.arbe_color = ARB_NULLCOL; \
93 } while (/*CONSTCOND*/ 0)
95 #define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0])
96 #define ARB_NODES(head) (head)->arb_nodes
97 #define ARB_MAXNODES(head) (head)->arb_maxnodes
98 #define ARB_CURNODES(head) (head)->arb_curnodes
99 #define ARB_EMPTY(head) ((head)->arb_curnodes == 0)
100 #define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes)
101 #define ARB_CNODE(head, idx) \
102 ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \
103 NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx))))
104 #define ARB_NODE(head, idx) \
105 (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx)))
106 #define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head))
107 #define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field))
108 #define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field))
109 #define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field))
110 #define ARB_FREEIDX(head) (head)->arb_free_idx
111 #define ARB_ROOTIDX(head) (head)->arb_root_idx
112 #define ARB_MINIDX(head) (head)->arb_min_idx
113 #define ARB_MAXIDX(head) (head)->arb_max_idx
114 #define ARB_SELFIDX(head, elm) \
115 ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \
116 ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \
117 (intptr_t)ARB_NULLIDX)
118 #define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx
119 #define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx
120 #define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx
121 #define ARB_COLOR(elm, field) (elm)->field.arbe_color
122 #define ARB_PREVFREE(head, elm, field) \
123 ARB_NODE(head, ARB_PREVFREEIDX(elm, field))
124 #define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field)
125 #define ARB_NEXTFREE(head, elm, field) \
126 ARB_NODE(head, ARB_NEXTFREEIDX(elm, field))
127 #define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field)
128 #define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL)
130 #define ARB_SET(head, elm, parent, field) do { \
131 ARB_PARENTIDX(elm, field) = \
132 parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \
133 ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \
134 ARB_COLOR(elm, field) = ARB_RED; \
135 } while (/*CONSTCOND*/ 0)
137 #define ARB_SET_BLACKRED(black, red, field) do { \
138 ARB_COLOR(black, field) = ARB_BLACK; \
139 ARB_COLOR(red, field) = ARB_RED; \
140 } while (/*CONSTCOND*/ 0)
143 #define ARB_AUGMENT(x) do {} while (0)
146 #define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \
147 __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \
148 (tmp) = ARB_RIGHT(head, elm, field); \
149 _tmpidx = ARB_RIGHTIDX(elm, field); \
150 ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \
151 if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \
152 ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \
153 ARB_SELFIDX(head, elm); \
156 ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
157 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
158 if (ARB_SELFIDX(head, elm) == \
159 ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
160 ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
163 ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
166 ARB_ROOTIDX(head) = _tmpidx; \
167 ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
168 ARB_PARENTIDX(elm, field) = _tmpidx; \
170 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
171 ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
172 } while (/*CONSTCOND*/ 0)
174 #define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \
175 __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \
176 (tmp) = ARB_LEFT(head, elm, field); \
177 _tmpidx = ARB_LEFTIDX(elm, field); \
178 ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \
179 if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \
180 ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \
181 ARB_SELFIDX(head, elm); \
184 ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
185 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
186 if (ARB_SELFIDX(head, elm) == \
187 ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
188 ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
191 ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
194 ARB_ROOTIDX(head) = _tmpidx; \
195 ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
196 ARB_PARENTIDX(elm, field) = _tmpidx; \
198 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
199 ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
200 } while (/*CONSTCOND*/ 0)
202 #define ARB_RETURNFREE(head, elm, field) \
204 ARB_COLOR(elm, field) = ARB_NULLCOL; \
205 ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \
206 ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \
210 #define ARB_GETFREEAT(head, field, fidx) \
212 __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \
214 if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \
215 /* Populate the free list. */ \
216 ARB_ARRFOREACH_REVERSE(_elm, field, head) { \
217 if (ARB_ISFREE(_elm, field)) \
218 ARB_RETURNFREE(head, _elm, field); \
221 _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \
222 for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \
223 _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \
226 ARB_FREEIDX(head) = \
227 ARB_NEXTFREEIDX(_elm, field); \
229 ARB_NEXTFREEIDX(_prevelm, field) = \
230 ARB_NEXTFREEIDX(_elm, field); \
234 #define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0)
236 /* Generates prototypes and inline functions */
237 #define ARB_PROTOTYPE(name, type, field, cmp) \
238 ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
239 #define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \
240 ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
241 #define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
242 ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
243 ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
244 ARB_PROTOTYPE_INSERT(name, type, attr); \
245 ARB_PROTOTYPE_REMOVE(name, type, attr); \
246 ARB_PROTOTYPE_CFIND(name, type, attr); \
247 ARB_PROTOTYPE_FIND(name, type, attr); \
248 ARB_PROTOTYPE_NFIND(name, type, attr); \
249 ARB_PROTOTYPE_CNEXT(name, type, attr); \
250 ARB_PROTOTYPE_NEXT(name, type, attr); \
251 ARB_PROTOTYPE_CPREV(name, type, attr); \
252 ARB_PROTOTYPE_PREV(name, type, attr); \
253 ARB_PROTOTYPE_CMINMAX(name, type, attr); \
254 ARB_PROTOTYPE_MINMAX(name, type, attr); \
255 ARB_PROTOTYPE_REINSERT(name, type, attr);
256 #define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
257 attr void name##_ARB_INSERT_COLOR(struct name *, struct type *)
258 #define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
259 attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *)
260 #define ARB_PROTOTYPE_REMOVE(name, type, attr) \
261 attr struct type *name##_ARB_REMOVE(struct name *, struct type *)
262 #define ARB_PROTOTYPE_INSERT(name, type, attr) \
263 attr struct type *name##_ARB_INSERT(struct name *, struct type *)
264 #define ARB_PROTOTYPE_CFIND(name, type, attr) \
265 attr const struct type *name##_ARB_CFIND(const struct name *, \
267 #define ARB_PROTOTYPE_FIND(name, type, attr) \
268 attr struct type *name##_ARB_FIND(const struct name *, \
270 #define ARB_PROTOTYPE_NFIND(name, type, attr) \
271 attr struct type *name##_ARB_NFIND(struct name *, struct type *)
272 #define ARB_PROTOTYPE_CNFIND(name, type, attr) \
273 attr const struct type *name##_ARB_CNFIND(const struct name *, \
275 #define ARB_PROTOTYPE_CNEXT(name, type, attr) \
276 attr const struct type *name##_ARB_CNEXT(const struct name *head,\
278 #define ARB_PROTOTYPE_NEXT(name, type, attr) \
279 attr struct type *name##_ARB_NEXT(const struct name *, \
281 #define ARB_PROTOTYPE_CPREV(name, type, attr) \
282 attr const struct type *name##_ARB_CPREV(const struct name *, \
284 #define ARB_PROTOTYPE_PREV(name, type, attr) \
285 attr struct type *name##_ARB_PREV(const struct name *, \
287 #define ARB_PROTOTYPE_CMINMAX(name, type, attr) \
288 attr const struct type *name##_ARB_CMINMAX(const struct name *, int)
289 #define ARB_PROTOTYPE_MINMAX(name, type, attr) \
290 attr struct type *name##_ARB_MINMAX(const struct name *, int)
291 #define ARB_PROTOTYPE_REINSERT(name, type, attr) \
292 attr struct type *name##_ARB_REINSERT(struct name *, struct type *)
294 #define ARB_GENERATE(name, type, field, cmp) \
295 ARB_GENERATE_INTERNAL(name, type, field, cmp,)
296 #define ARB_GENERATE_STATIC(name, type, field, cmp) \
297 ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
298 #define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
299 ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
300 ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
301 ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
302 ARB_GENERATE_REMOVE(name, type, field, attr) \
303 ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
304 ARB_GENERATE_FIND(name, type, field, cmp, attr) \
305 ARB_GENERATE_CNEXT(name, type, field, attr) \
306 ARB_GENERATE_NEXT(name, type, field, attr) \
307 ARB_GENERATE_CPREV(name, type, field, attr) \
308 ARB_GENERATE_PREV(name, type, field, attr) \
309 ARB_GENERATE_CMINMAX(name, type, field, attr) \
310 ARB_GENERATE_MINMAX(name, type, field, attr) \
311 ARB_GENERATE_REINSERT(name, type, field, cmp, attr)
313 #define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
315 name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \
317 struct type *parent, *gparent, *tmp; \
318 while ((parent = ARB_PARENT(head, elm, field)) != NULL && \
319 ARB_COLOR(parent, field) == ARB_RED) { \
320 gparent = ARB_PARENT(head, parent, field); \
321 if (parent == ARB_LEFT(head, gparent, field)) { \
322 tmp = ARB_RIGHT(head, gparent, field); \
323 if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \
324 ARB_COLOR(tmp, field) = ARB_BLACK; \
325 ARB_SET_BLACKRED(parent, gparent, field); \
329 if (ARB_RIGHT(head, parent, field) == elm) { \
330 ARB_ROTATE_LEFT(head, parent, tmp, field); \
335 ARB_SET_BLACKRED(parent, gparent, field); \
336 ARB_ROTATE_RIGHT(head, gparent, tmp, field); \
338 tmp = ARB_LEFT(head, gparent, field); \
339 if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \
340 ARB_COLOR(tmp, field) = ARB_BLACK; \
341 ARB_SET_BLACKRED(parent, gparent, field); \
345 if (ARB_LEFT(head, parent, field) == elm) { \
346 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
351 ARB_SET_BLACKRED(parent, gparent, field); \
352 ARB_ROTATE_LEFT(head, gparent, tmp, field); \
355 ARB_COLOR(ARB_ROOT(head), field) = ARB_BLACK; \
358 #define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
360 name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
363 while ((elm == NULL || ARB_COLOR(elm, field) == ARB_BLACK) && \
364 elm != ARB_ROOT(head)) { \
365 if (ARB_LEFT(head, parent, field) == elm) { \
366 tmp = ARB_RIGHT(head, parent, field); \
367 if (ARB_COLOR(tmp, field) == ARB_RED) { \
368 ARB_SET_BLACKRED(tmp, parent, field); \
369 ARB_ROTATE_LEFT(head, parent, tmp, field); \
370 tmp = ARB_RIGHT(head, parent, field); \
372 if ((ARB_LEFT(head, tmp, field) == NULL || \
373 ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
374 (ARB_RIGHT(head, tmp, field) == NULL || \
375 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
376 ARB_COLOR(tmp, field) = ARB_RED; \
378 parent = ARB_PARENT(head, elm, field); \
380 if (ARB_RIGHT(head, tmp, field) == NULL || \
381 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK) { \
382 struct type *oleft; \
383 if ((oleft = ARB_LEFT(head, tmp, field)) \
385 ARB_COLOR(oleft, field) = ARB_BLACK; \
386 ARB_COLOR(tmp, field) = ARB_RED; \
387 ARB_ROTATE_RIGHT(head, tmp, oleft, field); \
388 tmp = ARB_RIGHT(head, parent, field); \
390 ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
391 ARB_COLOR(parent, field) = ARB_BLACK; \
392 if (ARB_RIGHT(head, tmp, field)) \
393 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_BLACK; \
394 ARB_ROTATE_LEFT(head, parent, tmp, field); \
395 elm = ARB_ROOT(head); \
399 tmp = ARB_LEFT(head, parent, field); \
400 if (ARB_COLOR(tmp, field) == ARB_RED) { \
401 ARB_SET_BLACKRED(tmp, parent, field); \
402 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
403 tmp = ARB_LEFT(head, parent, field); \
405 if ((ARB_LEFT(head, tmp, field) == NULL || \
406 ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
407 (ARB_RIGHT(head, tmp, field) == NULL || \
408 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
409 ARB_COLOR(tmp, field) = ARB_RED; \
411 parent = ARB_PARENT(head, elm, field); \
413 if (ARB_LEFT(head, tmp, field) == NULL || \
414 ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) { \
415 struct type *oright; \
416 if ((oright = ARB_RIGHT(head, tmp, field)) \
418 ARB_COLOR(oright, field) = ARB_BLACK; \
419 ARB_COLOR(tmp, field) = ARB_RED; \
420 ARB_ROTATE_LEFT(head, tmp, oright, field); \
421 tmp = ARB_LEFT(head, parent, field); \
423 ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
424 ARB_COLOR(parent, field) = ARB_BLACK; \
425 if (ARB_LEFT(head, tmp, field)) \
426 ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \
427 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
428 elm = ARB_ROOT(head); \
434 ARB_COLOR(elm, field) = ARB_BLACK; \
437 #define ARB_GENERATE_REMOVE(name, type, field, attr) \
439 name##_ARB_REMOVE(struct name *head, struct type *elm) \
441 struct type *child, *parent, *old = elm; \
443 if (ARB_LEFT(head, elm, field) == NULL) \
444 child = ARB_RIGHT(head, elm, field); \
445 else if (ARB_RIGHT(head, elm, field) == NULL) \
446 child = ARB_LEFT(head, elm, field); \
449 elm = ARB_RIGHT(head, elm, field); \
450 while ((left = ARB_LEFT(head, elm, field)) != NULL) \
452 child = ARB_RIGHT(head, elm, field); \
453 parent = ARB_PARENT(head, elm, field); \
454 color = ARB_COLOR(elm, field); \
456 ARB_PARENTIDX(child, field) = \
457 ARB_SELFIDX(head, parent); \
459 if (ARB_LEFT(head, parent, field) == elm) \
460 ARB_LEFTIDX(parent, field) = \
461 ARB_SELFIDX(head, child); \
463 ARB_RIGHTIDX(parent, field) = \
464 ARB_SELFIDX(head, child); \
465 ARB_AUGMENT(parent); \
467 ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
468 if (ARB_PARENT(head, elm, field) == old) \
470 (elm)->field = (old)->field; \
471 if (ARB_PARENT(head, old, field)) { \
472 if (ARB_LEFT(head, ARB_PARENT(head, old, field), \
474 ARB_LEFTIDX(ARB_PARENT(head, old, field), \
475 field) = ARB_SELFIDX(head, elm); \
477 ARB_RIGHTIDX(ARB_PARENT(head, old, field),\
478 field) = ARB_SELFIDX(head, elm); \
479 ARB_AUGMENT(ARB_PARENT(head, old, field)); \
481 ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
482 ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \
483 ARB_SELFIDX(head, elm); \
484 if (ARB_RIGHT(head, old, field)) \
485 ARB_PARENTIDX(ARB_RIGHT(head, old, field), \
486 field) = ARB_SELFIDX(head, elm); \
491 } while ((left = ARB_PARENT(head, left, field)) \
496 parent = ARB_PARENT(head, elm, field); \
497 color = ARB_COLOR(elm, field); \
499 ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\
501 if (ARB_LEFT(head, parent, field) == elm) \
502 ARB_LEFTIDX(parent, field) = \
503 ARB_SELFIDX(head, child); \
505 ARB_RIGHTIDX(parent, field) = \
506 ARB_SELFIDX(head, child); \
507 ARB_AUGMENT(parent); \
509 ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
511 if (color == ARB_BLACK) \
512 name##_ARB_REMOVE_COLOR(head, parent, child); \
513 ARB_CURNODES(head) -= 1; \
514 if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \
515 ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \
516 if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \
517 ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \
518 ARB_RETURNFREE(head, old, field); \
522 #define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
523 /* Inserts a node into the RB tree */ \
525 name##_ARB_INSERT(struct name *head, struct type *elm) \
528 struct type *parent = NULL; \
530 tmp = ARB_ROOT(head); \
533 comp = (cmp)(elm, parent); \
535 tmp = ARB_LEFT(head, tmp, field); \
537 tmp = ARB_RIGHT(head, tmp, field); \
541 ARB_SET(head, elm, parent, field); \
542 if (parent != NULL) { \
544 ARB_LEFTIDX(parent, field) = \
545 ARB_SELFIDX(head, elm); \
547 ARB_RIGHTIDX(parent, field) = \
548 ARB_SELFIDX(head, elm); \
549 ARB_AUGMENT(parent); \
551 ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
552 name##_ARB_INSERT_COLOR(head, elm); \
553 ARB_CURNODES(head) += 1; \
554 if (ARB_MINIDX(head) == ARB_NULLIDX || \
555 (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \
556 ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
557 ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \
558 if (ARB_MAXIDX(head) == ARB_NULLIDX || \
559 (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \
560 ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
561 ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \
565 #define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
566 /* Finds the node with the same key as elm */ \
567 attr const struct type * \
568 name##_ARB_CFIND(const struct name *head, const struct type *elm) \
570 const struct type *tmp = ARB_ROOT(head); \
573 comp = cmp(elm, tmp); \
575 tmp = ARB_LEFT(head, tmp, field); \
577 tmp = ARB_RIGHT(head, tmp, field); \
584 #define ARB_GENERATE_FIND(name, type, field, cmp, attr) \
586 name##_ARB_FIND(const struct name *head, const struct type *elm) \
587 { return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); }
589 #define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \
590 /* Finds the first node greater than or equal to the search key */ \
591 attr const struct type * \
592 name##_ARB_CNFIND(const struct name *head, const struct type *elm) \
594 const struct type *tmp = ARB_ROOT(head); \
595 const struct type *res = NULL; \
598 comp = cmp(elm, tmp); \
601 tmp = ARB_LEFT(head, tmp, field); \
604 tmp = ARB_RIGHT(head, tmp, field); \
611 #define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \
613 name##_ARB_NFIND(const struct name *head, const struct type *elm) \
614 { return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); }
616 #define ARB_GENERATE_CNEXT(name, type, field, attr) \
618 attr const struct type * \
619 name##_ARB_CNEXT(const struct name *head, const struct type *elm) \
621 if (ARB_RIGHT(head, elm, field)) { \
622 elm = ARB_RIGHT(head, elm, field); \
623 while (ARB_LEFT(head, elm, field)) \
624 elm = ARB_LEFT(head, elm, field); \
626 if (ARB_PARENT(head, elm, field) && \
627 (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\
629 elm = ARB_PARENT(head, elm, field); \
631 while (ARB_PARENT(head, elm, field) && \
632 (elm == ARB_RIGHT(head, ARB_PARENT(head, \
633 elm, field), field))) \
634 elm = ARB_PARENT(head, elm, field); \
635 elm = ARB_PARENT(head, elm, field); \
641 #define ARB_GENERATE_NEXT(name, type, field, attr) \
643 name##_ARB_NEXT(const struct name *head, const struct type *elm) \
644 { return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); }
646 #define ARB_GENERATE_CPREV(name, type, field, attr) \
648 attr const struct type * \
649 name##_ARB_CPREV(const struct name *head, const struct type *elm) \
651 if (ARB_LEFT(head, elm, field)) { \
652 elm = ARB_LEFT(head, elm, field); \
653 while (ARB_RIGHT(head, elm, field)) \
654 elm = ARB_RIGHT(head, elm, field); \
656 if (ARB_PARENT(head, elm, field) && \
657 (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \
659 elm = ARB_PARENT(head, elm, field); \
661 while (ARB_PARENT(head, elm, field) && \
662 (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\
664 elm = ARB_PARENT(head, elm, field); \
665 elm = ARB_PARENT(head, elm, field); \
671 #define ARB_GENERATE_PREV(name, type, field, attr) \
673 name##_ARB_PREV(const struct name *head, const struct type *elm) \
674 { return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); }
676 #define ARB_GENERATE_CMINMAX(name, type, field, attr) \
677 attr const struct type * \
678 name##_ARB_CMINMAX(const struct name *head, int val) \
680 const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\
681 const struct type *parent = NULL; \
685 tmp = ARB_LEFT(head, tmp, field); \
687 tmp = ARB_RIGHT(head, tmp, field); \
689 return (__DECONST(struct type *, parent)); \
692 #define ARB_GENERATE_MINMAX(name, type, field, attr) \
694 name##_ARB_MINMAX(const struct name *head, int val) \
695 { return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); }
697 #define ARB_GENERATE_REINSERT(name, type, field, cmp, attr) \
699 name##_ARB_REINSERT(struct name *head, struct type *elm) \
701 struct type *cmpelm; \
702 if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \
703 (cmp)(cmpelm, elm) >= 0) || \
704 ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \
705 (cmp)(elm, cmpelm) >= 0)) { \
706 /* XXXLAS: Remove/insert is heavy handed. */ \
707 ARB_REMOVE(name, head, elm); \
708 /* Remove puts elm on the free list. */ \
709 elm = ARB_GETFREE(head, field); \
710 return (ARB_INSERT(name, head, elm)); \
715 #define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y)
716 #define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y)
717 #define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y)
718 #define ARB_FIND(name, x, y) name##_ARB_FIND(x, y)
719 #define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y)
720 #define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y)
721 #define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y)
722 #define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y)
723 #define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y)
724 #define ARB_PREV(name, x, y) name##_ARB_PREV(x, y)
725 #define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
726 name##_ARB_CMINMAX(x, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x)))
727 #define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
728 name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x)))
729 #define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
730 name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x)))
731 #define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
732 name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x)))
733 #define ARB_REINSERT(name, x, y) name##_ARB_REINSERT(x, y)
735 #define ARB_FOREACH(x, name, head) \
736 for ((x) = ARB_MIN(name, head); \
738 (x) = name##_ARB_NEXT(head, x))
740 #define ARB_FOREACH_FROM(x, name, y) \
742 ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
745 #define ARB_FOREACH_SAFE(x, name, head, y) \
746 for ((x) = ARB_MIN(name, head); \
747 ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
750 #define ARB_FOREACH_REVERSE(x, name, head) \
751 for ((x) = ARB_MAX(name, head); \
753 (x) = name##_ARB_PREV(x))
755 #define ARB_FOREACH_REVERSE_FROM(x, name, y) \
757 ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
760 #define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \
761 for ((x) = ARB_MAX(name, head); \
762 ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
765 #define ARB_ARRFOREACH(x, field, head) \
766 for ((x) = ARB_NODES(head); \
767 ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \
770 #define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \
771 for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \
772 (x) >= ARB_NODES(head) && (extracond); \
775 #define ARB_ARRFOREACH_REVERSE(x, field, head) \
776 ARB_ARRFOREACH_REVWCOND(x, field, head, 1)
778 #define ARB_RESET_TREE(head, name, maxn) \
779 *(head) = ARB_INITIALIZER(name, maxn)
781 #endif /* _SYS_ARB_H_ */