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