lustre/include/interval_tree.h

   1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
   2  * (visit-tags-table FILE)
   3  * vim:expandtab:shiftwidth=8:tabstop=8:
   4  *
   5  *  Copyright (c) 2002, 2007 Cluster File Systems, Inc.
   6  *   Author: Huang Wei <huangwei@clusterfs.com>
   7  *   Author: Jay Xiong <jinshan.xiong@sun.com>
   8  *
   9  *   This file is part of the Lustre file system, http://www.lustre.org
  10  *   Lustre is a trademark of Cluster File Systems, Inc.
  11  *
  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.
  16  *
  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.
  21  *
  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.
  26  */
  27
  28 #ifndef _INTERVAL_H__
  29 #define _INTERVAL_H__
  30
  31 #include <libcfs/types.h>  /* __u8, __u64 etc. */
  32 #include <libcfs/kp30.h>   /* LASSERT. */
  33
  34 struct interval_node {
  35         struct interval_node   *in_left;
  36         struct interval_node   *in_right;
  37         struct interval_node   *in_parent;
  38         __u8                    in_color;
  39         __u8                    res1[7];  /* tags, 8-bytes aligned */
  40         __u64                   in_max_high;
  41         struct interval_node_extent {
  42                 __u64 start;
  43                 __u64 end;
  44         } in_extent;
  45 };
  46
  47 enum interval_iter {
  48         INTERVAL_ITER_CONT = 1,
  49         INTERVAL_ITER_STOP = 2
  50 };
  51
  52 static inline __u64 interval_low(struct interval_node *node)
  53 {
  54         return node->in_extent.start;
  55 }
  56
  57 static inline __u64 interval_high(struct interval_node *node)
  58 {
  59         return node->in_extent.end;
  60 }
  61
  62 static inline void interval_set(struct interval_node *node,
  63                                 __u64 start, __u64 end)
  64 {
  65         LASSERT(start <= end);
  66         node->in_extent.start = start;
  67         node->in_extent.end = end;
  68         node->in_max_high = end;
  69 }
  70
  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.
  79  */
  80 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
  81                                                   void *args);
  82
  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);
  86
  87 /* Search the extents in the tree and call @func for each overlapped
  88  * extents. */
  89 enum interval_iter interval_search(struct interval_node *root,
  90                                    struct interval_node_extent *ex,
  91                                    interval_callback_t func, void *data);
  92
  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);
  98
  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);
 106 #endif