lustre/include/interval_tree.h

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   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.
   9  *
  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).
  15  *
  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
  19  *
  20  * GPL HEADER END
  21  */
  22 /*
  23  * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26 /*
  27  * This file is part of Lustre, http://www.lustre.org/
  28  *
  29  * lustre/include/interval_tree.h
  30  *
  31  * Author: Huang Wei <huangwei@clusterfs.com>
  32  * Author: Jay Xiong <jinshan.xiong@sun.com>
  33  */
  34
  35 #ifndef _INTERVAL_H__
  36 #define _INTERVAL_H__
  37
  38 #include <linux/errno.h>
  39 #include <linux/string.h>
  40 #include <linux/types.h>
  41
  42 struct interval_node {
  43         struct interval_node   *in_left;
  44         struct interval_node   *in_right;
  45         struct interval_node   *in_parent;
  46         unsigned                in_color:1,
  47                                 in_intree:1, /** set if the node is in tree */
  48                                 in_res1:30;
  49         __u8                    in_res2[4];  /** tags, 8-bytes aligned */
  50         __u64                   in_max_high;
  51         struct interval_node_extent {
  52                 __u64 start;
  53                 __u64 end;
  54         } in_extent;
  55 };
  56
  57 enum interval_iter {
  58         INTERVAL_ITER_CONT = 1,
  59         INTERVAL_ITER_STOP = 2
  60 };
  61
  62 static inline int interval_is_intree(struct interval_node *node)
  63 {
  64         return node->in_intree == 1;
  65 }
  66
  67 static inline __u64 interval_low(struct interval_node *node)
  68 {
  69         return node->in_extent.start;
  70 }
  71
  72 static inline __u64 interval_high(struct interval_node *node)
  73 {
  74         return node->in_extent.end;
  75 }
  76
  77 static inline int interval_set(struct interval_node *node,
  78                                __u64 start, __u64 end)
  79 {
  80         if (start > end)
  81                 return -ERANGE;
  82         node->in_extent.start = start;
  83         node->in_extent.end = end;
  84         node->in_max_high = end;
  85         return 0;
  86 }
  87
  88 static inline void interval_init(struct interval_node *node)
  89 {
  90         memset(node, 0, sizeof(*node));
  91 }
  92
  93 int node_equal(struct interval_node *n1, struct interval_node *n2);
  94
  95 /* Rules to write an interval callback.
  96  *  - the callback returns INTERVAL_ITER_STOP when it thinks the iteration
  97  *    should be stopped. It will then cause the iteration function to return
  98  *    immediately with return value INTERVAL_ITER_STOP.
  99  *  - callbacks for interval_iterate and interval_iterate_reverse: Every
 100  *    nodes in the tree will be set to @node before the callback being called
 101  *  - callback for interval_search: Only overlapped node will be set to @node
 102  *    before the callback being called.
 103  */
 104 typedef enum interval_iter (*interval_callback_t)(struct interval_node *node,
 105                                                   void *args);
 106
 107 struct interval_node *interval_insert(struct interval_node *node,
 108                                       struct interval_node **root);
 109 void interval_erase(struct interval_node *node, struct interval_node **root);
 110
 111 /* Search the extents in the tree and call @func for each overlapped
 112  * extents. */
 113 enum interval_iter interval_search(struct interval_node *root,
 114                                    struct interval_node_extent *ex,
 115                                    interval_callback_t func, void *data);
 116
 117 /* Iterate every node in the tree - by reverse order or regular order. */
 118 enum interval_iter interval_iterate(struct interval_node *root,
 119                                     interval_callback_t func, void *data);
 120 enum interval_iter interval_iterate_reverse(struct interval_node *root,
 121                                     interval_callback_t func,void *data);
 122
 123 void interval_expand(struct interval_node *root,
 124                      struct interval_node_extent *ext,
 125                      struct interval_node_extent *limiter);
 126 int interval_is_overlapped(struct interval_node *root,
 127                            struct interval_node_extent *ex);
 128 struct interval_node *interval_find(struct interval_node *root,
 129                                     struct interval_node_extent *ex);
 130 #endif