source: trunk/kernel/libk/rbtree.c @ 684

Last change on this file since 684 was 1, checked in by alain, 8 years ago

First import

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