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