aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux/interval_tree_tmpl.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/linux/interval_tree_tmpl.h')
-rw-r--r--include/linux/interval_tree_tmpl.h215
1 files changed, 215 insertions, 0 deletions
diff --git a/include/linux/interval_tree_tmpl.h b/include/linux/interval_tree_tmpl.h
new file mode 100644
index 000000000000..c65deda31413
--- /dev/null
+++ b/include/linux/interval_tree_tmpl.h
@@ -0,0 +1,215 @@
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_tmpl.h
20*/
21
22/*
23 * Template for implementing interval trees
24 *
25 * ITSTRUCT: struct type of the interval tree nodes
26 * ITRB: name of struct rb_node field within ITSTRUCT
27 * ITTYPE: type of the interval endpoints
28 * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
29 * ITSTART(n): start endpoint of ITSTRUCT node n
30 * ITLAST(n): last endpoing of ITSTRUCT node n
31 * ITSTATIC: 'static' or empty
32 * ITPREFIX: prefix to use for the inline tree definitions
33 */
34
35/* IT(name) -> ITPREFIX_name */
36#define _ITNAME(prefix, name) prefix ## _ ## name
37#define ITNAME(prefix, name) _ITNAME(prefix, name)
38#define IT(name) ITNAME(ITPREFIX, name)
39
40/* Callbacks for augmented rbtree insert and remove */
41
42static inline ITTYPE IT(compute_subtree_last)(ITSTRUCT *node)
43{
44 ITTYPE max = ITLAST(node), subtree_last;
45 if (node->ITRB.rb_left) {
46 subtree_last = rb_entry(node->ITRB.rb_left,
47 ITSTRUCT, ITRB)->ITSUBTREE;
48 if (max < subtree_last)
49 max = subtree_last;
50 }
51 if (node->ITRB.rb_right) {
52 subtree_last = rb_entry(node->ITRB.rb_right,
53 ITSTRUCT, ITRB)->ITSUBTREE;
54 if (max < subtree_last)
55 max = subtree_last;
56 }
57 return max;
58}
59
60static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
61{
62 while (rb != stop) {
63 ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
64 ITTYPE subtree_last = IT(compute_subtree_last)(node);
65 if (node->ITSUBTREE == subtree_last)
66 break;
67 node->ITSUBTREE = subtree_last;
68 rb = rb_parent(&node->ITRB);
69 }
70}
71
72static void IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
73{
74 ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
75 ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
76
77 new->ITSUBTREE = old->ITSUBTREE;
78}
79
80static void IT(augment_rotate)(struct rb_node *rb_old, struct rb_node *rb_new)
81{
82 ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
83 ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
84
85 new->ITSUBTREE = old->ITSUBTREE;
86 old->ITSUBTREE = IT(compute_subtree_last)(old);
87}
88
89static const struct rb_augment_callbacks IT(augment_callbacks) = {
90 IT(augment_propagate), IT(augment_copy), IT(augment_rotate)
91};
92
93/* Insert / remove interval nodes from the tree */
94
95ITSTATIC void IT(insert)(ITSTRUCT *node, struct rb_root *root)
96{
97 struct rb_node **link = &root->rb_node, *rb_parent = NULL;
98 ITTYPE start = ITSTART(node), last = ITLAST(node);
99 ITSTRUCT *parent;
100
101 while (*link) {
102 rb_parent = *link;
103 parent = rb_entry(rb_parent, ITSTRUCT, ITRB);
104 if (parent->ITSUBTREE < last)
105 parent->ITSUBTREE = last;
106 if (start < ITSTART(parent))
107 link = &parent->ITRB.rb_left;
108 else
109 link = &parent->ITRB.rb_right;
110 }
111
112 node->ITSUBTREE = last;
113 rb_link_node(&node->ITRB, rb_parent, link);
114 rb_insert_augmented(&node->ITRB, root, &IT(augment_callbacks));
115}
116
117ITSTATIC void IT(remove)(ITSTRUCT *node, struct rb_root *root)
118{
119 rb_erase_augmented(&node->ITRB, root, &IT(augment_callbacks));
120}
121
122/*
123 * Iterate over intervals intersecting [start;last]
124 *
125 * Note that a node's interval intersects [start;last] iff:
126 * Cond1: ITSTART(node) <= last
127 * and
128 * Cond2: start <= ITLAST(node)
129 */
130
131static ITSTRUCT *IT(subtree_search)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
132{
133 while (true) {
134 /*
135 * Loop invariant: start <= node->ITSUBTREE
136 * (Cond2 is satisfied by one of the subtree nodes)
137 */
138 if (node->ITRB.rb_left) {
139 ITSTRUCT *left = rb_entry(node->ITRB.rb_left,
140 ITSTRUCT, ITRB);
141 if (start <= left->ITSUBTREE) {
142 /*
143 * Some nodes in left subtree satisfy Cond2.
144 * Iterate to find the leftmost such node N.
145 * If it also satisfies Cond1, that's the match
146 * we are looking for. Otherwise, there is no
147 * matching interval as nodes to the right of N
148 * can't satisfy Cond1 either.
149 */
150 node = left;
151 continue;
152 }
153 }
154 if (ITSTART(node) <= last) { /* Cond1 */
155 if (start <= ITLAST(node)) /* Cond2 */
156 return node; /* node is leftmost match */
157 if (node->ITRB.rb_right) {
158 node = rb_entry(node->ITRB.rb_right,
159 ITSTRUCT, ITRB);
160 if (start <= node->ITSUBTREE)
161 continue;
162 }
163 }
164 return NULL; /* No match */
165 }
166}
167
168ITSTATIC ITSTRUCT *IT(iter_first)(struct rb_root *root,
169 ITTYPE start, ITTYPE last)
170{
171 ITSTRUCT *node;
172
173 if (!root->rb_node)
174 return NULL;
175 node = rb_entry(root->rb_node, ITSTRUCT, ITRB);
176 if (node->ITSUBTREE < start)
177 return NULL;
178 return IT(subtree_search)(node, start, last);
179}
180
181ITSTATIC ITSTRUCT *IT(iter_next)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
182{
183 struct rb_node *rb = node->ITRB.rb_right, *prev;
184
185 while (true) {
186 /*
187 * Loop invariants:
188 * Cond1: ITSTART(node) <= last
189 * rb == node->ITRB.rb_right
190 *
191 * First, search right subtree if suitable
192 */
193 if (rb) {
194 ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);
195 if (start <= right->ITSUBTREE)
196 return IT(subtree_search)(right, start, last);
197 }
198
199 /* Move up the tree until we come from a node's left child */
200 do {
201 rb = rb_parent(&node->ITRB);
202 if (!rb)
203 return NULL;
204 prev = &node->ITRB;
205 node = rb_entry(rb, ITSTRUCT, ITRB);
206 rb = node->ITRB.rb_right;
207 } while (prev == rb);
208
209 /* Check if the node intersects [start;last] */
210 if (last < ITSTART(node)) /* !Cond1 */
211 return NULL;
212 else if (start <= ITLAST(node)) /* Cond2 */
213 return node;
214 }
215}
generated by cgit v1.2.2 (git 2.25.0) at 2025-03-11 09:35:01 -0400