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