Rev 5270 | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 5270 | Rev 6082 | ||
|---|---|---|---|
| Line 121... | Line 121... | ||
| 121 | __rb_change_child(struct rb_node *old, struct rb_node *new, |
121 | __rb_change_child(struct rb_node *old, struct rb_node *new, |
| 122 | struct rb_node *parent, struct rb_root *root) |
122 | struct rb_node *parent, struct rb_root *root) |
| 123 | { |
123 | { |
| 124 | if (parent) { |
124 | if (parent) { |
| 125 | if (parent->rb_left == old) |
125 | if (parent->rb_left == old) |
| 126 | parent->rb_left = new; |
126 | WRITE_ONCE(parent->rb_left, new); |
| 127 | else |
127 | else |
| 128 | parent->rb_right = new; |
128 | WRITE_ONCE(parent->rb_right, new); |
| 129 | } else |
129 | } else |
| 130 | root->rb_node = new; |
130 | WRITE_ONCE(root->rb_node, new); |
| 131 | } |
131 | } |
| Line 132... | Line 132... | ||
| 132 | 132 | ||
| 133 | extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, |
133 | extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, |
| Line 134... | Line 134... | ||
| 134 | void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); |
134 | void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); |
| 135 | 135 | ||
| 136 | static __always_inline struct rb_node * |
136 | static __always_inline struct rb_node * |
| 137 | __rb_erase_augmented(struct rb_node *node, struct rb_root *root, |
137 | __rb_erase_augmented(struct rb_node *node, struct rb_root *root, |
| 138 | const struct rb_augment_callbacks *augment) |
138 | const struct rb_augment_callbacks *augment) |
| - | 139 | { |
|
| 139 | { |
140 | struct rb_node *child = node->rb_right; |
| 140 | struct rb_node *child = node->rb_right, *tmp = node->rb_left; |
141 | struct rb_node *tmp = node->rb_left; |
| Line 141... | Line 142... | ||
| 141 | struct rb_node *parent, *rebalance; |
142 | struct rb_node *parent, *rebalance; |
| 142 | unsigned long pc; |
143 | unsigned long pc; |
| Line 165... | Line 166... | ||
| 165 | __rb_change_child(node, tmp, parent, root); |
166 | __rb_change_child(node, tmp, parent, root); |
| 166 | rebalance = NULL; |
167 | rebalance = NULL; |
| 167 | tmp = parent; |
168 | tmp = parent; |
| 168 | } else { |
169 | } else { |
| 169 | struct rb_node *successor = child, *child2; |
170 | struct rb_node *successor = child, *child2; |
| - | 171 | ||
| 170 | tmp = child->rb_left; |
172 | tmp = child->rb_left; |
| 171 | if (!tmp) { |
173 | if (!tmp) { |
| 172 | /* |
174 | /* |
| 173 | * Case 2: node's successor is its right child |
175 | * Case 2: node's successor is its right child |
| 174 | * |
176 | * |
| Line 178... | Line 180... | ||
| 178 | * \ |
180 | * \ |
| 179 | * (c) |
181 | * (c) |
| 180 | */ |
182 | */ |
| 181 | parent = successor; |
183 | parent = successor; |
| 182 | child2 = successor->rb_right; |
184 | child2 = successor->rb_right; |
| - | 185 | ||
| 183 | augment->copy(node, successor); |
186 | augment->copy(node, successor); |
| 184 | } else { |
187 | } else { |
| 185 | /* |
188 | /* |
| 186 | * Case 3: node's successor is leftmost under |
189 | * Case 3: node's successor is leftmost under |
| 187 | * node's right child subtree |
190 | * node's right child subtree |
| Line 199... | Line 202... | ||
| 199 | do { |
202 | do { |
| 200 | parent = successor; |
203 | parent = successor; |
| 201 | successor = tmp; |
204 | successor = tmp; |
| 202 | tmp = tmp->rb_left; |
205 | tmp = tmp->rb_left; |
| 203 | } while (tmp); |
206 | } while (tmp); |
| 204 | parent->rb_left = child2 = successor->rb_right; |
207 | child2 = successor->rb_right; |
| - | 208 | WRITE_ONCE(parent->rb_left, child2); |
|
| 205 | successor->rb_right = child; |
209 | WRITE_ONCE(successor->rb_right, child); |
| 206 | rb_set_parent(child, successor); |
210 | rb_set_parent(child, successor); |
| - | 211 | ||
| 207 | augment->copy(node, successor); |
212 | augment->copy(node, successor); |
| 208 | augment->propagate(parent, successor); |
213 | augment->propagate(parent, successor); |
| 209 | } |
214 | } |
| Line 210... | Line 215... | ||
| 210 | 215 | ||
| - | 216 | tmp = node->rb_left; |
|
| 211 | successor->rb_left = tmp = node->rb_left; |
217 | WRITE_ONCE(successor->rb_left, tmp); |
| Line 212... | Line 218... | ||
| 212 | rb_set_parent(tmp, successor); |
218 | rb_set_parent(tmp, successor); |
| 213 | 219 | ||
| 214 | pc = node->__rb_parent_color; |
220 | pc = node->__rb_parent_color; |
| - | 221 | tmp = __rb_parent(pc); |
|
| 215 | tmp = __rb_parent(pc); |
222 | __rb_change_child(node, successor, tmp, root); |
| 216 | __rb_change_child(node, successor, tmp, root); |
223 | |
| 217 | if (child2) { |
224 | if (child2) { |
| 218 | successor->__rb_parent_color = pc; |
225 | successor->__rb_parent_color = pc; |
| 219 | rb_set_parent_color(child2, parent, RB_BLACK); |
226 | rb_set_parent_color(child2, parent, RB_BLACK); |