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         /* Silence clang possible NULL deference warning. */
 226         if (parent == NULL)
 227                 return;
 228
 229         while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) &&
 230             rbe != RBH_ROOT(rbt)) {
 231                 if (RBE_LEFT(parent) == rbe) {
 232                         tmp = RBE_RIGHT(parent);
 233                         if (RBE_COLOR(tmp) == RB_RED) {
 234                                 rbe_set_blackred(tmp, parent);
 235                                 rbe_rotate_left(t, rbt, parent);
 236                                 tmp = RBE_RIGHT(parent);
 237                         }
 238                         if ((RBE_LEFT(tmp) == NULL ||
 239                              RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
 240                             (RBE_RIGHT(tmp) == NULL ||
 241                              RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 242                                 RBE_COLOR(tmp) = RB_RED;
 243                                 rbe = parent;
 244                                 parent = RBE_PARENT(rbe);
 245                         } else {
 246                                 if (RBE_RIGHT(tmp) == NULL ||
 247                                     RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
 248                                         struct rb_entry *oleft;
 249
 250                                         oleft = RBE_LEFT(tmp);
 251                                         if (oleft != NULL)
 252                                                 RBE_COLOR(oleft) = RB_BLACK;
 253
 254                                         RBE_COLOR(tmp) = RB_RED;
 255                                         rbe_rotate_right(t, rbt, tmp);
 256                                         tmp = RBE_RIGHT(parent);
 257                                 }
 258
 259                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 260                                 RBE_COLOR(parent) = RB_BLACK;
 261                                 if (RBE_RIGHT(tmp))
 262                                         RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
 263
 264                                 rbe_rotate_left(t, rbt, parent);
 265                                 rbe = RBH_ROOT(rbt);
 266                                 break;
 267                         }
 268                 } else {
 269                         tmp = RBE_LEFT(parent);
 270                         if (RBE_COLOR(tmp) == RB_RED) {
 271                                 rbe_set_blackred(tmp, parent);
 272                                 rbe_rotate_right(t, rbt, parent);
 273                                 tmp = RBE_LEFT(parent);
 274                         }
 275
 276                         if ((RBE_LEFT(tmp) == NULL ||
 277                              RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
 278                             (RBE_RIGHT(tmp) == NULL ||
 279                              RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 280                                 RBE_COLOR(tmp) = RB_RED;
 281                                 rbe = parent;
 282                                 parent = RBE_PARENT(rbe);
 283                         } else {
 284                                 if (RBE_LEFT(tmp) == NULL ||
 285                                     RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
 286                                         struct rb_entry *oright;
 287
 288                                         oright = RBE_RIGHT(tmp);
 289                                         if (oright != NULL)
 290                                                 RBE_COLOR(oright) = RB_BLACK;
 291
 292                                         RBE_COLOR(tmp) = RB_RED;
 293                                         rbe_rotate_left(t, rbt, tmp);
 294                                         tmp = RBE_LEFT(parent);
 295                                 }
 296
 297                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 298                                 RBE_COLOR(parent) = RB_BLACK;
 299                                 if (RBE_LEFT(tmp) != NULL)
 300                                         RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
 301
 302                                 rbe_rotate_right(t, rbt, parent);
 303                                 rbe = RBH_ROOT(rbt);
 304                                 break;
 305                         }
 306                 }
 307         }
 308
 309         if (rbe != NULL)
 310                 RBE_COLOR(rbe) = RB_BLACK;
 311 }
 312
 313 static inline struct rb_entry *
 314 rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
 315 {
 316         struct rb_entry *child, *parent, *old = rbe;
 317         unsigned int color;
 318
 319         if (RBE_LEFT(rbe) == NULL)
 320                 child = RBE_RIGHT(rbe);
 321         else if (RBE_RIGHT(rbe) == NULL)
 322                 child = RBE_LEFT(rbe);
 323         else {
 324                 struct rb_entry *tmp;
 325
 326                 rbe = RBE_RIGHT(rbe);
 327                 while ((tmp = RBE_LEFT(rbe)) != NULL)
 328                         rbe = tmp;
 329
 330                 child = RBE_RIGHT(rbe);
 331                 parent = RBE_PARENT(rbe);
 332                 color = RBE_COLOR(rbe);
 333                 if (child != NULL)
 334                         RBE_PARENT(child) = parent;
 335                 if (parent != NULL) {
 336                         if (RBE_LEFT(parent) == rbe)
 337                                 RBE_LEFT(parent) = child;
 338                         else
 339                                 RBE_RIGHT(parent) = child;
 340
 341                         rbe_if_augment(t, parent);
 342                 } else
 343                         RBH_ROOT(rbt) = child;
 344                 if (RBE_PARENT(rbe) == old)
 345                         parent = rbe;
 346                 *rbe = *old;
 347
 348                 tmp = RBE_PARENT(old);
 349                 if (tmp != NULL) {
 350                         if (RBE_LEFT(tmp) == old)
 351                                 RBE_LEFT(tmp) = rbe;
 352                         else
 353                                 RBE_RIGHT(tmp) = rbe;
 354
 355                         rbe_if_augment(t, parent);
 356                 } else
 357                         RBH_ROOT(rbt) = rbe;
 358
 359                 RBE_PARENT(RBE_LEFT(old)) = rbe;
 360                 if (RBE_RIGHT(old))
 361                         RBE_PARENT(RBE_RIGHT(old)) = rbe;
 362
 363                 if (t->t_augment != NULL && parent != NULL) {
 364                         tmp = parent;
 365                         do {
 366                                 rbe_augment(t, tmp);
 367                                 tmp = RBE_PARENT(tmp);
 368                         } while (tmp != NULL);
 369                 }
 370
 371                 goto color;
 372         }
 373
 374         parent = RBE_PARENT(rbe);
 375         color = RBE_COLOR(rbe);
 376
 377         if (child != NULL)
 378                 RBE_PARENT(child) = parent;
 379         if (parent != NULL) {
 380                 if (RBE_LEFT(parent) == rbe)
 381                         RBE_LEFT(parent) = child;
 382                 else
 383                         RBE_RIGHT(parent) = child;
 384
 385                 rbe_if_augment(t, parent);
 386         } else
 387                 RBH_ROOT(rbt) = child;
 388 color:
 389         if (color == RB_BLACK)
 390                 rbe_remove_color(t, rbt, parent, child);
 391
 392         return (old);
 393 }
 394
 395 void *
 396 _rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
 397 {
 398         struct rb_entry *rbe = rb_n2e(t, elm);
 399         struct rb_entry *old;
 400
 401         old = rbe_remove(t, rbt, rbe);
 402
 403         return (old == NULL ? NULL : rb_e2n(t, old));
 404 }
 405
 406 void *
 407 _rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
 408 {
 409         struct rb_entry *rbe = rb_n2e(t, elm);
 410         struct rb_entry *tmp;
 411         struct rb_entry *parent = NULL;
 412         void *node;
 413         int comp = 0;
 414
 415         tmp = RBH_ROOT(rbt);
 416         while (tmp != NULL) {
 417                 parent = tmp;
 418
 419                 node = rb_e2n(t, tmp);
 420                 comp = (*t->t_compare)(elm, node);
 421                 if (comp < 0)
 422                         tmp = RBE_LEFT(tmp);
 423                 else if (comp > 0)
 424                         tmp = RBE_RIGHT(tmp);
 425                 else
 426                         return (node);
 427         }
 428
 429         rbe_set(rbe, parent);
 430
 431         if (parent != NULL) {
 432                 if (comp < 0)
 433                         RBE_LEFT(parent) = rbe;
 434                 else
 435                         RBE_RIGHT(parent) = rbe;
 436
 437                 rbe_if_augment(t, parent);
 438         } else
 439                 RBH_ROOT(rbt) = rbe;
 440
 441         rbe_insert_color(t, rbt, rbe);
 442
 443         return (NULL);
 444 }
 445
 446 /* Finds the node with the same key as elm */
 447 void *
 448 _rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key)
 449 {
 450         struct rb_entry *tmp = RBH_ROOT(rbt);
 451         void *node;
 452         int comp;
 453
 454         while (tmp != NULL) {
 455                 node = rb_e2n(t, tmp);
 456                 comp = (*t->t_compare)(key, node);
 457                 if (comp < 0)
 458                         tmp = RBE_LEFT(tmp);
 459                 else if (comp > 0)
 460                         tmp = RBE_RIGHT(tmp);
 461                 else
 462                         return (node);
 463         }
 464
 465         return (NULL);
 466 }
 467
 468 /* Finds the first node greater than or equal to the search key */
 469 void *
 470 _rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key)
 471 {
 472         struct rb_entry *tmp = RBH_ROOT(rbt);
 473         void *node;
 474         void *res = NULL;
 475         int comp;
 476
 477         while (tmp != NULL) {
 478                 node = rb_e2n(t, tmp);
 479                 comp = (*t->t_compare)(key, node);
 480                 if (comp < 0) {
 481                         res = node;
 482                         tmp = RBE_LEFT(tmp);
 483                 } else if (comp > 0)
 484                         tmp = RBE_RIGHT(tmp);
 485                 else
 486                         return (node);
 487         }
 488
 489         return (res);
 490 }
 491
 492 void *
 493 _rb_next(const struct rb_type *t, void *elm)
 494 {
 495         struct rb_entry *rbe = rb_n2e(t, elm);
 496
 497         if (RBE_RIGHT(rbe) != NULL) {
 498                 rbe = RBE_RIGHT(rbe);
 499                 while (RBE_LEFT(rbe) != NULL)
 500                         rbe = RBE_LEFT(rbe);
 501         } else {
 502                 if (RBE_PARENT(rbe) &&
 503                     (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 504                         rbe = RBE_PARENT(rbe);
 505                 else {
 506                         while (RBE_PARENT(rbe) &&
 507                             (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 508                                 rbe = RBE_PARENT(rbe);
 509                         rbe = RBE_PARENT(rbe);
 510                 }
 511         }
 512
 513         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 514 }
 515
 516 void *
 517 _rb_prev(const struct rb_type *t, void *elm)
 518 {
 519         struct rb_entry *rbe = rb_n2e(t, elm);
 520
 521         if (RBE_LEFT(rbe)) {
 522                 rbe = RBE_LEFT(rbe);
 523                 while (RBE_RIGHT(rbe))
 524                         rbe = RBE_RIGHT(rbe);
 525         } else {
 526                 if (RBE_PARENT(rbe) &&
 527                     (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 528                         rbe = RBE_PARENT(rbe);
 529                 else {
 530                         while (RBE_PARENT(rbe) &&
 531                             (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 532                                 rbe = RBE_PARENT(rbe);
 533                         rbe = RBE_PARENT(rbe);
 534                 }
 535         }
 536
 537         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 538 }
 539
 540 void *
 541 _rb_root(const struct rb_type *t, struct rbt_tree *rbt)
 542 {
 543         struct rb_entry *rbe = RBH_ROOT(rbt);
 544
 545         return (rbe == NULL ? rbe : rb_e2n(t, rbe));
 546 }
 547
 548 void *
 549 _rb_min(const struct rb_type *t, struct rbt_tree *rbt)
 550 {
 551         struct rb_entry *rbe = RBH_ROOT(rbt);
 552         struct rb_entry *parent = NULL;
 553
 554         while (rbe != NULL) {
 555                 parent = rbe;
 556                 rbe = RBE_LEFT(rbe);
 557         }
 558
 559         return (parent == NULL ? NULL : rb_e2n(t, parent));
 560 }
 561
 562 void *
 563 _rb_max(const struct rb_type *t, struct rbt_tree *rbt)
 564 {
 565         struct rb_entry *rbe = RBH_ROOT(rbt);
 566         struct rb_entry *parent = NULL;
 567
 568         while (rbe != NULL) {
 569                 parent = rbe;
 570                 rbe = RBE_RIGHT(rbe);
 571         }
 572
 573         return (parent == NULL ? NULL : rb_e2n(t, parent));
 574 }
 575
 576 void *
 577 _rb_left(const struct rb_type *t, void *node)
 578 {
 579         struct rb_entry *rbe = rb_n2e(t, node);
 580         rbe = RBE_LEFT(rbe);
 581         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 582 }
 583
 584 void *
 585 _rb_right(const struct rb_type *t, void *node)
 586 {
 587         struct rb_entry *rbe = rb_n2e(t, node);
 588         rbe = RBE_RIGHT(rbe);
 589         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 590 }
 591
 592 void *
 593 _rb_parent(const struct rb_type *t, void *node)
 594 {
 595         struct rb_entry *rbe = rb_n2e(t, node);
 596         rbe = RBE_PARENT(rbe);
 597         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 598 }
 599
 600 void
 601 _rb_set_left(const struct rb_type *t, void *node, void *left)
 602 {
 603         struct rb_entry *rbe = rb_n2e(t, node);
 604         struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
 605
 606         RBE_LEFT(rbe) = rbl;
 607 }
 608
 609 void
 610 _rb_set_right(const struct rb_type *t, void *node, void *right)
 611 {
 612         struct rb_entry *rbe = rb_n2e(t, node);
 613         struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
 614
 615         RBE_RIGHT(rbe) = rbr;
 616 }
 617
 618 void
 619 _rb_set_parent(const struct rb_type *t, void *node, void *parent)
 620 {
 621         struct rb_entry *rbe = rb_n2e(t, node);
 622         struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
 623
 624         RBE_PARENT(rbe) = rbp;
 625 }
 626
 627 void
 628 _rb_poison(const struct rb_type *t, void *node, unsigned long poison)
 629 {
 630         struct rb_entry *rbe = rb_n2e(t, node);
 631
 632         RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
 633             (struct rb_entry *)poison;
 634 }
 635
 636 int
 637 _rb_check(const struct rb_type *t, void *node, unsigned long poison)
 638 {
 639         struct rb_entry *rbe = rb_n2e(t, node);
 640
 641         return ((unsigned long)RBE_PARENT(rbe) == poison &&
 642             (unsigned long)RBE_LEFT(rbe) == poison &&
 643             (unsigned long)RBE_RIGHT(rbe) == poison);
 644 }