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 <libcfs/libcfs.h>
25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27 struct rb_node *right = node->rb_right;
28 struct rb_node *parent = rb_parent(node);
30 node->rb_right = right->rb_left;
31 if (node->rb_right != NULL)
32 rb_set_parent(right->rb_left, node);
33 right->rb_left = node;
35 rb_set_parent(right, parent);
38 if (node == parent->rb_left)
39 parent->rb_left = right;
41 parent->rb_right = right;
43 root->rb_node = right;
44 rb_set_parent(node, right);
47 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
49 struct rb_node *left = node->rb_left;
50 struct rb_node *parent = rb_parent(node);
52 node->rb_left = left->rb_right;
53 if (node->rb_left != NULL)
54 rb_set_parent(left->rb_right, node);
55 left->rb_right = node;
57 rb_set_parent(left, parent);
60 if (node == parent->rb_right)
61 parent->rb_right = left;
63 parent->rb_left = left;
66 rb_set_parent(node, left);
69 void rb_insert_color(struct rb_node *node, struct rb_root *root)
71 struct rb_node *parent, *gparent;
73 while ((parent = rb_parent(node)) != NULL && rb_is_red(parent)) {
74 gparent = rb_parent(parent);
76 if (parent == gparent->rb_left) {
77 register struct rb_node *uncle = gparent->rb_right;
78 if (uncle && rb_is_red(uncle)) {
86 if (parent->rb_right == node) {
87 register struct rb_node *tmp;
88 __rb_rotate_left(parent, root);
96 __rb_rotate_right(gparent, root);
98 register struct rb_node *uncle = gparent->rb_left;
99 if (uncle && rb_is_red(uncle)) {
101 rb_set_black(parent);
107 if (parent->rb_left == node) {
108 register struct rb_node *tmp;
109 __rb_rotate_right(parent, root);
115 rb_set_black(parent);
117 __rb_rotate_left(gparent, root);
121 rb_set_black(root->rb_node);
124 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
125 struct rb_root *root)
129 while ((!node || rb_is_black(node)) && node != root->rb_node) {
130 if (parent->rb_left == node) {
131 ptr = parent->rb_right;
132 if (rb_is_red(ptr)) {
135 __rb_rotate_left(parent, root);
136 ptr = parent->rb_right;
138 if ((!ptr->rb_left || rb_is_black(ptr->rb_left)) &&
139 (!ptr->rb_right || rb_is_black(ptr->rb_right))) {
142 parent = rb_parent(node);
144 if (!ptr->rb_right ||
145 rb_is_black(ptr->rb_right)) {
146 rb_set_black(ptr->rb_left);
148 __rb_rotate_right(ptr, root);
149 ptr = parent->rb_right;
151 rb_set_color(ptr, rb_color(parent));
152 rb_set_black(parent);
153 rb_set_black(ptr->rb_right);
154 __rb_rotate_left(parent, root);
155 node = root->rb_node;
159 ptr = parent->rb_left;
160 if (rb_is_red(ptr)) {
163 __rb_rotate_right(parent, root);
164 ptr = parent->rb_left;
166 if ((!ptr->rb_left || rb_is_black(ptr->rb_left)) &&
167 (!ptr->rb_right || rb_is_black(ptr->rb_right))) {
170 parent = rb_parent(node);
173 rb_is_black(ptr->rb_left)) {
174 rb_set_black(ptr->rb_right);
176 __rb_rotate_left(ptr, root);
177 ptr = parent->rb_left;
179 rb_set_color(ptr, rb_color(parent));
180 rb_set_black(parent);
181 rb_set_black(ptr->rb_left);
182 __rb_rotate_right(parent, root);
183 node = root->rb_node;
192 void rb_erase(struct rb_node *node, struct rb_root *root)
194 struct rb_node *child, *parent;
198 child = node->rb_right;
199 else if (!node->rb_right)
200 child = node->rb_left;
202 struct rb_node *old = node, *left;
204 node = node->rb_right;
205 while ((left = node->rb_left) != NULL)
208 if (rb_parent(old)) {
209 if (rb_parent(old)->rb_left == old)
210 rb_parent(old)->rb_left = node;
212 rb_parent(old)->rb_right = node;
214 root->rb_node = node;
216 child = node->rb_right;
217 parent = rb_parent(node);
218 color = rb_color(node);
224 rb_set_parent(child, parent);
225 parent->rb_left = child;
227 node->rb_right = old->rb_right;
228 rb_set_parent(old->rb_right, node);
231 node->rb_parent_color = old->rb_parent_color;
232 node->rb_left = old->rb_left;
233 rb_set_parent(old->rb_left, node);
238 parent = rb_parent(node);
239 color = rb_color(node);
242 rb_set_parent(child, parent);
244 if (parent->rb_left == node)
245 parent->rb_left = child;
247 parent->rb_right = child;
249 root->rb_node = child;
252 if (color == RB_BLACK)
253 __rb_erase_color(child, parent, root);
257 * This function returns the first node (in sort order) of the tree.
259 struct rb_node *rb_first(const struct rb_root *root)
271 struct rb_node *rb_last(const struct rb_root *root)
283 struct rb_node *rb_next(const struct rb_node *node)
285 struct rb_node *parent;
287 if (rb_parent(node) == node)
290 /* If we have a right-hand child, go down and then left as far
292 if (node->rb_right) {
293 node = node->rb_right;
294 while (node->rb_left)
295 node = node->rb_left;
296 return (struct rb_node *)node;
299 /* No right-hand children. Everything down and left is
300 smaller than us, so any 'next' node must be in the general
301 direction of our parent. Go up the tree; any time the
302 ancestor is a right-hand child of its parent, keep going
303 up. First time it's a left-hand child of its parent, said
304 parent is our 'next' node. */
305 while ((parent = rb_parent(node)) && node == parent->rb_right)
311 struct rb_node *rb_prev(const struct rb_node *node)
313 struct rb_node *parent;
315 if (rb_parent(node) == node)
318 /* If we have a left-hand child, go down and then right as far
321 node = node->rb_left;
322 while (node->rb_right)
323 node = node->rb_right;
324 return (struct rb_node *)node;
327 /* No left-hand children. Go up till we find an ancestor which
328 is a right-hand child of its parent */
329 while ((parent = rb_parent(node)) && node == parent->rb_left)