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