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, struct rb_root *root,
34 void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
37 * Fixup the rbtree and update the augmented information when rebalancing.
39 * On insertion, the user must update the augmented information on the path
40 * leading to the inserted node, then call rb_link_node() as usual and
41 * rb_insert_augmented() instead of the usual rb_insert_color() call.
42 * If rb_insert_augmented() rebalances the rbtree, it will callback into
43 * a user provided function to update the augmented information on the
47 rb_insert_augmented(struct rb_node *node, struct rb_root *root,
48 const struct rb_augment_callbacks *augment)
50 __rb_insert_augmented(node, root, augment->rotate);
54 rb_insert_augmented_cached(struct rb_node *node,
55 struct rb_root_cached *root, bool newleft,
56 const struct rb_augment_callbacks *augment)
59 root->rb_leftmost = node;
60 rb_insert_augmented(node, &root->rb_root, augment);
64 * Template for declaring augmented rbtree callbacks
66 * RBSTATIC: 'static' or empty
67 * RBNAME: name of the rb_augment_callbacks structure
68 * RBSTRUCT: struct type of the tree nodes
69 * RBFIELD: name of struct rb_node field within RBSTRUCT
70 * RBTYPE: type of the RBAUGMENTED field
71 * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
72 * RBCOMPUTE: name of function that recomputes the RBAUGMENTED data
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 const struct rb_augment_callbacks *augment)
167 struct rb_node *child = node->rb_right;
168 struct rb_node *tmp = node->rb_left;
169 struct rb_node *parent, *rebalance;
174 * Case 1: node to erase has no more than 1 child (easy!)
176 * Note that if there is one child it must be red due to 5)
177 * and node must be black due to 4). We adjust colors locally
178 * so as to bypass __rb_erase_color() later on.
180 pc = node->__rb_parent_color;
181 parent = __rb_parent(pc);
182 __rb_change_child(node, child, parent, root);
184 child->__rb_parent_color = pc;
187 rebalance = __rb_is_black(pc) ? parent : NULL;
190 /* Still case 1, but this time the child is node->rb_left */
191 tmp->__rb_parent_color = pc = node->__rb_parent_color;
192 parent = __rb_parent(pc);
193 __rb_change_child(node, tmp, parent, root);
197 struct rb_node *successor = child, *child2;
199 tmp = child->rb_left;
202 * Case 2: node's successor is its right child
211 child2 = successor->rb_right;
213 augment->copy(node, successor);
216 * Case 3: node's successor is leftmost under
217 * node's right child subtree
234 child2 = successor->rb_right;
235 WRITE_ONCE(parent->rb_left, child2);
236 WRITE_ONCE(successor->rb_right, child);
237 rb_set_parent(child, successor);
239 augment->copy(node, successor);
240 augment->propagate(parent, successor);
244 WRITE_ONCE(successor->rb_left, tmp);
245 rb_set_parent(tmp, successor);
247 pc = node->__rb_parent_color;
248 tmp = __rb_parent(pc);
249 __rb_change_child(node, successor, tmp, root);
252 successor->__rb_parent_color = pc;
253 rb_set_parent_color(child2, parent, RB_BLACK);
256 unsigned long pc2 = successor->__rb_parent_color;
257 successor->__rb_parent_color = pc;
258 rebalance = __rb_is_black(pc2) ? parent : NULL;
263 augment->propagate(tmp, NULL);
267 static __always_inline void
268 rb_erase_augmented(struct rb_node *node, struct rb_root *root,
269 const struct rb_augment_callbacks *augment)
271 struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
273 __rb_erase_color(rebalance, root, augment->rotate);
276 static __always_inline void
277 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
278 const struct rb_augment_callbacks *augment)
280 if (root->rb_leftmost == node)
281 root->rb_leftmost = rb_next(node);
282 rb_erase_augmented(node, &root->rb_root, augment);
285 #endif /* _LINUX_RBTREE_AUGMENTED_H */