1 /* Copied from linux/include/linux/rbtree_augmented.h */
2 /*
3 Red Black Trees
4 (C) 1999 Andrea Arcangeli <andrea@suse.de>
5 (C) 2002 David Woodhouse <dwmw2@infradead.org>
6 (C) 2012 Michel Lespinasse <walken@google.com>
7
8
9 linux/include/linux/rbtree_augmented.h
10 */
11
12 #ifndef _LINUX_RBTREE_AUGMENTED_H
13 #define _LINUX_RBTREE_AUGMENTED_H
14
15 #include "rbtree.h"
16 #include "linux_helpers.h"
17
18 /*
19 * Please note - only struct rb_augment_callbacks and the prototypes for
20 * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
21 * The rest are implementation details you are not expected to depend on.
22 *
23 * See Documentation/core-api/rbtree.rst for documentation and samples.
24 */
25
26 struct rb_augment_callbacks {
27 void (*propagate)(struct rb_node *node, struct rb_node *stop);
28 void (*copy)(struct rb_node *old, struct rb_node *new);
29 void (*rotate)(struct rb_node *old, struct rb_node *new);
30 };
31
32 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
33 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
34
35 /*
36 * Fixup the rbtree and update the augmented information when rebalancing.
37 *
38 * On insertion, the user must update the augmented information on the path
39 * leading to the inserted node, then call rb_link_node() as usual and
40 * rb_insert_augmented() instead of the usual rb_insert_color() call.
41 * If rb_insert_augmented() rebalances the rbtree, it will callback into
42 * a user provided function to update the augmented information on the
43 * affected subtrees.
44 */
45 static inline void
46 rb_insert_augmented(struct rb_node *node, struct rb_root *root,
47 const struct rb_augment_callbacks *augment)
48 {
49 __rb_insert_augmented(node, root, augment->rotate);
50 }
51
52 static inline void
53 rb_insert_augmented_cached(struct rb_node *node,
54 struct rb_root_cached *root, bool newleft,
55 const struct rb_augment_callbacks *augment)
56 {
57 if (newleft)
58 root->rb_leftmost = node;
59 rb_insert_augmented(node, &root->rb_root, augment);
60 }
61
62 /*
63 * Template for declaring augmented rbtree callbacks (generic case)
64 *
65 * RBSTATIC: 'static' or empty
66 * RBNAME: name of the rb_augment_callbacks structure
67 * RBSTRUCT: struct type of the tree nodes
68 * RBFIELD: name of struct rb_node field within RBSTRUCT
69 * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
70 * RBCOMPUTE: name of function that recomputes the RBAUGMENTED data
71 */
72
73 #define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \
74 RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \
75 static inline void \
76 RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop) \
77 { \
78 while (rb != stop) { \
79 RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD); \
80 if (RBCOMPUTE(node, true)) \
81 break; \
82 rb = rb_parent(&node->RBFIELD); \
83 } \
84 } \
85 static inline void \
86 RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
87 { \
88 RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \
89 RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \
90 new->RBAUGMENTED = old->RBAUGMENTED; \
91 } \
92 static void \
93 RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
94 { \
95 RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD); \
96 RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD); \
97 new->RBAUGMENTED = old->RBAUGMENTED; \
98 RBCOMPUTE(old, false); \
99 } \
100 RBSTATIC const struct rb_augment_callbacks RBNAME = { \
101 .propagate = RBNAME ## _propagate, \
102 .copy = RBNAME ## _copy, \
103 .rotate = RBNAME ## _rotate \
104 };
105
106 /*
107 * Template for declaring augmented rbtree callbacks,
108 * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
109 *
110 * RBSTATIC: 'static' or empty
111 * RBNAME: name of the rb_augment_callbacks structure
112 * RBSTRUCT: struct type of the tree nodes
113 * RBFIELD: name of struct rb_node field within RBSTRUCT
114 * RBTYPE: type of the RBAUGMENTED field
115 * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
116 * RBCOMPUTE: name of function that returns the per-node RBTYPE scalar
117 */
118
119 #define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, \
120 RBTYPE, RBAUGMENTED, RBCOMPUTE) \
121 static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit) \
122 { \
123 RBSTRUCT *child; \
124 RBTYPE max = RBCOMPUTE(node); \
125 if (node->RBFIELD.rb_left) { \
126 child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD); \
127 if (child->RBAUGMENTED > max) \
128 max = child->RBAUGMENTED; \
129 } \
130 if (node->RBFIELD.rb_right) { \
131 child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD); \
132 if (child->RBAUGMENTED > max) \
133 max = child->RBAUGMENTED; \
134 } \
135 if (exit && node->RBAUGMENTED == max) \
136 return true; \
137 node->RBAUGMENTED = max; \
138 return false; \
139 } \
140 RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, \
141 RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
142
143
144 #define RB_RED 0
145 #define RB_BLACK 1
146
147 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
148
149 #define __rb_color(pc) ((pc) & 1)
150 #define __rb_is_black(pc) __rb_color(pc)
151 #define __rb_is_red(pc) (!__rb_color(pc))
152 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
153 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
154 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
155
156 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
157 {
158 rb->__rb_parent_color = rb_color(rb) + (unsigned long)p;
159 }
160
161 static inline void rb_set_parent_color(struct rb_node *rb,
162 struct rb_node *p, int color)
163 {
|
(1) Event dereference: |
Dereferencing pointer "rb". |
164 rb->__rb_parent_color = (unsigned long)p + color;
165 }
166
167 static inline void
168 __rb_change_child(struct rb_node *old, struct rb_node *new,
169 struct rb_node *parent, struct rb_root *root)
170 {
171 if (parent) {
172 if (parent->rb_left == old)
173 WRITE_ONCE(parent->rb_left, new);
174 else
175 WRITE_ONCE(parent->rb_right, new);
176 } else
177 WRITE_ONCE(root->rb_node, new);
178 }
179
180 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
181 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
182
183 static __always_inline struct rb_node *
184 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
185 const struct rb_augment_callbacks *augment)
186 {
187 struct rb_node *child = node->rb_right;
188 struct rb_node *tmp = node->rb_left;
189 struct rb_node *parent, *rebalance;
190 unsigned long pc;
191
192 if (!tmp) {
193 /*
194 * Case 1: node to erase has no more than 1 child (easy!)
195 *
196 * Note that if there is one child it must be red due to 5)
197 * and node must be black due to 4). We adjust colors locally
198 * so as to bypass __rb_erase_color() later on.
199 */
200 pc = node->__rb_parent_color;
201 parent = __rb_parent(pc);
202 __rb_change_child(node, child, parent, root);
203 if (child) {
204 child->__rb_parent_color = pc;
205 rebalance = NULL;
206 } else
207 rebalance = __rb_is_black(pc) ? parent : NULL;
208 tmp = parent;
209 } else if (!child) {
210 /* Still case 1, but this time the child is node->rb_left */
211 tmp->__rb_parent_color = pc = node->__rb_parent_color;
212 parent = __rb_parent(pc);
213 __rb_change_child(node, tmp, parent, root);
214 rebalance = NULL;
215 tmp = parent;
216 } else {
217 struct rb_node *successor = child, *child2;
218
219 tmp = child->rb_left;
220 if (!tmp) {
221 /*
222 * Case 2: node's successor is its right child
223 *
224 * (n) (s)
225 * / \ / \
226 * (x) (s) -> (x) (c)
227 * \
228 * (c)
229 */
230 parent = successor;
231 child2 = successor->rb_right;
232
233 augment->copy(node, successor);
234 } else {
235 /*
236 * Case 3: node's successor is leftmost under
237 * node's right child subtree
238 *
239 * (n) (s)
240 * / \ / \
241 * (x) (y) -> (x) (y)
242 * / /
243 * (p) (p)
244 * / /
245 * (s) (c)
246 * \
247 * (c)
248 */
249 do {
250 parent = successor;
251 successor = tmp;
252 tmp = tmp->rb_left;
253 } while (tmp);
254 child2 = successor->rb_right;
255 WRITE_ONCE(parent->rb_left, child2);
256 WRITE_ONCE(successor->rb_right, child);
257 rb_set_parent(child, successor);
258
259 augment->copy(node, successor);
260 augment->propagate(parent, successor);
261 }
262
263 tmp = node->rb_left;
264 WRITE_ONCE(successor->rb_left, tmp);
265 rb_set_parent(tmp, successor);
266
267 pc = node->__rb_parent_color;
268 tmp = __rb_parent(pc);
269 __rb_change_child(node, successor, tmp, root);
270
271 if (child2) {
272 rb_set_parent_color(child2, parent, RB_BLACK);
273 rebalance = NULL;
274 } else {
275 rebalance = rb_is_black(successor) ? parent : NULL;
276 }
277 successor->__rb_parent_color = pc;
278 tmp = successor;
279 }
280
281 augment->propagate(tmp, NULL);
282 return rebalance;
283 }
284
285 static __always_inline void
286 rb_erase_augmented(struct rb_node *node, struct rb_root *root,
287 const struct rb_augment_callbacks *augment)
288 {
289 struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
290 if (rebalance)
291 __rb_erase_color(rebalance, root, augment->rotate);
292 }
293
294 static __always_inline void
295 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
296 const struct rb_augment_callbacks *augment)
297 {
298 if (root->rb_leftmost == node)
299 root->rb_leftmost = rb_next(node);
300 rb_erase_augmented(node, &root->rb_root, augment);
301 }
302
303 #endif /* _LINUX_RBTREE_AUGMENTED_H */
304