Rev 4103 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4103 | Serge | 1 | /* |
2 | Red Black Trees |
||
3 | (C) 1999 Andrea Arcangeli |
||
4 | (C) 2002 David Woodhouse |
||
5 | (C) 2012 Michel Lespinasse |
||
6 | |||
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. |
||
11 | |||
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. |
||
16 | |||
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 |
||
20 | |||
21 | linux/include/linux/rbtree_augmented.h |
||
22 | */ |
||
23 | |||
24 | #ifndef _LINUX_RBTREE_AUGMENTED_H |
||
25 | #define _LINUX_RBTREE_AUGMENTED_H |
||
26 | |||
27 | #include |
||
28 | #include |
||
29 | |||
30 | /* |
||
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. |
||
34 | * |
||
35 | * See Documentation/rbtree.txt for documentation and samples. |
||
36 | */ |
||
37 | |||
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); |
||
42 | }; |
||
43 | |||
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)); |
||
5270 | serge | 46 | /* |
47 | * Fixup the rbtree and update the augmented information when rebalancing. |
||
48 | * |
||
49 | * On insertion, the user must update the augmented information on the path |
||
50 | * leading to the inserted node, then call rb_link_node() as usual and |
||
51 | * rb_augment_inserted() instead of the usual rb_insert_color() call. |
||
52 | * If rb_augment_inserted() rebalances the rbtree, it will callback into |
||
53 | * a user provided function to update the augmented information on the |
||
54 | * affected subtrees. |
||
55 | */ |
||
4103 | Serge | 56 | static inline void |
57 | rb_insert_augmented(struct rb_node *node, struct rb_root *root, |
||
58 | const struct rb_augment_callbacks *augment) |
||
59 | { |
||
60 | __rb_insert_augmented(node, root, augment->rotate); |
||
61 | } |
||
62 | |||
63 | #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \ |
||
64 | rbtype, rbaugmented, rbcompute) \ |
||
65 | static inline void \ |
||
66 | rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \ |
||
67 | { \ |
||
68 | while (rb != stop) { \ |
||
69 | rbstruct *node = rb_entry(rb, rbstruct, rbfield); \ |
||
70 | rbtype augmented = rbcompute(node); \ |
||
71 | if (node->rbaugmented == augmented) \ |
||
72 | break; \ |
||
73 | node->rbaugmented = augmented; \ |
||
74 | rb = rb_parent(&node->rbfield); \ |
||
75 | } \ |
||
76 | } \ |
||
77 | static inline void \ |
||
78 | rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \ |
||
79 | { \ |
||
80 | rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \ |
||
81 | rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \ |
||
82 | new->rbaugmented = old->rbaugmented; \ |
||
83 | } \ |
||
84 | static void \ |
||
85 | rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \ |
||
86 | { \ |
||
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); \ |
||
91 | } \ |
||
92 | rbstatic const struct rb_augment_callbacks rbname = { \ |
||
93 | rbname ## _propagate, rbname ## _copy, rbname ## _rotate \ |
||
94 | }; |
||
95 | |||
96 | |||
97 | #define RB_RED 0 |
||
98 | #define RB_BLACK 1 |
||
99 | |||
100 | #define __rb_parent(pc) ((struct rb_node *)(pc & ~3)) |
||
101 | |||
102 | #define __rb_color(pc) ((pc) & 1) |
||
103 | #define __rb_is_black(pc) __rb_color(pc) |
||
104 | #define __rb_is_red(pc) (!__rb_color(pc)) |
||
105 | #define rb_color(rb) __rb_color((rb)->__rb_parent_color) |
||
106 | #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color) |
||
107 | #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color) |
||
108 | |||
109 | static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) |
||
110 | { |
||
111 | rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; |
||
112 | } |
||
113 | |||
114 | static inline void rb_set_parent_color(struct rb_node *rb, |
||
115 | struct rb_node *p, int color) |
||
116 | { |
||
117 | rb->__rb_parent_color = (unsigned long)p | color; |
||
118 | } |
||
119 | |||
120 | static inline void |
||
121 | __rb_change_child(struct rb_node *old, struct rb_node *new, |
||
122 | struct rb_node *parent, struct rb_root *root) |
||
123 | { |
||
124 | if (parent) { |
||
125 | if (parent->rb_left == old) |
||
126 | parent->rb_left = new; |
||
127 | else |
||
128 | parent->rb_right = new; |
||
129 | } else |
||
130 | root->rb_node = new; |
||
131 | } |
||
132 | |||
133 | extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, |
||
134 | void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); |
||
135 | |||
136 | static __always_inline struct rb_node * |
||
137 | __rb_erase_augmented(struct rb_node *node, struct rb_root *root, |
||
138 | const struct rb_augment_callbacks *augment) |
||
139 | { |
||
140 | struct rb_node *child = node->rb_right, *tmp = node->rb_left; |
||
141 | struct rb_node *parent, *rebalance; |
||
142 | unsigned long pc; |
||
143 | |||
144 | if (!tmp) { |
||
145 | /* |
||
146 | * Case 1: node to erase has no more than 1 child (easy!) |
||
147 | * |
||
148 | * Note that if there is one child it must be red due to 5) |
||
149 | * and node must be black due to 4). We adjust colors locally |
||
150 | * so as to bypass __rb_erase_color() later on. |
||
151 | */ |
||
152 | pc = node->__rb_parent_color; |
||
153 | parent = __rb_parent(pc); |
||
154 | __rb_change_child(node, child, parent, root); |
||
155 | if (child) { |
||
156 | child->__rb_parent_color = pc; |
||
157 | rebalance = NULL; |
||
158 | } else |
||
159 | rebalance = __rb_is_black(pc) ? parent : NULL; |
||
160 | tmp = parent; |
||
161 | } else if (!child) { |
||
162 | /* Still case 1, but this time the child is node->rb_left */ |
||
163 | tmp->__rb_parent_color = pc = node->__rb_parent_color; |
||
164 | parent = __rb_parent(pc); |
||
165 | __rb_change_child(node, tmp, parent, root); |
||
166 | rebalance = NULL; |
||
167 | tmp = parent; |
||
168 | } else { |
||
169 | struct rb_node *successor = child, *child2; |
||
170 | tmp = child->rb_left; |
||
171 | if (!tmp) { |
||
172 | /* |
||
173 | * Case 2: node's successor is its right child |
||
174 | * |
||
175 | * (n) (s) |
||
176 | * / \ / \ |
||
177 | * (x) (s) -> (x) (c) |
||
178 | * \ |
||
179 | * (c) |
||
180 | */ |
||
181 | parent = successor; |
||
182 | child2 = successor->rb_right; |
||
183 | augment->copy(node, successor); |
||
184 | } else { |
||
185 | /* |
||
186 | * Case 3: node's successor is leftmost under |
||
187 | * node's right child subtree |
||
188 | * |
||
189 | * (n) (s) |
||
190 | * / \ / \ |
||
191 | * (x) (y) -> (x) (y) |
||
192 | * / / |
||
193 | * (p) (p) |
||
194 | * / / |
||
195 | * (s) (c) |
||
196 | * \ |
||
197 | * (c) |
||
198 | */ |
||
199 | do { |
||
200 | parent = successor; |
||
201 | successor = tmp; |
||
202 | tmp = tmp->rb_left; |
||
203 | } while (tmp); |
||
204 | parent->rb_left = child2 = successor->rb_right; |
||
205 | successor->rb_right = child; |
||
206 | rb_set_parent(child, successor); |
||
207 | augment->copy(node, successor); |
||
208 | augment->propagate(parent, successor); |
||
209 | } |
||
210 | |||
211 | successor->rb_left = tmp = node->rb_left; |
||
212 | rb_set_parent(tmp, successor); |
||
213 | |||
214 | pc = node->__rb_parent_color; |
||
215 | tmp = __rb_parent(pc); |
||
216 | __rb_change_child(node, successor, tmp, root); |
||
217 | if (child2) { |
||
218 | successor->__rb_parent_color = pc; |
||
219 | rb_set_parent_color(child2, parent, RB_BLACK); |
||
220 | rebalance = NULL; |
||
221 | } else { |
||
222 | unsigned long pc2 = successor->__rb_parent_color; |
||
223 | successor->__rb_parent_color = pc; |
||
224 | rebalance = __rb_is_black(pc2) ? parent : NULL; |
||
225 | } |
||
226 | tmp = successor; |
||
227 | } |
||
228 | |||
229 | augment->propagate(tmp, NULL); |
||
230 | return rebalance; |
||
231 | } |
||
232 | |||
233 | static __always_inline void |
||
234 | rb_erase_augmented(struct rb_node *node, struct rb_root *root, |
||
235 | const struct rb_augment_callbacks *augment) |
||
236 | { |
||
237 | struct rb_node *rebalance = __rb_erase_augmented(node, root, augment); |
||
238 | if (rebalance) |
||
239 | __rb_erase_color(rebalance, root, augment->rotate); |
||
240 | } |
||
241 | |||
242 | #endif /* _LINUX_RBTREE_AUGMENTED_H */ |