libkern/libkern/tree.h

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