1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see [sun.com URL with a
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
29 * Copyright 2008 Sun Microsystems, Inc. All rights reserved
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
36 * lustre/include/interval_tree.h
38 * Author: Huang Wei <huangwei@clusterfs.com>
39 * Author: Jay Xiong <jinshan.xiong@sun.com>
45 #include <libcfs/types.h> /* __u8, __u64 etc. */
46 #include <libcfs/libcfs.h> /* LASSERT. */
48 struct interval_node {
49 struct interval_node *in_left;
50 struct interval_node *in_right;
51 struct interval_node *in_parent;
53 __u8 res1[7]; /* tags, 8-bytes aligned */
55 struct interval_node_extent {
62 INTERVAL_ITER_CONT = 1,
63 INTERVAL_ITER_STOP = 2
66 static inline __u64 interval_low(struct interval_node *node)
68 return node->in_extent.start;
71 static inline __u64 interval_high(struct interval_node *node)
73 return node->in_extent.end;
76 static inline void interval_set(struct interval_node *node,
77 __u64 start, __u64 end)
79 LASSERT(start <= end);
80 node->in_extent.start = start;
81 node->in_extent.end = end;
82 node->in_max_high = end;
85 /* Rules to write an interval callback.
86 * - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
87 * should be stopped. It will then cause the iteration function to return
88 * immediately with return value INTERVAL_ITER_STOP.
89 * - callbacks for interval_iterate and interval_iterate_reverse: Every
90 * nodes in the tree will be set to @node before the callback being called
91 * - callback for interval_search: Only overlapped node will be set to @node
92 * before the callback being called.
94 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
97 struct interval_node *interval_insert(struct interval_node *node,
98 struct interval_node **root);
99 void interval_erase(struct interval_node *node, struct interval_node **root);
101 /* Search the extents in the tree and call @func for each overlapped
103 enum interval_iter interval_search(struct interval_node *root,
104 struct interval_node_extent *ex,
105 interval_callback_t func, void *data);
107 /* Iterate every node in the tree - by reverse order or regular order. */
108 enum interval_iter interval_iterate(struct interval_node *root,
109 interval_callback_t func, void *data);
110 enum interval_iter interval_iterate_reverse(struct interval_node *root,
111 interval_callback_t func,void *data);
113 void interval_expand(struct interval_node *root,
114 struct interval_node_extent *ext,
115 struct interval_node_extent *limiter);
116 int interval_is_overlapped(struct interval_node *root,
117 struct interval_node_extent *ex);
118 struct interval_node *interval_find(struct interval_node *root,
119 struct interval_node_extent *ex);