Add the rt linux 4.1.3-rt3 as base

[kvmfornfv.git] / kernel / drivers / staging / lustre / lustre / include / interval_tree.h

diff --git a/kernel/drivers/staging/lustre/lustre/include/interval_tree.h b/kernel/drivers/staging/lustre/lustre/include/interval_tree.h
new file mode 100644 (file)
index 0000000..bf9027d
--- /dev/null
+++ b/kernel/drivers/staging/lustre/lustre/include/interval_tree.h
@@ -0,0 +1,124 @@
+/*
+ * GPL HEADER START
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * 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.
+ *
+ * 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).
+ *
+ * You should have received a copy of the GNU General Public License
+ * version 2 along with this program; If not, see
+ * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ * 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 "../../include/linux/libcfs/libcfs.h" /* LASSERT. */
+
+struct interval_node {
+       struct interval_node   *in_left;
+       struct interval_node   *in_right;
+       struct interval_node   *in_parent;
+       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;
+               __u64 end;
+       } in_extent;
+};
+
+enum interval_iter {
+       INTERVAL_ITER_CONT = 1,
+       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;
+}
+
+static inline __u64 interval_high(struct interval_node *node)
+{
+       return node->in_extent.end;
+}
+
+static inline void 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;
+}
+
+/* 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
+ *    immediately with return value INTERVAL_ITER_STOP.
+ *  - callbacks for interval_iterate and interval_iterate_reverse: Every
+ *    nodes in the tree will be set to @node before the callback being called
+ *  - callback for interval_search: Only overlapped node will be set to @node
+ *    before the callback being called.
+ */
+typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
+                                                 void *args);
+
+struct interval_node *interval_insert(struct interval_node *node,
+                                     struct interval_node **root);
+void interval_erase(struct interval_node *node, struct interval_node **root);
+
+/* Search the extents in the tree and call @func for each overlapped
+ * extents. */
+enum interval_iter interval_search(struct interval_node *root,
+                                  struct interval_node_extent *ex,
+                                  interval_callback_t func, void *data);
+
+/* Iterate every node in the tree - by reverse order or regular order. */
+enum interval_iter interval_iterate(struct interval_node *root,
+                                   interval_callback_t func, void *data);
+enum interval_iter interval_iterate_reverse(struct interval_node *root,
+                                   interval_callback_t func, void *data);
+
+void interval_expand(struct interval_node *root,
+                    struct interval_node_extent *ext,
+                    struct interval_node_extent *limiter);
+int interval_is_overlapped(struct interval_node *root,
+                          struct interval_node_extent *ex);
+struct interval_node *interval_find(struct interval_node *root,
+                                   struct interval_node_extent *ex);
+#endif