3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 rb_get_first and rb_get_next written by Theodore Ts'o, 9/8/2002
24 #include <liblustre.h>
25 #include <linux/rbtree.h>
27 static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
29 rb_node_t * right = node->rb_right;
31 if ((node->rb_right = right->rb_left))
32 right->rb_left->rb_parent = node;
33 right->rb_left = node;
35 if ((right->rb_parent = node->rb_parent))
37 if (node == node->rb_parent->rb_left)
38 node->rb_parent->rb_left = right;
40 node->rb_parent->rb_right = right;
43 root->rb_node = right;
44 node->rb_parent = right;
47 static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
49 rb_node_t * left = node->rb_left;
51 if ((node->rb_left = left->rb_right))
52 left->rb_right->rb_parent = node;
53 left->rb_right = node;
55 if ((left->rb_parent = node->rb_parent))
57 if (node == node->rb_parent->rb_right)
58 node->rb_parent->rb_right = left;
60 node->rb_parent->rb_left = left;
64 node->rb_parent = left;
67 void rb_insert_color(rb_node_t * node, rb_root_t * root)
69 rb_node_t * parent, * gparent;
71 while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
73 gparent = parent->rb_parent;
75 if (parent == gparent->rb_left)
78 register rb_node_t * uncle = gparent->rb_right;
79 if (uncle && uncle->rb_color == RB_RED)
81 uncle->rb_color = RB_BLACK;
82 parent->rb_color = RB_BLACK;
83 gparent->rb_color = RB_RED;
89 if (parent->rb_right == node)
91 register rb_node_t * tmp;
92 __rb_rotate_left(parent, root);
98 parent->rb_color = RB_BLACK;
99 gparent->rb_color = RB_RED;
100 __rb_rotate_right(gparent, root);
103 register rb_node_t * uncle = gparent->rb_left;
104 if (uncle && uncle->rb_color == RB_RED)
106 uncle->rb_color = RB_BLACK;
107 parent->rb_color = RB_BLACK;
108 gparent->rb_color = RB_RED;
114 if (parent->rb_left == node)
116 register rb_node_t * tmp;
117 __rb_rotate_right(parent, root);
123 parent->rb_color = RB_BLACK;
124 gparent->rb_color = RB_RED;
125 __rb_rotate_left(gparent, root);
129 root->rb_node->rb_color = RB_BLACK;
131 EXPORT_SYMBOL(rb_insert_color);
133 static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
138 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
140 if (parent->rb_left == node)
142 other = parent->rb_right;
143 if (other->rb_color == RB_RED)
145 other->rb_color = RB_BLACK;
146 parent->rb_color = RB_RED;
147 __rb_rotate_left(parent, root);
148 other = parent->rb_right;
150 if ((!other->rb_left ||
151 other->rb_left->rb_color == RB_BLACK)
152 && (!other->rb_right ||
153 other->rb_right->rb_color == RB_BLACK))
155 other->rb_color = RB_RED;
157 parent = node->rb_parent;
161 if (!other->rb_right ||
162 other->rb_right->rb_color == RB_BLACK)
164 register rb_node_t * o_left;
165 if ((o_left = other->rb_left))
166 o_left->rb_color = RB_BLACK;
167 other->rb_color = RB_RED;
168 __rb_rotate_right(other, root);
169 other = parent->rb_right;
171 other->rb_color = parent->rb_color;
172 parent->rb_color = RB_BLACK;
174 other->rb_right->rb_color = RB_BLACK;
175 __rb_rotate_left(parent, root);
176 node = root->rb_node;
182 other = parent->rb_left;
183 if (other->rb_color == RB_RED)
185 other->rb_color = RB_BLACK;
186 parent->rb_color = RB_RED;
187 __rb_rotate_right(parent, root);
188 other = parent->rb_left;
190 if ((!other->rb_left ||
191 other->rb_left->rb_color == RB_BLACK)
192 && (!other->rb_right ||
193 other->rb_right->rb_color == RB_BLACK))
195 other->rb_color = RB_RED;
197 parent = node->rb_parent;
201 if (!other->rb_left ||
202 other->rb_left->rb_color == RB_BLACK)
204 register rb_node_t * o_right;
205 if ((o_right = other->rb_right))
206 o_right->rb_color = RB_BLACK;
207 other->rb_color = RB_RED;
208 __rb_rotate_left(other, root);
209 other = parent->rb_left;
211 other->rb_color = parent->rb_color;
212 parent->rb_color = RB_BLACK;
214 other->rb_left->rb_color = RB_BLACK;
215 __rb_rotate_right(parent, root);
216 node = root->rb_node;
222 node->rb_color = RB_BLACK;
225 void rb_erase(rb_node_t * node, rb_root_t * root)
227 rb_node_t * child, * parent;
231 child = node->rb_right;
232 else if (!node->rb_right)
233 child = node->rb_left;
236 rb_node_t * old = node, * left;
238 node = node->rb_right;
239 while ((left = node->rb_left))
241 child = node->rb_right;
242 parent = node->rb_parent;
243 color = node->rb_color;
246 child->rb_parent = parent;
249 if (parent->rb_left == node)
250 parent->rb_left = child;
252 parent->rb_right = child;
255 root->rb_node = child;
257 if (node->rb_parent == old)
259 node->rb_parent = old->rb_parent;
260 node->rb_color = old->rb_color;
261 node->rb_right = old->rb_right;
262 node->rb_left = old->rb_left;
266 if (old->rb_parent->rb_left == old)
267 old->rb_parent->rb_left = node;
269 old->rb_parent->rb_right = node;
271 root->rb_node = node;
273 old->rb_left->rb_parent = node;
275 old->rb_right->rb_parent = node;
279 parent = node->rb_parent;
280 color = node->rb_color;
283 child->rb_parent = parent;
286 if (parent->rb_left == node)
287 parent->rb_left = child;
289 parent->rb_right = child;
292 root->rb_node = child;
295 if (color == RB_BLACK)
296 __rb_erase_color(child, parent, root);
298 EXPORT_SYMBOL(rb_erase);
301 * This function returns the first node (in sort order) of the tree.
303 rb_node_t *rb_get_first(rb_root_t *root)
314 EXPORT_SYMBOL(rb_get_first);
317 * Given a node, this function will return the next node in the tree.
319 rb_node_t *rb_get_next(rb_node_t *n)
329 while ((parent = n->rb_parent)) {
330 if (n == parent->rb_left)
337 EXPORT_SYMBOL(rb_get_next);