diff options
Diffstat (limited to 'drivers/staging/lustre/lustre/ldlm/interval_tree.c')
-rw-r--r-- | drivers/staging/lustre/lustre/ldlm/interval_tree.c | 100 |
1 files changed, 99 insertions, 1 deletions
diff --git a/drivers/staging/lustre/lustre/ldlm/interval_tree.c b/drivers/staging/lustre/lustre/ldlm/interval_tree.c index f4a70ebddeaf..e134ecd21bb2 100644 --- a/drivers/staging/lustre/lustre/ldlm/interval_tree.c +++ b/drivers/staging/lustre/lustre/ldlm/interval_tree.c @@ -90,6 +90,17 @@ static inline int extent_equal(struct interval_node_extent *e1, return (e1->start == e2->start) && (e1->end == e2->end); } +static inline int extent_overlapped(struct interval_node_extent *e1, + struct interval_node_extent *e2) +{ + return (e1->start <= e2->end) && (e2->start <= e1->end); +} + +static inline int node_equal(struct interval_node *n1, struct interval_node *n2) +{ + return extent_equal(&n1->in_extent, &n2->in_extent); +} + static inline __u64 max_u64(__u64 x, __u64 y) { return x > y ? x : y; @@ -262,7 +273,7 @@ struct interval_node *interval_insert(struct interval_node *node, p = root; while (*p) { parent = *p; - if (extent_equal(&parent->in_extent, &node->in_extent)) + if (node_equal(parent, node)) return parent; /* max_high field must be updated after each iteration */ @@ -463,3 +474,90 @@ color: interval_erase_color(child, parent, root); } EXPORT_SYMBOL(interval_erase); + +static inline int interval_may_overlap(struct interval_node *node, + struct interval_node_extent *ext) +{ + return (ext->start <= node->in_max_high && + ext->end >= interval_low(node)); +} + +/* + * This function finds all intervals that overlap interval ext, + * and calls func to handle resulted intervals one by one. + * in lustre, this function will find all conflicting locks in + * the granted queue and add these locks to the ast work list. + * + * { + * if (!node) + * return 0; + * if (ext->end < interval_low(node)) { + * interval_search(node->in_left, ext, func, data); + * } else if (interval_may_overlap(node, ext)) { + * if (extent_overlapped(ext, &node->in_extent)) + * func(node, data); + * interval_search(node->in_left, ext, func, data); + * interval_search(node->in_right, ext, func, data); + * } + * return 0; + * } + * + */ +enum interval_iter interval_search(struct interval_node *node, + struct interval_node_extent *ext, + interval_callback_t func, + void *data) +{ + enum interval_iter rc = INTERVAL_ITER_CONT; + struct interval_node *parent; + + LASSERT(ext); + LASSERT(func); + + while (node) { + if (ext->end < interval_low(node)) { + if (node->in_left) { + node = node->in_left; + continue; + } + } else if (interval_may_overlap(node, ext)) { + if (extent_overlapped(ext, &node->in_extent)) { + rc = func(node, data); + if (rc == INTERVAL_ITER_STOP) + break; + } + + if (node->in_left) { + node = node->in_left; + continue; + } + if (node->in_right) { + node = node->in_right; + continue; + } + } + + parent = node->in_parent; + while (parent) { + if (node_is_left_child(node) && + parent->in_right) { + /* + * If we ever got the left, it means that the + * parent met ext->end<interval_low(parent), or + * may_overlap(parent). If the former is true, + * we needn't go back. So stop early and check + * may_overlap(parent) after this loop. + */ + node = parent->in_right; + break; + } + node = parent; + parent = parent->in_parent; + } + if (!parent || !interval_may_overlap(parent, ext)) + break; + } + + return rc; +} +EXPORT_SYMBOL(interval_search); |