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 static void __rotate_left(struct interval_node *node,
 138                           struct interval_node **root)
 139 {
 140         struct interval_node *right = node->in_right;
 141         struct interval_node *parent = node->in_parent;
 142
 143         node->in_right = right->in_left;
 144         if (node->in_right)
 145                 right->in_left->in_parent = node;
 146
 147         right->in_left = node;
 148         right->in_parent = parent;
 149         if (parent) {
 150                 if (node_is_left_child(node))
 151                         parent->in_left = right;
 152                 else
 153                         parent->in_right = right;
 154         } else {
 155                 *root = right;
 156         }
 157         node->in_parent = right;
 158
 159         /* update max_high for node and right */
 160         __rotate_change_maxhigh(node, right);
 161 }
 162
 163 /* The right rotation "pivots" around the link from node to node->left, and
 164  * - node will be linked to node->left's right child, and
 165  * - node->left's right child will be linked to node's left child.  */
 166 static void __rotate_right(struct interval_node *node,
 167                            struct interval_node **root)
 168 {
 169         struct interval_node *left = node->in_left;
 170         struct interval_node *parent = node->in_parent;
 171
 172         node->in_left = left->in_right;
 173         if (node->in_left)
 174                 left->in_right->in_parent = node;
 175         left->in_right = node;
 176
 177         left->in_parent = parent;
 178         if (parent) {
 179                 if (node_is_right_child(node))
 180                         parent->in_right = left;
 181                 else
 182                         parent->in_left = left;
 183         } else {
 184                 *root = left;
 185         }
 186         node->in_parent = left;
 187
 188         /* update max_high for node and left */
 189         __rotate_change_maxhigh(node, left);
 190 }
 191
 192 #define interval_swap(a, b) do {                        \
 193         struct interval_node *c = a; a = b; b = c;      \
 194 } while (0)
 195
 196 /*
 197  * Operations INSERT and DELETE, when run on a tree with n keys,
 198  * take O(logN) time.Because they modify the tree, the result
 199  * may violate the red-black properties.To restore these properties,
 200  * we must change the colors of some of the nodes in the tree
 201  * and also change the pointer structure.
 202  */
 203 static void interval_insert_color(struct interval_node *node,
 204                                   struct interval_node **root)
 205 {
 206         struct interval_node *parent, *gparent;
 207
 208         while ((parent = node->in_parent) && node_is_red(parent)) {
 209                 gparent = parent->in_parent;
 210                 /* Parent is RED, so gparent must not be NULL */
 211                 if (node_is_left_child(parent)) {
 212                         struct interval_node *uncle;
 213
 214                         uncle = gparent->in_right;
 215                         if (uncle && node_is_red(uncle)) {
 216                                 uncle->in_color = INTERVAL_BLACK;
 217                                 parent->in_color = INTERVAL_BLACK;
 218                                 gparent->in_color = INTERVAL_RED;
 219                                 node = gparent;
 220                                 continue;
 221                         }
 222
 223                         if (parent->in_right == node) {
 224                                 __rotate_left(parent, root);
 225                                 interval_swap(node, parent);
 226                         }
 227
 228                         parent->in_color = INTERVAL_BLACK;
 229                         gparent->in_color = INTERVAL_RED;
 230                         __rotate_right(gparent, root);
 231                 } else {
 232                         struct interval_node *uncle;
 233
 234                         uncle = gparent->in_left;
 235                         if (uncle && node_is_red(uncle)) {
 236                                 uncle->in_color = INTERVAL_BLACK;
 237                                 parent->in_color = INTERVAL_BLACK;
 238                                 gparent->in_color = INTERVAL_RED;
 239                                 node = gparent;
 240                                 continue;
 241                         }
 242
 243                         if (node_is_left_child(node)) {
 244                                 __rotate_right(parent, root);
 245                                 interval_swap(node, parent);
 246                         }
 247
 248                         parent->in_color = INTERVAL_BLACK;
 249                         gparent->in_color = INTERVAL_RED;
 250                         __rotate_left(gparent, root);
 251                 }
 252         }
 253
 254         (*root)->in_color = INTERVAL_BLACK;
 255 }
 256
 257 struct interval_node *interval_insert(struct interval_node *node,
 258                                       struct interval_node **root)
 259
 260 {
 261         struct interval_node **p, *parent = NULL;
 262
 263         LASSERT(!interval_is_intree(node));
 264         p = root;
 265         while (*p) {
 266                 parent = *p;
 267                 if (extent_equal(&parent->in_extent, &node->in_extent))
 268                         return parent;
 269
 270                 /* max_high field must be updated after each iteration */
 271                 if (parent->in_max_high < interval_high(node))
 272                         parent->in_max_high = interval_high(node);
 273
 274                 if (extent_compare(&node->in_extent, &parent->in_extent) < 0)
 275                         p = &parent->in_left;
 276                 else
 277                         p = &parent->in_right;
 278         }
 279
 280         /* link node into the tree */
 281         node->in_parent = parent;
 282         node->in_color = INTERVAL_RED;
 283         node->in_left = NULL;
 284         node->in_right = NULL;
 285         *p = node;
 286
 287         interval_insert_color(node, root);
 288         node->in_intree = 1;
 289
 290         return NULL;
 291 }
 292 EXPORT_SYMBOL(interval_insert);
 293
 294 static inline int node_is_black_or_0(struct interval_node *node)
 295 {
 296         return !node || node_is_black(node);
 297 }
 298
 299 static void interval_erase_color(struct interval_node *node,
 300                                  struct interval_node *parent,
 301                                  struct interval_node **root)
 302 {
 303         struct interval_node *tmp;
 304
 305         while (node_is_black_or_0(node) && node != *root) {
 306                 if (parent->in_left == node) {
 307                         tmp = parent->in_right;
 308                         if (node_is_red(tmp)) {
 309                                 tmp->in_color = INTERVAL_BLACK;
 310                                 parent->in_color = INTERVAL_RED;
 311                                 __rotate_left(parent, root);
 312                                 tmp = parent->in_right;
 313                         }
 314                         if (node_is_black_or_0(tmp->in_left) &&
 315                             node_is_black_or_0(tmp->in_right)) {
 316                                 tmp->in_color = INTERVAL_RED;
 317                                 node = parent;
 318                                 parent = node->in_parent;
 319                         } else {
 320                                 if (node_is_black_or_0(tmp->in_right)) {
 321                                         struct interval_node *o_left;
 322
 323                                         o_left = tmp->in_left;
 324                                         if (o_left)
 325                                                 o_left->in_color = INTERVAL_BLACK;
 326                                         tmp->in_color = INTERVAL_RED;
 327                                         __rotate_right(tmp, root);
 328                                         tmp = parent->in_right;
 329                                 }
 330                                 tmp->in_color = parent->in_color;
 331                                 parent->in_color = INTERVAL_BLACK;
 332                                 if (tmp->in_right)
 333                                         tmp->in_right->in_color = INTERVAL_BLACK;
 334                                 __rotate_left(parent, root);
 335                                 node = *root;
 336                                 break;
 337                         }
 338                 } else {
 339                         tmp = parent->in_left;
 340                         if (node_is_red(tmp)) {
 341                                 tmp->in_color = INTERVAL_BLACK;
 342                                 parent->in_color = INTERVAL_RED;
 343                                 __rotate_right(parent, root);
 344                                 tmp = parent->in_left;
 345                         }
 346                         if (node_is_black_or_0(tmp->in_left) &&
 347                             node_is_black_or_0(tmp->in_right)) {
 348                                 tmp->in_color = INTERVAL_RED;
 349                                 node = parent;
 350                                 parent = node->in_parent;
 351                         } else {
 352                                 if (node_is_black_or_0(tmp->in_left)) {
 353                                         struct interval_node *o_right;
 354
 355                                         o_right = tmp->in_right;
 356                                         if (o_right)
 357                                                 o_right->in_color = INTERVAL_BLACK;
 358                                         tmp->in_color = INTERVAL_RED;
 359                                         __rotate_left(tmp, root);
 360                                         tmp = parent->in_left;
 361                                 }
 362                                 tmp->in_color = parent->in_color;
 363                                 parent->in_color = INTERVAL_BLACK;
 364                                 if (tmp->in_left)
 365                                         tmp->in_left->in_color = INTERVAL_BLACK;
 366                                 __rotate_right(parent, root);
 367                                 node = *root;
 368                                 break;
 369                         }
 370                 }
 371         }
 372         if (node)
 373                 node->in_color = INTERVAL_BLACK;
 374 }
 375
 376 /*
 377  * if the @max_high value of @node is changed, this function traverse  a path
 378  * from node  up to the root to update max_high for the whole tree.
 379  */
 380 static void update_maxhigh(struct interval_node *node,
 381                            __u64  old_maxhigh)
 382 {
 383         __u64 left_max, right_max;
 384
 385         while (node) {
 386                 left_max = node->in_left ? node->in_left->in_max_high : 0;
 387                 right_max = node->in_right ? node->in_right->in_max_high : 0;
 388                 node->in_max_high = max_u64(interval_high(node),
 389                                             max_u64(left_max, right_max));
 390
 391                 if (node->in_max_high >= old_maxhigh)
 392                         break;
 393                 node = node->in_parent;
 394         }
 395 }
 396
 397 void interval_erase(struct interval_node *node,
 398                     struct interval_node **root)
 399 {
 400         struct interval_node *child, *parent;
 401         int color;
 402
 403         LASSERT(interval_is_intree(node));
 404         node->in_intree = 0;
 405         if (!node->in_left) {
 406                 child = node->in_right;
 407         } else if (!node->in_right) {
 408                 child = node->in_left;
 409         } else { /* Both left and right child are not NULL */
 410                 struct interval_node *old = node;
 411
 412                 node = interval_next(node);
 413                 child = node->in_right;
 414                 parent = node->in_parent;
 415                 color = node->in_color;
 416
 417                 if (child)
 418                         child->in_parent = parent;
 419                 if (parent == old)
 420                         parent->in_right = child;
 421                 else
 422                         parent->in_left = child;
 423
 424                 node->in_color = old->in_color;
 425                 node->in_right = old->in_right;
 426                 node->in_left = old->in_left;
 427                 node->in_parent = old->in_parent;
 428
 429                 if (old->in_parent) {
 430                         if (node_is_left_child(old))
 431                                 old->in_parent->in_left = node;
 432                         else
 433                                 old->in_parent->in_right = node;
 434                 } else {
 435                         *root = node;
 436                 }
 437
 438                 old->in_left->in_parent = node;
 439                 if (old->in_right)
 440                         old->in_right->in_parent = node;
 441                 update_maxhigh(child ? : parent, node->in_max_high);
 442                 update_maxhigh(node, old->in_max_high);
 443                 if (parent == old)
 444                         parent = node;
 445                 goto color;
 446         }
 447         parent = node->in_parent;
 448         color = node->in_color;
 449
 450         if (child)
 451                 child->in_parent = parent;
 452         if (parent) {
 453                 if (node_is_left_child(node))
 454                         parent->in_left = child;
 455                 else
 456                         parent->in_right = child;
 457         } else {
 458                 *root = child;
 459         }
 460
 461         update_maxhigh(child ? : parent, node->in_max_high);
 462
 463 color:
 464         if (color == INTERVAL_BLACK)
 465                 interval_erase_color(child, parent, root);
 466 }
 467 EXPORT_SYMBOL(interval_erase);