1 /*======================================================================== 2 // 3 // rbtree.c 4 // 5 // Red Black tree implementation 6 // 7 //======================================================================== 8 // ####ECOSGPLCOPYRIGHTBEGIN#### 9 // ------------------------------------------- 10 // This file is part of eCos, the Embedded Configurable Operating System. 11 // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc. 12 // 13 // eCos is free software; you can redistribute it and/or modify it under 14 // the terms of the GNU General Public License as published by the Free 15 // Software Foundation; either version 2 or (at your option) any later 16 // version. 17 // 18 // eCos is distributed in the hope that it will be useful, but WITHOUT 19 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 20 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 21 // for more details. 22 // 23 // You should have received a copy of the GNU General Public License 24 // along with eCos; if not, write to the Free Software Foundation, Inc., 25 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 26 // 27 // As a special exception, if other files instantiate templates or use 28 // macros or inline functions from this file, or you compile this file 29 // and link it with other works to produce a work based on this file, 30 // this file does not by itself cause the resulting work to be covered by 31 // the GNU General Public License. However the source code for this file 32 // must still be made available in accordance with section (3) of the GNU 33 // General Public License v2. 34 // 35 // This exception does not invalidate any other reasons why a work based 36 // on this file might be covered by the GNU General Public License. 37 // ------------------------------------------- 38 // ####ECOSGPLCOPYRIGHTEND#### 39 //======================================================================== 40 //#####DESCRIPTIONBEGIN#### 41 // 42 // Author(s): Niels Provos/OpenBSD 43 // Contributors: dwmw2 44 // Date: 2003-01-21 45 // Purpose: This file provides an implementation of red-black trees. 46 // Description: Derived from OpenBSD src/sys/sys/tree.h 47 // Usage: 48 // 49 //####DESCRIPTIONEND#### 50 // 51 //====================================================================== 52 */ 53 54 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 55 /* 56 * Copyright 2002 Niels Provos <[email protected]> 57 * All rights reserved. 58 * 59 * Redistribution and use in source and binary forms, with or without 60 * modification, are permitted provided that the following conditions 61 * are met: 62 * 1. Redistributions of source code must retain the above copyright 63 * notice, this list of conditions and the following disclaimer. 64 * 2. Redistributions in binary form must reproduce the above copyright 65 * notice, this list of conditions and the following disclaimer in the 66 * documentation and/or other materials provided with the distribution. 67 * 68 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 69 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 70 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 71 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 72 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 73 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 74 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 75 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 76 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 77 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 78 */ 79 80 /* Fields renamed to match Linux ones. */ 81 #include <linux/rbtree.h> 82 83 84 #define RB_HEAD(head) (head)->rb_node 85 #define RB_LEFT(elm) (elm)->rb_left 86 #define RB_RIGHT(elm) (elm)->rb_right 87 #define RB_PARENT(elm) (elm)->rb_parent 88 #define RB_COLOR(elm) (elm)->rb_color 89 90 91 #define RB_SET(elm, parent) do { \ 92 RB_PARENT(elm) = parent; \ 93 RB_LEFT(elm) = RB_RIGHT(elm) = NULL; \ 94 RB_COLOR(elm) = RB_RED; \ 95 } while (0) 96 97 #define RB_SET_BLACKRED(black, red) do { \ 98 RB_COLOR(black) = RB_BLACK; \ 99 RB_COLOR(red) = RB_RED; \ 100 } while (0) 101 102 #ifndef RB_AUGMENT 103 #define RB_AUGMENT(x) 104 #endif 105 106 #define RB_ROTATE_LEFT(head, elm, tmp) do { \ 107 (tmp) = RB_RIGHT(elm); \ 108 if ((RB_RIGHT(elm) = RB_LEFT(tmp))) { \ 109 RB_PARENT(RB_LEFT(tmp)) = (elm); \ 110 } \ 111 RB_AUGMENT(elm); \ 112 if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \ 113 if ((elm) == RB_LEFT(RB_PARENT(elm))) \ 114 RB_LEFT(RB_PARENT(elm)) = (tmp); \ 115 else \ 116 RB_RIGHT(RB_PARENT(elm)) = (tmp); \ 117 } else \ 118 (head)->rb_node = (tmp); \ 119 RB_LEFT(tmp) = (elm); \ 120 RB_PARENT(elm) = (tmp); \ 121 RB_AUGMENT(tmp); \ 122 if ((RB_PARENT(tmp))) \ 123 RB_AUGMENT(RB_PARENT(tmp)); \ 124 } while (0) 125 126 #define RB_ROTATE_RIGHT(head, elm, tmp) do { \ 127 (tmp) = RB_LEFT(elm); \ 128 if ((RB_LEFT(elm) = RB_RIGHT(tmp))) { \ 129 RB_PARENT(RB_RIGHT(tmp)) = (elm); \ 130 } \ 131 RB_AUGMENT(elm); \ 132 if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \ 133 if ((elm) == RB_LEFT(RB_PARENT(elm))) \ 134 RB_LEFT(RB_PARENT(elm)) = (tmp); \ 135 else \ 136 RB_RIGHT(RB_PARENT(elm)) = (tmp); \ 137 } else \ 138 (head)->rb_node = (tmp); \ 139 RB_RIGHT(tmp) = (elm); \ 140 RB_PARENT(elm) = (tmp); \ 141 RB_AUGMENT(tmp); \ 142 if ((RB_PARENT(tmp))) \ 143 RB_AUGMENT(RB_PARENT(tmp)); \ 144 } while(0) 145 146 /* Note args swapped to match Linux */ 147 void rb_insert_color(struct rb_node *elm, struct rb_root *head) 148 { 149 struct rb_node *parent, *gparent, *tmp; 150 while ((parent = RB_PARENT(elm)) && 151 RB_COLOR(parent) == RB_RED) { 152 gparent = RB_PARENT(parent); 153 if (parent == RB_LEFT(gparent)) { 154 tmp = RB_RIGHT(gparent); 155 if (tmp && RB_COLOR(tmp) == RB_RED) { 156 RB_COLOR(tmp) = RB_BLACK; 157 RB_SET_BLACKRED(parent, gparent); 158 elm = gparent; 159 continue; 160 } 161 if (RB_RIGHT(parent) == elm) { 162 RB_ROTATE_LEFT(head, parent, tmp); 163 tmp = parent; 164 parent = elm; 165 elm = tmp; 166 } 167 RB_SET_BLACKRED(parent, gparent); 168 RB_ROTATE_RIGHT(head, gparent, tmp); 169 } else { 170 tmp = RB_LEFT(gparent); 171 if (tmp && RB_COLOR(tmp) == RB_RED) { 172 RB_COLOR(tmp) = RB_BLACK; 173 RB_SET_BLACKRED(parent, gparent); 174 elm = gparent; 175 continue; 176 } 177 if (RB_LEFT(parent) == elm) { 178 RB_ROTATE_RIGHT(head, parent, tmp); 179 tmp = parent; 180 parent = elm; 181 elm = tmp; 182 } 183 RB_SET_BLACKRED(parent, gparent); 184 RB_ROTATE_LEFT(head, gparent, tmp); 185 } 186 } 187 RB_COLOR(head->rb_node) = RB_BLACK; 188 } 189 190 191 static void rb_remove_color(struct rb_root *head, struct rb_node *parent, 192 struct rb_node *elm) 193 { 194 struct rb_node *tmp; 195 while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) && 196 elm != RB_HEAD(head)) { 197 if (RB_LEFT(parent) == elm) { 198 tmp = RB_RIGHT(parent); 199 if (RB_COLOR(tmp) == RB_RED) { 200 RB_SET_BLACKRED(tmp, parent); 201 RB_ROTATE_LEFT(head, parent, tmp); 202 tmp = RB_RIGHT(parent); 203 } 204 if ((RB_LEFT(tmp) == NULL || 205 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) && 206 (RB_RIGHT(tmp) == NULL || 207 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) { 208 RB_COLOR(tmp) = RB_RED; 209 elm = parent; 210 parent = RB_PARENT(elm); 211 } else { 212 if (RB_RIGHT(tmp) == NULL || 213 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) { 214 struct rb_node *oleft; 215 if ((oleft = RB_LEFT(tmp))) 216 RB_COLOR(oleft) = RB_BLACK; 217 RB_COLOR(tmp) = RB_RED; 218 RB_ROTATE_RIGHT(head, tmp, oleft); 219 tmp = RB_RIGHT(parent); 220 } 221 RB_COLOR(tmp) = RB_COLOR(parent); 222 RB_COLOR(parent) = RB_BLACK; 223 if (RB_RIGHT(tmp)) 224 RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK; 225 RB_ROTATE_LEFT(head, parent, tmp); 226 elm = RB_HEAD(head); 227 break; 228 } 229 } else { 230 tmp = RB_LEFT(parent); 231 if (RB_COLOR(tmp) == RB_RED) { 232 RB_SET_BLACKRED(tmp, parent); 233 RB_ROTATE_RIGHT(head, parent, tmp); 234 tmp = RB_LEFT(parent); 235 } 236 if ((RB_LEFT(tmp) == NULL || 237 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) && 238 (RB_RIGHT(tmp) == NULL || 239 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) { 240 RB_COLOR(tmp) = RB_RED; 241 elm = parent; 242 parent = RB_PARENT(elm); 243 } else { 244 if (RB_LEFT(tmp) == NULL || 245 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) { 246 struct rb_node *oright; 247 if ((oright = RB_RIGHT(tmp))) 248 RB_COLOR(oright) = RB_BLACK; 249 RB_COLOR(tmp) = RB_RED; 250 RB_ROTATE_LEFT(head, tmp, oright); 251 tmp = RB_LEFT(parent); 252 } 253 RB_COLOR(tmp) = RB_COLOR(parent); 254 RB_COLOR(parent) = RB_BLACK; 255 if (RB_LEFT(tmp)) 256 RB_COLOR(RB_LEFT(tmp)) = RB_BLACK; 257 RB_ROTATE_RIGHT(head, parent, tmp); 258 elm = RB_HEAD(head); 259 break; 260 } 261 } 262 } 263 if (elm) 264 RB_COLOR(elm) = RB_BLACK; 265 } 266 267 /* Note name changed. Guess why :) */ 268 void rb_erase(struct rb_node *elm, struct rb_root *head) 269 { 270 struct rb_node *child, *parent, *old = elm; 271 int color; 272 if (RB_LEFT(elm) == NULL) 273 child = RB_RIGHT(elm); 274 else if (RB_RIGHT(elm) == NULL) 275 child = RB_LEFT(elm); 276 else { 277 struct rb_node *left; 278 elm = RB_RIGHT(elm); 279 while ((left = RB_LEFT(elm))) 280 elm = left; 281 child = RB_RIGHT(elm); 282 parent = RB_PARENT(elm); 283 color = RB_COLOR(elm); 284 if (child) 285 RB_PARENT(child) = parent; 286 if (parent) { 287 if (RB_LEFT(parent) == elm) 288 RB_LEFT(parent) = child; 289 else 290 RB_RIGHT(parent) = child; 291 RB_AUGMENT(parent); 292 } else 293 RB_HEAD(head) = child; 294 if (RB_PARENT(elm) == old) 295 parent = elm; 296 *(elm) = *(old); 297 if (RB_PARENT(old)) { 298 if (RB_LEFT(RB_PARENT(old)) == old) 299 RB_LEFT(RB_PARENT(old)) = elm; 300 else 301 RB_RIGHT(RB_PARENT(old)) = elm; 302 RB_AUGMENT(RB_PARENT(old)); 303 } else 304 RB_HEAD(head) = elm; 305 RB_PARENT(RB_LEFT(old)) = elm; 306 if (RB_RIGHT(old)) 307 RB_PARENT(RB_RIGHT(old)) = elm; 308 if (parent) { 309 left = parent; 310 do { 311 RB_AUGMENT(left); 312 } while ((left = RB_PARENT(left))); 313 } 314 goto color; 315 } 316 parent = RB_PARENT(elm); 317 color = RB_COLOR(elm); 318 if (child) 319 RB_PARENT(child) = parent; 320 if (parent) { 321 if (RB_LEFT(parent) == elm) 322 RB_LEFT(parent) = child; 323 else 324 RB_RIGHT(parent) = child; 325 RB_AUGMENT(parent); 326 } else 327 RB_HEAD(head) = child; 328 color: 329 if (color == RB_BLACK) 330 rb_remove_color(head, parent, child); 331 } 332 333 struct rb_node *rb_next(struct rb_node *elm) 334 { 335 if (RB_RIGHT(elm)) { 336 elm = RB_RIGHT(elm); 337 while (RB_LEFT(elm)) 338 elm = RB_LEFT(elm); 339 } else { 340 if (RB_PARENT(elm) && 341 (elm == RB_LEFT(RB_PARENT(elm)))) 342 elm = RB_PARENT(elm); 343 else { 344 while (RB_PARENT(elm) && 345 (elm == RB_RIGHT(RB_PARENT(elm)))) 346 elm = RB_PARENT(elm); 347 elm = RB_PARENT(elm); 348 } 349 } 350 return (elm); 351 } 352 353 struct rb_node *rb_prev(struct rb_node *elm) 354 { 355 if (RB_LEFT(elm)) { 356 elm = RB_LEFT(elm); 357 while (RB_RIGHT(elm)) 358 elm = RB_RIGHT(elm); 359 } else { 360 if (RB_PARENT(elm) && 361 (elm == RB_RIGHT(RB_PARENT(elm)))) 362 elm = RB_PARENT(elm); 363 else { 364 while (RB_PARENT(elm) && 365 (elm == RB_LEFT(RB_PARENT(elm)))) 366 elm = RB_PARENT(elm); 367 elm = RB_PARENT(elm); 368 } 369 } 370 return (elm); 371 } 372 373 /* These ones are lifted from Linux -- but that's OK because I 374 wrote them. dwmw2. */ 375 struct rb_node *rb_first(struct rb_root *root) 376 { 377 struct rb_node *n; 378 379 n = root->rb_node; 380 if (!n) 381 return 0; 382 while (n->rb_left) 383 n = n->rb_left; 384 return n; 385 } 386 387 void rb_replace_node(struct rb_node *victim, struct rb_node *new, 388 struct rb_root *root) 389 { 390 struct rb_node *parent = victim->rb_parent; 391 392 /* Set the surrounding nodes to point to the replacement */ 393 if (parent) { 394 if (victim == parent->rb_left) 395 parent->rb_left = new; 396 else 397 parent->rb_right = new; 398 } else { 399 root->rb_node = new; 400 } 401 if (victim->rb_left) 402 victim->rb_left->rb_parent = new; 403 if (victim->rb_right) 404 victim->rb_right->rb_parent = new; 405 406 /* Copy the pointers/colour from the victim to the replacement */ 407 *new = *victim; 408 } 409