include/linux/interval_tree_generic.h

   1 /*
   2   Interval Trees
   3   (C) 2012  Michel Lespinasse <walken@google.com>
   4
   5   This program is free software; you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation; either version 2 of the License, or
   8   (at your option) any later version.
   9
  10   This program is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program; if not, write to the Free Software
  17   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18
  19   include/linux/interval_tree_generic.h
  20 */
  21
  22 #include <linux/rbtree_augmented.h>
  23
  24 /*
  25  * Template for implementing interval trees
  26  *
  27  * ITSTRUCT:   struct type of the interval tree nodes
  28  * ITRB:       name of struct rb_node field within ITSTRUCT
  29  * ITTYPE:     type of the interval endpoints
  30  * ITSUBTREE:  name of ITTYPE field within ITSTRUCT holding last-in-subtree
  31  * ITSTART(n): start endpoint of ITSTRUCT node n
  32  * ITLAST(n):  last endpoint of ITSTRUCT node n
  33  * ITSTATIC:   'static' or empty
  34  * ITPREFIX:   prefix to use for the inline tree definitions
  35  *
  36  * Note - before using this, please consider if non-generic version
  37  * (interval_tree.h) would work for you...
  38  */
  39
  40 #define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,               \
  41                              ITSTART, ITLAST, ITSTATIC, ITPREFIX)             \
  42                                                                               \
  43 /* Callbacks for augmented rbtree insert and remove */                        \
  44                                                                               \
  45 static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)        \
  46 {                                                                             \
  47         ITTYPE max = ITLAST(node), subtree_last;                              \
  48         if (node->ITRB.rb_left) {                                             \
  49                 subtree_last = rb_entry(node->ITRB.rb_left,                   \
  50                                         ITSTRUCT, ITRB)->ITSUBTREE;           \
  51                 if (max < subtree_last)                                       \
  52                         max = subtree_last;                                   \
  53         }                                                                     \
  54         if (node->ITRB.rb_right) {                                            \
  55                 subtree_last = rb_entry(node->ITRB.rb_right,                  \
  56                                         ITSTRUCT, ITRB)->ITSUBTREE;           \
  57                 if (max < subtree_last)                                       \
  58                         max = subtree_last;                                   \
  59         }                                                                     \
  60         return max;                                                           \
  61 }                                                                             \
  62                                                                               \
  63 RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,            \
  64                      ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
  65                                                                               \
  66 /* Insert / remove interval nodes from the tree */                            \
  67                                                                               \
  68 ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root)       \
  69 {                                                                             \
  70         struct rb_node **link = &root->rb_node, *rb_parent = NULL;            \
  71         ITTYPE start = ITSTART(node), last = ITLAST(node);                    \
  72         ITSTRUCT *parent;                                                     \
  73                                                                               \
  74         while (*link) {                                                       \
  75                 rb_parent = *link;                                            \
  76                 parent = rb_entry(rb_parent, ITSTRUCT, ITRB);                 \
  77                 if (parent->ITSUBTREE < last)                                 \
  78                         parent->ITSUBTREE = last;                             \
  79                 if (start < ITSTART(parent))                                  \
  80                         link = &parent->ITRB.rb_left;                         \
  81                 else                                                          \
  82                         link = &parent->ITRB.rb_right;                        \
  83         }                                                                     \
  84                                                                               \
  85         node->ITSUBTREE = last;                                               \
  86         rb_link_node(&node->ITRB, rb_parent, link);                           \
  87         rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment);        \
  88 }                                                                             \
  89                                                                               \
  90 ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root)       \
  91 {                                                                             \
  92         rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment);         \
  93 }                                                                             \
  94                                                                               \
  95 /*                                                                            \
  96  * Iterate over intervals intersecting [start;last]                           \
  97  *                                                                            \
  98  * Note that a node's interval intersects [start;last] iff:                   \
  99  *   Cond1: ITSTART(node) <= last                                             \
 100  * and                                                                        \
 101  *   Cond2: start <= ITLAST(node)                                             \
 102  */                                                                           \
 103                                                                               \
 104 static ITSTRUCT *                                                             \
 105 ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)        \
 106 {                                                                             \
 107         while (true) {                                                        \
 108                 /*                                                            \
 109                  * Loop invariant: start <= node->ITSUBTREE                   \
 110                  * (Cond2 is satisfied by one of the subtree nodes)           \
 111                  */                                                           \
 112                 if (node->ITRB.rb_left) {                                     \
 113                         ITSTRUCT *left = rb_entry(node->ITRB.rb_left,         \
 114                                                   ITSTRUCT, ITRB);            \
 115                         if (start <= left->ITSUBTREE) {                       \
 116                                 /*                                            \
 117                                  * Some nodes in left subtree satisfy Cond2.  \
 118                                  * Iterate to find the leftmost such node N.  \
 119                                  * If it also satisfies Cond1, that's the     \
 120                                  * match we are looking for. Otherwise, there \
 121                                  * is no matching interval as nodes to the    \
 122                                  * right of N can't satisfy Cond1 either.     \
 123                                  */                                           \
 124                                 node = left;                                  \
 125                                 continue;                                     \
 126                         }                                                     \
 127                 }                                                             \
 128                 if (ITSTART(node) <= last) {            /* Cond1 */           \
 129                         if (start <= ITLAST(node))      /* Cond2 */           \
 130                                 return node;    /* node is leftmost match */  \
 131                         if (node->ITRB.rb_right) {                            \
 132                                 node = rb_entry(node->ITRB.rb_right,          \
 133                                                 ITSTRUCT, ITRB);              \
 134                                 if (start <= node->ITSUBTREE)                 \
 135                                         continue;                             \
 136                         }                                                     \
 137                 }                                                             \
 138                 return NULL;    /* No match */                                \
 139         }                                                                     \
 140 }                                                                             \
 141                                                                               \
 142 ITSTATIC ITSTRUCT *                                                           \
 143 ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last)      \
 144 {                                                                             \
 145         ITSTRUCT *node;                                                       \
 146                                                                               \
 147         if (!root->rb_node)                                                   \
 148                 return NULL;                                                  \
 149         node = rb_entry(root->rb_node, ITSTRUCT, ITRB);                       \
 150         if (node->ITSUBTREE < start)                                          \
 151                 return NULL;                                                  \
 152         return ITPREFIX ## _subtree_search(node, start, last);                \
 153 }                                                                             \
 154                                                                               \
 155 ITSTATIC ITSTRUCT *                                                           \
 156 ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)             \
 157 {                                                                             \
 158         struct rb_node *rb = node->ITRB.rb_right, *prev;                      \
 159                                                                               \
 160         while (true) {                                                        \
 161                 /*                                                            \
 162                  * Loop invariants:                                           \
 163                  *   Cond1: ITSTART(node) <= last                             \
 164                  *   rb == node->ITRB.rb_right                                \
 165                  *                                                            \
 166                  * First, search right subtree if suitable                    \
 167                  */                                                           \
 168                 if (rb) {                                                     \
 169                         ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);       \
 170                         if (start <= right->ITSUBTREE)                        \
 171                                 return ITPREFIX ## _subtree_search(right,     \
 172                                                                 start, last); \
 173                 }                                                             \
 174                                                                               \
 175                 /* Move up the tree until we come from a node's left child */ \
 176                 do {                                                          \
 177                         rb = rb_parent(&node->ITRB);                          \
 178                         if (!rb)                                              \
 179                                 return NULL;                                  \
 180                         prev = &node->ITRB;                                   \
 181                         node = rb_entry(rb, ITSTRUCT, ITRB);                  \
 182                         rb = node->ITRB.rb_right;                             \
 183                 } while (prev == rb);                                         \
 184                                                                               \
 185                 /* Check if the node intersects [start;last] */               \
 186                 if (last < ITSTART(node))               /* !Cond1 */          \
 187                         return NULL;                                          \
 188                 else if (start <= ITLAST(node))         /* Cond2 */           \
 189                         return node;                                          \
 190         }                                                                     \
 191 }