interval_tree.c

来自「lustre 1.6.5 source code」· C语言 代码 · 共 753 行 · 第 1/2 页

        p = root;
        while (*p) {
                parent = *p;
                if (node_equal(parent, node))
                        RETURN(parent);

                /* max_high field must be updated after each iteration */
                if (parent->in_max_high < interval_high(node))
                        parent->in_max_high = interval_high(node);

                if (node_compare(node, parent) < 0)
                        p = &parent->in_left;
                else 
                        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;

        interval_insert_color(node, root);

        RETURN(NULL);
}
EXPORT_SYMBOL(interval_insert);

static inline int node_is_black_or_0(struct interval_node *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;
}

/* 
 * 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 left_max, right_max;
        ENTRY;

        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;

        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;
                        parent = node;
                } 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, node->in_max_high);
                update_maxhigh(node, old->in_max_high);
                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, node->in_max_high);

color:
        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)
{
        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 == NULL)
 *               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)
{
        struct interval_node *parent;
        enum interval_iter rc = INTERVAL_ITER_CONT;

        LASSERT(ext != NULL);
        LASSERT(func != NULL);

        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 == NULL || !interval_may_overlap(parent, ext))
                        break;
        }

        return rc;
}
EXPORT_SYMBOL(interval_search);

static enum interval_iter interval_overlap_cb(struct interval_node *n,
                                              void *args)
{
        *(int *)args = 1;
        return INTERVAL_ITER_STOP;
}

int interval_is_overlapped(struct interval_node *root,
                           struct interval_node_extent *ext)
{
        int has = 0;
        (void)interval_search(root, ext, interval_overlap_cb, &has);
        return has;
}
EXPORT_SYMBOL(interval_is_overlapped);

/* Don't expand to low. Expanding downwards is expensive, and meaningless to
 * some extents, because programs seldom do IO backward.
 *
 * The recursive algorithm of expanding low:
 * expand_low {
 *        struct interval_node *tmp;
 *        static __u64 res = 0;
 *
 *        if (root == NULL)
 *                return res;
 *        if (root->in_max_high < low) {
 *                res = max_u64(root->in_max_high + 1, res);
 *                return res;
 *        } else if (low < interval_low(root)) {
 *                interval_expand_low(root->in_left, low);
 *                return res;
 *        }
 *
 *        if (interval_high(root) < low)
 *                res = max_u64(interval_high(root) + 1, res);
 *        interval_expand_low(root->in_left, low);
 *        interval_expand_low(root->in_right, low);
 *
 *        return res;
 * }
 *
 * 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;
}

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;
                }
        }

        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);
}
EXPORT_SYMBOL(interval_expand);