4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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
23 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Use is subject to license terms.
27 * This file is part of Lustre, http://www.lustre.org/
28 * Lustre is a trademark of Sun Microsystems, Inc.
30 * lustre/include/interval_tree.h
32 * Author: Huang Wei <huangwei@clusterfs.com>
33 * Author: Jay Xiong <jinshan.xiong@sun.com>
39 #include <linux/errno.h>
40 #include <linux/string.h>
41 #include <linux/types.h>
43 struct interval_node {
44 struct interval_node *in_left;
45 struct interval_node *in_right;
46 struct interval_node *in_parent;
48 in_intree:1, /** set if the node is in tree */
50 __u8 in_res2[4]; /** tags, 8-bytes aligned */
52 struct interval_node_extent {
59 INTERVAL_ITER_CONT = 1,
60 INTERVAL_ITER_STOP = 2
63 static inline int interval_is_intree(struct interval_node *node)
65 return node->in_intree == 1;
68 static inline __u64 interval_low(struct interval_node *node)
70 return node->in_extent.start;
73 static inline __u64 interval_high(struct interval_node *node)
75 return node->in_extent.end;
78 static inline int interval_set(struct interval_node *node,
79 __u64 start, __u64 end)
83 node->in_extent.start = start;
84 node->in_extent.end = end;
85 node->in_max_high = end;
90 * Rules to write an interval callback.
91 * - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
92 * should be stopped. It will then cause the iteration function to return
93 * immediately with return value INTERVAL_ITER_STOP.
94 * - callbacks for interval_iterate and interval_iterate_reverse: Every
95 * nodes in the tree will be set to @node before the callback being called
96 * - callback for interval_search: Only overlapped node will be set to @node
97 * before the callback being called.
99 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
102 struct interval_node *interval_insert(struct interval_node *node,
103 struct interval_node **root);
104 void interval_erase(struct interval_node *node, struct interval_node **root);
107 * Search the extents in the tree and call @func for each overlapped
110 enum interval_iter interval_search(struct interval_node *root,
111 struct interval_node_extent *ex,
112 interval_callback_t func, void *data);
114 enum interval_iter interval_iterate_reverse(struct interval_node *root,
115 interval_callback_t func,