From e530a34bd47fdb8d795fb5888f07e650971b484a Mon Sep 17 00:00:00 2001 From: Arshad Hussain Date: Thu, 21 Mar 2019 15:32:20 +0530 Subject: [PATCH] LU-6142 ldlm: Fix style issues for interval_tree.c This patch fixes issues reported by checkpatch for file lustre/ldlm/interval_tree.c Test-Parameters: trivial Change-Id: Ida99aa8f7a5928e87611c73aa7b5d0dc4a5246e9 Signed-off-by: Arshad Hussain Reviewed-on: https://review.whamcloud.com/34498 Tested-by: Jenkins Tested-by: Maloo Reviewed-by: Andreas Dilger Reviewed-by: Ben Evans Reviewed-by: Oleg Drokin --- lustre/ldlm/interval_tree.c | 866 ++++++++++++++++++++++---------------------- 1 file changed, 443 insertions(+), 423 deletions(-) diff --git a/lustre/ldlm/interval_tree.c b/lustre/ldlm/interval_tree.c index b39b105..1b1bc3a 100644 --- a/lustre/ldlm/interval_tree.c +++ b/lustre/ldlm/interval_tree.c @@ -41,68 +41,69 @@ #include enum { - INTERVAL_RED = 0, - INTERVAL_BLACK = 1 + INTERVAL_RED = 0, + INTERVAL_BLACK = 1 }; static inline int node_is_left_child(struct interval_node *node) { - LASSERT(node->in_parent != NULL); - return node == node->in_parent->in_left; + LASSERT(node->in_parent != NULL); + return node == node->in_parent->in_left; } static inline int node_is_right_child(struct interval_node *node) { - LASSERT(node->in_parent != NULL); - return node == node->in_parent->in_right; + LASSERT(node->in_parent != NULL); + return node == node->in_parent->in_right; } static inline int node_is_red(struct interval_node *node) { - return node->in_color == INTERVAL_RED; + return node->in_color == INTERVAL_RED; } static inline int node_is_black(struct interval_node *node) { - return node->in_color == INTERVAL_BLACK; + return node->in_color == INTERVAL_BLACK; } static inline int extent_compare(struct interval_node_extent *e1, - struct interval_node_extent *e2) -{ - int rc; - if (e1->start == e2->start) { - if (e1->end < e2->end) - rc = -1; - else if (e1->end > e2->end) - rc = 1; - else - rc = 0; - } else { - if (e1->start < e2->start) - rc = -1; - else - rc = 1; - } - return rc; + struct interval_node_extent *e2) +{ + int rc; + + if (e1->start == e2->start) { + if (e1->end < e2->end) + rc = -1; + else if (e1->end > e2->end) + rc = 1; + else + rc = 0; + } else { + if (e1->start < e2->start) + rc = -1; + else + rc = 1; + } + return rc; } static inline int extent_equal(struct interval_node_extent *e1, - struct interval_node_extent *e2) + struct interval_node_extent *e2) { - return (e1->start == e2->start) && (e1->end == e2->end); + return (e1->start == e2->start) && (e1->end == e2->end); } static inline int extent_overlapped(struct interval_node_extent *e1, - struct interval_node_extent *e2) + struct interval_node_extent *e2) { - return (e1->start <= e2->end) && (e2->start <= e1->end); + return (e1->start <= e2->end) && (e2->start <= e1->end); } static inline int node_compare(struct interval_node *n1, - struct interval_node *n2) + struct interval_node *n2) { - return extent_compare(&n1->in_extent, &n2->in_extent); + return extent_compare(&n1->in_extent, &n2->in_extent); } int node_equal(struct interval_node *n1, struct interval_node *n2) @@ -112,276 +113,285 @@ int node_equal(struct interval_node *n1, struct interval_node *n2) static inline __u64 max_u64(__u64 x, __u64 y) { - return x > y ? x : y; + return x > y ? x : y; } static inline __u64 min_u64(__u64 x, __u64 y) { - return x < y ? x : y; + return x < y ? x : y; } #define interval_for_each(node, root) \ for (node = interval_first(root); node != NULL; \ - node = interval_next(node)) + node = interval_next(node)) #define interval_for_each_reverse(node, root) \ for (node = interval_last(root); node != NULL; \ - node = interval_prev(node)) + node = interval_prev(node)) static struct interval_node *interval_first(struct interval_node *node) { - ENTRY; + ENTRY; - if (!node) - RETURN(NULL); - while (node->in_left) - node = node->in_left; - RETURN(node); + if (!node) + RETURN(NULL); + while (node->in_left) + node = node->in_left; + RETURN(node); } static struct interval_node *interval_last(struct interval_node *node) { - ENTRY; + ENTRY; - if (!node) - RETURN(NULL); - while (node->in_right) - node = node->in_right; - RETURN(node); + if (!node) + RETURN(NULL); + while (node->in_right) + node = node->in_right; + RETURN(node); } static struct interval_node *interval_next(struct interval_node *node) { - ENTRY; + ENTRY; - if (!node) - RETURN(NULL); - if (node->in_right) - RETURN(interval_first(node->in_right)); - while (node->in_parent && node_is_right_child(node)) - node = node->in_parent; - RETURN(node->in_parent); + if (!node) + RETURN(NULL); + if (node->in_right) + RETURN(interval_first(node->in_right)); + while (node->in_parent && node_is_right_child(node)) + node = node->in_parent; + RETURN(node->in_parent); } static struct interval_node *interval_prev(struct interval_node *node) { - ENTRY; + ENTRY; - if (!node) - RETURN(NULL); + if (!node) + RETURN(NULL); - if (node->in_left) - RETURN(interval_last(node->in_left)); + if (node->in_left) + RETURN(interval_last(node->in_left)); - while (node->in_parent && node_is_left_child(node)) - node = node->in_parent; + while (node->in_parent && node_is_left_child(node)) + node = node->in_parent; - RETURN(node->in_parent); + RETURN(node->in_parent); } enum interval_iter interval_iterate(struct interval_node *root, - interval_callback_t func, - void *data) -{ - struct interval_node *node; - enum interval_iter rc = INTERVAL_ITER_CONT; - ENTRY; - - interval_for_each(node, root) { - rc = func(node, data); - if (rc == INTERVAL_ITER_STOP) - break; - } + interval_callback_t func, + void *data) +{ + struct interval_node *node; + enum interval_iter rc = INTERVAL_ITER_CONT; + + ENTRY; + + interval_for_each(node, root) { + rc = func(node, data); + if (rc == INTERVAL_ITER_STOP) + break; + } - RETURN(rc); + RETURN(rc); } EXPORT_SYMBOL(interval_iterate); enum interval_iter interval_iterate_reverse(struct interval_node *root, - interval_callback_t func, - void *data) -{ - struct interval_node *node; - enum interval_iter rc = INTERVAL_ITER_CONT; - ENTRY; - - interval_for_each_reverse(node, root) { - rc = func(node, data); - if (rc == INTERVAL_ITER_STOP) - break; - } + interval_callback_t func, + void *data) +{ + struct interval_node *node; + enum interval_iter rc = INTERVAL_ITER_CONT; - RETURN(rc); + ENTRY; + + interval_for_each_reverse(node, root) { + rc = func(node, data); + if (rc == INTERVAL_ITER_STOP) + break; + } + + RETURN(rc); } EXPORT_SYMBOL(interval_iterate_reverse); /* try to find a node with same interval in the tree, - * if found, return the pointer to the node, otherwise return NULL*/ + * if found, return the pointer to the node, otherwise return NULL + */ struct interval_node *interval_find(struct interval_node *root, - struct interval_node_extent *ex) -{ - struct interval_node *walk = root; - int rc; - ENTRY; - - while (walk) { - rc = extent_compare(ex, &walk->in_extent); - if (rc == 0) - break; - else if (rc < 0) - walk = walk->in_left; - else - walk = walk->in_right; - } + struct interval_node_extent *ex) +{ + struct interval_node *walk = root; + int rc; + + ENTRY; + + while (walk) { + rc = extent_compare(ex, &walk->in_extent); + if (rc == 0) + break; + else if (rc < 0) + walk = walk->in_left; + else + walk = walk->in_right; + } - RETURN(walk); + RETURN(walk); } EXPORT_SYMBOL(interval_find); static void __rotate_change_maxhigh(struct interval_node *node, - struct interval_node *rotate) + struct interval_node *rotate) { - __u64 left_max, right_max; + __u64 left_max, right_max; - rotate->in_max_high = node->in_max_high; - left_max = node->in_left ? node->in_left->in_max_high : 0; - right_max = node->in_right ? node->in_right->in_max_high : 0; - node->in_max_high = max_u64(interval_high(node), - max_u64(left_max,right_max)); + rotate->in_max_high = node->in_max_high; + left_max = node->in_left ? node->in_left->in_max_high : 0; + right_max = node->in_right ? node->in_right->in_max_high : 0; + node->in_max_high = max_u64(interval_high(node), + max_u64(left_max, right_max)); } /* The left rotation "pivots" around the link from node to node->right, and * - node will be linked to node->right's left child, and - * - node->right's left child will be linked to node's right child. */ + * - node->right's left child will be linked to node's right child. + */ static void __rotate_left(struct interval_node *node, - struct interval_node **root) -{ - struct interval_node *right = node->in_right; - struct interval_node *parent = node->in_parent; - - node->in_right = right->in_left; - if (node->in_right) - right->in_left->in_parent = node; - - right->in_left = node; - right->in_parent = parent; - if (parent) { - if (node_is_left_child(node)) - parent->in_left = right; - else - parent->in_right = right; - } else { - *root = right; - } - node->in_parent = right; + struct interval_node **root) +{ + struct interval_node *right = node->in_right; + struct interval_node *parent = node->in_parent; + + node->in_right = right->in_left; + if (node->in_right) + right->in_left->in_parent = node; + + right->in_left = node; + right->in_parent = parent; + if (parent) { + if (node_is_left_child(node)) + parent->in_left = right; + else + parent->in_right = right; + } else { + *root = right; + } + node->in_parent = right; - /* update max_high for node and right */ - __rotate_change_maxhigh(node, right); + /* update max_high for node and right */ + __rotate_change_maxhigh(node, right); } /* The right rotation "pivots" around the link from node to node->left, and * - node will be linked to node->left's right child, and - * - node->left's right child will be linked to node's left child. */ + * - node->left's right child will be linked to node's left child. + */ static void __rotate_right(struct interval_node *node, - struct interval_node **root) -{ - struct interval_node *left = node->in_left; - struct interval_node *parent = node->in_parent; - - node->in_left = left->in_right; - if (node->in_left) - left->in_right->in_parent = node; - left->in_right = node; - - left->in_parent = parent; - if (parent) { - if (node_is_right_child(node)) - parent->in_right = left; - else - parent->in_left = left; - } else { - *root = left; - } - node->in_parent = left; + struct interval_node **root) +{ + struct interval_node *left = node->in_left; + struct interval_node *parent = node->in_parent; + + node->in_left = left->in_right; + if (node->in_left) + left->in_right->in_parent = node; + left->in_right = node; + + left->in_parent = parent; + if (parent) { + if (node_is_right_child(node)) + parent->in_right = left; + else + parent->in_left = left; + } else { + *root = left; + } + node->in_parent = left; - /* update max_high for node and left */ - __rotate_change_maxhigh(node, left); + /* update max_high for node and left */ + __rotate_change_maxhigh(node, left); } #define interval_swap(a, b) do { \ - struct interval_node *c = a; a = b; b = c; \ + struct interval_node *c = a; a = b; b = c; \ } while (0) /* - * Operations INSERT and DELETE, when run on a tree with n keys, - * take O(logN) time.Because they modify the tree, the result - * may violate the red-black properties.To restore these properties, - * we must change the colors of some of the nodes in the tree + * Operations INSERT and DELETE, when run on a tree with n keys, + * take O(logN) time.Because they modify the tree, the result + * may violate the red-black properties.To restore these properties, + * we must change the colors of some of the nodes in the tree * and also change the pointer structure. */ static void interval_insert_color(struct interval_node *node, - struct interval_node **root) -{ - struct interval_node *parent, *gparent; - ENTRY; - - while ((parent = node->in_parent) && node_is_red(parent)) { - gparent = parent->in_parent; - /* Parent is RED, so gparent must not be NULL */ - if (node_is_left_child(parent)) { - struct interval_node *uncle; - uncle = gparent->in_right; - if (uncle && node_is_red(uncle)) { - uncle->in_color = INTERVAL_BLACK; - parent->in_color = INTERVAL_BLACK; - gparent->in_color = INTERVAL_RED; - node = gparent; - continue; - } - - if (parent->in_right == node) { - __rotate_left(parent, root); - interval_swap(node, parent); - } - - parent->in_color = INTERVAL_BLACK; - gparent->in_color = INTERVAL_RED; - __rotate_right(gparent, root); - } else { - struct interval_node *uncle; - uncle = gparent->in_left; - if (uncle && node_is_red(uncle)) { - uncle->in_color = INTERVAL_BLACK; - parent->in_color = INTERVAL_BLACK; - gparent->in_color = INTERVAL_RED; - node = gparent; - continue; - } - - if (node_is_left_child(node)) { - __rotate_right(parent, root); - interval_swap(node, parent); - } - - parent->in_color = INTERVAL_BLACK; - gparent->in_color = INTERVAL_RED; - __rotate_left(gparent, root); - } - } + struct interval_node **root) +{ + struct interval_node *parent, *gparent; + + ENTRY; + + while ((parent = node->in_parent) && node_is_red(parent)) { + gparent = parent->in_parent; + /* Parent is RED, so gparent must not be NULL */ + if (node_is_left_child(parent)) { + struct interval_node *uncle; + + uncle = gparent->in_right; + if (uncle && node_is_red(uncle)) { + uncle->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + node = gparent; + continue; + } + + if (parent->in_right == node) { + __rotate_left(parent, root); + interval_swap(node, parent); + } - (*root)->in_color = INTERVAL_BLACK; - EXIT; + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + __rotate_right(gparent, root); + } else { + struct interval_node *uncle; + + uncle = gparent->in_left; + if (uncle && node_is_red(uncle)) { + uncle->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + node = gparent; + continue; + } + + if (node_is_left_child(node)) { + __rotate_right(parent, root); + interval_swap(node, parent); + } + + parent->in_color = INTERVAL_BLACK; + gparent->in_color = INTERVAL_RED; + __rotate_left(gparent, root); + } + } + + (*root)->in_color = INTERVAL_BLACK; + EXIT; } struct interval_node *interval_insert(struct interval_node *node, struct interval_node **root) - { - struct interval_node **p, *parent = NULL; - ENTRY; + struct interval_node **p, *parent = NULL; + + ENTRY; - LASSERT(!interval_is_intree(node)); - p = root; + LASSERT(!interval_is_intree(node)); + p = root; while (*p) { parent = *p; if (node_equal(parent, node)) @@ -397,201 +407,209 @@ struct interval_node *interval_insert(struct interval_node *node, p = &parent->in_right; } - /* link node into the tree */ - node->in_parent = parent; - node->in_color = INTERVAL_RED; - node->in_left = node->in_right = NULL; - *p = node; + /* link node into the tree */ + node->in_parent = parent; + node->in_color = INTERVAL_RED; + node->in_left = node->in_right = NULL; + *p = node; - interval_insert_color(node, root); - node->in_intree = 1; + interval_insert_color(node, root); + node->in_intree = 1; - RETURN(NULL); + RETURN(NULL); } EXPORT_SYMBOL(interval_insert); static inline int node_is_black_or_0(struct interval_node *node) { - return !node || node_is_black(node); + return !node || node_is_black(node); } static void interval_erase_color(struct interval_node *node, - struct interval_node *parent, - struct interval_node **root) -{ - struct interval_node *tmp; - ENTRY; - - while (node_is_black_or_0(node) && node != *root) { - if (parent->in_left == node) { - tmp = parent->in_right; - if (node_is_red(tmp)) { - tmp->in_color = INTERVAL_BLACK; - parent->in_color = INTERVAL_RED; - __rotate_left(parent, root); - tmp = parent->in_right; - } - if (node_is_black_or_0(tmp->in_left) && - node_is_black_or_0(tmp->in_right)) { - tmp->in_color = INTERVAL_RED; - node = parent; - parent = node->in_parent; - } else { - if (node_is_black_or_0(tmp->in_right)) { - struct interval_node *o_left; - if ((o_left = tmp->in_left)) - o_left->in_color = INTERVAL_BLACK; - tmp->in_color = INTERVAL_RED; - __rotate_right(tmp, root); - tmp = parent->in_right; - } - tmp->in_color = parent->in_color; - parent->in_color = INTERVAL_BLACK; - if (tmp->in_right) - tmp->in_right->in_color = INTERVAL_BLACK; - __rotate_left(parent, root); - node = *root; - break; - } - } else { - tmp = parent->in_left; - if (node_is_red(tmp)) { - tmp->in_color = INTERVAL_BLACK; - parent->in_color = INTERVAL_RED; - __rotate_right(parent, root); - tmp = parent->in_left; - } - if (node_is_black_or_0(tmp->in_left) && - node_is_black_or_0(tmp->in_right)) { - tmp->in_color = INTERVAL_RED; - node = parent; - parent = node->in_parent; - } else { - if (node_is_black_or_0(tmp->in_left)) { - struct interval_node *o_right; - if ((o_right = tmp->in_right)) - o_right->in_color = INTERVAL_BLACK; - tmp->in_color = INTERVAL_RED; - __rotate_left(tmp, root); - tmp = parent->in_left; - } - tmp->in_color = parent->in_color; - parent->in_color = INTERVAL_BLACK; - if (tmp->in_left) - tmp->in_left->in_color = INTERVAL_BLACK; - __rotate_right(parent, root); - node = *root; - break; - } - } - } - if (node) - node->in_color = INTERVAL_BLACK; - EXIT; + struct interval_node *parent, + struct interval_node **root) +{ + struct interval_node *tmp; + + ENTRY; + + while (node_is_black_or_0(node) && node != *root) { + if (parent->in_left == node) { + tmp = parent->in_right; + if (node_is_red(tmp)) { + tmp->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_RED; + __rotate_left(parent, root); + tmp = parent->in_right; + } + if (node_is_black_or_0(tmp->in_left) && + node_is_black_or_0(tmp->in_right)) { + tmp->in_color = INTERVAL_RED; + node = parent; + parent = node->in_parent; + } else { + if (node_is_black_or_0(tmp->in_right)) { + struct interval_node *o_left; + + if ((o_left = tmp->in_left)) + o_left->in_color = + INTERVAL_BLACK; + tmp->in_color = INTERVAL_RED; + __rotate_right(tmp, root); + tmp = parent->in_right; + } + tmp->in_color = parent->in_color; + parent->in_color = INTERVAL_BLACK; + if (tmp->in_right) + tmp->in_right->in_color = + INTERVAL_BLACK; + __rotate_left(parent, root); + node = *root; + break; + } + } else { + tmp = parent->in_left; + if (node_is_red(tmp)) { + tmp->in_color = INTERVAL_BLACK; + parent->in_color = INTERVAL_RED; + __rotate_right(parent, root); + tmp = parent->in_left; + } + if (node_is_black_or_0(tmp->in_left) && + node_is_black_or_0(tmp->in_right)) { + tmp->in_color = INTERVAL_RED; + node = parent; + parent = node->in_parent; + } else { + if (node_is_black_or_0(tmp->in_left)) { + struct interval_node *o_right; + + if ((o_right = tmp->in_right)) + o_right->in_color = + INTERVAL_BLACK; + tmp->in_color = INTERVAL_RED; + __rotate_left(tmp, root); + tmp = parent->in_left; + } + tmp->in_color = parent->in_color; + parent->in_color = INTERVAL_BLACK; + if (tmp->in_left) + tmp->in_left->in_color = INTERVAL_BLACK; + __rotate_right(parent, root); + node = *root; + break; + } + } + } + if (node) + node->in_color = INTERVAL_BLACK; + EXIT; } -/* - * if the @max_high value of @node is changed, this function traverse a path +/* + * if the @max_high value of @node is changed, this function traverse a path * from node up to the root to update max_high for the whole tree. */ static void update_maxhigh(struct interval_node *node, - __u64 old_maxhigh) + __u64 old_maxhigh) { - __u64 left_max, right_max; - ENTRY; + __u64 left_max, right_max; - while (node) { - left_max = node->in_left ? node->in_left->in_max_high : 0; - right_max = node->in_right ? node->in_right->in_max_high : 0; - node->in_max_high = max_u64(interval_high(node), - max_u64(left_max, right_max)); + ENTRY; - if (node->in_max_high >= old_maxhigh) - break; - node = node->in_parent; - } - EXIT; + while (node) { + left_max = node->in_left ? node->in_left->in_max_high : 0; + right_max = node->in_right ? node->in_right->in_max_high : 0; + node->in_max_high = max_u64(interval_high(node), + max_u64(left_max, right_max)); + + if (node->in_max_high >= old_maxhigh) + break; + node = node->in_parent; + } + EXIT; } void interval_erase(struct interval_node *node, - struct interval_node **root) -{ - struct interval_node *child, *parent; - int color; - ENTRY; - - LASSERT(interval_is_intree(node)); - node->in_intree = 0; - if (!node->in_left) { - child = node->in_right; - } else if (!node->in_right) { - child = node->in_left; - } else { /* Both left and right child are not NULL */ - struct interval_node *old = node; - - node = interval_next(node); - child = node->in_right; - parent = node->in_parent; - color = node->in_color; - - if (child) - child->in_parent = parent; - if (parent == old) - parent->in_right = child; - else - parent->in_left = child; - - node->in_color = old->in_color; - node->in_right = old->in_right; - node->in_left = old->in_left; - node->in_parent = old->in_parent; - - if (old->in_parent) { - if (node_is_left_child(old)) - old->in_parent->in_left = node; - else - old->in_parent->in_right = node; - } else { - *root = node; - } - - old->in_left->in_parent = node; - if (old->in_right) - old->in_right->in_parent = node; - update_maxhigh(child ? : parent, node->in_max_high); - update_maxhigh(node, old->in_max_high); - if (parent == old) - parent = node; - goto color; - } - parent = node->in_parent; - color = node->in_color; - - if (child) - child->in_parent = parent; - if (parent) { - if (node_is_left_child(node)) - parent->in_left = child; - else - parent->in_right = child; - } else { - *root = child; - } + struct interval_node **root) +{ + struct interval_node *child, *parent; + int color; - update_maxhigh(child ? : parent, node->in_max_high); + ENTRY; + + LASSERT(interval_is_intree(node)); + node->in_intree = 0; + if (!node->in_left) { + child = node->in_right; + } else if (!node->in_right) { + child = node->in_left; + } else { /* Both left and right child are not NULL */ + struct interval_node *old = node; + + node = interval_next(node); + child = node->in_right; + parent = node->in_parent; + color = node->in_color; + + if (child) + child->in_parent = parent; + if (parent == old) + parent->in_right = child; + else + parent->in_left = child; + + node->in_color = old->in_color; + node->in_right = old->in_right; + node->in_left = old->in_left; + node->in_parent = old->in_parent; + + if (old->in_parent) { + if (node_is_left_child(old)) + old->in_parent->in_left = node; + else + old->in_parent->in_right = node; + } else { + *root = node; + } + + old->in_left->in_parent = node; + if (old->in_right) + old->in_right->in_parent = node; + update_maxhigh(child ? : parent, node->in_max_high); + update_maxhigh(node, old->in_max_high); + if (parent == old) + parent = node; + goto color; + } + parent = node->in_parent; + color = node->in_color; + + if (child) + child->in_parent = parent; + if (parent) { + if (node_is_left_child(node)) + parent->in_left = child; + else + parent->in_right = child; + } else { + *root = child; + } + + update_maxhigh(child ? : parent, node->in_max_high); color: - if (color == INTERVAL_BLACK) - interval_erase_color(child, parent, root); - EXIT; + if (color == INTERVAL_BLACK) + interval_erase_color(child, parent, root); + EXIT; } EXPORT_SYMBOL(interval_erase); static inline int interval_may_overlap(struct interval_node *node, - struct interval_node_extent *ext) + struct interval_node_extent *ext) { - return (ext->start <= node->in_max_high && - ext->end >= interval_low(node)); + return (ext->start <= node->in_max_high && + ext->end >= interval_low(node)); } /* @@ -659,7 +677,8 @@ enum interval_iter interval_search(struct interval_node *node, * parent met ext->endin_right; break; } @@ -675,18 +694,18 @@ enum interval_iter interval_search(struct interval_node *node, EXPORT_SYMBOL(interval_search); static enum interval_iter interval_overlap_cb(struct interval_node *n, - void *args) + void *args) { - *(int *)args = 1; - return INTERVAL_ITER_STOP; + *(int *)args = 1; + return INTERVAL_ITER_STOP; } int interval_is_overlapped(struct interval_node *root, - struct interval_node_extent *ext) + struct interval_node_extent *ext) { - int has = 0; - (void)interval_search(root, ext, interval_overlap_cb, &has); - return has; + int has = 0; + (void)interval_search(root, ext, interval_overlap_cb, &has); + return has; } EXPORT_SYMBOL(interval_is_overlapped); @@ -716,47 +735,48 @@ EXPORT_SYMBOL(interval_is_overlapped); * return res; * } * - * It's much easy to eliminate the recursion, see interval_search for + * It's much easy to eliminate the recursion, see interval_search for * an example. -jay */ static inline __u64 interval_expand_low(struct interval_node *root, __u64 low) { - /* we only concern the empty tree right now. */ - if (root == NULL) - return 0; - return low; + /* we only concern the empty tree right now. */ + if (root == NULL) + return 0; + return low; } static inline __u64 interval_expand_high(struct interval_node *node, __u64 high) { - __u64 result = ~0; - - while (node != NULL) { - if (node->in_max_high < high) - break; - - if (interval_low(node) > high) { - result = interval_low(node) - 1; - node = node->in_left; - } else { - node = node->in_right; - } - } + __u64 result = ~0; + + while (node != NULL) { + if (node->in_max_high < high) + break; + + if (interval_low(node) > high) { + result = interval_low(node) - 1; + node = node->in_left; + } else { + node = node->in_right; + } + } - return result; + return result; } /* expanding the extent based on @ext. */ void interval_expand(struct interval_node *root, - struct interval_node_extent *ext, - struct interval_node_extent *limiter) -{ - /* The assertion of interval_is_overlapped is expensive because we may - * travel many nodes to find the overlapped node. */ - LASSERT(interval_is_overlapped(root, ext) == 0); - if (!limiter || limiter->start < ext->start) - ext->start = interval_expand_low(root, ext->start); - if (!limiter || limiter->end > ext->end) - ext->end = interval_expand_high(root, ext->end); - LASSERT(interval_is_overlapped(root, ext) == 0); + struct interval_node_extent *ext, + struct interval_node_extent *limiter) +{ + /* The assertion of interval_is_overlapped is expensive because we may + * travel many nodes to find the overlapped node. + */ + LASSERT(interval_is_overlapped(root, ext) == 0); + if (!limiter || limiter->start < ext->start) + ext->start = interval_expand_low(root, ext->start); + if (!limiter || limiter->end > ext->end) + ext->end = interval_expand_high(root, ext->end); + LASSERT(interval_is_overlapped(root, ext) == 0); } -- 1.8.3.1