Lines Matching refs:node
50 static inline int node_is_left_child(struct interval_node *node)
52 LASSERT(node->in_parent != NULL);
53 return node == node->in_parent->in_left;
56 static inline int node_is_right_child(struct interval_node *node)
58 LASSERT(node->in_parent != NULL);
59 return node == node->in_parent->in_right;
62 static inline int node_is_red(struct interval_node *node)
64 return node->in_color == INTERVAL_RED;
67 static inline int node_is_black(struct interval_node *node)
69 return node->in_color == INTERVAL_BLACK;
126 #define interval_for_each(node, root) \
127 for (node = interval_first(root); node != NULL; \
128 node = interval_next(node))
130 #define interval_for_each_reverse(node, root) \
131 for (node = interval_last(root); node != NULL; \
132 node = interval_prev(node))
134 static struct interval_node *interval_first(struct interval_node *node)
136 if (!node)
138 while (node->in_left)
139 node = node->in_left;
140 return node;
143 static struct interval_node *interval_last(struct interval_node *node)
145 if (!node)
147 while (node->in_right)
148 node = node->in_right;
149 return node;
152 static struct interval_node *interval_next(struct interval_node *node)
154 if (!node)
156 if (node->in_right)
157 return interval_first(node->in_right);
158 while (node->in_parent && node_is_right_child(node))
159 node = node->in_parent;
160 return node->in_parent;
163 static struct interval_node *interval_prev(struct interval_node *node)
165 if (!node)
168 if (node->in_left)
169 return interval_last(node->in_left);
171 while (node->in_parent && node_is_left_child(node))
172 node = node->in_parent;
174 return node->in_parent;
181 struct interval_node *node;
184 interval_for_each(node, root) {
185 rc = func(node, data);
198 struct interval_node *node;
201 interval_for_each_reverse(node, root) {
202 rc = func(node, data);
211 /* try to find a node with same interval in the tree,
212 * if found, return the pointer to the node, otherwise return NULL*/
233 static void __rotate_change_maxhigh(struct interval_node *node,
238 rotate->in_max_high = node->in_max_high;
239 left_max = node->in_left ? node->in_left->in_max_high : 0;
240 right_max = node->in_right ? node->in_right->in_max_high : 0;
241 node->in_max_high = max_u64(interval_high(node),
245 /* The left rotation "pivots" around the link from node to node->right, and
246 * - node will be linked to node->right's left child, and
247 * - node->right's left child will be linked to node's right child. */
248 static void __rotate_left(struct interval_node *node,
251 struct interval_node *right = node->in_right;
252 struct interval_node *parent = node->in_parent;
254 node->in_right = right->in_left;
255 if (node->in_right)
256 right->in_left->in_parent = node;
258 right->in_left = node;
261 if (node_is_left_child(node))
268 node->in_parent = right;
270 /* update max_high for node and right */
271 __rotate_change_maxhigh(node, right);
274 /* The right rotation "pivots" around the link from node to node->left, and
275 * - node will be linked to node->left's right child, and
276 * - node->left's right child will be linked to node's left child. */
277 static void __rotate_right(struct interval_node *node,
280 struct interval_node *left = node->in_left;
281 struct interval_node *parent = node->in_parent;
283 node->in_left = left->in_right;
284 if (node->in_left)
285 left->in_right->in_parent = node;
286 left->in_right = node;
290 if (node_is_right_child(node))
297 node->in_parent = left;
299 /* update max_high for node and left */
300 __rotate_change_maxhigh(node, left);
314 static void interval_insert_color(struct interval_node *node,
319 while ((parent = node->in_parent) && node_is_red(parent)) {
329 node = gparent;
333 if (parent->in_right == node) {
335 interval_swap(node, parent);
348 node = gparent;
352 if (node_is_left_child(node)) {
354 interval_swap(node, parent);
366 struct interval_node *interval_insert(struct interval_node *node,
372 LASSERT(!interval_is_intree(node));
376 if (node_equal(parent, node))
380 if (parent->in_max_high < interval_high(node))
381 parent->in_max_high = interval_high(node);
383 if (node_compare(node, parent) < 0)
389 /* link node into the tree */
390 node->in_parent = parent;
391 node->in_color = INTERVAL_RED;
392 node->in_left = node->in_right = NULL;
393 *p = node;
395 interval_insert_color(node, root);
396 node->in_intree = 1;
402 static inline int node_is_black_or_0(struct interval_node *node)
404 return !node || node_is_black(node);
407 static void interval_erase_color(struct interval_node *node,
413 while (node_is_black_or_0(node) && node != *root) {
414 if (parent->in_left == node) {
425 node = parent;
426 parent = node->in_parent;
442 node = *root;
456 node = parent;
457 parent = node->in_parent;
473 node = *root;
478 if (node)
479 node->in_color = INTERVAL_BLACK;
483 * if the @max_high value of @node is changed, this function traverse a path
484 * from node up to the root to update max_high for the whole tree.
486 static void update_maxhigh(struct interval_node *node,
491 while (node) {
492 left_max = node->in_left ? node->in_left->in_max_high : 0;
493 right_max = node->in_right ? node->in_right->in_max_high : 0;
494 node->in_max_high = max_u64(interval_high(node),
497 if (node->in_max_high >= old_maxhigh)
499 node = node->in_parent;
503 void interval_erase(struct interval_node *node,
509 LASSERT(interval_is_intree(node));
510 node->in_intree = 0;
511 if (!node->in_left) {
512 child = node->in_right;
513 } else if (!node->in_right) {
514 child = node->in_left;
516 struct interval_node *old = node;
518 node = interval_next(node);
519 child = node->in_right;
520 parent = node->in_parent;
521 color = node->in_color;
530 node->in_color = old->in_color;
531 node->in_right = old->in_right;
532 node->in_left = old->in_left;
533 node->in_parent = old->in_parent;
537 old->in_parent->in_left = node;
539 old->in_parent->in_right = node;
541 *root = node;
544 old->in_left->in_parent = node;
546 old->in_right->in_parent = node;
547 update_maxhigh(child ? : parent, node->in_max_high);
548 update_maxhigh(node, old->in_max_high);
550 parent = node;
553 parent = node->in_parent;
554 color = node->in_color;
559 if (node_is_left_child(node))
567 update_maxhigh(child ? : parent, node->in_max_high);
575 static inline int interval_may_overlap(struct interval_node *node,
578 return (ext->start <= node->in_max_high &&
579 ext->end >= interval_low(node));
589 * if (node == NULL)
591 * if (ext->end < interval_low(node)) {
592 * interval_search(node->in_left, ext, func, data);
593 * } else if (interval_may_overlap(node, ext)) {
594 * if (extent_overlapped(ext, &node->in_extent))
595 * func(node, data);
596 * interval_search(node->in_left, ext, func, data);
597 * interval_search(node->in_right, ext, func, data);
603 enum interval_iter interval_search(struct interval_node *node,
614 while (node) {
615 if (ext->end < interval_low(node)) {
616 if (node->in_left) {
617 node = node->in_left;
620 } else if (interval_may_overlap(node, ext)) {
621 if (extent_overlapped(ext, &node->in_extent)) {
622 rc = func(node, data);
627 if (node->in_left) {
628 node = node->in_left;
631 if (node->in_right) {
632 node = node->in_right;
637 parent = node->in_parent;
639 if (node_is_left_child(node) &&
646 node = parent->in_right;
649 node = parent;
713 static inline __u64 interval_expand_high(struct interval_node *node, __u64 high)
717 while (node != NULL) {
718 if (node->in_max_high < high)
721 if (interval_low(node) > high) {
722 result = interval_low(node) - 1;
723 node = node->in_left;
725 node = node->in_right;
738 * travel many nodes to find the overlapped node. */