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 } 192