src/opr/rbtree.c

   1 /*
   2  * Copyright (c) 2008 - 2010 Jason Evans <jasone@FreeBSD.org>
   3  * Copyright (c) 2011 Your File System Inc.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 /* Left-leaning rbtree implementation. Originally derived from the FreeBSD
  28  * CPP macro definitions by Jason Evans, but extensively modified to
  29  *     *) Be function, rather than macro based
  30  *     *) Use parent pointers, rather than calling an embeded comparison fn
  31  *     *) Use 'NULL' to represent empty nodes, rather than a magic pointer
  32  */
  33
  34 #include <afsconfig.h>
  35 #include <afs/param.h>
  36
  37 #ifdef KERNEL
  38 # include "afs/sysincludes.h"
  39 # include "afsincludes.h"
  40 #else
  41 # include <roken.h>
  42 #endif
  43 #include <afs/opr.h>
  44
  45 #include "rbtree.h"
  46
  47 struct {
  48     struct opr_rbtree_node *left;
  49     struct opr_rbtree_node *right;
  50     struct opr_rbtree_node *parent;
  51     int red;
  52 } opr_rbtree_node;
  53
  54 struct {
  55     struct opr_rbtree_node *root;
  56 } opr_rbtree;
  57
  58 /* Update the parent pointers for a node which is being replaced.
  59  *
  60  * If the original node had no parent, then it was the root of the tree,
  61  * and the replacement is too.
  62  * Otherwise, the original node must have been either the left or right
  63  * child of its parent, so update the left (or right) pointer to point
  64  * to the replacement as appropriate.
  65  */
  66
  67 static_inline void
  68 update_parent_ptr(struct opr_rbtree *head, struct opr_rbtree_node *old,
  69                   struct opr_rbtree_node *replacement)
  70 {
  71     if (old->parent) {
  72         if (old->parent->left == old)
  73             old->parent->left = replacement;
  74         else
  75             old->parent->right = replacement;
  76     } else
  77         head->root = replacement;
  78 }
  79
  80 void
  81 opr_rbtree_init(struct opr_rbtree *head)
  82 {
  83     head->root = NULL;
  84 }
  85
  86 struct opr_rbtree_node *
  87 opr_rbtree_first(struct opr_rbtree *head)
  88 {
  89     struct opr_rbtree_node *node;
  90
  91     node = head->root;
  92     if (node == NULL)
  93         return node;
  94
  95     while (node->left != NULL)
  96         node = node->left;
  97
  98     return node;
  99 }
 100
 101 struct opr_rbtree_node *
 102 opr_rbtree_last(struct opr_rbtree *head)
 103 {
 104     struct opr_rbtree_node *node;
 105
 106     node = head->root;
 107
 108     if (node == NULL)
 109         return node;
 110
 111     while (node->right != NULL)
 112         node = node->right;
 113
 114     return node;
 115 }
 116
 117
 118 struct opr_rbtree_node *
 119 opr_rbtree_next(struct opr_rbtree_node *node)
 120 {
 121     struct opr_rbtree_node *parent;
 122
 123     /* Where there is a right child, the next node is to the right, then
 124      * left as far as we can go */
 125     if (node->right != NULL) {
 126         node = node->right;
 127         while (node->left != NULL)
 128              node = node->left;
 129
 130         return node;
 131     }
 132
 133     /* If there is no right hand child, then the next node is above us.
 134      * Whenever our ancestor is a right-hand child, the next node is
 135      * further up. When it is a left-hand child, it is our next node
 136      */
 137     while ((parent = node->parent) != NULL && node == parent->right)
 138         node = parent;
 139
 140     return parent;
 141 }
 142
 143 struct opr_rbtree_node *
 144 opr_rbtree_prev(struct opr_rbtree_node *node)
 145 {
 146     struct opr_rbtree_node *parent;
 147
 148     if (node->left != NULL) {
 149         node = node->left;
 150         while (node->right != NULL)
 151             node = node->right;
 152
 153         return node;
 154     }
 155
 156     /* Same ancestor logic as for 'next', but in reverse */
 157     while ((parent = node->parent) != NULL && node == parent->left)
 158         node = parent;
 159
 160     return parent;
 161 }
 162
 163 static_inline void
 164 rotateright(struct opr_rbtree *head, struct opr_rbtree_node *node)
 165 {
 166     struct opr_rbtree_node *left = node->left;
 167
 168     node->left = left->right;
 169     if (left->right)
 170         left->right->parent = node;
 171
 172     left->right = node;
 173     left->parent = node->parent;
 174
 175     update_parent_ptr(head, node, left);
 176
 177     node->parent = left;
 178 }
 179
 180 static_inline void
 181 rotateleft(struct opr_rbtree *head, struct opr_rbtree_node *node)
 182 {
 183     struct opr_rbtree_node *right = node->right;
 184
 185     node->right = right->left;
 186     if (right->left)
 187         right->left->parent = node;
 188
 189     right->left = node;
 190     right->parent = node->parent;
 191
 192     update_parent_ptr(head, node, right);
 193
 194     node->parent = right;
 195 }
 196
 197 static_inline void
 198 swapnode(struct opr_rbtree_node **a, struct opr_rbtree_node **b)
 199 {
 200     struct opr_rbtree_node *tmp;
 201
 202     tmp = *a;
 203     *a = *b;
 204     *b = tmp;
 205 }
 206
 207 static void
 208 insert_recolour(struct opr_rbtree *head, struct opr_rbtree_node *node)
 209 {
 210     struct opr_rbtree_node *parent, *gramps;
 211
 212     while ((parent = node->parent) && parent->red) {
 213         gramps = parent->parent;
 214
 215         if (parent == gramps->left) {
 216             struct opr_rbtree_node *uncle = gramps->right;
 217
 218             if (uncle && uncle->red) {
 219                 uncle->red = 0;
 220                 parent->red = 0;
 221                 gramps->red = 1;
 222                 node = gramps;
 223                 continue;
 224             }
 225
 226             if (parent->right == node) {
 227                 rotateleft(head, parent);
 228                 swapnode(&parent, &node);
 229             }
 230
 231             parent->red = 0;
 232             gramps->red = 1;
 233             rotateright(head, gramps);
 234         } else {
 235             struct opr_rbtree_node *uncle = gramps->left;
 236
 237             if (uncle && uncle->red) {
 238                 uncle->red = 0;
 239                 parent->red = 0;
 240                 gramps->red = 1;
 241                 node = gramps;
 242                 continue;
 243             }
 244
 245             if (parent->left == node) {
 246                 rotateright(head, parent);
 247                 swapnode(&parent, &node);
 248             }
 249
 250             parent->red = 0;
 251             gramps->red = 1;
 252             rotateleft(head, gramps);
 253         }
 254     }
 255
 256     head->root->red = 0;
 257 }
 258
 259 void
 260 opr_rbtree_insert(struct opr_rbtree *head,
 261                   struct opr_rbtree_node *parent,
 262                   struct opr_rbtree_node **childptr,
 263                   struct opr_rbtree_node *node)
 264 {
 265     /* Link node 'node' into the tree at position 'parent', using either the
 266      * left or right pointers */
 267
 268     node->parent = parent;
 269     node->left = node->right = NULL;
 270     node->red = 1;
 271     *childptr = node;
 272
 273     /* Rebalance the tree for the newly inserted node */
 274     insert_recolour(head, node);
 275 }
 276
 277 static void
 278 remove_recolour(struct opr_rbtree *head, struct opr_rbtree_node *parent,
 279                 struct opr_rbtree_node *node)
 280 {
 281     struct opr_rbtree_node *other;
 282
 283     while ((node == NULL || !node->red) && node != head->root) {
 284         if (parent->left == node) {
 285             other = parent->right;
 286             if (other->red) {
 287                 other->red = 0;
 288                 parent->red = 1;
 289                 rotateleft(head, parent);
 290                 other = parent->right;
 291             }
 292             if ((other->left == NULL || !other->left->red) &&
 293                 (other->right == NULL || !other->right->red)) {
 294                 other->red = 1;
 295                 node = parent;
 296                 parent = node->parent;
 297             } else {
 298                 if (other->right == NULL || !other->right->red) {
 299                     other->left->red = 0;
 300                     other->red = 1;
 301                     rotateright(head, other);
 302                     other = parent->right;
 303                 }
 304                 other->red = parent->red;
 305                 parent->red = 0;
 306                 other->right->red = 0;
 307                 rotateleft(head, parent);
 308                 node = head->root;
 309                 break;
 310             }
 311         } else {
 312             other = parent->left;
 313             if (other->red) {
 314                 other->red = 0;
 315                 parent->red = 1;
 316                 rotateright(head, parent);
 317                 other = parent->left;
 318             }
 319             if ((other->left == NULL || !other->left->red) &&
 320                 (other->right == NULL || !other->right->red)) {
 321                 other->red = 1;
 322                 node = parent;
 323                 parent = node->parent;
 324             } else {
 325                 if (other->left == NULL || !other->left->red) {
 326                     other->right->red = 0;
 327                     other->red = 1;
 328                     rotateleft(head, other);
 329                     other = parent->left;
 330                 }
 331                 other->red = parent->red;
 332                 parent->red = 0;
 333                 other->left->red = 0;
 334                 rotateright(head, parent);
 335                 node = head->root;
 336                 break;
 337             }
 338         }
 339     }
 340     if (node)
 341         node->red = 0;
 342 }
 343
 344 void
 345 opr_rbtree_remove(struct opr_rbtree *head, struct opr_rbtree_node *node)
 346 {
 347     struct opr_rbtree_node *child, *parent;
 348     int red;
 349
 350
 351     if (node->left == NULL && node->right == NULL) {
 352         /* A node with no non-leaf children */
 353         update_parent_ptr(head, node, NULL);
 354
 355         if (!node->red)
 356             remove_recolour(head, node->parent, NULL);
 357
 358         return;
 359     }
 360
 361     if (node->left != NULL && node->right != NULL) {
 362         /* A node with two children.
 363          *
 364          * Move the next node in the tree (which will be a leaf node)
 365          * onto our tree current position, then rebalance as required
 366          */
 367         struct opr_rbtree_node *old, *left;
 368
 369         old = node;
 370
 371         /* Set node to the next node in the tree from the current
 372          * position, where the next node is the left-most leaf node
 373          * in our right child */
 374         node = node->right;
 375         while ((left = node->left) != NULL)
 376             node = left;
 377
 378         /* Move 'node' into the position occupied by 'old', which is being
 379          * removed */
 380
 381         update_parent_ptr(head, old, node);
 382
 383         child = node->right;
 384         parent = node->parent;
 385         red = node->red;
 386
 387         /* As we're logically just copying the value, must preserve the
 388          * old node's colour */
 389         node->red = old->red;
 390
 391         /* ... and the old node's linkage */
 392         if (parent == old)
 393             parent = node;
 394         else {
 395             if (child)
 396                 child->parent = parent;
 397             parent->left = child;
 398
 399             node->right = old->right;
 400             old->right->parent = node;
 401         }
 402
 403         node->parent = old->parent;
 404         node->left = old->left;
 405         old->left->parent = node;
 406
 407         /* If the node being removed was black, then we must recolour the
 408          * tree to maintain balance */
 409         if (!red)
 410             remove_recolour(head, parent, child);
 411
 412         return;
 413     }
 414
 415     /* Only remaining option - node with a single child */
 416
 417     if (node->left == NULL)
 418         child = node->right;
 419     else {
 420         opr_Assert(node->right == NULL);
 421         child = node->left;
 422     }
 423
 424     child->parent = node->parent;
 425
 426     update_parent_ptr(head, node, child);
 427
 428     if (!node->red)
 429         remove_recolour(head, node->parent, child);
 430 }
 431
 432 void
 433 opr_rbtree_replace(struct opr_rbtree *head,
 434                    struct opr_rbtree_node *old,
 435                    struct opr_rbtree_node *replacement)
 436 {
 437     /* Update our parent's pointer to us */
 438     update_parent_ptr(head, old, replacement);
 439
 440     /* And our children's pointers to us */
 441     if (old->left)
 442         old->left->parent = replacement;
 443     if (old->right)
 444         old->right->parent = replacement;
 445
 446     /* Copy over parent, left, right and colour */
 447     *replacement = *old;
 448 }