drivers/staging/lustre/lustre/ldlm/interval_tree.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 only,
   8  * as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License version 2 for more details (a copy is included
  14  * in the LICENSE file that accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * version 2 along with this program; If not, see
  18  * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
  19  *
  20  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  21  * CA 95054 USA or visit www.sun.com if you need additional information or
  22  * have any questions.
  23  *
  24  * GPL HEADER END
  25  */
  26 /*
  27  * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
  28  * Use is subject to license terms.
  29  */
  30 /*
  31  * This file is part of Lustre, http://www.lustre.org/
  32  * Lustre is a trademark of Sun Microsystems, Inc.
  33  *
  34  * lustre/ldlm/interval_tree.c
  35  *
  36  * Interval tree library used by ldlm extent lock code
  37  *
  38  * Author: Huang Wei <huangwei@clusterfs.com>
  39  * Author: Jay Xiong <jinshan.xiong@sun.com>
  40  */
  41 #include "../include/lustre_dlm.h"
  42 #include "../include/obd_support.h"
  43 #include "../include/interval_tree.h"
  44
  45 enum {
  46         INTERVAL_RED = 0,
  47         INTERVAL_BLACK = 1
  48 };
  49
  50 static inline int node_is_left_child(struct interval_node *node)
  51 {
  52         return node == node->in_parent->in_left;
  53 }
  54
  55 static inline int node_is_right_child(struct interval_node *node)
  56 {
  57         return node == node->in_parent->in_right;
  58 }
  59
  60 static inline int node_is_red(struct interval_node *node)
  61 {
  62         return node->in_color == INTERVAL_RED;
  63 }
  64
  65 static inline int node_is_black(struct interval_node *node)
  66 {
  67         return node->in_color == INTERVAL_BLACK;
  68 }
  69
  70 static inline int extent_compare(struct interval_node_extent *e1,
  71                                  struct interval_node_extent *e2)
  72 {
  73         int rc;
  74
  75         if (e1->start == e2->start) {
  76                 if (e1->end < e2->end)
  77                         rc = -1;
  78                 else if (e1->end > e2->end)
  79                         rc = 1;
  80                 else
  81                         rc = 0;
  82         } else {
  83                 if (e1->start < e2->start)
  84                         rc = -1;
  85                 else
  86                         rc = 1;
  87         }
  88         return rc;
  89 }
  90
  91 static inline int extent_equal(struct interval_node_extent *e1,
  92                                struct interval_node_extent *e2)
  93 {
  94         return (e1->start == e2->start) && (e1->end == e2->end);
  95 }
  96
  97 static inline __u64 max_u64(__u64 x, __u64 y)
  98 {
  99         return x > y ? x : y;
 100 }
 101
 102 static struct interval_node *interval_first(struct interval_node *node)
 103 {
 104         if (!node)
 105                 return NULL;
 106         while (node->in_left)
 107                 node = node->in_left;
 108         return node;
 109 }
 110
 111 static struct interval_node *interval_next(struct interval_node *node)
 112 {
 113         if (!node)
 114                 return NULL;
 115         if (node->in_right)
 116                 return interval_first(node->in_right);
 117         while (node->in_parent && node_is_right_child(node))
 118                 node = node->in_parent;
 119         return node->in_parent;
 120 }
 121
 122 static void __rotate_change_maxhigh(struct interval_node *node,
 123                                     struct interval_node *rotate)
 124 {
 125         __u64 left_max, right_max;
 126
 127         rotate->in_max_high = node->in_max_high;
 128         left_max = node->in_left ? node->in_left->in_max_high : 0;
 129         right_max = node->in_right ? node->in_right->in_max_high : 0;
 130         node->in_max_high  = max_u64(interval_high(node),
 131                                      max_u64(left_max, right_max));
 132 }
 133
 134 /* The left rotation "pivots" around the link from node to node->right, and
 135  * - node will be linked to node->right's left child, and
 136  * - node->right's left child will be linked to node's right child.
 137  */
 138 static void __rotate_left(struct interval_node *node,
 139                           struct interval_node **root)
 140 {
 141         struct interval_node *right = node->in_right;
 142         struct interval_node *parent = node->in_parent;
 143
 144         node->in_right = right->in_left;
 145         if (node->in_right)
 146                 right->in_left->in_parent = node;
 147
 148         right->in_left = node;
 149         right->in_parent = parent;
 150         if (parent) {
 151                 if (node_is_left_child(node))
 152                         parent->in_left = right;
 153                 else
 154                         parent->in_right = right;
 155         } else {
 156                 *root = right;
 157         }
 158         node->in_parent = right;
 159
 160         /* update max_high for node and right */
 161         __rotate_change_maxhigh(node, right);
 162 }
 163
 164 /* The right rotation "pivots" around the link from node to node->left, and
 165  * - node will be linked to node->left's right child, and
 166  * - node->left's right child will be linked to node's left child.
 167  */
 168 static void __rotate_right(struct interval_node *node,
 169                            struct interval_node **root)
 170 {
 171         struct interval_node *left = node->in_left;
 172         struct interval_node *parent = node->in_parent;
 173
 174         node->in_left = left->in_right;
 175         if (node->in_left)
 176                 left->in_right->in_parent = node;
 177         left->in_right = node;
 178
 179         left->in_parent = parent;
 180         if (parent) {
 181                 if (node_is_right_child(node))
 182                         parent->in_right = left;
 183                 else
 184                         parent->in_left = left;
 185         } else {
 186                 *root = left;
 187         }
 188         node->in_parent = left;
 189
 190         /* update max_high for node and left */
 191         __rotate_change_maxhigh(node, left);
 192 }
 193
 194 #define interval_swap(a, b) do {                        \
 195         struct interval_node *c = a; a = b; b = c;      \
 196 } while (0)
 197
 198 /*
 199  * Operations INSERT and DELETE, when run on a tree with n keys,
 200  * take O(logN) time.Because they modify the tree, the result
 201  * may violate the red-black properties.To restore these properties,
 202  * we must change the colors of some of the nodes in the tree
 203  * and also change the pointer structure.
 204  */
 205 static void interval_insert_color(struct interval_node *node,
 206                                   struct interval_node **root)
 207 {
 208         struct interval_node *parent, *gparent;
 209
 210         while ((parent = node->in_parent) && node_is_red(parent)) {
 211                 gparent = parent->in_parent;
 212                 /* Parent is RED, so gparent must not be NULL */
 213                 if (node_is_left_child(parent)) {
 214                         struct interval_node *uncle;
 215
 216                         uncle = gparent->in_right;
 217                         if (uncle && node_is_red(uncle)) {
 218                                 uncle->in_color = INTERVAL_BLACK;
 219                                 parent->in_color = INTERVAL_BLACK;
 220                                 gparent->in_color = INTERVAL_RED;
 221                                 node = gparent;
 222                                 continue;
 223                         }
 224
 225                         if (parent->in_right == node) {
 226                                 __rotate_left(parent, root);
 227                                 interval_swap(node, parent);
 228                         }
 229
 230                         parent->in_color = INTERVAL_BLACK;
 231                         gparent->in_color = INTERVAL_RED;
 232                         __rotate_right(gparent, root);
 233                 } else {
 234                         struct interval_node *uncle;
 235
 236                         uncle = gparent->in_left;
 237                         if (uncle && node_is_red(uncle)) {
 238                                 uncle->in_color = INTERVAL_BLACK;
 239                                 parent->in_color = INTERVAL_BLACK;
 240                                 gparent->in_color = INTERVAL_RED;
 241                                 node = gparent;
 242                                 continue;
 243                         }
 244
 245                         if (node_is_left_child(node)) {
 246                                 __rotate_right(parent, root);
 247                                 interval_swap(node, parent);
 248                         }
 249
 250                         parent->in_color = INTERVAL_BLACK;
 251                         gparent->in_color = INTERVAL_RED;
 252                         __rotate_left(gparent, root);
 253                 }
 254         }
 255
 256         (*root)->in_color = INTERVAL_BLACK;
 257 }
 258
 259 struct interval_node *interval_insert(struct interval_node *node,
 260                                       struct interval_node **root)
 261
 262 {
 263         struct interval_node **p, *parent = NULL;
 264
 265         LASSERT(!interval_is_intree(node));
 266         p = root;
 267         while (*p) {
 268                 parent = *p;
 269                 if (extent_equal(&parent->in_extent, &node->in_extent))
 270                         return parent;
 271
 272                 /* max_high field must be updated after each iteration */
 273                 if (parent->in_max_high < interval_high(node))
 274                         parent->in_max_high = interval_high(node);
 275
 276                 if (extent_compare(&node->in_extent, &parent->in_extent) < 0)
 277                         p = &parent->in_left;
 278                 else
 279                         p = &parent->in_right;
 280         }
 281
 282         /* link node into the tree */
 283         node->in_parent = parent;
 284         node->in_color = INTERVAL_RED;
 285         node->in_left = NULL;
 286         node->in_right = NULL;
 287         *p = node;
 288
 289         interval_insert_color(node, root);
 290         node->in_intree = 1;
 291
 292         return NULL;
 293 }
 294 EXPORT_SYMBOL(interval_insert);
 295
 296 static inline int node_is_black_or_0(struct interval_node *node)
 297 {
 298         return !node || node_is_black(node);
 299 }
 300
 301 static void interval_erase_color(struct interval_node *node,
 302                                  struct interval_node *parent,
 303                                  struct interval_node **root)
 304 {
 305         struct interval_node *tmp;
 306
 307         while (node_is_black_or_0(node) && node != *root) {
 308                 if (parent->in_left == node) {
 309                         tmp = parent->in_right;
 310                         if (node_is_red(tmp)) {
 311                                 tmp->in_color = INTERVAL_BLACK;
 312                                 parent->in_color = INTERVAL_RED;
 313                                 __rotate_left(parent, root);
 314                                 tmp = parent->in_right;
 315                         }
 316                         if (node_is_black_or_0(tmp->in_left) &&
 317                             node_is_black_or_0(tmp->in_right)) {
 318                                 tmp->in_color = INTERVAL_RED;
 319                                 node = parent;
 320                                 parent = node->in_parent;
 321                         } else {
 322                                 if (node_is_black_or_0(tmp->in_right)) {
 323                                         struct interval_node *o_left;
 324
 325                                         o_left = tmp->in_left;
 326                                         if (o_left)
 327                                                 o_left->in_color = INTERVAL_BLACK;
 328                                         tmp->in_color = INTERVAL_RED;
 329                                         __rotate_right(tmp, root);
 330                                         tmp = parent->in_right;
 331                                 }
 332                                 tmp->in_color = parent->in_color;
 333                                 parent->in_color = INTERVAL_BLACK;
 334                                 if (tmp->in_right)
 335                                         tmp->in_right->in_color = INTERVAL_BLACK;
 336                                 __rotate_left(parent, root);
 337                                 node = *root;
 338                                 break;
 339                         }
 340                 } else {
 341                         tmp = parent->in_left;
 342                         if (node_is_red(tmp)) {
 343                                 tmp->in_color = INTERVAL_BLACK;
 344                                 parent->in_color = INTERVAL_RED;
 345                                 __rotate_right(parent, root);
 346                                 tmp = parent->in_left;
 347                         }
 348                         if (node_is_black_or_0(tmp->in_left) &&
 349                             node_is_black_or_0(tmp->in_right)) {
 350                                 tmp->in_color = INTERVAL_RED;
 351                                 node = parent;
 352                                 parent = node->in_parent;
 353                         } else {
 354                                 if (node_is_black_or_0(tmp->in_left)) {
 355                                         struct interval_node *o_right;
 356
 357                                         o_right = tmp->in_right;
 358                                         if (o_right)
 359                                                 o_right->in_color = INTERVAL_BLACK;
 360                                         tmp->in_color = INTERVAL_RED;
 361                                         __rotate_left(tmp, root);
 362                                         tmp = parent->in_left;
 363                                 }
 364                                 tmp->in_color = parent->in_color;
 365                                 parent->in_color = INTERVAL_BLACK;
 366                                 if (tmp->in_left)
 367                                         tmp->in_left->in_color = INTERVAL_BLACK;
 368                                 __rotate_right(parent, root);
 369                                 node = *root;
 370                                 break;
 371                         }
 372                 }
 373         }
 374         if (node)
 375                 node->in_color = INTERVAL_BLACK;
 376 }
 377
 378 /*
 379  * if the @max_high value of @node is changed, this function traverse  a path
 380  * from node  up to the root to update max_high for the whole tree.
 381  */
 382 static void update_maxhigh(struct interval_node *node,
 383                            __u64  old_maxhigh)
 384 {
 385         __u64 left_max, right_max;
 386
 387         while (node) {
 388                 left_max = node->in_left ? node->in_left->in_max_high : 0;
 389                 right_max = node->in_right ? node->in_right->in_max_high : 0;
 390                 node->in_max_high = max_u64(interval_high(node),
 391                                             max_u64(left_max, right_max));
 392
 393                 if (node->in_max_high >= old_maxhigh)
 394                         break;
 395                 node = node->in_parent;
 396         }
 397 }
 398
 399 void interval_erase(struct interval_node *node,
 400                     struct interval_node **root)
 401 {
 402         struct interval_node *child, *parent;
 403         int color;
 404
 405         LASSERT(interval_is_intree(node));
 406         node->in_intree = 0;
 407         if (!node->in_left) {
 408                 child = node->in_right;
 409         } else if (!node->in_right) {
 410                 child = node->in_left;
 411         } else { /* Both left and right child are not NULL */
 412                 struct interval_node *old = node;
 413
 414                 node = interval_next(node);
 415                 child = node->in_right;
 416                 parent = node->in_parent;
 417                 color = node->in_color;
 418
 419                 if (child)
 420                         child->in_parent = parent;
 421                 if (parent == old)
 422                         parent->in_right = child;
 423                 else
 424                         parent->in_left = child;
 425
 426                 node->in_color = old->in_color;
 427                 node->in_right = old->in_right;
 428                 node->in_left = old->in_left;
 429                 node->in_parent = old->in_parent;
 430
 431                 if (old->in_parent) {
 432                         if (node_is_left_child(old))
 433                                 old->in_parent->in_left = node;
 434                         else
 435                                 old->in_parent->in_right = node;
 436                 } else {
 437                         *root = node;
 438                 }
 439
 440                 old->in_left->in_parent = node;
 441                 if (old->in_right)
 442                         old->in_right->in_parent = node;
 443                 update_maxhigh(child ? : parent, node->in_max_high);
 444                 update_maxhigh(node, old->in_max_high);
 445                 if (parent == old)
 446                         parent = node;
 447                 goto color;
 448         }
 449         parent = node->in_parent;
 450         color = node->in_color;
 451
 452         if (child)
 453                 child->in_parent = parent;
 454         if (parent) {
 455                 if (node_is_left_child(node))
 456                         parent->in_left = child;
 457                 else
 458                         parent->in_right = child;
 459         } else {
 460                 *root = child;
 461         }
 462
 463         update_maxhigh(child ? : parent, node->in_max_high);
 464
 465 color:
 466         if (color == INTERVAL_BLACK)
 467                 interval_erase_color(child, parent, root);
 468 }
 469 EXPORT_SYMBOL(interval_erase);