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