1/* 2 * Copyright 2016, NICTA 3 * 4 * This software may be distributed and modified according to the terms of 5 * the GNU General Public License version 2. Note that NO WARRANTY is provided. 6 * See "LICENSE_GPLv2.txt" for details. 7 * 8 * @TAG(NICTA_GPL) 9 */ 10 11/* 12 Red Black Trees 13 (C) 1999 Andrea Arcangeli <andrea@suse.de> 14 (C) 2002 David Woodhouse <dwmw2@infradead.org> 15 16 This program is free software; you can redistribute it and/or modify 17 it under the terms of the GNU General Public License as published by 18 the Free Software Foundation; either version 2 of the License, or 19 (at your option) any later version. 20 21 This program is distributed in the hope that it will be useful, 22 but WITHOUT ANY WARRANTY; without even the implied warranty of 23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 GNU General Public License for more details. 25 26 You should have received a copy of the GNU General Public License 27 along with this program; if not, write to the Free Software 28 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 29 30*/ 31 32#include <lib/rbt.h> 33 34void rbt_link_node(struct rbt_node * node, struct rbt_node * parent, 35 struct rbt_node ** rbt_link) 36{ 37 node->rbt_parent_color = (unsigned long )parent; 38 node->rbt_left = NULL; 39 node->rbt_right = NULL; 40 *rbt_link = node; 41} 42 43static void __rbt_rotate_left(struct rbt_node *node, struct rbt_root *rbt) 44{ 45 struct rbt_node *right = node->rbt_right; 46 struct rbt_node *parent = rbt_parent(node); 47 48 node->rbt_right = right->rbt_left; 49 if (node->rbt_right) 50 rbt_set_parent(right->rbt_left, node); 51 right->rbt_left = node; 52 53 rbt_set_parent(right, parent); 54 55 if (parent) 56 { 57 if (node == parent->rbt_left) 58 parent->rbt_left = right; 59 else 60 parent->rbt_right = right; 61 } 62 else 63 rbt->root = right; 64 rbt_set_parent(node, right); 65} 66 67static void __rbt_rotate_right(struct rbt_node *node, struct rbt_root *rbt) 68{ 69 struct rbt_node *left = node->rbt_left; 70 struct rbt_node *parent = rbt_parent(node); 71 72 node->rbt_left = left->rbt_right; 73 if (node->rbt_left) 74 rbt_set_parent(left->rbt_right, node); 75 left->rbt_right = node; 76 77 rbt_set_parent(left, parent); 78 79 if (parent) 80 { 81 if (node == parent->rbt_right) 82 parent->rbt_right = left; 83 else 84 parent->rbt_left = left; 85 } 86 else 87 rbt->root = left; 88 rbt_set_parent(node, left); 89} 90 91void rbt_insert_color(struct rbt_node *node, struct rbt_root *rbt) 92{ 93 struct rbt_node *parent, *gparent; 94 95 for (parent = rbt_parent(node); parent && rbt_is_red(parent); parent = rbt_parent(node)) 96 { 97 gparent = rbt_parent(parent); 98 99 if (parent == gparent->rbt_left) 100 { 101 { 102 register struct rbt_node *uncle = gparent->rbt_right; 103 if (uncle && rbt_is_red(uncle)) 104 { 105 rbt_set_black(uncle); 106 rbt_set_black(parent); 107 rbt_set_red(gparent); 108 node = gparent; 109 continue; 110 } 111 } 112 113 if (parent->rbt_right == node) 114 { 115 register struct rbt_node *tmp; 116 __rbt_rotate_left(parent, rbt); 117 tmp = parent; 118 parent = node; 119 node = tmp; 120 } 121 122 rbt_set_black(parent); 123 rbt_set_red(gparent); 124 __rbt_rotate_right(gparent, rbt); 125 } else { 126 { 127 register struct rbt_node *uncle = gparent->rbt_left; 128 if (uncle && rbt_is_red(uncle)) 129 { 130 rbt_set_black(uncle); 131 rbt_set_black(parent); 132 rbt_set_red(gparent); 133 node = gparent; 134 continue; 135 } 136 } 137 138 if (parent->rbt_left == node) 139 { 140 register struct rbt_node *tmp; 141 __rbt_rotate_right(parent, rbt); 142 tmp = parent; 143 parent = node; 144 node = tmp; 145 } 146 147 rbt_set_black(parent); 148 rbt_set_red(gparent); 149 __rbt_rotate_left(gparent, rbt); 150 } 151 } 152 153 rbt_set_black(rbt->root); 154} 155 156static void __rbt_erase_color(struct rbt_node *node, struct rbt_node *parent, 157 struct rbt_root *rbt) 158{ 159 struct rbt_node *other; 160 161 while ((!node || rbt_is_black(node)) && node != rbt->root) 162 { 163 if (parent->rbt_left == node) 164 { 165 other = parent->rbt_right; 166 if (rbt_is_red(other)) 167 { 168 rbt_set_black(other); 169 rbt_set_red(parent); 170 __rbt_rotate_left(parent, rbt); 171 other = parent->rbt_right; 172 } 173 if ((!other->rbt_left || rbt_is_black(other->rbt_left)) && 174 (!other->rbt_right || rbt_is_black(other->rbt_right))) 175 { 176 rbt_set_red(other); 177 node = parent; 178 parent = rbt_parent(node); 179 } 180 else 181 { 182 if (!other->rbt_right || rbt_is_black(other->rbt_right)) 183 { 184 rbt_set_black(other->rbt_left); 185 rbt_set_red(other); 186 __rbt_rotate_right(other, rbt); 187 other = parent->rbt_right; 188 } 189 rbt_set_color(other, rbt_color(parent)); 190 rbt_set_black(parent); 191 rbt_set_black(other->rbt_right); 192 __rbt_rotate_left(parent, rbt); 193 node = rbt->root; 194 break; 195 } 196 } 197 else 198 { 199 other = parent->rbt_left; 200 if (rbt_is_red(other)) 201 { 202 rbt_set_black(other); 203 rbt_set_red(parent); 204 __rbt_rotate_right(parent, rbt); 205 other = parent->rbt_left; 206 } 207 if ((!other->rbt_left || rbt_is_black(other->rbt_left)) && 208 (!other->rbt_right || rbt_is_black(other->rbt_right))) 209 { 210 rbt_set_red(other); 211 node = parent; 212 parent = rbt_parent(node); 213 } 214 else 215 { 216 if (!other->rbt_left || rbt_is_black(other->rbt_left)) 217 { 218 rbt_set_black(other->rbt_right); 219 rbt_set_red(other); 220 __rbt_rotate_left(other, rbt); 221 other = parent->rbt_left; 222 } 223 rbt_set_color(other, rbt_color(parent)); 224 rbt_set_black(parent); 225 rbt_set_black(other->rbt_left); 226 __rbt_rotate_right(parent, rbt); 227 node = rbt->root; 228 break; 229 } 230 } 231 } 232 if (node) 233 rbt_set_black(node); 234} 235 236void rbt_erase(struct rbt_node *node, struct rbt_root *rbt) 237{ 238 struct rbt_node *child, *parent; 239 int color; 240 241 if (!node->rbt_left) 242 child = node->rbt_right; 243 else if (!node->rbt_right) 244 child = node->rbt_left; 245 else 246 { 247 struct rbt_node *old = node, *left; 248 249 node = node->rbt_right; 250 for (left = node->rbt_left; left != NULL; left = node->rbt_left) 251 node = left; 252 253 if (rbt_parent(old)) { 254 if (rbt_parent(old)->rbt_left == old) 255 rbt_parent(old)->rbt_left = node; 256 else 257 rbt_parent(old)->rbt_right = node; 258 } else 259 rbt->root = node; 260 261 child = node->rbt_right; 262 parent = rbt_parent(node); 263 color = rbt_color(node); 264 265 if (parent == old) { 266 parent = node; 267 } else { 268 if (child) 269 rbt_set_parent(child, parent); 270 parent->rbt_left = child; 271 272 node->rbt_right = old->rbt_right; 273 rbt_set_parent(old->rbt_right, node); 274 } 275 276 node->rbt_parent_color = old->rbt_parent_color; 277 node->rbt_left = old->rbt_left; 278 rbt_set_parent(old->rbt_left, node); 279 280 if (color == RBT_BLACK) 281 __rbt_erase_color(child, parent, rbt); 282 return; 283 } 284 285 parent = rbt_parent(node); 286 color = rbt_color(node); 287 288 if (child) 289 rbt_set_parent(child, parent); 290 if (parent) 291 { 292 if (parent->rbt_left == node) 293 parent->rbt_left = child; 294 else 295 parent->rbt_right = child; 296 } 297 else 298 rbt->root = child; 299 300 if (color == RBT_BLACK) 301 __rbt_erase_color(child, parent, rbt); 302} 303