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