]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - include/linux/rbtree_augmented.h
3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 (C) 2012 Michel Lespinasse <walken@google.com>
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.
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.
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
21 linux/include/linux/rbtree_augmented.h
24 #ifndef _LINUX_RBTREE_AUGMENTED_H
25 #define _LINUX_RBTREE_AUGMENTED_H
27 #include <linux/compiler.h>
28 #include <linux/rbtree.h>
29 #include <linux/rcupdate.h>
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.
36 * See Documentation/rbtree.txt for documentation and samples.
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);
45 extern void __rb_insert_augmented(struct rb_node
*node
,
47 bool newleft
, struct rb_node
**leftmost
,
48 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
50 * Fixup the rbtree and update the augmented information when rebalancing.
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
60 rb_insert_augmented(struct rb_node
*node
, struct rb_root
*root
,
61 const struct rb_augment_callbacks
*augment
)
63 __rb_insert_augmented(node
, root
, false, NULL
, augment
->rotate
);
67 rb_insert_augmented_cached(struct rb_node
*node
,
68 struct rb_root_cached
*root
, bool newleft
,
69 const struct rb_augment_callbacks
*augment
)
71 __rb_insert_augmented(node
, &root
->rb_root
,
72 newleft
, &root
->rb_leftmost
, augment
->rotate
);
75 #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
76 rbtype, rbaugmented, rbcompute) \
78 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
80 while (rb != stop) { \
81 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
82 rbtype augmented = rbcompute(node); \
83 if (node->rbaugmented == augmented) \
85 node->rbaugmented = augmented; \
86 rb = rb_parent(&node->rbfield); \
90 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
92 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
93 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
94 new->rbaugmented = old->rbaugmented; \
97 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
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); \
104 rbstatic const struct rb_augment_callbacks rbname = { \
105 .propagate = rbname ## _propagate, \
106 .copy = rbname ## _copy, \
107 .rotate = rbname ## _rotate \
114 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
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)
123 static inline void rb_set_parent(struct rb_node
*rb
, struct rb_node
*p
)
125 rb
->__rb_parent_color
= rb_color(rb
) | (unsigned long)p
;
128 static inline void rb_set_parent_color(struct rb_node
*rb
,
129 struct rb_node
*p
, int color
)
131 rb
->__rb_parent_color
= (unsigned long)p
| color
;
135 __rb_change_child(struct rb_node
*old
, struct rb_node
*new,
136 struct rb_node
*parent
, struct rb_root
*root
)
139 if (parent
->rb_left
== old
)
140 WRITE_ONCE(parent
->rb_left
, new);
142 WRITE_ONCE(parent
->rb_right
, new);
144 WRITE_ONCE(root
->rb_node
, new);
148 __rb_change_child_rcu(struct rb_node
*old
, struct rb_node
*new,
149 struct rb_node
*parent
, struct rb_root
*root
)
152 if (parent
->rb_left
== old
)
153 rcu_assign_pointer(parent
->rb_left
, new);
155 rcu_assign_pointer(parent
->rb_right
, new);
157 rcu_assign_pointer(root
->rb_node
, new);
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));
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
)
168 struct rb_node
*child
= node
->rb_right
;
169 struct rb_node
*tmp
= node
->rb_left
;
170 struct rb_node
*parent
, *rebalance
;
173 if (leftmost
&& node
== *leftmost
)
174 *leftmost
= rb_next(node
);
178 * Case 1: node to erase has no more than 1 child (easy!)
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.
184 pc
= node
->__rb_parent_color
;
185 parent
= __rb_parent(pc
);
186 __rb_change_child(node
, child
, parent
, root
);
188 child
->__rb_parent_color
= pc
;
191 rebalance
= __rb_is_black(pc
) ? parent
: NULL
;
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
);
201 struct rb_node
*successor
= child
, *child2
;
203 tmp
= child
->rb_left
;
206 * Case 2: node's successor is its right child
215 child2
= successor
->rb_right
;
217 augment
->copy(node
, successor
);
220 * Case 3: node's successor is leftmost under
221 * node's right child subtree
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
);
243 augment
->copy(node
, successor
);
244 augment
->propagate(parent
, successor
);
248 WRITE_ONCE(successor
->rb_left
, tmp
);
249 rb_set_parent(tmp
, successor
);
251 pc
= node
->__rb_parent_color
;
252 tmp
= __rb_parent(pc
);
253 __rb_change_child(node
, successor
, tmp
, root
);
256 successor
->__rb_parent_color
= pc
;
257 rb_set_parent_color(child2
, parent
, RB_BLACK
);
260 unsigned long pc2
= successor
->__rb_parent_color
;
261 successor
->__rb_parent_color
= pc
;
262 rebalance
= __rb_is_black(pc2
) ? parent
: NULL
;
267 augment
->propagate(tmp
, NULL
);
271 static __always_inline
void
272 rb_erase_augmented(struct rb_node
*node
, struct rb_root
*root
,
273 const struct rb_augment_callbacks
*augment
)
275 struct rb_node
*rebalance
= __rb_erase_augmented(node
, root
,
278 __rb_erase_color(rebalance
, root
, augment
->rotate
);
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
)
285 struct rb_node
*rebalance
= __rb_erase_augmented(node
, &root
->rb_root
,
289 __rb_erase_color(rebalance
, &root
->rb_root
, augment
->rotate
);
292 #endif /* _LINUX_RBTREE_AUGMENTED_H */