lib/openbsd-tree.h

   1 /*      $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt Exp $       */
   2 /*
   3  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #ifndef _SYS_TREE_H_
  28 #define _SYS_TREE_H_
  29
  30 /*
  31  * This file defines data structures for different types of trees:
  32  * splay trees and red-black trees.
  33  *
  34  * A splay tree is a self-organizing data structure.  Every operation
  35  * on the tree causes a splay to happen.  The splay moves the requested
  36  * node to the root of the tree and partly rebalances it.
  37  *
  38  * This has the benefit that request locality causes faster lookups as
  39  * the requested nodes move to the top of the tree.  On the other hand,
  40  * every lookup causes memory writes.
  41  *
  42  * The Balance Theorem bounds the total access time for m operations
  43  * and n inserts on an initially empty tree as O((m + n)lg n).  The
  44  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
  45  *
  46  * A red-black tree is a binary search tree with the node color as an
  47  * extra attribute.  It fulfills a set of conditions:
  48  *      - every search path from the root to a leaf consists of the
  49  *        same number of black nodes,
  50  *      - each red node (except for the root) has a black parent,
  51  *      - each leaf node is black.
  52  *
  53  * Every operation on a red-black tree is bounded as O(lg n).
  54  * The maximum height of a red-black tree is 2lg (n+1).
  55  */
  56
  57 #define SPLAY_HEAD(name, type)                                                 \
  58         struct name {                                                          \
  59                 struct type *sph_root; /* root of the tree */                  \
  60         }
  61
  62 #define SPLAY_INITIALIZER(root)                                                \
  63         {                                                                      \
  64                 NULL                                                           \
  65         }
  66
  67 #define SPLAY_INIT(root)                                                       \
  68         do {                                                                   \
  69                 (root)->sph_root = NULL;                                       \
  70         } while (0)
  71
  72 #define SPLAY_ENTRY(type)                                                      \
  73         struct {                                                               \
  74                 struct type *spe_left;  /* left element */                     \
  75                 struct type *spe_right; /* right element */                    \
  76         }
  77
  78 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
  79 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
  80 #define SPLAY_ROOT(head)                (head)->sph_root
  81 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
  82
  83 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
  84 #define SPLAY_ROTATE_RIGHT(head, tmp, field)                                   \
  85         do {                                                                   \
  86                 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
  87                 SPLAY_RIGHT(tmp, field) = (head)->sph_root;                    \
  88                 (head)->sph_root = tmp;                                        \
  89         } while (0)
  90
  91 #define SPLAY_ROTATE_LEFT(head, tmp, field)                                    \
  92         do {                                                                   \
  93                 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
  94                 SPLAY_LEFT(tmp, field) = (head)->sph_root;                     \
  95                 (head)->sph_root = tmp;                                        \
  96         } while (0)
  97
  98 #define SPLAY_LINKLEFT(head, tmp, field)                                       \
  99         do {                                                                   \
 100                 SPLAY_LEFT(tmp, field) = (head)->sph_root;                     \
 101                 tmp = (head)->sph_root;                                        \
 102                 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);        \
 103         } while (0)
 104
 105 #define SPLAY_LINKRIGHT(head, tmp, field)                                      \
 106         do {                                                                   \
 107                 SPLAY_RIGHT(tmp, field) = (head)->sph_root;                    \
 108                 tmp = (head)->sph_root;                                        \
 109                 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);       \
 110         } while (0)
 111
 112 #define SPLAY_ASSEMBLE(head, node, left, right, field)                         \
 113         do {                                                                   \
 114                 SPLAY_RIGHT(left, field) =                                     \
 115                         SPLAY_LEFT((head)->sph_root, field);                   \
 116                 SPLAY_LEFT(right, field) =                                     \
 117                         SPLAY_RIGHT((head)->sph_root, field);                  \
 118                 SPLAY_LEFT((head)->sph_root, field) =                          \
 119                         SPLAY_RIGHT(node, field);                              \
 120                 SPLAY_RIGHT((head)->sph_root, field) =                         \
 121                         SPLAY_LEFT(node, field);                               \
 122         } while (0)
 123
 124 /* Generates prototypes and inline functions */
 125
 126 #define SPLAY_PROTOTYPE(name, type, field, cmp)                                \
 127         void name##_SPLAY(struct name *, struct type *);                       \
 128         void name##_SPLAY_MINMAX(struct name *, int);                          \
 129         struct type *name##_SPLAY_INSERT(struct name *, struct type *);        \
 130         struct type *name##_SPLAY_REMOVE(struct name *, struct type *);        \
 131                                                                                \
 132         /* Finds the node with the same key as elm */                          \
 133         static __inline struct type *name##_SPLAY_FIND(struct name *head,      \
 134                                                        struct type *elm)       \
 135         {                                                                      \
 136                 if (SPLAY_EMPTY(head))                                         \
 137                         return (NULL);                                         \
 138                 name##_SPLAY(head, elm);                                       \
 139                 if ((cmp)(elm, (head)->sph_root) == 0)                         \
 140                         return (head->sph_root);                               \
 141                 return (NULL);                                                 \
 142         }                                                                      \
 143                                                                                \
 144         static __inline struct type *name##_SPLAY_NEXT(struct name *head,      \
 145                                                        struct type *elm)       \
 146         {                                                                      \
 147                 name##_SPLAY(head, elm);                                       \
 148                 if (SPLAY_RIGHT(elm, field) != NULL) {                         \
 149                         elm = SPLAY_RIGHT(elm, field);                         \
 150                         while (SPLAY_LEFT(elm, field) != NULL) {               \
 151                                 elm = SPLAY_LEFT(elm, field);                  \
 152                         }                                                      \
 153                 } else                                                         \
 154                         elm = NULL;                                            \
 155                 return (elm);                                                  \
 156         }                                                                      \
 157                                                                                \
 158         static __inline struct type *name##_SPLAY_MIN_MAX(struct name *head,   \
 159                                                           int val)             \
 160         {                                                                      \
 161                 name##_SPLAY_MINMAX(head, val);                                \
 162                 return (SPLAY_ROOT(head));                                     \
 163         }
 164
 165 /* Main splay operation.
 166  * Moves node close to the key of elm to top
 167  */
 168 #define SPLAY_GENERATE(name, type, field, cmp)                                 \
 169         struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm)  \
 170         {                                                                      \
 171                 if (SPLAY_EMPTY(head)) {                                       \
 172                         SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) =     \
 173                                 NULL;                                          \
 174                 } else {                                                       \
 175                         int __comp;                                            \
 176                         name##_SPLAY(head, elm);                               \
 177                         __comp = (cmp)(elm, (head)->sph_root);                 \
 178                         if (__comp < 0) {                                      \
 179                                 SPLAY_LEFT(elm, field) =                       \
 180                                         SPLAY_LEFT((head)->sph_root, field);   \
 181                                 SPLAY_RIGHT(elm, field) = (head)->sph_root;    \
 182                                 SPLAY_LEFT((head)->sph_root, field) = NULL;    \
 183                         } else if (__comp > 0) {                               \
 184                                 SPLAY_RIGHT(elm, field) =                      \
 185                                         SPLAY_RIGHT((head)->sph_root, field);  \
 186                                 SPLAY_LEFT(elm, field) = (head)->sph_root;     \
 187                                 SPLAY_RIGHT((head)->sph_root, field) = NULL;   \
 188                         } else                                                 \
 189                                 return ((head)->sph_root);                     \
 190                 }                                                              \
 191                 (head)->sph_root = (elm);                                      \
 192                 return (NULL);                                                 \
 193         }                                                                      \
 194                                                                                \
 195         struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm)  \
 196         {                                                                      \
 197                 struct type *__tmp;                                            \
 198                 if (SPLAY_EMPTY(head))                                         \
 199                         return (NULL);                                         \
 200                 name##_SPLAY(head, elm);                                       \
 201                 if ((cmp)(elm, (head)->sph_root) == 0) {                       \
 202                         if (SPLAY_LEFT((head)->sph_root, field) == NULL) {     \
 203                                 (head)->sph_root =                             \
 204                                         SPLAY_RIGHT((head)->sph_root, field);  \
 205                         } else {                                               \
 206                                 __tmp = SPLAY_RIGHT((head)->sph_root, field);  \
 207                                 (head)->sph_root =                             \
 208                                         SPLAY_LEFT((head)->sph_root, field);   \
 209                                 name##_SPLAY(head, elm);                       \
 210                                 SPLAY_RIGHT((head)->sph_root, field) = __tmp;  \
 211                         }                                                      \
 212                         return (elm);                                          \
 213                 }                                                              \
 214                 return (NULL);                                                 \
 215         }                                                                      \
 216                                                                                \
 217         void name##_SPLAY(struct name *head, struct type *elm)                 \
 218         {                                                                      \
 219                 struct type __node, *__left, *__right, *__tmp;                 \
 220                 int __comp;                                                    \
 221                                                                                \
 222                 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) =     \
 223                         NULL;                                                  \
 224                 __left = __right = &__node;                                    \
 225                                                                                \
 226                 while ((__comp = (cmp)(elm, (head)->sph_root))) {              \
 227                         if (__comp < 0) {                                      \
 228                                 __tmp = SPLAY_LEFT((head)->sph_root, field);   \
 229                                 if (__tmp == NULL)                             \
 230                                         break;                                 \
 231                                 if ((cmp)(elm, __tmp) < 0) {                   \
 232                                         SPLAY_ROTATE_RIGHT(head, __tmp,        \
 233                                                            field);             \
 234                                         if (SPLAY_LEFT((head)->sph_root,       \
 235                                                        field)                  \
 236                                             == NULL)                           \
 237                                                 break;                         \
 238                                 }                                              \
 239                                 SPLAY_LINKLEFT(head, __right, field);          \
 240                         } else if (__comp > 0) {                               \
 241                                 __tmp = SPLAY_RIGHT((head)->sph_root, field);  \
 242                                 if (__tmp == NULL)                             \
 243                                         break;                                 \
 244                                 if ((cmp)(elm, __tmp) > 0) {                   \
 245                                         SPLAY_ROTATE_LEFT(head, __tmp, field); \
 246                                         if (SPLAY_RIGHT((head)->sph_root,      \
 247                                                         field)                 \
 248                                             == NULL)                           \
 249                                                 break;                         \
 250                                 }                                              \
 251                                 SPLAY_LINKRIGHT(head, __left, field);          \
 252                         }                                                      \
 253                 }                                                              \
 254                 SPLAY_ASSEMBLE(head, &__node, __left, __right, field);         \
 255         }                                                                      \
 256                                                                                \
 257         /* Splay with either the minimum or the maximum element                \
 258          * Used to find minimum or maximum element in tree.                    \
 259          */                                                                    \
 260         void name##_SPLAY_MINMAX(struct name *head, int __comp)                \
 261         {                                                                      \
 262                 struct type __node, *__left, *__right, *__tmp;                 \
 263                                                                                \
 264                 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) =     \
 265                         NULL;                                                  \
 266                 __left = __right = &__node;                                    \
 267                                                                                \
 268                 while (1) {                                                    \
 269                         if (__comp < 0) {                                      \
 270                                 __tmp = SPLAY_LEFT((head)->sph_root, field);   \
 271                                 if (__tmp == NULL)                             \
 272                                         break;                                 \
 273                                 if (__comp < 0) {                              \
 274                                         SPLAY_ROTATE_RIGHT(head, __tmp,        \
 275                                                            field);             \
 276                                         if (SPLAY_LEFT((head)->sph_root,       \
 277                                                        field)                  \
 278                                             == NULL)                           \
 279                                                 break;                         \
 280                                 }                                              \
 281                                 SPLAY_LINKLEFT(head, __right, field);          \
 282                         } else if (__comp > 0) {                               \
 283                                 __tmp = SPLAY_RIGHT((head)->sph_root, field);  \
 284                                 if (__tmp == NULL)                             \
 285                                         break;                                 \
 286                                 if (__comp > 0) {                              \
 287                                         SPLAY_ROTATE_LEFT(head, __tmp, field); \
 288                                         if (SPLAY_RIGHT((head)->sph_root,      \
 289                                                         field)                 \
 290                                             == NULL)                           \
 291                                                 break;                         \
 292                                 }                                              \
 293                                 SPLAY_LINKRIGHT(head, __left, field);          \
 294                         }                                                      \
 295                 }                                                              \
 296                 SPLAY_ASSEMBLE(head, &__node, __left, __right, field);         \
 297         }
 298
 299 #define SPLAY_NEGINF    -1
 300 #define SPLAY_INF       1
 301
 302 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
 303 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
 304 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
 305 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
 306 #define SPLAY_MIN(name, x)                                                     \
 307         (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
 308 #define SPLAY_MAX(name, x)                                                     \
 309         (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
 310
 311 #define SPLAY_FOREACH(x, name, head)                                           \
 312         for ((x) = SPLAY_MIN(name, head); (x) != NULL;                         \
 313              (x) = SPLAY_NEXT(name, head, x))
 314
 315 /*
 316  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
 317  *
 318  * Permission to use, copy, modify, and distribute this software for any
 319  * purpose with or without fee is hereby granted, provided that the above
 320  * copyright notice and this permission notice appear in all copies.
 321  *
 322  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 323  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 324  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 325  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 326  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 327  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 328  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 329  */
 330
 331 #define RB_BLACK        0
 332 #define RB_RED          1
 333
 334 struct rb_type {
 335         int (*t_compare)(const void *, const void *);
 336         void (*t_augment)(void *);
 337         unsigned int t_offset; /* offset of rb_entry in type */
 338 };
 339
 340 struct rbt_tree {
 341         struct rb_entry *rbt_root;
 342 };
 343
 344 struct rb_entry {
 345         struct rb_entry *rbt_parent;
 346         struct rb_entry *rbt_left;
 347         struct rb_entry *rbt_right;
 348         unsigned int rbt_color;
 349 };
 350
 351 #define RB_HEAD(_name, _type)                                                  \
 352         struct _name {                                                         \
 353                 struct rbt_tree rbh_root;                                      \
 354         }
 355
 356 #define RB_ENTRY(_type) struct rb_entry
 357
 358 static inline void _rb_init(struct rbt_tree *rbt)
 359 {
 360         rbt->rbt_root = NULL;
 361 }
 362
 363 static inline int _rb_empty(struct rbt_tree *rbt)
 364 {
 365         return (rbt->rbt_root == NULL);
 366 }
 367
 368 void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *);
 369 void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *);
 370 void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *);
 371 void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *);
 372 void *_rb_root(const struct rb_type *, struct rbt_tree *);
 373 void *_rb_min(const struct rb_type *, struct rbt_tree *);
 374 void *_rb_max(const struct rb_type *, struct rbt_tree *);
 375 void *_rb_next(const struct rb_type *, void *);
 376 void *_rb_prev(const struct rb_type *, void *);
 377 void *_rb_left(const struct rb_type *, void *);
 378 void *_rb_right(const struct rb_type *, void *);
 379 void *_rb_parent(const struct rb_type *, void *);
 380 void _rb_set_left(const struct rb_type *, void *, void *);
 381 void _rb_set_right(const struct rb_type *, void *, void *);
 382 void _rb_set_parent(const struct rb_type *, void *, void *);
 383 void _rb_poison(const struct rb_type *, void *, unsigned long);
 384 int _rb_check(const struct rb_type *, void *, unsigned long);
 385
 386 #define RB_INITIALIZER(_head)   { { NULL } }
 387
 388 #define RB_PROTOTYPE(_name, _type, _field, _cmp)                               \
 389         extern const struct rb_type *const _name##_RB_TYPE;                    \
 390                                                                                \
 391         __attribute__((__unused__)) static inline void _name##_RB_INIT(        \
 392                 struct _name *head)                                            \
 393         {                                                                      \
 394                 _rb_init(&head->rbh_root);                                     \
 395         }                                                                      \
 396                                                                                \
 397         __attribute__((__unused__)) static inline struct _type                 \
 398                 *_name##_RB_INSERT(struct _name *head, struct _type *elm)      \
 399         {                                                                      \
 400                 return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm);      \
 401         }                                                                      \
 402                                                                                \
 403         __attribute__((__unused__)) static inline struct _type                 \
 404                 *_name##_RB_REMOVE(struct _name *head, struct _type *elm)      \
 405         {                                                                      \
 406                 return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm);      \
 407         }                                                                      \
 408                                                                                \
 409         __attribute__((__unused__)) static inline struct _type                 \
 410                 *_name##_RB_FIND(struct _name *head, const struct _type *key)  \
 411         {                                                                      \
 412                 return _rb_find(_name##_RB_TYPE, &head->rbh_root, key);        \
 413         }                                                                      \
 414                                                                                \
 415         __attribute__((__unused__)) static inline struct _type                 \
 416                 *_name##_RB_NFIND(struct _name *head, const struct _type *key) \
 417         {                                                                      \
 418                 return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key);       \
 419         }                                                                      \
 420                                                                                \
 421         __attribute__((__unused__)) static inline struct _type                 \
 422                 *_name##_RB_ROOT(struct _name *head)                           \
 423         {                                                                      \
 424                 return _rb_root(_name##_RB_TYPE, &head->rbh_root);             \
 425         }                                                                      \
 426                                                                                \
 427         __attribute__((__unused__)) static inline int _name##_RB_EMPTY(        \
 428                 struct _name *head)                                            \
 429         {                                                                      \
 430                 return _rb_empty(&head->rbh_root);                             \
 431         }                                                                      \
 432                                                                                \
 433         __attribute__((__unused__)) static inline struct _type                 \
 434                 *_name##_RB_MIN(struct _name *head)                            \
 435         {                                                                      \
 436                 return _rb_min(_name##_RB_TYPE, &head->rbh_root);              \
 437         }                                                                      \
 438                                                                                \
 439         __attribute__((__unused__)) static inline struct _type                 \
 440                 *_name##_RB_MAX(struct _name *head)                            \
 441         {                                                                      \
 442                 return _rb_max(_name##_RB_TYPE, &head->rbh_root);              \
 443         }                                                                      \
 444                                                                                \
 445         __attribute__((__unused__)) static inline struct _type                 \
 446                 *_name##_RB_NEXT(struct _type *elm)                            \
 447         {                                                                      \
 448                 return _rb_next(_name##_RB_TYPE, elm);                         \
 449         }                                                                      \
 450                                                                                \
 451         __attribute__((__unused__)) static inline struct _type                 \
 452                 *_name##_RB_PREV(struct _type *elm)                            \
 453         {                                                                      \
 454                 return _rb_prev(_name##_RB_TYPE, elm);                         \
 455         }                                                                      \
 456                                                                                \
 457         __attribute__((__unused__)) static inline struct _type                 \
 458                 *_name##_RB_LEFT(struct _type *elm)                            \
 459         {                                                                      \
 460                 return _rb_left(_name##_RB_TYPE, elm);                         \
 461         }                                                                      \
 462                                                                                \
 463         __attribute__((__unused__)) static inline struct _type                 \
 464                 *_name##_RB_RIGHT(struct _type *elm)                           \
 465         {                                                                      \
 466                 return _rb_right(_name##_RB_TYPE, elm);                        \
 467         }                                                                      \
 468                                                                                \
 469         __attribute__((__unused__)) static inline struct _type                 \
 470                 *_name##_RB_PARENT(struct _type *elm)                          \
 471         {                                                                      \
 472                 return _rb_parent(_name##_RB_TYPE, elm);                       \
 473         }                                                                      \
 474                                                                                \
 475         __attribute__((__unused__)) static inline void _name##_RB_SET_LEFT(    \
 476                 struct _type *elm, struct _type *left)                         \
 477         {                                                                      \
 478                 _rb_set_left(_name##_RB_TYPE, elm, left);                      \
 479         }                                                                      \
 480                                                                                \
 481         __attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT(   \
 482                 struct _type *elm, struct _type *right)                        \
 483         {                                                                      \
 484                 _rb_set_right(_name##_RB_TYPE, elm, right);                    \
 485         }                                                                      \
 486                                                                                \
 487         __attribute__((__unused__)) static inline void _name##_RB_SET_PARENT(  \
 488                 struct _type *elm, struct _type *parent)                       \
 489         {                                                                      \
 490                 _rb_set_parent(_name##_RB_TYPE, elm, parent);                  \
 491         }                                                                      \
 492                                                                                \
 493         __attribute__((__unused__)) static inline void _name##_RB_POISON(      \
 494                 struct _type *elm, unsigned long poison)                       \
 495         {                                                                      \
 496                 _rb_poison(_name##_RB_TYPE, elm, poison);                      \
 497         }                                                                      \
 498                                                                                \
 499         __attribute__((__unused__)) static inline int _name##_RB_CHECK(        \
 500                 struct _type *elm, unsigned long poison)                       \
 501         {                                                                      \
 502                 return _rb_check(_name##_RB_TYPE, elm, poison);                \
 503         }
 504
 505 #define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)                 \
 506         static int _name##_RB_COMPARE(const void *lptr, const void *rptr)      \
 507         {                                                                      \
 508                 const struct _type *l = lptr, *r = rptr;                       \
 509                 return _cmp(l, r);                                             \
 510         }                                                                      \
 511         static const struct rb_type _name##_RB_INFO = {                        \
 512                 _name##_RB_COMPARE, _aug, offsetof(struct _type, _field),      \
 513         };                                                                     \
 514         const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO;
 515
 516 #define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug)                  \
 517         static void _name##_RB_AUGMENT(void *ptr)                              \
 518         {                                                                      \
 519                 struct _type *p = ptr;                                         \
 520                 return _aug(p);                                                \
 521         }                                                                      \
 522         RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT)
 523
 524 #define RB_GENERATE(_name, _type, _field, _cmp)                                \
 525         RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
 526
 527 #define RB_INIT(_name, _head)           _name##_RB_INIT(_head)
 528 #define RB_INSERT(_name, _head, _elm)   _name##_RB_INSERT(_head, _elm)
 529 #define RB_REMOVE(_name, _head, _elm)   _name##_RB_REMOVE(_head, _elm)
 530 #define RB_FIND(_name, _head, _key)     _name##_RB_FIND(_head, _key)
 531 #define RB_NFIND(_name, _head, _key)    _name##_RB_NFIND(_head, _key)
 532 #define RB_ROOT(_name, _head)           _name##_RB_ROOT(_head)
 533 #define RB_EMPTY(_name, _head)          _name##_RB_EMPTY(_head)
 534 #define RB_MIN(_name, _head)            _name##_RB_MIN(_head)
 535 #define RB_MAX(_name, _head)            _name##_RB_MAX(_head)
 536 #define RB_NEXT(_name, _elm)            _name##_RB_NEXT(_elm)
 537 #define RB_PREV(_name, _elm)            _name##_RB_PREV(_elm)
 538 #define RB_LEFT(_name, _elm)            _name##_RB_LEFT(_elm)
 539 #define RB_RIGHT(_name, _elm)           _name##_RB_RIGHT(_elm)
 540 #define RB_PARENT(_name, _elm)          _name##_RB_PARENT(_elm)
 541 #define RB_SET_LEFT(_name, _elm, _l)    _name##_RB_SET_LEFT(_elm, _l)
 542 #define RB_SET_RIGHT(_name, _elm, _r)   _name##_RB_SET_RIGHT(_elm, _r)
 543 #define RB_SET_PARENT(_name, _elm, _p)  _name##_RB_SET_PARENT(_elm, _p)
 544 #define RB_POISON(_name, _elm, _p)      _name##_RB_POISON(_elm, _p)
 545 #define RB_CHECK(_name, _elm, _p)       _name##_RB_CHECK(_elm, _p)
 546
 547 #define RB_FOREACH(_e, _name, _head)                                           \
 548         for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL;                      \
 549              (_e) = RB_NEXT(_name, (_e)))
 550
 551 #define RB_FOREACH_SAFE(_e, _name, _head, _n)                                  \
 552         for ((_e) = RB_MIN(_name, (_head));                                    \
 553              (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n))
 554
 555 #define RB_FOREACH_REVERSE(_e, _name, _head)                                   \
 556         for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL;                      \
 557              (_e) = RB_PREV(_name, (_e)))
 558
 559 #define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n)                          \
 560         for ((_e) = RB_MAX(_name, (_head));                                    \
 561              (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n))
 562
 563 #endif /* _SYS_TREE_H_ */