Commit | Line | Data |
---|---|---|
8fc0abbc 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; | |
28 | ||
29 | if ((node->rb_right = right->rb_left)) | |
30 | right->rb_left->rb_parent = node; | |
31 | right->rb_left = node; | |
32 | ||
33 | if ((right->rb_parent = node->rb_parent)) | |
34 | { | |
35 | if (node == node->rb_parent->rb_left) | |
36 | node->rb_parent->rb_left = right; | |
37 | else | |
38 | node->rb_parent->rb_right = right; | |
39 | } | |
40 | else | |
41 | root->rb_node = right; | |
42 | node->rb_parent = right; | |
43 | } | |
44 | ||
45 | static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) | |
46 | { | |
47 | struct rb_node *left = node->rb_left; | |
48 | ||
49 | if ((node->rb_left = left->rb_right)) | |
50 | left->rb_right->rb_parent = node; | |
51 | left->rb_right = node; | |
52 | ||
53 | if ((left->rb_parent = node->rb_parent)) | |
54 | { | |
55 | if (node == node->rb_parent->rb_right) | |
56 | node->rb_parent->rb_right = left; | |
57 | else | |
58 | node->rb_parent->rb_left = left; | |
59 | } | |
60 | else | |
61 | root->rb_node = left; | |
62 | node->rb_parent = left; | |
63 | } | |
64 | ||
65 | void rb_insert_color(struct rb_node *node, struct rb_root *root) | |
66 | { | |
67 | struct rb_node *parent, *gparent; | |
68 | ||
69 | while ((parent = node->rb_parent) && parent->rb_color == RB_RED) | |
70 | { | |
71 | gparent = parent->rb_parent; | |
72 | ||
73 | if (parent == gparent->rb_left) | |
74 | { | |
75 | { | |
76 | register struct rb_node *uncle = gparent->rb_right; | |
77 | if (uncle && uncle->rb_color == RB_RED) | |
78 | { | |
79 | uncle->rb_color = RB_BLACK; | |
80 | parent->rb_color = RB_BLACK; | |
81 | gparent->rb_color = RB_RED; | |
82 | node = gparent; | |
83 | continue; | |
84 | } | |
85 | } | |
86 | ||
87 | if (parent->rb_right == node) | |
88 | { | |
89 | register struct rb_node *tmp; | |
90 | __rb_rotate_left(parent, root); | |
91 | tmp = parent; | |
92 | parent = node; | |
93 | node = tmp; | |
94 | } | |
95 | ||
96 | parent->rb_color = RB_BLACK; | |
97 | gparent->rb_color = RB_RED; | |
98 | __rb_rotate_right(gparent, root); | |
99 | } else { | |
100 | { | |
101 | register struct rb_node *uncle = gparent->rb_left; | |
102 | if (uncle && uncle->rb_color == RB_RED) | |
103 | { | |
104 | uncle->rb_color = RB_BLACK; | |
105 | parent->rb_color = RB_BLACK; | |
106 | gparent->rb_color = RB_RED; | |
107 | node = gparent; | |
108 | continue; | |
109 | } | |
110 | } | |
111 | ||
112 | if (parent->rb_left == node) | |
113 | { | |
114 | register struct rb_node *tmp; | |
115 | __rb_rotate_right(parent, root); | |
116 | tmp = parent; | |
117 | parent = node; | |
118 | node = tmp; | |
119 | } | |
120 | ||
121 | parent->rb_color = RB_BLACK; | |
122 | gparent->rb_color = RB_RED; | |
123 | __rb_rotate_left(gparent, root); | |
124 | } | |
125 | } | |
126 | ||
127 | root->rb_node->rb_color = RB_BLACK; | |
128 | } | |
129 | ||
130 | static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, | |
131 | struct rb_root *root) | |
132 | { | |
133 | struct rb_node *other; | |
134 | ||
135 | while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) | |
136 | { | |
137 | if (parent->rb_left == node) | |
138 | { | |
139 | other = parent->rb_right; | |
140 | if (other->rb_color == RB_RED) | |
141 | { | |
142 | other->rb_color = RB_BLACK; | |
143 | parent->rb_color = RB_RED; | |
144 | __rb_rotate_left(parent, root); | |
145 | other = parent->rb_right; | |
146 | } | |
147 | if ((!other->rb_left || | |
148 | other->rb_left->rb_color == RB_BLACK) | |
149 | && (!other->rb_right || | |
150 | other->rb_right->rb_color == RB_BLACK)) | |
151 | { | |
152 | other->rb_color = RB_RED; | |
153 | node = parent; | |
154 | parent = node->rb_parent; | |
155 | } | |
156 | else | |
157 | { | |
158 | if (!other->rb_right || | |
159 | other->rb_right->rb_color == RB_BLACK) | |
160 | { | |
161 | register struct rb_node *o_left; | |
162 | if ((o_left = other->rb_left)) | |
163 | o_left->rb_color = RB_BLACK; | |
164 | other->rb_color = RB_RED; | |
165 | __rb_rotate_right(other, root); | |
166 | other = parent->rb_right; | |
167 | } | |
168 | other->rb_color = parent->rb_color; | |
169 | parent->rb_color = RB_BLACK; | |
170 | if (other->rb_right) | |
171 | other->rb_right->rb_color = RB_BLACK; | |
172 | __rb_rotate_left(parent, root); | |
173 | node = root->rb_node; | |
174 | break; | |
175 | } | |
176 | } | |
177 | else | |
178 | { | |
179 | other = parent->rb_left; | |
180 | if (other->rb_color == RB_RED) | |
181 | { | |
182 | other->rb_color = RB_BLACK; | |
183 | parent->rb_color = RB_RED; | |
184 | __rb_rotate_right(parent, root); | |
185 | other = parent->rb_left; | |
186 | } | |
187 | if ((!other->rb_left || | |
188 | other->rb_left->rb_color == RB_BLACK) | |
189 | && (!other->rb_right || | |
190 | other->rb_right->rb_color == RB_BLACK)) | |
191 | { | |
192 | other->rb_color = RB_RED; | |
193 | node = parent; | |
194 | parent = node->rb_parent; | |
195 | } | |
196 | else | |
197 | { | |
198 | if (!other->rb_left || | |
199 | other->rb_left->rb_color == RB_BLACK) | |
200 | { | |
201 | register struct rb_node *o_right; | |
202 | if ((o_right = other->rb_right)) | |
203 | o_right->rb_color = RB_BLACK; | |
204 | other->rb_color = RB_RED; | |
205 | __rb_rotate_left(other, root); | |
206 | other = parent->rb_left; | |
207 | } | |
208 | other->rb_color = parent->rb_color; | |
209 | parent->rb_color = RB_BLACK; | |
210 | if (other->rb_left) | |
211 | other->rb_left->rb_color = RB_BLACK; | |
212 | __rb_rotate_right(parent, root); | |
213 | node = root->rb_node; | |
214 | break; | |
215 | } | |
216 | } | |
217 | } | |
218 | if (node) | |
219 | node->rb_color = RB_BLACK; | |
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; | |
239 | parent = node->rb_parent; | |
240 | color = node->rb_color; | |
241 | ||
242 | if (child) | |
243 | child->rb_parent = parent; | |
244 | if (parent) | |
245 | { | |
246 | if (parent->rb_left == node) | |
247 | parent->rb_left = child; | |
248 | else | |
249 | parent->rb_right = child; | |
250 | } | |
251 | else | |
252 | root->rb_node = child; | |
253 | ||
254 | if (node->rb_parent == old) | |
255 | parent = node; | |
256 | node->rb_parent = old->rb_parent; | |
257 | node->rb_color = old->rb_color; | |
258 | node->rb_right = old->rb_right; | |
259 | node->rb_left = old->rb_left; | |
260 | ||
261 | if (old->rb_parent) | |
262 | { | |
263 | if (old->rb_parent->rb_left == old) | |
264 | old->rb_parent->rb_left = node; | |
265 | else | |
266 | old->rb_parent->rb_right = node; | |
267 | } else | |
268 | root->rb_node = node; | |
269 | ||
270 | old->rb_left->rb_parent = node; | |
271 | if (old->rb_right) | |
272 | old->rb_right->rb_parent = node; | |
273 | goto color; | |
274 | } | |
275 | ||
276 | parent = node->rb_parent; | |
277 | color = node->rb_color; | |
278 | ||
279 | if (child) | |
280 | child->rb_parent = parent; | |
281 | if (parent) | |
282 | { | |
283 | if (parent->rb_left == node) | |
284 | parent->rb_left = child; | |
285 | else | |
286 | parent->rb_right = child; | |
287 | } | |
288 | else | |
289 | root->rb_node = child; | |
290 | ||
291 | color: | |
292 | if (color == RB_BLACK) | |
293 | __rb_erase_color(child, parent, root); | |
294 | } | |
295 | ||
296 | /* | |
297 | * This function returns the first node (in sort order) of the tree. | |
298 | */ | |
299 | struct rb_node *rb_first(struct rb_root *root) | |
300 | { | |
301 | struct rb_node *n; | |
302 | ||
303 | n = root->rb_node; | |
304 | if (!n) | |
305 | return NULL; | |
306 | while (n->rb_left) | |
307 | n = n->rb_left; | |
308 | return n; | |
309 | } | |
310 | ||
311 | struct rb_node *rb_last(struct rb_root *root) | |
312 | { | |
313 | struct rb_node *n; | |
314 | ||
315 | n = root->rb_node; | |
316 | if (!n) | |
317 | return NULL; | |
318 | while (n->rb_right) | |
319 | n = n->rb_right; | |
320 | return n; | |
321 | } | |
322 | ||
323 | struct rb_node *rb_next(struct rb_node *node) | |
324 | { | |
325 | /* If we have a right-hand child, go down and then left as far | |
326 | as we can. */ | |
327 | if (node->rb_right) { | |
328 | node = node->rb_right; | |
329 | while (node->rb_left) | |
330 | node=node->rb_left; | |
331 | return node; | |
332 | } | |
333 | ||
334 | /* No right-hand children. Everything down and left is | |
335 | smaller than us, so any 'next' node must be in the general | |
336 | direction of our parent. Go up the tree; any time the | |
337 | ancestor is a right-hand child of its parent, keep going | |
338 | up. First time it's a left-hand child of its parent, said | |
339 | parent is our 'next' node. */ | |
340 | while (node->rb_parent && node == node->rb_parent->rb_right) | |
341 | node = node->rb_parent; | |
342 | ||
343 | return node->rb_parent; | |
344 | } | |
345 | ||
346 | struct rb_node *rb_prev(struct rb_node *node) | |
347 | { | |
348 | /* If we have a left-hand child, go down and then right as far | |
349 | as we can. */ | |
350 | if (node->rb_left) { | |
351 | node = node->rb_left; | |
352 | while (node->rb_right) | |
353 | node=node->rb_right; | |
354 | return node; | |
355 | } | |
356 | ||
357 | /* No left-hand children. Go up till we find an ancestor which | |
358 | is a right-hand child of its parent */ | |
359 | while (node->rb_parent && node == node->rb_parent->rb_left) | |
360 | node = node->rb_parent; | |
361 | ||
362 | return node->rb_parent; | |
363 | } | |
364 | ||
365 | void rb_replace_node(struct rb_node *victim, struct rb_node *new, | |
366 | struct rb_root *root) | |
367 | { | |
368 | struct rb_node *parent = victim->rb_parent; | |
369 | ||
370 | /* Set the surrounding nodes to point to the replacement */ | |
371 | if (parent) { | |
372 | if (victim == parent->rb_left) | |
373 | parent->rb_left = new; | |
374 | else | |
375 | parent->rb_right = new; | |
376 | } else { | |
377 | root->rb_node = new; | |
378 | } | |
379 | if (victim->rb_left) | |
380 | victim->rb_left->rb_parent = new; | |
381 | if (victim->rb_right) | |
382 | victim->rb_right->rb_parent = new; | |
383 | ||
384 | /* Copy the pointers/colour from the victim to the replacement */ | |
385 | *new = *victim; | |
386 | } |