aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 19:31:33 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:22:40 -0400
commit9c079add0d0f45220f4bb37febf0621137ec2d38 (patch)
treece6ba6d7e2d517a2004de856c882f2a08af12be2
parent147e615f83c2c36caf89e7a3bf78090ade6f266c (diff)
rbtree: move augmented rbtree functionality to rbtree_augmented.h
Provide rb_insert_augmented() and rb_erase_augmented() through a new rbtree_augmented.h include file. rb_erase_augmented() is defined there as an __always_inline function, in order to allow inlining of augmented rbtree callbacks into it. Since this generates a relatively large function, each augmented rbtree user should make sure to have a single call site. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat
-rw-r--r--Documentation/rbtree.txt13
-rw-r--r--arch/x86/mm/pat_rbtree.c2
-rw-r--r--include/linux/interval_tree_tmpl.h8
-rw-r--r--include/linux/rbtree.h48
-rw-r--r--include/linux/rbtree_augmented.h223
-rw-r--r--lib/rbtree.c162
-rw-r--r--lib/rbtree_test.c2
7 files changed, 255 insertions, 203 deletions
diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 0a0b6dce3e08..61b6c48871a0 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -202,6 +202,14 @@ An rbtree user who wants this feature will have to call the augmentation
202functions with the user provided augmentation callback when inserting 202functions with the user provided augmentation callback when inserting
203and erasing nodes. 203and erasing nodes.
204 204
205C files implementing augmented rbtree manipulation must include
206<linux/rbtree_augmented.h> instead of <linus/rbtree.h>. Note that
207linux/rbtree_augmented.h exposes some rbtree implementations details
208you are not expected to rely on; please stick to the documented APIs
209there and do not include <linux/rbtree_augmented.h> from header files
210either so as to minimize chances of your users accidentally relying on
211such implementation details.
212
205On insertion, the user must update the augmented information on the path 213On insertion, the user must update the augmented information on the path
206leading to the inserted node, then call rb_link_node() as usual and 214leading to the inserted node, then call rb_link_node() as usual and
207rb_augment_inserted() instead of the usual rb_insert_color() call. 215rb_augment_inserted() instead of the usual rb_insert_color() call.
@@ -227,6 +235,11 @@ In both cases, the callbacks are provided through struct rb_augment_callbacks.
227 subtree to a newly assigned subtree root AND recomputes the augmented 235 subtree to a newly assigned subtree root AND recomputes the augmented
228 information for the former subtree root. 236 information for the former subtree root.
229 237
238The compiled code for rb_erase_augmented() may inline the propagation and
239copy callbacks, which results in a large function, so each augmented rbtree
240user should have a single rb_erase_augmented() call site in order to limit
241compiled code size.
242
230 243
231Sample usage: 244Sample usage:
232 245
diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index 4d116959075d..415f6c4ced36 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -12,7 +12,7 @@
12#include <linux/debugfs.h> 12#include <linux/debugfs.h>
13#include <linux/kernel.h> 13#include <linux/kernel.h>
14#include <linux/module.h> 14#include <linux/module.h>
15#include <linux/rbtree.h> 15#include <linux/rbtree_augmented.h>
16#include <linux/sched.h> 16#include <linux/sched.h>
17#include <linux/gfp.h> 17#include <linux/gfp.h>
18 18
diff --git a/include/linux/interval_tree_tmpl.h b/include/linux/interval_tree_tmpl.h
index c65deda31413..c1aeb922d65f 100644
--- a/include/linux/interval_tree_tmpl.h
+++ b/include/linux/interval_tree_tmpl.h
@@ -19,6 +19,8 @@
19 include/linux/interval_tree_tmpl.h 19 include/linux/interval_tree_tmpl.h
20*/ 20*/
21 21
22#include <linux/rbtree_augmented.h>
23
22/* 24/*
23 * Template for implementing interval trees 25 * Template for implementing interval trees
24 * 26 *
@@ -57,7 +59,8 @@ static inline ITTYPE IT(compute_subtree_last)(ITSTRUCT *node)
57 return max; 59 return max;
58} 60}
59 61
60static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop) 62static inline void
63IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
61{ 64{
62 while (rb != stop) { 65 while (rb != stop) {
63 ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB); 66 ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
@@ -69,7 +72,8 @@ static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
69 } 72 }
70} 73}
71 74
72static void IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new) 75static inline void
76IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
73{ 77{
74 ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB); 78 ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
75 ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB); 79 ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d1e83b1c87b..0022c1bb1e26 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -62,54 +62,6 @@ extern void rb_insert_color(struct rb_node *, struct rb_root *);
62extern void rb_erase(struct rb_node *, struct rb_root *); 62extern void rb_erase(struct rb_node *, struct rb_root *);
63 63
64 64
65struct rb_augment_callbacks {
66 void (*propagate)(struct rb_node *node, struct rb_node *stop);
67 void (*copy)(struct rb_node *old, struct rb_node *new);
68 void (*rotate)(struct rb_node *old, struct rb_node *new);
69};
70
71extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
72 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
73extern void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
74 const struct rb_augment_callbacks *augment);
75static inline void
76rb_insert_augmented(struct rb_node *node, struct rb_root *root,
77 const struct rb_augment_callbacks *augment)
78{
79 __rb_insert_augmented(node, root, augment->rotate);
80}
81
82#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
83 rbtype, rbaugmented, rbcompute) \
84static void rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
85{ \
86 while (rb != stop) { \
87 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
88 rbtype augmented = rbcompute(node); \
89 if (node->rbaugmented == augmented) \
90 break; \
91 node->rbaugmented = augmented; \
92 rb = rb_parent(&node->rbfield); \
93 } \
94} \
95static void rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
96{ \
97 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
98 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
99 new->rbaugmented = old->rbaugmented; \
100} \
101static void rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
102{ \
103 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
104 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
105 new->rbaugmented = old->rbaugmented; \
106 old->rbaugmented = rbcompute(old); \
107} \
108rbstatic const struct rb_augment_callbacks rbname = { \
109 rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
110};
111
112
113/* Find logical next and previous nodes in a tree */ 65/* Find logical next and previous nodes in a tree */
114extern struct rb_node *rb_next(const struct rb_node *); 66extern struct rb_node *rb_next(const struct rb_node *);
115extern struct rb_node *rb_prev(const struct rb_node *); 67extern struct rb_node *rb_prev(const struct rb_node *);
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
new file mode 100644
index 000000000000..214caa33433b
--- /dev/null
+++ b/include/linux/rbtree_augmented.h
@@ -0,0 +1,223 @@
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/rbtree.h>
28
29/*
30 * Please note - only struct rb_augment_callbacks and the prototypes for
31 * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
32 * The rest are implementation details you are not expected to depend on.
33 *
34 * See Documentation/rbtree.txt for documentation and samples.
35 */
36
37struct rb_augment_callbacks {
38 void (*propagate)(struct rb_node *node, struct rb_node *stop);
39 void (*copy)(struct rb_node *old, struct rb_node *new);
40 void (*rotate)(struct rb_node *old, struct rb_node *new);
41};
42
43extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
44 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
45static inline void
46rb_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#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
53 rbtype, rbaugmented, rbcompute) \
54static inline void \
55rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
56{ \
57 while (rb != stop) { \
58 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
59 rbtype augmented = rbcompute(node); \
60 if (node->rbaugmented == augmented) \
61 break; \
62 node->rbaugmented = augmented; \
63 rb = rb_parent(&node->rbfield); \
64 } \
65} \
66static inline void \
67rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
68{ \
69 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
70 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
71 new->rbaugmented = old->rbaugmented; \
72} \
73static void \
74rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
75{ \
76 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
77 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
78 new->rbaugmented = old->rbaugmented; \
79 old->rbaugmented = rbcompute(old); \
80} \
81rbstatic const struct rb_augment_callbacks rbname = { \
82 rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
83};
84
85
86#define RB_RED 0
87#define RB_BLACK 1
88
89#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
90
91#define __rb_color(pc) ((pc) & 1)
92#define __rb_is_black(pc) __rb_color(pc)
93#define __rb_is_red(pc) (!__rb_color(pc))
94#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
95#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
96#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
97
98static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
99{
100 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
101}
102
103static inline void rb_set_parent_color(struct rb_node *rb,
104 struct rb_node *p, int color)
105{
106 rb->__rb_parent_color = (unsigned long)p | color;
107}
108
109static inline void
110__rb_change_child(struct rb_node *old, struct rb_node *new,
111 struct rb_node *parent, struct rb_root *root)
112{
113 if (parent) {
114 if (parent->rb_left == old)
115 parent->rb_left = new;
116 else
117 parent->rb_right = new;
118 } else
119 root->rb_node = new;
120}
121
122extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
123 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
124
125static __always_inline void
126rb_erase_augmented(struct rb_node *node, struct rb_root *root,
127 const struct rb_augment_callbacks *augment)
128{
129 struct rb_node *child = node->rb_right, *tmp = node->rb_left;
130 struct rb_node *parent, *rebalance;
131 unsigned long pc;
132
133 if (!tmp) {
134 /*
135 * Case 1: node to erase has no more than 1 child (easy!)
136 *
137 * Note that if there is one child it must be red due to 5)
138 * and node must be black due to 4). We adjust colors locally
139 * so as to bypass __rb_erase_color() later on.
140 */
141 pc = node->__rb_parent_color;
142 parent = __rb_parent(pc);
143 __rb_change_child(node, child, parent, root);
144 if (child) {
145 child->__rb_parent_color = pc;
146 rebalance = NULL;
147 } else
148 rebalance = __rb_is_black(pc) ? parent : NULL;
149 tmp = parent;
150 } else if (!child) {
151 /* Still case 1, but this time the child is node->rb_left */
152 tmp->__rb_parent_color = pc = node->__rb_parent_color;
153 parent = __rb_parent(pc);
154 __rb_change_child(node, tmp, parent, root);
155 rebalance = NULL;
156 tmp = parent;
157 } else {
158 struct rb_node *successor = child, *child2;
159 tmp = child->rb_left;
160 if (!tmp) {
161 /*
162 * Case 2: node's successor is its right child
163 *
164 * (n) (s)
165 * / \ / \
166 * (x) (s) -> (x) (c)
167 * \
168 * (c)
169 */
170 parent = successor;
171 child2 = successor->rb_right;
172 augment->copy(node, successor);
173 } else {
174 /*
175 * Case 3: node's successor is leftmost under
176 * node's right child subtree
177 *
178 * (n) (s)
179 * / \ / \
180 * (x) (y) -> (x) (y)
181 * / /
182 * (p) (p)
183 * / /
184 * (s) (c)
185 * \
186 * (c)
187 */
188 do {
189 parent = successor;
190 successor = tmp;
191 tmp = tmp->rb_left;
192 } while (tmp);
193 parent->rb_left = child2 = successor->rb_right;
194 successor->rb_right = child;
195 rb_set_parent(child, successor);
196 augment->copy(node, successor);
197 augment->propagate(parent, successor);
198 }
199
200 successor->rb_left = tmp = node->rb_left;
201 rb_set_parent(tmp, successor);
202
203 pc = node->__rb_parent_color;
204 tmp = __rb_parent(pc);
205 __rb_change_child(node, successor, tmp, root);
206 if (child2) {
207 successor->__rb_parent_color = pc;
208 rb_set_parent_color(child2, parent, RB_BLACK);
209 rebalance = NULL;
210 } else {
211 unsigned long pc2 = successor->__rb_parent_color;
212 successor->__rb_parent_color = pc;
213 rebalance = __rb_is_black(pc2) ? parent : NULL;
214 }
215 tmp = successor;
216 }
217
218 augment->propagate(tmp, NULL);
219 if (rebalance)
220 __rb_erase_color(rebalance, root, augment->rotate);
221}
222
223#endif /* _LINUX_RBTREE_AUGMENTED_H */
diff --git a/lib/rbtree.c b/lib/rbtree.c
index c0088ca345f9..4f56a11d67fa 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -21,7 +21,7 @@
21 linux/lib/rbtree.c 21 linux/lib/rbtree.c
22*/ 22*/
23 23
24#include <linux/rbtree.h> 24#include <linux/rbtree_augmented.h>
25#include <linux/export.h> 25#include <linux/export.h>
26 26
27/* 27/*
@@ -44,52 +44,16 @@
44 * parentheses and have some accompanying text comment. 44 * parentheses and have some accompanying text comment.
45 */ 45 */
46 46
47#define RB_RED 0
48#define RB_BLACK 1
49
50#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
51
52#define __rb_color(pc) ((pc) & 1)
53#define __rb_is_black(pc) __rb_color(pc)
54#define __rb_is_red(pc) (!__rb_color(pc))
55#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
56#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
57#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
58
59static inline void rb_set_black(struct rb_node *rb) 47static inline void rb_set_black(struct rb_node *rb)
60{ 48{
61 rb->__rb_parent_color |= RB_BLACK; 49 rb->__rb_parent_color |= RB_BLACK;
62} 50}
63 51
64static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
65{
66 rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
67}
68
69static inline void rb_set_parent_color(struct rb_node *rb,
70 struct rb_node *p, int color)
71{
72 rb->__rb_parent_color = (unsigned long)p | color;
73}
74
75static inline struct rb_node *rb_red_parent(struct rb_node *red) 52static inline struct rb_node *rb_red_parent(struct rb_node *red)
76{ 53{
77 return (struct rb_node *)red->__rb_parent_color; 54 return (struct rb_node *)red->__rb_parent_color;
78} 55}
79 56
80static inline void
81__rb_change_child(struct rb_node *old, struct rb_node *new,
82 struct rb_node *parent, struct rb_root *root)
83{
84 if (parent) {
85 if (parent->rb_left == old)
86 parent->rb_left = new;
87 else
88 parent->rb_right = new;
89 } else
90 root->rb_node = new;
91}
92
93/* 57/*
94 * Helper function for rotations: 58 * Helper function for rotations:
95 * - old's parent and color get assigned to new 59 * - old's parent and color get assigned to new
@@ -230,9 +194,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
230 } 194 }
231} 195}
232 196
233static __always_inline void 197__always_inline void
234__rb_erase_color(struct rb_node *parent, struct rb_root *root, 198__rb_erase_color(struct rb_node *parent, struct rb_root *root,
235 const struct rb_augment_callbacks *augment) 199 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
236{ 200{
237 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; 201 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
238 202
@@ -261,7 +225,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
261 rb_set_parent_color(tmp1, parent, RB_BLACK); 225 rb_set_parent_color(tmp1, parent, RB_BLACK);
262 __rb_rotate_set_parents(parent, sibling, root, 226 __rb_rotate_set_parents(parent, sibling, root,
263 RB_RED); 227 RB_RED);
264 augment->rotate(parent, sibling); 228 augment_rotate(parent, sibling);
265 sibling = tmp1; 229 sibling = tmp1;
266 } 230 }
267 tmp1 = sibling->rb_right; 231 tmp1 = sibling->rb_right;
@@ -313,7 +277,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
313 if (tmp1) 277 if (tmp1)
314 rb_set_parent_color(tmp1, sibling, 278 rb_set_parent_color(tmp1, sibling,
315 RB_BLACK); 279 RB_BLACK);
316 augment->rotate(sibling, tmp2); 280 augment_rotate(sibling, tmp2);
317 tmp1 = sibling; 281 tmp1 = sibling;
318 sibling = tmp2; 282 sibling = tmp2;
319 } 283 }
@@ -336,7 +300,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
336 rb_set_parent(tmp2, parent); 300 rb_set_parent(tmp2, parent);
337 __rb_rotate_set_parents(parent, sibling, root, 301 __rb_rotate_set_parents(parent, sibling, root,
338 RB_BLACK); 302 RB_BLACK);
339 augment->rotate(parent, sibling); 303 augment_rotate(parent, sibling);
340 break; 304 break;
341 } else { 305 } else {
342 sibling = parent->rb_left; 306 sibling = parent->rb_left;
@@ -347,7 +311,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
347 rb_set_parent_color(tmp1, parent, RB_BLACK); 311 rb_set_parent_color(tmp1, parent, RB_BLACK);
348 __rb_rotate_set_parents(parent, sibling, root, 312 __rb_rotate_set_parents(parent, sibling, root,
349 RB_RED); 313 RB_RED);
350 augment->rotate(parent, sibling); 314 augment_rotate(parent, sibling);
351 sibling = tmp1; 315 sibling = tmp1;
352 } 316 }
353 tmp1 = sibling->rb_left; 317 tmp1 = sibling->rb_left;
@@ -374,7 +338,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
374 if (tmp1) 338 if (tmp1)
375 rb_set_parent_color(tmp1, sibling, 339 rb_set_parent_color(tmp1, sibling,
376 RB_BLACK); 340 RB_BLACK);
377 augment->rotate(sibling, tmp2); 341 augment_rotate(sibling, tmp2);
378 tmp1 = sibling; 342 tmp1 = sibling;
379 sibling = tmp2; 343 sibling = tmp2;
380 } 344 }
@@ -386,109 +350,12 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
386 rb_set_parent(tmp2, parent); 350 rb_set_parent(tmp2, parent);
387 __rb_rotate_set_parents(parent, sibling, root, 351 __rb_rotate_set_parents(parent, sibling, root,
388 RB_BLACK); 352 RB_BLACK);
389 augment->rotate(parent, sibling); 353 augment_rotate(parent, sibling);
390 break; 354 break;
391 } 355 }
392 } 356 }
393} 357}
394 358EXPORT_SYMBOL(__rb_erase_color);
395static __always_inline void
396__rb_erase(struct rb_node *node, struct rb_root *root,
397 const struct rb_augment_callbacks *augment)
398{
399 struct rb_node *child = node->rb_right, *tmp = node->rb_left;
400 struct rb_node *parent, *rebalance;
401 unsigned long pc;
402
403 if (!tmp) {
404 /*
405 * Case 1: node to erase has no more than 1 child (easy!)
406 *
407 * Note that if there is one child it must be red due to 5)
408 * and node must be black due to 4). We adjust colors locally
409 * so as to bypass __rb_erase_color() later on.
410 */
411 pc = node->__rb_parent_color;
412 parent = __rb_parent(pc);
413 __rb_change_child(node, child, parent, root);
414 if (child) {
415 child->__rb_parent_color = pc;
416 rebalance = NULL;
417 } else
418 rebalance = __rb_is_black(pc) ? parent : NULL;
419 tmp = parent;
420 } else if (!child) {
421 /* Still case 1, but this time the child is node->rb_left */
422 tmp->__rb_parent_color = pc = node->__rb_parent_color;
423 parent = __rb_parent(pc);
424 __rb_change_child(node, tmp, parent, root);
425 rebalance = NULL;
426 tmp = parent;
427 } else {
428 struct rb_node *successor = child, *child2;
429 tmp = child->rb_left;
430 if (!tmp) {
431 /*
432 * Case 2: node's successor is its right child
433 *
434 * (n) (s)
435 * / \ / \
436 * (x) (s) -> (x) (c)
437 * \
438 * (c)
439 */
440 parent = successor;
441 child2 = successor->rb_right;
442 augment->copy(node, successor);
443 } else {
444 /*
445 * Case 3: node's successor is leftmost under
446 * node's right child subtree
447 *
448 * (n) (s)
449 * / \ / \
450 * (x) (y) -> (x) (y)
451 * / /
452 * (p) (p)
453 * / /
454 * (s) (c)
455 * \
456 * (c)
457 */
458 do {
459 parent = successor;
460 successor = tmp;
461 tmp = tmp->rb_left;
462 } while (tmp);
463 parent->rb_left = child2 = successor->rb_right;
464 successor->rb_right = child;
465 rb_set_parent(child, successor);
466 augment->copy(node, successor);
467 augment->propagate(parent, successor);
468 }
469
470 successor->rb_left = tmp = node->rb_left;
471 rb_set_parent(tmp, successor);
472
473 pc = node->__rb_parent_color;
474 tmp = __rb_parent(pc);
475 __rb_change_child(node, successor, tmp, root);
476 if (child2) {
477 successor->__rb_parent_color = pc;
478 rb_set_parent_color(child2, parent, RB_BLACK);
479 rebalance = NULL;
480 } else {
481 unsigned long pc2 = successor->__rb_parent_color;
482 successor->__rb_parent_color = pc;
483 rebalance = __rb_is_black(pc2) ? parent : NULL;
484 }
485 tmp = successor;
486 }
487
488 augment->propagate(tmp, NULL);
489 if (rebalance)
490 __rb_erase_color(rebalance, root, augment);
491}
492 359
493/* 360/*
494 * Non-augmented rbtree manipulation functions. 361 * Non-augmented rbtree manipulation functions.
@@ -513,7 +380,7 @@ EXPORT_SYMBOL(rb_insert_color);
513 380
514void rb_erase(struct rb_node *node, struct rb_root *root) 381void rb_erase(struct rb_node *node, struct rb_root *root)
515{ 382{
516 __rb_erase(node, root, &dummy_callbacks); 383 rb_erase_augmented(node, root, &dummy_callbacks);
517} 384}
518EXPORT_SYMBOL(rb_erase); 385EXPORT_SYMBOL(rb_erase);
519 386
@@ -531,13 +398,6 @@ void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
531} 398}
532EXPORT_SYMBOL(__rb_insert_augmented); 399EXPORT_SYMBOL(__rb_insert_augmented);
533 400
534void rb_erase_augmented(struct rb_node *node, struct rb_root *root,
535 const struct rb_augment_callbacks *augment)
536{
537 __rb_erase(node, root, augment);
538}
539EXPORT_SYMBOL(rb_erase_augmented);
540
541/* 401/*
542 * This function returns the first node (in sort order) of the tree. 402 * This function returns the first node (in sort order) of the tree.
543 */ 403 */
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index b20e99969b0f..268b23951fec 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -1,5 +1,5 @@
1#include <linux/module.h> 1#include <linux/module.h>
2#include <linux/rbtree.h> 2#include <linux/rbtree_augmented.h>
3#include <linux/random.h> 3#include <linux/random.h>
4#include <asm/timex.h> 4#include <asm/timex.h>
5 5
generated by cgit v1.2.2 (git 2.25.0) at 2025-08-11 08:12:55 -0400