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 <stdbool.h>
  23
  24 #include "rbtree_augmented.h"
  25
  26 /*
  27  * Template for implementing interval trees
  28  *
  29  * ITSTRUCT:   struct type of the interval tree nodes
  30  * ITRB:       name of struct rb_node field within ITSTRUCT
  31  * ITTYPE:     type of the interval endpoints
  32  * ITSUBTREE:  name of ITTYPE field within ITSTRUCT holding last-in-subtree
  33  * ITSTART(n): start endpoint of ITSTRUCT node n
  34  * ITLAST(n):  last endpoint of ITSTRUCT node n
  35  * ITSTATIC:   'static' or empty
  36  * ITPREFIX:   prefix to use for the inline tree definitions
  37  *
  38  * Note - before using this, please consider if non-generic version
  39  * (interval_tree.h) would work for you...
  40  */
  41
  42 #define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,               \
  43                              ITSTART, ITLAST, ITSTATIC, ITPREFIX)             \
  44                                                                               \
  45 /* Callbacks for augmented rbtree insert and remove */                        \
  46                                                                               \
  47 static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)        \
  48 {                                                                             \
  49         ITTYPE max = ITLAST(node), subtree_last;                              \
  50         if (node->ITRB.rb_left) {                                             \
  51                 subtree_last = rb_entry(node->ITRB.rb_left,                   \
  52                                         ITSTRUCT, ITRB)->ITSUBTREE;           \
  53                 if (max < subtree_last)                                       \
  54                         max = subtree_last;                                   \
  55         }                                                                     \
  56         if (node->ITRB.rb_right) {                                            \
  57                 subtree_last = rb_entry(node->ITRB.rb_right,                  \
  58                                         ITSTRUCT, ITRB)->ITSUBTREE;           \
  59                 if (max < subtree_last)                                       \
  60                         max = subtree_last;                                   \
  61         }                                                                     \
  62         return max;                                                           \
  63 }                                                                             \
  64                                                                               \
  65 RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,            \
  66                      ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
  67                                                                               \
  68 /* Insert / remove interval nodes from the tree */                            \
  69                                                                               \
  70 ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root)       \
  71 {                                                                             \
  72         struct rb_node **link = &root->rb_node, *rb_parent = NULL;            \
  73         ITTYPE start = ITSTART(node), last = ITLAST(node);                    \
  74         ITSTRUCT *parent;                                                     \
  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         }                                                                     \
  86                                                                               \
  87         node->ITSUBTREE = last;                                               \
  88         rb_link_node(&node->ITRB, rb_parent, link);                           \
  89         rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment);        \
  90 }                                                                             \
  91                                                                               \
  92 ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root)       \
  93 {                                                                             \
  94         rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment);         \
  95 }                                                                             \
  96                                                                               \
  97 /*                                                                            \
  98  * Iterate over intervals intersecting [start;last]                           \
  99  *                                                                            \
 100  * Note that a node's interval intersects [start;last] iff:                   \
 101  *   Cond1: ITSTART(node) <= last                                             \
 102  * and                                                                        \
 103  *   Cond2: start <= ITLAST(node)                                             \
 104  */                                                                           \
 105                                                                               \
 106 static ITSTRUCT *                                                             \
 107 ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)        \
 108 {                                                                             \
 109         while (true) {                                                        \
 110                 /*                                                            \
 111                  * Loop invariant: start <= node->ITSUBTREE                   \
 112                  * (Cond2 is satisfied by one of the subtree nodes)           \
 113                  */                                                           \
 114                 if (node->ITRB.rb_left) {                                     \
 115                         ITSTRUCT *left = rb_entry(node->ITRB.rb_left,         \
 116                                                   ITSTRUCT, ITRB);            \
 117                         if (start <= left->ITSUBTREE) {                       \
 118                                 /*                                            \
 119                                  * Some nodes in left subtree satisfy Cond2.  \
 120                                  * Iterate to find the leftmost such node N.  \
 121                                  * If it also satisfies Cond1, that's the     \
 122                                  * match we are looking for. Otherwise, there \
 123                                  * is no matching interval as nodes to the    \
 124                                  * right of N can't satisfy Cond1 either.     \
 125                                  */                                           \
 126                                 node = left;                                  \
 127                                 continue;                                     \
 128                         }                                                     \
 129                 }                                                             \
 130                 if (ITSTART(node) <= last) {            /* Cond1 */           \
 131                         if (start <= ITLAST(node))      /* Cond2 */           \
 132                                 return node;    /* node is leftmost match */  \
 133                         if (node->ITRB.rb_right) {                            \
 134                                 node = rb_entry(node->ITRB.rb_right,          \
 135                                                 ITSTRUCT, ITRB);              \
 136                                 if (start <= node->ITSUBTREE)                 \
 137                                         continue;                             \
 138                         }                                                     \
 139                 }                                                             \
 140                 return NULL;    /* No match */                                \
 141         }                                                                     \
 142 }                                                                             \
 143                                                                               \
 144 ITSTATIC ITSTRUCT *                                                           \
 145 ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last)      \
 146 {                                                                             \
 147         ITSTRUCT *node;                                                       \
 148                                                                               \
 149         if (!root->rb_node)                                                   \
 150                 return NULL;                                                  \
 151         node = rb_entry(root->rb_node, ITSTRUCT, ITRB);                       \
 152         if (node->ITSUBTREE < start)                                          \
 153                 return NULL;                                                  \
 154         return ITPREFIX ## _subtree_search(node, start, last);                \
 155 }                                                                             \
 156                                                                               \
 157 ITSTATIC ITSTRUCT *                                                           \
 158 ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)             \
 159 {                                                                             \
 160         struct rb_node *rb = node->ITRB.rb_right, *prev;                      \
 161                                                                               \
 162         while (true) {                                                        \
 163                 /*                                                            \
 164                  * Loop invariants:                                           \
 165                  *   Cond1: ITSTART(node) <= last                             \
 166                  *   rb == node->ITRB.rb_right                                \
 167                  *                                                            \
 168                  * First, search right subtree if suitable                    \
 169                  */                                                           \
 170                 if (rb) {                                                     \
 171                         ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);       \
 172                         if (start <= right->ITSUBTREE)                        \
 173                                 return ITPREFIX ## _subtree_search(right,     \
 174                                                                 start, last); \
 175                 }                                                             \
 176                                                                               \
 177                 /* Move up the tree until we come from a node's left child */ \
 178                 do {                                                          \
 179                         rb = rb_parent(&node->ITRB);                          \
 180                         if (!rb)                                              \
 181                                 return NULL;                                  \
 182                         prev = &node->ITRB;                                   \
 183                         node = rb_entry(rb, ITSTRUCT, ITRB);                  \
 184                         rb = node->ITRB.rb_right;                             \
 185                 } while (prev == rb);                                         \
 186                                                                               \
 187                 /* Check if the node intersects [start;last] */               \
 188                 if (last < ITSTART(node))               /* !Cond1 */          \
 189                         return NULL;                                          \
 190                 else if (start <= ITLAST(node))         /* Cond2 */           \
 191                         return node;                                          \
 192         }                                                                     \
 193 }