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