linux/include/linux/interval_tree_generic.h
<<
>>
Prefs
   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                                                                              \
  45static 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                                                                              \
  63RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,            \
  64                     ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
  65                                                                              \
  66/* Insert / remove interval nodes from the tree */                            \
  67                                                                              \
  68ITSTATIC 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                                                                              \
  90ITSTATIC 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                                                                              \
 104static ITSTRUCT *                                                             \
 105ITPREFIX ## _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                                                                              \
 142ITSTATIC ITSTRUCT *                                                           \
 143ITPREFIX ## _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                                                                              \
 155ITSTATIC ITSTRUCT *                                                           \
 156ITPREFIX ## _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}
 192
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.