Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mattst88...
[linux-2.6-microblaze.git] / include / linux / rbtree_augmented.h
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
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
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
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
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
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
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 *
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
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
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 */