• 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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 = rb_parent(node);
29 
30 	if ((node->rb_right = right->rb_left))
31 		rb_set_parent(right->rb_left, node);
32 	right->rb_left = node;
33 
34 	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 	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 = rb_parent(node);
52 
53 	if ((node->rb_left = left->rb_right))
54 		rb_set_parent(left->rb_right, node);
55 	left->rb_right = node;
56 
57 	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 	rb_set_parent(node, left);
69 }
70 
rb_insert_color(struct rb_node * node,struct rb_root * root)71 void rb_insert_color(struct rb_node *node, struct rb_root *root)
72 {
73 	struct rb_node *parent, *gparent;
74 
75 	while ((parent = rb_parent(node)) && rb_is_red(parent))
76 	{
77 		gparent = rb_parent(parent);
78 
79 		if (parent == gparent->rb_left)
80 		{
81 			{
82 				register struct rb_node *uncle = gparent->rb_right;
83 				if (uncle && rb_is_red(uncle))
84 				{
85 					rb_set_black(uncle);
86 					rb_set_black(parent);
87 					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 			rb_set_black(parent);
103 			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 && rb_is_red(uncle))
109 				{
110 					rb_set_black(uncle);
111 					rb_set_black(parent);
112 					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 			rb_set_black(parent);
128 			rb_set_red(gparent);
129 			__rb_rotate_left(gparent, root);
130 		}
131 	}
132 
133 	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 || rb_is_black(node)) && node != root->rb_node)
142 	{
143 		if (parent->rb_left == node)
144 		{
145 			other = parent->rb_right;
146 			if (rb_is_red(other))
147 			{
148 				rb_set_black(other);
149 				rb_set_red(parent);
150 				__rb_rotate_left(parent, root);
151 				other = parent->rb_right;
152 			}
153 			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
154 			    (!other->rb_right || rb_is_black(other->rb_right)))
155 			{
156 				rb_set_red(other);
157 				node = parent;
158 				parent = rb_parent(node);
159 			}
160 			else
161 			{
162 				if (!other->rb_right || rb_is_black(other->rb_right))
163 				{
164 					struct rb_node *o_left;
165 					if ((o_left = other->rb_left))
166 						rb_set_black(o_left);
167 					rb_set_red(other);
168 					__rb_rotate_right(other, root);
169 					other = parent->rb_right;
170 				}
171 				rb_set_color(other, rb_color(parent));
172 				rb_set_black(parent);
173 				if (other->rb_right)
174 					rb_set_black(other->rb_right);
175 				__rb_rotate_left(parent, root);
176 				node = root->rb_node;
177 				break;
178 			}
179 		}
180 		else
181 		{
182 			other = parent->rb_left;
183 			if (rb_is_red(other))
184 			{
185 				rb_set_black(other);
186 				rb_set_red(parent);
187 				__rb_rotate_right(parent, root);
188 				other = parent->rb_left;
189 			}
190 			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
191 			    (!other->rb_right || rb_is_black(other->rb_right)))
192 			{
193 				rb_set_red(other);
194 				node = parent;
195 				parent = rb_parent(node);
196 			}
197 			else
198 			{
199 				if (!other->rb_left || rb_is_black(other->rb_left))
200 				{
201 					register struct rb_node *o_right;
202 					if ((o_right = other->rb_right))
203 						rb_set_black(o_right);
204 					rb_set_red(other);
205 					__rb_rotate_left(other, root);
206 					other = parent->rb_left;
207 				}
208 				rb_set_color(other, rb_color(parent));
209 				rb_set_black(parent);
210 				if (other->rb_left)
211 					rb_set_black(other->rb_left);
212 				__rb_rotate_right(parent, root);
213 				node = root->rb_node;
214 				break;
215 			}
216 		}
217 	}
218 	if (node)
219 		rb_set_black(node);
220 }
221 
rb_erase(struct rb_node * node,struct rb_root * root)222 void rb_erase(struct rb_node *node, struct rb_root *root)
223 {
224 	struct rb_node *child, *parent;
225 	int color;
226 
227 	if (!node->rb_left)
228 		child = node->rb_right;
229 	else if (!node->rb_right)
230 		child = node->rb_left;
231 	else
232 	{
233 		struct rb_node *old = node, *left;
234 
235 		node = node->rb_right;
236 		while ((left = node->rb_left) != NULL)
237 			node = left;
238 		child = node->rb_right;
239 		parent = rb_parent(node);
240 		color = rb_color(node);
241 
242 		if (child)
243 			rb_set_parent(child, parent);
244 		if (parent == old) {
245 			parent->rb_right = child;
246 			parent = node;
247 		} else
248 			parent->rb_left = child;
249 
250 		node->rb_parent_color = old->rb_parent_color;
251 		node->rb_right = old->rb_right;
252 		node->rb_left = old->rb_left;
253 
254 		if (rb_parent(old))
255 		{
256 			if (rb_parent(old)->rb_left == old)
257 				rb_parent(old)->rb_left = node;
258 			else
259 				rb_parent(old)->rb_right = node;
260 		} else
261 			root->rb_node = node;
262 
263 		rb_set_parent(old->rb_left, node);
264 		if (old->rb_right)
265 			rb_set_parent(old->rb_right, node);
266 		goto color;
267 	}
268 
269 	parent = rb_parent(node);
270 	color = rb_color(node);
271 
272 	if (child)
273 		rb_set_parent(child, parent);
274 	if (parent)
275 	{
276 		if (parent->rb_left == node)
277 			parent->rb_left = child;
278 		else
279 			parent->rb_right = child;
280 	}
281 	else
282 		root->rb_node = child;
283 
284  color:
285 	if (color == RB_BLACK)
286 		__rb_erase_color(child, parent, root);
287 }
288 
289 /*
290  * This function returns the first node (in sort order) of the tree.
291  */
rb_first(struct rb_root * root)292 struct rb_node *rb_first(struct rb_root *root)
293 {
294 	struct rb_node	*n;
295 
296 	n = root->rb_node;
297 	if (!n)
298 		return NULL;
299 	while (n->rb_left)
300 		n = n->rb_left;
301 	return n;
302 }
303 
rb_next(const struct rb_node * node)304 struct rb_node *rb_next(const struct rb_node *node)
305 {
306 	struct rb_node *parent;
307 
308 	if (RB_EMPTY_NODE(node))
309 		return NULL;
310 
311 	/*
312 	 * If we have a right-hand child, go down and then left as far
313 	 * as we can.
314 	 */
315 	if (node->rb_right) {
316 		node = node->rb_right;
317 		while (node->rb_left)
318 			node=node->rb_left;
319 		return (struct rb_node *)node;
320 	}
321 
322 	/*
323 	 * No right-hand children. Everything down and left is smaller than us,
324 	 * so any 'next' node must be in the general direction of our parent.
325 	 * Go up the tree; any time the ancestor is a right-hand child of its
326 	 * parent, keep going up. First time it's a left-hand child of its
327 	 * parent, said parent is our 'next' node.
328 	 */
329 	while ((parent = rb_parent(node)) && node == parent->rb_right)
330 		node = parent;
331 
332 	return parent;
333 }
334