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