lib/openbsd-tree.c

   1 /*      $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
   2
   3 /*
   4  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 /*
  29  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
  30  *
  31  * Permission to use, copy, modify, and distribute this software for any
  32  * purpose with or without fee is hereby granted, provided that the above
  33  * copyright notice and this permission notice appear in all copies.
  34  *
  35  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  36  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  37  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  38  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  39  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  40  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  41  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  42  */
  43
  44 #include <stdlib.h>
  45
  46 #include <lib/openbsd-tree.h>
  47
  48 static inline struct rb_entry *
  49 rb_n2e(const struct rb_type *t, void *node)
  50 {
  51         unsigned long addr = (unsigned long)node;
  52
  53         return ((struct rb_entry *)(addr + t->t_offset));
  54 }
  55
  56 static inline void *
  57 rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
  58 {
  59         unsigned long addr = (unsigned long)rbe;
  60
  61         return ((void *)(addr - t->t_offset));
  62 }
  63
  64 #define RBE_LEFT(_rbe)          (_rbe)->rbt_left
  65 #define RBE_RIGHT(_rbe)         (_rbe)->rbt_right
  66 #define RBE_PARENT(_rbe)        (_rbe)->rbt_parent
  67 #define RBE_COLOR(_rbe)         (_rbe)->rbt_color
  68
  69 #define RBH_ROOT(_rbt)          (_rbt)->rbt_root
  70
  71 static inline void
  72 rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
  73 {
  74         RBE_PARENT(rbe) = parent;
  75         RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
  76         RBE_COLOR(rbe) = RB_RED;
  77 }
  78
  79 static inline void
  80 rbe_set_blackred(struct rb_entry *black, struct rb_entry *red)
  81 {
  82         RBE_COLOR(black) = RB_BLACK;
  83         RBE_COLOR(red) = RB_RED;
  84 }
  85
  86 static inline void
  87 rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
  88 {
  89         (*t->t_augment)(rb_e2n(t, rbe));
  90 }
  91
  92 static inline void
  93 rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
  94 {
  95         if (t->t_augment != NULL)
  96                 rbe_augment(t, rbe);
  97 }
  98
  99 static inline void
 100 rbe_rotate_left(const struct rb_type *t, struct rbt_tree *rbt,
 101     struct rb_entry *rbe)
 102 {
 103         struct rb_entry *parent;
 104         struct rb_entry *tmp;
 105
 106         tmp = RBE_RIGHT(rbe);
 107         RBE_RIGHT(rbe) = RBE_LEFT(tmp);
 108         if (RBE_RIGHT(rbe) != NULL)
 109                 RBE_PARENT(RBE_LEFT(tmp)) = rbe;
 110
 111         parent = RBE_PARENT(rbe);
 112         RBE_PARENT(tmp) = parent;
 113         if (parent != NULL) {
 114                 if (rbe == RBE_LEFT(parent))
 115                         RBE_LEFT(parent) = tmp;
 116                 else
 117                         RBE_RIGHT(parent) = tmp;
 118         } else
 119                 RBH_ROOT(rbt) = tmp;
 120
 121         RBE_LEFT(tmp) = rbe;
 122         RBE_PARENT(rbe) = tmp;
 123
 124         if (t->t_augment != NULL) {
 125                 rbe_augment(t, rbe);
 126                 rbe_augment(t, tmp);
 127                 parent = RBE_PARENT(tmp);
 128                 if (parent != NULL)
 129                         rbe_augment(t, parent);
 130         }
 131 }
 132
 133 static inline void
 134 rbe_rotate_right(const struct rb_type *t, struct rbt_tree *rbt,
 135     struct rb_entry *rbe)
 136 {
 137         struct rb_entry *parent;
 138         struct rb_entry *tmp;
 139
 140         tmp = RBE_LEFT(rbe);
 141         RBE_LEFT(rbe) = RBE_RIGHT(tmp);
 142         if (RBE_LEFT(rbe) != NULL)
 143                 RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
 144
 145         parent = RBE_PARENT(rbe);
 146         RBE_PARENT(tmp) = parent;
 147         if (parent != NULL) {
 148                 if (rbe == RBE_LEFT(parent))
 149                         RBE_LEFT(parent) = tmp;
 150                 else
 151                         RBE_RIGHT(parent) = tmp;
 152         } else
 153                 RBH_ROOT(rbt) = tmp;
 154
 155         RBE_RIGHT(tmp) = rbe;
 156         RBE_PARENT(rbe) = tmp;
 157
 158         if (t->t_augment != NULL) {
 159                 rbe_augment(t, rbe);
 160                 rbe_augment(t, tmp);
 161                 parent = RBE_PARENT(tmp);
 162                 if (parent != NULL)
 163                         rbe_augment(t, parent);
 164         }
 165 }
 166
 167 static inline void
 168 rbe_insert_color(const struct rb_type *t, struct rbt_tree *rbt,
 169     struct rb_entry *rbe)
 170 {
 171         struct rb_entry *parent, *gparent, *tmp;
 172
 173         while ((parent = RBE_PARENT(rbe)) != NULL &&
 174             RBE_COLOR(parent) == RB_RED) {
 175                 gparent = RBE_PARENT(parent);
 176
 177                 if (parent == RBE_LEFT(gparent)) {
 178                         tmp = RBE_RIGHT(gparent);
 179                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 180                                 RBE_COLOR(tmp) = RB_BLACK;
 181                                 rbe_set_blackred(parent, gparent);
 182                                 rbe = gparent;
 183                                 continue;
 184                         }
 185
 186                         if (RBE_RIGHT(parent) == rbe) {
 187                                 rbe_rotate_left(t, rbt, parent);
 188                                 tmp = parent;
 189                                 parent = rbe;
 190                                 rbe = tmp;
 191                         }
 192
 193                         rbe_set_blackred(parent, gparent);
 194                         rbe_rotate_right(t, rbt, gparent);
 195                 } else {
 196                         tmp = RBE_LEFT(gparent);
 197                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 198                                 RBE_COLOR(tmp) = RB_BLACK;
 199                                 rbe_set_blackred(parent, gparent);
 200                                 rbe = gparent;
 201                                 continue;
 202                         }
 203
 204                         if (RBE_LEFT(parent) == rbe) {
 205                                 rbe_rotate_right(t, rbt, parent);
 206                                 tmp = parent;
 207                                 parent = rbe;
 208                                 rbe = tmp;
 209                         }
 210
 211                         rbe_set_blackred(parent, gparent);
 212                         rbe_rotate_left(t, rbt, gparent);
 213                 }
 214         }
 215
 216         RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
 217 }
 218
 219 static inline void
 220 rbe_remove_color(const struct rb_type *t, struct rbt_tree *rbt,
 221     struct rb_entry *parent, struct rb_entry *rbe)
 222 {
 223         struct rb_entry *tmp;
 224
 225         while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) &&
 226             rbe != RBH_ROOT(rbt) && parent) {
 227                 if (RBE_LEFT(parent) == rbe) {
 228                         tmp = RBE_RIGHT(parent);
 229                         if (RBE_COLOR(tmp) == RB_RED) {
 230                                 rbe_set_blackred(tmp, parent);
 231                                 rbe_rotate_left(t, rbt, parent);
 232                                 tmp = RBE_RIGHT(parent);
 233                         }
 234                         if ((RBE_LEFT(tmp) == NULL ||
 235                              RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
 236                             (RBE_RIGHT(tmp) == NULL ||
 237                              RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 238                                 RBE_COLOR(tmp) = RB_RED;
 239                                 rbe = parent;
 240                                 parent = RBE_PARENT(rbe);
 241                         } else {
 242                                 if (RBE_RIGHT(tmp) == NULL ||
 243                                     RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
 244                                         struct rb_entry *oleft;
 245
 246                                         oleft = RBE_LEFT(tmp);
 247                                         if (oleft != NULL)
 248                                                 RBE_COLOR(oleft) = RB_BLACK;
 249
 250                                         RBE_COLOR(tmp) = RB_RED;
 251                                         rbe_rotate_right(t, rbt, tmp);
 252                                         tmp = RBE_RIGHT(parent);
 253                                 }
 254
 255                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 256                                 RBE_COLOR(parent) = RB_BLACK;
 257                                 if (RBE_RIGHT(tmp))
 258                                         RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
 259
 260                                 rbe_rotate_left(t, rbt, parent);
 261                                 rbe = RBH_ROOT(rbt);
 262                                 break;
 263                         }
 264                 } else {
 265                         tmp = RBE_LEFT(parent);
 266                         if (RBE_COLOR(tmp) == RB_RED) {
 267                                 rbe_set_blackred(tmp, parent);
 268                                 rbe_rotate_right(t, rbt, parent);
 269                                 tmp = RBE_LEFT(parent);
 270                         }
 271
 272                         if ((RBE_LEFT(tmp) == NULL ||
 273                              RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
 274                             (RBE_RIGHT(tmp) == NULL ||
 275                              RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 276                                 RBE_COLOR(tmp) = RB_RED;
 277                                 rbe = parent;
 278                                 parent = RBE_PARENT(rbe);
 279                         } else {
 280                                 if (RBE_LEFT(tmp) == NULL ||
 281                                     RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
 282                                         struct rb_entry *oright;
 283
 284                                         oright = RBE_RIGHT(tmp);
 285                                         if (oright != NULL)
 286                                                 RBE_COLOR(oright) = RB_BLACK;
 287
 288                                         RBE_COLOR(tmp) = RB_RED;
 289                                         rbe_rotate_left(t, rbt, tmp);
 290                                         tmp = RBE_LEFT(parent);
 291                                 }
 292
 293                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 294                                 RBE_COLOR(parent) = RB_BLACK;
 295                                 if (RBE_LEFT(tmp) != NULL)
 296                                         RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
 297
 298                                 rbe_rotate_right(t, rbt, parent);
 299                                 rbe = RBH_ROOT(rbt);
 300                                 break;
 301                         }
 302                 }
 303         }
 304
 305         if (rbe != NULL)
 306                 RBE_COLOR(rbe) = RB_BLACK;
 307 }
 308
 309 static inline struct rb_entry *
 310 rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
 311 {
 312         struct rb_entry *child, *parent, *old = rbe;
 313         unsigned int color;
 314
 315         if (RBE_LEFT(rbe) == NULL)
 316                 child = RBE_RIGHT(rbe);
 317         else if (RBE_RIGHT(rbe) == NULL)
 318                 child = RBE_LEFT(rbe);
 319         else {
 320                 struct rb_entry *tmp;
 321
 322                 rbe = RBE_RIGHT(rbe);
 323                 while ((tmp = RBE_LEFT(rbe)) != NULL)
 324                         rbe = tmp;
 325
 326                 child = RBE_RIGHT(rbe);
 327                 parent = RBE_PARENT(rbe);
 328                 color = RBE_COLOR(rbe);
 329                 if (child != NULL)
 330                         RBE_PARENT(child) = parent;
 331                 if (parent != NULL) {
 332                         if (RBE_LEFT(parent) == rbe)
 333                                 RBE_LEFT(parent) = child;
 334                         else
 335                                 RBE_RIGHT(parent) = child;
 336
 337                         rbe_if_augment(t, parent);
 338                 } else
 339                         RBH_ROOT(rbt) = child;
 340                 if (RBE_PARENT(rbe) == old)
 341                         parent = rbe;
 342                 *rbe = *old;
 343
 344                 tmp = RBE_PARENT(old);
 345                 if (tmp != NULL) {
 346                         if (RBE_LEFT(tmp) == old)
 347                                 RBE_LEFT(tmp) = rbe;
 348                         else
 349                                 RBE_RIGHT(tmp) = rbe;
 350
 351                         rbe_if_augment(t, parent);
 352                 } else
 353                         RBH_ROOT(rbt) = rbe;
 354
 355                 RBE_PARENT(RBE_LEFT(old)) = rbe;
 356                 if (RBE_RIGHT(old))
 357                         RBE_PARENT(RBE_RIGHT(old)) = rbe;
 358
 359                 if (t->t_augment != NULL && parent != NULL) {
 360                         tmp = parent;
 361                         do {
 362                                 rbe_augment(t, tmp);
 363                                 tmp = RBE_PARENT(tmp);
 364                         } while (tmp != NULL);
 365                 }
 366
 367                 goto color;
 368         }
 369
 370         parent = RBE_PARENT(rbe);
 371         color = RBE_COLOR(rbe);
 372
 373         if (child != NULL)
 374                 RBE_PARENT(child) = parent;
 375         if (parent != NULL) {
 376                 if (RBE_LEFT(parent) == rbe)
 377                         RBE_LEFT(parent) = child;
 378                 else
 379                         RBE_RIGHT(parent) = child;
 380
 381                 rbe_if_augment(t, parent);
 382         } else
 383                 RBH_ROOT(rbt) = child;
 384 color:
 385         if (color == RB_BLACK)
 386                 rbe_remove_color(t, rbt, parent, child);
 387
 388         return (old);
 389 }
 390
 391 void *
 392 _rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
 393 {
 394         struct rb_entry *rbe = rb_n2e(t, elm);
 395         struct rb_entry *old;
 396
 397         old = rbe_remove(t, rbt, rbe);
 398
 399         return (old == NULL ? NULL : rb_e2n(t, old));
 400 }
 401
 402 void *
 403 _rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
 404 {
 405         struct rb_entry *rbe = rb_n2e(t, elm);
 406         struct rb_entry *tmp;
 407         struct rb_entry *parent = NULL;
 408         void *node;
 409         int comp = 0;
 410
 411         tmp = RBH_ROOT(rbt);
 412         while (tmp != NULL) {
 413                 parent = tmp;
 414
 415                 node = rb_e2n(t, tmp);
 416                 comp = (*t->t_compare)(elm, node);
 417                 if (comp < 0)
 418                         tmp = RBE_LEFT(tmp);
 419                 else if (comp > 0)
 420                         tmp = RBE_RIGHT(tmp);
 421                 else
 422                         return (node);
 423         }
 424
 425         rbe_set(rbe, parent);
 426
 427         if (parent != NULL) {
 428                 if (comp < 0)
 429                         RBE_LEFT(parent) = rbe;
 430                 else
 431                         RBE_RIGHT(parent) = rbe;
 432
 433                 rbe_if_augment(t, parent);
 434         } else
 435                 RBH_ROOT(rbt) = rbe;
 436
 437         rbe_insert_color(t, rbt, rbe);
 438
 439         return (NULL);
 440 }
 441
 442 /* Finds the node with the same key as elm */
 443 void *
 444 _rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key)
 445 {
 446         struct rb_entry *tmp = RBH_ROOT(rbt);
 447         void *node;
 448         int comp;
 449
 450         while (tmp != NULL) {
 451                 node = rb_e2n(t, tmp);
 452                 comp = (*t->t_compare)(key, node);
 453                 if (comp < 0)
 454                         tmp = RBE_LEFT(tmp);
 455                 else if (comp > 0)
 456                         tmp = RBE_RIGHT(tmp);
 457                 else
 458                         return (node);
 459         }
 460
 461         return (NULL);
 462 }
 463
 464 /* Finds the first node greater than or equal to the search key */
 465 void *
 466 _rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key)
 467 {
 468         struct rb_entry *tmp = RBH_ROOT(rbt);
 469         void *node;
 470         void *res = NULL;
 471         int comp;
 472
 473         while (tmp != NULL) {
 474                 node = rb_e2n(t, tmp);
 475                 comp = (*t->t_compare)(key, node);
 476                 if (comp < 0) {
 477                         res = node;
 478                         tmp = RBE_LEFT(tmp);
 479                 } else if (comp > 0)
 480                         tmp = RBE_RIGHT(tmp);
 481                 else
 482                         return (node);
 483         }
 484
 485         return (res);
 486 }
 487
 488 void *
 489 _rb_next(const struct rb_type *t, void *elm)
 490 {
 491         struct rb_entry *rbe = rb_n2e(t, elm);
 492
 493         if (RBE_RIGHT(rbe) != NULL) {
 494                 rbe = RBE_RIGHT(rbe);
 495                 while (RBE_LEFT(rbe) != NULL)
 496                         rbe = RBE_LEFT(rbe);
 497         } else {
 498                 if (RBE_PARENT(rbe) &&
 499                     (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 500                         rbe = RBE_PARENT(rbe);
 501                 else {
 502                         while (RBE_PARENT(rbe) &&
 503                             (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 504                                 rbe = RBE_PARENT(rbe);
 505                         rbe = RBE_PARENT(rbe);
 506                 }
 507         }
 508
 509         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 510 }
 511
 512 void *
 513 _rb_prev(const struct rb_type *t, void *elm)
 514 {
 515         struct rb_entry *rbe = rb_n2e(t, elm);
 516
 517         if (RBE_LEFT(rbe)) {
 518                 rbe = RBE_LEFT(rbe);
 519                 while (RBE_RIGHT(rbe))
 520                         rbe = RBE_RIGHT(rbe);
 521         } else {
 522                 if (RBE_PARENT(rbe) &&
 523                     (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 524                         rbe = RBE_PARENT(rbe);
 525                 else {
 526                         while (RBE_PARENT(rbe) &&
 527                             (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 528                                 rbe = RBE_PARENT(rbe);
 529                         rbe = RBE_PARENT(rbe);
 530                 }
 531         }
 532
 533         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 534 }
 535
 536 void *
 537 _rb_root(const struct rb_type *t, struct rbt_tree *rbt)
 538 {
 539         struct rb_entry *rbe = RBH_ROOT(rbt);
 540
 541         return (rbe == NULL ? rbe : rb_e2n(t, rbe));
 542 }
 543
 544 void *
 545 _rb_min(const struct rb_type *t, struct rbt_tree *rbt)
 546 {
 547         struct rb_entry *rbe = RBH_ROOT(rbt);
 548         struct rb_entry *parent = NULL;
 549
 550         while (rbe != NULL) {
 551                 parent = rbe;
 552                 rbe = RBE_LEFT(rbe);
 553         }
 554
 555         return (parent == NULL ? NULL : rb_e2n(t, parent));
 556 }
 557
 558 void *
 559 _rb_max(const struct rb_type *t, struct rbt_tree *rbt)
 560 {
 561         struct rb_entry *rbe = RBH_ROOT(rbt);
 562         struct rb_entry *parent = NULL;
 563
 564         while (rbe != NULL) {
 565                 parent = rbe;
 566                 rbe = RBE_RIGHT(rbe);
 567         }
 568
 569         return (parent == NULL ? NULL : rb_e2n(t, parent));
 570 }
 571
 572 void *
 573 _rb_left(const struct rb_type *t, void *node)
 574 {
 575         struct rb_entry *rbe = rb_n2e(t, node);
 576         rbe = RBE_LEFT(rbe);
 577         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 578 }
 579
 580 void *
 581 _rb_right(const struct rb_type *t, void *node)
 582 {
 583         struct rb_entry *rbe = rb_n2e(t, node);
 584         rbe = RBE_RIGHT(rbe);
 585         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 586 }
 587
 588 void *
 589 _rb_parent(const struct rb_type *t, void *node)
 590 {
 591         struct rb_entry *rbe = rb_n2e(t, node);
 592         rbe = RBE_PARENT(rbe);
 593         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 594 }
 595
 596 void
 597 _rb_set_left(const struct rb_type *t, void *node, void *left)
 598 {
 599         struct rb_entry *rbe = rb_n2e(t, node);
 600         struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
 601
 602         RBE_LEFT(rbe) = rbl;
 603 }
 604
 605 void
 606 _rb_set_right(const struct rb_type *t, void *node, void *right)
 607 {
 608         struct rb_entry *rbe = rb_n2e(t, node);
 609         struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
 610
 611         RBE_RIGHT(rbe) = rbr;
 612 }
 613
 614 void
 615 _rb_set_parent(const struct rb_type *t, void *node, void *parent)
 616 {
 617         struct rb_entry *rbe = rb_n2e(t, node);
 618         struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
 619
 620         RBE_PARENT(rbe) = rbp;
 621 }
 622
 623 void
 624 _rb_poison(const struct rb_type *t, void *node, unsigned long poison)
 625 {
 626         struct rb_entry *rbe = rb_n2e(t, node);
 627
 628         RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
 629             (struct rb_entry *)poison;
 630 }
 631
 632 int
 633 _rb_check(const struct rb_type *t, void *node, unsigned long poison)
 634 {
 635         struct rb_entry *rbe = rb_n2e(t, node);
 636
 637         return ((unsigned long)RBE_PARENT(rbe) == poison &&
 638             (unsigned long)RBE_LEFT(rbe) == poison &&
 639             (unsigned long)RBE_RIGHT(rbe) == poison);
 640 }