Lines Matching refs:node
25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27 struct rb_node *right = node->rb_right;
28 struct rb_node *parent = ext2fs_rb_parent(node);
30 if ((node->rb_right = right->rb_left))
31 ext2fs_rb_set_parent(right->rb_left, node);
32 right->rb_left = node;
38 if (node == parent->rb_left)
45 ext2fs_rb_set_parent(node, right);
48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
50 struct rb_node *left = node->rb_left;
51 struct rb_node *parent = ext2fs_rb_parent(node);
53 if ((node->rb_left = left->rb_right))
54 ext2fs_rb_set_parent(left->rb_right, node);
55 left->rb_right = node;
61 if (node == parent->rb_right)
68 ext2fs_rb_set_parent(node, left);
71 void ext2fs_rb_insert_color(struct rb_node *node, struct rb_root *root)
75 while ((parent = ext2fs_rb_parent(node)) && ext2fs_rb_is_red(parent))
88 node = gparent;
93 if (parent->rb_right == node)
98 parent = node;
99 node = tmp;
113 node = gparent;
118 if (parent->rb_left == node)
123 parent = node;
124 node = tmp;
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
141 while ((!node || ext2fs_rb_is_black(node)) && node != root->rb_node)
143 if (parent->rb_left == node)
157 node = parent;
158 parent = ext2fs_rb_parent(node);
173 node = root->rb_node;
191 node = parent;
192 parent = ext2fs_rb_parent(node);
207 node = root->rb_node;
212 if (node)
213 ext2fs_rb_set_black(node);
216 void ext2fs_rb_erase(struct rb_node *node, struct rb_root *root)
221 if (!node->rb_left)
222 child = node->rb_right;
223 else if (!node->rb_right)
224 child = node->rb_left;
227 struct rb_node *old = node, *left;
229 node = node->rb_right;
230 while ((left = node->rb_left) != NULL)
231 node = left;
235 ext2fs_rb_parent(old)->rb_left = node;
237 ext2fs_rb_parent(old)->rb_right = node;
239 root->rb_node = node;
241 child = node->rb_right;
242 parent = ext2fs_rb_parent(node);
243 color = ext2fs_rb_color(node);
246 parent = node;
252 node->rb_right = old->rb_right;
253 ext2fs_rb_set_parent(old->rb_right, node);
256 node->rb_parent_color = old->rb_parent_color;
257 node->rb_left = old->rb_left;
258 ext2fs_rb_set_parent(old->rb_left, node);
263 parent = ext2fs_rb_parent(node);
264 color = ext2fs_rb_color(node);
270 if (parent->rb_left == node)
283 static void ext2fs_rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
288 func(node, data);
289 parent = ext2fs_rb_parent(node);
293 if (node == parent->rb_left && parent->rb_right)
298 node = parent;
303 * after inserting @node into the tree, update the tree to account for
306 void ext2fs_rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
308 if (node->rb_left)
309 node = node->rb_left;
310 else if (node->rb_right)
311 node = node->rb_right;
313 ext2fs_rb_augment_path(node, func, data);
317 * before removing the node, find the deepest node on the rebalance path
318 * that will still be there after @node gets removed
320 struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node)
324 if (!node->rb_right && !node->rb_left)
325 deepest = ext2fs_rb_parent(node);
326 else if (!node->rb_right)
327 deepest = node->rb_left;
328 else if (!node->rb_left)
329 deepest = node->rb_right;
331 deepest = ext2fs_rb_next(node);
334 else if (ext2fs_rb_parent(deepest) != node)
345 void ext2fs_rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
347 if (node)
348 ext2fs_rb_augment_path(node, func, data);
352 * This function returns the first node (in sort order) of the tree.
378 struct rb_node *ext2fs_rb_next(struct rb_node *node)
382 if (ext2fs_rb_parent(node) == node)
387 if (node->rb_right) {
388 node = node->rb_right;
389 while (node->rb_left)
390 node=node->rb_left;
391 return (struct rb_node *)node;
395 smaller than us, so any 'next' node must be in the general
399 parent is our 'next' node. */
400 while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_right)
401 node = parent;
406 struct rb_node *ext2fs_rb_prev(struct rb_node *node)
410 if (ext2fs_rb_parent(node) == node)
415 if (node->rb_left) {
416 node = node->rb_left;
417 while (node->rb_right)
418 node=node->rb_right;
419 return (struct rb_node *)node;
424 while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_left)
425 node = parent;
