11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds Red Black Trees 31da177e4SLinus Torvalds (C) 1999 Andrea Arcangeli <andrea@suse.de> 41da177e4SLinus Torvalds (C) 2002 David Woodhouse <dwmw2@infradead.org> 51da177e4SLinus Torvalds 61da177e4SLinus Torvalds This program is free software; you can redistribute it and/or modify 71da177e4SLinus Torvalds it under the terms of the GNU General Public License as published by 81da177e4SLinus Torvalds the Free Software Foundation; either version 2 of the License, or 91da177e4SLinus Torvalds (at your option) any later version. 101da177e4SLinus Torvalds 111da177e4SLinus Torvalds This program is distributed in the hope that it will be useful, 121da177e4SLinus Torvalds but WITHOUT ANY WARRANTY; without even the implied warranty of 131da177e4SLinus Torvalds MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 141da177e4SLinus Torvalds GNU General Public License for more details. 151da177e4SLinus Torvalds 161da177e4SLinus Torvalds You should have received a copy of the GNU General Public License 171da177e4SLinus Torvalds along with this program; if not, write to the Free Software 181da177e4SLinus Torvalds Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 191da177e4SLinus Torvalds 201da177e4SLinus Torvalds linux/lib/rbtree.c 211da177e4SLinus Torvalds */ 221da177e4SLinus Torvalds 231da177e4SLinus Torvalds #include <linux/rbtree.h> 241da177e4SLinus Torvalds #include <linux/module.h> 251da177e4SLinus Torvalds 261da177e4SLinus Torvalds static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 271da177e4SLinus Torvalds { 281da177e4SLinus Torvalds struct rb_node *right = node->rb_right; 2955a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 301da177e4SLinus Torvalds 311da177e4SLinus Torvalds if ((node->rb_right = right->rb_left)) 3255a98102SDavid Woodhouse rb_set_parent(right->rb_left, node); 331da177e4SLinus Torvalds right->rb_left = node; 341da177e4SLinus Torvalds 3555a98102SDavid Woodhouse rb_set_parent(right, parent); 3655a98102SDavid Woodhouse 3755a98102SDavid Woodhouse if (parent) 381da177e4SLinus Torvalds { 3955a98102SDavid Woodhouse if (node == parent->rb_left) 4055a98102SDavid Woodhouse parent->rb_left = right; 411da177e4SLinus Torvalds else 4255a98102SDavid Woodhouse parent->rb_right = right; 431da177e4SLinus Torvalds } 441da177e4SLinus Torvalds else 451da177e4SLinus Torvalds root->rb_node = right; 4655a98102SDavid Woodhouse rb_set_parent(node, right); 471da177e4SLinus Torvalds } 481da177e4SLinus Torvalds 491da177e4SLinus Torvalds static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 501da177e4SLinus Torvalds { 511da177e4SLinus Torvalds struct rb_node *left = node->rb_left; 5255a98102SDavid Woodhouse struct rb_node *parent = rb_parent(node); 531da177e4SLinus Torvalds 541da177e4SLinus Torvalds if ((node->rb_left = left->rb_right)) 5555a98102SDavid Woodhouse rb_set_parent(left->rb_right, node); 561da177e4SLinus Torvalds left->rb_right = node; 571da177e4SLinus Torvalds 5855a98102SDavid Woodhouse rb_set_parent(left, parent); 5955a98102SDavid Woodhouse 6055a98102SDavid Woodhouse if (parent) 611da177e4SLinus Torvalds { 6255a98102SDavid Woodhouse if (node == parent->rb_right) 6355a98102SDavid Woodhouse parent->rb_right = left; 641da177e4SLinus Torvalds else 6555a98102SDavid Woodhouse parent->rb_left = left; 661da177e4SLinus Torvalds } 671da177e4SLinus Torvalds else 681da177e4SLinus Torvalds root->rb_node = left; 6955a98102SDavid Woodhouse rb_set_parent(node, left); 701da177e4SLinus Torvalds } 711da177e4SLinus Torvalds 721da177e4SLinus Torvalds void rb_insert_color(struct rb_node *node, struct rb_root *root) 731da177e4SLinus Torvalds { 741da177e4SLinus Torvalds struct rb_node *parent, *gparent; 751da177e4SLinus Torvalds 7655a98102SDavid Woodhouse while ((parent = rb_parent(node)) && rb_is_red(parent)) 771da177e4SLinus Torvalds { 7855a98102SDavid Woodhouse gparent = rb_parent(parent); 791da177e4SLinus Torvalds 801da177e4SLinus Torvalds if (parent == gparent->rb_left) 811da177e4SLinus Torvalds { 821da177e4SLinus Torvalds { 831da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_right; 8455a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 851da177e4SLinus Torvalds { 8655a98102SDavid Woodhouse rb_set_black(uncle); 8755a98102SDavid Woodhouse rb_set_black(parent); 8855a98102SDavid Woodhouse rb_set_red(gparent); 891da177e4SLinus Torvalds node = gparent; 901da177e4SLinus Torvalds continue; 911da177e4SLinus Torvalds } 921da177e4SLinus Torvalds } 931da177e4SLinus Torvalds 941da177e4SLinus Torvalds if (parent->rb_right == node) 951da177e4SLinus Torvalds { 961da177e4SLinus Torvalds register struct rb_node *tmp; 971da177e4SLinus Torvalds __rb_rotate_left(parent, root); 981da177e4SLinus Torvalds tmp = parent; 991da177e4SLinus Torvalds parent = node; 1001da177e4SLinus Torvalds node = tmp; 1011da177e4SLinus Torvalds } 1021da177e4SLinus Torvalds 10355a98102SDavid Woodhouse rb_set_black(parent); 10455a98102SDavid Woodhouse rb_set_red(gparent); 1051da177e4SLinus Torvalds __rb_rotate_right(gparent, root); 1061da177e4SLinus Torvalds } else { 1071da177e4SLinus Torvalds { 1081da177e4SLinus Torvalds register struct rb_node *uncle = gparent->rb_left; 10955a98102SDavid Woodhouse if (uncle && rb_is_red(uncle)) 1101da177e4SLinus Torvalds { 11155a98102SDavid Woodhouse rb_set_black(uncle); 11255a98102SDavid Woodhouse rb_set_black(parent); 11355a98102SDavid Woodhouse rb_set_red(gparent); 1141da177e4SLinus Torvalds node = gparent; 1151da177e4SLinus Torvalds continue; 1161da177e4SLinus Torvalds } 1171da177e4SLinus Torvalds } 1181da177e4SLinus Torvalds 1191da177e4SLinus Torvalds if (parent->rb_left == node) 1201da177e4SLinus Torvalds { 1211da177e4SLinus Torvalds register struct rb_node *tmp; 1221da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1231da177e4SLinus Torvalds tmp = parent; 1241da177e4SLinus Torvalds parent = node; 1251da177e4SLinus Torvalds node = tmp; 1261da177e4SLinus Torvalds } 1271da177e4SLinus Torvalds 12855a98102SDavid Woodhouse rb_set_black(parent); 12955a98102SDavid Woodhouse rb_set_red(gparent); 1301da177e4SLinus Torvalds __rb_rotate_left(gparent, root); 1311da177e4SLinus Torvalds } 1321da177e4SLinus Torvalds } 1331da177e4SLinus Torvalds 13455a98102SDavid Woodhouse rb_set_black(root->rb_node); 1351da177e4SLinus Torvalds } 1361da177e4SLinus Torvalds EXPORT_SYMBOL(rb_insert_color); 1371da177e4SLinus Torvalds 1381da177e4SLinus Torvalds static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 1391da177e4SLinus Torvalds struct rb_root *root) 1401da177e4SLinus Torvalds { 1411da177e4SLinus Torvalds struct rb_node *other; 1421da177e4SLinus Torvalds 14355a98102SDavid Woodhouse while ((!node || rb_is_black(node)) && node != root->rb_node) 1441da177e4SLinus Torvalds { 1451da177e4SLinus Torvalds if (parent->rb_left == node) 1461da177e4SLinus Torvalds { 1471da177e4SLinus Torvalds other = parent->rb_right; 14855a98102SDavid Woodhouse if (rb_is_red(other)) 1491da177e4SLinus Torvalds { 15055a98102SDavid Woodhouse rb_set_black(other); 15155a98102SDavid Woodhouse rb_set_red(parent); 1521da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1531da177e4SLinus Torvalds other = parent->rb_right; 1541da177e4SLinus Torvalds } 15555a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 15655a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1571da177e4SLinus Torvalds { 15855a98102SDavid Woodhouse rb_set_red(other); 1591da177e4SLinus Torvalds node = parent; 16055a98102SDavid Woodhouse parent = rb_parent(node); 1611da177e4SLinus Torvalds } 1621da177e4SLinus Torvalds else 1631da177e4SLinus Torvalds { 16455a98102SDavid Woodhouse if (!other->rb_right || rb_is_black(other->rb_right)) 1651da177e4SLinus Torvalds { 16655a63998SWolfram Strepp rb_set_black(other->rb_left); 16755a98102SDavid Woodhouse rb_set_red(other); 1681da177e4SLinus Torvalds __rb_rotate_right(other, root); 1691da177e4SLinus Torvalds other = parent->rb_right; 1701da177e4SLinus Torvalds } 1712f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 17255a98102SDavid Woodhouse rb_set_black(parent); 17355a98102SDavid Woodhouse rb_set_black(other->rb_right); 1741da177e4SLinus Torvalds __rb_rotate_left(parent, root); 1751da177e4SLinus Torvalds node = root->rb_node; 1761da177e4SLinus Torvalds break; 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds } 1791da177e4SLinus Torvalds else 1801da177e4SLinus Torvalds { 1811da177e4SLinus Torvalds other = parent->rb_left; 18255a98102SDavid Woodhouse if (rb_is_red(other)) 1831da177e4SLinus Torvalds { 18455a98102SDavid Woodhouse rb_set_black(other); 18555a98102SDavid Woodhouse rb_set_red(parent); 1861da177e4SLinus Torvalds __rb_rotate_right(parent, root); 1871da177e4SLinus Torvalds other = parent->rb_left; 1881da177e4SLinus Torvalds } 18955a98102SDavid Woodhouse if ((!other->rb_left || rb_is_black(other->rb_left)) && 19055a98102SDavid Woodhouse (!other->rb_right || rb_is_black(other->rb_right))) 1911da177e4SLinus Torvalds { 19255a98102SDavid Woodhouse rb_set_red(other); 1931da177e4SLinus Torvalds node = parent; 19455a98102SDavid Woodhouse parent = rb_parent(node); 1951da177e4SLinus Torvalds } 1961da177e4SLinus Torvalds else 1971da177e4SLinus Torvalds { 19855a98102SDavid Woodhouse if (!other->rb_left || rb_is_black(other->rb_left)) 1991da177e4SLinus Torvalds { 20055a63998SWolfram Strepp rb_set_black(other->rb_right); 20155a98102SDavid Woodhouse rb_set_red(other); 2021da177e4SLinus Torvalds __rb_rotate_left(other, root); 2031da177e4SLinus Torvalds other = parent->rb_left; 2041da177e4SLinus Torvalds } 2052f3243aeSDavid Woodhouse rb_set_color(other, rb_color(parent)); 20655a98102SDavid Woodhouse rb_set_black(parent); 20755a98102SDavid Woodhouse rb_set_black(other->rb_left); 2081da177e4SLinus Torvalds __rb_rotate_right(parent, root); 2091da177e4SLinus Torvalds node = root->rb_node; 2101da177e4SLinus Torvalds break; 2111da177e4SLinus Torvalds } 2121da177e4SLinus Torvalds } 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds if (node) 21555a98102SDavid Woodhouse rb_set_black(node); 2161da177e4SLinus Torvalds } 2171da177e4SLinus Torvalds 2181da177e4SLinus Torvalds void rb_erase(struct rb_node *node, struct rb_root *root) 2191da177e4SLinus Torvalds { 2201da177e4SLinus Torvalds struct rb_node *child, *parent; 2211da177e4SLinus Torvalds int color; 2221da177e4SLinus Torvalds 2231da177e4SLinus Torvalds if (!node->rb_left) 2241da177e4SLinus Torvalds child = node->rb_right; 2251da177e4SLinus Torvalds else if (!node->rb_right) 2261da177e4SLinus Torvalds child = node->rb_left; 2271da177e4SLinus Torvalds else 2281da177e4SLinus Torvalds { 2291da177e4SLinus Torvalds struct rb_node *old = node, *left; 2301da177e4SLinus Torvalds 2311da177e4SLinus Torvalds node = node->rb_right; 2321da177e4SLinus Torvalds while ((left = node->rb_left) != NULL) 2331da177e4SLinus Torvalds node = left; 23416c047adSWolfram Strepp 23516c047adSWolfram Strepp if (rb_parent(old)) { 23616c047adSWolfram Strepp if (rb_parent(old)->rb_left == old) 23716c047adSWolfram Strepp rb_parent(old)->rb_left = node; 23816c047adSWolfram Strepp else 23916c047adSWolfram Strepp rb_parent(old)->rb_right = node; 24016c047adSWolfram Strepp } else 24116c047adSWolfram Strepp root->rb_node = node; 24216c047adSWolfram Strepp 2431da177e4SLinus Torvalds child = node->rb_right; 24455a98102SDavid Woodhouse parent = rb_parent(node); 2452f3243aeSDavid Woodhouse color = rb_color(node); 2461da177e4SLinus Torvalds 247*4c601178SWolfram Strepp if (parent == old) { 248*4c601178SWolfram Strepp parent = node; 249*4c601178SWolfram Strepp } else { 2501da177e4SLinus Torvalds if (child) 25155a98102SDavid Woodhouse rb_set_parent(child, parent); 2521975e593SDavid Woodhouse parent->rb_left = child; 253*4c601178SWolfram Strepp } 2541975e593SDavid Woodhouse 2552f3243aeSDavid Woodhouse node->rb_parent_color = old->rb_parent_color; 2561da177e4SLinus Torvalds node->rb_right = old->rb_right; 2571da177e4SLinus Torvalds node->rb_left = old->rb_left; 2581da177e4SLinus Torvalds 25955a98102SDavid Woodhouse rb_set_parent(old->rb_left, node); 2601da177e4SLinus Torvalds if (old->rb_right) 26155a98102SDavid Woodhouse rb_set_parent(old->rb_right, node); 2621da177e4SLinus Torvalds goto color; 2631da177e4SLinus Torvalds } 2641da177e4SLinus Torvalds 26555a98102SDavid Woodhouse parent = rb_parent(node); 2662f3243aeSDavid Woodhouse color = rb_color(node); 2671da177e4SLinus Torvalds 2681da177e4SLinus Torvalds if (child) 26955a98102SDavid Woodhouse rb_set_parent(child, parent); 2701da177e4SLinus Torvalds if (parent) 2711da177e4SLinus Torvalds { 2721da177e4SLinus Torvalds if (parent->rb_left == node) 2731da177e4SLinus Torvalds parent->rb_left = child; 2741da177e4SLinus Torvalds else 2751da177e4SLinus Torvalds parent->rb_right = child; 2761da177e4SLinus Torvalds } 2771da177e4SLinus Torvalds else 2781da177e4SLinus Torvalds root->rb_node = child; 2791da177e4SLinus Torvalds 2801da177e4SLinus Torvalds color: 2811da177e4SLinus Torvalds if (color == RB_BLACK) 2821da177e4SLinus Torvalds __rb_erase_color(child, parent, root); 2831da177e4SLinus Torvalds } 2841da177e4SLinus Torvalds EXPORT_SYMBOL(rb_erase); 2851da177e4SLinus Torvalds 2861da177e4SLinus Torvalds /* 2871da177e4SLinus Torvalds * This function returns the first node (in sort order) of the tree. 2881da177e4SLinus Torvalds */ 289f4b477c4SArtem Bityutskiy struct rb_node *rb_first(const struct rb_root *root) 2901da177e4SLinus Torvalds { 2911da177e4SLinus Torvalds struct rb_node *n; 2921da177e4SLinus Torvalds 2931da177e4SLinus Torvalds n = root->rb_node; 2941da177e4SLinus Torvalds if (!n) 2951da177e4SLinus Torvalds return NULL; 2961da177e4SLinus Torvalds while (n->rb_left) 2971da177e4SLinus Torvalds n = n->rb_left; 2981da177e4SLinus Torvalds return n; 2991da177e4SLinus Torvalds } 3001da177e4SLinus Torvalds EXPORT_SYMBOL(rb_first); 3011da177e4SLinus Torvalds 302f4b477c4SArtem Bityutskiy struct rb_node *rb_last(const struct rb_root *root) 3031da177e4SLinus Torvalds { 3041da177e4SLinus Torvalds struct rb_node *n; 3051da177e4SLinus Torvalds 3061da177e4SLinus Torvalds n = root->rb_node; 3071da177e4SLinus Torvalds if (!n) 3081da177e4SLinus Torvalds return NULL; 3091da177e4SLinus Torvalds while (n->rb_right) 3101da177e4SLinus Torvalds n = n->rb_right; 3111da177e4SLinus Torvalds return n; 3121da177e4SLinus Torvalds } 3131da177e4SLinus Torvalds EXPORT_SYMBOL(rb_last); 3141da177e4SLinus Torvalds 315f4b477c4SArtem Bityutskiy struct rb_node *rb_next(const struct rb_node *node) 3161da177e4SLinus Torvalds { 31755a98102SDavid Woodhouse struct rb_node *parent; 31855a98102SDavid Woodhouse 31910fd48f2SJens Axboe if (rb_parent(node) == node) 32010fd48f2SJens Axboe return NULL; 32110fd48f2SJens Axboe 3221da177e4SLinus Torvalds /* If we have a right-hand child, go down and then left as far 3231da177e4SLinus Torvalds as we can. */ 3241da177e4SLinus Torvalds if (node->rb_right) { 3251da177e4SLinus Torvalds node = node->rb_right; 3261da177e4SLinus Torvalds while (node->rb_left) 3271da177e4SLinus Torvalds node=node->rb_left; 328f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 3291da177e4SLinus Torvalds } 3301da177e4SLinus Torvalds 3311da177e4SLinus Torvalds /* No right-hand children. Everything down and left is 3321da177e4SLinus Torvalds smaller than us, so any 'next' node must be in the general 3331da177e4SLinus Torvalds direction of our parent. Go up the tree; any time the 3341da177e4SLinus Torvalds ancestor is a right-hand child of its parent, keep going 3351da177e4SLinus Torvalds up. First time it's a left-hand child of its parent, said 3361da177e4SLinus Torvalds parent is our 'next' node. */ 33755a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_right) 33855a98102SDavid Woodhouse node = parent; 3391da177e4SLinus Torvalds 34055a98102SDavid Woodhouse return parent; 3411da177e4SLinus Torvalds } 3421da177e4SLinus Torvalds EXPORT_SYMBOL(rb_next); 3431da177e4SLinus Torvalds 344f4b477c4SArtem Bityutskiy struct rb_node *rb_prev(const struct rb_node *node) 3451da177e4SLinus Torvalds { 34655a98102SDavid Woodhouse struct rb_node *parent; 34755a98102SDavid Woodhouse 34810fd48f2SJens Axboe if (rb_parent(node) == node) 34910fd48f2SJens Axboe return NULL; 35010fd48f2SJens Axboe 3511da177e4SLinus Torvalds /* If we have a left-hand child, go down and then right as far 3521da177e4SLinus Torvalds as we can. */ 3531da177e4SLinus Torvalds if (node->rb_left) { 3541da177e4SLinus Torvalds node = node->rb_left; 3551da177e4SLinus Torvalds while (node->rb_right) 3561da177e4SLinus Torvalds node=node->rb_right; 357f4b477c4SArtem Bityutskiy return (struct rb_node *)node; 3581da177e4SLinus Torvalds } 3591da177e4SLinus Torvalds 3601da177e4SLinus Torvalds /* No left-hand children. Go up till we find an ancestor which 3611da177e4SLinus Torvalds is a right-hand child of its parent */ 36255a98102SDavid Woodhouse while ((parent = rb_parent(node)) && node == parent->rb_left) 36355a98102SDavid Woodhouse node = parent; 3641da177e4SLinus Torvalds 36555a98102SDavid Woodhouse return parent; 3661da177e4SLinus Torvalds } 3671da177e4SLinus Torvalds EXPORT_SYMBOL(rb_prev); 3681da177e4SLinus Torvalds 3691da177e4SLinus Torvalds void rb_replace_node(struct rb_node *victim, struct rb_node *new, 3701da177e4SLinus Torvalds struct rb_root *root) 3711da177e4SLinus Torvalds { 37255a98102SDavid Woodhouse struct rb_node *parent = rb_parent(victim); 3731da177e4SLinus Torvalds 3741da177e4SLinus Torvalds /* Set the surrounding nodes to point to the replacement */ 3751da177e4SLinus Torvalds if (parent) { 3761da177e4SLinus Torvalds if (victim == parent->rb_left) 3771da177e4SLinus Torvalds parent->rb_left = new; 3781da177e4SLinus Torvalds else 3791da177e4SLinus Torvalds parent->rb_right = new; 3801da177e4SLinus Torvalds } else { 3811da177e4SLinus Torvalds root->rb_node = new; 3821da177e4SLinus Torvalds } 3831da177e4SLinus Torvalds if (victim->rb_left) 38455a98102SDavid Woodhouse rb_set_parent(victim->rb_left, new); 3851da177e4SLinus Torvalds if (victim->rb_right) 38655a98102SDavid Woodhouse rb_set_parent(victim->rb_right, new); 3871da177e4SLinus Torvalds 3881da177e4SLinus Torvalds /* Copy the pointers/colour from the victim to the replacement */ 3891da177e4SLinus Torvalds *new = *victim; 3901da177e4SLinus Torvalds } 3911da177e4SLinus Torvalds EXPORT_SYMBOL(rb_replace_node); 392