pscnv/pscnv_tree.h

   1 /*
   2  * Originally sys/tree.h from FreeBSD. Changes:
   3  *  - SPLAY removed
   4  *  - name changed to avoid collisions
   5  */
   6
   7 /*
   8  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  21  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  22  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  23  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  29  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifndef __PSCNV_TREE_H__
  33 #define __PSCNV_TREE_H__
  34
  35 #define __unused __attribute__((__unused__))
  36
  37 /* Macros that define a red-black tree */
  38 #define PSCNV_RB_HEAD(name, type)                                               \
  39 struct name {                                                           \
  40         struct type *rbh_root; /* root of the tree */                   \
  41 }
  42
  43 #define PSCNV_RB_INITIALIZER(root)                                              \
  44         { NULL }
  45
  46 #define PSCNV_RB_INIT(root) do {                                                \
  47         (root)->rbh_root = NULL;                                        \
  48 } while (/*CONSTCOND*/ 0)
  49
  50 #define PSCNV_RB_BLACK  0
  51 #define PSCNV_RB_RED            1
  52 #define PSCNV_RB_ENTRY(type)                                                    \
  53 struct {                                                                \
  54         struct type *rbe_left;          /* left element */              \
  55         struct type *rbe_right;         /* right element */             \
  56         struct type *rbe_parent;        /* parent element */            \
  57         int rbe_color;                  /* node color */                \
  58 }
  59
  60 #define PSCNV_RB_LEFT(elm, field)               (elm)->field.rbe_left
  61 #define PSCNV_RB_RIGHT(elm, field)              (elm)->field.rbe_right
  62 #define PSCNV_RB_PARENT(elm, field)             (elm)->field.rbe_parent
  63 #define PSCNV_RB_COLOR(elm, field)              (elm)->field.rbe_color
  64 #define PSCNV_RB_ROOT(head)                     (head)->rbh_root
  65 #define PSCNV_RB_EMPTY(head)                    (PSCNV_RB_ROOT(head) == NULL)
  66
  67 #define PSCNV_RB_SET(elm, parent, field) do {                                   \
  68         PSCNV_RB_PARENT(elm, field) = parent;                                   \
  69         PSCNV_RB_LEFT(elm, field) = PSCNV_RB_RIGHT(elm, field) = NULL;          \
  70         PSCNV_RB_COLOR(elm, field) = PSCNV_RB_RED;                                      \
  71 } while (/*CONSTCOND*/ 0)
  72
  73 #define PSCNV_RB_SET_BLACKRED(black, red, field) do {                           \
  74         PSCNV_RB_COLOR(black, field) = PSCNV_RB_BLACK;                          \
  75         PSCNV_RB_COLOR(red, field) = PSCNV_RB_RED;                                      \
  76 } while (/*CONSTCOND*/ 0)
  77
  78 #ifndef PSCNV_RB_AUGMENT
  79 #define PSCNV_RB_AUGMENT(x) (void)(x)
  80 #endif
  81
  82 #define PSCNV_RB_ROTATE_LEFT(head, elm, tmp, field) do {                        \
  83         (tmp) = PSCNV_RB_RIGHT(elm, field);                                     \
  84         if ((PSCNV_RB_RIGHT(elm, field) = PSCNV_RB_LEFT(tmp, field)) != NULL) { \
  85                 PSCNV_RB_PARENT(PSCNV_RB_LEFT(tmp, field), field) = (elm);              \
  86         }                                                               \
  87         PSCNV_RB_AUGMENT(elm);                                          \
  88         if ((PSCNV_RB_PARENT(tmp, field) = PSCNV_RB_PARENT(elm, field)) != NULL) {      \
  89                 if ((elm) == PSCNV_RB_LEFT(PSCNV_RB_PARENT(elm, field), field)) \
  90                         PSCNV_RB_LEFT(PSCNV_RB_PARENT(elm, field), field) = (tmp);      \
  91                 else                                                    \
  92                         PSCNV_RB_RIGHT(PSCNV_RB_PARENT(elm, field), field) = (tmp);     \
  93         } else                                                          \
  94                 (head)->rbh_root = (tmp);                               \
  95         PSCNV_RB_LEFT(tmp, field) = (elm);                                      \
  96         PSCNV_RB_PARENT(elm, field) = (tmp);                                    \
  97         PSCNV_RB_AUGMENT(tmp);                                          \
  98         if ((PSCNV_RB_PARENT(tmp, field)))                                      \
  99                 PSCNV_RB_AUGMENT(PSCNV_RB_PARENT(tmp, field));                  \
 100 } while (/*CONSTCOND*/ 0)
 101
 102 #define PSCNV_RB_ROTATE_RIGHT(head, elm, tmp, field) do {                       \
 103         (tmp) = PSCNV_RB_LEFT(elm, field);                                      \
 104         if ((PSCNV_RB_LEFT(elm, field) = PSCNV_RB_RIGHT(tmp, field)) != NULL) { \
 105                 PSCNV_RB_PARENT(PSCNV_RB_RIGHT(tmp, field), field) = (elm);             \
 106         }                                                               \
 107         PSCNV_RB_AUGMENT(elm);                                          \
 108         if ((PSCNV_RB_PARENT(tmp, field) = PSCNV_RB_PARENT(elm, field)) != NULL) {      \
 109                 if ((elm) == PSCNV_RB_LEFT(PSCNV_RB_PARENT(elm, field), field)) \
 110                         PSCNV_RB_LEFT(PSCNV_RB_PARENT(elm, field), field) = (tmp);      \
 111                 else                                                    \
 112                         PSCNV_RB_RIGHT(PSCNV_RB_PARENT(elm, field), field) = (tmp);     \
 113         } else                                                          \
 114                 (head)->rbh_root = (tmp);                               \
 115         PSCNV_RB_RIGHT(tmp, field) = (elm);                                     \
 116         PSCNV_RB_PARENT(elm, field) = (tmp);                                    \
 117         PSCNV_RB_AUGMENT(tmp);                                          \
 118         if ((PSCNV_RB_PARENT(tmp, field)))                                      \
 119                 PSCNV_RB_AUGMENT(PSCNV_RB_PARENT(tmp, field));                  \
 120 } while (/*CONSTCOND*/ 0)
 121
 122 /* Generates prototypes and inline functions */
 123 #define PSCNV_RB_PROTOTYPE(name, type, field, cmp)                              \
 124         PSCNV_RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
 125 #define PSCNV_RB_PROTOTYPE_STATIC(name, type, field, cmp)                       \
 126         PSCNV_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 127 #define PSCNV_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)               \
 128 attr void name##_PSCNV_RB_INSERT_COLOR(struct name *, struct type *);           \
 129 attr void name##_PSCNV_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
 130 attr struct type *name##_PSCNV_RB_REMOVE(struct name *, struct type *); \
 131 attr struct type *name##_PSCNV_RB_INSERT(struct name *, struct type *); \
 132 attr struct type *name##_PSCNV_RB_FIND(struct name *, struct type *);           \
 133 attr struct type *name##_PSCNV_RB_NFIND(struct name *, struct type *);  \
 134 attr struct type *name##_PSCNV_RB_NEXT(struct type *);                  \
 135 attr struct type *name##_PSCNV_RB_PREV(struct type *);                  \
 136 attr struct type *name##_PSCNV_RB_MINMAX(struct name *, int);                   \
 137                                                                         \
 138
 139 /* Main rb operation.
 140  * Moves node close to the key of elm to top
 141  */
 142 #define PSCNV_RB_GENERATE(name, type, field, cmp)                               \
 143         PSCNV_RB_GENERATE_INTERNAL(name, type, field, cmp,)
 144 #define PSCNV_RB_GENERATE_STATIC(name, type, field, cmp)                        \
 145         PSCNV_RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 146 #define PSCNV_RB_GENERATE_INTERNAL(name, type, field, cmp, attr)                \
 147 attr void                                                               \
 148 name##_PSCNV_RB_INSERT_COLOR(struct name *head, struct type *elm)               \
 149 {                                                                       \
 150         struct type *parent, *gparent, *tmp;                            \
 151         while ((parent = PSCNV_RB_PARENT(elm, field)) != NULL &&                \
 152             PSCNV_RB_COLOR(parent, field) == PSCNV_RB_RED) {                    \
 153                 gparent = PSCNV_RB_PARENT(parent, field);                       \
 154                 if (parent == PSCNV_RB_LEFT(gparent, field)) {          \
 155                         tmp = PSCNV_RB_RIGHT(gparent, field);                   \
 156                         if (tmp && PSCNV_RB_COLOR(tmp, field) == PSCNV_RB_RED) {        \
 157                                 PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_BLACK;    \
 158                                 PSCNV_RB_SET_BLACKRED(parent, gparent, field);\
 159                                 elm = gparent;                          \
 160                                 continue;                               \
 161                         }                                               \
 162                         if (PSCNV_RB_RIGHT(parent, field) == elm) {             \
 163                                 PSCNV_RB_ROTATE_LEFT(head, parent, tmp, field);\
 164                                 tmp = parent;                           \
 165                                 parent = elm;                           \
 166                                 elm = tmp;                              \
 167                         }                                               \
 168                         PSCNV_RB_SET_BLACKRED(parent, gparent, field);  \
 169                         PSCNV_RB_ROTATE_RIGHT(head, gparent, tmp, field);       \
 170                 } else {                                                \
 171                         tmp = PSCNV_RB_LEFT(gparent, field);                    \
 172                         if (tmp && PSCNV_RB_COLOR(tmp, field) == PSCNV_RB_RED) {        \
 173                                 PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_BLACK;    \
 174                                 PSCNV_RB_SET_BLACKRED(parent, gparent, field);\
 175                                 elm = gparent;                          \
 176                                 continue;                               \
 177                         }                                               \
 178                         if (PSCNV_RB_LEFT(parent, field) == elm) {              \
 179                                 PSCNV_RB_ROTATE_RIGHT(head, parent, tmp, field);\
 180                                 tmp = parent;                           \
 181                                 parent = elm;                           \
 182                                 elm = tmp;                              \
 183                         }                                               \
 184                         PSCNV_RB_SET_BLACKRED(parent, gparent, field);  \
 185                         PSCNV_RB_ROTATE_LEFT(head, gparent, tmp, field);        \
 186                 }                                                       \
 187         }                                                               \
 188         PSCNV_RB_COLOR(head->rbh_root, field) = PSCNV_RB_BLACK;                 \
 189 }                                                                       \
 190                                                                         \
 191 attr void                                                               \
 192 name##_PSCNV_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
 193 {                                                                       \
 194         struct type *tmp;                                               \
 195         while ((elm == NULL || PSCNV_RB_COLOR(elm, field) == PSCNV_RB_BLACK) && \
 196             elm != PSCNV_RB_ROOT(head)) {                                       \
 197                 if (PSCNV_RB_LEFT(parent, field) == elm) {                      \
 198                         tmp = PSCNV_RB_RIGHT(parent, field);                    \
 199                         if (PSCNV_RB_COLOR(tmp, field) == PSCNV_RB_RED) {               \
 200                                 PSCNV_RB_SET_BLACKRED(tmp, parent, field);      \
 201                                 PSCNV_RB_ROTATE_LEFT(head, parent, tmp, field);\
 202                                 tmp = PSCNV_RB_RIGHT(parent, field);            \
 203                         }                                               \
 204                         if ((PSCNV_RB_LEFT(tmp, field) == NULL ||               \
 205                             PSCNV_RB_COLOR(PSCNV_RB_LEFT(tmp, field), field) == PSCNV_RB_BLACK) &&\
 206                             (PSCNV_RB_RIGHT(tmp, field) == NULL ||              \
 207                             PSCNV_RB_COLOR(PSCNV_RB_RIGHT(tmp, field), field) == PSCNV_RB_BLACK)) {\
 208                                 PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_RED;              \
 209                                 elm = parent;                           \
 210                                 parent = PSCNV_RB_PARENT(elm, field);           \
 211                         } else {                                        \
 212                                 if (PSCNV_RB_RIGHT(tmp, field) == NULL ||       \
 213                                     PSCNV_RB_COLOR(PSCNV_RB_RIGHT(tmp, field), field) == PSCNV_RB_BLACK) {\
 214                                         struct type *oleft;             \
 215                                         if ((oleft = PSCNV_RB_LEFT(tmp, field)) \
 216                                             != NULL)                    \
 217                                                 PSCNV_RB_COLOR(oleft, field) = PSCNV_RB_BLACK;\
 218                                         PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_RED;      \
 219                                         PSCNV_RB_ROTATE_RIGHT(head, tmp, oleft, field);\
 220                                         tmp = PSCNV_RB_RIGHT(parent, field);    \
 221                                 }                                       \
 222                                 PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_COLOR(parent, field);\
 223                                 PSCNV_RB_COLOR(parent, field) = PSCNV_RB_BLACK; \
 224                                 if (PSCNV_RB_RIGHT(tmp, field))         \
 225                                         PSCNV_RB_COLOR(PSCNV_RB_RIGHT(tmp, field), field) = PSCNV_RB_BLACK;\
 226                                 PSCNV_RB_ROTATE_LEFT(head, parent, tmp, field);\
 227                                 elm = PSCNV_RB_ROOT(head);                      \
 228                                 break;                                  \
 229                         }                                               \
 230                 } else {                                                \
 231                         tmp = PSCNV_RB_LEFT(parent, field);                     \
 232                         if (PSCNV_RB_COLOR(tmp, field) == PSCNV_RB_RED) {               \
 233                                 PSCNV_RB_SET_BLACKRED(tmp, parent, field);      \
 234                                 PSCNV_RB_ROTATE_RIGHT(head, parent, tmp, field);\
 235                                 tmp = PSCNV_RB_LEFT(parent, field);             \
 236                         }                                               \
 237                         if ((PSCNV_RB_LEFT(tmp, field) == NULL ||               \
 238                             PSCNV_RB_COLOR(PSCNV_RB_LEFT(tmp, field), field) == PSCNV_RB_BLACK) &&\
 239                             (PSCNV_RB_RIGHT(tmp, field) == NULL ||              \
 240                             PSCNV_RB_COLOR(PSCNV_RB_RIGHT(tmp, field), field) == PSCNV_RB_BLACK)) {\
 241                                 PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_RED;              \
 242                                 elm = parent;                           \
 243                                 parent = PSCNV_RB_PARENT(elm, field);           \
 244                         } else {                                        \
 245                                 if (PSCNV_RB_LEFT(tmp, field) == NULL ||        \
 246                                     PSCNV_RB_COLOR(PSCNV_RB_LEFT(tmp, field), field) == PSCNV_RB_BLACK) {\
 247                                         struct type *oright;            \
 248                                         if ((oright = PSCNV_RB_RIGHT(tmp, field)) \
 249                                             != NULL)                    \
 250                                                 PSCNV_RB_COLOR(oright, field) = PSCNV_RB_BLACK;\
 251                                         PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_RED;      \
 252                                         PSCNV_RB_ROTATE_LEFT(head, tmp, oright, field);\
 253                                         tmp = PSCNV_RB_LEFT(parent, field);     \
 254                                 }                                       \
 255                                 PSCNV_RB_COLOR(tmp, field) = PSCNV_RB_COLOR(parent, field);\
 256                                 PSCNV_RB_COLOR(parent, field) = PSCNV_RB_BLACK; \
 257                                 if (PSCNV_RB_LEFT(tmp, field))          \
 258                                         PSCNV_RB_COLOR(PSCNV_RB_LEFT(tmp, field), field) = PSCNV_RB_BLACK;\
 259                                 PSCNV_RB_ROTATE_RIGHT(head, parent, tmp, field);\
 260                                 elm = PSCNV_RB_ROOT(head);                      \
 261                                 break;                                  \
 262                         }                                               \
 263                 }                                                       \
 264         }                                                               \
 265         if (elm)                                                        \
 266                 PSCNV_RB_COLOR(elm, field) = PSCNV_RB_BLACK;                    \
 267 }                                                                       \
 268                                                                         \
 269 attr struct type *                                                      \
 270 name##_PSCNV_RB_REMOVE(struct name *head, struct type *elm)                     \
 271 {                                                                       \
 272         struct type *child, *parent, *old = elm;                        \
 273         int color;                                                      \
 274         if (PSCNV_RB_LEFT(elm, field) == NULL)                          \
 275                 child = PSCNV_RB_RIGHT(elm, field);                             \
 276         else if (PSCNV_RB_RIGHT(elm, field) == NULL)                            \
 277                 child = PSCNV_RB_LEFT(elm, field);                              \
 278         else {                                                          \
 279                 struct type *left;                                      \
 280                 elm = PSCNV_RB_RIGHT(elm, field);                               \
 281                 while ((left = PSCNV_RB_LEFT(elm, field)) != NULL)              \
 282                         elm = left;                                     \
 283                 child = PSCNV_RB_RIGHT(elm, field);                             \
 284                 parent = PSCNV_RB_PARENT(elm, field);                           \
 285                 color = PSCNV_RB_COLOR(elm, field);                             \
 286                 if (child)                                              \
 287                         PSCNV_RB_PARENT(child, field) = parent;         \
 288                 if (parent) {                                           \
 289                         if (PSCNV_RB_LEFT(parent, field) == elm)                \
 290                                 PSCNV_RB_LEFT(parent, field) = child;           \
 291                         else                                            \
 292                                 PSCNV_RB_RIGHT(parent, field) = child;  \
 293                         PSCNV_RB_AUGMENT(parent);                               \
 294                 } else                                                  \
 295                         PSCNV_RB_ROOT(head) = child;                            \
 296                 if (PSCNV_RB_PARENT(elm, field) == old)                 \
 297                         parent = elm;                                   \
 298                 (elm)->field = (old)->field;                            \
 299                 if (PSCNV_RB_PARENT(old, field)) {                              \
 300                         if (PSCNV_RB_LEFT(PSCNV_RB_PARENT(old, field), field) == old)\
 301                                 PSCNV_RB_LEFT(PSCNV_RB_PARENT(old, field), field) = elm;\
 302                         else                                            \
 303                                 PSCNV_RB_RIGHT(PSCNV_RB_PARENT(old, field), field) = elm;\
 304                         PSCNV_RB_AUGMENT(PSCNV_RB_PARENT(old, field));          \
 305                 } else                                                  \
 306                         PSCNV_RB_ROOT(head) = elm;                              \
 307                 PSCNV_RB_PARENT(PSCNV_RB_LEFT(old, field), field) = elm;                \
 308                 if (PSCNV_RB_RIGHT(old, field))                         \
 309                         PSCNV_RB_PARENT(PSCNV_RB_RIGHT(old, field), field) = elm;       \
 310                 if (parent) {                                           \
 311                         left = parent;                                  \
 312                         do {                                            \
 313                                 PSCNV_RB_AUGMENT(left);                 \
 314                         } while ((left = PSCNV_RB_PARENT(left, field)) != NULL); \
 315                 }                                                       \
 316                 goto color;                                             \
 317         }                                                               \
 318         parent = PSCNV_RB_PARENT(elm, field);                                   \
 319         color = PSCNV_RB_COLOR(elm, field);                                     \
 320         if (child)                                                      \
 321                 PSCNV_RB_PARENT(child, field) = parent;                 \
 322         if (parent) {                                                   \
 323                 if (PSCNV_RB_LEFT(parent, field) == elm)                        \
 324                         PSCNV_RB_LEFT(parent, field) = child;                   \
 325                 else                                                    \
 326                         PSCNV_RB_RIGHT(parent, field) = child;          \
 327                 PSCNV_RB_AUGMENT(parent);                                       \
 328         } else                                                          \
 329                 PSCNV_RB_ROOT(head) = child;                                    \
 330 color:                                                                  \
 331         if (color == PSCNV_RB_BLACK)                                            \
 332                 name##_PSCNV_RB_REMOVE_COLOR(head, parent, child);              \
 333         return (old);                                                   \
 334 }                                                                       \
 335                                                                         \
 336 /* Inserts a node into the RB tree */                                   \
 337 attr struct type *                                                      \
 338 name##_PSCNV_RB_INSERT(struct name *head, struct type *elm)                     \
 339 {                                                                       \
 340         struct type *tmp;                                               \
 341         struct type *parent = NULL;                                     \
 342         int comp = 0;                                                   \
 343         tmp = PSCNV_RB_ROOT(head);                                              \
 344         while (tmp) {                                                   \
 345                 parent = tmp;                                           \
 346                 comp = (cmp)(elm, parent);                              \
 347                 if (comp < 0)                                           \
 348                         tmp = PSCNV_RB_LEFT(tmp, field);                        \
 349                 else if (comp > 0)                                      \
 350                         tmp = PSCNV_RB_RIGHT(tmp, field);                       \
 351                 else                                                    \
 352                         return (tmp);                                   \
 353         }                                                               \
 354         PSCNV_RB_SET(elm, parent, field);                                       \
 355         if (parent != NULL) {                                           \
 356                 if (comp < 0)                                           \
 357                         PSCNV_RB_LEFT(parent, field) = elm;                     \
 358                 else                                                    \
 359                         PSCNV_RB_RIGHT(parent, field) = elm;                    \
 360                 PSCNV_RB_AUGMENT(parent);                                       \
 361         } else                                                          \
 362                 PSCNV_RB_ROOT(head) = elm;                                      \
 363         name##_PSCNV_RB_INSERT_COLOR(head, elm);                                \
 364         return (NULL);                                                  \
 365 }                                                                       \
 366                                                                         \
 367 /* Finds the node with the same key as elm */                           \
 368 attr struct type *                                                      \
 369 name##_PSCNV_RB_FIND(struct name *head, struct type *elm)                       \
 370 {                                                                       \
 371         struct type *tmp = PSCNV_RB_ROOT(head);                         \
 372         int comp;                                                       \
 373         while (tmp) {                                                   \
 374                 comp = cmp(elm, tmp);                                   \
 375                 if (comp < 0)                                           \
 376                         tmp = PSCNV_RB_LEFT(tmp, field);                        \
 377                 else if (comp > 0)                                      \
 378                         tmp = PSCNV_RB_RIGHT(tmp, field);                       \
 379                 else                                                    \
 380                         return (tmp);                                   \
 381         }                                                               \
 382         return (NULL);                                                  \
 383 }                                                                       \
 384                                                                         \
 385 /* Finds the first node greater than or equal to the search key */      \
 386 attr struct type *                                                      \
 387 name##_PSCNV_RB_NFIND(struct name *head, struct type *elm)                      \
 388 {                                                                       \
 389         struct type *tmp = PSCNV_RB_ROOT(head);                         \
 390         struct type *res = NULL;                                        \
 391         int comp;                                                       \
 392         while (tmp) {                                                   \
 393                 comp = cmp(elm, tmp);                                   \
 394                 if (comp < 0) {                                         \
 395                         res = tmp;                                      \
 396                         tmp = PSCNV_RB_LEFT(tmp, field);                        \
 397                 }                                                       \
 398                 else if (comp > 0)                                      \
 399                         tmp = PSCNV_RB_RIGHT(tmp, field);                       \
 400                 else                                                    \
 401                         return (tmp);                                   \
 402         }                                                               \
 403         return (res);                                                   \
 404 }                                                                       \
 405                                                                         \
 406 /* ARGSUSED */                                                          \
 407 attr struct type *                                                      \
 408 name##_PSCNV_RB_NEXT(struct type *elm)                                  \
 409 {                                                                       \
 410         if (PSCNV_RB_RIGHT(elm, field)) {                                       \
 411                 elm = PSCNV_RB_RIGHT(elm, field);                               \
 412                 while (PSCNV_RB_LEFT(elm, field))                               \
 413                         elm = PSCNV_RB_LEFT(elm, field);                        \
 414         } else {                                                        \
 415                 if (PSCNV_RB_PARENT(elm, field) &&                              \
 416                     (elm == PSCNV_RB_LEFT(PSCNV_RB_PARENT(elm, field), field))) \
 417                         elm = PSCNV_RB_PARENT(elm, field);                      \
 418                 else {                                                  \
 419                         while (PSCNV_RB_PARENT(elm, field) &&                   \
 420                             (elm == PSCNV_RB_RIGHT(PSCNV_RB_PARENT(elm, field), field)))\
 421                                 elm = PSCNV_RB_PARENT(elm, field);              \
 422                         elm = PSCNV_RB_PARENT(elm, field);                      \
 423                 }                                                       \
 424         }                                                               \
 425         return (elm);                                                   \
 426 }                                                                       \
 427                                                                         \
 428 /* ARGSUSED */                                                          \
 429 attr struct type *                                                      \
 430 name##_PSCNV_RB_PREV(struct type *elm)                                  \
 431 {                                                                       \
 432         if (PSCNV_RB_LEFT(elm, field)) {                                        \
 433                 elm = PSCNV_RB_LEFT(elm, field);                                \
 434                 while (PSCNV_RB_RIGHT(elm, field))                              \
 435                         elm = PSCNV_RB_RIGHT(elm, field);                       \
 436         } else {                                                        \
 437                 if (PSCNV_RB_PARENT(elm, field) &&                              \
 438                     (elm == PSCNV_RB_RIGHT(PSCNV_RB_PARENT(elm, field), field)))        \
 439                         elm = PSCNV_RB_PARENT(elm, field);                      \
 440                 else {                                                  \
 441                         while (PSCNV_RB_PARENT(elm, field) &&                   \
 442                             (elm == PSCNV_RB_LEFT(PSCNV_RB_PARENT(elm, field), field)))\
 443                                 elm = PSCNV_RB_PARENT(elm, field);              \
 444                         elm = PSCNV_RB_PARENT(elm, field);                      \
 445                 }                                                       \
 446         }                                                               \
 447         return (elm);                                                   \
 448 }                                                                       \
 449                                                                         \
 450 attr struct type *                                                      \
 451 name##_PSCNV_RB_MINMAX(struct name *head, int val)                              \
 452 {                                                                       \
 453         struct type *tmp = PSCNV_RB_ROOT(head);                         \
 454         struct type *parent = NULL;                                     \
 455         while (tmp) {                                                   \
 456                 parent = tmp;                                           \
 457                 if (val < 0)                                            \
 458                         tmp = PSCNV_RB_LEFT(tmp, field);                        \
 459                 else                                                    \
 460                         tmp = PSCNV_RB_RIGHT(tmp, field);                       \
 461         }                                                               \
 462         return (parent);                                                \
 463 }
 464
 465 #define PSCNV_RB_NEGINF -1
 466 #define PSCNV_RB_INF    1
 467
 468 #define PSCNV_RB_INSERT(name, x, y)     name##_PSCNV_RB_INSERT(x, y)
 469 #define PSCNV_RB_REMOVE(name, x, y)     name##_PSCNV_RB_REMOVE(x, y)
 470 #define PSCNV_RB_FIND(name, x, y)       name##_PSCNV_RB_FIND(x, y)
 471 #define PSCNV_RB_NFIND(name, x, y)      name##_PSCNV_RB_NFIND(x, y)
 472 #define PSCNV_RB_NEXT(name, x, y)       name##_PSCNV_RB_NEXT(y)
 473 #define PSCNV_RB_PREV(name, x, y)       name##_PSCNV_RB_PREV(y)
 474 #define PSCNV_RB_MIN(name, x)           name##_PSCNV_RB_MINMAX(x, PSCNV_RB_NEGINF)
 475 #define PSCNV_RB_MAX(name, x)           name##_PSCNV_RB_MINMAX(x, PSCNV_RB_INF)
 476
 477 #define PSCNV_RB_FOREACH(x, name, head)                                 \
 478         for ((x) = PSCNV_RB_MIN(name, head);                                    \
 479              (x) != NULL;                                               \
 480              (x) = name##_PSCNV_RB_NEXT(x))
 481
 482 #define PSCNV_RB_FOREACH_REVERSE(x, name, head)                         \
 483         for ((x) = PSCNV_RB_MAX(name, head);                                    \
 484              (x) != NULL;                                               \
 485              (x) = name##_PSCNV_RB_PREV(x))
 486
 487 #endif  /* __PSCNV_TREE_H__ */