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 <bilbyfs.h> 33 34static inline void rbt_init_node(struct rbt_node *rb) 35{ 36 rb->rbt_parent_color = 0; 37 rb->rbt_right = NULL; 38 rb->rbt_left = NULL; 39 RBT_CLEAR_NODE(rb); 40} 41 42void rbt_link_node(struct rbt_node * node, struct rbt_node * parent, 43 struct rbt_node ** rbt_link) 44{ 45 node->rbt_parent_color = (unsigned long )parent; 46 node->rbt_left = NULL; 47 node->rbt_right = NULL; 48 *rbt_link = node; 49} 50 51static void __rbt_rotate_left(struct rbt_node *node, struct rbt_root *root) 52{ 53 struct rbt_node *right = node->rbt_right; 54 struct rbt_node *parent = rbt_parent(node); 55 56 node->rbt_right = right->rbt_left; 57 if (node->rbt_right) 58 rbt_set_parent(right->rbt_left, node); 59 right->rbt_left = node; 60 61 rbt_set_parent(right, parent); 62 63 if (parent) 64 { 65 if (node == parent->rbt_left) 66 parent->rbt_left = right; 67 else 68 parent->rbt_right = right; 69 } 70 else 71 root->rbt_node = right; 72 rbt_set_parent(node, right); 73} 74 75static void __rbt_rotate_right(struct rbt_node *node, struct rbt_root *root) 76{ 77 struct rbt_node *left = node->rbt_left; 78 struct rbt_node *parent = rbt_parent(node); 79 80 node->rbt_left = left->rbt_right; 81 if (node->rbt_left) 82 rbt_set_parent(left->rbt_right, node); 83 left->rbt_right = node; 84 85 rbt_set_parent(left, parent); 86 87 if (parent) 88 { 89 if (node == parent->rbt_right) 90 parent->rbt_right = left; 91 else 92 parent->rbt_left = left; 93 } 94 else 95 root->rbt_node = left; 96 rbt_set_parent(node, left); 97} 98 99void rbt_insert_color(struct rbt_node *node, struct rbt_root *root) 100{ 101 struct rbt_node *parent, *gparent; 102 103 for (parent = rbt_parent(node); parent && rbt_is_red(parent); parent = rbt_parent(node)) 104 { 105 gparent = rbt_parent(parent); 106 107 if (parent == gparent->rbt_left) 108 { 109 { 110 register struct rbt_node *uncle = gparent->rbt_right; 111 if (uncle && rbt_is_red(uncle)) 112 { 113 rbt_set_black(uncle); 114 rbt_set_black(parent); 115 rbt_set_red(gparent); 116 node = gparent; 117 continue; 118 } 119 } 120 121 if (parent->rbt_right == node) 122 { 123 register struct rbt_node *tmp; 124 __rbt_rotate_left(parent, root); 125 tmp = parent; 126 parent = node; 127 node = tmp; 128 } 129 130 rbt_set_black(parent); 131 rbt_set_red(gparent); 132 __rbt_rotate_right(gparent, root); 133 } else { 134 { 135 register struct rbt_node *uncle = gparent->rbt_left; 136 if (uncle && rbt_is_red(uncle)) 137 { 138 rbt_set_black(uncle); 139 rbt_set_black(parent); 140 rbt_set_red(gparent); 141 node = gparent; 142 continue; 143 } 144 } 145 146 if (parent->rbt_left == node) 147 { 148 register struct rbt_node *tmp; 149 __rbt_rotate_right(parent, root); 150 tmp = parent; 151 parent = node; 152 node = tmp; 153 } 154 155 rbt_set_black(parent); 156 rbt_set_red(gparent); 157 __rbt_rotate_left(gparent, root); 158 } 159 } 160 161 rbt_set_black(root->rbt_node); 162} 163 164static void __rbt_erase_color(struct rbt_node *node, struct rbt_node *parent, 165 struct rbt_root *root) 166{ 167 struct rbt_node *other; 168 169 while ((!node || rbt_is_black(node)) && node != root->rbt_node) 170 { 171 if (parent->rbt_left == node) 172 { 173 other = parent->rbt_right; 174 if (rbt_is_red(other)) 175 { 176 rbt_set_black(other); 177 rbt_set_red(parent); 178 __rbt_rotate_left(parent, root); 179 other = parent->rbt_right; 180 } 181 if ((!other->rbt_left || rbt_is_black(other->rbt_left)) && 182 (!other->rbt_right || rbt_is_black(other->rbt_right))) 183 { 184 rbt_set_red(other); 185 node = parent; 186 parent = rbt_parent(node); 187 } 188 else 189 { 190 if (!other->rbt_right || rbt_is_black(other->rbt_right)) 191 { 192 rbt_set_black(other->rbt_left); 193 rbt_set_red(other); 194 __rbt_rotate_right(other, root); 195 other = parent->rbt_right; 196 } 197 rbt_set_color(other, rbt_color(parent)); 198 rbt_set_black(parent); 199 rbt_set_black(other->rbt_right); 200 __rbt_rotate_left(parent, root); 201 node = root->rbt_node; 202 break; 203 } 204 } 205 else 206 { 207 other = parent->rbt_left; 208 if (rbt_is_red(other)) 209 { 210 rbt_set_black(other); 211 rbt_set_red(parent); 212 __rbt_rotate_right(parent, root); 213 other = parent->rbt_left; 214 } 215 if ((!other->rbt_left || rbt_is_black(other->rbt_left)) && 216 (!other->rbt_right || rbt_is_black(other->rbt_right))) 217 { 218 rbt_set_red(other); 219 node = parent; 220 parent = rbt_parent(node); 221 } 222 else 223 { 224 if (!other->rbt_left || rbt_is_black(other->rbt_left)) 225 { 226 rbt_set_black(other->rbt_right); 227 rbt_set_red(other); 228 __rbt_rotate_left(other, root); 229 other = parent->rbt_left; 230 } 231 rbt_set_color(other, rbt_color(parent)); 232 rbt_set_black(parent); 233 rbt_set_black(other->rbt_left); 234 __rbt_rotate_right(parent, root); 235 node = root->rbt_node; 236 break; 237 } 238 } 239 } 240 if (node) 241 rbt_set_black(node); 242} 243 244void rbt_erase(struct rbt_node *node, struct rbt_root *root) 245{ 246 struct rbt_node *child, *parent; 247 int color; 248 249 if (!node->rbt_left) 250 child = node->rbt_right; 251 else if (!node->rbt_right) 252 child = node->rbt_left; 253 else 254 { 255 struct rbt_node *old = node, *left; 256 257 node = node->rbt_right; 258 for (left = node->rbt_left; left != NULL; left = node->rbt_left) 259 node = left; 260 261 if (rbt_parent(old)) { 262 if (rbt_parent(old)->rbt_left == old) 263 rbt_parent(old)->rbt_left = node; 264 else 265 rbt_parent(old)->rbt_right = node; 266 } else 267 root->rbt_node = node; 268 269 child = node->rbt_right; 270 parent = rbt_parent(node); 271 color = rbt_color(node); 272 273 if (parent == old) { 274 parent = node; 275 } else { 276 if (child) 277 rbt_set_parent(child, parent); 278 parent->rbt_left = child; 279 280 node->rbt_right = old->rbt_right; 281 rbt_set_parent(old->rbt_right, node); 282 } 283 284 node->rbt_parent_color = old->rbt_parent_color; 285 node->rbt_left = old->rbt_left; 286 rbt_set_parent(old->rbt_left, node); 287 288 if (color == RBT_BLACK) 289 __rbt_erase_color(child, parent, root); 290 return; 291 } 292 293 parent = rbt_parent(node); 294 color = rbt_color(node); 295 296 if (child) 297 rbt_set_parent(child, parent); 298 if (parent) 299 { 300 if (parent->rbt_left == node) 301 parent->rbt_left = child; 302 else 303 parent->rbt_right = child; 304 } 305 else 306 root->rbt_node = child; 307 308 if (color == RBT_BLACK) 309 __rbt_erase_color(child, parent, root); 310} 311 312/* 313 * This function returns the first node (in sort order) of the tree. 314 */ 315struct rbt_node *rbt_first(const struct rbt_root *root) 316{ 317 struct rbt_node *n; 318 319 n = root->rbt_node; 320 if (!n) 321 return NULL; 322 while (n->rbt_left) 323 n = n->rbt_left; 324 return n; 325} 326 327struct rbt_node *rbt_last(const struct rbt_root *root) 328{ 329 struct rbt_node *n; 330 331 n = root->rbt_node; 332 if (!n) 333 return NULL; 334 while (n->rbt_right) 335 n = n->rbt_right; 336 return n; 337} 338 339struct rbt_node *rbt_next(const struct rbt_node *node) 340{ 341 struct rbt_node *parent; 342 343 if (rbt_parent(node) == node) 344 return NULL; 345 346 /* If we have a right-hand child, go down and then left as far 347 as we can. */ 348 if (node->rbt_right) { 349 node = node->rbt_right; 350 while (node->rbt_left) 351 node=node->rbt_left; 352 return (struct rbt_node *)node; 353 } 354 355 /* No right-hand children. Everything down and left is 356 smaller than us, so any 'next' node must be in the general 357 direction of our parent. Go up the tree; any time the 358 ancestor is a right-hand child of its parent, keep going 359 up. First time it's a left-hand child of its parent, said 360 parent is our 'next' node. */ 361 for (parent = rbt_parent(node); parent && node == parent->rbt_right; parent = rbt_parent(node)) 362 node = parent; 363 364 return parent; 365} 366 367struct rbt_node *rbt_prev(const struct rbt_node *node) 368{ 369 struct rbt_node *parent; 370 371 if (rbt_parent(node) == node) 372 return NULL; 373 374 /* If we have a left-hand child, go down and then right as far 375 as we can. */ 376 if (node->rbt_left) { 377 node = node->rbt_left; 378 while (node->rbt_right) 379 node=node->rbt_right; 380 return (struct rbt_node *)node; 381 } 382 383 /* No left-hand children. Go up till we find an ancestor which 384 is a right-hand child of its parent */ 385 for (parent = rbt_parent(node); parent && node == parent->rbt_left; parent = rbt_parent(node)) 386 node = parent; 387 388 return parent; 389} 390 391void rbt_replace_node(struct rbt_node *victim, struct rbt_node *new, 392 struct rbt_root *root) 393{ 394 struct rbt_node *parent = rbt_parent(victim); 395 396 /* Set the surrounding nodes to point to the replacement */ 397 if (parent) { 398 if (victim == parent->rbt_left) 399 parent->rbt_left = new; 400 else 401 parent->rbt_right = new; 402 } else { 403 root->rbt_node = new; 404 } 405 if (victim->rbt_left) 406 rbt_set_parent(victim->rbt_left, new); 407 if (victim->rbt_right) 408 rbt_set_parent(victim->rbt_right, new); 409 410 /* Copy the pointers/colour from the victim to the replacement */ 411 *new = *victim; 412} 413