URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [lib/] [rbtree.c] - Blame information for rev 1765

Details | Compare with Previous | View Log


/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <andrea@suse.de>
 
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.
 
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
  linux/lib/rbtree.c
*/
 
#include <linux/rbtree.h>
#include <linux/module.h>
 
static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
{
        rb_node_t * right = node->rb_right;
 
        if ((node->rb_right = right->rb_left))
                right->rb_left->rb_parent = node;
        right->rb_left = node;
 
        if ((right->rb_parent = node->rb_parent))
        {
                if (node == node->rb_parent->rb_left)
                        node->rb_parent->rb_left = right;
                else
                        node->rb_parent->rb_right = right;
        }
        else
                root->rb_node = right;
        node->rb_parent = right;
}
 
static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
{
        rb_node_t * left = node->rb_left;
 
        if ((node->rb_left = left->rb_right))
                left->rb_right->rb_parent = node;
        left->rb_right = node;
 
        if ((left->rb_parent = node->rb_parent))
        {
                if (node == node->rb_parent->rb_right)
                        node->rb_parent->rb_right = left;
                else
                        node->rb_parent->rb_left = left;
        }
        else
                root->rb_node = left;
        node->rb_parent = left;
}
 
void rb_insert_color(rb_node_t * node, rb_root_t * root)
{
        rb_node_t * parent, * gparent;
 
        while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
        {
                gparent = parent->rb_parent;
 
                if (parent == gparent->rb_left)
                {
                        {
                                register rb_node_t * uncle = gparent->rb_right;
                                if (uncle && uncle->rb_color == RB_RED)
                                {
                                        uncle->rb_color = RB_BLACK;
                                        parent->rb_color = RB_BLACK;
                                        gparent->rb_color = RB_RED;
                                        node = gparent;
                                        continue;
                                }
                        }
 
                        if (parent->rb_right == node)
                        {
                                register rb_node_t * tmp;
                                __rb_rotate_left(parent, root);
                                tmp = parent;
                                parent = node;
                                node = tmp;
                        }
 
                        parent->rb_color = RB_BLACK;
                        gparent->rb_color = RB_RED;
                        __rb_rotate_right(gparent, root);
                } else {
                        {
                                register rb_node_t * uncle = gparent->rb_left;
                                if (uncle && uncle->rb_color == RB_RED)
                                {
                                        uncle->rb_color = RB_BLACK;
                                        parent->rb_color = RB_BLACK;
                                        gparent->rb_color = RB_RED;
                                        node = gparent;
                                        continue;
                                }
                        }
 
                        if (parent->rb_left == node)
                        {
                                register rb_node_t * tmp;
                                __rb_rotate_right(parent, root);
                                tmp = parent;
                                parent = node;
                                node = tmp;
                        }
 
                        parent->rb_color = RB_BLACK;
                        gparent->rb_color = RB_RED;
                        __rb_rotate_left(gparent, root);
                }
        }
 
        root->rb_node->rb_color = RB_BLACK;
}
EXPORT_SYMBOL(rb_insert_color);
 
static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
                             rb_root_t * root)
{
        rb_node_t * other;
 
        while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
        {
                if (parent->rb_left == node)
                {
                        other = parent->rb_right;
                        if (other->rb_color == RB_RED)
                        {
                                other->rb_color = RB_BLACK;
                                parent->rb_color = RB_RED;
                                __rb_rotate_left(parent, root);
                                other = parent->rb_right;
                        }
                        if ((!other->rb_left ||
                             other->rb_left->rb_color == RB_BLACK)
                            && (!other->rb_right ||
                                other->rb_right->rb_color == RB_BLACK))
                        {
                                other->rb_color = RB_RED;
                                node = parent;
                                parent = node->rb_parent;
                        }
                        else
                        {
                                if (!other->rb_right ||
                                    other->rb_right->rb_color == RB_BLACK)
                                {
                                        register rb_node_t * o_left;
                                        if ((o_left = other->rb_left))
                                                o_left->rb_color = RB_BLACK;
                                        other->rb_color = RB_RED;
                                        __rb_rotate_right(other, root);
                                        other = parent->rb_right;
                                }
                                other->rb_color = parent->rb_color;
                                parent->rb_color = RB_BLACK;
                                if (other->rb_right)
                                        other->rb_right->rb_color = RB_BLACK;
                                __rb_rotate_left(parent, root);
                                node = root->rb_node;
                                break;
                        }
                }
                else
                {
                        other = parent->rb_left;
                        if (other->rb_color == RB_RED)
                        {
                                other->rb_color = RB_BLACK;
                                parent->rb_color = RB_RED;
                                __rb_rotate_right(parent, root);
                                other = parent->rb_left;
                        }
                        if ((!other->rb_left ||
                             other->rb_left->rb_color == RB_BLACK)
                            && (!other->rb_right ||
                                other->rb_right->rb_color == RB_BLACK))
                        {
                                other->rb_color = RB_RED;
                                node = parent;
                                parent = node->rb_parent;
                        }
                        else
                        {
                                if (!other->rb_left ||
                                    other->rb_left->rb_color == RB_BLACK)
                                {
                                        register rb_node_t * o_right;
                                        if ((o_right = other->rb_right))
                                                o_right->rb_color = RB_BLACK;
                                        other->rb_color = RB_RED;
                                        __rb_rotate_left(other, root);
                                        other = parent->rb_left;
                                }
                                other->rb_color = parent->rb_color;
                                parent->rb_color = RB_BLACK;
                                if (other->rb_left)
                                        other->rb_left->rb_color = RB_BLACK;
                                __rb_rotate_right(parent, root);
                                node = root->rb_node;
                                break;
                        }
                }
        }
        if (node)
                node->rb_color = RB_BLACK;
}
 
