]> git.sur5r.net Git - u-boot/blob - lib/rbtree.c
arc: add Arcangel4 board support
[u-boot] / 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  * SPDX-License-Identifier:     GPL-2.0+
7
8   linux/lib/rbtree.c
9 */
10
11 #include <ubi_uboot.h>
12 #include <linux/rbtree.h>
13
14 static 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
37 static 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
60 void 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
125 static 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
211 void 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  */
281 struct 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
293 struct 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
305 struct 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
333 struct 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
357 void 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 }