-/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
- * (visit-tags-table FILE)
- * vim:expandtab:shiftwidth=8:tabstop=8:
+/*
+ * GPL HEADER START
*
- * Copyright (c) 2002, 2007 Cluster File Systems, Inc.
- * Author: Huang Wei <huangwei@clusterfs.com>
- * Author: Jay Xiong <jinshan.xiong@sun.com>
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
- * This file is part of the Lustre file system, http://www.lustre.org
- * Lustre is a trademark of Cluster File Systems, Inc.
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 only,
+ * as published by the Free Software Foundation.
*
- * 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.
+ * This program 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 GNU
+ * General Public License version 2 for more details (a copy is included
+ * in the LICENSE file that accompanied this code).
*
- * 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.
+ * You should have received a copy of the GNU General Public License
+ * version 2 along with this program; If not, see
+ * http://www.gnu.org/licenses/gpl-2.0.html
*
- * 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.
+ * GPL HEADER END
+ */
+/*
+ * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
+ * Use is subject to license terms.
+ */
+/*
+ * This file is part of Lustre, http://www.lustre.org/
+ * Lustre is a trademark of Sun Microsystems, Inc.
+ *
+ * lustre/include/interval_tree.h
+ *
+ * Author: Huang Wei <huangwei@clusterfs.com>
+ * Author: Jay Xiong <jinshan.xiong@sun.com>
*/
#ifndef _INTERVAL_H__
#define _INTERVAL_H__
-#include <libcfs/types.h> /* __u8, __u64 etc. */
-#include <libcfs/libcfs.h> /* LASSERT. */
+#include <linux/errno.h>
+#include <linux/string.h>
+#include <linux/types.h>
struct interval_node {
struct interval_node *in_left;
struct interval_node *in_right;
struct interval_node *in_parent;
- __u8 in_color;
- __u8 res1[7]; /* tags, 8-bytes aligned */
+ unsigned in_color:1,
+ in_intree:1, /** set if the node is in tree */
+ in_res1:30;
+ __u8 in_res2[4]; /** tags, 8-bytes aligned */
__u64 in_max_high;
struct interval_node_extent {
__u64 start;
INTERVAL_ITER_STOP = 2
};
+static inline int interval_is_intree(struct interval_node *node)
+{
+ return node->in_intree == 1;
+}
+
static inline __u64 interval_low(struct interval_node *node)
{
return node->in_extent.start;
return node->in_extent.end;
}
-static inline void interval_set(struct interval_node *node,
- __u64 start, __u64 end)
+static inline int interval_set(struct interval_node *node,
+ __u64 start, __u64 end)
{
- LASSERT(start <= end);
- node->in_extent.start = start;
- node->in_extent.end = end;
- node->in_max_high = end;
+ if (start > end)
+ return -ERANGE;
+ node->in_extent.start = start;
+ node->in_extent.end = end;
+ node->in_max_high = end;
+ return 0;
}
+static inline void interval_init(struct interval_node *node)
+{
+ memset(node, 0, sizeof(*node));
+}
+
+int node_equal(struct interval_node *n1, struct interval_node *n2);
+
/* Rules to write an interval callback.
* - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
* should be stopped. It will then cause the iteration function to return