Loading...
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}
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 \
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, \
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 \
95ITSTATIC 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 \
110static ITSTRUCT * \
111ITPREFIX ## _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 \
148ITSTATIC ITSTRUCT * \
149ITPREFIX ## _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 \
181ITSTATIC ITSTRUCT * \
182ITPREFIX ## _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}