Line data Source code
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 "replace.h"
24 : #include "rbtree.h"
25 : #include "fault.h"
26 :
27 : #define RB_RED 0
28 : #define RB_BLACK 1
29 :
30 : #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
31 : #define rb_color(r) ((r)->rb_parent_color & 1)
32 : #define rb_is_red(r) (!rb_color(r))
33 : #define rb_is_black(r) rb_color(r)
34 : #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
35 : #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
36 :
37 5390838 : static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
38 : {
39 5390838 : rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
40 5336588 : }
41 35655 : static void rb_set_color(struct rb_node *rb, int color)
42 : {
43 35655 : rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
44 35342 : }
45 :
46 : #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
47 : #define RB_EMPTY_NODE(node) (rb_parent(node) == node)
48 : #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
49 :
50 1242399 : static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
51 : {
52 1242399 : struct rb_node *right = node->rb_right;
53 1242399 : struct rb_node *parent = rb_parent(node);
54 :
55 1242399 : if ((node->rb_right = right->rb_left))
56 289648 : rb_set_parent(right->rb_left, node);
57 1242399 : right->rb_left = node;
58 :
59 1242399 : rb_set_parent(right, parent);
60 :
61 1242399 : if (parent)
62 : {
63 1087757 : if (node == parent->rb_left)
64 694769 : parent->rb_left = right;
65 : else
66 392988 : parent->rb_right = right;
67 : }
68 : else
69 154642 : root->rb_node = right;
70 1242399 : rb_set_parent(node, right);
71 1242399 : }
72 :
73 1010245 : static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
74 : {
75 1010245 : struct rb_node *left = node->rb_left;
76 1010245 : struct rb_node *parent = rb_parent(node);
77 :
78 1010245 : if ((node->rb_left = left->rb_right))
79 220588 : rb_set_parent(left->rb_right, node);
80 1010245 : left->rb_right = node;
81 :
82 1010245 : rb_set_parent(left, parent);
83 :
84 1010245 : if (parent)
85 : {
86 934773 : if (node == parent->rb_right)
87 651669 : parent->rb_right = left;
88 : else
89 283104 : parent->rb_left = left;
90 : }
91 : else
92 75472 : root->rb_node = left;
93 1010245 : rb_set_parent(node, left);
94 1010245 : }
95 :
96 4304596 : void rb_insert_color(struct rb_node *node, struct rb_root *root)
97 : {
98 48647 : struct rb_node *parent, *gparent;
99 :
100 7249555 : while ((parent = rb_parent(node)) && rb_is_red(parent))
101 : {
102 2944959 : gparent = rb_parent(parent);
103 :
104 2944959 : if (parent == gparent->rb_left)
105 : {
106 : {
107 1324101 : register struct rb_node *uncle = gparent->rb_right;
108 1324101 : if (uncle && rb_is_red(uncle))
109 : {
110 608512 : rb_set_black(uncle);
111 608512 : rb_set_black(parent);
112 608512 : rb_set_red(gparent);
113 608512 : node = gparent;
114 608512 : continue;
115 : }
116 : }
117 :
118 715589 : if (parent->rb_right == node)
119 : {
120 4107 : register struct rb_node *tmp;
121 437441 : __rb_rotate_left(parent, root);
122 437441 : tmp = parent;
123 437441 : parent = node;
124 437441 : node = tmp;
125 : }
126 :
127 715589 : rb_set_black(parent);
128 715589 : rb_set_red(gparent);
129 715589 : __rb_rotate_right(gparent, root);
130 : } else {
131 : {
132 1620858 : register struct rb_node *uncle = gparent->rb_left;
133 1620858 : if (uncle && rb_is_red(uncle))
134 : {
135 855218 : rb_set_black(uncle);
136 855218 : rb_set_black(parent);
137 855218 : rb_set_red(gparent);
138 855218 : node = gparent;
139 855218 : continue;
140 : }
141 : }
142 :
143 765640 : if (parent->rb_left == node)
144 : {
145 4642 : register struct rb_node *tmp;
146 259161 : __rb_rotate_right(parent, root);
147 259161 : tmp = parent;
148 259161 : parent = node;
149 259161 : node = tmp;
150 : }
151 :
152 765640 : rb_set_black(parent);
153 765640 : rb_set_red(gparent);
154 765640 : __rb_rotate_left(gparent, root);
155 : }
156 : }
157 :
158 4304596 : rb_set_black(root->rb_node);
159 4304596 : }
160 :
161 234656 : static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
162 : struct rb_root *root)
163 : {
164 2528 : struct rb_node *other;
165 :
166 318982 : while ((!node || rb_is_black(node)) && node != root->rb_node)
167 : {
168 119981 : if (parent->rb_left == node)
169 : {
170 65060 : other = parent->rb_right;
171 65060 : if (other == NULL) {
172 : /* we should never get here */
173 0 : smb_panic("corrupted rb tree");
174 : /* satisfy static checkers */
175 : return;
176 : }
177 65060 : if (rb_is_red(other))
178 : {
179 11798 : rb_set_black(other);
180 11798 : rb_set_red(parent);
181 11798 : __rb_rotate_left(parent, root);
182 11798 : other = parent->rb_right;
183 : }
184 65060 : if ((!other->rb_left || rb_is_black(other->rb_left)) &&
185 51100 : (!other->rb_right || rb_is_black(other->rb_right)))
186 : {
187 45960 : rb_set_red(other);
188 45960 : node = parent;
189 45960 : parent = rb_parent(node);
190 : }
191 : else
192 : {
193 19100 : if (!other->rb_right || rb_is_black(other->rb_right))
194 : {
195 61 : struct rb_node *o_left;
196 9353 : if ((o_left = other->rb_left))
197 9353 : rb_set_black(o_left);
198 9353 : rb_set_red(other);
199 9353 : __rb_rotate_right(other, root);
200 9353 : other = parent->rb_right;
201 : }
202 19100 : rb_set_color(other, rb_color(parent));
203 19100 : rb_set_black(parent);
204 19100 : if (other->rb_right)
205 19100 : rb_set_black(other->rb_right);
206 19100 : __rb_rotate_left(parent, root);
207 19100 : node = root->rb_node;
208 19100 : break;
209 : }
210 : }
211 : else
212 : {
213 54921 : other = parent->rb_left;
214 54921 : if (rb_is_red(other))
215 : {
216 9587 : rb_set_black(other);
217 9587 : rb_set_red(parent);
218 9587 : __rb_rotate_right(parent, root);
219 9587 : other = parent->rb_left;
220 : }
221 54921 : if ((!other->rb_left || rb_is_black(other->rb_left)) &&
222 46786 : (!other->rb_right || rb_is_black(other->rb_right)))
223 : {
224 38366 : rb_set_red(other);
225 38366 : node = parent;
226 38366 : parent = rb_parent(node);
227 : }
228 : else
229 : {
230 16555 : if (!other->rb_left || rb_is_black(other->rb_left))
231 : {
232 58 : register struct rb_node *o_right;
233 8420 : if ((o_right = other->rb_right))
234 8420 : rb_set_black(o_right);
235 8420 : rb_set_red(other);
236 8420 : __rb_rotate_left(other, root);
237 8420 : other = parent->rb_left;
238 : }
239 16555 : rb_set_color(other, rb_color(parent));
240 16555 : rb_set_black(parent);
241 16555 : if (other->rb_left)
242 16555 : rb_set_black(other->rb_left);
243 16555 : __rb_rotate_right(parent, root);
244 16555 : node = root->rb_node;
245 16555 : break;
246 : }
247 : }
248 : }
249 234656 : if (node)
250 159090 : rb_set_black(node);
251 : }
252 :
253 784233 : void rb_erase(struct rb_node *node, struct rb_root *root)
254 : {
255 4279 : struct rb_node *child, *parent;
256 4279 : int color;
257 :
258 784233 : if (!node->rb_left)
259 543162 : child = node->rb_right;
260 241071 : else if (!node->rb_right)
261 26112 : child = node->rb_left;
262 : else
263 : {
264 214291 : struct rb_node *old = node, *left;
265 :
266 214291 : node = node->rb_right;
267 358804 : while ((left = node->rb_left) != NULL)
268 143470 : node = left;
269 214777 : child = node->rb_right;
270 214777 : parent = rb_parent(node);
271 214777 : color = rb_color(node);
272 :
273 214777 : if (child)
274 20979 : rb_set_parent(child, parent);
275 214777 : if (parent == old) {
276 136209 : parent->rb_right = child;
277 136209 : parent = node;
278 : } else
279 78568 : parent->rb_left = child;
280 :
281 214777 : node->rb_parent_color = old->rb_parent_color;
282 214777 : node->rb_right = old->rb_right;
283 214777 : node->rb_left = old->rb_left;
284 :
285 214777 : if (rb_parent(old))
286 : {
287 205975 : if (rb_parent(old)->rb_left == old)
288 63743 : rb_parent(old)->rb_left = node;
289 : else
290 142232 : rb_parent(old)->rb_right = node;
291 : } else
292 8802 : root->rb_node = node;
293 :
294 214777 : rb_set_parent(old->rb_left, node);
295 214777 : if (old->rb_right)
296 86507 : rb_set_parent(old->rb_right, node);
297 214777 : goto color;
298 : }
299 :
300 569456 : parent = rb_parent(node);
301 569456 : color = rb_color(node);
302 :
303 569456 : if (child)
304 53051 : rb_set_parent(child, parent);
305 569456 : if (parent)
306 : {
307 493081 : if (parent->rb_left == node)
308 66304 : parent->rb_left = child;
309 : else
310 426777 : parent->rb_right = child;
311 : }
312 : else
313 76375 : root->rb_node = child;
314 :
315 784233 : color:
316 784233 : if (color == RB_BLACK)
317 234656 : __rb_erase_color(child, parent, root);
318 784233 : }
319 :
320 : /*
321 : * This function returns the first node (in sort order) of the tree.
322 : */
323 0 : struct rb_node *rb_first(struct rb_root *root)
324 : {
325 0 : struct rb_node *n;
326 :
327 0 : n = root->rb_node;
328 0 : if (!n)
329 0 : return NULL;
330 0 : while (n->rb_left)
331 0 : n = n->rb_left;
332 0 : return n;
333 : }
334 :
335 0 : struct rb_node *rb_last(struct rb_root *root)
336 : {
337 0 : struct rb_node *n;
338 :
339 0 : n = root->rb_node;
340 0 : if (!n)
341 0 : return NULL;
342 0 : while (n->rb_right)
343 0 : n = n->rb_right;
344 0 : return n;
345 : }
346 :
347 42004 : struct rb_node *rb_next(struct rb_node *node)
348 : {
349 1 : struct rb_node *parent;
350 :
351 42004 : if (rb_parent(node) == node)
352 0 : return NULL;
353 :
354 : /* If we have a right-hand child, go down and then left as far
355 : as we can. */
356 42004 : if (node->rb_right) {
357 20061 : node = node->rb_right;
358 20075 : while (node->rb_left)
359 14 : node=node->rb_left;
360 20061 : return node;
361 : }
362 :
363 : /* No right-hand children. Everything down and left is
364 : smaller than us, so any 'next' node must be in the general
365 : direction of our parent. Go up the tree; any time the
366 : ancestor is a right-hand child of its parent, keep going
367 : up. First time it's a left-hand child of its parent, said
368 : parent is our 'next' node. */
369 44296 : while ((parent = rb_parent(node)) && node == parent->rb_right)
370 22353 : node = parent;
371 :
372 21942 : return parent;
373 : }
374 :
375 21894 : struct rb_node *rb_prev(struct rb_node *node)
376 : {
377 1 : struct rb_node *parent;
378 :
379 21894 : if (rb_parent(node) == node)
380 0 : return NULL;
381 :
382 : /* If we have a left-hand child, go down and then right as far
383 : as we can. */
384 21894 : if (node->rb_left) {
385 154 : node = node->rb_left;
386 154 : while (node->rb_right)
387 0 : node=node->rb_right;
388 154 : return node;
389 : }
390 :
391 : /* No left-hand children. Go up till we find an ancestor which
392 : is a right-hand child of its parent */
393 21791 : while ((parent = rb_parent(node)) && node == parent->rb_left)
394 51 : node = parent;
395 :
396 21739 : return parent;
397 : }
398 :
399 0 : void rb_replace_node(struct rb_node *victim, struct rb_node *new_node,
400 : struct rb_root *root)
401 : {
402 0 : struct rb_node *parent = rb_parent(victim);
403 :
404 : /* Set the surrounding nodes to point to the replacement */
405 0 : if (parent) {
406 0 : if (victim == parent->rb_left)
407 0 : parent->rb_left = new_node;
408 : else
409 0 : parent->rb_right = new_node;
410 : } else {
411 0 : root->rb_node = new_node;
412 : }
413 0 : if (victim->rb_left)
414 0 : rb_set_parent(victim->rb_left, new_node);
415 0 : if (victim->rb_right)
416 0 : rb_set_parent(victim->rb_right, new_node);
417 :
418 : /* Copy the pointers/colour from the victim to the replacement */
419 0 : *new_node = *victim;
420 0 : }
421 :
422 4304596 : void rb_link_node(struct rb_node * node, struct rb_node * parent,
423 : struct rb_node ** rb_link)
424 : {
425 4304596 : node->rb_parent_color = (unsigned long )parent;
426 4304596 : node->rb_left = node->rb_right = NULL;
427 :
428 4304596 : *rb_link = node;
429 4304596 : }
|
