Root/
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 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9