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