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.sun.com/software/products/lustre/docs/GPLv2.pdf
19 *
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
22 * have any questions.
23 *
24 * GPL HEADER END
25 */
26 /*
27 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
29 */
30 /*
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
33 *
34 * lustre/include/interval_tree.h
35 *
36 * Author: Huang Wei <huangwei@clusterfs.com>
37 * Author: Jay Xiong <jinshan.xiong@sun.com>
38 */
39
40 #ifndef _INTERVAL_H__
41 #define _INTERVAL_H__
42
43 #include "../../include/linux/libcfs/libcfs.h" /* LASSERT. */
44
45 struct interval_node {
46 struct interval_node *in_left;
47 struct interval_node *in_right;
48 struct interval_node *in_parent;
49 unsigned in_color:1,
50 in_intree:1, /** set if the node is in tree */
51 in_res1:30;
52 __u8 in_res2[4]; /** tags, 8-bytes aligned */
53 __u64 in_max_high;
54 struct interval_node_extent {
55 __u64 start;
56 __u64 end;
57 } in_extent;
58 };
59
60 enum interval_iter {
61 INTERVAL_ITER_CONT = 1,
62 INTERVAL_ITER_STOP = 2
63 };
64
interval_is_intree(struct interval_node * node)65 static inline int interval_is_intree(struct interval_node *node)
66 {
67 return node->in_intree == 1;
68 }
69
interval_high(struct interval_node * node)70 static inline __u64 interval_high(struct interval_node *node)
71 {
72 return node->in_extent.end;
73 }
74
interval_set(struct interval_node * node,__u64 start,__u64 end)75 static inline void interval_set(struct interval_node *node,
76 __u64 start, __u64 end)
77 {
78 LASSERT(start <= end);
79 node->in_extent.start = start;
80 node->in_extent.end = end;
81 node->in_max_high = end;
82 }
83
84 struct interval_node *interval_insert(struct interval_node *node,
85 struct interval_node **root);
86 void interval_erase(struct interval_node *node, struct interval_node **root);
87
88 #endif
89