1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#include <linux/rbtree.h>
23
24static void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
25{
26 rb_node_t * right = node->rb_right;
27
28 if ((node->rb_right = right->rb_left))
29 right->rb_left->rb_parent = node;
30 right->rb_left = node;
31
32 if ((right->rb_parent = node->rb_parent))
33 {
34 if (node == node->rb_parent->rb_left)
35 node->rb_parent->rb_left = right;
36 else
37 node->rb_parent->rb_right = right;
38 }
39 else
40 root->rb_node = right;
41 node->rb_parent = right;
42}
43
44static void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
45{
46 rb_node_t * left = node->rb_left;
47
48 if ((node->rb_left = left->rb_right))
49 left->rb_right->rb_parent = node;
50 left->rb_right = node;
51
52 if ((left->rb_parent = node->rb_parent))
53 {
54 if (node == node->rb_parent->rb_right)
55 node->rb_parent->rb_right = left;
56 else
57 node->rb_parent->rb_left = left;
58 }
59 else
60 root->rb_node = left;
61 node->rb_parent = left;
62}
63
64void rb_insert_color(rb_node_t * node, rb_root_t * root)
65{
66 rb_node_t * parent, * gparent;
67
68 while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
69 {
70 gparent = parent->rb_parent;
71
72 if (parent == gparent->rb_left)
73 {
74 {
75 register rb_node_t * uncle = gparent->rb_right;
76 if (uncle && uncle->rb_color == RB_RED)
77 {
78 uncle->rb_color = RB_BLACK;
79 parent->rb_color = RB_BLACK;
80 gparent->rb_color = RB_RED;
81 node = gparent;
82 continue;
83 }
84 }
85
86 if (parent->rb_right == node)
87 {
88 register rb_node_t * tmp;
89 __rb_rotate_left(parent, root);
90 tmp = parent;
91 parent = node;
92 node = tmp;
93 }
94
95 parent->rb_color = RB_BLACK;
96 gparent->rb_color = RB_RED;
97 __rb_rotate_right(gparent, root);
98 } else {
99 {
100 register rb_node_t * uncle = gparent->rb_left;
101 if (uncle && uncle->rb_color == RB_RED)
102 {
103 uncle->rb_color = RB_BLACK;
104 parent->rb_color = RB_BLACK;
105 gparent->rb_color = RB_RED;
106 node = gparent;
107 continue;
108 }
109 }
110
111 if (parent->rb_left == node)
112 {
113 register rb_node_t * tmp;
114 __rb_rotate_right(parent, root);
115 tmp = parent;
116 parent = node;
117 node = tmp;
118 }
119
120 parent->rb_color = RB_BLACK;
121 gparent->rb_color = RB_RED;
122 __rb_rotate_left(gparent, root);
123 }
124 }
125
126 root->rb_node->rb_color = RB_BLACK;
127}
128
129static void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
130 rb_root_t * root)
131{
132 rb_node_t * other;
133
134 while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
135 {
136 if (parent->rb_left == node)
137 {
138 other = parent->rb_right;
139 if (other->rb_color == RB_RED)
140 {
141 other->rb_color = RB_BLACK;
142 parent->rb_color = RB_RED;
143 __rb_rotate_left(parent, root);
144 other = parent->rb_right;
145 }
146 if ((!other->rb_left ||
147 other->rb_left->rb_color == RB_BLACK)
148 && (!other->rb_right ||
149 other->rb_right->rb_color == RB_BLACK))
150 {
151 other->rb_color = RB_RED;
152 node = parent;
153 parent = node->rb_parent;
154 }
155 else
156 {
157 if (!other->rb_right ||
158 other->rb_right->rb_color == RB_BLACK)
159 {
160 register rb_node_t * o_left;
161 if ((o_left = other->rb_left))
162 o_left->rb_color = RB_BLACK;
163 other->rb_color = RB_RED;
164 __rb_rotate_right(other, root);
165 other = parent->rb_right;
166 }
167 other->rb_color = parent->rb_color;
168 parent->rb_color = RB_BLACK;
169 if (other->rb_right)
170 other->rb_right->rb_color = RB_BLACK;
171 __rb_rotate_left(parent, root);
172 node = root->rb_node;
173 break;
174 }
175 }
176 else
177 {
178 other = parent->rb_left;
179 if (other->rb_color == RB_RED)
180 {
181 other->rb_color = RB_BLACK;
182 parent->rb_color = RB_RED;
183 __rb_rotate_right(parent, root);
184 other = parent->rb_left;
185 }
186 if ((!other->rb_left ||
187 other->rb_left->rb_color == RB_BLACK)
188 && (!other->rb_right ||
189 other->rb_right->rb_color == RB_BLACK))
190 {
191 other->rb_color = RB_RED;
192 node = parent;
193 parent = node->rb_parent;
194 }
195 else
196 {
197 if (!other->rb_left ||
198 other->rb_left->rb_color == RB_BLACK)
199 {
200 register rb_node_t * o_right;
201 if ((o_right = other->rb_right))
202 o_right->rb_color = RB_BLACK;
203 other->rb_color = RB_RED;
204 __rb_rotate_left(other, root);
205 other = parent->rb_left;
206 }
207 other->rb_color = parent->rb_color;
208 parent->rb_color = RB_BLACK;
209 if (other->rb_left)
210 other->rb_left->rb_color = RB_BLACK;
211 __rb_rotate_right(parent, root);
212 node = root->rb_node;
213 break;
214 }
215 }
216 }
217 if (node)
218 node->rb_color = RB_BLACK;
219}
220
221void rb_erase(rb_node_t * node, rb_root_t * root)
222{
223 rb_node_t * child, * parent;
224 int color;
225
226 if (!node->rb_left)
227 child = node->rb_right;
228 else if (!node->rb_right)
229 child = node->rb_left;
230 else
231 {
232 rb_node_t * old = node, * left;
233
234 node = node->rb_right;
235 while ((left = node->rb_left))
236 node = left;
237 child = node->rb_right;
238 parent = node->rb_parent;
239 color = node->rb_color;
240
241 if (child)
242 child->rb_parent = parent;
243 if (parent)
244 {
245 if (parent->rb_left == node)
246 parent->rb_left = child;
247 else
248 parent->rb_right = child;
249 }
250 else
251 root->rb_node = child;
252
253 if (node->rb_parent == old)
254 parent = node;
255 node->rb_parent = old->rb_parent;
256 node->rb_color = old->rb_color;
257 node->rb_right = old->rb_right;
258 node->rb_left = old->rb_left;
259
260 if (old->rb_parent)
261 {
262 if (old->rb_parent->rb_left == old)
263 old->rb_parent->rb_left = node;
264 else
265 old->rb_parent->rb_right = node;
266 } else
267 root->rb_node = node;
268
269 old->rb_left->rb_parent = node;
270 if (old->rb_right)
271 old->rb_right->rb_parent = node;
272 goto color;
273 }
274
275 parent = node->rb_parent;
276 color = node->rb_color;
277
278 if (child)
279 child->rb_parent = parent;
280 if (parent)
281 {
282 if (parent->rb_left == node)
283 parent->rb_left = child;
284 else
285 parent->rb_right = child;
286 }
287 else
288 root->rb_node = child;
289
290 color:
291 if (color == RB_BLACK)
292 __rb_erase_color(child, parent, root);
293}
294
