ia64/linux-2.6.18-xen.hg

annotate lib/rbtree.c @ 847:ad4d307bf9ce

net sfc: Update sfc and sfc_resource driver to latest release

...and update sfc_netfront, sfc_netback, sfc_netutil for any API changes

sfc_netback: Fix asymmetric use of SFC buffer table alloc and free
sfc_netback: Clean up if no SFC accel device found
sfc_netback: Gracefully handle case where page grant fails
sfc_netback: Disable net acceleration if the physical link goes down
sfc_netfront: Less verbose error messages, more verbose counters for
rx discard errors
sfc_netfront: Gracefully handle case where SFC netfront fails during
initialisation

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