]>
git.ipfire.org Git - people/ms/u-boot.git/blob - lib/rbtree.c
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
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.
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.
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
23 #include <ubi_uboot.h>
24 #include <linux/rbtree.h>
26 static void __rb_rotate_left(struct rb_node
*node
, struct rb_root
*root
)
28 struct rb_node
*right
= node
->rb_right
;
29 struct rb_node
*parent
= rb_parent(node
);
31 if ((node
->rb_right
= right
->rb_left
))
32 rb_set_parent(right
->rb_left
, node
);
33 right
->rb_left
= node
;
35 rb_set_parent(right
, parent
);
39 if (node
== parent
->rb_left
)
40 parent
->rb_left
= right
;
42 parent
->rb_right
= right
;
45 root
->rb_node
= right
;
46 rb_set_parent(node
, right
);
49 static void __rb_rotate_right(struct rb_node
*node
, struct rb_root
*root
)
51 struct rb_node
*left
= node
->rb_left
;
52 struct rb_node
*parent
= rb_parent(node
);
54 if ((node
->rb_left
= left
->rb_right
))
55 rb_set_parent(left
->rb_right
, node
);
56 left
->rb_right
= node
;
58 rb_set_parent(left
, parent
);
62 if (node
== parent
->rb_right
)
63 parent
->rb_right
= left
;
65 parent
->rb_left
= left
;
69 rb_set_parent(node
, left
);
72 void rb_insert_color(struct rb_node
*node
, struct rb_root
*root
)
74 struct rb_node
*parent
, *gparent
;
76 while ((parent
= rb_parent(node
)) && rb_is_red(parent
))
78 gparent
= rb_parent(parent
);
80 if (parent
== gparent
->rb_left
)
83 register struct rb_node
*uncle
= gparent
->rb_right
;
84 if (uncle
&& rb_is_red(uncle
))
94 if (parent
->rb_right
== node
)
96 register struct rb_node
*tmp
;
97 __rb_rotate_left(parent
, root
);
103 rb_set_black(parent
);
105 __rb_rotate_right(gparent
, root
);
108 register struct rb_node
*uncle
= gparent
->rb_left
;
109 if (uncle
&& rb_is_red(uncle
))
112 rb_set_black(parent
);
119 if (parent
->rb_left
== node
)
121 register struct rb_node
*tmp
;
122 __rb_rotate_right(parent
, root
);
128 rb_set_black(parent
);
130 __rb_rotate_left(gparent
, root
);
134 rb_set_black(root
->rb_node
);
137 static void __rb_erase_color(struct rb_node
*node
, struct rb_node
*parent
,
138 struct rb_root
*root
)
140 struct rb_node
*other
;
142 while ((!node
|| rb_is_black(node
)) && node
!= root
->rb_node
)
144 if (parent
->rb_left
== node
)
146 other
= parent
->rb_right
;
147 if (rb_is_red(other
))
151 __rb_rotate_left(parent
, root
);
152 other
= parent
->rb_right
;
154 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
155 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
159 parent
= rb_parent(node
);
163 if (!other
->rb_right
|| rb_is_black(other
->rb_right
))
165 struct rb_node
*o_left
;
166 if ((o_left
= other
->rb_left
))
167 rb_set_black(o_left
);
169 __rb_rotate_right(other
, root
);
170 other
= parent
->rb_right
;
172 rb_set_color(other
, rb_color(parent
));
173 rb_set_black(parent
);
175 rb_set_black(other
->rb_right
);
176 __rb_rotate_left(parent
, root
);
177 node
= root
->rb_node
;
183 other
= parent
->rb_left
;
184 if (rb_is_red(other
))
188 __rb_rotate_right(parent
, root
);
189 other
= parent
->rb_left
;
191 if ((!other
->rb_left
|| rb_is_black(other
->rb_left
)) &&
192 (!other
->rb_right
|| rb_is_black(other
->rb_right
)))
196 parent
= rb_parent(node
);
200 if (!other
->rb_left
|| rb_is_black(other
->rb_left
))
202 register struct rb_node
*o_right
;
203 if ((o_right
= other
->rb_right
))
204 rb_set_black(o_right
);
206 __rb_rotate_left(other
, root
);
207 other
= parent
->rb_left
;
209 rb_set_color(other
, rb_color(parent
));
210 rb_set_black(parent
);
212 rb_set_black(other
->rb_left
);
213 __rb_rotate_right(parent
, root
);
214 node
= root
->rb_node
;
223 void rb_erase(struct rb_node
*node
, struct rb_root
*root
)
225 struct rb_node
*child
, *parent
;
229 child
= node
->rb_right
;
230 else if (!node
->rb_right
)
231 child
= node
->rb_left
;
234 struct rb_node
*old
= node
, *left
;
236 node
= node
->rb_right
;
237 while ((left
= node
->rb_left
) != NULL
)
239 child
= node
->rb_right
;
240 parent
= rb_parent(node
);
241 color
= rb_color(node
);
244 rb_set_parent(child
, parent
);
246 parent
->rb_right
= child
;
249 parent
->rb_left
= child
;
251 node
->rb_parent_color
= old
->rb_parent_color
;
252 node
->rb_right
= old
->rb_right
;
253 node
->rb_left
= old
->rb_left
;
257 if (rb_parent(old
)->rb_left
== old
)
258 rb_parent(old
)->rb_left
= node
;
260 rb_parent(old
)->rb_right
= node
;
262 root
->rb_node
= node
;
264 rb_set_parent(old
->rb_left
, node
);
266 rb_set_parent(old
->rb_right
, node
);
270 parent
= rb_parent(node
);
271 color
= rb_color(node
);
274 rb_set_parent(child
, parent
);
277 if (parent
->rb_left
== node
)
278 parent
->rb_left
= child
;
280 parent
->rb_right
= child
;
283 root
->rb_node
= child
;
286 if (color
== RB_BLACK
)
287 __rb_erase_color(child
, parent
, root
);
291 * This function returns the first node (in sort order) of the tree.
293 struct rb_node
*rb_first(struct rb_root
*root
)
305 struct rb_node
*rb_last(struct rb_root
*root
)
317 struct rb_node
*rb_next(struct rb_node
*node
)
319 struct rb_node
*parent
;
321 if (rb_parent(node
) == node
)
324 /* If we have a right-hand child, go down and then left as far
326 if (node
->rb_right
) {
327 node
= node
->rb_right
;
328 while (node
->rb_left
)
333 /* No right-hand children. Everything down and left is
334 smaller than us, so any 'next' node must be in the general
335 direction of our parent. Go up the tree; any time the
336 ancestor is a right-hand child of its parent, keep going
337 up. First time it's a left-hand child of its parent, said
338 parent is our 'next' node. */
339 while ((parent
= rb_parent(node
)) && node
== parent
->rb_right
)
345 struct rb_node
*rb_prev(struct rb_node
*node
)
347 struct rb_node
*parent
;
349 if (rb_parent(node
) == node
)
352 /* If we have a left-hand child, go down and then right as far
355 node
= node
->rb_left
;
356 while (node
->rb_right
)
361 /* No left-hand children. Go up till we find an ancestor which
362 is a right-hand child of its parent */
363 while ((parent
= rb_parent(node
)) && node
== parent
->rb_left
)
369 void rb_replace_node(struct rb_node
*victim
, struct rb_node
*new,
370 struct rb_root
*root
)
372 struct rb_node
*parent
= rb_parent(victim
);
374 /* Set the surrounding nodes to point to the replacement */
376 if (victim
== parent
->rb_left
)
377 parent
->rb_left
= new;
379 parent
->rb_right
= new;
384 rb_set_parent(victim
->rb_left
, new);
385 if (victim
->rb_right
)
386 rb_set_parent(victim
->rb_right
, new);
388 /* Copy the pointers/colour from the victim to the replacement */