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 = rb_parent(node);
30 if ((node->rb_right = right->rb_left))
31 rb_set_parent(right->rb_left, node);
32 right->rb_left = node;
38 if (node == parent->rb_left)
45 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 = rb_parent(node);
53 if ((node->rb_left = left->rb_right))
54 rb_set_parent(left->rb_right, node);
55 left->rb_right = node;
61 if (node == parent->rb_right)
68 rb_set_parent(node, left);
71 void rb_insert_color(struct rb_node *node, struct rb_root *root)
75 while ((parent = rb_parent(node)) && 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 || rb_is_black(node)) && node != root->rb_node)
143 if (parent->rb_left == node)
157 node = parent;
158 parent = rb_parent(node);
176 node = root->rb_node;
194 node = parent;
195 parent = rb_parent(node);
213 node = root->rb_node;
218 if (node)
219 rb_set_black(node);
222 void rb_erase(struct rb_node *node, struct rb_root *root)
227 if (!node->rb_left)
228 child = node->rb_right;
229 else if (!node->rb_right)
230 child = node->rb_left;
233 struct rb_node *old = node, *left;
235 node = node->rb_right;
236 while ((left = node->rb_left) != NULL)
237 node = left;
238 child = node->rb_right;
239 parent = rb_parent(node);
240 color = rb_color(node);
246 parent = node;
250 node->rb_parent_color = old->rb_parent_color;
251 node->rb_right = old->rb_right;
252 node->rb_left = old->rb_left;
257 rb_parent(old)->rb_left = node;
259 rb_parent(old)->rb_right = node;
261 root->rb_node = node;
263 rb_set_parent(old->rb_left, node);
265 rb_set_parent(old->rb_right, node);
269 parent = rb_parent(node);
270 color = rb_color(node);
276 if (parent->rb_left == node)
290 * This function returns the first node (in sort order) of the tree.
304 struct rb_node *rb_next(const struct rb_node *node)
308 if (RB_EMPTY_NODE(node))
315 if (node->rb_right) {
316 node = node->rb_right;
317 while (node->rb_left)
318 node=node->rb_left;
319 return (struct rb_node *)node;
324 * so any 'next' node must be in the general direction of our parent.
327 * parent, said parent is our 'next' node.
329 while ((parent = rb_parent(node)) && node == parent->rb_right)
330 node = parent;
