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  2008 Sun Microsystems, Inc. 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         __u8                    in_color;
  52         __u8                    res1[7];  /* 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
  65 static inline __u64 interval_low(struct interval_node *node)
  66 {
  67         return node->in_extent.start;
  68 }
  69
  70 static inline __u64 interval_high(struct interval_node *node)
  71 {
  72         return node->in_extent.end;
  73 }
  74
  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 /* Rules to write an interval callback.
  85  *  - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
  86  *    should be stopped. It will then cause the iteration function to return
  87  *    immediately with return value INTERVAL_ITER_STOP.
  88  *  - callbacks for interval_iterate and interval_iterate_reverse: Every
  89  *    nodes in the tree will be set to @node before the callback being called
  90  *  - callback for interval_search: Only overlapped node will be set to @node
  91  *    before the callback being called.
  92  */
  93 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
  94                                                   void *args);
  95
  96 struct interval_node *interval_insert(struct interval_node *node,
  97                                       struct interval_node **root);
  98 void interval_erase(struct interval_node *node, struct interval_node **root);
  99
 100 /* Search the extents in the tree and call @func for each overlapped
 101  * extents. */
 102 enum interval_iter interval_search(struct interval_node *root,
 103                                    struct interval_node_extent *ex,
 104                                    interval_callback_t func, void *data);
 105
 106 /* Iterate every node in the tree - by reverse order or regular order. */
 107 enum interval_iter interval_iterate(struct interval_node *root,
 108                                     interval_callback_t func, void *data);
 109 enum interval_iter interval_iterate_reverse(struct interval_node *root,
 110                                     interval_callback_t func,void *data);
 111
 112 void interval_expand(struct interval_node *root,
 113                      struct interval_node_extent *ext,
 114                      struct interval_node_extent *limiter);
 115 int interval_is_overlapped(struct interval_node *root,
 116                            struct interval_node_extent *ex);
 117 struct interval_node *interval_find(struct interval_node *root,
 118                                     struct interval_node_extent *ex);
 119 #endif