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