Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 |
Oleg Drokin | 6a5b99a | 2016-06-14 23:33:40 -0400 | [diff] [blame] | 18 | * http://www.gnu.org/licenses/gpl-2.0.html |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 19 | * |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 | */ |
Greg Kroah-Hartman | e27db14 | 2014-07-11 22:29:36 -0700 | [diff] [blame] | 37 | #include "../include/lustre_dlm.h" |
| 38 | #include "../include/obd_support.h" |
| 39 | #include "../include/interval_tree.h" |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 | { |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 48 | return node == node->in_parent->in_left; |
| 49 | } |
| 50 | |
| 51 | static inline int node_is_right_child(struct interval_node *node) |
| 52 | { |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Andreas Ruprecht | 902f3bb | 2014-11-23 14:37:48 +0100 | [diff] [blame] | 70 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 93 | static inline __u64 max_u64(__u64 x, __u64 y) |
| 94 | { |
| 95 | return x > y ? x : y; |
| 96 | } |
| 97 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 98 | static struct interval_node *interval_first(struct interval_node *node) |
| 99 | { |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 100 | if (!node) |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 101 | return NULL; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 102 | while (node->in_left) |
| 103 | node = node->in_left; |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 104 | return node; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 105 | } |
| 106 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 107 | static struct interval_node *interval_next(struct interval_node *node) |
| 108 | { |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 109 | if (!node) |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 110 | return NULL; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 111 | if (node->in_right) |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 112 | return interval_first(node->in_right); |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 113 | while (node->in_parent && node_is_right_child(node)) |
| 114 | node = node->in_parent; |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 115 | return node->in_parent; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 116 | } |
| 117 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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), |
Rashika Kheria | 5bd7797 | 2013-10-26 16:23:21 +0530 | [diff] [blame] | 127 | max_u64(left_max, right_max)); |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 |
Oleg Drokin | 6f789a6 | 2016-02-24 22:00:29 -0500 | [diff] [blame] | 132 | * - node->right's left child will be linked to node's right child. |
| 133 | */ |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 |
Oleg Drokin | 6f789a6 | 2016-02-24 22:00:29 -0500 | [diff] [blame] | 162 | * - node->left's right child will be linked to node's left child. |
| 163 | */ |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Andreas Ruprecht | 902f3bb | 2014-11-23 14:37:48 +0100 | [diff] [blame] | 211 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Andreas Ruprecht | 902f3bb | 2014-11-23 14:37:48 +0100 | [diff] [blame] | 231 | |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 260 | |
| 261 | LASSERT(!interval_is_intree(node)); |
| 262 | p = root; |
| 263 | while (*p) { |
| 264 | parent = *p; |
Shivani Bhardwaj | 5d21c5a | 2015-10-31 20:26:56 +0530 | [diff] [blame] | 265 | if (extent_equal(&parent->in_extent, &node->in_extent)) |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 266 | return parent; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 | |
Shivani Bhardwaj | 5d21c5a | 2015-10-31 20:26:56 +0530 | [diff] [blame] | 272 | if (extent_compare(&node->in_extent, &parent->in_extent) < 0) |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Shivani Bhardwaj | 7b318b4 | 2015-10-19 00:17:13 +0530 | [diff] [blame] | 281 | node->in_left = NULL; |
| 282 | node->in_right = NULL; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 283 | *p = node; |
| 284 | |
| 285 | interval_insert_color(node, root); |
| 286 | node->in_intree = 1; |
| 287 | |
Greg Kroah-Hartman | 0a3bdb0 | 2013-08-03 10:35:28 +0800 | [diff] [blame] | 288 | return NULL; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Andreas Ruprecht | 902f3bb | 2014-11-23 14:37:48 +0100 | [diff] [blame] | 320 | |
Rashika Kheria | 16fcfa1 | 2013-10-27 18:49:31 +0530 | [diff] [blame] | 321 | o_left = tmp->in_left; |
| 322 | if (o_left) |
Rashika Kheria | 490f4db | 2013-10-26 16:19:42 +0530 | [diff] [blame] | 323 | o_left->in_color = INTERVAL_BLACK; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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) |
Rashika Kheria | 490f4db | 2013-10-26 16:19:42 +0530 | [diff] [blame] | 331 | tmp->in_right->in_color = INTERVAL_BLACK; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Andreas Ruprecht | 902f3bb | 2014-11-23 14:37:48 +0100 | [diff] [blame] | 352 | |
Rashika Kheria | 16fcfa1 | 2013-10-27 18:49:31 +0530 | [diff] [blame] | 353 | o_right = tmp->in_right; |
| 354 | if (o_right) |
Rashika Kheria | 490f4db | 2013-10-26 16:19:42 +0530 | [diff] [blame] | 355 | o_right->in_color = INTERVAL_BLACK; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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 | } |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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) |
Rashika Kheria | 490f4db | 2013-10-26 16:19:42 +0530 | [diff] [blame] | 442 | parent = node; |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 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); |
Peng Tao | d7e09d0 | 2013-05-02 16:46:55 +0800 | [diff] [blame] | 464 | } |
| 465 | EXPORT_SYMBOL(interval_erase); |