Line data Source code
1 : #ifndef __OSI_RBTREE_DOT_H__
2 : #define __OSI_RBTREE_DOT_H__
3 :
4 : #include <stdlib.h>
5 : #include <stddef.h>
6 : #include <assert.h>
7 :
8 : /* Adapted from the kernel's rbtree.c */
9 : struct osi_node {
10 : unsigned long osi_parent_color;
11 : #define OSI_RED 0
12 : #define OSI_BLACK 1
13 : struct osi_node *osi_left;
14 : struct osi_node *osi_right;
15 : };
16 :
17 : #define osi_parent(r) ((struct osi_node *)((r)->osi_parent_color & ~3))
18 : #define osi_color(r) ((r)->osi_parent_color & 1)
19 : #define osi_is_red(r) (!osi_color(r))
20 : #define osi_is_black(r) osi_color(r)
21 : #define osi_set_red(r) do { (r)->osi_parent_color &= ~1; } while (0)
22 : #define osi_set_black(r) do { (r)->osi_parent_color |= 1; } while (0)
23 : #define OSI_EMPTY_NODE(node) (osi_parent(node) == node)
24 :
25 : struct osi_root
26 : {
27 : struct osi_node *osi_node;
28 : };
29 :
30 : #define OSI_EMPTY_ROOT(root) ((root)->osi_node == NULL)
31 :
32 9331954 : static inline void osi_set_parent(struct osi_node *rb, struct osi_node *p)
33 : {
34 9331954 : rb->osi_parent_color = (rb->osi_parent_color & 3) | (unsigned long)p;
35 9331954 : }
36 :
37 27991 : static inline void osi_set_color(struct osi_node *rb, int color)
38 : {
39 27991 : rb->osi_parent_color = (rb->osi_parent_color & ~1) | color;
40 27991 : }
41 :
42 2138014 : static inline void osi_link_node(struct osi_node *node,
43 : struct osi_node *parent,
44 : struct osi_node **osi_link)
45 : {
46 2138014 : node->osi_parent_color = (unsigned long )parent;
47 2138014 : node->osi_left = node->osi_right = NULL;
48 :
49 2138014 : *osi_link = node;
50 2138014 : }
51 :
52 3110880 : static inline void __osi_rotate_left(struct osi_node *node,
53 : struct osi_root *root)
54 : {
55 3110880 : struct osi_node *right = node->osi_right;
56 3110880 : struct osi_node *parent = osi_parent(node);
57 :
58 3110880 : if ((node->osi_right = right->osi_left))
59 2043950 : osi_set_parent(right->osi_left, node);
60 3110880 : right->osi_left = node;
61 :
62 3110880 : osi_set_parent(right, parent);
63 :
64 3110880 : if (parent) {
65 3026608 : if (node == parent->osi_left)
66 982338 : parent->osi_left = right;
67 : else
68 2044270 : parent->osi_right = right;
69 : }
70 : else
71 84272 : root->osi_node = right;
72 3110880 : osi_set_parent(node, right);
73 3110880 : }
74 :
75 115 : static inline void __osi_rotate_right(struct osi_node *node,
76 : struct osi_root *root)
77 : {
78 115 : struct osi_node *left = node->osi_left;
79 115 : struct osi_node *parent = osi_parent(node);
80 :
81 115 : if ((node->osi_left = left->osi_right))
82 0 : osi_set_parent(left->osi_right, node);
83 115 : left->osi_right = node;
84 :
85 115 : osi_set_parent(left, parent);
86 :
87 115 : if (parent) {
88 115 : if (node == parent->osi_right)
89 115 : parent->osi_right = left;
90 : else
91 0 : parent->osi_left = left;
92 : } else
93 0 : root->osi_node = left;
94 115 : osi_set_parent(node, left);
95 115 : }
96 :
97 2138014 : static inline void osi_insert_color(struct osi_node *node,
98 : struct osi_root *root)
99 : {
100 : struct osi_node *parent, *gparent;
101 :
102 6259304 : while ((parent = osi_parent(node)) && osi_is_red(parent)) {
103 4121290 : gparent = osi_parent(parent);
104 :
105 4121290 : if (parent == gparent->osi_left) {
106 : {
107 0 : register struct osi_node *uncle = gparent->osi_right;
108 0 : if (uncle && osi_is_red(uncle)) {
109 0 : osi_set_black(uncle);
110 0 : osi_set_black(parent);
111 0 : osi_set_red(gparent);
112 0 : node = gparent;
113 0 : continue;
114 : }
115 : }
116 :
117 0 : if (parent->osi_right == node) {
118 : register struct osi_node *tmp;
119 :
120 0 : __osi_rotate_left(parent, root);
121 0 : tmp = parent;
122 0 : parent = node;
123 0 : node = tmp;
124 : }
125 :
126 0 : osi_set_black(parent);
127 0 : osi_set_red(gparent);
128 0 : __osi_rotate_right(gparent, root);
129 : } else {
130 : {
131 4121290 : register struct osi_node *uncle = gparent->osi_left;
132 4121290 : if (uncle && osi_is_red(uncle)) {
133 2048113 : osi_set_black(uncle);
134 2048113 : osi_set_black(parent);
135 2048113 : osi_set_red(gparent);
136 2048113 : node = gparent;
137 2048113 : continue;
138 : }
139 : }
140 :
141 2073177 : if (parent->osi_left == node) {
142 : register struct osi_node *tmp;
143 57 : __osi_rotate_right(parent, root);
144 57 : tmp = parent;
145 57 : parent = node;
146 57 : node = tmp;
147 : }
148 :
149 2073177 : osi_set_black(parent);
150 2073177 : osi_set_red(gparent);
151 2073177 : __osi_rotate_left(gparent, root);
152 : }
153 : }
154 :
155 2138014 : osi_set_black(root->osi_node);
156 2138014 : }
157 :
158 2137254 : static inline void __osi_erase_color(struct osi_node *node,
159 : struct osi_node *parent,
160 : struct osi_root *root)
161 : {
162 : struct osi_node *other;
163 :
164 4184745 : while ((!node || osi_is_black(node)) && node != root->osi_node) {
165 2075482 : if (parent->osi_left == node) {
166 2075482 : other = parent->osi_right;
167 2075482 : if (osi_is_red(other)) {
168 1009712 : osi_set_black(other);
169 1009712 : osi_set_red(parent);
170 1009712 : __osi_rotate_left(parent, root);
171 1009712 : other = parent->osi_right;
172 : }
173 2075482 : if ((!other->osi_left || osi_is_black(other->osi_left)) &&
174 2051257 : (!other->osi_right || osi_is_black(other->osi_right)))
175 : {
176 2047491 : osi_set_red(other);
177 2047491 : node = parent;
178 2047491 : parent = osi_parent(node);
179 : } else {
180 27991 : if (!other->osi_right || osi_is_black(other->osi_right))
181 : {
182 : struct osi_node *o_left;
183 58 : if ((o_left = other->osi_left))
184 58 : osi_set_black(o_left);
185 58 : osi_set_red(other);
186 58 : __osi_rotate_right(other, root);
187 58 : other = parent->osi_right;
188 : }
189 27991 : osi_set_color(other, osi_color(parent));
190 27991 : osi_set_black(parent);
191 27991 : if (other->osi_right)
192 27991 : osi_set_black(other->osi_right);
193 27991 : __osi_rotate_left(parent, root);
194 27991 : node = root->osi_node;
195 27991 : break;
196 : }
197 : } else {
198 0 : other = parent->osi_left;
199 0 : if (osi_is_red(other)) {
200 0 : osi_set_black(other);
201 0 : osi_set_red(parent);
202 0 : __osi_rotate_right(parent, root);
203 0 : other = parent->osi_left;
204 : }
205 0 : if ((!other->osi_left || osi_is_black(other->osi_left)) &&
206 0 : (!other->osi_right || osi_is_black(other->osi_right)))
207 : {
208 0 : osi_set_red(other);
209 0 : node = parent;
210 0 : parent = osi_parent(node);
211 : } else {
212 0 : if (!other->osi_left || osi_is_black(other->osi_left))
213 : {
214 : register struct osi_node *o_right;
215 0 : if ((o_right = other->osi_right))
216 0 : osi_set_black(o_right);
217 0 : osi_set_red(other);
218 0 : __osi_rotate_left(other, root);
219 0 : other = parent->osi_left;
220 : }
221 0 : osi_set_color(other, osi_color(parent));
222 0 : osi_set_black(parent);
223 0 : if (other->osi_left)
224 0 : osi_set_black(other->osi_left);
225 0 : __osi_rotate_right(parent, root);
226 0 : node = root->osi_node;
227 0 : break;
228 : }
229 : }
230 : }
231 2137254 : if (node)
232 2132570 : osi_set_black(node);
233 2137254 : }
234 :
235 2137260 : static inline void osi_erase(struct osi_node *node, struct osi_root *root)
236 : {
237 : struct osi_node *child, *parent;
238 : int color;
239 :
240 2137260 : if (!node->osi_left)
241 2137260 : child = node->osi_right;
242 0 : else if (!node->osi_right)
243 0 : child = node->osi_left;
244 : else {
245 0 : struct osi_node *old = node, *left;
246 :
247 0 : node = node->osi_right;
248 0 : while ((left = node->osi_left) != NULL)
249 0 : node = left;
250 :
251 0 : if (osi_parent(old)) {
252 0 : if (osi_parent(old)->osi_left == old)
253 0 : osi_parent(old)->osi_left = node;
254 : else
255 0 : osi_parent(old)->osi_right = node;
256 : } else
257 0 : root->osi_node = node;
258 :
259 0 : child = node->osi_right;
260 0 : parent = osi_parent(node);
261 0 : color = osi_color(node);
262 :
263 0 : if (parent == old) {
264 0 : parent = node;
265 : } else {
266 0 : if (child)
267 0 : osi_set_parent(child, parent);
268 0 : parent->osi_left = child;
269 :
270 0 : node->osi_right = old->osi_right;
271 0 : osi_set_parent(old->osi_right, node);
272 : }
273 :
274 0 : node->osi_parent_color = old->osi_parent_color;
275 0 : node->osi_left = old->osi_left;
276 0 : osi_set_parent(old->osi_left, node);
277 :
278 0 : goto color;
279 : }
280 :
281 2137260 : parent = osi_parent(node);
282 2137260 : color = osi_color(node);
283 :
284 2137260 : if (child)
285 1066014 : osi_set_parent(child, parent);
286 2137260 : if (parent)
287 : {
288 2127896 : if (parent->osi_left == node)
289 2127896 : parent->osi_left = child;
290 : else
291 0 : parent->osi_right = child;
292 : }
293 : else
294 9364 : root->osi_node = child;
295 :
296 2137260 : color:
297 2137260 : if (color == OSI_BLACK)
298 : /* coverity[var_deref_model:SUPPRESS] */
299 2137254 : __osi_erase_color(child, parent, root);
300 2137260 : }
301 :
302 : /*
303 : * This function returns the first node (in sort order) of the tree.
304 : */
305 2213976 : static inline struct osi_node *osi_first(struct osi_root *root)
306 : {
307 : struct osi_node *n;
308 :
309 2213976 : n = root->osi_node;
310 2213976 : if (!n)
311 5023 : return NULL;
312 14779501 : while (n->osi_left)
313 12570548 : n = n->osi_left;
314 2208953 : return n;
315 : }
316 :
317 11642 : static inline struct osi_node *osi_last(struct osi_root *root)
318 : {
319 : struct osi_node *n;
320 :
321 11642 : n = root->osi_node;
322 11642 : if (!n)
323 83 : return NULL;
324 127765 : while (n->osi_right)
325 116206 : n = n->osi_right;
326 11559 : return n;
327 : }
328 :
329 150960 : static inline struct osi_node *osi_next(struct osi_node *node)
330 : {
331 : struct osi_node *parent;
332 :
333 150960 : if (OSI_EMPTY_NODE(node))
334 0 : return NULL;
335 :
336 : /* If we have a right-hand child, go down and then left as far
337 : as we can. */
338 150960 : if (node->osi_right) {
339 45478 : node = node->osi_right;
340 77359 : while (node->osi_left)
341 31881 : node=node->osi_left;
342 45478 : return node;
343 : }
344 :
345 : /* No right-hand children. Everything down and left is
346 : smaller than us, so any 'next' node must be in the general
347 : direction of our parent. Go up the tree; any time the
348 : ancestor is a right-hand child of its parent, keep going
349 : up. First time it's a left-hand child of its parent, said
350 : parent is our 'next' node. */
351 145229 : while ((parent = osi_parent(node)) && node == parent->osi_right)
352 39747 : node = parent;
353 :
354 105482 : return parent;
355 : }
356 :
357 6510 : static inline struct osi_node *osi_prev(struct osi_node *node)
358 : {
359 : struct osi_node *parent;
360 :
361 6510 : if (OSI_EMPTY_NODE(node))
362 0 : return NULL;
363 :
364 : /* If we have a left-hand child, go down and then right as far
365 : as we can. */
366 6510 : if (node->osi_left) {
367 0 : node = node->osi_left;
368 0 : while (node->osi_right)
369 0 : node=node->osi_right;
370 0 : return node;
371 : }
372 :
373 : /* No left-hand children. Go up till we find an ancestor which
374 : is a right-hand child of its parent */
375 6510 : while ((parent = osi_parent(node)) && node == parent->osi_left)
376 0 : node = parent;
377 :
378 6510 : return parent;
379 : }
380 :
381 : static inline void osi_replace_node(struct osi_node *victim,
382 : struct osi_node *new,
383 : struct osi_root *root)
384 : {
385 : struct osi_node *parent = osi_parent(victim);
386 :
387 : /* Set the surrounding nodes to point to the replacement */
388 : if (parent) {
389 : if (victim == parent->osi_left)
390 : parent->osi_left = new;
391 : else
392 : parent->osi_right = new;
393 : } else {
394 : root->osi_node = new;
395 : }
396 : if (victim->osi_left)
397 : osi_set_parent(victim->osi_left, new);
398 : if (victim->osi_right)
399 : osi_set_parent(victim->osi_right, new);
400 :
401 : /* Copy the pointers/colour from the victim to the replacement */
402 : *new = *victim;
403 : }
404 :
405 : #endif
|