void rb_erase(rb_node_t * node, rb_root_t * root)
{
        rb_node_t * child, * parent;
        int color;
 
        if (!node->rb_left)
                child = node->rb_right;
        else if (!node->rb_right)
                child = node->rb_left;
        else
        {
                rb_node_t * old = node, * left;
 
                node = node->rb_right;
                while ((left = node->rb_left))
                        node = left;
                child = node->rb_right;
                parent = node->rb_parent;
                color = node->rb_color;
 
                if (child)
                        child->rb_parent = parent;
                if (parent)
                {
                        if (parent->rb_left == node)
                                parent->rb_left = child;
                        else
                                parent->rb_right = child;
                }
                else
                        root->rb_node = child;
 
                if (node->rb_parent == old)
                        parent = node;
                node->rb_parent = old->rb_parent;
                node->rb_color = old->rb_color;
                node->rb_right = old->rb_right;
                node->rb_left = old->rb_left;
 
                if (old->rb_parent)
                {
                        if (old->rb_parent->rb_left == old)
                                old->rb_parent->rb_left = node;
                        else
                                old->rb_parent->rb_right = node;
                } else
                        root->rb_node = node;
 
                old->rb_left->rb_parent = node;
                if (old->rb_right)
                        old->rb_right->rb_parent = node;
                goto color;
        }
 
        parent = node->rb_parent;
        color = node->rb_color;
 
        if (child)
                child->rb_parent = parent;
        if (parent)
        {
                if (parent->rb_left == node)
                        parent->rb_left = child;
                else
                        parent->rb_right = child;
        }
        else
                root->rb_node = child;
 
 color:
        if (color == RB_BLACK)
                __rb_erase_color(child, parent, root);
}
EXPORT_SYMBOL(rb_erase);

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [lib/] [rbtree.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
2			`Red Black Trees`
3			`(C) 1999 Andrea Arcangeli <andrea@suse.de>`
4
5			`This program is free software; you can redistribute it and/or modify`
6			`it under the terms of the GNU General Public License as published by`
7			`the Free Software Foundation; either version 2 of the License, or`
8			`(at your option) any later version.`
9
10			`This program is distributed in the hope that it will be useful,`
11			`but WITHOUT ANY WARRANTY; without even the implied warranty of`
12			`MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
13			`GNU General Public License for more details.`
14
15			`You should have received a copy of the GNU General Public License`
16			`along with this program; if not, write to the Free Software`
17			`Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA`
18
19			`linux/lib/rbtree.c`
20			`*/`
21
22			`#include <linux/rbtree.h>`
23			`#include <linux/module.h>`
24
25			`static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)`
26			`{`
27			`rb_node_t * 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(rb_node_t * node, rb_root_t * root)`
46			`{`
47			`rb_node_t * 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(rb_node_t * node, rb_root_t * root)`
66			`{`
67			`rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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 rb_node_t * 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			`EXPORT_SYMBOL(rb_insert_color);`
130
131			`static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,`
132			`rb_root_t * root)`
133			`{`
134			`rb_node_t * other;`
135
136			`while ((!node \|\| node->rb_color == RB_BLACK) && node != root->rb_node)`
137			`{`
138			`if (parent->rb_left == node)`
139			`{`
140			`other = parent->rb_right;`
141			`if (other->rb_color == RB_RED)`
142			`{`
143			`other->rb_color = RB_BLACK;`
144			`parent->rb_color = RB_RED;`
145			`__rb_rotate_left(parent, root);`
146			`other = parent->rb_right;`
147			`}`
148			`if ((!other->rb_left \|\|`
149			`other->rb_left->rb_color == RB_BLACK)`
150			`&& (!other->rb_right \|\|`
151			`other->rb_right->rb_color == RB_BLACK))`
152			`{`
153			`other->rb_color = RB_RED;`
154			`node = parent;`
155			`parent = node->rb_parent;`
156			`}`
157			`else`
158			`{`
159			`if (!other->rb_right \|\|`
160			`other->rb_right->rb_color == RB_BLACK)`
161			`{`
162			`register rb_node_t * o_left;`
163			`if ((o_left = other->rb_left))`
164			`o_left->rb_color = RB_BLACK;`
165			`other->rb_color = RB_RED;`
166			`__rb_rotate_right(other, root);`
167			`other = parent->rb_right;`
168			`}`
169			`other->rb_color = parent->rb_color;`
170			`parent->rb_color = RB_BLACK;`
171			`if (other->rb_right)`
172			`other->rb_right->rb_color = RB_BLACK;`
173			`__rb_rotate_left(parent, root);`
174			`node = root->rb_node;`
175			`break;`
176			`}`
177			`}`
178			`else`
179			`{`
180			`other = parent->rb_left;`
181			`if (other->rb_color == RB_RED)`
182			`{`
183			`other->rb_color = RB_BLACK;`
184			`parent->rb_color = RB_RED;`
185			`__rb_rotate_right(parent, root);`
186			`other = parent->rb_left;`
187			`}`
188			`if ((!other->rb_left \|\|`
189			`other->rb_left->rb_color == RB_BLACK)`
190			`&& (!other->rb_right \|\|`
191			`other->rb_right->rb_color == RB_BLACK))`
192			`{`
193			`other->rb_color = RB_RED;`
194			`node = parent;`
195			`parent = node->rb_parent;`
196			`}`
197			`else`
198			`{`
199			`if (!other->rb_left \|\|`
200			`other->rb_left->rb_color == RB_BLACK)`
201			`{`
202			`register rb_node_t * o_right;`
203			`if ((o_right = other->rb_right))`
204			`o_right->rb_color = RB_BLACK;`
205			`other->rb_color = RB_RED;`
206			`__rb_rotate_left(other, root);`
207			`other = parent->rb_left;`
208			`}`
209			`other->rb_color = parent->rb_color;`
210			`parent->rb_color = RB_BLACK;`
211			`if (other->rb_left)`
212			`other->rb_left->rb_color = RB_BLACK;`
213			`__rb_rotate_right(parent, root);`
214			`node = root->rb_node;`
215			`break;`
216			`}`
217			`}`
218			`}`
219			`if (node)`
220			`node->rb_color = RB_BLACK;`
221			`}`
222
223			`void rb_erase(rb_node_t * node, rb_root_t * root)`
224			`{`
225			`rb_node_t * child, * parent;`
226			`int color;`
227
228			`if (!node->rb_left)`
229			`child = node->rb_right;`
230			`else if (!node->rb_right)`
231			`child = node->rb_left;`
232			`else`
233			`{`
234			`rb_node_t * old = node, * left;`
235
236			`node = node->rb_right;`
237			`while ((left = node->rb_left))`
238			`node = left;`
239			`child = node->rb_right;`
240			`parent = node->rb_parent;`
241			`color = node->rb_color;`
242
243			`if (child)`
244			`child->rb_parent = parent;`
245			`if (parent)`
246			`{`
247			`if (parent->rb_left == node)`
248			`parent->rb_left = child;`
249			`else`
250			`parent->rb_right = child;`
251			`}`
252			`else`
253			`root->rb_node = child;`
254
255			`if (node->rb_parent == old)`
256			`parent = node;`
257			`node->rb_parent = old->rb_parent;`
258			`node->rb_color = old->rb_color;`
259			`node->rb_right = old->rb_right;`
260			`node->rb_left = old->rb_left;`
261
262			`if (old->rb_parent)`
263			`{`
264			`if (old->rb_parent->rb_left == old)`
265			`old->rb_parent->rb_left = node;`
266			`else`
267			`old->rb_parent->rb_right = node;`
268			`} else`
269			`root->rb_node = node;`
270
271			`old->rb_left->rb_parent = node;`
272			`if (old->rb_right)`
273			`old->rb_right->rb_parent = node;`
274			`goto color;`
275			`}`
276
277			`parent = node->rb_parent;`
278			`color = node->rb_color;`
279
280			`if (child)`
281			`child->rb_parent = parent;`
282			`if (parent)`
283			`{`
284			`if (parent->rb_left == node)`
285			`parent->rb_left = child;`
286			`else`
287			`parent->rb_right = child;`
288			`}`
289			`else`
290			`root->rb_node = child;`
291
292			`color:`
293			`if (color == RB_BLACK)`
294			`__rb_erase_color(child, parent, root);`
295			`}`
296			`EXPORT_SYMBOL(rb_erase);`