source: rtems-libbsd/freebsd/sys/sys/tree.h @ 66659ff

4.1155-freebsd-126-freebsd-12freebsd-9.3
Last change on this file since 66659ff was e599318, checked in by Sebastian Huber <sebastian.huber@…>, on 10/09/13 at 20:52:54

Update files to match FreeBSD layout

Add compatibility with Newlib header files. Some FreeBSD header files
are mapped by the translation script:

o rtems/bsd/sys/_types.h
o rtems/bsd/sys/errno.h
o rtems/bsd/sys/lock.h
o rtems/bsd/sys/param.h
o rtems/bsd/sys/resource.h
o rtems/bsd/sys/time.h
o rtems/bsd/sys/timespec.h
o rtems/bsd/sys/types.h
o rtems/bsd/sys/unistd.h

It is now possible to include <sys/socket.h> directly for example.

Generate one Makefile which builds everything including tests.

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