1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#include "../include/lustre_dlm.h"
38#include "../include/obd_support.h"
39#include "../include/interval_tree.h"
40
41enum {
42 INTERVAL_RED = 0,
43 INTERVAL_BLACK = 1
44};
45
46static inline int node_is_left_child(struct interval_node *node)
47{
48 return node == node->in_parent->in_left;
49}
50
51static inline int node_is_right_child(struct interval_node *node)
52{
53 return node == node->in_parent->in_right;
54}
55
56static inline int node_is_red(struct interval_node *node)
57{
58 return node->in_color == INTERVAL_RED;
59}
60
61static inline int node_is_black(struct interval_node *node)
62{
63 return node->in_color == INTERVAL_BLACK;
64}
65
66static inline int extent_compare(struct interval_node_extent *e1,
67 struct interval_node_extent *e2)
68{
69 int rc;
70
71 if (e1->start == e2->start) {
72 if (e1->end < e2->end)
73 rc = -1;
74 else if (e1->end > e2->end)
75 rc = 1;
76 else
77 rc = 0;
78 } else {
79 if (e1->start < e2->start)
80 rc = -1;
81 else
82 rc = 1;
83 }
84 return rc;
85}
86
87static inline int extent_equal(struct interval_node_extent *e1,
88 struct interval_node_extent *e2)
89{
90 return (e1->start == e2->start) && (e1->end == e2->end);
91}
92
93static inline __u64 max_u64(__u64 x, __u64 y)
94{
95 return x > y ? x : y;
96}
97
98static struct interval_node *interval_first(struct interval_node *node)
99{
100 if (!node)
101 return NULL;
102 while (node->in_left)
103 node = node->in_left;
104 return node;
105}
106
107static struct interval_node *interval_next(struct interval_node *node)
108{
109 if (!node)
110 return NULL;
111 if (node->in_right)
112 return interval_first(node->in_right);
113 while (node->in_parent && node_is_right_child(node))
114 node = node->in_parent;
115 return node->in_parent;
116}
117
118static void __rotate_change_maxhigh(struct interval_node *node,
119 struct interval_node *rotate)
120{
121 __u64 left_max, right_max;
122
123 rotate->in_max_high = node->in_max_high;
124 left_max = node->in_left ? node->in_left->in_max_high : 0;
125 right_max = node->in_right ? node->in_right->in_max_high : 0;
126 node->in_max_high = max_u64(interval_high(node),
127 max_u64(left_max, right_max));
128}
129
130
131
132
133
134static void __rotate_left(struct interval_node *node,
135 struct interval_node **root)
136{
137 struct interval_node *right = node->in_right;
138 struct interval_node *parent = node->in_parent;
139
140 node->in_right = right->in_left;
141 if (node->in_right)
142 right->in_left->in_parent = node;
143
144 right->in_left = node;
145 right->in_parent = parent;
146 if (parent) {
147 if (node_is_left_child(node))
148 parent->in_left = right;
149 else
150 parent->in_right = right;
151 } else {
152 *root = right;
153 }
154 node->in_parent = right;
155
156
157 __rotate_change_maxhigh(node, right);
158}
159
160
161
162
163
164static void __rotate_right(struct interval_node *node,
165 struct interval_node **root)
166{
167 struct interval_node *left = node->in_left;
168 struct interval_node *parent = node->in_parent;
169
170 node->in_left = left->in_right;
171 if (node->in_left)
172 left->in_right->in_parent = node;
173 left->in_right = node;
174
175 left->in_parent = parent;
176 if (parent) {
177 if (node_is_right_child(node))
178 parent->in_right = left;
179 else
180 parent->in_left = left;
181 } else {
182 *root = left;
183 }
184 node->in_parent = left;
185
186
187 __rotate_change_maxhigh(node, left);
188}
189
190#define interval_swap(a, b) do { \
191 struct interval_node *c = a; a = b; b = c; \
192} while (0)
193
194
195
196
197
198
199
200
201static void interval_insert_color(struct interval_node *node,
202 struct interval_node **root)
203{
204 struct interval_node *parent, *gparent;
205
206 while ((parent = node->in_parent) && node_is_red(parent)) {
207 gparent = parent->in_parent;
208
209 if (node_is_left_child(parent)) {
210 struct interval_node *uncle;
211
212 uncle = gparent->in_right;
213 if (uncle && node_is_red(uncle)) {
214 uncle->in_color = INTERVAL_BLACK;
215 parent->in_color = INTERVAL_BLACK;
216 gparent->in_color = INTERVAL_RED;
217 node = gparent;
218 continue;
219 }
220
221 if (parent->in_right == node) {
222 __rotate_left(parent, root);
223 interval_swap(node, parent);
224 }
225
226 parent->in_color = INTERVAL_BLACK;
227 gparent->in_color = INTERVAL_RED;
228 __rotate_right(gparent, root);
229 } else {
230 struct interval_node *uncle;
231
232 uncle = gparent->in_left;
233 if (uncle && node_is_red(uncle)) {
234 uncle->in_color = INTERVAL_BLACK;
235 parent->in_color = INTERVAL_BLACK;
236 gparent->in_color = INTERVAL_RED;
237 node = gparent;
238 continue;
239 }
240
241 if (node_is_left_child(node)) {
242 __rotate_right(parent, root);
243 interval_swap(node, parent);
244 }
245
246 parent->in_color = INTERVAL_BLACK;
247 gparent->in_color = INTERVAL_RED;
248 __rotate_left(gparent, root);
249 }
250 }
251
252 (*root)->in_color = INTERVAL_BLACK;
253}
254
255struct interval_node *interval_insert(struct interval_node *node,
256 struct interval_node **root)
257
258{
259 struct interval_node **p, *parent = NULL;
260
261 LASSERT(!interval_is_intree(node));
262 p = root;
263 while (*p) {
264 parent = *p;
265 if (extent_equal(&parent->in_extent, &node->in_extent))
266 return parent;
267
268
269 if (parent->in_max_high < interval_high(node))
270 parent->in_max_high = interval_high(node);
271
272 if (extent_compare(&node->in_extent, &parent->in_extent) < 0)
273 p = &parent->in_left;
274 else
275 p = &parent->in_right;
276 }
277
278
279 node->in_parent = parent;
280 node->in_color = INTERVAL_RED;
281 node->in_left = NULL;
282 node->in_right = NULL;
283 *p = node;
284
285 interval_insert_color(node, root);
286 node->in_intree = 1;
287
288 return NULL;
289}
290EXPORT_SYMBOL(interval_insert);
291
292static inline int node_is_black_or_0(struct interval_node *node)
293{
294 return !node || node_is_black(node);
295}
296
297static void interval_erase_color(struct interval_node *node,
298 struct interval_node *parent,
299 struct interval_node **root)
300{
301 struct interval_node *tmp;
302
303 while (node_is_black_or_0(node) && node != *root) {
304 if (parent->in_left == node) {
305 tmp = parent->in_right;
306 if (node_is_red(tmp)) {
307 tmp->in_color = INTERVAL_BLACK;
308 parent->in_color = INTERVAL_RED;
309 __rotate_left(parent, root);
310 tmp = parent->in_right;
311 }
312 if (node_is_black_or_0(tmp->in_left) &&
313 node_is_black_or_0(tmp->in_right)) {
314 tmp->in_color = INTERVAL_RED;
315 node = parent;
316 parent = node->in_parent;
317 } else {
318 if (node_is_black_or_0(tmp->in_right)) {
319 struct interval_node *o_left;
320
321 o_left = tmp->in_left;
322 if (o_left)
323 o_left->in_color = INTERVAL_BLACK;
324 tmp->in_color = INTERVAL_RED;
325 __rotate_right(tmp, root);
326 tmp = parent->in_right;
327 }
328 tmp->in_color = parent->in_color;
329 parent->in_color = INTERVAL_BLACK;
330 if (tmp->in_right)
331 tmp->in_right->in_color = INTERVAL_BLACK;
332 __rotate_left(parent, root);
333 node = *root;
334 break;
335 }
336 } else {
337 tmp = parent->in_left;
338 if (node_is_red(tmp)) {
339 tmp->in_color = INTERVAL_BLACK;
340 parent->in_color = INTERVAL_RED;
341 __rotate_right(parent, root);
342 tmp = parent->in_left;
343 }
344 if (node_is_black_or_0(tmp->in_left) &&
345 node_is_black_or_0(tmp->in_right)) {
346 tmp->in_color = INTERVAL_RED;
347 node = parent;
348 parent = node->in_parent;
349 } else {
350 if (node_is_black_or_0(tmp->in_left)) {
351 struct interval_node *o_right;
352
353 o_right = tmp->in_right;
354 if (o_right)
355 o_right->in_color = INTERVAL_BLACK;
356 tmp->in_color = INTERVAL_RED;
357 __rotate_left(tmp, root);
358 tmp = parent->in_left;
359 }
360 tmp->in_color = parent->in_color;
361 parent->in_color = INTERVAL_BLACK;
362 if (tmp->in_left)
363 tmp->in_left->in_color = INTERVAL_BLACK;
364 __rotate_right(parent, root);
365 node = *root;
366 break;
367 }
368 }
369 }
370 if (node)
371 node->in_color = INTERVAL_BLACK;
372}
373
374
375
376
377
378static void update_maxhigh(struct interval_node *node,
379 __u64 old_maxhigh)
380{
381 __u64 left_max, right_max;
382
383 while (node) {
384 left_max = node->in_left ? node->in_left->in_max_high : 0;
385 right_max = node->in_right ? node->in_right->in_max_high : 0;
386 node->in_max_high = max_u64(interval_high(node),
387 max_u64(left_max, right_max));
388
389 if (node->in_max_high >= old_maxhigh)
390 break;
391 node = node->in_parent;
392 }
393}
394
395void interval_erase(struct interval_node *node,
396 struct interval_node **root)
397{
398 struct interval_node *child, *parent;
399 int color;
400
401 LASSERT(interval_is_intree(node));
402 node->in_intree = 0;
403 if (!node->in_left) {
404 child = node->in_right;
405 } else if (!node->in_right) {
406 child = node->in_left;
407 } else {
408 struct interval_node *old = node;
409
410 node = interval_next(node);
411 child = node->in_right;
412 parent = node->in_parent;
413 color = node->in_color;
414
415 if (child)
416 child->in_parent = parent;
417 if (parent == old)
418 parent->in_right = child;
419 else
420 parent->in_left = child;
421
422 node->in_color = old->in_color;
423 node->in_right = old->in_right;
424 node->in_left = old->in_left;
425 node->in_parent = old->in_parent;
426
427 if (old->in_parent) {
428 if (node_is_left_child(old))
429 old->in_parent->in_left = node;
430 else
431 old->in_parent->in_right = node;
432 } else {
433 *root = node;
434 }
435
436 old->in_left->in_parent = node;
437 if (old->in_right)
438 old->in_right->in_parent = node;
439 update_maxhigh(child ? : parent, node->in_max_high);
440 update_maxhigh(node, old->in_max_high);
441 if (parent == old)
442 parent = node;
443 goto color;
444 }
445 parent = node->in_parent;
446 color = node->in_color;
447
448 if (child)
449 child->in_parent = parent;
450 if (parent) {
451 if (node_is_left_child(node))
452 parent->in_left = child;
453 else
454 parent->in_right = child;
455 } else {
456 *root = child;
457 }
458
459 update_maxhigh(child ? : parent, node->in_max_high);
460
461color:
462 if (color == INTERVAL_BLACK)
463 interval_erase_color(child, parent, root);
464}
465EXPORT_SYMBOL(interval_erase);
466