debuggers.hg

annotate xen/common/rbtree.c @ 22848:6341fe0f4e5a

find changesets by author, revision, files, or words in the commit message
Added tag 4.1.0-rc2 for changeset 9dca60d88c63
author Keir Fraser <keir@xen.org>
date Tue Jan 25 14:06:55 2011 +0000 (2011-01-25)
parents f210a633571c
children
rev   line source
keir@19684 1 /*
keir@19684 2 Red Black Trees
keir@19684 3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
keir@19684 4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
keir@19684 5
keir@19684 6 This program is free software; you can redistribute it and/or modify
keir@19684 7 it under the terms of the GNU General Public License as published by
keir@19684 8 the Free Software Foundation; either version 2 of the License, or
keir@19684 9 (at your option) any later version.
keir@19684 10
keir@19684 11 This program is distributed in the hope that it will be useful,
keir@19684 12 but WITHOUT ANY WARRANTY; without even the implied warranty of
keir@19684 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
keir@19684 14 GNU General Public License for more details.
keir@19684 15
keir@19684 16 You should have received a copy of the GNU General Public License
keir@19684 17 along with this program; if not, write to the Free Software
keir@19684 18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
keir@19684 19
keir@19684 20 linux/lib/rbtree.c
keir@19684 21 */
keir@19684 22
keir@19684 23 #include <xen/config.h>
keir@19684 24 #include <xen/types.h>
keir@19684 25 #include <xen/rbtree.h>
keir@19684 26
keir@19684 27 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
keir@19684 28 {
keir@19684 29 struct rb_node *right = node->rb_right;
keir@19684 30 struct rb_node *parent = rb_parent(node);
keir@19684 31
keir@19684 32 if ((node->rb_right = right->rb_left))
keir@19684 33 rb_set_parent(right->rb_left, node);
keir@19684 34 right->rb_left = node;
keir@19684 35
keir@19684 36 rb_set_parent(right, parent);
keir@19684 37
keir@19684 38 if (parent)
keir@19684 39 {
keir@19684 40 if (node == parent->rb_left)
keir@19684 41 parent->rb_left = right;
keir@19684 42 else
keir@19684 43 parent->rb_right = right;
keir@19684 44 }
keir@19684 45 else
keir@19684 46 root->rb_node = right;
keir@19684 47 rb_set_parent(node, right);
keir@19684 48 }
keir@19684 49
keir@19684 50 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
keir@19684 51 {
keir@19684 52 struct rb_node *left = node->rb_left;
keir@19684 53 struct rb_node *parent = rb_parent(node);
keir@19684 54
keir@19684 55 if ((node->rb_left = left->rb_right))
keir@19684 56 rb_set_parent(left->rb_right, node);
keir@19684 57 left->rb_right = node;
keir@19684 58
keir@19684 59 rb_set_parent(left, parent);
keir@19684 60
keir@19684 61 if (parent)
keir@19684 62 {
keir@19684 63 if (node == parent->rb_right)
keir@19684 64 parent->rb_right = left;
keir@19684 65 else
keir@19684 66 parent->rb_left = left;
keir@19684 67 }
keir@19684 68 else
keir@19684 69 root->rb_node = left;
keir@19684 70 rb_set_parent(node, left);
keir@19684 71 }
keir@19684 72
keir@19684 73 void rb_insert_color(struct rb_node *node, struct rb_root *root)
keir@19684 74 {
keir@19684 75 struct rb_node *parent, *gparent;
keir@19684 76
keir@19684 77 while ((parent = rb_parent(node)) && rb_is_red(parent))
keir@19684 78 {
keir@19684 79 gparent = rb_parent(parent);
keir@19684 80
keir@19684 81 if (parent == gparent->rb_left)
keir@19684 82 {
keir@19684 83 {
keir@19684 84 register struct rb_node *uncle = gparent->rb_right;
keir@19684 85 if (uncle && rb_is_red(uncle))
keir@19684 86 {
keir@19684 87 rb_set_black(uncle);
keir@19684 88 rb_set_black(parent);
keir@19684 89 rb_set_red(gparent);
keir@19684 90 node = gparent;
keir@19684 91 continue;
keir@19684 92 }
keir@19684 93 }
keir@19684 94
keir@19684 95 if (parent->rb_right == node)
keir@19684 96 {
keir@19684 97 register struct rb_node *tmp;
keir@19684 98 __rb_rotate_left(parent, root);
keir@19684 99 tmp = parent;
keir@19684 100 parent = node;
keir@19684 101 node = tmp;
keir@19684 102 }
keir@19684 103
keir@19684 104 rb_set_black(parent);
keir@19684 105 rb_set_red(gparent);
keir@19684 106 __rb_rotate_right(gparent, root);
keir@19684 107 } else {
keir@19684 108 {
keir@19684 109 register struct rb_node *uncle = gparent->rb_left;
keir@19684 110 if (uncle && rb_is_red(uncle))
keir@19684 111 {
keir@19684 112 rb_set_black(uncle);
keir@19684 113 rb_set_black(parent);
keir@19684 114 rb_set_red(gparent);
keir@19684 115 node = gparent;
keir@19684 116 continue;
keir@19684 117 }
keir@19684 118 }
keir@19684 119
keir@19684 120 if (parent->rb_left == node)
keir@19684 121 {
keir@19684 122 register struct rb_node *tmp;
keir@19684 123 __rb_rotate_right(parent, root);
keir@19684 124 tmp = parent;
keir@19684 125 parent = node;
keir@19684 126 node = tmp;
keir@19684 127 }
keir@19684 128
keir@19684 129 rb_set_black(parent);
keir@19684 130 rb_set_red(gparent);
keir@19684 131 __rb_rotate_left(gparent, root);
keir@19684 132 }
keir@19684 133 }
keir@19684 134
keir@19684 135 rb_set_black(root->rb_node);
keir@19684 136 }
keir@19684 137 EXPORT_SYMBOL(rb_insert_color);
keir@19684 138
keir@19684 139 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
keir@19684 140 struct rb_root *root)
keir@19684 141 {
keir@19684 142 struct rb_node *other;
keir@19684 143
keir@19684 144 while ((!node || rb_is_black(node)) && node != root->rb_node)
keir@19684 145 {
keir@19684 146 if (parent->rb_left == node)
keir@19684 147 {
keir@19684 148 other = parent->rb_right;
keir@19684 149 if (rb_is_red(other))
keir@19684 150 {
keir@19684 151 rb_set_black(other);
keir@19684 152 rb_set_red(parent);
keir@19684 153 __rb_rotate_left(parent, root);
keir@19684 154 other = parent->rb_right;
keir@19684 155 }
keir@19684 156 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
keir@19684 157 (!other->rb_right || rb_is_black(other->rb_right)))
keir@19684 158 {
keir@19684 159 rb_set_red(other);
keir@19684 160 node = parent;
keir@19684 161 parent = rb_parent(node);
keir@19684 162 }
keir@19684 163 else
keir@19684 164 {
keir@19684 165 if (!other->rb_right || rb_is_black(other->rb_right))
keir@19684 166 {
keir@19684 167 struct rb_node *o_left;
keir@19684 168 if ((o_left = other->rb_left))
keir@19684 169 rb_set_black(o_left);
keir@19684 170 rb_set_red(other);
keir@19684 171 __rb_rotate_right(other, root);
keir@19684 172 other = parent->rb_right;
keir@19684 173 }
keir@19684 174 rb_set_color(other, rb_color(parent));
keir@19684 175 rb_set_black(parent);
keir@19684 176 if (other->rb_right)
keir@19684 177 rb_set_black(other->rb_right);
keir@19684 178 __rb_rotate_left(parent, root);
keir@19684 179 node = root->rb_node;
keir@19684 180 break;
keir@19684 181 }
keir@19684 182 }
keir@19684 183 else
keir@19684 184 {
keir@19684 185 other = parent->rb_left;
keir@19684 186 if (rb_is_red(other))
keir@19684 187 {
keir@19684 188 rb_set_black(other);
keir@19684 189 rb_set_red(parent);
keir@19684 190 __rb_rotate_right(parent, root);
keir@19684 191 other = parent->rb_left;
keir@19684 192 }
keir@19684 193 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
keir@19684 194 (!other->rb_right || rb_is_black(other->rb_right)))
keir@19684 195 {
keir@19684 196 rb_set_red(other);
keir@19684 197 node = parent;
keir@19684 198 parent = rb_parent(node);
keir@19684 199 }
keir@19684 200 else
keir@19684 201 {
keir@19684 202 if (!other->rb_left || rb_is_black(other->rb_left))
keir@19684 203 {
keir@19684 204 register struct rb_node *o_right;
keir@19684 205 if ((o_right = other->rb_right))
keir@19684 206 rb_set_black(o_right);
keir@19684 207 rb_set_red(other);
keir@19684 208 __rb_rotate_left(other, root);
keir@19684 209 other = parent->rb_left;
keir@19684 210 }
keir@19684 211 rb_set_color(other, rb_color(parent));
keir@19684 212 rb_set_black(parent);
keir@19684 213 if (other->rb_left)
keir@19684 214 rb_set_black(other->rb_left);
keir@19684 215 __rb_rotate_right(parent, root);
keir@19684 216 node = root->rb_node;
keir@19684 217 break;
keir@19684 218 }
keir@19684 219 }
keir@19684 220 }
keir@19684 221 if (node)
keir@19684 222 rb_set_black(node);
keir@19684 223 }
keir@19684 224
keir@19684 225 void rb_erase(struct rb_node *node, struct rb_root *root)
keir@19684 226 {
keir@19684 227 struct rb_node *child, *parent;
keir@19684 228 int color;
keir@19684 229
keir@19684 230 if (!node->rb_left)
keir@19684 231 child = node->rb_right;
keir@19684 232 else if (!node->rb_right)
keir@19684 233 child = node->rb_left;
keir@19684 234 else
keir@19684 235 {
keir@19684 236 struct rb_node *old = node, *left;
keir@19684 237
keir@19684 238 node = node->rb_right;
keir@19684 239 while ((left = node->rb_left) != NULL)
keir@19684 240 node = left;
keir@19684 241 child = node->rb_right;
keir@19684 242 parent = rb_parent(node);
keir@19684 243 color = rb_color(node);
keir@19684 244
keir@19684 245 if (child)
keir@19684 246 rb_set_parent(child, parent);
keir@19684 247 if (parent == old) {
keir@19684 248 parent->rb_right = child;
keir@19684 249 parent = node;
keir@19684 250 } else
keir@19684 251 parent->rb_left = child;
keir@19684 252
keir@19684 253 node->rb_parent_color = old->rb_parent_color;
keir@19684 254 node->rb_right = old->rb_right;
keir@19684 255 node->rb_left = old->rb_left;
keir@19684 256
keir@19684 257 if (rb_parent(old))
keir@19684 258 {
keir@19684 259 if (rb_parent(old)->rb_left == old)
keir@19684 260 rb_parent(old)->rb_left = node;
keir@19684 261 else
keir@19684 262 rb_parent(old)->rb_right = node;
keir@19684 263 } else
keir@19684 264 root->rb_node = node;
keir@19684 265
keir@19684 266 rb_set_parent(old->rb_left, node);
keir@19684 267 if (old->rb_right)
keir@19684 268 rb_set_parent(old->rb_right, node);
keir@19684 269 goto color;
keir@19684 270 }
keir@19684 271
keir@19684 272 parent = rb_parent(node);
keir@19684 273 color = rb_color(node);
keir@19684 274
keir@19684 275 if (child)
keir@19684 276 rb_set_parent(child, parent);
keir@19684 277 if (parent)
keir@19684 278 {
keir@19684 279 if (parent->rb_left == node)
keir@19684 280 parent->rb_left = child;
keir@19684 281 else
keir@19684 282 parent->rb_right = child;
keir@19684 283 }
keir@19684 284 else
keir@19684 285 root->rb_node = child;
keir@19684 286
keir@19684 287 color:
keir@19684 288 if (color == RB_BLACK)
keir@19684 289 __rb_erase_color(child, parent, root);
keir@19684 290 }
keir@19684 291 EXPORT_SYMBOL(rb_erase);
keir@19684 292
keir@19684 293 /*
keir@19684 294 * This function returns the first node (in sort order) of the tree.
keir@19684 295 */
keir@19684 296 struct rb_node *rb_first(struct rb_root *root)
keir@19684 297 {
keir@19684 298 struct rb_node *n;
keir@19684 299
keir@19684 300 n = root->rb_node;
keir@19684 301 if (!n)
keir@19684 302 return NULL;
keir@19684 303 while (n->rb_left)
keir@19684 304 n = n->rb_left;
keir@19684 305 return n;
keir@19684 306 }
keir@19684 307 EXPORT_SYMBOL(rb_first);
keir@19684 308
keir@19684 309 struct rb_node *rb_last(struct rb_root *root)
keir@19684 310 {
keir@19684 311 struct rb_node *n;
keir@19684 312
keir@19684 313 n = root->rb_node;
keir@19684 314 if (!n)
keir@19684 315 return NULL;
keir@19684 316 while (n->rb_right)
keir@19684 317 n = n->rb_right;
keir@19684 318 return n;
keir@19684 319 }
keir@19684 320 EXPORT_SYMBOL(rb_last);
keir@19684 321
keir@19684 322 struct rb_node *rb_next(struct rb_node *node)
keir@19684 323 {
keir@19684 324 struct rb_node *parent;
keir@19684 325
keir@19684 326 if (rb_parent(node) == node)
keir@19684 327 return NULL;
keir@19684 328
keir@19684 329 /* If we have a right-hand child, go down and then left as far
keir@19684 330 as we can. */
keir@19684 331 if (node->rb_right) {
keir@19684 332 node = node->rb_right;
keir@19684 333 while (node->rb_left)
keir@19684 334 node=node->rb_left;
keir@19684 335 return node;
keir@19684 336 }
keir@19684 337
keir@19684 338 /* No right-hand children. Everything down and left is
keir@19684 339 smaller than us, so any 'next' node must be in the general
keir@19684 340 direction of our parent. Go up the tree; any time the
keir@19684 341 ancestor is a right-hand child of its parent, keep going
keir@19684 342 up. First time it's a left-hand child of its parent, said
keir@19684 343 parent is our 'next' node. */
keir@19684 344 while ((parent = rb_parent(node)) && node == parent->rb_right)
keir@19684 345 node = parent;
keir@19684 346
keir@19684 347 return parent;
keir@19684 348 }
keir@19684 349 EXPORT_SYMBOL(rb_next);
keir@19684 350
keir@19684 351 struct rb_node *rb_prev(struct rb_node *node)
keir@19684 352 {
keir@19684 353 struct rb_node *parent;
keir@19684 354
keir@19684 355 if (rb_parent(node) == node)
keir@19684 356 return NULL;
keir@19684 357
keir@19684 358 /* If we have a left-hand child, go down and then right as far
keir@19684 359 as we can. */
keir@19684 360 if (node->rb_left) {
keir@19684 361 node = node->rb_left;
keir@19684 362 while (node->rb_right)
keir@19684 363 node=node->rb_right;
keir@19684 364 return node;
keir@19684 365 }
keir@19684 366
keir@19684 367 /* No left-hand children. Go up till we find an ancestor which
keir@19684 368 is a right-hand child of its parent */
keir@19684 369 while ((parent = rb_parent(node)) && node == parent->rb_left)
keir@19684 370 node = parent;
keir@19684 371
keir@19684 372 return parent;
keir@19684 373 }
keir@19684 374 EXPORT_SYMBOL(rb_prev);
keir@19684 375
keir@19684 376 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
keir@19684 377 struct rb_root *root)
keir@19684 378 {
keir@19684 379 struct rb_node *parent = rb_parent(victim);
keir@19684 380
keir@19684 381 /* Set the surrounding nodes to point to the replacement */
keir@19684 382 if (parent) {
keir@19684 383 if (victim == parent->rb_left)
keir@19684 384 parent->rb_left = new;
keir@19684 385 else
keir@19684 386 parent->rb_right = new;
keir@19684 387 } else {
keir@19684 388 root->rb_node = new;
keir@19684 389 }
keir@19684 390 if (victim->rb_left)
keir@19684 391 rb_set_parent(victim->rb_left, new);
keir@19684 392 if (victim->rb_right)
keir@19684 393 rb_set_parent(victim->rb_right, new);
keir@19684 394
keir@19684 395 /* Copy the pointers/colour from the victim to the replacement */
keir@19684 396 *new = *victim;
keir@19684 397 }
keir@19684 398 EXPORT_SYMBOL(rb_replace_node);