Whamcloud - gitweb
LU-9611 lod: allow -1 for default stripe count/offset
[fs/lustre-release.git] / lustre / include / interval_tree.h
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License version 2 only,
8  * as published by the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but
11  * WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * General Public License version 2 for more details (a copy is included
14  * in the LICENSE file that accompanied this code).
15  *
16  * You should have received a copy of the GNU General Public License
17  * version 2 along with this program; If not, see
18  * http://www.gnu.org/licenses/gpl-2.0.html
19  *
20  * GPL HEADER END
21  */
22 /*
23  * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
24  * Use is subject to license terms.
25  */
26 /*
27  * This file is part of Lustre, http://www.lustre.org/
28  * Lustre is a trademark of Sun Microsystems, Inc.
29  *
30  * lustre/include/interval_tree.h
31  *
32  * Author: Huang Wei <huangwei@clusterfs.com>
33  * Author: Jay Xiong <jinshan.xiong@sun.com>
34  */
35
36 #ifndef _INTERVAL_H__
37 #define _INTERVAL_H__
38
39 #include <linux/errno.h>
40 #include <linux/string.h>
41 #include <linux/types.h>
42
43 struct interval_node {
44         struct interval_node   *in_left;
45         struct interval_node   *in_right;
46         struct interval_node   *in_parent;
47         unsigned                in_color:1,
48                                 in_intree:1, /** set if the node is in tree */
49                                 in_res1:30;
50         __u8                    in_res2[4];  /** tags, 8-bytes aligned */
51         __u64                   in_max_high;
52         struct interval_node_extent {
53                 __u64 start;
54                 __u64 end;
55         } in_extent;
56 };
57
58 enum interval_iter {
59         INTERVAL_ITER_CONT = 1,
60         INTERVAL_ITER_STOP = 2
61 };
62
63 static inline int interval_is_intree(struct interval_node *node)
64 {
65         return node->in_intree == 1;
66 }
67
68 static inline __u64 interval_low(struct interval_node *node)
69 {
70         return node->in_extent.start;
71 }
72
73 static inline __u64 interval_high(struct interval_node *node)
74 {
75         return node->in_extent.end;
76 }
77
78 static inline int interval_set(struct interval_node *node,
79                                __u64 start, __u64 end)
80 {
81         if (start > end)
82                 return -ERANGE;
83         node->in_extent.start = start;
84         node->in_extent.end = end;
85         node->in_max_high = end;
86         return 0;
87 }
88
89 static inline void interval_init(struct interval_node *node)
90 {
91         memset(node, 0, sizeof(*node));
92 }
93
94 int node_equal(struct interval_node *n1, struct interval_node *n2);
95
96 /* Rules to write an interval callback.
97  *  - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
98  *    should be stopped. It will then cause the iteration function to return
99  *    immediately with return value INTERVAL_ITER_STOP.
100  *  - callbacks for interval_iterate and interval_iterate_reverse: Every 
101  *    nodes in the tree will be set to @node before the callback being called
102  *  - callback for interval_search: Only overlapped node will be set to @node
103  *    before the callback being called.
104  */
105 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
106                                                   void *args);
107
108 struct interval_node *interval_insert(struct interval_node *node,
109                                       struct interval_node **root);
110 void interval_erase(struct interval_node *node, struct interval_node **root);
111
112 /* Search the extents in the tree and call @func for each overlapped
113  * extents. */
114 enum interval_iter interval_search(struct interval_node *root,
115                                    struct interval_node_extent *ex,
116                                    interval_callback_t func, void *data);
117
118 /* Iterate every node in the tree - by reverse order or regular order. */
119 enum interval_iter interval_iterate(struct interval_node *root, 
120                                     interval_callback_t func, void *data);
121 enum interval_iter interval_iterate_reverse(struct interval_node *root,
122                                     interval_callback_t func,void *data);
123
124 void interval_expand(struct interval_node *root, 
125                      struct interval_node_extent *ext,
126                      struct interval_node_extent *limiter);
127 int interval_is_overlapped(struct interval_node *root, 
128                            struct interval_node_extent *ex);
129 struct interval_node *interval_find(struct interval_node *root,
130                                     struct interval_node_extent *ex);
131 #endif