aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux
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 /include/linux
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 (limited to 'include/linux')
-rw-r--r--include/linux/interval_tree_tmpl.h8
-rw-r--r--include/linux/rbtree.h48
-rw-r--r--include/linux/rbtree_augmented.h223
3 files changed, 229 insertions, 50 deletions
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 */
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-25 02:18:26 -0500