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