interval_tree.c

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

/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
 * vim:expandtab:shiftwidth=8:tabstop=8:
 *
 *  Interval tree library used by ldlm extent lock code
 *
 *  Copyright (c) 2007 Cluster File Systems, Inc.
 *   Author: Huang Wei <[e-mail]>
 *   Author: Jay Xiong <[e-mail]>
 *
 *   This file is part of the Lustre file system, http://www.lustre.org
 *   Lustre is a trademark of Cluster File Systems, Inc.
 *
 *   You may have signed or agreed to another license before downloading
 *   this software.  If so, you are bound by the terms and conditions
 *   of that agreement, and the following does not apply to you.  See the
 *   LICENSE file included with this distribution for more information.
 *
 *   If you did not agree to a different license, then this copy of Lustre
 *   is open source software; you can redistribute it and/or modify it
 *   under the terms of version 2 of the GNU General Public License as
 *   published by the Free Software Foundation.
 *
 *   In either case, Lustre is distributed in the hope that it will be
 *   useful, but WITHOUT ANY WARRANTY; without even the implied warranty
 *   of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   license text for more details.
 */
#ifdef __KERNEL__
# include <lustre_dlm.h>
#else
# include <liblustre.h>
# include <libcfs/kp30.h>
#endif
#include <obd_support.h>
#include <interval_tree.h>

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

static inline int node_is_right_child(struct interval_node *node)
{
        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;
}

static inline int node_is_black(struct interval_node *node)
{
        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;
}

static inline int extent_equal(struct interval_node_extent *e1,
                               struct interval_node_extent *e2)
{
        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_compare(struct interval_node *n1,
                               struct interval_node *n2)
{
        return extent_compare(&n1->in_extent, &n2->in_extent);
}

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

static inline __u64 min_u64(__u64 x, __u64 y)
{
        return x < y ? x : y;
}

#define interval_for_each(node, root)                   \
for (node = interval_first(root); node != NULL;         \
     node = interval_next(node))

#define interval_for_each_reverse(node, root)           \
for (node = interval_last(root); node != NULL;          \
     node = interval_prev(node))

static struct interval_node *interval_first(struct interval_node *node)
{
        ENTRY;

        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;

        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;

        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;

        if (!node)
                RETURN(NULL);

        if (node->in_left)
                RETURN(interval_last(node->in_left));

        while (node->in_parent && node_is_left_child(node))
                node = 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;
        }

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

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

        RETURN(walk);
}
EXPORT_SYMBOL(interval_find);

static void __rotate_change_maxhigh(struct interval_node *node,
                                    struct interval_node *rotate)
{
        __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.  */
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;

        /* 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.  */
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;

        /* 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;      \
} 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 
 * 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);
                }
        }

        (*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;