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