Commit | Line | Data |
---|---|---|
9826a516 ML |
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 | } |