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