Root/lib/rbtree.c

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 <linux/rbtree.h>
24#include <linux/module.h>
25
26static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27{
28    struct rb_node *right = node->rb_right;
29    struct rb_node *parent = rb_parent(node);
30
31    if ((node->rb_right = right->rb_left))
32        rb_set_parent(right->rb_left, node);
33    right->rb_left = node;
34
35    rb_set_parent(right, parent);
36
37    if (parent)
38    {
39        if (node == parent->rb_left)
40            parent->rb_left = right;
41        else
42            parent->rb_right = right;
43    }
44    else
45        root->rb_node = right;
46    rb_set_parent(node, right);
47}
48
49static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
50{
51    struct rb_node *left = node->rb_left;
52    struct rb_node *parent = rb_parent(node);
53
54    if ((node->rb_left = left->rb_right))
55        rb_set_parent(left->rb_right, node);
56    left->rb_right = node;
57
58    rb_set_parent(left, parent);
59
60    if (parent)
61    {
62        if (node == parent->rb_right)
63            parent->rb_right = left;
64        else
65            parent->rb_left = left;
66    }
67    else
68        root->rb_node = left;
69    rb_set_parent(node, left);
70}
71
72void rb_insert_color(struct rb_node *node, struct rb_root *root)
73{
74    struct rb_node *parent, *gparent;
75
76    while ((parent = rb_parent(node)) && rb_is_red(parent))
77    {
78        gparent = rb_parent(parent);
79
80        if (parent == gparent->rb_left)
81        {
82            {
83                register struct rb_node *uncle = gparent->rb_right;
84                if (uncle && rb_is_red(uncle))
85                {
86                    rb_set_black(uncle);
87                    rb_set_black(parent);
88                    rb_set_red(gparent);
89                    node = gparent;
90                    continue;
91                }
92            }
93
94            if (parent->rb_right == node)
95            {
96                register struct rb_node *tmp;
97                __rb_rotate_left(parent, root);
98                tmp = parent;
99                parent = node;
100                node = tmp;
101            }
102
103            rb_set_black(parent);
104            rb_set_red(gparent);
105            __rb_rotate_right(gparent, root);
106        } else {
107            {
108                register struct rb_node *uncle = gparent->rb_left;
109                if (uncle && rb_is_red(uncle))
110                {
111                    rb_set_black(uncle);
112                    rb_set_black(parent);
113                    rb_set_red(gparent);
114                    node = gparent;
115                    continue;
116                }
117            }
118
119            if (parent->rb_left == node)
120            {
121                register struct rb_node *tmp;
122                __rb_rotate_right(parent, root);
123                tmp = parent;
124                parent = node;
125                node = tmp;
126            }
127
128            rb_set_black(parent);
129            rb_set_red(gparent);
130            __rb_rotate_left(gparent, root);
131        }
132    }
133
134    rb_set_black(root->rb_node);
135}
136EXPORT_SYMBOL(rb_insert_color);
137
138static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
139                 struct rb_root *root)
140{
141    struct rb_node *other;
142
143    while ((!node || rb_is_black(node)) && node != root->rb_node)
144    {
145        if (parent->rb_left == node)
146        {
147            other = parent->rb_right;
148            if (rb_is_red(other))
149            {
150                rb_set_black(other);
151                rb_set_red(parent);
152                __rb_rotate_left(parent, root);
153                other = parent->rb_right;
154            }
155            if ((!other->rb_left || rb_is_black(other->rb_left)) &&
156                (!other->rb_right || rb_is_black(other->rb_right)))
157            {
158                rb_set_red(other);
159                node = parent;
160                parent = rb_parent(node);
161            }
162            else
163            {
164                if (!other->rb_right || rb_is_black(other->rb_right))
165                {
166                    rb_set_black(other->rb_left);
167                    rb_set_red(other);
168                    __rb_rotate_right(other, root);
169                    other = parent->rb_right;
170                }
171                rb_set_color(other, rb_color(parent));
172                rb_set_black(parent);
173                rb_set_black(other->rb_right);
174                __rb_rotate_left(parent, root);
175                node = root->rb_node;
176                break;
177            }
178        }
179        else
180        {
181            other = parent->rb_left;
182            if (rb_is_red(other))
183            {
184                rb_set_black(other);
185                rb_set_red(parent);
186                __rb_rotate_right(parent, root);
187                other = parent->rb_left;
188            }
189            if ((!other->rb_left || rb_is_black(other->rb_left)) &&
190                (!other->rb_right || rb_is_black(other->rb_right)))
191            {
192                rb_set_red(other);
193                node = parent;
194                parent = rb_parent(node);
195            }
196            else
197            {
198                if (!other->rb_left || rb_is_black(other->rb_left))
199                {
200                    rb_set_black(other->rb_right);
201                    rb_set_red(other);
202                    __rb_rotate_left(other, root);
203                    other = parent->rb_left;
204                }
205                rb_set_color(other, rb_color(parent));
206                rb_set_black(parent);
207                rb_set_black(other->rb_left);
208                __rb_rotate_right(parent, root);
209                node = root->rb_node;
210                break;
211            }
212        }
213    }
214    if (node)
215        rb_set_black(node);
216}
217
218void rb_erase(struct rb_node *node, struct rb_root *root)
219{
220    struct rb_node *child, *parent;
221    int color;
222
223    if (!node->rb_left)
224        child = node->rb_right;
225    else if (!node->rb_right)
226        child = node->rb_left;
227    else
228    {
229        struct rb_node *old = node, *left;
230
231        node = node->rb_right;
232        while ((left = node->rb_left) != NULL)
233            node = left;
234
235        if (rb_parent(old)) {
236            if (rb_parent(old)->rb_left == old)
237                rb_parent(old)->rb_left = node;
238            else
239                rb_parent(old)->rb_right = node;
240        } else
241            root->rb_node = node;
242
243        child = node->rb_right;
244        parent = rb_parent(node);
245        color = rb_color(node);
246
247        if (parent == old) {
248            parent = node;
249        } else {
250            if (child)
251                rb_set_parent(child, parent);
252            parent->rb_left = child;
253
254            node->rb_right = old->rb_right;
255            rb_set_parent(old->rb_right, node);
256        }
257
258        node->rb_parent_color = old->rb_parent_color;
259        node->rb_left = old->rb_left;
260        rb_set_parent(old->rb_left, node);
261
262        goto color;
263    }
264
265    parent = rb_parent(node);
266    color = rb_color(node);
267
268    if (child)
269        rb_set_parent(child, parent);
270    if (parent)
271    {
272        if (parent->rb_left == node)
273            parent->rb_left = child;
274        else
275            parent->rb_right = child;
276    }
277    else
278        root->rb_node = child;
279
280 color:
281    if (color == RB_BLACK)
282        __rb_erase_color(child, parent, root);
283}
284EXPORT_SYMBOL(rb_erase);
285
286static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
287{
288    struct rb_node *parent;
289
290up:
291    func(node, data);
292    parent = rb_parent(node);
293    if (!parent)
294        return;
295
296    if (node == parent->rb_left && parent->rb_right)
297        func(parent->rb_right, data);
298    else if (parent->rb_left)
299        func(parent->rb_left, data);
300
301    node = parent;
302    goto up;
303}
304
305/*
306 * after inserting @node into the tree, update the tree to account for
307 * both the new entry and any damage done by rebalance
308 */
309void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
310{
311    if (node->rb_left)
312        node = node->rb_left;
313    else if (node->rb_right)
314        node = node->rb_right;
315
316    rb_augment_path(node, func, data);
317}
318
319/*
320 * before removing the node, find the deepest node on the rebalance path
321 * that will still be there after @node gets removed
322 */
323struct rb_node *rb_augment_erase_begin(struct rb_node *node)
324{
325    struct rb_node *deepest;
326
327    if (!node->rb_right && !node->rb_left)
328        deepest = rb_parent(node);
329    else if (!node->rb_right)
330        deepest = node->rb_left;
331    else if (!node->rb_left)
332        deepest = node->rb_right;
333    else {
334        deepest = rb_next(node);
335        if (deepest->rb_right)
336            deepest = deepest->rb_right;
337        else if (rb_parent(deepest) != node)
338            deepest = rb_parent(deepest);
339    }
340
341    return deepest;
342}
343
344/*
345 * after removal, update the tree to account for the removed entry
346 * and any rebalance damage.
347 */
348void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
349{
350    if (node)
351        rb_augment_path(node, func, data);
352}
353
354/*
355 * This function returns the first node (in sort order) of the tree.
356 */
357struct rb_node *rb_first(const struct rb_root *root)
358{
359    struct rb_node *n;
360
361    n = root->rb_node;
362    if (!n)
363        return NULL;
364    while (n->rb_left)
365        n = n->rb_left;
366    return n;
367}
368EXPORT_SYMBOL(rb_first);
369
370struct rb_node *rb_last(const struct rb_root *root)
371{
372    struct rb_node *n;
373
374    n = root->rb_node;
375    if (!n)
376        return NULL;
377    while (n->rb_right)
378        n = n->rb_right;
379    return n;
380}
381EXPORT_SYMBOL(rb_last);
382
383struct rb_node *rb_next(const struct rb_node *node)
384{
385    struct rb_node *parent;
386
387    if (rb_parent(node) == node)
388        return NULL;
389
390    /* If we have a right-hand child, go down and then left as far
391       as we can. */
392    if (node->rb_right) {
393        node = node->rb_right;
394        while (node->rb_left)
395            node=node->rb_left;
396        return (struct rb_node *)node;
397    }
398
399    /* No right-hand children. Everything down and left is
400       smaller than us, so any 'next' node must be in the general
401       direction of our parent. Go up the tree; any time the
402       ancestor is a right-hand child of its parent, keep going
403       up. First time it's a left-hand child of its parent, said
404       parent is our 'next' node. */
405    while ((parent = rb_parent(node)) && node == parent->rb_right)
406        node = parent;
407
408    return parent;
409}
410EXPORT_SYMBOL(rb_next);
411
412struct rb_node *rb_prev(const struct rb_node *node)
413{
414    struct rb_node *parent;
415
416    if (rb_parent(node) == node)
417        return NULL;
418
419    /* If we have a left-hand child, go down and then right as far
420       as we can. */
421    if (node->rb_left) {
422        node = node->rb_left;
423        while (node->rb_right)
424            node=node->rb_right;
425        return (struct rb_node *)node;
426    }
427
428    /* No left-hand children. Go up till we find an ancestor which
429       is a right-hand child of its parent */
430    while ((parent = rb_parent(node)) && node == parent->rb_left)
431        node = parent;
432
433    return parent;
434}
435EXPORT_SYMBOL(rb_prev);
436
437void rb_replace_node(struct rb_node *victim, struct rb_node *new,
438             struct rb_root *root)
439{
440    struct rb_node *parent = rb_parent(victim);
441
442    /* Set the surrounding nodes to point to the replacement */
443    if (parent) {
444        if (victim == parent->rb_left)
445            parent->rb_left = new;
446        else
447            parent->rb_right = new;
448    } else {
449        root->rb_node = new;
450    }
451    if (victim->rb_left)
452        rb_set_parent(victim->rb_left, new);
453    if (victim->rb_right)
454        rb_set_parent(victim->rb_right, new);
455
456    /* Copy the pointers/colour from the victim to the replacement */
457    *new = *victim;
458}
459EXPORT_SYMBOL(rb_replace_node);
460

Archive Download this file



interactive