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