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/rbtree.h>
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.
34 * See Documentation/rbtree.txt for documentation and samples.
37 struct 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);
43 extern void __rb_insert_augmented(struct rb_node
*node
, struct rb_root
*root
,
44 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
46 rb_insert_augmented(struct rb_node
*node
, struct rb_root
*root
,
47 const struct rb_augment_callbacks
*augment
)
49 __rb_insert_augmented(node
, root
, augment
->rotate
);
52 #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
53 rbtype, rbaugmented, rbcompute) \
55 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
57 while (rb != stop) { \
58 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
59 rbtype augmented = rbcompute(node); \
60 if (node->rbaugmented == augmented) \
62 node->rbaugmented = augmented; \
63 rb = rb_parent(&node->rbfield); \
67 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
69 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
70 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
71 new->rbaugmented = old->rbaugmented; \
74 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
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); \
81 rbstatic const struct rb_augment_callbacks rbname = { \
82 rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
89 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
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)
98 static inline void rb_set_parent(struct rb_node
*rb
, struct rb_node
*p
)
100 rb
->__rb_parent_color
= rb_color(rb
) | (unsigned long)p
;
103 static inline void rb_set_parent_color(struct rb_node
*rb
,
104 struct rb_node
*p
, int color
)
106 rb
->__rb_parent_color
= (unsigned long)p
| color
;
110 __rb_change_child(struct rb_node
*old
, struct rb_node
*new,
111 struct rb_node
*parent
, struct rb_root
*root
)
114 if (parent
->rb_left
== old
)
115 parent
->rb_left
= new;
117 parent
->rb_right
= new;
122 extern void __rb_erase_color(struct rb_node
*parent
, struct rb_root
*root
,
123 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
125 static __always_inline
void
126 rb_erase_augmented(struct rb_node
*node
, struct rb_root
*root
,
127 const struct rb_augment_callbacks
*augment
)
129 struct rb_node
*child
= node
->rb_right
, *tmp
= node
->rb_left
;
130 struct rb_node
*parent
, *rebalance
;
135 * Case 1: node to erase has no more than 1 child (easy!)
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.
141 pc
= node
->__rb_parent_color
;
142 parent
= __rb_parent(pc
);
143 __rb_change_child(node
, child
, parent
, root
);
145 child
->__rb_parent_color
= pc
;
148 rebalance
= __rb_is_black(pc
) ? parent
: NULL
;
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
);
158 struct rb_node
*successor
= child
, *child2
;
159 tmp
= child
->rb_left
;
162 * Case 2: node's successor is its right child
171 child2
= successor
->rb_right
;
172 augment
->copy(node
, successor
);
175 * Case 3: node's successor is leftmost under
176 * node's right child subtree
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
);
200 successor
->rb_left
= tmp
= node
->rb_left
;
201 rb_set_parent(tmp
, successor
);
203 pc
= node
->__rb_parent_color
;
204 tmp
= __rb_parent(pc
);
205 __rb_change_child(node
, successor
, tmp
, root
);
207 successor
->__rb_parent_color
= pc
;
208 rb_set_parent_color(child2
, parent
, RB_BLACK
);
211 unsigned long pc2
= successor
->__rb_parent_color
;
212 successor
->__rb_parent_color
= pc
;
213 rebalance
= __rb_is_black(pc2
) ? parent
: NULL
;
218 augment
->propagate(tmp
, NULL
);
220 __rb_erase_color(rebalance
, root
, augment
->rotate
);
223 #endif /* _LINUX_RBTREE_AUGMENTED_H */