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