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 *rb_n2e(const struct rb_type *t, void *node)
  49 {
  50         unsigned long addr = (unsigned long)node;
  51
  52         return ((struct rb_entry *)(addr + t->t_offset));
  53 }
  54
  55 static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
  56 {
  57         unsigned long addr = (unsigned long)rbe;
  58
  59         return ((void *)(addr - t->t_offset));
  60 }
  61
  62 #define RBE_LEFT(_rbe)          (_rbe)->rbt_left
  63 #define RBE_RIGHT(_rbe)         (_rbe)->rbt_right
  64 #define RBE_PARENT(_rbe)        (_rbe)->rbt_parent
  65 #define RBE_COLOR(_rbe)         (_rbe)->rbt_color
  66
  67 #define RBH_ROOT(_rbt)          (_rbt)->rbt_root
  68
  69 static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
  70 {
  71         RBE_PARENT(rbe) = parent;
  72         RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
  73         RBE_COLOR(rbe) = RB_RED;
  74 }
  75
  76 static inline void rbe_set_blackred(struct rb_entry *black,
  77                                     struct rb_entry *red)
  78 {
  79         RBE_COLOR(black) = RB_BLACK;
  80         RBE_COLOR(red) = RB_RED;
  81 }
  82
  83 static inline void rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
  84 {
  85         (*t->t_augment)(rb_e2n(t, rbe));
  86 }
  87
  88 static inline void rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
  89 {
  90         if (t->t_augment != NULL)
  91                 rbe_augment(t, rbe);
  92 }
  93
  94 static inline void rbe_rotate_left(const struct rb_type *t,
  95                                    struct rbt_tree *rbt, struct rb_entry *rbe)
  96 {
  97         struct rb_entry *parent;
  98         struct rb_entry *tmp;
  99
 100         tmp = RBE_RIGHT(rbe);
 101         RBE_RIGHT(rbe) = RBE_LEFT(tmp);
 102         if (RBE_RIGHT(rbe) != NULL)
 103                 RBE_PARENT(RBE_LEFT(tmp)) = rbe;
 104
 105         parent = RBE_PARENT(rbe);
 106         RBE_PARENT(tmp) = parent;
 107         if (parent != NULL) {
 108                 if (rbe == RBE_LEFT(parent))
 109                         RBE_LEFT(parent) = tmp;
 110                 else
 111                         RBE_RIGHT(parent) = tmp;
 112         } else
 113                 RBH_ROOT(rbt) = tmp;
 114
 115         RBE_LEFT(tmp) = rbe;
 116         RBE_PARENT(rbe) = tmp;
 117
 118         if (t->t_augment != NULL) {
 119                 rbe_augment(t, rbe);
 120                 rbe_augment(t, tmp);
 121                 parent = RBE_PARENT(tmp);
 122                 if (parent != NULL)
 123                         rbe_augment(t, parent);
 124         }
 125 }
 126
 127 static inline void rbe_rotate_right(const struct rb_type *t,
 128                                     struct rbt_tree *rbt, struct rb_entry *rbe)
 129 {
 130         struct rb_entry *parent;
 131         struct rb_entry *tmp;
 132
 133         tmp = RBE_LEFT(rbe);
 134         RBE_LEFT(rbe) = RBE_RIGHT(tmp);
 135         if (RBE_LEFT(rbe) != NULL)
 136                 RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
 137
 138         parent = RBE_PARENT(rbe);
 139         RBE_PARENT(tmp) = parent;
 140         if (parent != NULL) {
 141                 if (rbe == RBE_LEFT(parent))
 142                         RBE_LEFT(parent) = tmp;
 143                 else
 144                         RBE_RIGHT(parent) = tmp;
 145         } else
 146                 RBH_ROOT(rbt) = tmp;
 147
 148         RBE_RIGHT(tmp) = rbe;
 149         RBE_PARENT(rbe) = tmp;
 150
 151         if (t->t_augment != NULL) {
 152                 rbe_augment(t, rbe);
 153                 rbe_augment(t, tmp);
 154                 parent = RBE_PARENT(tmp);
 155                 if (parent != NULL)
 156                         rbe_augment(t, parent);
 157         }
 158 }
 159
 160 static inline void rbe_insert_color(const struct rb_type *t,
 161                                     struct rbt_tree *rbt, struct rb_entry *rbe)
 162 {
 163         struct rb_entry *parent, *gparent, *tmp;
 164
 165         while ((parent = RBE_PARENT(rbe)) != NULL
 166                && RBE_COLOR(parent) == RB_RED) {
 167                 gparent = RBE_PARENT(parent);
 168
 169                 if (parent == RBE_LEFT(gparent)) {
 170                         tmp = RBE_RIGHT(gparent);
 171                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 172                                 RBE_COLOR(tmp) = RB_BLACK;
 173                                 rbe_set_blackred(parent, gparent);
 174                                 rbe = gparent;
 175                                 continue;
 176                         }
 177
 178                         if (RBE_RIGHT(parent) == rbe) {
 179                                 rbe_rotate_left(t, rbt, parent);
 180                                 tmp = parent;
 181                                 parent = rbe;
 182                                 rbe = tmp;
 183                         }
 184
 185                         rbe_set_blackred(parent, gparent);
 186                         rbe_rotate_right(t, rbt, gparent);
 187                 } else {
 188                         tmp = RBE_LEFT(gparent);
 189                         if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
 190                                 RBE_COLOR(tmp) = RB_BLACK;
 191                                 rbe_set_blackred(parent, gparent);
 192                                 rbe = gparent;
 193                                 continue;
 194                         }
 195
 196                         if (RBE_LEFT(parent) == rbe) {
 197                                 rbe_rotate_right(t, rbt, parent);
 198                                 tmp = parent;
 199                                 parent = rbe;
 200                                 rbe = tmp;
 201                         }
 202
 203                         rbe_set_blackred(parent, gparent);
 204                         rbe_rotate_left(t, rbt, gparent);
 205                 }
 206         }
 207
 208         RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
 209 }
 210
 211 static inline void rbe_remove_color(const struct rb_type *t,
 212                                     struct rbt_tree *rbt,
 213                                     struct rb_entry *parent,
 214                                     struct rb_entry *rbe)
 215 {
 216         struct rb_entry *tmp;
 217
 218         /* Silence clang possible NULL deference warning. */
 219         if (parent == NULL)
 220                 return;
 221
 222         while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
 223                && rbe != RBH_ROOT(rbt)) {
 224                 if (RBE_LEFT(parent) == rbe) {
 225                         tmp = RBE_RIGHT(parent);
 226                         if (RBE_COLOR(tmp) == RB_RED) {
 227                                 rbe_set_blackred(tmp, parent);
 228                                 rbe_rotate_left(t, rbt, parent);
 229                                 tmp = RBE_RIGHT(parent);
 230                         }
 231                         if ((RBE_LEFT(tmp) == NULL
 232                              || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
 233                             && (RBE_RIGHT(tmp) == NULL
 234                                 || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 235                                 RBE_COLOR(tmp) = RB_RED;
 236                                 rbe = parent;
 237                                 parent = RBE_PARENT(rbe);
 238                         } else {
 239                                 if (RBE_RIGHT(tmp) == NULL
 240                                     || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
 241                                         struct rb_entry *oleft;
 242
 243                                         oleft = RBE_LEFT(tmp);
 244                                         if (oleft != NULL)
 245                                                 RBE_COLOR(oleft) = RB_BLACK;
 246
 247                                         RBE_COLOR(tmp) = RB_RED;
 248                                         rbe_rotate_right(t, rbt, tmp);
 249                                         tmp = RBE_RIGHT(parent);
 250                                 }
 251
 252                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 253                                 RBE_COLOR(parent) = RB_BLACK;
 254                                 if (RBE_RIGHT(tmp))
 255                                         RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
 256
 257                                 rbe_rotate_left(t, rbt, parent);
 258                                 rbe = RBH_ROOT(rbt);
 259                                 break;
 260                         }
 261                 } else {
 262                         tmp = RBE_LEFT(parent);
 263                         if (RBE_COLOR(tmp) == RB_RED) {
 264                                 rbe_set_blackred(tmp, parent);
 265                                 rbe_rotate_right(t, rbt, parent);
 266                                 tmp = RBE_LEFT(parent);
 267                         }
 268
 269                         if ((RBE_LEFT(tmp) == NULL
 270                              || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
 271                             && (RBE_RIGHT(tmp) == NULL
 272                                 || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
 273                                 RBE_COLOR(tmp) = RB_RED;
 274                                 rbe = parent;
 275                                 parent = RBE_PARENT(rbe);
 276                         } else {
 277                                 if (RBE_LEFT(tmp) == NULL
 278                                     || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
 279                                         struct rb_entry *oright;
 280
 281                                         oright = RBE_RIGHT(tmp);
 282                                         if (oright != NULL)
 283                                                 RBE_COLOR(oright) = RB_BLACK;
 284
 285                                         RBE_COLOR(tmp) = RB_RED;
 286                                         rbe_rotate_left(t, rbt, tmp);
 287                                         tmp = RBE_LEFT(parent);
 288                                 }
 289
 290                                 RBE_COLOR(tmp) = RBE_COLOR(parent);
 291                                 RBE_COLOR(parent) = RB_BLACK;
 292                                 if (RBE_LEFT(tmp) != NULL)
 293                                         RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
 294
 295                                 rbe_rotate_right(t, rbt, parent);
 296                                 rbe = RBH_ROOT(rbt);
 297                                 break;
 298                         }
 299                 }
 300         }
 301
 302         if (rbe != NULL)
 303                 RBE_COLOR(rbe) = RB_BLACK;
 304 }
 305
 306 static inline struct rb_entry *
 307 rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
 308 {
 309         struct rb_entry *child, *parent, *old = rbe;
 310         unsigned int color;
 311
 312         if (RBE_LEFT(rbe) == NULL)
 313                 child = RBE_RIGHT(rbe);
 314         else if (RBE_RIGHT(rbe) == NULL)
 315                 child = RBE_LEFT(rbe);
 316         else {
 317                 struct rb_entry *tmp;
 318
 319                 rbe = RBE_RIGHT(rbe);
 320                 while ((tmp = RBE_LEFT(rbe)) != NULL)
 321                         rbe = tmp;
 322
 323                 child = RBE_RIGHT(rbe);
 324                 parent = RBE_PARENT(rbe);
 325                 color = RBE_COLOR(rbe);
 326                 if (child != NULL)
 327                         RBE_PARENT(child) = parent;
 328                 if (parent != NULL) {
 329                         if (RBE_LEFT(parent) == rbe)
 330                                 RBE_LEFT(parent) = child;
 331                         else
 332                                 RBE_RIGHT(parent) = child;
 333
 334                         rbe_if_augment(t, parent);
 335                 } else
 336                         RBH_ROOT(rbt) = child;
 337                 if (RBE_PARENT(rbe) == old)
 338                         parent = rbe;
 339                 *rbe = *old;
 340
 341                 tmp = RBE_PARENT(old);
 342                 if (tmp != NULL) {
 343                         if (RBE_LEFT(tmp) == old)
 344                                 RBE_LEFT(tmp) = rbe;
 345                         else
 346                                 RBE_RIGHT(tmp) = rbe;
 347
 348                         rbe_if_augment(t, parent);
 349                 } else
 350                         RBH_ROOT(rbt) = rbe;
 351
 352                 RBE_PARENT(RBE_LEFT(old)) = rbe;
 353                 if (RBE_RIGHT(old))
 354                         RBE_PARENT(RBE_RIGHT(old)) = rbe;
 355
 356                 if (t->t_augment != NULL && parent != NULL) {
 357                         tmp = parent;
 358                         do {
 359                                 rbe_augment(t, tmp);
 360                                 tmp = RBE_PARENT(tmp);
 361                         } while (tmp != NULL);
 362                 }
 363
 364                 goto color;
 365         }
 366
 367         parent = RBE_PARENT(rbe);
 368         color = RBE_COLOR(rbe);
 369
 370         if (child != NULL)
 371                 RBE_PARENT(child) = parent;
 372         if (parent != NULL) {
 373                 if (RBE_LEFT(parent) == rbe)
 374                         RBE_LEFT(parent) = child;
 375                 else
 376                         RBE_RIGHT(parent) = child;
 377
 378                 rbe_if_augment(t, parent);
 379         } else
 380                 RBH_ROOT(rbt) = child;
 381 color:
 382         if (color == RB_BLACK)
 383                 rbe_remove_color(t, rbt, parent, child);
 384
 385         return (old);
 386 }
 387
 388 void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
 389 {
 390         struct rb_entry *rbe = rb_n2e(t, elm);
 391         struct rb_entry *old;
 392
 393         old = rbe_remove(t, rbt, rbe);
 394
 395         return (old == NULL ? NULL : rb_e2n(t, old));
 396 }
 397
 398 void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
 399 {
 400         struct rb_entry *rbe = rb_n2e(t, elm);
 401         struct rb_entry *tmp;
 402         struct rb_entry *parent = NULL;
 403         void *node;
 404         int comp = 0;
 405
 406         tmp = RBH_ROOT(rbt);
 407         while (tmp != NULL) {
 408                 parent = tmp;
 409
 410                 node = rb_e2n(t, tmp);
 411                 comp = (*t->t_compare)(elm, node);
 412                 if (comp < 0)
 413                         tmp = RBE_LEFT(tmp);
 414                 else if (comp > 0)
 415                         tmp = RBE_RIGHT(tmp);
 416                 else
 417                         return (node);
 418         }
 419
 420         rbe_set(rbe, parent);
 421
 422         if (parent != NULL) {
 423                 if (comp < 0)
 424                         RBE_LEFT(parent) = rbe;
 425                 else
 426                         RBE_RIGHT(parent) = rbe;
 427
 428                 rbe_if_augment(t, parent);
 429         } else
 430                 RBH_ROOT(rbt) = rbe;
 431
 432         rbe_insert_color(t, rbt, rbe);
 433
 434         return (NULL);
 435 }
 436
 437 /* Finds the node with the same key as elm */
 438 void *_rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key)
 439 {
 440         struct rb_entry *tmp = RBH_ROOT(rbt);
 441         void *node;
 442         int comp;
 443
 444         while (tmp != NULL) {
 445                 node = rb_e2n(t, tmp);
 446                 comp = (*t->t_compare)(key, node);
 447                 if (comp < 0)
 448                         tmp = RBE_LEFT(tmp);
 449                 else if (comp > 0)
 450                         tmp = RBE_RIGHT(tmp);
 451                 else
 452                         return (node);
 453         }
 454
 455         return (NULL);
 456 }
 457
 458 /* Finds the first node greater than or equal to the search key */
 459 void *_rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key)
 460 {
 461         struct rb_entry *tmp = RBH_ROOT(rbt);
 462         void *node;
 463         void *res = NULL;
 464         int comp;
 465
 466         while (tmp != NULL) {
 467                 node = rb_e2n(t, tmp);
 468                 comp = (*t->t_compare)(key, node);
 469                 if (comp < 0) {
 470                         res = node;
 471                         tmp = RBE_LEFT(tmp);
 472                 } else if (comp > 0)
 473                         tmp = RBE_RIGHT(tmp);
 474                 else
 475                         return (node);
 476         }
 477
 478         return (res);
 479 }
 480
 481 void *_rb_next(const struct rb_type *t, void *elm)
 482 {
 483         struct rb_entry *rbe = rb_n2e(t, elm);
 484
 485         if (RBE_RIGHT(rbe) != NULL) {
 486                 rbe = RBE_RIGHT(rbe);
 487                 while (RBE_LEFT(rbe) != NULL)
 488                         rbe = RBE_LEFT(rbe);
 489         } else {
 490                 if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 491                         rbe = RBE_PARENT(rbe);
 492                 else {
 493                         while (RBE_PARENT(rbe)
 494                                && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 495                                 rbe = RBE_PARENT(rbe);
 496                         rbe = RBE_PARENT(rbe);
 497                 }
 498         }
 499
 500         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 501 }
 502
 503 void *_rb_prev(const struct rb_type *t, void *elm)
 504 {
 505         struct rb_entry *rbe = rb_n2e(t, elm);
 506
 507         if (RBE_LEFT(rbe)) {
 508                 rbe = RBE_LEFT(rbe);
 509                 while (RBE_RIGHT(rbe))
 510                         rbe = RBE_RIGHT(rbe);
 511         } else {
 512                 if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
 513                         rbe = RBE_PARENT(rbe);
 514                 else {
 515                         while (RBE_PARENT(rbe)
 516                                && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
 517                                 rbe = RBE_PARENT(rbe);
 518                         rbe = RBE_PARENT(rbe);
 519                 }
 520         }
 521
 522         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 523 }
 524
 525 void *_rb_root(const struct rb_type *t, struct rbt_tree *rbt)
 526 {
 527         struct rb_entry *rbe = RBH_ROOT(rbt);
 528
 529         return (rbe == NULL ? rbe : rb_e2n(t, rbe));
 530 }
 531
 532 void *_rb_min(const struct rb_type *t, struct rbt_tree *rbt)
 533 {
 534         struct rb_entry *rbe = RBH_ROOT(rbt);
 535         struct rb_entry *parent = NULL;
 536
 537         while (rbe != NULL) {
 538                 parent = rbe;
 539                 rbe = RBE_LEFT(rbe);
 540         }
 541
 542         return (parent == NULL ? NULL : rb_e2n(t, parent));
 543 }
 544
 545 void *_rb_max(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_RIGHT(rbe);
 553         }
 554
 555         return (parent == NULL ? NULL : rb_e2n(t, parent));
 556 }
 557
 558 void *_rb_left(const struct rb_type *t, void *node)
 559 {
 560         struct rb_entry *rbe = rb_n2e(t, node);
 561         rbe = RBE_LEFT(rbe);
 562         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 563 }
 564
 565 void *_rb_right(const struct rb_type *t, void *node)
 566 {
 567         struct rb_entry *rbe = rb_n2e(t, node);
 568         rbe = RBE_RIGHT(rbe);
 569         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 570 }
 571
 572 void *_rb_parent(const struct rb_type *t, void *node)
 573 {
 574         struct rb_entry *rbe = rb_n2e(t, node);
 575         rbe = RBE_PARENT(rbe);
 576         return (rbe == NULL ? NULL : rb_e2n(t, rbe));
 577 }
 578
 579 void _rb_set_left(const struct rb_type *t, void *node, void *left)
 580 {
 581         struct rb_entry *rbe = rb_n2e(t, node);
 582         struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
 583
 584         RBE_LEFT(rbe) = rbl;
 585 }
 586
 587 void _rb_set_right(const struct rb_type *t, void *node, void *right)
 588 {
 589         struct rb_entry *rbe = rb_n2e(t, node);
 590         struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
 591
 592         RBE_RIGHT(rbe) = rbr;
 593 }
 594
 595 void _rb_set_parent(const struct rb_type *t, void *node, void *parent)
 596 {
 597         struct rb_entry *rbe = rb_n2e(t, node);
 598         struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
 599
 600         RBE_PARENT(rbe) = rbp;
 601 }
 602
 603 void _rb_poison(const struct rb_type *t, void *node, unsigned long poison)
 604 {
 605         struct rb_entry *rbe = rb_n2e(t, node);
 606
 607         RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
 608                 (struct rb_entry *)poison;
 609 }
 610
 611 int _rb_check(const struct rb_type *t, void *node, unsigned long poison)
 612 {
 613         struct rb_entry *rbe = rb_n2e(t, node);
 614
 615         return ((unsigned long)RBE_PARENT(rbe) == poison
 616                 && (unsigned long)RBE_LEFT(rbe) == poison
 617                 && (unsigned long)RBE_RIGHT(rbe) == poison);
 618 }