kernel/drivers/staging/lustre/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.sun.com/software/products/lustre/docs/GPLv2.pdf
  19  *
  20  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  21  * CA 95054 USA or visit www.sun.com if you need additional information or
  22  * have any questions.
  23  *
  24  * GPL HEADER END
  25  */
  26 /*
  27  * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
  28  * Use is subject to license terms.
  29  */
  30 /*
  31  * This file is part of Lustre, http://www.lustre.org/
  32  * Lustre is a trademark of Sun Microsystems, Inc.
  33  *
  34  * lustre/include/interval_tree.h
  35  *
  36  * Author: Huang Wei <huangwei@clusterfs.com>
  37  * Author: Jay Xiong <jinshan.xiong@sun.com>
  38  */
  39
  40 #ifndef _INTERVAL_H__
  41 #define _INTERVAL_H__
  42
  43 #include "../../include/linux/libcfs/libcfs.h"  /* LASSERT. */
  44
  45 struct interval_node {
  46         struct interval_node   *in_left;
  47         struct interval_node   *in_right;
  48         struct interval_node   *in_parent;
  49         unsigned                in_color:1,
  50                                 in_intree:1, /** set if the node is in tree */
  51                                 in_res1:30;
  52         __u8                in_res2[4];  /** 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 int interval_is_intree(struct interval_node *node)
  66 {
  67         return node->in_intree == 1;
  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 struct interval_node *interval_insert(struct interval_node *node,
  85                                       struct interval_node **root);
  86 void interval_erase(struct interval_node *node, struct interval_node **root);
  87
  88 #endif