]>
git.ipfire.org Git - thirdparty/kernel/stable.git/blob - include/linux/rbtree_augmented.h
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
4 (C) 1999 Andrea Arcangeli <andrea@suse.de>
5 (C) 2002 David Woodhouse <dwmw2@infradead.org>
6 (C) 2012 Michel Lespinasse <walken@google.com>
9 linux/include/linux/rbtree_augmented.h
12 #ifndef _LINUX_RBTREE_AUGMENTED_H
13 #define _LINUX_RBTREE_AUGMENTED_H
15 #include <linux/compiler.h>
16 #include <linux/rbtree.h>
17 #include <linux/rcupdate.h>
20 * Please note - only struct rb_augment_callbacks and the prototypes for
21 * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
22 * The rest are implementation details you are not expected to depend on.
24 * See Documentation/rbtree.txt for documentation and samples.
27 struct rb_augment_callbacks
{
28 void (*propagate
)(struct rb_node
*node
, struct rb_node
*stop
);
29 void (*copy
)(struct rb_node
*old
, struct rb_node
*new);
30 void (*rotate
)(struct rb_node
*old
, struct rb_node
*new);
33 extern void __rb_insert_augmented(struct rb_node
*node
,
35 bool newleft
, struct rb_node
**leftmost
,
36 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
38 * Fixup the rbtree and update the augmented information when rebalancing.
40 * On insertion, the user must update the augmented information on the path
41 * leading to the inserted node, then call rb_link_node() as usual and
42 * rb_insert_augmented() instead of the usual rb_insert_color() call.
43 * If rb_insert_augmented() rebalances the rbtree, it will callback into
44 * a user provided function to update the augmented information on the
48 rb_insert_augmented(struct rb_node
*node
, struct rb_root
*root
,
49 const struct rb_augment_callbacks
*augment
)
51 __rb_insert_augmented(node
, root
, false, NULL
, augment
->rotate
);
55 rb_insert_augmented_cached(struct rb_node
*node
,
56 struct rb_root_cached
*root
, bool newleft
,
57 const struct rb_augment_callbacks
*augment
)
59 __rb_insert_augmented(node
, &root
->rb_root
,
60 newleft
, &root
->rb_leftmost
, augment
->rotate
);
63 #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
64 rbtype, rbaugmented, rbcompute) \
66 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
68 while (rb != stop) { \
69 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
70 rbtype augmented = rbcompute(node); \
71 if (node->rbaugmented == augmented) \
73 node->rbaugmented = augmented; \
74 rb = rb_parent(&node->rbfield); \
78 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
80 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
81 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
82 new->rbaugmented = old->rbaugmented; \
85 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
87 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
88 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
89 new->rbaugmented = old->rbaugmented; \
90 old->rbaugmented = rbcompute(old); \
92 rbstatic const struct rb_augment_callbacks rbname = { \
93 .propagate = rbname ## _propagate, \
94 .copy = rbname ## _copy, \
95 .rotate = rbname ## _rotate \
102 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
104 #define __rb_color(pc) ((pc) & 1)
105 #define __rb_is_black(pc) __rb_color(pc)
106 #define __rb_is_red(pc) (!__rb_color(pc))
107 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
108 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
109 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
111 static inline void rb_set_parent(struct rb_node
*rb
, struct rb_node
*p
)
113 rb
->__rb_parent_color
= rb_color(rb
) | (unsigned long)p
;
116 static inline void rb_set_parent_color(struct rb_node
*rb
,
117 struct rb_node
*p
, int color
)
119 rb
->__rb_parent_color
= (unsigned long)p
| color
;
123 __rb_change_child(struct rb_node
*old
, struct rb_node
*new,
124 struct rb_node
*parent
, struct rb_root
*root
)
127 if (parent
->rb_left
== old
)
128 WRITE_ONCE(parent
->rb_left
, new);
130 WRITE_ONCE(parent
->rb_right
, new);
132 WRITE_ONCE(root
->rb_node
, new);
136 __rb_change_child_rcu(struct rb_node
*old
, struct rb_node
*new,
137 struct rb_node
*parent
, struct rb_root
*root
)
140 if (parent
->rb_left
== old
)
141 rcu_assign_pointer(parent
->rb_left
, new);
143 rcu_assign_pointer(parent
->rb_right
, new);
145 rcu_assign_pointer(root
->rb_node
, new);
148 extern void __rb_erase_color(struct rb_node
*parent
, struct rb_root
*root
,
149 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
151 static __always_inline
struct rb_node
*
152 __rb_erase_augmented(struct rb_node
*node
, struct rb_root
*root
,
153 struct rb_node
**leftmost
,
154 const struct rb_augment_callbacks
*augment
)
156 struct rb_node
*child
= node
->rb_right
;
157 struct rb_node
*tmp
= node
->rb_left
;
158 struct rb_node
*parent
, *rebalance
;
161 if (leftmost
&& node
== *leftmost
)
162 *leftmost
= rb_next(node
);
166 * Case 1: node to erase has no more than 1 child (easy!)
168 * Note that if there is one child it must be red due to 5)
169 * and node must be black due to 4). We adjust colors locally
170 * so as to bypass __rb_erase_color() later on.
172 pc
= node
->__rb_parent_color
;
173 parent
= __rb_parent(pc
);
174 __rb_change_child(node
, child
, parent
, root
);
176 child
->__rb_parent_color
= pc
;
179 rebalance
= __rb_is_black(pc
) ? parent
: NULL
;
182 /* Still case 1, but this time the child is node->rb_left */
183 tmp
->__rb_parent_color
= pc
= node
->__rb_parent_color
;
184 parent
= __rb_parent(pc
);
185 __rb_change_child(node
, tmp
, parent
, root
);
189 struct rb_node
*successor
= child
, *child2
;
191 tmp
= child
->rb_left
;
194 * Case 2: node's successor is its right child
203 child2
= successor
->rb_right
;
205 augment
->copy(node
, successor
);
208 * Case 3: node's successor is leftmost under
209 * node's right child subtree
226 child2
= successor
->rb_right
;
227 WRITE_ONCE(parent
->rb_left
, child2
);
228 WRITE_ONCE(successor
->rb_right
, child
);
229 rb_set_parent(child
, successor
);
231 augment
->copy(node
, successor
);
232 augment
->propagate(parent
, successor
);
236 WRITE_ONCE(successor
->rb_left
, tmp
);
237 rb_set_parent(tmp
, successor
);
239 pc
= node
->__rb_parent_color
;
240 tmp
= __rb_parent(pc
);
241 __rb_change_child(node
, successor
, tmp
, root
);
244 successor
->__rb_parent_color
= pc
;
245 rb_set_parent_color(child2
, parent
, RB_BLACK
);
248 unsigned long pc2
= successor
->__rb_parent_color
;
249 successor
->__rb_parent_color
= pc
;
250 rebalance
= __rb_is_black(pc2
) ? parent
: NULL
;
255 augment
->propagate(tmp
, NULL
);
259 static __always_inline
void
260 rb_erase_augmented(struct rb_node
*node
, struct rb_root
*root
,
261 const struct rb_augment_callbacks
*augment
)
263 struct rb_node
*rebalance
= __rb_erase_augmented(node
, root
,
266 __rb_erase_color(rebalance
, root
, augment
->rotate
);
269 static __always_inline
void
270 rb_erase_augmented_cached(struct rb_node
*node
, struct rb_root_cached
*root
,
271 const struct rb_augment_callbacks
*augment
)
273 struct rb_node
*rebalance
= __rb_erase_augmented(node
, &root
->rb_root
,
277 __rb_erase_color(rebalance
, &root
->rb_root
, augment
->rotate
);
280 #endif /* _LINUX_RBTREE_AUGMENTED_H */