1/*
2 * Copyright 2016, NICTA
3 *
4 * This software may be distributed and modified according to the terms of
5 * the GNU General Public License version 2. Note that NO WARRANTY is provided.
6 * See "LICENSE_GPLv2.txt" for details.
7 *
8 * @TAG(NICTA_GPL)
9 */
10
11/*
12  Red Black Trees
13  (C) 1999  Andrea Arcangeli <andrea@suse.de>
14  (C) 2002  David Woodhouse <dwmw2@infradead.org>
15
16  This program is free software; you can redistribute it and/or modify
17  it under the terms of the GNU General Public License as published by
18  the Free Software Foundation; either version 2 of the License, or
19  (at your option) any later version.
20
21  This program is distributed in the hope that it will be useful,
22  but WITHOUT ANY WARRANTY; without even the implied warranty of
23  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
24  GNU General Public License for more details.
25
26  You should have received a copy of the GNU General Public License
27  along with this program; if not, write to the Free Software
28  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
29
30*/
31
32#include <lib/rbt.h>
33
34void rbt_link_node(struct rbt_node * node, struct rbt_node * parent,
35                  struct rbt_node ** rbt_link)
36{
37	node->rbt_parent_color = (unsigned long )parent;
38	node->rbt_left = NULL;
39	node->rbt_right = NULL;
40	*rbt_link = node;
41}
42
43static void __rbt_rotate_left(struct rbt_node *node, struct rbt_root *rbt)
44{
45	struct rbt_node *right = node->rbt_right;
46	struct rbt_node *parent = rbt_parent(node);
47
48        node->rbt_right = right->rbt_left;
49	if (node->rbt_right)
50		rbt_set_parent(right->rbt_left, node);
51	right->rbt_left = node;
52
53	rbt_set_parent(right, parent);
54
55	if (parent)
56	{
57		if (node == parent->rbt_left)
58			parent->rbt_left = right;
59		else
60			parent->rbt_right = right;
61	}
62	else
63		rbt->root = right;
64	rbt_set_parent(node, right);
65}
66
67static void __rbt_rotate_right(struct rbt_node *node, struct rbt_root *rbt)
68{
69	struct rbt_node *left = node->rbt_left;
70	struct rbt_node *parent = rbt_parent(node);
71
72        node->rbt_left = left->rbt_right;
73	if (node->rbt_left)
74		rbt_set_parent(left->rbt_right, node);
75	left->rbt_right = node;
76
77	rbt_set_parent(left, parent);
78
79	if (parent)
80	{
81		if (node == parent->rbt_right)
82			parent->rbt_right = left;
83		else
84			parent->rbt_left = left;
85	}
86	else
87		rbt->root = left;
88	rbt_set_parent(node, left);
89}
90
91void rbt_insert_color(struct rbt_node *node, struct rbt_root *rbt)
92{
93	struct rbt_node *parent, *gparent;
94
95	for (parent = rbt_parent(node); parent && rbt_is_red(parent); parent = rbt_parent(node))
96	{
97		gparent = rbt_parent(parent);
98
99		if (parent == gparent->rbt_left)
100		{
101			{
102				register struct rbt_node *uncle = gparent->rbt_right;
103				if (uncle && rbt_is_red(uncle))
104				{
105					rbt_set_black(uncle);
106					rbt_set_black(parent);
107					rbt_set_red(gparent);
108					node = gparent;
109					continue;
110				}
111			}
112
113			if (parent->rbt_right == node)
114			{
115				register struct rbt_node *tmp;
116				__rbt_rotate_left(parent, rbt);
117				tmp = parent;
118				parent = node;
119				node = tmp;
120			}
121
122			rbt_set_black(parent);
123			rbt_set_red(gparent);
124			__rbt_rotate_right(gparent, rbt);
125		} else {
126			{
127				register struct rbt_node *uncle = gparent->rbt_left;
128				if (uncle && rbt_is_red(uncle))
129				{
130					rbt_set_black(uncle);
131					rbt_set_black(parent);
132					rbt_set_red(gparent);
133					node = gparent;
134					continue;
135				}
136			}
137
138			if (parent->rbt_left == node)
139			{
140				register struct rbt_node *tmp;
141				__rbt_rotate_right(parent, rbt);
142				tmp = parent;
143				parent = node;
144				node = tmp;
145			}
146
147			rbt_set_black(parent);
148			rbt_set_red(gparent);
149			__rbt_rotate_left(gparent, rbt);
150		}
151	}
152
153	rbt_set_black(rbt->root);
154}
155
156static void __rbt_erase_color(struct rbt_node *node, struct rbt_node *parent,
157			     struct rbt_root *rbt)
158{
159	struct rbt_node *other;
160
161	while ((!node || rbt_is_black(node)) && node != rbt->root)
162	{
163		if (parent->rbt_left == node)
164		{
165			other = parent->rbt_right;
166			if (rbt_is_red(other))
167			{
168				rbt_set_black(other);
169				rbt_set_red(parent);
170				__rbt_rotate_left(parent, rbt);
171				other = parent->rbt_right;
172			}
173			if ((!other->rbt_left || rbt_is_black(other->rbt_left)) &&
174			    (!other->rbt_right || rbt_is_black(other->rbt_right)))
175			{
176				rbt_set_red(other);
177				node = parent;
178				parent = rbt_parent(node);
179			}
180			else
181			{
182				if (!other->rbt_right || rbt_is_black(other->rbt_right))
183				{
184					rbt_set_black(other->rbt_left);
185					rbt_set_red(other);
186					__rbt_rotate_right(other, rbt);
187					other = parent->rbt_right;
188				}
189				rbt_set_color(other, rbt_color(parent));
190				rbt_set_black(parent);
191				rbt_set_black(other->rbt_right);
192				__rbt_rotate_left(parent, rbt);
193				node = rbt->root;
194				break;
195			}
196		}
197		else
198		{
199			other = parent->rbt_left;
200			if (rbt_is_red(other))
201			{
202				rbt_set_black(other);
203				rbt_set_red(parent);
204				__rbt_rotate_right(parent, rbt);
205				other = parent->rbt_left;
206			}
207			if ((!other->rbt_left || rbt_is_black(other->rbt_left)) &&
208			    (!other->rbt_right || rbt_is_black(other->rbt_right)))
209			{
210				rbt_set_red(other);
211				node = parent;
212				parent = rbt_parent(node);
213			}
214			else
215			{
216				if (!other->rbt_left || rbt_is_black(other->rbt_left))
217				{
218					rbt_set_black(other->rbt_right);
219					rbt_set_red(other);
220					__rbt_rotate_left(other, rbt);
221					other = parent->rbt_left;
222				}
223				rbt_set_color(other, rbt_color(parent));
224				rbt_set_black(parent);
225				rbt_set_black(other->rbt_left);
226				__rbt_rotate_right(parent, rbt);
227				node = rbt->root;
228				break;
229			}
230		}
231	}
232	if (node)
233		rbt_set_black(node);
234}
235
236void rbt_erase(struct rbt_node *node, struct rbt_root *rbt)
237{
238	struct rbt_node *child, *parent;
239	int color;
240
241	if (!node->rbt_left)
242		child = node->rbt_right;
243	else if (!node->rbt_right)
244		child = node->rbt_left;
245	else
246	{
247		struct rbt_node *old = node, *left;
248
249		node = node->rbt_right;
250		for (left = node->rbt_left; left != NULL; left = node->rbt_left)
251			node = left;
252
253		if (rbt_parent(old)) {
254			if (rbt_parent(old)->rbt_left == old)
255				rbt_parent(old)->rbt_left = node;
256			else
257				rbt_parent(old)->rbt_right = node;
258		} else
259			rbt->root = node;
260
261		child = node->rbt_right;
262		parent = rbt_parent(node);
263		color = rbt_color(node);
264
265		if (parent == old) {
266			parent = node;
267		} else {
268			if (child)
269				rbt_set_parent(child, parent);
270			parent->rbt_left = child;
271
272			node->rbt_right = old->rbt_right;
273			rbt_set_parent(old->rbt_right, node);
274		}
275
276		node->rbt_parent_color = old->rbt_parent_color;
277		node->rbt_left = old->rbt_left;
278		rbt_set_parent(old->rbt_left, node);
279
280                if (color == RBT_BLACK)
281                        __rbt_erase_color(child, parent, rbt);
282                return;
283	}
284
285	parent = rbt_parent(node);
286	color = rbt_color(node);
287
288	if (child)
289		rbt_set_parent(child, parent);
290	if (parent)
291	{
292		if (parent->rbt_left == node)
293			parent->rbt_left = child;
294		else
295			parent->rbt_right = child;
296	}
297	else
298		rbt->root = child;
299
300	if (color == RBT_BLACK)
301		__rbt_erase_color(child, parent, rbt);
302}
303