blob: b05f1ab7f592c150341c3c1508bd757cec0068e9 [file] [log] [blame]
Kyungmin Park7ba890b2008-10-08 11:01:17 +09001/*
2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5
Wolfgang Denk1a459662013-07-08 09:37:19 +02006 * SPDX-License-Identifier: GPL-2.0+
Kyungmin Park7ba890b2008-10-08 11:01:17 +09007
8 linux/lib/rbtree.c
9*/
10
11#include <ubi_uboot.h>
12#include <linux/rbtree.h>
13
14static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
15{
16 struct rb_node *right = node->rb_right;
17 struct rb_node *parent = rb_parent(node);
18
19 if ((node->rb_right = right->rb_left))
20 rb_set_parent(right->rb_left, node);
21 right->rb_left = node;
22
23 rb_set_parent(right, parent);
24
25 if (parent)
26 {
27 if (node == parent->rb_left)
28 parent->rb_left = right;
29 else
30 parent->rb_right = right;
31 }
32 else
33 root->rb_node = right;
34 rb_set_parent(node, right);
35}
36
37static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
38{
39 struct rb_node *left = node->rb_left;
40 struct rb_node *parent = rb_parent(node);
41
42 if ((node->rb_left = left->rb_right))
43 rb_set_parent(left->rb_right, node);
44 left->rb_right = node;
45
46 rb_set_parent(left, parent);
47
48 if (parent)
49 {
50 if (node == parent->rb_right)
51 parent->rb_right = left;
52 else
53 parent->rb_left = left;
54 }
55 else
56 root->rb_node = left;
57 rb_set_parent(node, left);
58}
59
60void rb_insert_color(struct rb_node *node, struct rb_root *root)
61{
62 struct rb_node *parent, *gparent;
63
64 while ((parent = rb_parent(node)) && rb_is_red(parent))
65 {
66 gparent = rb_parent(parent);
67
68 if (parent == gparent->rb_left)
69 {
70 {
71 register struct rb_node *uncle = gparent->rb_right;
72 if (uncle && rb_is_red(uncle))
73 {
74 rb_set_black(uncle);
75 rb_set_black(parent);
76 rb_set_red(gparent);
77 node = gparent;
78 continue;
79 }
80 }
81
82 if (parent->rb_right == node)
83 {
84 register struct rb_node *tmp;
85 __rb_rotate_left(parent, root);
86 tmp = parent;
87 parent = node;
88 node = tmp;
89 }
90
91 rb_set_black(parent);
92 rb_set_red(gparent);
93 __rb_rotate_right(gparent, root);
94 } else {
95 {
96 register struct rb_node *uncle = gparent->rb_left;
97 if (uncle && rb_is_red(uncle))
98 {
99 rb_set_black(uncle);
100 rb_set_black(parent);
101 rb_set_red(gparent);
102 node = gparent;
103 continue;
104 }
105 }
106
107 if (parent->rb_left == node)
108 {
109 register struct rb_node *tmp;
110 __rb_rotate_right(parent, root);
111 tmp = parent;
112 parent = node;
113 node = tmp;
114 }
115
116 rb_set_black(parent);
117 rb_set_red(gparent);
118 __rb_rotate_left(gparent, root);
119 }
120 }
121
122 rb_set_black(root->rb_node);
123}
124
125static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
126 struct rb_root *root)
127{
128 struct rb_node *other;
129
130 while ((!node || rb_is_black(node)) && node != root->rb_node)
131 {
132 if (parent->rb_left == node)
133 {
134 other = parent->rb_right;
135 if (rb_is_red(other))
136 {
137 rb_set_black(other);
138 rb_set_red(parent);
139 __rb_rotate_left(parent, root);
140 other = parent->rb_right;
141 }
142 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
143 (!other->rb_right || rb_is_black(other->rb_right)))
144 {
145 rb_set_red(other);
146 node = parent;
147 parent = rb_parent(node);
148 }
149 else
150 {
151 if (!other->rb_right || rb_is_black(other->rb_right))
152 {
153 struct rb_node *o_left;
154 if ((o_left = other->rb_left))
155 rb_set_black(o_left);
156 rb_set_red(other);
157 __rb_rotate_right(other, root);
158 other = parent->rb_right;
159 }
160 rb_set_color(other, rb_color(parent));
161 rb_set_black(parent);
162 if (other->rb_right)
163 rb_set_black(other->rb_right);
164 __rb_rotate_left(parent, root);
165 node = root->rb_node;
166 break;
167 }
168 }
169 else
170 {
171 other = parent->rb_left;
172 if (rb_is_red(other))
173 {
174 rb_set_black(other);
175 rb_set_red(parent);
176 __rb_rotate_right(parent, root);
177 other = parent->rb_left;
178 }
179 if ((!other->rb_left || rb_is_black(other->rb_left)) &&
180 (!other->rb_right || rb_is_black(other->rb_right)))
181 {
182 rb_set_red(other);
183 node = parent;
184 parent = rb_parent(node);
185 }
186 else
187 {
188 if (!other->rb_left || rb_is_black(other->rb_left))
189 {
190 register struct rb_node *o_right;
191 if ((o_right = other->rb_right))
192 rb_set_black(o_right);
193 rb_set_red(other);
194 __rb_rotate_left(other, root);
195 other = parent->rb_left;
196 }
197 rb_set_color(other, rb_color(parent));
198 rb_set_black(parent);
199 if (other->rb_left)
200 rb_set_black(other->rb_left);
201 __rb_rotate_right(parent, root);
202 node = root->rb_node;
203 break;
204 }
205 }
206 }
207 if (node)
208 rb_set_black(node);
209}
210
211void rb_erase(struct rb_node *node, struct rb_root *root)
212{
213 struct rb_node *child, *parent;
214 int color;
215
216 if (!node->rb_left)
217 child = node->rb_right;
218 else if (!node->rb_right)
219 child = node->rb_left;
220 else
221 {
222 struct rb_node *old = node, *left;
223
224 node = node->rb_right;
225 while ((left = node->rb_left) != NULL)
226 node = left;
227 child = node->rb_right;
228 parent = rb_parent(node);
229 color = rb_color(node);
230
231 if (child)
232 rb_set_parent(child, parent);
233 if (parent == old) {
234 parent->rb_right = child;
235 parent = node;
236 } else
237 parent->rb_left = child;
238
239 node->rb_parent_color = old->rb_parent_color;
240 node->rb_right = old->rb_right;
241 node->rb_left = old->rb_left;
242
243 if (rb_parent(old))
244 {
245 if (rb_parent(old)->rb_left == old)
246 rb_parent(old)->rb_left = node;
247 else
248 rb_parent(old)->rb_right = node;
249 } else
250 root->rb_node = node;
251
252 rb_set_parent(old->rb_left, node);
253 if (old->rb_right)
254 rb_set_parent(old->rb_right, node);
255 goto color;
256 }
257
258 parent = rb_parent(node);
259 color = rb_color(node);
260
261 if (child)
262 rb_set_parent(child, parent);
263 if (parent)
264 {
265 if (parent->rb_left == node)
266 parent->rb_left = child;
267 else
268 parent->rb_right = child;
269 }
270 else
271 root->rb_node = child;
272
273 color:
274 if (color == RB_BLACK)
275 __rb_erase_color(child, parent, root);
276}
277
278/*
279 * This function returns the first node (in sort order) of the tree.
280 */
281struct rb_node *rb_first(struct rb_root *root)
282{
283 struct rb_node *n;
284
285 n = root->rb_node;
286 if (!n)
287 return NULL;
288 while (n->rb_left)
289 n = n->rb_left;
290 return n;
291}
292
293struct rb_node *rb_last(struct rb_root *root)
294{
295 struct rb_node *n;
296
297 n = root->rb_node;
298 if (!n)
299 return NULL;
300 while (n->rb_right)
301 n = n->rb_right;
302 return n;
303}
304
305struct rb_node *rb_next(struct rb_node *node)
306{
307 struct rb_node *parent;
308
309 if (rb_parent(node) == node)
310 return NULL;
311
312 /* If we have a right-hand child, go down and then left as far
313 as we can. */
314 if (node->rb_right) {
315 node = node->rb_right;
316 while (node->rb_left)
317 node=node->rb_left;
318 return node;
319 }
320
321 /* No right-hand children. Everything down and left is
322 smaller than us, so any 'next' node must be in the general
323 direction of our parent. Go up the tree; any time the
324 ancestor is a right-hand child of its parent, keep going
325 up. First time it's a left-hand child of its parent, said
326 parent is our 'next' node. */
327 while ((parent = rb_parent(node)) && node == parent->rb_right)
328 node = parent;
329
330 return parent;
331}
332
333struct rb_node *rb_prev(struct rb_node *node)
334{
335 struct rb_node *parent;
336
337 if (rb_parent(node) == node)
338 return NULL;
339
340 /* If we have a left-hand child, go down and then right as far
341 as we can. */
342 if (node->rb_left) {
343 node = node->rb_left;
344 while (node->rb_right)
345 node=node->rb_right;
346 return node;
347 }
348
349 /* No left-hand children. Go up till we find an ancestor which
350 is a right-hand child of its parent */
351 while ((parent = rb_parent(node)) && node == parent->rb_left)
352 node = parent;
353
354 return parent;
355}
356
357void rb_replace_node(struct rb_node *victim, struct rb_node *new,
358 struct rb_root *root)
359{
360 struct rb_node *parent = rb_parent(victim);
361
362 /* Set the surrounding nodes to point to the replacement */
363 if (parent) {
364 if (victim == parent->rb_left)
365 parent->rb_left = new;
366 else
367 parent->rb_right = new;
368 } else {
369 root->rb_node = new;
370 }
371 if (victim->rb_left)
372 rb_set_parent(victim->rb_left, new);
373 if (victim->rb_right)
374 rb_set_parent(victim->rb_right, new);
375
376 /* Copy the pointers/colour from the victim to the replacement */
377 *new = *victim;
378}