rtems/score/bsd-tree.h

0001 /*  $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
0002 /*  $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
0003 /* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */
0004
0005 /**
0006  * @file
0007  *
0008  * @ingroup RTEMSScoreRBTree
0009  *
0010  * @brief This header file provides a red-black tree implementation.
0011  *
0012  * The contents of this file come from the above version of FreeBSD with local
0013  * changes applied in Newlib and then migrated to RTEMS. These changes lock
0014  * RTEMS to a specific version of this file. As a result, the macros defined
0015  * in this file have been scoped with an RTEMS_ namespace. This allows other
0016  * versions of tree.h to be used by RTEMS libraries and applications without
0017  * conflicts.
0018  */
0019
0020 /*-
0021  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
0022  *
0023  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
0024  * All rights reserved.
0025  *
0026  * Redistribution and use in source and binary forms, with or without
0027  * modification, are permitted provided that the following conditions
0028  * are met:
0029  * 1. Redistributions of source code must retain the above copyright
0030  *    notice, this list of conditions and the following disclaimer.
0031  * 2. Redistributions in binary form must reproduce the above copyright
0032  *    notice, this list of conditions and the following disclaimer in the
0033  *    documentation and/or other materials provided with the distribution.
0034  *
0035  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
0036  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
0037  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
0038  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
0039  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
0040  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0041  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0042  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0043  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
0044  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0045  */
0046
0047 #ifndef _RTEMS_SCORE_BSD_TREE_H_
0048 #define _RTEMS_SCORE_BSD_TREE_H_
0049
0050 #include <sys/cdefs.h>
0051
0052 /*
0053  * This file defines data structures for different types of trees:
0054  * splay trees and red-black trees.
0055  *
0056  * A splay tree is a self-organizing data structure.  Every operation
0057  * on the tree causes a splay to happen.  The splay moves the requested
0058  * node to the root of the tree and partly rebalances it.
0059  *
0060  * This has the benefit that request locality causes faster lookups as
0061  * the requested nodes move to the top of the tree.  On the other hand,
0062  * every lookup causes memory writes.
0063  *
0064  * The Balance Theorem bounds the total access time for m operations
0065  * and n inserts on an initially empty tree as O((m + n)lg n).  The
0066  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
0067  *
0068  * A red-black tree is a binary search tree with the node color as an
0069  * extra attribute.  It fulfills a set of conditions:
0070  *  - every search path from the root to a leaf consists of the
0071  *    same number of black nodes,
0072  *  - each red node (except for the root) has a black parent,
0073  *  - each leaf node is black.
0074  *
0075  * Every operation on a red-black tree is bounded as O(lg n).
0076  * The maximum height of a red-black tree is 2lg (n+1).
0077  */
0078
0079 #define RTEMS_SPLAY_HEAD(name, type)                        \
0080 struct name {                               \
0081     struct type *sph_root; /* root of the tree */           \
0082 }
0083
0084 #define RTEMS_SPLAY_INITIALIZER(root)                       \
0085     { NULL }
0086
0087 #define RTEMS_SPLAY_INIT(root) do {                     \
0088     (root)->sph_root = NULL;                    \
0089 } while (/*CONSTCOND*/ 0)
0090
0091 #define RTEMS_SPLAY_ENTRY(type)                     \
0092 struct {                                \
0093     struct type *spe_left; /* left element */           \
0094     struct type *spe_right; /* right element */         \
0095 }
0096
0097 #define RTEMS_SPLAY_LEFT(elm, field)        (elm)->field.spe_left
0098 #define RTEMS_SPLAY_RIGHT(elm, field)       (elm)->field.spe_right
0099 #define RTEMS_SPLAY_ROOT(head)      (head)->sph_root
0100 #define RTEMS_SPLAY_EMPTY(head)     (RTEMS_SPLAY_ROOT(head) == NULL)
0101
0102 /* RTEMS_SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold RTEMS_SPLAY_{RIGHT,LEFT} */
0103 #define RTEMS_SPLAY_ROTATE_RIGHT(head, tmp, field) do {         \
0104     RTEMS_SPLAY_LEFT((head)->sph_root, field) = RTEMS_SPLAY_RIGHT(tmp, field);  \
0105     RTEMS_SPLAY_RIGHT(tmp, field) = (head)->sph_root;           \
0106     (head)->sph_root = tmp;                     \
0107 } while (/*CONSTCOND*/ 0)
0108
0109 #define RTEMS_SPLAY_ROTATE_LEFT(head, tmp, field) do {          \
0110     RTEMS_SPLAY_RIGHT((head)->sph_root, field) = RTEMS_SPLAY_LEFT(tmp, field);  \
0111     RTEMS_SPLAY_LEFT(tmp, field) = (head)->sph_root;            \
0112     (head)->sph_root = tmp;                     \
0113 } while (/*CONSTCOND*/ 0)
0114
0115 #define RTEMS_SPLAY_LINKLEFT(head, tmp, field) do {             \
0116     RTEMS_SPLAY_LEFT(tmp, field) = (head)->sph_root;            \
0117     tmp = (head)->sph_root;                     \
0118     (head)->sph_root = RTEMS_SPLAY_LEFT((head)->sph_root, field);       \
0119 } while (/*CONSTCOND*/ 0)
0120
0121 #define RTEMS_SPLAY_LINKRIGHT(head, tmp, field) do {                \
0122     RTEMS_SPLAY_RIGHT(tmp, field) = (head)->sph_root;           \
0123     tmp = (head)->sph_root;                     \
0124     (head)->sph_root = RTEMS_SPLAY_RIGHT((head)->sph_root, field);  \
0125 } while (/*CONSTCOND*/ 0)
0126
0127 #define RTEMS_SPLAY_ASSEMBLE(head, node, left, right, field) do {       \
0128     RTEMS_SPLAY_RIGHT(left, field) = RTEMS_SPLAY_LEFT((head)->sph_root, field); \
0129     RTEMS_SPLAY_LEFT(right, field) = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
0130     RTEMS_SPLAY_LEFT((head)->sph_root, field) = RTEMS_SPLAY_RIGHT(node, field); \
0131     RTEMS_SPLAY_RIGHT((head)->sph_root, field) = RTEMS_SPLAY_LEFT(node, field); \
0132 } while (/*CONSTCOND*/ 0)
0133
0134 /* Generates prototypes and inline functions */
0135
0136 #define RTEMS_SPLAY_PROTOTYPE(name, type, field, cmp)               \
0137 void name##_SPLAY(struct name *, struct type *);            \
0138 void name##_RTEMS_SPLAY_MINMAX(struct name *, int);             \
0139 struct type *name##_RTEMS_SPLAY_INSERT(struct name *, struct type *);       \
0140 struct type *name##_RTEMS_SPLAY_REMOVE(struct name *, struct type *);       \
0141                                     \
0142 /* Finds the node with the same key as elm */               \
0143 static __unused __inline struct type *                  \
0144 name##_RTEMS_SPLAY_FIND(struct name *head, struct type *elm)            \
0145 {                                   \
0146     if (RTEMS_SPLAY_EMPTY(head))                        \
0147         return(NULL);                       \
0148     name##_SPLAY(head, elm);                    \
0149     if ((cmp)(elm, (head)->sph_root) == 0)              \
0150         return (head->sph_root);                \
0151     return (NULL);                          \
0152 }                                   \
0153                                     \
0154 static __unused __inline struct type *                  \
0155 name##_RTEMS_SPLAY_NEXT(struct name *head, struct type *elm)            \
0156 {                                   \
0157     name##_SPLAY(head, elm);                    \
0158     if (RTEMS_SPLAY_RIGHT(elm, field) != NULL) {                \
0159         elm = RTEMS_SPLAY_RIGHT(elm, field);                \
0160         while (RTEMS_SPLAY_LEFT(elm, field) != NULL) {      \
0161             elm = RTEMS_SPLAY_LEFT(elm, field);         \
0162         }                           \
0163     } else                              \
0164         elm = NULL;                     \
0165     return (elm);                           \
0166 }                                   \
0167                                     \
0168 static __unused __inline struct type *                  \
0169 name##_RTEMS_SPLAY_MIN_MAX(struct name *head, int val)          \
0170 {                                   \
0171     name##_RTEMS_SPLAY_MINMAX(head, val);                   \
0172         return (RTEMS_SPLAY_ROOT(head));                    \
0173 }
0174
0175 /* Main splay operation.
0176  * Moves node close to the key of elm to top
0177  */
0178 #define RTEMS_SPLAY_GENERATE(name, type, field, cmp)                \
0179 struct type *                               \
0180 name##_RTEMS_SPLAY_INSERT(struct name *head, struct type *elm)      \
0181 {                                   \
0182     if (RTEMS_SPLAY_EMPTY(head)) {                      \
0183         RTEMS_SPLAY_LEFT(elm, field) = RTEMS_SPLAY_RIGHT(elm, field) = NULL;    \
0184     } else {                                \
0185         int __comp;                         \
0186         name##_SPLAY(head, elm);                    \
0187         __comp = (cmp)(elm, (head)->sph_root);          \
0188         if(__comp < 0) {                        \
0189             RTEMS_SPLAY_LEFT(elm, field) = RTEMS_SPLAY_LEFT((head)->sph_root, field);\
0190             RTEMS_SPLAY_RIGHT(elm, field) = (head)->sph_root;       \
0191             RTEMS_SPLAY_LEFT((head)->sph_root, field) = NULL;       \
0192         } else if (__comp > 0) {                    \
0193             RTEMS_SPLAY_RIGHT(elm, field) = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
0194             RTEMS_SPLAY_LEFT(elm, field) = (head)->sph_root;        \
0195             RTEMS_SPLAY_RIGHT((head)->sph_root, field) = NULL;  \
0196         } else                          \
0197             return ((head)->sph_root);              \
0198     }                                   \
0199     (head)->sph_root = (elm);                       \
0200     return (NULL);                          \
0201 }                                   \
0202                                     \
0203 struct type *                               \
0204 name##_RTEMS_SPLAY_REMOVE(struct name *head, struct type *elm)      \
0205 {                                   \
0206     struct type *__tmp;                     \
0207     if (RTEMS_SPLAY_EMPTY(head))                        \
0208         return (NULL);                      \
0209     name##_SPLAY(head, elm);                    \
0210     if ((cmp)(elm, (head)->sph_root) == 0) {            \
0211         if (RTEMS_SPLAY_LEFT((head)->sph_root, field) == NULL) {    \
0212             (head)->sph_root = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
0213         } else {                        \
0214             __tmp = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
0215             (head)->sph_root = RTEMS_SPLAY_LEFT((head)->sph_root, field);\
0216             name##_SPLAY(head, elm);            \
0217             RTEMS_SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
0218         }                           \
0219         return (elm);                       \
0220     }                               \
0221     return (NULL);                          \
0222 }                                   \
0223                                     \
0224 void                                    \
0225 name##_SPLAY(struct name *head, struct type *elm)           \
0226 {                                   \
0227     struct type __node, *__left, *__right, *__tmp;          \
0228     int __comp;                         \
0229 \
0230     RTEMS_SPLAY_LEFT(&__node, field) = RTEMS_SPLAY_RIGHT(&__node, field) = NULL;\
0231     __left = __right = &__node;                 \
0232 \
0233     while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {      \
0234         if (__comp < 0) {                   \
0235             __tmp = RTEMS_SPLAY_LEFT((head)->sph_root, field);  \
0236             if (__tmp == NULL)              \
0237                 break;                  \
0238             if ((cmp)(elm, __tmp) < 0){         \
0239                 RTEMS_SPLAY_ROTATE_RIGHT(head, __tmp, field);   \
0240                 if (RTEMS_SPLAY_LEFT((head)->sph_root, field) == NULL)\
0241                     break;              \
0242             }                       \
0243             RTEMS_SPLAY_LINKLEFT(head, __right, field);     \
0244         } else if (__comp > 0) {                \
0245             __tmp = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
0246             if (__tmp == NULL)              \
0247                 break;                  \
0248             if ((cmp)(elm, __tmp) > 0){         \
0249                 RTEMS_SPLAY_ROTATE_LEFT(head, __tmp, field);    \
0250                 if (RTEMS_SPLAY_RIGHT((head)->sph_root, field) == NULL)\
0251                     break;              \
0252             }                       \
0253             RTEMS_SPLAY_LINKRIGHT(head, __left, field);     \
0254         }                           \
0255     }                               \
0256     RTEMS_SPLAY_ASSEMBLE(head, &__node, __left, __right, field);        \
0257 }                                   \
0258                                     \
0259 /* Splay with either the minimum or the maximum element         \
0260  * Used to find minimum or maximum element in tree.         \
0261  */                                 \
0262 void name##_RTEMS_SPLAY_MINMAX(struct name *head, int __comp) \
0263 {                                   \
0264     struct type __node, *__left, *__right, *__tmp;          \
0265 \
0266     RTEMS_SPLAY_LEFT(&__node, field) = RTEMS_SPLAY_RIGHT(&__node, field) = NULL;\
0267     __left = __right = &__node;                 \
0268 \
0269     while (1) {                         \
0270         if (__comp < 0) {                   \
0271             __tmp = RTEMS_SPLAY_LEFT((head)->sph_root, field);  \
0272             if (__tmp == NULL)              \
0273                 break;                  \
0274             if (__comp < 0){                \
0275                 RTEMS_SPLAY_ROTATE_RIGHT(head, __tmp, field);   \
0276                 if (RTEMS_SPLAY_LEFT((head)->sph_root, field) == NULL)\
0277                     break;              \
0278             }                       \
0279             RTEMS_SPLAY_LINKLEFT(head, __right, field);     \
0280         } else if (__comp > 0) {                \
0281             __tmp = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
0282             if (__tmp == NULL)              \
0283                 break;                  \
0284             if (__comp > 0) {               \
0285                 RTEMS_SPLAY_ROTATE_LEFT(head, __tmp, field);    \
0286                 if (RTEMS_SPLAY_RIGHT((head)->sph_root, field) == NULL)\
0287                     break;              \
0288             }                       \
0289             RTEMS_SPLAY_LINKRIGHT(head, __left, field);     \
0290         }                           \
0291     }                               \
0292     RTEMS_SPLAY_ASSEMBLE(head, &__node, __left, __right, field);        \
0293 }
0294
0295 #define RTEMS_SPLAY_NEGINF  -1
0296 #define RTEMS_SPLAY_INF 1
0297
0298 #define RTEMS_SPLAY_INSERT(name, x, y)  name##_RTEMS_SPLAY_INSERT(x, y)
0299 #define RTEMS_SPLAY_REMOVE(name, x, y)  name##_RTEMS_SPLAY_REMOVE(x, y)
0300 #define RTEMS_SPLAY_FIND(name, x, y)        name##_RTEMS_SPLAY_FIND(x, y)
0301 #define RTEMS_SPLAY_NEXT(name, x, y)        name##_RTEMS_SPLAY_NEXT(x, y)
0302 #define RTEMS_SPLAY_MIN(name, x)        (RTEMS_SPLAY_EMPTY(x) ? NULL    \
0303                     : name##_RTEMS_SPLAY_MIN_MAX(x, RTEMS_SPLAY_NEGINF))
0304 #define RTEMS_SPLAY_MAX(name, x)        (RTEMS_SPLAY_EMPTY(x) ? NULL    \
0305                     : name##_RTEMS_SPLAY_MIN_MAX(x, RTEMS_SPLAY_INF))
0306
0307 #define RTEMS_SPLAY_FOREACH(x, name, head)                  \
0308     for ((x) = RTEMS_SPLAY_MIN(name, head);             \
0309          (x) != NULL;                       \
0310          (x) = RTEMS_SPLAY_NEXT(name, head, x))
0311
0312 /* Macros that define a red-black tree */
0313 #define RTEMS_RB_HEAD(name, type)                       \
0314 struct name {                               \
0315     struct type *rbh_root; /* root of the tree */           \
0316 }
0317
0318 #define RTEMS_RB_INITIALIZER(root)                      \
0319     { NULL }
0320
0321 #define RTEMS_RB_INIT(root) do {                        \
0322     (root)->rbh_root = NULL;                    \
0323 } while (/*CONSTCOND*/ 0)
0324
0325 #define RTEMS_RB_BLACK  0
0326 #define RTEMS_RB_RED        1
0327 #define RTEMS_RB_ENTRY(type)                            \
0328 struct {                                \
0329     struct type *rbe_left;      /* left element */      \
0330     struct type *rbe_right;     /* right element */     \
0331     struct type *rbe_parent;    /* parent element */        \
0332     int rbe_color;          /* node color */        \
0333 }
0334
0335 #define RTEMS_RB_LEFT(elm, field)       (elm)->field.rbe_left
0336 #define RTEMS_RB_RIGHT(elm, field)      (elm)->field.rbe_right
0337 #define RTEMS_RB_PARENT(elm, field)     (elm)->field.rbe_parent
0338 #define RTEMS_RB_COLOR(elm, field)      (elm)->field.rbe_color
0339 #define RTEMS_RB_ISRED(elm, field)      ((elm) != NULL && RTEMS_RB_COLOR(elm, field) == RTEMS_RB_RED)
0340 #define RTEMS_RB_ROOT(head)         (head)->rbh_root
0341 #define RTEMS_RB_EMPTY(head)            (RTEMS_RB_ROOT(head) == NULL)
0342
0343 #define RTEMS_RB_SET_PARENT(dst, src, field) do {               \
0344     RTEMS_RB_PARENT(dst, field) = src;                  \
0345 } while (/*CONSTCOND*/ 0)
0346
0347 #define RTEMS_RB_SET(elm, parent, field) do {                   \
0348     RTEMS_RB_SET_PARENT(elm, parent, field);                \
0349     RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(elm, field) = NULL;      \
0350     RTEMS_RB_COLOR(elm, field) = RTEMS_RB_RED;                  \
0351 } while (/*CONSTCOND*/ 0)
0352
0353 #define RTEMS_RB_SET_BLACKRED(black, red, field) do {               \
0354     RTEMS_RB_COLOR(black, field) = RTEMS_RB_BLACK;              \
0355     RTEMS_RB_COLOR(red, field) = RTEMS_RB_RED;                  \
0356 } while (/*CONSTCOND*/ 0)
0357
0358 /*
0359  * Something to be invoked in a loop at the root of every modified subtree,
0360  * from the bottom up to the root, to update augmented node data.
0361  */
0362 #ifndef RTEMS_RB_AUGMENT
0363 #define RTEMS_RB_AUGMENT(x) break
0364 #endif
0365
0366 #define RTEMS_RB_SWAP_CHILD(head, out, in, field) do {          \
0367     if (RTEMS_RB_PARENT(out, field) == NULL)                \
0368         RTEMS_RB_ROOT(head) = (in);                 \
0369     else if ((out) == RTEMS_RB_LEFT(RTEMS_RB_PARENT(out, field), field))    \
0370         RTEMS_RB_LEFT(RTEMS_RB_PARENT(out, field), field) = (in);       \
0371     else                                \
0372         RTEMS_RB_RIGHT(RTEMS_RB_PARENT(out, field), field) = (in);      \
0373 } while (/*CONSTCOND*/ 0)
0374
0375 #define RTEMS_RB_ROTATE_LEFT(head, elm, tmp, field) do {            \
0376     (tmp) = RTEMS_RB_RIGHT(elm, field);                 \
0377     if ((RTEMS_RB_RIGHT(elm, field) = RTEMS_RB_LEFT(tmp, field)) != NULL) { \
0378         RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(elm, field), elm, field);    \
0379     }                               \
0380     RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
0381     RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
0382     RTEMS_RB_LEFT(tmp, field) = (elm);                  \
0383     RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
0384     RTEMS_RB_AUGMENT(elm);                      \
0385 } while (/*CONSTCOND*/ 0)
0386
0387 #define RTEMS_RB_ROTATE_RIGHT(head, elm, tmp, field) do {           \
0388     (tmp) = RTEMS_RB_LEFT(elm, field);                  \
0389     if ((RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(tmp, field)) != NULL) { \
0390         RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(elm, field), elm, field);     \
0391     }                               \
0392     RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
0393     RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
0394     RTEMS_RB_RIGHT(tmp, field) = (elm);                 \
0395     RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
0396     RTEMS_RB_AUGMENT(elm);                      \
0397 } while (/*CONSTCOND*/ 0)
0398
0399 /*
0400  * The RTEMS_RB_PARENT_ROTATE_LEFT() and RTEMS_RB_PARENT_ROTATE_RIGHT() rotations are
0401  * specialized versions of RTEMS_RB_ROTATE_LEFT() and RTEMS_RB_ROTATE_RIGHT() which may be
0402  * used if the parent node exists and the direction of the child element is
0403  * known.
0404  */
0405
0406 #define RTEMS_RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do {      \
0407     (tmp) = RTEMS_RB_RIGHT(left, field);                    \
0408     if ((RTEMS_RB_RIGHT(left, field) = RTEMS_RB_LEFT(tmp, field)) != NULL) {    \
0409         RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(left, field), left, field);  \
0410     }                               \
0411     RTEMS_RB_SET_PARENT(tmp, parent, field);                \
0412     RTEMS_RB_LEFT(parent, field) = (tmp);                   \
0413     RTEMS_RB_LEFT(tmp, field) = (left);                 \
0414     RTEMS_RB_SET_PARENT(left, tmp, field);              \
0415     RTEMS_RB_AUGMENT(left);                     \
0416 } while (/*CONSTCOND*/ 0)
0417
0418 #define RTEMS_RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do {        \
0419     (tmp) = RTEMS_RB_LEFT(right, field);                    \
0420     if ((RTEMS_RB_LEFT(right, field) = RTEMS_RB_RIGHT(tmp, field)) != NULL) {   \
0421         RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(right, field), right, field); \
0422     }                               \
0423     RTEMS_RB_SET_PARENT(tmp, parent, field);                \
0424     RTEMS_RB_RIGHT(parent, field) = (tmp);              \
0425     RTEMS_RB_RIGHT(tmp, field) = (right);                   \
0426     RTEMS_RB_SET_PARENT(right, tmp, field);             \
0427     RTEMS_RB_AUGMENT(right);                        \
0428 } while (/*CONSTCOND*/ 0)
0429
0430 /*
0431  * The RTEMS_RB_RED_ROTATE_LEFT() and RTEMS_RB_RED_ROTATE_RIGHT() rotations are specialized
0432  * versions of RTEMS_RB_ROTATE_LEFT() and RTEMS_RB_ROTATE_RIGHT() which may be used if we
0433  * rotate an element with a red child which has a black sibling.  Such a red
0434  * node must have at least two child nodes so that the following red-black tree
0435  * invariant is fulfilled:
0436  *
0437  *  Every path from a given node to any of its descendant NULL nodes goes
0438  *  through the same number of black nodes.
0439  *
0440  *  elm (could be the root)
0441  *    /      \
0442  * BLACK   RED (left or right child)
0443  *          /   \
0444  *       BLACK  BLACK
0445  */
0446
0447 #define RTEMS_RB_RED_ROTATE_LEFT(head, elm, tmp, field) do {            \
0448     (tmp) = RTEMS_RB_RIGHT(elm, field);                 \
0449     RTEMS_RB_RIGHT(elm, field) = RTEMS_RB_LEFT(tmp, field);         \
0450     RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(elm, field), elm, field);        \
0451     RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
0452     RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
0453     RTEMS_RB_LEFT(tmp, field) = (elm);                  \
0454     RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
0455     RTEMS_RB_AUGMENT(elm);                      \
0456 } while (/*CONSTCOND*/ 0)
0457
0458 #define RTEMS_RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do {           \
0459     (tmp) = RTEMS_RB_LEFT(elm, field);                  \
0460     RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(tmp, field);         \
0461     RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(elm, field), elm, field);         \
0462     RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field);       \
0463     RTEMS_RB_SWAP_CHILD(head, elm, tmp, field);             \
0464     RTEMS_RB_RIGHT(tmp, field) = (elm);                 \
0465     RTEMS_RB_SET_PARENT(elm, tmp, field);                   \
0466     RTEMS_RB_AUGMENT(elm);                      \
0467 } while (/*CONSTCOND*/ 0)
0468
0469 /* Generates prototypes and inline functions */
0470 #define RTEMS_RB_PROTOTYPE(name, type, field, cmp)              \
0471     RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
0472 #define RTEMS_RB_PROTOTYPE_STATIC(name, type, field, cmp)           \
0473     RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
0474 #define RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)       \
0475     RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr);          \
0476     RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);          \
0477     RTEMS_RB_PROTOTYPE_INSERT(name, type, attr);                \
0478     RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr);                \
0479     RTEMS_RB_PROTOTYPE_FIND(name, type, attr);              \
0480     RTEMS_RB_PROTOTYPE_NFIND(name, type, attr);             \
0481     RTEMS_RB_PROTOTYPE_NEXT(name, type, attr);              \
0482     RTEMS_RB_PROTOTYPE_PREV(name, type, attr);              \
0483     RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr);                \
0484     RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr);
0485 #define RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr)           \
0486     attr void name##_RTEMS_RB_INSERT_COLOR(struct name *, struct type *)
0487 #define RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)           \
0488     attr void name##_RTEMS_RB_REMOVE_COLOR(struct name *, struct type *)
0489 #define RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr)             \
0490     attr struct type *name##_RTEMS_RB_REMOVE(struct name *, struct type *)
0491 #define RTEMS_RB_PROTOTYPE_INSERT(name, type, attr)             \
0492     attr struct type *name##_RTEMS_RB_INSERT(struct name *, struct type *)
0493 #define RTEMS_RB_PROTOTYPE_FIND(name, type, attr)               \
0494     attr struct type *name##_RTEMS_RB_FIND(struct name *, struct type *)
0495 #define RTEMS_RB_PROTOTYPE_NFIND(name, type, attr)              \
0496     attr struct type *name##_RTEMS_RB_NFIND(struct name *, struct type *)
0497 #define RTEMS_RB_PROTOTYPE_NEXT(name, type, attr)               \
0498     attr struct type *name##_RTEMS_RB_NEXT(struct type *)
0499 #define RTEMS_RB_PROTOTYPE_PREV(name, type, attr)               \
0500     attr struct type *name##_RTEMS_RB_PREV(struct type *)
0501 #define RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr)             \
0502     attr struct type *name##_RTEMS_RB_MINMAX(struct name *, int)
0503 #define RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr)           \
0504     attr struct type *name##_RTEMS_RB_REINSERT(struct name *, struct type *)
0505
0506 /* Main rb operation.
0507  * Moves node close to the key of elm to top
0508  */
0509 #define RTEMS_RB_GENERATE(name, type, field, cmp)               \
0510     RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp,)
0511 #define RTEMS_RB_GENERATE_STATIC(name, type, field, cmp)            \
0512     RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
0513 #define RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, attr)        \
0514     RTEMS_RB_GENERATE_INSERT_COLOR(name, type, field, attr)     \
0515     RTEMS_RB_GENERATE_REMOVE_COLOR(name, type, field, attr)     \
0516     RTEMS_RB_GENERATE_INSERT(name, type, field, cmp, attr)      \
0517     RTEMS_RB_GENERATE_REMOVE(name, type, field, attr)           \
0518     RTEMS_RB_GENERATE_FIND(name, type, field, cmp, attr)            \
0519     RTEMS_RB_GENERATE_NFIND(name, type, field, cmp, attr)           \
0520     RTEMS_RB_GENERATE_NEXT(name, type, field, attr)         \
0521     RTEMS_RB_GENERATE_PREV(name, type, field, attr)         \
0522     RTEMS_RB_GENERATE_MINMAX(name, type, field, attr)           \
0523     RTEMS_RB_GENERATE_REINSERT(name, type, field, cmp, attr)
0524
0525
0526 #define RTEMS_RB_GENERATE_INSERT_COLOR(name, type, field, attr)     \
0527 attr void                               \
0528 name##_RTEMS_RB_INSERT_COLOR(struct name *head, struct type *elm)       \
0529 {                                   \
0530     struct type *parent, *gparent, *tmp;                \
0531     while (RTEMS_RB_ISRED((parent = RTEMS_RB_PARENT(elm, field)), field)) { \
0532         gparent = RTEMS_RB_PARENT(parent, field);           \
0533         if (parent == RTEMS_RB_LEFT(gparent, field)) {      \
0534             tmp = RTEMS_RB_RIGHT(gparent, field);           \
0535             if (RTEMS_RB_ISRED(tmp, field)) {           \
0536                 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_BLACK;    \
0537                 RTEMS_RB_SET_BLACKRED(parent, gparent, field);\
0538                 elm = gparent;              \
0539                 continue;               \
0540             }                       \
0541             if (RTEMS_RB_RIGHT(parent, field) == elm) {     \
0542                 RTEMS_RB_PARENT_ROTATE_LEFT(gparent, parent,    \
0543                     tmp, field);            \
0544                 tmp = parent;               \
0545                 parent = elm;               \
0546                 elm = tmp;              \
0547             }                       \
0548             RTEMS_RB_SET_BLACKRED(parent, gparent, field);  \
0549             RTEMS_RB_ROTATE_RIGHT(head, gparent, tmp, field);   \
0550         } else {                        \
0551             tmp = RTEMS_RB_LEFT(gparent, field);            \
0552             if (RTEMS_RB_ISRED(tmp, field)) {           \
0553                 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_BLACK;    \
0554                 RTEMS_RB_SET_BLACKRED(parent, gparent, field);\
0555                 elm = gparent;              \
0556                 continue;               \
0557             }                       \
0558             if (RTEMS_RB_LEFT(parent, field) == elm) {      \
0559                 RTEMS_RB_PARENT_ROTATE_RIGHT(gparent, parent,   \
0560                     tmp, field);            \
0561                 tmp = parent;               \
0562                 parent = elm;               \
0563                 elm = tmp;              \
0564             }                       \
0565             RTEMS_RB_SET_BLACKRED(parent, gparent, field);  \
0566             RTEMS_RB_ROTATE_LEFT(head, gparent, tmp, field);    \
0567         }                           \
0568     }                               \
0569     RTEMS_RB_COLOR(head->rbh_root, field) = RTEMS_RB_BLACK;         \
0570 }
0571
0572 #define RTEMS_RB_GENERATE_REMOVE_COLOR(name, type, field, attr)     \
0573 attr void                               \
0574 name##_RTEMS_RB_REMOVE_COLOR(struct name *head, struct type *parent)        \
0575 {                                   \
0576     struct type *elm, *tmp;                     \
0577     elm = NULL;                         \
0578     do {                                \
0579         if (RTEMS_RB_LEFT(parent, field) == elm) {          \
0580             tmp = RTEMS_RB_RIGHT(parent, field);            \
0581             if (RTEMS_RB_COLOR(tmp, field) == RTEMS_RB_RED) {       \
0582                 RTEMS_RB_SET_BLACKRED(tmp, parent, field);  \
0583                 RTEMS_RB_RED_ROTATE_LEFT(head, parent, tmp, field); \
0584                 tmp = RTEMS_RB_RIGHT(parent, field);        \
0585             }                       \
0586             if (RTEMS_RB_ISRED(RTEMS_RB_RIGHT(tmp, field), field))  \
0587                 RTEMS_RB_COLOR(RTEMS_RB_RIGHT(tmp, field), field) = RTEMS_RB_BLACK; \
0588             else if (RTEMS_RB_ISRED(RTEMS_RB_LEFT(tmp, field), field)) { \
0589                 struct type *oleft;         \
0590                 RTEMS_RB_PARENT_ROTATE_RIGHT(parent, tmp,   \
0591                     oleft, field);          \
0592                 RTEMS_RB_COLOR(oleft, field) = RTEMS_RB_BLACK;  \
0593                 tmp = oleft;                \
0594             } else {                    \
0595                 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_RED;      \
0596                 elm = parent;               \
0597                 parent = RTEMS_RB_PARENT(elm, field);       \
0598                 continue;               \
0599             }                       \
0600             RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_COLOR(parent, field); \
0601             RTEMS_RB_COLOR(parent, field) = RTEMS_RB_BLACK;     \
0602             RTEMS_RB_ROTATE_LEFT(head, parent, tmp, field); \
0603             elm = RTEMS_RB_ROOT(head);              \
0604             break;                      \
0605         } else {                        \
0606             tmp = RTEMS_RB_LEFT(parent, field);         \
0607             if (RTEMS_RB_COLOR(tmp, field) == RTEMS_RB_RED) {       \
0608                 RTEMS_RB_SET_BLACKRED(tmp, parent, field);  \
0609                 RTEMS_RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \
0610                 tmp = RTEMS_RB_LEFT(parent, field);     \
0611             }                       \
0612             if (RTEMS_RB_ISRED(RTEMS_RB_LEFT(tmp, field), field))   \
0613                 RTEMS_RB_COLOR(RTEMS_RB_LEFT(tmp, field), field) = RTEMS_RB_BLACK; \
0614             else if (RTEMS_RB_ISRED(RTEMS_RB_RIGHT(tmp, field), field)) { \
0615                 struct type *oright;            \
0616                 RTEMS_RB_PARENT_ROTATE_LEFT(parent, tmp,    \
0617                     oright, field);         \
0618                 RTEMS_RB_COLOR(oright, field) = RTEMS_RB_BLACK; \
0619                 tmp = oright;               \
0620             } else {                    \
0621                 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_RED;      \
0622                 elm = parent;               \
0623                 parent = RTEMS_RB_PARENT(elm, field);       \
0624                 continue;               \
0625             }                       \
0626             RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_COLOR(parent, field); \
0627             RTEMS_RB_COLOR(parent, field) = RTEMS_RB_BLACK;     \
0628             RTEMS_RB_ROTATE_RIGHT(head, parent, tmp, field);    \
0629             elm = RTEMS_RB_ROOT(head);              \
0630             break;                      \
0631         }                           \
0632     } while (RTEMS_RB_COLOR(elm, field) == RTEMS_RB_BLACK && parent != NULL);   \
0633     RTEMS_RB_COLOR(elm, field) = RTEMS_RB_BLACK;                \
0634 }
0635
0636 #define RTEMS_RB_GENERATE_REMOVE(name, type, field, attr)           \
0637 attr struct type *                          \
0638 name##_RTEMS_RB_REMOVE(struct name *head, struct type *elm)         \
0639 {                                   \
0640     struct type *child, *old, *parent, *right;          \
0641     int color;                          \
0642                                     \
0643     old = elm;                          \
0644     parent = RTEMS_RB_PARENT(elm, field);                   \
0645     right = RTEMS_RB_RIGHT(elm, field);                 \
0646     color = RTEMS_RB_COLOR(elm, field);                 \
0647     if (RTEMS_RB_LEFT(elm, field) == NULL)              \
0648         elm = child = right;                    \
0649     else if (right == NULL)                     \
0650         elm = child = RTEMS_RB_LEFT(elm, field);            \
0651     else {                              \
0652         if ((child = RTEMS_RB_LEFT(right, field)) == NULL) {        \
0653             child = RTEMS_RB_RIGHT(right, field);           \
0654             RTEMS_RB_RIGHT(old, field) = child;         \
0655             parent = elm = right;               \
0656         } else {                        \
0657             do                      \
0658                 elm = child;                \
0659             while ((child = RTEMS_RB_LEFT(elm, field)) != NULL);    \
0660             child = RTEMS_RB_RIGHT(elm, field);         \
0661             parent = RTEMS_RB_PARENT(elm, field);           \
0662             RTEMS_RB_LEFT(parent, field) = child;           \
0663             RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(old, field), elm, field); \
0664         }                           \
0665         RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(old, field), elm, field);     \
0666         color = RTEMS_RB_COLOR(elm, field);             \
0667         elm->field = old->field;                \
0668     }                               \
0669     RTEMS_RB_SWAP_CHILD(head, old, elm, field);             \
0670     if (child != NULL) {                        \
0671         RTEMS_RB_SET_PARENT(child, parent, field);          \
0672         RTEMS_RB_COLOR(child, field) = RTEMS_RB_BLACK;          \
0673     } else if (color != RTEMS_RB_RED && parent != NULL)         \
0674         name##_RTEMS_RB_REMOVE_COLOR(head, parent);         \
0675     while (parent != NULL) {                    \
0676         RTEMS_RB_AUGMENT(parent);                   \
0677         parent = RTEMS_RB_PARENT(parent, field);            \
0678     }                               \
0679     return (old);                           \
0680 }
0681
0682 #define RTEMS_RB_GENERATE_INSERT(name, type, field, cmp, attr)      \
0683 /* Inserts a node into the RB tree */                   \
0684 attr struct type *                          \
0685 name##_RTEMS_RB_INSERT(struct name *head, struct type *elm)         \
0686 {                                   \
0687     struct type *tmp;                       \
0688     struct type *parent = NULL;                 \
0689     int comp = 0;                           \
0690     tmp = RTEMS_RB_ROOT(head);                      \
0691     while (tmp) {                           \
0692         parent = tmp;                       \
0693         comp = (cmp)(elm, parent);              \
0694         if (comp < 0)                       \
0695             tmp = RTEMS_RB_LEFT(tmp, field);            \
0696         else if (comp > 0)                  \
0697             tmp = RTEMS_RB_RIGHT(tmp, field);           \
0698         else                            \
0699             return (tmp);                   \
0700     }                               \
0701     RTEMS_RB_SET(elm, parent, field);                   \
0702     if (parent != NULL) {                       \
0703         if (comp < 0)                       \
0704             RTEMS_RB_LEFT(parent, field) = elm;         \
0705         else                            \
0706             RTEMS_RB_RIGHT(parent, field) = elm;            \
0707     } else                              \
0708         RTEMS_RB_ROOT(head) = elm;                  \
0709     name##_RTEMS_RB_INSERT_COLOR(head, elm);                \
0710     while (elm != NULL) {                       \
0711         RTEMS_RB_AUGMENT(elm);                  \
0712         elm = RTEMS_RB_PARENT(elm, field);              \
0713     }                               \
0714     return (NULL);                          \
0715 }
0716
0717 #define RTEMS_RB_GENERATE_FIND(name, type, field, cmp, attr)            \
0718 /* Finds the node with the same key as elm */               \
0719 attr struct type *                          \
0720 name##_RTEMS_RB_FIND(struct name *head, struct type *elm)           \
0721 {                                   \
0722     struct type *tmp = RTEMS_RB_ROOT(head);             \
0723     int comp;                           \
0724     while (tmp) {                           \
0725         comp = cmp(elm, tmp);                   \
0726         if (comp < 0)                       \
0727             tmp = RTEMS_RB_LEFT(tmp, field);            \
0728         else if (comp > 0)                  \
0729             tmp = RTEMS_RB_RIGHT(tmp, field);           \
0730         else                            \
0731             return (tmp);                   \
0732     }                               \
0733     return (NULL);                          \
0734 }
0735
0736 #define RTEMS_RB_GENERATE_NFIND(name, type, field, cmp, attr)           \
0737 /* Finds the first node greater than or equal to the search key */  \
0738 attr struct type *                          \
0739 name##_RTEMS_RB_NFIND(struct name *head, struct type *elm)          \
0740 {                                   \
0741     struct type *tmp = RTEMS_RB_ROOT(head);             \
0742     struct type *res = NULL;                    \
0743     int comp;                           \
0744     while (tmp) {                           \
0745         comp = cmp(elm, tmp);                   \
0746         if (comp < 0) {                     \
0747             res = tmp;                  \
0748             tmp = RTEMS_RB_LEFT(tmp, field);            \
0749         }                           \
0750         else if (comp > 0)                  \
0751             tmp = RTEMS_RB_RIGHT(tmp, field);           \
0752         else                            \
0753             return (tmp);                   \
0754     }                               \
0755     return (res);                           \
0756 }
0757
0758 #define RTEMS_RB_GENERATE_NEXT(name, type, field, attr)         \
0759 /* ARGSUSED */                              \
0760 attr struct type *                          \
0761 name##_RTEMS_RB_NEXT(struct type *elm)                  \
0762 {                                   \
0763     if (RTEMS_RB_RIGHT(elm, field)) {                   \
0764         elm = RTEMS_RB_RIGHT(elm, field);               \
0765         while (RTEMS_RB_LEFT(elm, field))               \
0766             elm = RTEMS_RB_LEFT(elm, field);            \
0767     } else {                            \
0768         if (RTEMS_RB_PARENT(elm, field) &&              \
0769             (elm == RTEMS_RB_LEFT(RTEMS_RB_PARENT(elm, field), field))) \
0770             elm = RTEMS_RB_PARENT(elm, field);          \
0771         else {                          \
0772             while (RTEMS_RB_PARENT(elm, field) &&           \
0773                 (elm == RTEMS_RB_RIGHT(RTEMS_RB_PARENT(elm, field), field)))\
0774                 elm = RTEMS_RB_PARENT(elm, field);      \
0775             elm = RTEMS_RB_PARENT(elm, field);          \
0776         }                           \
0777     }                               \
0778     return (elm);                           \
0779 }
0780
0781 #define RTEMS_RB_GENERATE_PREV(name, type, field, attr)         \
0782 /* ARGSUSED */                              \
0783 attr struct type *                          \
0784 name##_RTEMS_RB_PREV(struct type *elm)                  \
0785 {                                   \
0786     if (RTEMS_RB_LEFT(elm, field)) {                    \
0787         elm = RTEMS_RB_LEFT(elm, field);                \
0788         while (RTEMS_RB_RIGHT(elm, field))              \
0789             elm = RTEMS_RB_RIGHT(elm, field);           \
0790     } else {                            \
0791         if (RTEMS_RB_PARENT(elm, field) &&              \
0792             (elm == RTEMS_RB_RIGHT(RTEMS_RB_PARENT(elm, field), field)))    \
0793             elm = RTEMS_RB_PARENT(elm, field);          \
0794         else {                          \
0795             while (RTEMS_RB_PARENT(elm, field) &&           \
0796                 (elm == RTEMS_RB_LEFT(RTEMS_RB_PARENT(elm, field), field)))\
0797                 elm = RTEMS_RB_PARENT(elm, field);      \
0798             elm = RTEMS_RB_PARENT(elm, field);          \
0799         }                           \
0800     }                               \
0801     return (elm);                           \
0802 }
0803
0804 #define RTEMS_RB_GENERATE_MINMAX(name, type, field, attr)           \
0805 attr struct type *                          \
0806 name##_RTEMS_RB_MINMAX(struct name *head, int val)              \
0807 {                                   \
0808     struct type *tmp = RTEMS_RB_ROOT(head);             \
0809     struct type *parent = NULL;                 \
0810     while (tmp) {                           \
0811         parent = tmp;                       \
0812         if (val < 0)                        \
0813             tmp = RTEMS_RB_LEFT(tmp, field);            \
0814         else                            \
0815             tmp = RTEMS_RB_RIGHT(tmp, field);           \
0816     }                               \
0817     return (parent);                        \
0818 }
0819
0820 #define RTEMS_RB_GENERATE_REINSERT(name, type, field, cmp, attr)        \
0821 attr struct type *                          \
0822 name##_RTEMS_RB_REINSERT(struct name *head, struct type *elm)           \
0823 {                                   \
0824     struct type *cmpelm;                        \
0825     if (((cmpelm = RTEMS_RB_PREV(name, head, elm)) != NULL &&       \
0826         cmp(cmpelm, elm) >= 0) ||                   \
0827         ((cmpelm = RTEMS_RB_NEXT(name, head, elm)) != NULL &&       \
0828         cmp(elm, cmpelm) >= 0)) {                   \
0829         /* XXXLAS: Remove/insert is heavy handed. */        \
0830         RTEMS_RB_REMOVE(name, head, elm);               \
0831         return (RTEMS_RB_INSERT(name, head, elm));          \
0832     }                               \
0833     return (NULL);                          \
0834 }                                   \
0835
0836 #define RTEMS_RB_NEGINF -1
0837 #define RTEMS_RB_INF    1
0838
0839 #define RTEMS_RB_INSERT(name, x, y) name##_RTEMS_RB_INSERT(x, y)
0840 #define RTEMS_RB_REMOVE(name, x, y) name##_RTEMS_RB_REMOVE(x, y)
0841 #define RTEMS_RB_FIND(name, x, y)   name##_RTEMS_RB_FIND(x, y)
0842 #define RTEMS_RB_NFIND(name, x, y)  name##_RTEMS_RB_NFIND(x, y)
0843 #define RTEMS_RB_NEXT(name, x, y)   name##_RTEMS_RB_NEXT(y)
0844 #define RTEMS_RB_PREV(name, x, y)   name##_RTEMS_RB_PREV(y)
0845 #define RTEMS_RB_MIN(name, x)       name##_RTEMS_RB_MINMAX(x, RTEMS_RB_NEGINF)
0846 #define RTEMS_RB_MAX(name, x)       name##_RTEMS_RB_MINMAX(x, RTEMS_RB_INF)
0847 #define RTEMS_RB_REINSERT(name, x, y)   name##_RTEMS_RB_REINSERT(x, y)
0848
0849 #define RTEMS_RB_FOREACH(x, name, head)                 \
0850     for ((x) = RTEMS_RB_MIN(name, head);                    \
0851          (x) != NULL;                       \
0852          (x) = name##_RTEMS_RB_NEXT(x))
0853
0854 #define RTEMS_RB_FOREACH_FROM(x, name, y)                   \
0855     for ((x) = (y);                         \
0856         ((x) != NULL) && ((y) = name##_RTEMS_RB_NEXT(x), (x) != NULL);  \
0857          (x) = (y))
0858
0859 #define RTEMS_RB_FOREACH_SAFE(x, name, head, y)             \
0860     for ((x) = RTEMS_RB_MIN(name, head);                    \
0861         ((x) != NULL) && ((y) = name##_RTEMS_RB_NEXT(x), (x) != NULL);  \
0862          (x) = (y))
0863
0864 #define RTEMS_RB_FOREACH_REVERSE(x, name, head)             \
0865     for ((x) = RTEMS_RB_MAX(name, head);                    \
0866          (x) != NULL;                       \
0867          (x) = name##_RTEMS_RB_PREV(x))
0868
0869 #define RTEMS_RB_FOREACH_REVERSE_FROM(x, name, y)               \
0870     for ((x) = (y);                         \
0871         ((x) != NULL) && ((y) = name##_RTEMS_RB_PREV(x), (x) != NULL);  \
0872          (x) = (y))
0873
0874 #define RTEMS_RB_FOREACH_REVERSE_SAFE(x, name, head, y)         \
0875     for ((x) = RTEMS_RB_MAX(name, head);                    \
0876         ((x) != NULL) && ((y) = name##_RTEMS_RB_PREV(x), (x) != NULL);  \
0877          (x) = (y))
0878
0879 #endif  /* _RTEMS_SCORE_BSD_TREE_H_ */