1
2
3
4
5
6
7
8
9
10#include <linux/rbtree_augmented.h>
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
29 ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
30 \
31 \
32 \
33static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
34{ \
35 ITTYPE max = ITLAST(node), subtree_last; \
36 if (node->ITRB.rb_left) { \
37 subtree_last = rb_entry(node->ITRB.rb_left, \
38 ITSTRUCT, ITRB)->ITSUBTREE; \
39 if (max < subtree_last) \
40 max = subtree_last; \
41 } \
42 if (node->ITRB.rb_right) { \
43 subtree_last = rb_entry(node->ITRB.rb_right, \
44 ITSTRUCT, ITRB)->ITSUBTREE; \
45 if (max < subtree_last) \
46 max = subtree_last; \
47 } \
48 return max; \
49} \
50 \
51RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \
52 ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \
53 \
54 \
55 \
56ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
57 struct rb_root_cached *root) \
58{ \
59 struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
60 ITTYPE start = ITSTART(node), last = ITLAST(node); \
61 ITSTRUCT *parent; \
62 bool leftmost = true; \
63 \
64 while (*link) { \
65 rb_parent = *link; \
66 parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
67 if (parent->ITSUBTREE < last) \
68 parent->ITSUBTREE = last; \
69 if (start < ITSTART(parent)) \
70 link = &parent->ITRB.rb_left; \
71 else { \
72 link = &parent->ITRB.rb_right; \
73 leftmost = false; \
74 } \
75 } \
76 \
77 node->ITSUBTREE = last; \
78 rb_link_node(&node->ITRB, rb_parent, link); \
79 rb_insert_augmented_cached(&node->ITRB, root, \
80 leftmost, &ITPREFIX ## _augment); \
81} \
82 \
83ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
84 struct rb_root_cached *root) \
85{ \
86 rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \
87} \
88 \
89
90
91
92
93
94
95
96 \
97 \
98static ITSTRUCT * \
99ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
100{ \
101 while (true) { \
102
103
104
105 \
106 if (node->ITRB.rb_left) { \
107 ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
108 ITSTRUCT, ITRB); \
109 if (start <= left->ITSUBTREE) { \
110
111
112
113
114
115
116
117 \
118 node = left; \
119 continue; \
120 } \
121 } \
122 if (ITSTART(node) <= last) { \
123 if (start <= ITLAST(node)) \
124 return node; \
125 if (node->ITRB.rb_right) { \
126 node = rb_entry(node->ITRB.rb_right, \
127 ITSTRUCT, ITRB); \
128 if (start <= node->ITSUBTREE) \
129 continue; \
130 } \
131 } \
132 return NULL; \
133 } \
134} \
135 \
136ITSTATIC ITSTRUCT * \
137ITPREFIX ## _iter_first(struct rb_root_cached *root, \
138 ITTYPE start, ITTYPE last) \
139{ \
140 ITSTRUCT *node, *leftmost; \
141 \
142 if (!root->rb_root.rb_node) \
143 return NULL; \
144 \
145
146
147
148
149
150
151
152
153
154
155
156
157 \
158 node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
159 if (node->ITSUBTREE < start) \
160 return NULL; \
161 \
162 leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \
163 if (ITSTART(leftmost) > last) \
164 return NULL; \
165 \
166 return ITPREFIX ## _subtree_search(node, start, last); \
167} \
168 \
169ITSTATIC ITSTRUCT * \
170ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
171{ \
172 struct rb_node *rb = node->ITRB.rb_right, *prev; \
173 \
174 while (true) { \
175
176
177
178
179
180
181 \
182 if (rb) { \
183 ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
184 if (start <= right->ITSUBTREE) \
185 return ITPREFIX ## _subtree_search(right, \
186 start, last); \
187 } \
188 \
189 \
190 do { \
191 rb = rb_parent(&node->ITRB); \
192 if (!rb) \
193 return NULL; \
194 prev = &node->ITRB; \
195 node = rb_entry(rb, ITSTRUCT, ITRB); \
196 rb = node->ITRB.rb_right; \
197 } while (prev == rb); \
198 \
199 \
200 if (last < ITSTART(node)) \
201 return NULL; \
202 else if (start <= ITLAST(node)) \
203 return node; \
204 } \
205}
206