1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * (visit-tags-table FILE)
3 * vim:expandtab:shiftwidth=8:tabstop=8:
5 * Copyright (c) 2002, 2007 Cluster File Systems, Inc.
6 * Author: Huang Wei <huangwei@clusterfs.com>
7 * Author: Jay Xiong <jinshan.xiong@sun.com>
9 * This file is part of the Lustre file system, http://www.lustre.org
10 * Lustre is a trademark of Cluster File Systems, Inc.
12 * You may have signed or agreed to another license before downloading
13 * this software. If so, you are bound by the terms and conditions
14 * of that agreement, and the following does not apply to you. See the
15 * LICENSE file included with this distribution for more information.
17 * If you did not agree to a different license, then this copy of Lustre
18 * is open source software; you can redistribute it and/or modify it
19 * under the terms of version 2 of the GNU General Public License as
20 * published by the Free Software Foundation.
22 * In either case, Lustre is distributed in the hope that it will be
23 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
24 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * license text for more details.
31 #include <libcfs/types.h> /* __u8, __u64 etc. */
32 #include <libcfs/kp30.h> /* LASSERT. */
34 struct interval_node {
35 struct interval_node *in_left;
36 struct interval_node *in_right;
37 struct interval_node *in_parent;
39 __u8 res1[7]; /* tags, 8-bytes aligned */
41 struct interval_node_extent {
48 INTERVAL_ITER_CONT = 1,
49 INTERVAL_ITER_STOP = 2
52 static inline __u64 interval_low(struct interval_node *node)
54 return node->in_extent.start;
57 static inline __u64 interval_high(struct interval_node *node)
59 return node->in_extent.end;
62 static inline void interval_set(struct interval_node *node,
63 __u64 start, __u64 end)
65 LASSERT(start <= end);
66 node->in_extent.start = start;
67 node->in_extent.end = end;
68 node->in_max_high = end;
71 /* Rules to write an interval callback.
72 * - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
73 * should be stopped. It will then cause the iteration function to return
74 * immediately with return value INTERVAL_ITER_STOP.
75 * - callbacks for interval_iterate and interval_iterate_reverse: Every
76 * nodes in the tree will be set to @node before the callback being called
77 * - callback for interval_search: Only overlapped node will be set to @node
78 * before the callback being called.
80 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
83 struct interval_node *interval_insert(struct interval_node *node,
84 struct interval_node **root);
85 void interval_erase(struct interval_node *node, struct interval_node **root);
87 /* Search the extents in the tree and call @func for each overlapped
89 enum interval_iter interval_search(struct interval_node *root,
90 struct interval_node_extent *ex,
91 interval_callback_t func, void *data);
93 /* Iterate every node in the tree - by reverse order or regular order. */
94 enum interval_iter interval_iterate(struct interval_node *root,
95 interval_callback_t func, void *data);
96 enum interval_iter interval_iterate_reverse(struct interval_node *root,
97 interval_callback_t func,void *data);
99 void interval_expand(struct interval_node *root,
100 struct interval_node_extent *ext,
101 struct interval_node_extent *limiter);
102 int interval_is_overlapped(struct interval_node *root,
103 struct interval_node_extent *ex);
104 struct interval_node *interval_find(struct interval_node *root,
105 struct interval_node_extent *ex);