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 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,                             \
  69                                   struct rb_root_cached *root)                \
  70 {                                                                             \
  71         struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL;    \
  72         ITTYPE start = ITSTART(node), last = ITLAST(node);                    \
  73         ITSTRUCT *parent;                                                     \
  74         bool leftmost = true;                                                 \
  75                                                                               \
  76         while (*link) {                                                       \
  77                 rb_parent = *link;                                            \
  78                 parent = rb_entry(rb_parent, ITSTRUCT, ITRB);                 \
  79                 if (parent->ITSUBTREE < last)                                 \
  80                         parent->ITSUBTREE = last;                             \
  81                 if (start < ITSTART(parent))                                  \
  82                         link = &parent->ITRB.rb_left;                         \
  83                 else {                                                        \
  84                         link = &parent->ITRB.rb_right;                        \
  85                         leftmost = false;                                     \
  86                 }                                                             \
  87         }                                                                     \
  88                                                                               \
  89         node->ITSUBTREE = last;                                               \
  90         rb_link_node(&node->ITRB, rb_parent, link);                           \
  91         rb_insert_augmented_cached(&node->ITRB, root,                         \
  92                                    leftmost, &ITPREFIX ## _augment);          \
  93 }                                                                             \
  94                                                                               \
  95 ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node,                             \
  96                                   struct rb_root_cached *root)                \
  97 {                                                                             \
  98         rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment);  \
  99 }                                                                             \
 100                                                                               \
 101 /*                                                                            \
 102  * Iterate over intervals intersecting [start;last]                           \
 103  *                                                                            \
 104  * Note that a node's interval intersects [start;last] iff:                   \
 105  *   Cond1: ITSTART(node) <= last                                             \
 106  * and                                                                        \
 107  *   Cond2: start <= ITLAST(node)                                             \
 108  */                                                                           \
 109                                                                               \
 110 static ITSTRUCT *                                                             \
 111 ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)        \
 112 {                                                                             \
 113         while (true) {                                                        \
 114                 /*                                                            \
 115                  * Loop invariant: start <= node->ITSUBTREE                   \
 116                  * (Cond2 is satisfied by one of the subtree nodes)           \
 117                  */                                                           \
 118                 if (node->ITRB.rb_left) {                                     \
 119                         ITSTRUCT *left = rb_entry(node->ITRB.rb_left,         \
 120                                                   ITSTRUCT, ITRB);            \
 121                         if (start <= left->ITSUBTREE) {                       \
 122                                 /*                                            \
 123                                  * Some nodes in left subtree satisfy Cond2.  \
 124                                  * Iterate to find the leftmost such node N.  \
 125                                  * If it also satisfies Cond1, that's the     \
 126                                  * match we are looking for. Otherwise, there \
 127                                  * is no matching interval as nodes to the    \
 128                                  * right of N can't satisfy Cond1 either.     \
 129                                  */                                           \
 130                                 node = left;                                  \
 131                                 continue;                                     \
 132                         }                                                     \
 133                 }                                                             \
 134                 if (ITSTART(node) <= last) {            /* Cond1 */           \
 135                         if (start <= ITLAST(node))      /* Cond2 */           \
 136                                 return node;    /* node is leftmost match */  \
 137                         if (node->ITRB.rb_right) {                            \
 138                                 node = rb_entry(node->ITRB.rb_right,          \
 139                                                 ITSTRUCT, ITRB);              \
 140                                 if (start <= node->ITSUBTREE)                 \
 141                                         continue;                             \
 142                         }                                                     \
 143                 }                                                             \
 144                 return NULL;    /* No match */                                \
 145         }                                                                     \
 146 }                                                                             \
 147                                                                               \
 148 ITSTATIC ITSTRUCT *                                                           \
 149 ITPREFIX ## _iter_first(struct rb_root_cached *root,                          \
 150                         ITTYPE start, ITTYPE last)                            \
 151 {                                                                             \
 152         ITSTRUCT *node, *leftmost;                                            \
 153                                                                               \
 154         if (!root->rb_root.rb_node)                                           \
 155                 return NULL;                                                  \
 156                                                                               \
 157         /*                                                                    \
 158          * Fastpath range intersection/overlap between A: [a0, a1] and        \
 159          * B: [b0, b1] is given by:                                           \
 160          *                                                                    \
 161          *         a0 <= b1 && b0 <= a1                                       \
 162          *                                                                    \
 163          *  ... where A holds the lock range and B holds the smallest         \
 164          * 'start' and largest 'last' in the tree. For the later, we          \
 165          * rely on the root node, which by augmented interval tree            \
 166          * property, holds the largest value in its last-in-subtree.          \
 167          * This allows mitigating some of the tree walk overhead for          \
 168          * for non-intersecting ranges, maintained and consulted in O(1).     \
 169          */                                                                   \
 170         node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB);               \
 171         if (node->ITSUBTREE < start)                                          \
 172                 return NULL;                                                  \
 173                                                                               \
 174         leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB);               \
 175         if (ITSTART(leftmost) > last)                                         \
 176                 return NULL;                                                  \
 177                                                                               \
 178         return ITPREFIX ## _subtree_search(node, start, last);                \
 179 }                                                                             \
 180                                                                               \
 181 ITSTATIC ITSTRUCT *                                                           \
 182 ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)             \
 183 {                                                                             \
 184         struct rb_node *rb = node->ITRB.rb_right, *prev;                      \
 185                                                                               \
 186         while (true) {                                                        \
 187                 /*                                                            \
 188                  * Loop invariants:                                           \
 189                  *   Cond1: ITSTART(node) <= last                             \
 190                  *   rb == node->ITRB.rb_right                                \
 191                  *                                                            \
 192                  * First, search right subtree if suitable                    \
 193                  */                                                           \
 194                 if (rb) {                                                     \
 195                         ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);       \
 196                         if (start <= right->ITSUBTREE)                        \
 197                                 return ITPREFIX ## _subtree_search(right,     \
 198                                                                 start, last); \
 199                 }                                                             \
 200                                                                               \
 201                 /* Move up the tree until we come from a node's left child */ \
 202                 do {                                                          \
 203                         rb = rb_parent(&node->ITRB);                          \
 204                         if (!rb)                                              \
 205                                 return NULL;                                  \
 206                         prev = &node->ITRB;                                   \
 207                         node = rb_entry(rb, ITSTRUCT, ITRB);                  \
 208                         rb = node->ITRB.rb_right;                             \
 209                 } while (prev == rb);                                         \
 210                                                                               \
 211                 /* Check if the node intersects [start;last] */               \
 212                 if (last < ITSTART(node))               /* !Cond1 */          \
 213                         return NULL;                                          \
 214                 else if (start <= ITLAST(node))         /* Cond2 */           \
 215                         return node;                                          \
 216         }                                                                     \
 217 }