Line data Source code
1 : /* $OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $ */
2 : /*
3 : * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions
8 : * are met:
9 : * 1. Redistributions of source code must retain the above copyright
10 : * notice, this list of conditions and the following disclaimer.
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 : * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 : * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 : * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 : * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 : * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 : */
26 :
27 : #ifndef _SYS_TREE_H_
28 : #define _SYS_TREE_H_
29 :
30 : #include <sys/_null.h>
31 :
32 : /*
33 : * This file defines data structures for different types of trees:
34 : * splay trees and red-black trees.
35 : *
36 : * A splay tree is a self-organizing data structure. Every operation
37 : * on the tree causes a splay to happen. The splay moves the requested
38 : * node to the root of the tree and partly rebalances it.
39 : *
40 : * This has the benefit that request locality causes faster lookups as
41 : * the requested nodes move to the top of the tree. On the other hand,
42 : * every lookup causes memory writes.
43 : *
44 : * The Balance Theorem bounds the total access time for m operations
45 : * and n inserts on an initially empty tree as O((m + n)lg n). The
46 : * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
47 : *
48 : * A red-black tree is a binary search tree with the node color as an
49 : * extra attribute. It fulfills a set of conditions:
50 : * - every search path from the root to a leaf consists of the
51 : * same number of black nodes,
52 : * - each red node (except for the root) has a black parent,
53 : * - each leaf node is black.
54 : *
55 : * Every operation on a red-black tree is bounded as O(lg n).
56 : * The maximum height of a red-black tree is 2lg (n+1).
57 : */
58 :
59 : #define SPLAY_HEAD(name, type) \
60 : struct name { \
61 : struct type *sph_root; /* root of the tree */ \
62 : }
63 :
64 : #define SPLAY_INITIALIZER(root) \
65 : { NULL }
66 :
67 : #define SPLAY_INIT(root) do { \
68 : (root)->sph_root = NULL; \
69 : } while (0)
70 :
71 : #define SPLAY_ENTRY(type) \
72 : struct { \
73 : struct type *spe_left; /* left element */ \
74 : struct type *spe_right; /* right element */ \
75 : }
76 :
77 : #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
78 : #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
79 : #define SPLAY_ROOT(head) (head)->sph_root
80 : #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
81 :
82 : /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
83 : #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
84 : SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
85 : SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
86 : (head)->sph_root = tmp; \
87 : } while (0)
88 :
89 : #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
90 : SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
91 : SPLAY_LEFT(tmp, field) = (head)->sph_root; \
92 : (head)->sph_root = tmp; \
93 : } while (0)
94 :
95 : #define SPLAY_LINKLEFT(head, tmp, field) do { \
96 : SPLAY_LEFT(tmp, field) = (head)->sph_root; \
97 : tmp = (head)->sph_root; \
98 : (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
99 : } while (0)
100 :
101 : #define SPLAY_LINKRIGHT(head, tmp, field) do { \
102 : SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
103 : tmp = (head)->sph_root; \
104 : (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
105 : } while (0)
106 :
107 : #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
108 : SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
109 : SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
110 : SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
111 : SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
112 : } while (0)
113 :
114 : /* Generates prototypes and inline functions */
115 :
116 : #define SPLAY_PROTOTYPE(name, type, field, cmp) \
117 : void name##_SPLAY(struct name *, struct type *); \
118 : void name##_SPLAY_MINMAX(struct name *, int); \
119 : struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
120 : struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
121 : \
122 : /* Finds the node with the same key as elm */ \
123 : static __unused __inline struct type * \
124 : name##_SPLAY_FIND(struct name *head, struct type *elm) \
125 : { \
126 : if (SPLAY_EMPTY(head)) \
127 : return(NULL); \
128 : name##_SPLAY(head, elm); \
129 : if ((cmp)(elm, (head)->sph_root) == 0) \
130 : return (head->sph_root); \
131 : return (NULL); \
132 : } \
133 : \
134 : static __unused __inline struct type * \
135 : name##_SPLAY_NEXT(struct name *head, struct type *elm) \
136 : { \
137 : name##_SPLAY(head, elm); \
138 : if (SPLAY_RIGHT(elm, field) != NULL) { \
139 : elm = SPLAY_RIGHT(elm, field); \
140 : while (SPLAY_LEFT(elm, field) != NULL) { \
141 : elm = SPLAY_LEFT(elm, field); \
142 : } \
143 : } else \
144 : elm = NULL; \
145 : return (elm); \
146 : } \
147 : \
148 : static __unused __inline struct type * \
149 : name##_SPLAY_MIN_MAX(struct name *head, int val) \
150 : { \
151 : name##_SPLAY_MINMAX(head, val); \
152 : return (SPLAY_ROOT(head)); \
153 : }
154 :
155 : /* Main splay operation.
156 : * Moves node close to the key of elm to top
157 : */
158 : #define SPLAY_GENERATE(name, type, field, cmp) \
159 : struct type * \
160 : name##_SPLAY_INSERT(struct name *head, struct type *elm) \
161 : { \
162 : if (SPLAY_EMPTY(head)) { \
163 : SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
164 : } else { \
165 : int __comp; \
166 : name##_SPLAY(head, elm); \
167 : __comp = (cmp)(elm, (head)->sph_root); \
168 : if(__comp < 0) { \
169 : SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
170 : SPLAY_RIGHT(elm, field) = (head)->sph_root; \
171 : SPLAY_LEFT((head)->sph_root, field) = NULL; \
172 : } else if (__comp > 0) { \
173 : SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
174 : SPLAY_LEFT(elm, field) = (head)->sph_root; \
175 : SPLAY_RIGHT((head)->sph_root, field) = NULL; \
176 : } else \
177 : return ((head)->sph_root); \
178 : } \
179 : (head)->sph_root = (elm); \
180 : return (NULL); \
181 : } \
182 : \
183 : struct type * \
184 : name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
185 : { \
186 : struct type *__tmp; \
187 : if (SPLAY_EMPTY(head)) \
188 : return (NULL); \
189 : name##_SPLAY(head, elm); \
190 : if ((cmp)(elm, (head)->sph_root) == 0) { \
191 : if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
192 : (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
193 : } else { \
194 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
195 : (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
196 : name##_SPLAY(head, elm); \
197 : SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
198 : } \
199 : return (elm); \
200 : } \
201 : return (NULL); \
202 : } \
203 : \
204 : void \
205 : name##_SPLAY(struct name *head, struct type *elm) \
206 : { \
207 : struct type __node, *__left, *__right, *__tmp; \
208 : int __comp; \
209 : \
210 : SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
211 : __left = __right = &__node; \
212 : \
213 : while ((__comp = (cmp)(elm, (head)->sph_root))) { \
214 : if (__comp < 0) { \
215 : __tmp = SPLAY_LEFT((head)->sph_root, field); \
216 : if (__tmp == NULL) \
217 : break; \
218 : if ((cmp)(elm, __tmp) < 0){ \
219 : SPLAY_ROTATE_RIGHT(head, __tmp, field); \
220 : if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
221 : break; \
222 : } \
223 : SPLAY_LINKLEFT(head, __right, field); \
224 : } else if (__comp > 0) { \
225 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
226 : if (__tmp == NULL) \
227 : break; \
228 : if ((cmp)(elm, __tmp) > 0){ \
229 : SPLAY_ROTATE_LEFT(head, __tmp, field); \
230 : if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
231 : break; \
232 : } \
233 : SPLAY_LINKRIGHT(head, __left, field); \
234 : } \
235 : } \
236 : SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
237 : } \
238 : \
239 : /* Splay with either the minimum or the maximum element \
240 : * Used to find minimum or maximum element in tree. \
241 : */ \
242 : void name##_SPLAY_MINMAX(struct name *head, int __comp) \
243 : { \
244 : struct type __node, *__left, *__right, *__tmp; \
245 : \
246 : SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
247 : __left = __right = &__node; \
248 : \
249 : while (1) { \
250 : if (__comp < 0) { \
251 : __tmp = SPLAY_LEFT((head)->sph_root, field); \
252 : if (__tmp == NULL) \
253 : break; \
254 : if (__comp < 0){ \
255 : SPLAY_ROTATE_RIGHT(head, __tmp, field); \
256 : if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
257 : break; \
258 : } \
259 : SPLAY_LINKLEFT(head, __right, field); \
260 : } else if (__comp > 0) { \
261 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
262 : if (__tmp == NULL) \
263 : break; \
264 : if (__comp > 0) { \
265 : SPLAY_ROTATE_LEFT(head, __tmp, field); \
266 : if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
267 : break; \
268 : } \
269 : SPLAY_LINKRIGHT(head, __left, field); \
270 : } \
271 : } \
272 : SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
273 : }
274 :
275 : #define SPLAY_NEGINF -1
276 : #define SPLAY_INF 1
277 :
278 : #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
279 : #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
280 : #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
281 : #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
282 : #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
283 : : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
284 : #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
285 : : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
286 :
287 : #define SPLAY_FOREACH(x, name, head) \
288 : for ((x) = SPLAY_MIN(name, head); \
289 : (x) != NULL; \
290 : (x) = SPLAY_NEXT(name, head, x))
291 :
292 : /* Macros that define a red-black tree */
293 : #define RB_HEAD(name, type) \
294 : struct name { \
295 : struct type *rbh_root; /* root of the tree */ \
296 : }
297 :
298 : #define RB_INITIALIZER(root) \
299 : { NULL }
300 :
301 : #define RB_INIT(root) do { \
302 : (root)->rbh_root = NULL; \
303 : } while (0)
304 :
305 : #define RB_BLACK 0
306 : #define RB_RED 1
307 : #define RB_ENTRY(type) \
308 : struct { \
309 : struct type *rbe_left; /* left element */ \
310 : struct type *rbe_right; /* right element */ \
311 : struct type *rbe_parent; /* parent element */ \
312 : int rbe_color; /* node color */ \
313 : }
314 :
315 : #define RB_LEFT(elm, field) (elm)->field.rbe_left
316 : #define RB_RIGHT(elm, field) (elm)->field.rbe_right
317 : #define RB_PARENT(elm, field) (elm)->field.rbe_parent
318 : #define RB_COLOR(elm, field) (elm)->field.rbe_color
319 : #define RB_ROOT(head) (head)->rbh_root
320 : #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
321 :
322 : #define RB_SET(elm, parent, field) do { \
323 : RB_PARENT(elm, field) = parent; \
324 : RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
325 : RB_COLOR(elm, field) = RB_RED; \
326 : } while (0)
327 :
328 : #define RB_SET_BLACKRED(black, red, field) do { \
329 : RB_COLOR(black, field) = RB_BLACK; \
330 : RB_COLOR(red, field) = RB_RED; \
331 : } while (0)
332 :
333 : #ifndef RB_AUGMENT
334 : #define RB_AUGMENT(x) do {} while (0)
335 : #endif
336 :
337 : #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
338 : (tmp) = RB_RIGHT(elm, field); \
339 : if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
340 : RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
341 : } \
342 : RB_AUGMENT(elm); \
343 : if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
344 : if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
345 : RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
346 : else \
347 : RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
348 : } else \
349 : (head)->rbh_root = (tmp); \
350 : RB_LEFT(tmp, field) = (elm); \
351 : RB_PARENT(elm, field) = (tmp); \
352 : RB_AUGMENT(tmp); \
353 : if ((RB_PARENT(tmp, field))) \
354 : RB_AUGMENT(RB_PARENT(tmp, field)); \
355 : } while (0)
356 :
357 : #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
358 : (tmp) = RB_LEFT(elm, field); \
359 : if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
360 : RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
361 : } \
362 : RB_AUGMENT(elm); \
363 : if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
364 : if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
365 : RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
366 : else \
367 : RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
368 : } else \
369 : (head)->rbh_root = (tmp); \
370 : RB_RIGHT(tmp, field) = (elm); \
371 : RB_PARENT(elm, field) = (tmp); \
372 : RB_AUGMENT(tmp); \
373 : if ((RB_PARENT(tmp, field))) \
374 : RB_AUGMENT(RB_PARENT(tmp, field)); \
375 : } while (0)
376 :
377 : /* Generates prototypes and inline functions */
378 : #define RB_PROTOTYPE(name, type, field, cmp) \
379 : RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
380 : #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
381 : RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
382 : #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
383 : attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
384 : attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
385 : attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
386 : attr struct type *name##_RB_INSERT(struct name *, struct type *); \
387 : attr struct type *name##_RB_FIND(struct name *, struct type *); \
388 : attr struct type *name##_RB_NFIND(struct name *, struct type *); \
389 : attr struct type *name##_RB_NEXT(struct type *); \
390 : attr struct type *name##_RB_PREV(struct type *); \
391 : attr struct type *name##_RB_MINMAX(struct name *, int); \
392 : \
393 :
394 : /* Main rb operation.
395 : * Moves node close to the key of elm to top
396 : */
397 : #define RB_GENERATE(name, type, field, cmp) \
398 : RB_GENERATE_INTERNAL(name, type, field, cmp,)
399 : #define RB_GENERATE_STATIC(name, type, field, cmp) \
400 : RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
401 : #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
402 : attr void \
403 : name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
404 : { \
405 : struct type *parent, *gparent, *tmp; \
406 : while ((parent = RB_PARENT(elm, field)) && \
407 : RB_COLOR(parent, field) == RB_RED) { \
408 : gparent = RB_PARENT(parent, field); \
409 : if (parent == RB_LEFT(gparent, field)) { \
410 : tmp = RB_RIGHT(gparent, field); \
411 : if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
412 : RB_COLOR(tmp, field) = RB_BLACK; \
413 : RB_SET_BLACKRED(parent, gparent, field);\
414 : elm = gparent; \
415 : continue; \
416 : } \
417 : if (RB_RIGHT(parent, field) == elm) { \
418 : RB_ROTATE_LEFT(head, parent, tmp, field);\
419 : tmp = parent; \
420 : parent = elm; \
421 : elm = tmp; \
422 : } \
423 : RB_SET_BLACKRED(parent, gparent, field); \
424 : RB_ROTATE_RIGHT(head, gparent, tmp, field); \
425 : } else { \
426 : tmp = RB_LEFT(gparent, field); \
427 : if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
428 : RB_COLOR(tmp, field) = RB_BLACK; \
429 : RB_SET_BLACKRED(parent, gparent, field);\
430 : elm = gparent; \
431 : continue; \
432 : } \
433 : if (RB_LEFT(parent, field) == elm) { \
434 : RB_ROTATE_RIGHT(head, parent, tmp, field);\
435 : tmp = parent; \
436 : parent = elm; \
437 : elm = tmp; \
438 : } \
439 : RB_SET_BLACKRED(parent, gparent, field); \
440 : RB_ROTATE_LEFT(head, gparent, tmp, field); \
441 : } \
442 : } \
443 : RB_COLOR(head->rbh_root, field) = RB_BLACK; \
444 : } \
445 : \
446 : attr void \
447 : name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
448 : { \
449 : struct type *tmp; \
450 : while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
451 : elm != RB_ROOT(head)) { \
452 : if (RB_LEFT(parent, field) == elm) { \
453 : tmp = RB_RIGHT(parent, field); \
454 : if (RB_COLOR(tmp, field) == RB_RED) { \
455 : RB_SET_BLACKRED(tmp, parent, field); \
456 : RB_ROTATE_LEFT(head, parent, tmp, field);\
457 : tmp = RB_RIGHT(parent, field); \
458 : } \
459 : if ((RB_LEFT(tmp, field) == NULL || \
460 : RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
461 : (RB_RIGHT(tmp, field) == NULL || \
462 : RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
463 : RB_COLOR(tmp, field) = RB_RED; \
464 : elm = parent; \
465 : parent = RB_PARENT(elm, field); \
466 : } else { \
467 : if (RB_RIGHT(tmp, field) == NULL || \
468 : RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
469 : struct type *oleft; \
470 : if ((oleft = RB_LEFT(tmp, field)))\
471 : RB_COLOR(oleft, field) = RB_BLACK;\
472 : RB_COLOR(tmp, field) = RB_RED; \
473 : RB_ROTATE_RIGHT(head, tmp, oleft, field);\
474 : tmp = RB_RIGHT(parent, field); \
475 : } \
476 : RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
477 : RB_COLOR(parent, field) = RB_BLACK; \
478 : if (RB_RIGHT(tmp, field)) \
479 : RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
480 : RB_ROTATE_LEFT(head, parent, tmp, field);\
481 : elm = RB_ROOT(head); \
482 : break; \
483 : } \
484 : } else { \
485 : tmp = RB_LEFT(parent, field); \
486 : if (RB_COLOR(tmp, field) == RB_RED) { \
487 : RB_SET_BLACKRED(tmp, parent, field); \
488 : RB_ROTATE_RIGHT(head, parent, tmp, field);\
489 : tmp = RB_LEFT(parent, field); \
490 : } \
491 : if ((RB_LEFT(tmp, field) == NULL || \
492 : RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
493 : (RB_RIGHT(tmp, field) == NULL || \
494 : RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
495 : RB_COLOR(tmp, field) = RB_RED; \
496 : elm = parent; \
497 : parent = RB_PARENT(elm, field); \
498 : } else { \
499 : if (RB_LEFT(tmp, field) == NULL || \
500 : RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
501 : struct type *oright; \
502 : if ((oright = RB_RIGHT(tmp, field)))\
503 : RB_COLOR(oright, field) = RB_BLACK;\
504 : RB_COLOR(tmp, field) = RB_RED; \
505 : RB_ROTATE_LEFT(head, tmp, oright, field);\
506 : tmp = RB_LEFT(parent, field); \
507 : } \
508 : RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
509 : RB_COLOR(parent, field) = RB_BLACK; \
510 : if (RB_LEFT(tmp, field)) \
511 : RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
512 : RB_ROTATE_RIGHT(head, parent, tmp, field);\
513 : elm = RB_ROOT(head); \
514 : break; \
515 : } \
516 : } \
517 : } \
518 : if (elm) \
519 : RB_COLOR(elm, field) = RB_BLACK; \
520 : } \
521 : \
522 : attr struct type * \
523 : name##_RB_REMOVE(struct name *head, struct type *elm) \
524 : { \
525 : struct type *child, *parent, *old = elm; \
526 : int color; \
527 : if (RB_LEFT(elm, field) == NULL) \
528 : child = RB_RIGHT(elm, field); \
529 : else if (RB_RIGHT(elm, field) == NULL) \
530 : child = RB_LEFT(elm, field); \
531 : else { \
532 : struct type *left; \
533 : elm = RB_RIGHT(elm, field); \
534 : while ((left = RB_LEFT(elm, field))) \
535 : elm = left; \
536 : child = RB_RIGHT(elm, field); \
537 : parent = RB_PARENT(elm, field); \
538 : color = RB_COLOR(elm, field); \
539 : if (child) \
540 : RB_PARENT(child, field) = parent; \
541 : if (parent) { \
542 : if (RB_LEFT(parent, field) == elm) \
543 : RB_LEFT(parent, field) = child; \
544 : else \
545 : RB_RIGHT(parent, field) = child; \
546 : RB_AUGMENT(parent); \
547 : } else \
548 : RB_ROOT(head) = child; \
549 : if (RB_PARENT(elm, field) == old) \
550 : parent = elm; \
551 : (elm)->field = (old)->field; \
552 : if (RB_PARENT(old, field)) { \
553 : if (RB_LEFT(RB_PARENT(old, field), field) == old)\
554 : RB_LEFT(RB_PARENT(old, field), field) = elm;\
555 : else \
556 : RB_RIGHT(RB_PARENT(old, field), field) = elm;\
557 : RB_AUGMENT(RB_PARENT(old, field)); \
558 : } else \
559 : RB_ROOT(head) = elm; \
560 : RB_PARENT(RB_LEFT(old, field), field) = elm; \
561 : if (RB_RIGHT(old, field)) \
562 : RB_PARENT(RB_RIGHT(old, field), field) = elm; \
563 : if (parent) { \
564 : left = parent; \
565 : do { \
566 : RB_AUGMENT(left); \
567 : } while ((left = RB_PARENT(left, field))); \
568 : } \
569 : goto color; \
570 : } \
571 : parent = RB_PARENT(elm, field); \
572 : color = RB_COLOR(elm, field); \
573 : if (child) \
574 : RB_PARENT(child, field) = parent; \
575 : if (parent) { \
576 : if (RB_LEFT(parent, field) == elm) \
577 : RB_LEFT(parent, field) = child; \
578 : else \
579 : RB_RIGHT(parent, field) = child; \
580 : RB_AUGMENT(parent); \
581 : } else \
582 : RB_ROOT(head) = child; \
583 : color: \
584 : if (color == RB_BLACK) \
585 : name##_RB_REMOVE_COLOR(head, parent, child); \
586 : return (old); \
587 : } \
588 : \
589 : /* Inserts a node into the RB tree */ \
590 : attr struct type * \
591 : name##_RB_INSERT(struct name *head, struct type *elm) \
592 : { \
593 : struct type *tmp; \
594 : struct type *parent = NULL; \
595 : int comp = 0; \
596 : tmp = RB_ROOT(head); \
597 : while (tmp) { \
598 : parent = tmp; \
599 : comp = (cmp)(elm, parent); \
600 : if (comp < 0) \
601 : tmp = RB_LEFT(tmp, field); \
602 : else if (comp > 0) \
603 : tmp = RB_RIGHT(tmp, field); \
604 : else \
605 : return (tmp); \
606 : } \
607 : RB_SET(elm, parent, field); \
608 : if (parent != NULL) { \
609 : if (comp < 0) \
610 : RB_LEFT(parent, field) = elm; \
611 : else \
612 : RB_RIGHT(parent, field) = elm; \
613 : RB_AUGMENT(parent); \
614 : } else \
615 : RB_ROOT(head) = elm; \
616 : name##_RB_INSERT_COLOR(head, elm); \
617 : return (NULL); \
618 : } \
619 : \
620 : /* Finds the node with the same key as elm */ \
621 : attr struct type * \
622 : name##_RB_FIND(struct name *head, struct type *elm) \
623 : { \
624 : struct type *tmp = RB_ROOT(head); \
625 : int comp; \
626 : while (tmp) { \
627 : comp = cmp(elm, tmp); \
628 : if (comp < 0) \
629 : tmp = RB_LEFT(tmp, field); \
630 : else if (comp > 0) \
631 : tmp = RB_RIGHT(tmp, field); \
632 : else \
633 : return (tmp); \
634 : } \
635 : return (NULL); \
636 : } \
637 : \
638 : /* Finds the first node greater than or equal to the search key */ \
639 : attr struct type * \
640 : name##_RB_NFIND(struct name *head, struct type *elm) \
641 : { \
642 : struct type *tmp = RB_ROOT(head); \
643 : struct type *res = NULL; \
644 : int comp; \
645 : while (tmp) { \
646 : comp = cmp(elm, tmp); \
647 : if (comp < 0) { \
648 : res = tmp; \
649 : tmp = RB_LEFT(tmp, field); \
650 : } \
651 : else if (comp > 0) \
652 : tmp = RB_RIGHT(tmp, field); \
653 : else \
654 : return (tmp); \
655 : } \
656 : return (res); \
657 : } \
658 : \
659 : /* ARGSUSED */ \
660 : attr struct type * \
661 : name##_RB_NEXT(struct type *elm) \
662 : { \
663 : if (RB_RIGHT(elm, field)) { \
664 : elm = RB_RIGHT(elm, field); \
665 : while (RB_LEFT(elm, field)) \
666 : elm = RB_LEFT(elm, field); \
667 : } else { \
668 : if (RB_PARENT(elm, field) && \
669 : (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
670 : elm = RB_PARENT(elm, field); \
671 : else { \
672 : while (RB_PARENT(elm, field) && \
673 : (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
674 : elm = RB_PARENT(elm, field); \
675 : elm = RB_PARENT(elm, field); \
676 : } \
677 : } \
678 : return (elm); \
679 : } \
680 : \
681 : /* ARGSUSED */ \
682 : attr struct type * \
683 : name##_RB_PREV(struct type *elm) \
684 : { \
685 : if (RB_LEFT(elm, field)) { \
686 : elm = RB_LEFT(elm, field); \
687 : while (RB_RIGHT(elm, field)) \
688 : elm = RB_RIGHT(elm, field); \
689 : } else { \
690 : if (RB_PARENT(elm, field) && \
691 : (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
692 : elm = RB_PARENT(elm, field); \
693 : else { \
694 : while (RB_PARENT(elm, field) && \
695 : (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
696 : elm = RB_PARENT(elm, field); \
697 : elm = RB_PARENT(elm, field); \
698 : } \
699 : } \
700 : return (elm); \
701 : } \
702 : \
703 : attr struct type * \
704 : name##_RB_MINMAX(struct name *head, int val) \
705 : { \
706 : struct type *tmp = RB_ROOT(head); \
707 : struct type *parent = NULL; \
708 : while (tmp) { \
709 : parent = tmp; \
710 : if (val < 0) \
711 : tmp = RB_LEFT(tmp, field); \
712 : else \
713 : tmp = RB_RIGHT(tmp, field); \
714 : } \
715 : return (parent); \
716 : }
717 :
718 : #define RB_NEGINF -1
719 : #define RB_INF 1
720 :
721 : #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
722 : #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
723 : #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
724 : #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
725 : #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
726 : #define RB_PREV(name, x, y) name##_RB_PREV(y)
727 : #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
728 : #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
729 :
730 : #define RB_FOREACH(x, name, head) \
731 : for ((x) = RB_MIN(name, head); \
732 : (x) != NULL; \
733 : (x) = name##_RB_NEXT(x))
734 :
735 : #define RB_FOREACH_SAFE(x, name, head, y) \
736 : for ((x) = RB_MIN(name, head); \
737 : ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
738 : (x) = (y))
739 :
740 : #define RB_FOREACH_REVERSE(x, name, head) \
741 : for ((x) = RB_MAX(name, head); \
742 : (x) != NULL; \
743 : (x) = name##_RB_PREV(x))
744 :
745 : #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
746 : for ((x) = RB_MAX(name, head); \
747 : ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
748 : (x) = (y))
749 :
750 :
751 : /*
752 : * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
753 : *
754 : * Permission to use, copy, modify, and distribute this software for any
755 : * purpose with or without fee is hereby granted, provided that the above
756 : * copyright notice and this permission notice appear in all copies.
757 : *
758 : * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
759 : * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
760 : * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
761 : * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
762 : * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
763 : * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
764 : * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
765 : */
766 :
767 : struct rb_type {
768 : int (*t_compare)(const void *, const void *);
769 : void (*t_augment)(void *);
770 : unsigned int t_offset; /* offset of rb_entry in type */
771 : };
772 :
773 : struct rb_tree {
774 : struct rb_entry *rbt_root;
775 : };
776 :
777 : struct rb_entry {
778 : struct rb_entry *rbt_parent;
779 : struct rb_entry *rbt_left;
780 : struct rb_entry *rbt_right;
781 : unsigned int rbt_color;
782 : };
783 :
784 : #define RBT_HEAD(_name, _type) \
785 : struct _name { \
786 : struct rb_tree rbh_root; \
787 : }
788 :
789 : #define RBT_ENTRY(_type) struct rb_entry
790 :
791 : static inline void
792 0 : _rb_init(struct rb_tree *rbt)
793 : {
794 0 : rbt->rbt_root = NULL;
795 0 : }
796 :
797 : static inline int
798 0 : _rb_empty(struct rb_tree *rbt)
799 : {
800 0 : return (rbt->rbt_root == NULL);
801 : }
802 :
803 : void *_rb_insert(const struct rb_type *, struct rb_tree *, void *);
804 : void *_rb_remove(const struct rb_type *, struct rb_tree *, void *);
805 : void *_rb_find(const struct rb_type *, struct rb_tree *, const void *);
806 : void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *);
807 : void *_rb_root(const struct rb_type *, struct rb_tree *);
808 : void *_rb_min(const struct rb_type *, struct rb_tree *);
809 : void *_rb_max(const struct rb_type *, struct rb_tree *);
810 : void *_rb_next(const struct rb_type *, void *);
811 : void *_rb_prev(const struct rb_type *, void *);
812 : void *_rb_left(const struct rb_type *, void *);
813 : void *_rb_right(const struct rb_type *, void *);
814 : void *_rb_parent(const struct rb_type *, void *);
815 : void _rb_set_left(const struct rb_type *, void *, void *);
816 : void _rb_set_right(const struct rb_type *, void *, void *);
817 : void _rb_set_parent(const struct rb_type *, void *, void *);
818 : void _rb_poison(const struct rb_type *, void *, unsigned long);
819 : int _rb_check(const struct rb_type *, void *, unsigned long);
820 :
821 : #define RBT_INITIALIZER(_head) { { NULL } }
822 :
823 : #define RBT_PROTOTYPE(_name, _type, _field, _cmp) \
824 : extern const struct rb_type *const _name##_RBT_TYPE; \
825 : \
826 : __unused static inline void \
827 : _name##_RBT_INIT(struct _name *head) \
828 : { \
829 : _rb_init(&head->rbh_root); \
830 : } \
831 : \
832 : __unused static inline struct _type * \
833 : _name##_RBT_INSERT(struct _name *head, struct _type *elm) \
834 : { \
835 : return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \
836 : } \
837 : \
838 : __unused static inline struct _type * \
839 : _name##_RBT_REMOVE(struct _name *head, struct _type *elm) \
840 : { \
841 : return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \
842 : } \
843 : \
844 : __unused static inline struct _type * \
845 : _name##_RBT_FIND(struct _name *head, const struct _type *key) \
846 : { \
847 : return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \
848 : } \
849 : \
850 : __unused static inline struct _type * \
851 : _name##_RBT_NFIND(struct _name *head, const struct _type *key) \
852 : { \
853 : return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \
854 : } \
855 : \
856 : __unused static inline struct _type * \
857 : _name##_RBT_ROOT(struct _name *head) \
858 : { \
859 : return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \
860 : } \
861 : \
862 : __unused static inline int \
863 : _name##_RBT_EMPTY(struct _name *head) \
864 : { \
865 : return _rb_empty(&head->rbh_root); \
866 : } \
867 : \
868 : __unused static inline struct _type * \
869 : _name##_RBT_MIN(struct _name *head) \
870 : { \
871 : return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \
872 : } \
873 : \
874 : __unused static inline struct _type * \
875 : _name##_RBT_MAX(struct _name *head) \
876 : { \
877 : return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \
878 : } \
879 : \
880 : __unused static inline struct _type * \
881 : _name##_RBT_NEXT(struct _type *elm) \
882 : { \
883 : return _rb_next(_name##_RBT_TYPE, elm); \
884 : } \
885 : \
886 : __unused static inline struct _type * \
887 : _name##_RBT_PREV(struct _type *elm) \
888 : { \
889 : return _rb_prev(_name##_RBT_TYPE, elm); \
890 : } \
891 : \
892 : __unused static inline struct _type * \
893 : _name##_RBT_LEFT(struct _type *elm) \
894 : { \
895 : return _rb_left(_name##_RBT_TYPE, elm); \
896 : } \
897 : \
898 : __unused static inline struct _type * \
899 : _name##_RBT_RIGHT(struct _type *elm) \
900 : { \
901 : return _rb_right(_name##_RBT_TYPE, elm); \
902 : } \
903 : \
904 : __unused static inline struct _type * \
905 : _name##_RBT_PARENT(struct _type *elm) \
906 : { \
907 : return _rb_parent(_name##_RBT_TYPE, elm); \
908 : } \
909 : \
910 : __unused static inline void \
911 : _name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \
912 : { \
913 : return _rb_set_left(_name##_RBT_TYPE, elm, left); \
914 : } \
915 : \
916 : __unused static inline void \
917 : _name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \
918 : { \
919 : return _rb_set_right(_name##_RBT_TYPE, elm, right); \
920 : } \
921 : \
922 : __unused static inline void \
923 : _name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \
924 : { \
925 : return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \
926 : } \
927 : \
928 : __unused static inline void \
929 : _name##_RBT_POISON(struct _type *elm, unsigned long poison) \
930 : { \
931 : return _rb_poison(_name##_RBT_TYPE, elm, poison); \
932 : } \
933 : \
934 : __unused static inline int \
935 : _name##_RBT_CHECK(struct _type *elm, unsigned long poison) \
936 : { \
937 : return _rb_check(_name##_RBT_TYPE, elm, poison); \
938 : }
939 :
940 : #define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \
941 : static int \
942 : _name##_RBT_COMPARE(const void *lptr, const void *rptr) \
943 : { \
944 : const struct _type *l = lptr, *r = rptr; \
945 : return _cmp(l, r); \
946 : } \
947 : static const struct rb_type _name##_RBT_INFO = { \
948 : _name##_RBT_COMPARE, \
949 : _aug, \
950 : offsetof(struct _type, _field), \
951 : }; \
952 : const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO
953 :
954 : #define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \
955 : static void \
956 : _name##_RBT_AUGMENT(void *ptr) \
957 : { \
958 : struct _type *p = ptr; \
959 : return _aug(p); \
960 : } \
961 : RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT)
962 :
963 : #define RBT_GENERATE(_name, _type, _field, _cmp) \
964 : RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
965 :
966 : #define RBT_INIT(_name, _head) _name##_RBT_INIT(_head)
967 : #define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm)
968 : #define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm)
969 : #define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key)
970 : #define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key)
971 : #define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head)
972 : #define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head)
973 : #define RBT_MIN(_name, _head) _name##_RBT_MIN(_head)
974 : #define RBT_MAX(_name, _head) _name##_RBT_MAX(_head)
975 : #define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm)
976 : #define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm)
977 : #define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm)
978 : #define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm)
979 : #define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm)
980 : #define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l)
981 : #define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r)
982 : #define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p)
983 : #define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p)
984 : #define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p)
985 :
986 : #define RBT_FOREACH(_e, _name, _head) \
987 : for ((_e) = RBT_MIN(_name, (_head)); \
988 : (_e) != NULL; \
989 : (_e) = RBT_NEXT(_name, (_e)))
990 :
991 : #define RBT_FOREACH_SAFE(_e, _name, _head, _n) \
992 : for ((_e) = RBT_MIN(_name, (_head)); \
993 : (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \
994 : (_e) = (_n))
995 :
996 : #define RBT_FOREACH_REVERSE(_e, _name, _head) \
997 : for ((_e) = RBT_MAX(_name, (_head)); \
998 : (_e) != NULL; \
999 : (_e) = RBT_PREV(_name, (_e)))
1000 :
1001 : #define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
1002 : for ((_e) = RBT_MAX(_name, (_head)); \
1003 : (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \
1004 : (_e) = (_n))
1005 :
1006 : #endif /* _SYS_TREE_H_ */
|
