1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
5 * Copyright 2018-2019 Netflix, Inc.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
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.
16 *
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.
27 */
28
29#ifndef _SYS_ARB_H_
30#define _SYS_ARB_H_
31
32#include <sys/cdefs.h>
33
34/* Array-based red-black trees. */
35
36#define ARB_NULLIDX -1
37#define ARB_NULLCOL -1
38
39#define ARB_BLACK 0
40#define ARB_RED 1
41
42#define ARB_NEGINF -1
43#define ARB_INF 1
44
45#define ARB_HEAD(name, type, idxbits) \
46struct name { \
47 int##idxbits##_t arb_curnodes; \
48 int##idxbits##_t arb_maxnodes; \
49 int##idxbits##_t arb_root_idx; \
50 int##idxbits##_t arb_free_idx; \
51 int##idxbits##_t arb_min_idx; \
52 int##idxbits##_t arb_max_idx; \
53 struct type arb_nodes[]; \
54}
55#define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8)
56#define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16)
57#define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32)
58
59#define ARB_ALLOCSIZE(head, maxn, x) \
60 (sizeof(*head) + (maxn) * sizeof(*x))
61
62#define ARB_INITIALIZER(name, maxn) \
63 ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \
64 ARB_NULLIDX, ARB_NULLIDX })
65
66#define ARB_INIT(x, field, head, maxn) \
67 (head)->arb_curnodes = 0; \
68 (head)->arb_maxnodes = (maxn); \
69 (head)->arb_root_idx = (head)->arb_free_idx = \
70 (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \
71 /* The ARB_RETURNFREE() puts all entries on the free list. */ \
72 ARB_ARRFOREACH_REVWCOND(x, field, head, \
73 ARB_RETURNFREE(head, x, field))
74
75#define ARB_ENTRY(idxbits) \
76struct { \
77 int##idxbits##_t arbe_parent_idx; \
78 int##idxbits##_t arbe_left_idx; \
79 int##idxbits##_t arbe_right_idx; \
80 int8_t arbe_color; \
81}
82#define ARB8_ENTRY() ARB_ENTRY(8)
83#define ARB16_ENTRY() ARB_ENTRY(16)
84#define ARB32_ENTRY() ARB_ENTRY(32)
85
86#define ARB_ENTRYINIT(elm, field) do { \
87 (elm)->field.arbe_parent_idx = \
88 (elm)->field.arbe_left_idx = \
89 (elm)->field.arbe_right_idx = ARB_NULLIDX; \
90 (elm)->field.arbe_color = ARB_NULLCOL; \
91} while (/*CONSTCOND*/ 0)
92
93#define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0])
94#define ARB_NODES(head) (head)->arb_nodes
95#define ARB_MAXNODES(head) (head)->arb_maxnodes
96#define ARB_CURNODES(head) (head)->arb_curnodes
97#define ARB_EMPTY(head) ((head)->arb_curnodes == 0)
98#define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes)
99#define ARB_CNODE(head, idx) \
100 ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \
101 NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx))))
102#define ARB_NODE(head, idx) \
103 (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx)))
104#define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head))
105#define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field))
106#define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field))
107#define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field))
108#define ARB_FREEIDX(head) (head)->arb_free_idx
109#define ARB_ROOTIDX(head) (head)->arb_root_idx
110#define ARB_MINIDX(head) (head)->arb_min_idx
111#define ARB_MAXIDX(head) (head)->arb_max_idx
112#define ARB_SELFIDX(head, elm) \
113 ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \
114 ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \
115 (intptr_t)ARB_NULLIDX)
116#define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx
117#define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx
118#define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx
119#define ARB_COLOR(elm, field) (elm)->field.arbe_color
120#define ARB_PREVFREE(head, elm, field) \
121 ARB_NODE(head, ARB_PREVFREEIDX(elm, field))
122#define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field)
123#define ARB_NEXTFREE(head, elm, field) \
124 ARB_NODE(head, ARB_NEXTFREEIDX(elm, field))
125#define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field)
126#define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL)
127
128#define ARB_SET(head, elm, parent, field) do { \
129 ARB_PARENTIDX(elm, field) = \
130 parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \
131 ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \
132 ARB_COLOR(elm, field) = ARB_RED; \
133} while (/*CONSTCOND*/ 0)
134
135#define ARB_SET_BLACKRED(black, red, field) do { \
136 ARB_COLOR(black, field) = ARB_BLACK; \
137 ARB_COLOR(red, field) = ARB_RED; \
138} while (/*CONSTCOND*/ 0)
139
140#ifndef ARB_AUGMENT
141#define ARB_AUGMENT(x) do {} while (0)
142#endif
143
144#define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \
145 __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \
146 (tmp) = ARB_RIGHT(head, elm, field); \
147 _tmpidx = ARB_RIGHTIDX(elm, field); \
148 ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \
149 if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \
150 ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \
151 ARB_SELFIDX(head, elm); \
152 } \
153 ARB_AUGMENT(elm); \
154 ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
155 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
156 if (ARB_SELFIDX(head, elm) == \
157 ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
158 ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
159 field) = _tmpidx; \
160 else \
161 ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
162 field) = _tmpidx; \
163 } else \
164 ARB_ROOTIDX(head) = _tmpidx; \
165 ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
166 ARB_PARENTIDX(elm, field) = _tmpidx; \
167 ARB_AUGMENT(tmp); \
168 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
169 ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
170} while (/*CONSTCOND*/ 0)
171
172#define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \
173 __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \
174 (tmp) = ARB_LEFT(head, elm, field); \
175 _tmpidx = ARB_LEFTIDX(elm, field); \
176 ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \
177 if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \
178 ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \
179 ARB_SELFIDX(head, elm); \
180 } \
181 ARB_AUGMENT(elm); \
182 ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
183 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
184 if (ARB_SELFIDX(head, elm) == \
185 ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
186 ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
187 field) = _tmpidx; \
188 else \
189 ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
190 field) = _tmpidx; \
191 } else \
192 ARB_ROOTIDX(head) = _tmpidx; \
193 ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
194 ARB_PARENTIDX(elm, field) = _tmpidx; \
195 ARB_AUGMENT(tmp); \
196 if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
197 ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
198} while (/*CONSTCOND*/ 0)
199
200#define ARB_RETURNFREE(head, elm, field) \
201({ \
202 ARB_COLOR(elm, field) = ARB_NULLCOL; \
203 ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \
204 ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \
205 elm; \
206})
207
208#define ARB_GETFREEAT(head, field, fidx) \
209({ \
210 __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \
211 int _idx = fidx; \
212 if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \
213 /* Populate the free list. */ \
214 ARB_ARRFOREACH_REVERSE(_elm, field, head) { \
215 if (ARB_ISFREE(_elm, field)) \
216 ARB_RETURNFREE(head, _elm, field); \
217 } \
218 } \
219 _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \
220 for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \
221 _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \
222 if (_elm) { \
223 if (fidx == 0) \
224 ARB_FREEIDX(head) = \
225 ARB_NEXTFREEIDX(_elm, field); \
226 else \
227 ARB_NEXTFREEIDX(_prevelm, field) = \
228 ARB_NEXTFREEIDX(_elm, field); \
229 } \
230 _elm; \
231})
232#define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0)
233
234/* Generates prototypes and inline functions */
235#define ARB_PROTOTYPE(name, type, field, cmp) \
236 ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
237#define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \
238 ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
239#define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
240 ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
241 ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
242 ARB_PROTOTYPE_INSERT(name, type, attr); \
243 ARB_PROTOTYPE_REMOVE(name, type, attr); \
244 ARB_PROTOTYPE_CFIND(name, type, attr); \
245 ARB_PROTOTYPE_FIND(name, type, attr); \
246 ARB_PROTOTYPE_NFIND(name, type, attr); \
247 ARB_PROTOTYPE_CNEXT(name, type, attr); \
248 ARB_PROTOTYPE_NEXT(name, type, attr); \
249 ARB_PROTOTYPE_CPREV(name, type, attr); \
250 ARB_PROTOTYPE_PREV(name, type, attr); \
251 ARB_PROTOTYPE_CMINMAX(name, type, attr); \
252 ARB_PROTOTYPE_MINMAX(name, type, attr); \
253 ARB_PROTOTYPE_REINSERT(name, type, attr);
254#define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
255 attr void name##_ARB_INSERT_COLOR(struct name *, struct type *)
256#define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
257 attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *)
258#define ARB_PROTOTYPE_REMOVE(name, type, attr) \
259 attr struct type *name##_ARB_REMOVE(struct name *, struct type *)
260#define ARB_PROTOTYPE_INSERT(name, type, attr) \
261 attr struct type *name##_ARB_INSERT(struct name *, struct type *)
262#define ARB_PROTOTYPE_CFIND(name, type, attr) \
263 attr const struct type *name##_ARB_CFIND(const struct name *, \
264 const struct type *)
265#define ARB_PROTOTYPE_FIND(name, type, attr) \
266 attr struct type *name##_ARB_FIND(const struct name *, \
267 const struct type *)
268#define ARB_PROTOTYPE_NFIND(name, type, attr) \
269 attr struct type *name##_ARB_NFIND(struct name *, struct type *)
270#define ARB_PROTOTYPE_CNFIND(name, type, attr) \
271 attr const struct type *name##_ARB_CNFIND(const struct name *, \
272 const struct type *)
273#define ARB_PROTOTYPE_CNEXT(name, type, attr) \
274 attr const struct type *name##_ARB_CNEXT(const struct name *head,\
275 const struct type *)
276#define ARB_PROTOTYPE_NEXT(name, type, attr) \
277 attr struct type *name##_ARB_NEXT(const struct name *, \
278 const struct type *)
279#define ARB_PROTOTYPE_CPREV(name, type, attr) \
280 attr const struct type *name##_ARB_CPREV(const struct name *, \
281 const struct type *)
282#define ARB_PROTOTYPE_PREV(name, type, attr) \
283 attr struct type *name##_ARB_PREV(const struct name *, \
284 const struct type *)
285#define ARB_PROTOTYPE_CMINMAX(name, type, attr) \
286 attr const struct type *name##_ARB_CMINMAX(const struct name *, int)
287#define ARB_PROTOTYPE_MINMAX(name, type, attr) \
288 attr struct type *name##_ARB_MINMAX(const struct name *, int)
289#define ARB_PROTOTYPE_REINSERT(name, type, attr) \
290 attr struct type *name##_ARB_REINSERT(struct name *, struct type *)
291
292#define ARB_GENERATE(name, type, field, cmp) \
293 ARB_GENERATE_INTERNAL(name, type, field, cmp,)
294#define ARB_GENERATE_STATIC(name, type, field, cmp) \
295 ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
296#define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
297 ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
298 ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
299 ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
300 ARB_GENERATE_REMOVE(name, type, field, attr) \
301 ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
302 ARB_GENERATE_FIND(name, type, field, cmp, attr) \
303 ARB_GENERATE_CNEXT(name, type, field, attr) \
304 ARB_GENERATE_NEXT(name, type, field, attr) \
305 ARB_GENERATE_CPREV(name, type, field, attr) \
306 ARB_GENERATE_PREV(name, type, field, attr) \
307 ARB_GENERATE_CMINMAX(name, type, field, attr) \
308 ARB_GENERATE_MINMAX(name, type, field, attr) \
309 ARB_GENERATE_REINSERT(name, type, field, cmp, attr)
310
311#define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
312attr void \
313name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \
314{ \
315 struct type *parent, *gparent, *tmp; \
316 while ((parent = ARB_PARENT(head, elm, field)) != NULL && \
317 ARB_COLOR(parent, field) == ARB_RED) { \
318 gparent = ARB_PARENT(head, parent, field); \
319 if (parent == ARB_LEFT(head, gparent, field)) { \
320 tmp = ARB_RIGHT(head, gparent, field); \
321 if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \
322 ARB_COLOR(tmp, field) = ARB_BLACK; \
323 ARB_SET_BLACKRED(parent, gparent, field); \
324 elm = gparent; \
325 continue; \
326 } \
327 if (ARB_RIGHT(head, parent, field) == elm) { \
328 ARB_ROTATE_LEFT(head, parent, tmp, field); \
329 tmp = parent; \
330 parent = elm; \
331 elm = tmp; \
332 } \
333 ARB_SET_BLACKRED(parent, gparent, field); \
334 ARB_ROTATE_RIGHT(head, gparent, tmp, field); \
335 } else { \
336 tmp = ARB_LEFT(head, gparent, field); \
337 if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \
338 ARB_COLOR(tmp, field) = ARB_BLACK; \
339 ARB_SET_BLACKRED(parent, gparent, field); \
340 elm = gparent; \
341 continue; \
342 } \
343 if (ARB_LEFT(head, parent, field) == elm) { \
344 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
345 tmp = parent; \
346 parent = elm; \
347 elm = tmp; \
348 } \
349 ARB_SET_BLACKRED(parent, gparent, field); \
350 ARB_ROTATE_LEFT(head, gparent, tmp, field); \
351 } \
352 } \
353 ARB_COLOR(ARB_ROOT(head), field) = ARB_BLACK; \
354}
355
356#define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
357attr void \
358name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
359{ \
360 struct type *tmp; \
361 while ((elm == NULL || ARB_COLOR(elm, field) == ARB_BLACK) && \
362 elm != ARB_ROOT(head)) { \
363 if (ARB_LEFT(head, parent, field) == elm) { \
364 tmp = ARB_RIGHT(head, parent, field); \
365 if (ARB_COLOR(tmp, field) == ARB_RED) { \
366 ARB_SET_BLACKRED(tmp, parent, field); \
367 ARB_ROTATE_LEFT(head, parent, tmp, field); \
368 tmp = ARB_RIGHT(head, parent, field); \
369 } \
370 if ((ARB_LEFT(head, tmp, field) == NULL || \
371 ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
372 (ARB_RIGHT(head, tmp, field) == NULL || \
373 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
374 ARB_COLOR(tmp, field) = ARB_RED; \
375 elm = parent; \
376 parent = ARB_PARENT(head, elm, field); \
377 } else { \
378 if (ARB_RIGHT(head, tmp, field) == NULL || \
379 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK) { \
380 struct type *oleft; \
381 if ((oleft = ARB_LEFT(head, tmp, field)) \
382 != NULL) \
383 ARB_COLOR(oleft, field) = ARB_BLACK; \
384 ARB_COLOR(tmp, field) = ARB_RED; \
385 ARB_ROTATE_RIGHT(head, tmp, oleft, field); \
386 tmp = ARB_RIGHT(head, parent, field); \
387 } \
388 ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
389 ARB_COLOR(parent, field) = ARB_BLACK; \
390 if (ARB_RIGHT(head, tmp, field)) \
391 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_BLACK; \
392 ARB_ROTATE_LEFT(head, parent, tmp, field); \
393 elm = ARB_ROOT(head); \
394 break; \
395 } \
396 } else { \
397 tmp = ARB_LEFT(head, parent, field); \
398 if (ARB_COLOR(tmp, field) == ARB_RED) { \
399 ARB_SET_BLACKRED(tmp, parent, field); \
400 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
401 tmp = ARB_LEFT(head, parent, field); \
402 } \
403 if ((ARB_LEFT(head, tmp, field) == NULL || \
404 ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
405 (ARB_RIGHT(head, tmp, field) == NULL || \
406 ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
407 ARB_COLOR(tmp, field) = ARB_RED; \
408 elm = parent; \
409 parent = ARB_PARENT(head, elm, field); \
410 } else { \
411 if (ARB_LEFT(head, tmp, field) == NULL || \
412 ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) { \
413 struct type *oright; \
414 if ((oright = ARB_RIGHT(head, tmp, field)) \
415 != NULL) \
416 ARB_COLOR(oright, field) = ARB_BLACK; \
417 ARB_COLOR(tmp, field) = ARB_RED; \
418 ARB_ROTATE_LEFT(head, tmp, oright, field); \
419 tmp = ARB_LEFT(head, parent, field); \
420 } \
421 ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
422 ARB_COLOR(parent, field) = ARB_BLACK; \
423 if (ARB_LEFT(head, tmp, field)) \
424 ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \
425 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
426 elm = ARB_ROOT(head); \
427 break; \
428 } \
429 } \
430 } \
431 if (elm) \
432 ARB_COLOR(elm, field) = ARB_BLACK; \
433}
434
435#define ARB_GENERATE_REMOVE(name, type, field, attr) \
436attr struct type * \
437name##_ARB_REMOVE(struct name *head, struct type *elm) \
438{ \
439 struct type *child, *parent, *old = elm; \
440 int color; \
441 if (ARB_LEFT(head, elm, field) == NULL) \
442 child = ARB_RIGHT(head, elm, field); \
443 else if (ARB_RIGHT(head, elm, field) == NULL) \
444 child = ARB_LEFT(head, elm, field); \
445 else { \
446 struct type *left; \
447 elm = ARB_RIGHT(head, elm, field); \
448 while ((left = ARB_LEFT(head, elm, field)) != NULL) \
449 elm = left; \
450 child = ARB_RIGHT(head, elm, field); \
451 parent = ARB_PARENT(head, elm, field); \
452 color = ARB_COLOR(elm, field); \
453 if (child) \
454 ARB_PARENTIDX(child, field) = \
455 ARB_SELFIDX(head, parent); \
456 if (parent) { \
457 if (ARB_LEFT(head, parent, field) == elm) \
458 ARB_LEFTIDX(parent, field) = \
459 ARB_SELFIDX(head, child); \
460 else \
461 ARB_RIGHTIDX(parent, field) = \
462 ARB_SELFIDX(head, child); \
463 ARB_AUGMENT(parent); \
464 } else \
465 ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
466 if (ARB_PARENT(head, elm, field) == old) \
467 parent = elm; \
468 (elm)->field = (old)->field; \
469 if (ARB_PARENT(head, old, field)) { \
470 if (ARB_LEFT(head, ARB_PARENT(head, old, field), \
471 field) == old) \
472 ARB_LEFTIDX(ARB_PARENT(head, old, field), \
473 field) = ARB_SELFIDX(head, elm); \
474 else \
475 ARB_RIGHTIDX(ARB_PARENT(head, old, field),\
476 field) = ARB_SELFIDX(head, elm); \
477 ARB_AUGMENT(ARB_PARENT(head, old, field)); \
478 } else \
479 ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
480 ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \
481 ARB_SELFIDX(head, elm); \
482 if (ARB_RIGHT(head, old, field)) \
483 ARB_PARENTIDX(ARB_RIGHT(head, old, field), \
484 field) = ARB_SELFIDX(head, elm); \
485 if (parent) { \
486 left = parent; \
487 do { \
488 ARB_AUGMENT(left); \
489 } while ((left = ARB_PARENT(head, left, field)) \
490 != NULL); \
491 } \
492 goto color; \
493 } \
494 parent = ARB_PARENT(head, elm, field); \
495 color = ARB_COLOR(elm, field); \
496 if (child) \
497 ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\
498 if (parent) { \
499 if (ARB_LEFT(head, parent, field) == elm) \
500 ARB_LEFTIDX(parent, field) = \
501 ARB_SELFIDX(head, child); \
502 else \
503 ARB_RIGHTIDX(parent, field) = \
504 ARB_SELFIDX(head, child); \
505 ARB_AUGMENT(parent); \
506 } else \
507 ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
508color: \
509 if (color == ARB_BLACK) \
510 name##_ARB_REMOVE_COLOR(head, parent, child); \
511 ARB_CURNODES(head) -= 1; \
512 if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \
513 ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \
514 if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \
515 ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \
516 ARB_RETURNFREE(head, old, field); \
517 return (old); \
518} \
519
520#define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
521/* Inserts a node into the RB tree */ \
522attr struct type * \
523name##_ARB_INSERT(struct name *head, struct type *elm) \
524{ \
525 struct type *tmp; \
526 struct type *parent = NULL; \
527 int comp = 0; \
528 tmp = ARB_ROOT(head); \
529 while (tmp) { \
530 parent = tmp; \
531 comp = (cmp)(elm, parent); \
532 if (comp < 0) \
533 tmp = ARB_LEFT(head, tmp, field); \
534 else if (comp > 0) \
535 tmp = ARB_RIGHT(head, tmp, field); \
536 else \
537 return (tmp); \
538 } \
539 ARB_SET(head, elm, parent, field); \
540 if (parent != NULL) { \
541 if (comp < 0) \
542 ARB_LEFTIDX(parent, field) = \
543 ARB_SELFIDX(head, elm); \
544 else \
545 ARB_RIGHTIDX(parent, field) = \
546 ARB_SELFIDX(head, elm); \
547 ARB_AUGMENT(parent); \
548 } else \
549 ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
550 name##_ARB_INSERT_COLOR(head, elm); \
551 ARB_CURNODES(head) += 1; \
552 if (ARB_MINIDX(head) == ARB_NULLIDX || \
553 (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \
554 ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
555 ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \
556 if (ARB_MAXIDX(head) == ARB_NULLIDX || \
557 (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \
558 ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
559 ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \
560 return (NULL); \
561}
562
563#define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
564/* Finds the node with the same key as elm */ \
565attr const struct type * \
566name##_ARB_CFIND(const struct name *head, const struct type *elm) \
567{ \
568 const struct type *tmp = ARB_ROOT(head); \
569 int comp; \
570 while (tmp) { \
571 comp = cmp(elm, tmp); \
572 if (comp < 0) \
573 tmp = ARB_LEFT(head, tmp, field); \
574 else if (comp > 0) \
575 tmp = ARB_RIGHT(head, tmp, field); \
576 else \
577 return (tmp); \
578 } \
579 return (NULL); \
580}
581
582#define ARB_GENERATE_FIND(name, type, field, cmp, attr) \
583attr struct type * \
584name##_ARB_FIND(const struct name *head, const struct type *elm) \
585{ return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); }
586
587#define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \
588/* Finds the first node greater than or equal to the search key */ \
589attr const struct type * \
590name##_ARB_CNFIND(const struct name *head, const struct type *elm) \
591{ \
592 const struct type *tmp = ARB_ROOT(head); \
593 const struct type *res = NULL; \
594 int comp; \
595 while (tmp) { \
596 comp = cmp(elm, tmp); \
597 if (comp < 0) { \
598 res = tmp; \
599 tmp = ARB_LEFT(head, tmp, field); \
600 } \
601 else if (comp > 0) \
602 tmp = ARB_RIGHT(head, tmp, field); \
603 else \
604 return (tmp); \
605 } \
606 return (res); \
607}
608
609#define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \
610attr struct type * \
611name##_ARB_NFIND(const struct name *head, const struct type *elm) \
612{ return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); }
613
614#define ARB_GENERATE_CNEXT(name, type, field, attr) \
615/* ARGSUSED */ \
616attr const struct type * \
617name##_ARB_CNEXT(const struct name *head, const struct type *elm) \
618{ \
619 if (ARB_RIGHT(head, elm, field)) { \
620 elm = ARB_RIGHT(head, elm, field); \
621 while (ARB_LEFT(head, elm, field)) \
622 elm = ARB_LEFT(head, elm, field); \
623 } else { \
624 if (ARB_PARENT(head, elm, field) && \
625 (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\
626 field))) \
627 elm = ARB_PARENT(head, elm, field); \
628 else { \
629 while (ARB_PARENT(head, elm, field) && \
630 (elm == ARB_RIGHT(head, ARB_PARENT(head, \
631 elm, field), field))) \
632 elm = ARB_PARENT(head, elm, field); \
633 elm = ARB_PARENT(head, elm, field); \
634 } \
635 } \
636 return (elm); \
637}
638
639#define ARB_GENERATE_NEXT(name, type, field, attr) \
640attr struct type * \
641name##_ARB_NEXT(const struct name *head, const struct type *elm) \
642{ return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); }
643
644#define ARB_GENERATE_CPREV(name, type, field, attr) \
645/* ARGSUSED */ \
646attr const struct type * \
647name##_ARB_CPREV(const struct name *head, const struct type *elm) \
648{ \
649 if (ARB_LEFT(head, elm, field)) { \
650 elm = ARB_LEFT(head, elm, field); \
651 while (ARB_RIGHT(head, elm, field)) \
652 elm = ARB_RIGHT(head, elm, field); \
653 } else { \
654 if (ARB_PARENT(head, elm, field) && \
655 (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \
656 field), field))) \
657 elm = ARB_PARENT(head, elm, field); \
658 else { \
659 while (ARB_PARENT(head, elm, field) && \
660 (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\
661 field), field))) \
662 elm = ARB_PARENT(head, elm, field); \
663 elm = ARB_PARENT(head, elm, field); \
664 } \
665 } \
666 return (elm); \
667}
668
669#define ARB_GENERATE_PREV(name, type, field, attr) \
670attr struct type * \
671name##_ARB_PREV(const struct name *head, const struct type *elm) \
672{ return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); }
673
674#define ARB_GENERATE_CMINMAX(name, type, field, attr) \
675attr const struct type * \
676name##_ARB_CMINMAX(const struct name *head, int val) \
677{ \
678 const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\
679 const struct type *parent = NULL; \
680 while (tmp) { \
681 parent = tmp; \
682 if (val < 0) \
683 tmp = ARB_LEFT(head, tmp, field); \
684 else \
685 tmp = ARB_RIGHT(head, tmp, field); \
686 } \
687 return (__DECONST(struct type *, parent)); \
688}
689
690#define ARB_GENERATE_MINMAX(name, type, field, attr) \
691attr struct type * \
692name##_ARB_MINMAX(const struct name *head, int val) \
693{ return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); }
694
695#define ARB_GENERATE_REINSERT(name, type, field, cmp, attr) \
696attr struct type * \
697name##_ARB_REINSERT(struct name *head, struct type *elm) \
698{ \
699 struct type *cmpelm; \
700 if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \
701 (cmp)(cmpelm, elm) >= 0) || \
702 ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \
703 (cmp)(elm, cmpelm) >= 0)) { \
704 /* XXXLAS: Remove/insert is heavy handed. */ \
705 ARB_REMOVE(name, head, elm); \
706 /* Remove puts elm on the free list. */ \
707 elm = ARB_GETFREE(head, field); \
708 return (ARB_INSERT(name, head, elm)); \
709 } \
710 return (NULL); \
711} \
712
713#define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y)
714#define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y)
715#define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y)
716#define ARB_FIND(name, x, y) name##_ARB_FIND(x, y)
717#define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y)
718#define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y)
719#define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y)
720#define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y)
721#define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y)
722#define ARB_PREV(name, x, y) name##_ARB_PREV(x, y)
723#define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
724 name##_ARB_CMINMAX(x, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x)))
725#define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
726 name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x)))
727#define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
728 name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x)))
729#define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
730 name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x)))
731#define ARB_REINSERT(name, x, y) name##_ARB_REINSERT(x, y)
732
733#define ARB_FOREACH(x, name, head) \
734 for ((x) = ARB_MIN(name, head); \
735 (x) != NULL; \
736 (x) = name##_ARB_NEXT(head, x))
737
738#define ARB_FOREACH_FROM(x, name, y) \
739 for ((x) = (y); \
740 ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
741 (x) = (y))
742
743#define ARB_FOREACH_SAFE(x, name, head, y) \
744 for ((x) = ARB_MIN(name, head); \
745 ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
746 (x) = (y))
747
748#define ARB_FOREACH_REVERSE(x, name, head) \
749 for ((x) = ARB_MAX(name, head); \
750 (x) != NULL; \
751 (x) = name##_ARB_PREV(x))
752
753#define ARB_FOREACH_REVERSE_FROM(x, name, y) \
754 for ((x) = (y); \
755 ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
756 (x) = (y))
757
758#define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \
759 for ((x) = ARB_MAX(name, head); \
760 ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
761 (x) = (y))
762
763#define ARB_ARRFOREACH(x, field, head) \
764 for ((x) = ARB_NODES(head); \
765 ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \
766 (x)++)
767
768#define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \
769 for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \
770 (x) >= ARB_NODES(head) && (extracond); \
771 (x)--)
772
773#define ARB_ARRFOREACH_REVERSE(x, field, head) \
774 ARB_ARRFOREACH_REVWCOND(x, field, head, 1)
775
776#define ARB_RESET_TREE(head, name, maxn) \
777 *(head) = ARB_INITIALIZER(name, maxn)
778
779#endif /* _SYS_ARB_H_ */