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