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