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>
31 * Please note - only struct rb_augment_callbacks and the prototypes for
32 * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
33 * The rest are implementation details you are not expected to depend on.
35 * See Documentation/rbtree.txt for documentation and samples.
38 struct rb_augment_callbacks
{
39 void (*propagate
)(struct rb_node
*node
, struct rb_node
*stop
);
40 void (*copy
)(struct rb_node
*old
, struct rb_node
*new);
41 void (*rotate
)(struct rb_node
*old
, struct rb_node
*new);
44 extern void __rb_insert_augmented(struct rb_node
*node
, struct rb_root
*root
,
45 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
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
);
53 #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
54 rbtype, rbaugmented, rbcompute) \
56 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
58 while (rb != stop) { \
59 rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
60 rbtype augmented = rbcompute(node); \
61 if (node->rbaugmented == augmented) \
63 node->rbaugmented = augmented; \
64 rb = rb_parent(&node->rbfield); \
68 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
70 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
71 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
72 new->rbaugmented = old->rbaugmented; \
75 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
77 rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
78 rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
79 new->rbaugmented = old->rbaugmented; \
80 old->rbaugmented = rbcompute(old); \
82 rbstatic const struct rb_augment_callbacks rbname = { \
83 rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
90 #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
92 #define __rb_color(pc) ((pc) & 1)
93 #define __rb_is_black(pc) __rb_color(pc)
94 #define __rb_is_red(pc) (!__rb_color(pc))
95 #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
96 #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
97 #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
99 static inline void rb_set_parent(struct rb_node
*rb
, struct rb_node
*p
)
101 rb
->__rb_parent_color
= rb_color(rb
) | (unsigned long)p
;
104 static inline void rb_set_parent_color(struct rb_node
*rb
,
105 struct rb_node
*p
, int color
)
107 rb
->__rb_parent_color
= (unsigned long)p
| color
;
111 __rb_change_child(struct rb_node
*old
, struct rb_node
*new,
112 struct rb_node
*parent
, struct rb_root
*root
)
115 if (parent
->rb_left
== old
)
116 parent
->rb_left
= new;
118 parent
->rb_right
= new;
123 extern void __rb_erase_color(struct rb_node
*parent
, struct rb_root
*root
,
124 void (*augment_rotate
)(struct rb_node
*old
, struct rb_node
*new));
126 static __always_inline
void
127 rb_erase_augmented(struct rb_node
*node
, struct rb_root
*root
,
128 const struct rb_augment_callbacks
*augment
)
130 struct rb_node
*child
= node
->rb_right
, *tmp
= node
->rb_left
;
131 struct rb_node
*parent
, *rebalance
;
136 * Case 1: node to erase has no more than 1 child (easy!)
138 * Note that if there is one child it must be red due to 5)
139 * and node must be black due to 4). We adjust colors locally
140 * so as to bypass __rb_erase_color() later on.
142 pc
= node
->__rb_parent_color
;
143 parent
= __rb_parent(pc
);
144 __rb_change_child(node
, child
, parent
, root
);
146 child
->__rb_parent_color
= pc
;
149 rebalance
= __rb_is_black(pc
) ? parent
: NULL
;
152 /* Still case 1, but this time the child is node->rb_left */
153 tmp
->__rb_parent_color
= pc
= node
->__rb_parent_color
;
154 parent
= __rb_parent(pc
);
155 __rb_change_child(node
, tmp
, parent
, root
);
159 struct rb_node
*successor
= child
, *child2
;
160 tmp
= child
->rb_left
;
163 * Case 2: node's successor is its right child
172 child2
= successor
->rb_right
;
173 augment
->copy(node
, successor
);
176 * Case 3: node's successor is leftmost under
177 * node's right child subtree
194 parent
->rb_left
= child2
= successor
->rb_right
;
195 successor
->rb_right
= child
;
196 rb_set_parent(child
, successor
);
197 augment
->copy(node
, successor
);
198 augment
->propagate(parent
, successor
);
201 successor
->rb_left
= tmp
= node
->rb_left
;
202 rb_set_parent(tmp
, successor
);
204 pc
= node
->__rb_parent_color
;
205 tmp
= __rb_parent(pc
);
206 __rb_change_child(node
, successor
, tmp
, root
);
208 successor
->__rb_parent_color
= pc
;
209 rb_set_parent_color(child2
, parent
, RB_BLACK
);
212 unsigned long pc2
= successor
->__rb_parent_color
;
213 successor
->__rb_parent_color
= pc
;
214 rebalance
= __rb_is_black(pc2
) ? parent
: NULL
;
219 augment
->propagate(tmp
, NULL
);
221 __rb_erase_color(rebalance
, root
, augment
->rotate
);
224 #endif /* _LINUX_RBTREE_AUGMENTED_H */
This page took 0.036352 seconds and 6 git commands to generate.